449
紹 介
・−− ざ3一一・
部分基底法一退化輸送問題の解法（1）
瀬 戸 広 明
1．はしがき
2け 輸送問題とその退化解法 2．1 問題
2．．2 通常のMODI法 2，．3柿動法
2．4 部分基底法及びその計野手続（以上本号）
31．電子計算機による計静例 3・1稀動法
3。2 部分基底法（以上41巻3号予定）
1、ほ し が き
本稿はMadanLalMittal ANote on Resolution o．fPegeneracyin TY a71Sbor P′〃∂Jβ雛ぶ〃0♪gγα如〝αJ斤βざβ〃γCカQ〝αγ才βγJ．γぴ〃J一．18，Ⅳ〃．2，一／〝〝β1967，♪♪175仙184の 紹介である。
退化輸送問題の解法として−は締動法（Perturbation Techniques）がよく知られて る。掘動法に対するMittalの方法の特長は次の点にある。すなわち，繍動法においては，
ステップ毎に基底を構成しているベクトルを1つずつ入れかえるのであるが，Mittalの方 法では，同一・ステップで，入れかえられるだけ多くのベクトルを入れかえるゐである。し たがって，最適鮮紅到達するまでのステップの数は櫛動法紅くらべて少い。また締動法に おいては退化可能解の場合，値0をもつ変数を係数とするベクトルが基底に含まれるが，
Mittalの方法では，正の値をもつ変数を係数とするベクトルだけで基底一部分基底「を構 成する。部分基席法と呼ばれる所以である。部分基底法はMqDI法の一度形である。
2．輸送問題とその退化解法 2．1 問 題
基本的な輸送の問題ほ次の・ような形をも・つている。
殆
∑勘メ＝α￡
ブ≦1
よ＝1，2，小，桝
∫45C
貨40巻 難5号
ーβJ−
汀一
宮芝・光り中∫ ．グ＝1，2，・・，〝
勘．声0 なる制約条件のもとで
9乃 クさ
∑ ∑ cけガり
慮＝1戸1
を最小にするような変数勒の値を見出せ。
次の条件は必しも必要でないが，ここでは．この条件をおく 別クa
∑勘誉＝∑∂プ
拝ユ タニユ
以上を表にすれば下表のように表わされる。
C82 ぎ F C88 F ／どさ4 CB2−ぐる2 】 ・芳a竃 】 ・ガ8ヰ
∂2 1 ∂8
ここで，匂一′（査＝1，2，3；ブ＝1，2，3，4）は供給地古から需要地化製品1単位を輸送する に遷する費用・（粕，・ガ12・・方22，・方23巨方88，∬34）は1つの基底可能解，Cり−C名．′（≠−＝1・2，3；・タコ 1，2，3，4）はこのステップの基底ベクトル以外のベクトルを基底に導入した場合の輸送費 用の増減を判別する基準であり，基底ベクトルに関しては0であり，それ以外のベクトル
に関しては，0ならばそれに対応するベクトルを基底に入れても目的関数Aの値は変ら ず，負ならば値は増大し，正ならば値ほ減少する。
以下の諸節では記述の便宜のため， 次のような記替を用小る。■ソニ 黒石 ：基底に入っているベタレレ
白石 ：基底に入っていないベクトル
部分基底法一退化輸送画題の解法（1） − βき−
451
判別評価：巌戸旬−− 〃 2．．2 通常のMOI）Ⅰ法
沼ナ〝−rl個の正の変数をもつ基底可能解から出発し，各黒石（タ■，ぶ）紅関して
C，一さ＝〟γ＋ぴ∫
となるように
〟名：i＝1，2， ，∽
〃．プ：′＝1，2，…… ，搾
を決める。
次に
‰戸（録γ十びざ）−で7さ＝らg−C㌢g
なる式により，各白石（′・，．ざ）に関して判別評価私・gを計静する。全てのゐγ8が0または負な らば，そのステップでの解は最適解である。しかし，正のみざが1■っでもあれば，そのス テップの解はまだ改良されうる。次のステップでは，あαガゐ，gをも。た石が基底紅入り，
代り紅1つの石が基底から追い出されて新しい基底可能解が成立し，目的関数の値ほ改良 される。
2．3 繍動法
輸送問題にわける退化は，供給α名（才＝1，2，…，椚），需要∂ブ（，グ＝1，‥；，カ）に．閲し，αせ が∂メニ1に供給し密残りの虫と∂プの需要鼻，あるいはみ．タがα名＿1から供給をうけたがまだ満足 されない需要立とα名が供給しうる蛍がちょうど−致した場合，あるいほ，さらに．α名．1が供 給しうる畳とわ感．1の需要屋が−・致した場合に生ずる。との退化が生じた場合に．も研＋〝−・1 個の基底変数（基底を構成するベクトルの係数紅なっている変数鶴）を維持するため紅，
無限小だが正であるような占だけ（α1，α2，…，αぶを稀勤し，（α1＋古，禦＋ち‥l・，α彿−ト￡）
仇クさ とする。∑呵戸∑∂Jを満足するため紅（∂1，み2，…，々ね）を輔勤して（∂1，∂2，・・・一，∂叫，∂殉＋ ￡＝1 ノ＝1
∽∈）とする。このようにすれば退化ほ起らず，有限回のステップで最滴解に到達しう・る。
2い4 部分基底法及びその計界手続
この方法の出発点は退化した基底可能解である。計界手続ほ次のようであるも
二一（1卜；也東女吏ップ■LG尉虹た塵底可静解の茨女王ッサ）蔽おける双対変数の決定 ∴
奴対変数の1七）に厚意の値を与える。具体的には，祝1＝ 拓これに・よってできるだけ多
くの双対変数を決定する。解ほ退化しているので，双対変数のうち決定されないものがでて
親側巻 策5一弓
・− ββ− 452
くる。未決定の双対変数のうちのどれか1つに任意の値を与．える。具体的に．は，γを拘が まだ決定されていない行の†番若いインデクスとすれば，〝7・＝Ⅷ扇犯C㌢・．プを選ぶ。これに．よ っでできるだけ多くの双対変数を決定する。このような手続が全ての双対変数の値が決定 されるまで行われる。
（2）最適性の判別
すべての白石匿ついて
ゐ7・g＝〝γ＋恥−−Cγざ＝C7β−Cγ宥
を計静する。もし全ての白石に・ついてゐ，ざく0ならば，現在の解は最適解ごある。もし1
つでも正の判別評価をもった白石があれば，それらを次のようにして基底紅導入するよう に試みる。
（3）1個又は複数の非基底石（白石）の基底への導入
最も大きい正の判別評価をもった白石を選び，黒石（複数）とつないでル・−プを作る。
このとき必要なら0またほ正の判別評価をもった白石ともつないでルーニプを作る。ただ し，、0または正の判別評価をもった白石ともつない・でループを作るとき紅は，新しい基底 可能解がループ上の白石（2個）に正の配分をもつように澄恋しなければならない。この最
も大きい正の判別評価をもった白石がループを作れないときには，二番目にネきい正の判 別評価をもぅた白石について同様にル−プを作るよう試みる。この二番目に大きい．正の判
別評価をもった白石叱ついてもル−プを作れないとせほ，三番目に大きい正の判別評価を もった白石について同様のことを行う。このようなことをル−・プが得られるまで反復す る。もし正の判別評価をもった白石の全てについて同様のことを行ったが，ル・−プを1つ
も得られなかったときは，手続（5卜で述べて∨、るようにんて双対変数を変える。双対変数 を変えた場合基底に入っていない石（白石）の判別評価はノ変わるが，基底に入って：いる右
（黒石）の判別評価は相変らず0であるという性質を利用するのである。
今ループが1つ発見されてなお，そのル−プ上に．ない白石が正の判別評価をもっていれ ば，その石が他の右（白石であろうと黒石であろうと）とル・−プを形成できないかどうか
を調べ，もし形成できれはループを作る。ただしこの場合2つのル−プが1つの石を共有 レてはならな・い。
こ申よう▲紅して，ループ上にある白石の数cが退化次数d（退化次数とほ基底を完成する
に欠けている白石の数と定義する）とループの数ゑの和に等しいかそれよりも小であるか
ぎり，すなわち亡くd＋烏である限り，ル−プを見出す努力を続行する。
部分基底法−退化輸送問題の解法（1） −β7・・−−
453
（4）新しい盈底可能解
（3）で形成された1つまたは復数のループの各々について，（もし白石が2つあればその 中でより大きな判別評価をもつ）白石にβをおき十これに．したがっでそのルー：プの黒石
（およびもしあれば白石）の変数の借をそのル−プ上の変数の砥がどれも負にはならない ように注意しながら変更する。ループを形成しない黒石の変数の値ほ変らない。
（5）双対変数を変えること
変数に変イヒのあった列つまりル−プの垂線が通る列を調べ，ループの垂線の通らない列
をJとする。ループがなければ．Jは〝列の全部からなる。一Jのうらの最大の正の判別評価 をもった白石を選ぶ。それを判別評価私ざをもった白石（γ，5）としLう。的を戎r＝〟㌢−ゐγgと 変え．，これ紅伴ってできるだけ多くの双対変数を決・定する。判別評価は0になり，その行 の黒石（例え．ば（γ，f）としょう）の存在する列（鰭≠列）と算ざ列で黒石の存在する行（例 えば寛．グ行う との交わる白石（メ，f）の判別評価は毎＝毎＋カrgとなる。カJ才が正であれば 白石（ゎ古）は白石（㌢・，・ざ）とループを形成する。何故なら毎ほ黒石（ブ，g）から配分畳1 単位を白石（γ・，5）に移し，黒石（′−．f）から白石（。グ，わに配分畠1単位を移したとき紅 節約できる費用を意味するからである。妬＝0であれば，白石（r，ぶ）とループを形成して 基底を入れかえても目的関数の値ほ変らない。解ほ退化しているので，みこ埠−みざ紅関 連して変化した判別評価以外紅，変化しない判別評価があるはずである。ということほ変 化していなレり勘があるということである。この変化していない的に関する行の中から，
行．／のうち最大の判別評価をもった白石を選ぶ。これを判別評価み′￡′をもった白石（r′iざ′）
としょう。〝㌢′をみ′＝りち′−ゐ．′′g′と変え，これに伴って，できるねけ多くめ双対変数を決定 する。すると白石（γ′，ざ′）の判別評価は0に．なり，その行の黒石（例え．ば（γノ，f′）とし■よう）
の存在する列（幾γ列）と第ざ′列で黒石の存在する行（例え．ば寛ブ′行）との交わる白石（メソ，
f′）の判別評価は妬′＝ゐ一わ′＋み′ざ′となる。尾J′8′が正であれば白石（ブ′，f′）は白石（r′，ざ′）
とループを形成する。このような手続を双対変数が全て新しく決定されるまで行う。もし 最後まで残った．／紅ついて正の判別評価をもった白石がない場合にほ，その双対変数につ
いては−・段前のステップの的をそのままもってくる。この場合負のゐ，ざ紅関レて，み干物
−・カグざと心でも構わないが，そうすることによってほ薪らしい基底解を得ることにほなら ない。
Jのうち最大の正の判別評価をもった白石庭関して
寛40巻 発5号 454
−− ββ−
細る＝〟威−∽α∬ゐ￡β （カ ざ＞0）
β6J
を繰り返していけば，そのステップの解が最適解でない限り必ず1つほループを見出すこ とができる 。その理由は以下の通りである。
㌫。花輪送行列における退化の次数を′とすると，沼・乃行列の行と列をr＋1個のグル ープに分割するこ．とができる。行列の行と列を適当に．整序すると，これらのグループは表 1のように示すこ．とができる。表1で寛gグルー・プの行はα感で，列はβ￡で示されるこれ らのグル−プほ次のような特性をもって．いる。
川退化基底可能解の黒石は全てこれらのグループの石に含まれて：いる。
（占）グルー・プ内の白石に関していえば，この白石をそのグループ内の黒石（3個）と結 びつけるル、−プほただ1つある。
表1
β1 β2
βγ＋1α1 第1グループ
策2グル−プ
策（㍗＋1）グル−プ 押 どのグループにも属さない白石が黒石とのみ（3個）ルー・プを作ることほありえな
い。この右ほそれぞれ別のグル・−プ紅属する2個の黒石とどのグル⊥プにも属さない
Ⅰ偶の白石とでル−プを形成する。
以上の皐うな特性をもったグループ分けの仕方から次のことがいえる。
a）グル−プ内の白石が正の判別評価をもてば直ち紅・そ・のグループ内の3偶の黒石とル
−プが形成される。
b）どのグルー・プ内に．も正の判別評価をもった白石が存在しない場合にはどのグループ
紅も属さないで最大の正の判別評価をもった白石と相異なる2つのグル−プに属する黒石
及び最大の正の判別評価をもった白石と対角線上にある白石（もしこの右の正または0ま
たほ負の判別評価と最大の正の判別評価の和が正の場合には）とからなるループが形成さ
れる。表2において，Aを最大の正の判別評価をもった白石，βを自身の判別評価と石A
の判別評価の和が正であるような白石とすれば，ノみられるようなループが形成される。た
部分基底法一過化輸送問題の解法（1）
455 ・・−・β9−
だし右Aは最大の判別評価をもった石でなくて：もよく，また石βの判別評価ほ必しも正で ある必要はないのであり，両者の和が正であればよい。また石Aの判別評価をゐ如とすれ
表2
β1 β2 βr＋1
算1グループ
l
l
算2グルー・プ
第（㌢十1）グループ
ば，
ゐ ＝〝名−ゐ盛g （毎＞0）
とすることにより板戸0，右βの判別評価ほ，籍1グループに属して石A・βとループを 形成する黒石への配分を1単位だけ右Aに移し算（γ＋1）グループに属して石A・βとル ープを形成する黒石への配分を1単位だけ石βに移した場合に節約しうる費用を表わす。
さて，右Aの判別評価を0とおくことに．よって：双対変数α川1とβ 1の値が決定される。
このときノレープが見出せなければ，α川1の諸行を除いた他の行で最大の判別評価をもった 白石に目をつける。その石を例えばCとしよう（β押1列に属する白石の判別評価がたとえ 正であってもこの石は使えない。何故ならこの右の判別評価を0とおいてもループが形成
されえないこ．とは右Aの判別評価を0とおいたときの計静ではっきりしているからであ る）。表3に．おいて，石Cの判別評価Cグさを0とおけば，この石が算1グル「プ及び罪2グ ループ紅属する黒石及び白石pとループを形成できるかどうかが，石かの新しい判別評価
が正であるかどうかで判定できる。正であればループを形成できる。いまもしこの行列の
グループが3つだとすれば，石pの新しい判別評価が正でなければこのステップの退化基底 表3
β1 β2 ……βr＋1
α1
第†グループ
l 第2グル−プ
αγ．1 第
第40巻 第5号
・−9∂− 456
可能解が最適解である。何故なら我々は残る第1グル−プに．は正の判別評価はないと仮定 しているからである。かくしてグル−プが3つなら同一・ステ・ツプ内で∽α方ゐグg＝0を二度 行えばよく，グループの数がr＋1個であればγ回だけ椚α方ゐ㌢合＝0を繰返せば，そのスタ
シプの解が最適解でない限りルー・プを得ることができる。このことを次の計穿例で示そ う。
表αが与えられている。太線で囲った内部がそれぞれのグループである。この表で〝 列，
ぴ．プ行は双対変数を，析の中央上方の数字は基底変数の値，その左下方の数字ほ単位当り輸 表 α
4 −5 、0 0 5・−8 1 −2
−4 0 0 −5 1 −9 6 −・8
2 0 2 −3 4．＿8 5 −3 1 1 2 11−4 5 4 1
0
