線型計画と分権的決定
古瀬大
↓ ノ、
歴史的回顧
線 型計画 と分権 的決定
拘束条件附き極値問題の解法を考えることは︑純数学的問題であるだけでなく︑経済現象における均衡過程を論ず
ることでもあり︑また同時に組織における分権的決定過程を考えることでもある︒従って︑この問題にたいする貢献
は︑理論経済学︑組織論︑システムズ・エソジニヤリソグ︑数値解法︑等々の広い応用分野における進歩を意味す
る︒
この問題の最初の発見者は勺9三ω9巨￠Φぎ昌であった︒彼はその︑︑司︒ロ巳聾8の9罎讐冨目簿什凶︒鎗団8昌︒邑︒ρ..H漣①の
中で︑一般均衡への収束過程が︑あるポテンシャル画数の極値点への運動過程として記述される可能性について簡単
に触れている︒その後間もなく彼はラソド・コーポレーションからの報告の形で︑その具体的なモデルの一つを提案
した(℃暫巳鋭ω9︒旨β巴ωoづ"︑︑寓騨蒔9ζooゴ帥巳ω目ω"巳罎9恩巨N9δ匿"︑.やOρ幻諺ZUO自宕雷江oP竃9︒3げト︒︒︒"一〇お)︒然し
261
それは︑彼自身も認めているように︑収束性を欠く不完全なモデルであった︒622この問題の発展に最も大きな貢献をしたのは︑国巨P胃ミ●勢ロα}毛.↓ロ舞零"︑︑2露・ぎ$﹃勺3鴨9︒ヨ目ぢαq"..言﹄・
2畠導§(O山・)"犀88仙百暢o賄爵︒留8ロαしd︒蒔oδ鴫ω矯目boω葺ヨ凶口竃讐冨巳餌膏9︒一ω什曽器二︒ω9︒巳勺8ぴ筈凶鼻ざδ望である︒
これによって︑非線型の場合をも含めた一般的な拘束条件附き極値問題(数学的計画法蜜讐げo目拶二〇9︒一℃邑oぴq﹃9ρヨ目一昌αq)の
解の必要十分条件が︑数学的に厳密な形で示された︒
この︑クーソタッカーによる解の静態的条件と︑均衡点への動学的運動過程のサムエルソソ・モデルを結びつけ
て︑問題を最も一般的な形で表わし︑収束性をもったモデルを与えることに成功したのが︑国︒聲d墨毒斜貯︒妻矯
山霞註自等の︼連の研究である︒その成果は︑諺議︒ぎ溶﹄.︾い●出霞乱︒N9口αd鑓≦讐ωε臼︒ω置ピぢ8目雪傷Z8,ぎ︒胃
勺8窟目目言︒q"一霧︒︒℃ω富ほ臼αd巳タ℃H︒ωωにまとめられている︒
二∪99§oqの批判
上記の研究に共通する基本的な態度は︑与えられた数学的計画問題の解をその鞍点としてもつポテンシャルを作
り︑その点に向って連続的に動いていく点の動きを微分方程式(又は定差方程式)で表わし︑その解の収束性を解析的
に論ずる︑という態度である︒この収束性は︑問題が線型計画問題である場合には︑あまり良好ではない︒理論的には
収束性をもっていても︑現実の問題を定差方程式で表わしてディジタル・コソピューターにかけてみると︑時間がか
かってなかなか解に近附くことができない︑というのが︑これらのいわゆるO冨貸・糞竃︒旨巳の一派にたいするρ甲
U9︒ロ旦αqの批判である︒
冨9N碍は︑彼の考案になるピ℃の解法︑シソプレックス法︑の基本的な考え方である凸多面体の角から角への移動
という考え方を保持しながら︑大きな電問題を幾つかの小さなピ℃問題に分割し︑ であることを示した︒これが︑いわゆる︑U80ヨ宕の憲o昌勺㎏ぼ9営oに外ならない︒ これを分権的に解くことが可能 線 型計 画 と分権 的決定
三UgΩ日りo忽口o昌℃鼠ロo首5
次のような形のH勺問題を考えてみよう︒
旨9×讐O
(H) §ーら遠1ら曼ー畠碗ー10謡いー戴
︻ 卜曼ー1餅
匡畏ー1守︒︒
き撃NWO について
(μ.O)
(H﹂)
(μ・bo)
(日・ω)
(ド劇)
これをそのままコンピュ!ターにかけてシンプレックス法によって解くことは︑原理的には勿論可能である︒しか
し︑トご﹄ぎ}︾⁝⁝のマトリックスの一つ一つなら扱えるが︑この全体ということになると︑計算機の能力を越える
大きさになってしまって︑実用的には解けない︑という場合も少なくない︑このような場合に︑これをいくつかの小
さな問題に切断して分権的に解くことができると︑大変有難い︒
そこで︑これを次のような手続きによって︑三つのの昏胃︒鴨薗ヨのと一つのヨ"ω8↓鴇︒鴨勢目に分割する︒まず︑何
63等かの方法で﹄篭11黛のゐ個の異った非負基底解ギ⁝⁝"§が得られたとする︒他の工蔓"酵﹄︒・N11診についても同2
様に︑それぞれ1個及び翅個の異った非負解璽﹃⁝‑"撃恥﹃⁝・・温§が与えられているとしよう︒ただし︑袖︑噂§は
それぞれ1又はそれ以上の整数で︑その合計(趣+︑十§)は︑問題(1)の条件式(ドH)の数πに}"トぎム︒・の数3
を加えたもの︒すなわち(ミ十ω)に等しくなるように定めておく︒しかし︑これらの基底非負解のうちの任意の一
組︑たとえば蓄賢きをとってこれを(1)に代入した場合︑条件式(ドb︒)導(一.︒︒)矯(μ誌)の方は勿論成り立つけれど
も︑(一●H)が成り立ってくれるという保証は何もない︒
それ故︑これらの(勘十︑十ミ)個の初期解は︑勝手に選べるわけではなく︑その加重平均が(一﹂)の解を含むように
決めておかなければならない︒こうしておけば︑これらの加重平均が他の条件式(ドbδ)〜(一﹄)を満足させることはい
うまでもないから︑万事O国ということになる︒(一●b︒)〜(H﹄)の非負基底解の加重平均をとれば︑その非負性︑及
び︑それが(﹁b︒)〜(目・ら)の解であるという二つの性格はそのまま維持されるけれども︑それが(一﹄)〜(﹁蔭)の基底解
であるという性質は失われる︒しかし︑問題ω全体の最適解においては︑そのき撃恥要素がそれぞれ(﹁b︒)〜( ・ら)
の基底解でなければならないという必要は全然ないのだから︑一向さしつかえはないわけである︒
以上の考え方に従って︑これら(趣十︑十§)個の初期解にたいしてウェイト}⁝⁝﹂き書・⁝・・噂蚕ジ⁝⁝uぎを附け
れば︑その加重平均は全条件式を満足するはずである︒すなわち︑次の式が成り立たなければならない︒
(PO)
(b︒)藩謙濃
沁ミ覧WO (b︒・一)
(N﹄)
(b︒・ω)
(b︒・軽)
線型 計画 と分権 的決定
これが問題ωの基底許容解であっても︑それがωの最適解であるかどうかはまだ明らかでない︒その判定法は︑
シソプレックス計算法の周知の手続きに従って︑この基底許容解ト︾℃に対応する各条件式のω冨山薯旦︒$
鵠ご⁝⁝︾ぎ葛ξ3欝を計算し︑それで非基底ヴェクトルを評価すればよい︒しかし︑残念ながら︑われわれは基底ヴェ
クトルだけしか持ちあわせていない︒②の初期解をつくるときに︑(ピbの)〜(﹁腿)の初期基底許容解を全部もうらして
おいたならばよかったのだが︑それは如何なる大型電子計算機をもってしても不可能な相談である︒U碧琶α︒の優れ
たアイディアは︑この非基底ヴェクトルを︑必要の都度つくりだしていく︑という着想である︒勿論︑勝手に作った
のでは︑それがo言8・言されるヴェクトルでなくて︑肩ぎ869されるべきものであるかもしれない︒それが必らず
目的函数の値蜘を増加させるようなものにするにはどうしたらよいか︒
それにたいする答えた︑次の通りである︒すなわち︑次のような三つの小さない℃問題をそれぞれ独立に解いて︑
それらの最適解を求めれば︑それがわれわれの希望する新しい基底ヴェクトルになるのである︒
]B言
(ω)
一 一
目 ヨ
け コ
ロ 昌
ミ ミ ミi
●o鱒P
§i(ー9十詞国p︾110
工篭11驚℃
ミ牌1(ー"苗十鵠凶h︒)璽110
態璽11夢
§ー(1壽十尉凶︒︒)恥110
郎︒・NHぎ 著WO
健WO
賊WO
これらの最適解がト篭11守ごトミー‑富卜︒・碗11辱︒・の基底許容解であることは当然であり︑かつまた︑それら§暢§"§の獅最小値がそれぞれよご1章ー恥︒.より小であれば︑それを新らしい基底ヴェクトルに加えた②の解が︑その蜘のを前
回よりもー(砺﹁§)りー(g+§)℃1(8+§)だけ増加させるであろうことも明らかである︒こうして得られた②の新らし
い最適基底ヴェクトルをもとにして︑そのω冨α︒毛噂翫8ωを新らしく計算しなおし︑その新らしいω冨α︒毛嘗8ωを
使って上記の三つの小さいピ℃を解いて蜘の増加の可能性を確かめ︑それが可能であれば︑②にさらにこの新ヴェク
トルを加えて解きなをす︒この過程を何度でも必要なだけくりかえし︑蜘の増加の可能性がなくなったところで計算
を中止する︒このときの②の解を(N︒峯︒燭〜)とすれば︑われわれの元来の目的であるωの最適解}健︒噛魅は︑
へ胴竜"M︼No帖毫軌
斜11印
ヨ(卜)健︒日Mざ︒ミぐ︑﹂
︹旭‑酔.・魅・
で与えられる︒ただし︑上の聾愚︒︑矯掛はそれぞれ︑最終段階における②の最適基底ヴェクトルを示す︒
この解法の実用的利点は︑大きなピ℃問題をいくつかの小さない℃問題のくりかえし計算に帰着させることによっ
て︑計算機の所要能力を低い値をおさえることを可能にしている点である︒上の例では︑それは一つの日器8h娼亭
︒q量目と三つのω昌亡3唱①目ωとに分割される︒このヨ9︒ω8↓肩︒鴨簿ヨにおいては︑ωロぴ・ロ8窟ヨωの幾つかの基底解に
それぞれ凶ぴ轡"国.・を乗じたものが係数行列として扱われ︑それらの加重平均を求めることによって︑ω暮ら3鴨曽ヨω
における♂勢忽蓬芽をそこなうことなしに︑それらの共通条件式(昌﹂)を満足する解を求められるように配慮され
ている︒
残された問題は︑この目婁葭鷺︒鵯曽言の初期許容解をどうして求めるか︑という点である︒これは︑普通の冨の場
合の℃冨器一を一般化してみれば︑次のような方法が直ちに考えだされるであろう︒すなわち︑まず︑それぞれの
のロび‑只oαq量巳ω卜篭11曽ご︾ミ旺夢卜︒・畿"夢きぎ軸W⑤の初期基底許容解を論♂壁襲印シソプレックス法の㌧訂器Hによって求
め︑それから︑次のヒ勺を解けばよい︒
H巨一bミ
線 型 計画 と分権 的決定
(α)
但し︑碗はゴ番目の要素がーで他は全部0の単位ヴェクトル
の前の符号±は︑鋸がプラスになるように何れか一
以上のUΦ8目宕ω三︒昌
方は︑Uき鼠αqし・炉きα即箋9け"U①8讐冒ω置︒口国ヨ9δ8吋ピぢ$↓寄︒鴨弾目ρO儲壁怠︒器幻￠器胃9<9︒︒"冥9ど}掌︒P‑
国oρ一〇〇〇もやHO一〜嵩一.をおよみ願いたい︒ 映︒ー(9穂)きー(爵撃)書1(畠蛙)ミHO}
(国蔑 )沁 十(国b︒鴨)唇十(凶︒瓶)ξ汗ミ蚕汗⁝⁝匪ミ§§H制
沁 11一
書目μ
ニー1H
畠十:・:・十〇§ーミHO
きぶざmWO
銃は左右のバラソスをとるための人為変数であり︑そ
つを選ぶものとする︒
喝甑口9営Φの説明は︑直観的であって︑数学的厳密性を欠いている︒厳密な証明を希望される
四U①8目りoω三〇口とU①ooロ胃9︒冒9怠o昌
三つの部門からなる企業を想像してみる︒会社は次期の生産計画を立てなければならない︒計画の責任者は本社経蜥理部であるが︑本社としてはあまり各部門の細かい問題には立ち入りたくない︒そこで︑まず︑本社では︑各部門に
