« ブラウン運動と伊藤積分(9) | トップページ | 準線形計画法(ネットワーク輸送問題)(2) »

2007年7月13日 (金)

準線形計画法(ネットワーク輸送問題)(1)

 書類の整理をしていたところ,昔1991年頃に2番目の会社での社員時代に書いた未発表の数値計算に関する私の論文が見つかったので,それを紹介したいと思います。

これは,当時仕事上で,ある水道局の上水道について圧力損失が最小となるようなネットワークを構成する方法を開発してプログラム化する必要があって,その過程で書いたものです。 

こうしたことについて,当時私は全くの素人だったので,まず,線型計画法の専門書を数冊読みました。

 

その後,結局,線型問題ではなくて,より実際に近い近似的に2次の問題である準線形な"輸送問題=最小コスト問題"を解くための当時オリジナル?と思われる"方法=アルゴリズム"を自力で思いつき,それの論文を書いて某大手の中央研究所に収めました。

ネットワーク自体については,学生時代に専門の量子電磁力学(QED)や場の量子論で摂動計算を行なう必要があり,ファインマン・ダイアグラムを用いて具体的にS行列要素の摂動の2次や4次のグラフの計算をしたり,また,そうしたネットワークのグラフの解析性や構造を論じたりしたことはありました。

特にファインマン(Feynman)やダイソン(Dyson)らのくり込み理論においてグラフのツリー構造や"閉路=ループ"の構造と摂動における運動量積分の発散の次数の関係を求めることにより,くり込み可能性を考察する上で様々なネットワーク・グラフの構造を調べた経験があります。

 

また,独学ですが主に線形素子から成る直流や交流の電気回路の理論においても,回路グラフなどを学習したことがあります。

 

それらはこの理論のネットワークとも共通した話なので,この理論には比較的違和感がなく入れました。

当時,本論文の方法を用いて実際にFortranでプログラムを組みましたが,これ自体の内容をプログラムするのは,そもそもこの論文がアルゴリズムの手順を書いたものですから,決して難しいものではありませんでした。

しかし,そのプロセスとして,いろいろな場合を想定して場合分けをする必要性があり,そのために順列,あるいは組合わせの全てを尽くす,という問題が生じました。

 

これは通常の数学の問題としては高校でも習う単純なものですから,最初は安易に考えていました。

 

しかし,実際にそれをプログラムにするためにアルゴリズム化しようとしたとき,非常に複雑な問題であることに気付き,結局,このプログラムを完成させるために,本質的内容には関係ないその部分でとても苦労した覚えがあります。 

もちろん,あらゆる場合についてネットワークのコストを全て計算して最小値を求めるというのでは,何の工夫もなく(非)線型計画法など全然必要ないわけですが,(非)線型計画法をうまく利用しても,なおかつ,かなりの場合分けが必要でした。

そして,実際,この順列,あるいは組合わせを尽くす,というプロセスのためには膨大な計算時間を必要とするので,当時利用できた今よりメモリーが少なく,ディスクのサイズも小さくて,CPUによる演算スピードも遅いコンピュータでは,計算時間がかかり過ぎる,というネックがありました。

 

プログラムの使用メモリ-のサイズを小さくしたり,計算時間を短縮したりするために,さらにいろいろと工夫した覚えがあります。

 

その後まもなく,私はその会社もやめたので,以後そのプログラムがどうなったかは知りません。 

論文のほうは,原理的には,これをプログラミングすることが可能であることを述べたものです。

 

私のやる仕事の特徴なのですが,ある意味で"理屈だけでくその役にも立たない"と言われるものの部類に属しています。

 

つまり,アルゴリズムであるにも関わらず,実用的であるというよりも単に理論的な意味しか持たないかも知れません。 

 論文の正確な表題は「準線形コスト関数を最小化する特殊なネットワーク輸送問題を解決するアルゴリズム」です。以下に論文をそのまま写します。

 

                        Abstract

Resently,because of the development in linear planning methods and the utility of digital computers with high efficiency, the techniques for solving the problems of minimizing network flow costs have been successfully developed by many investigators.

Most of these studys is due to the primal simplex algorithms.

In this paper,we modify the ordinary primal simplex method to apply the minimal cost network flow problems with more complex cost fuctions that increases with network flow amount on each arc.

1.     序文 

ネットワーク輸送問題,あるいは最小コスト問題は一般的な線型計画問題とは別に,通常の方法で線型方程式を解くことなく解ける問題であるという意味で,線型計画法の特殊な1分野として多くの研究者によって独立に研究されてきている。

 

もちろん,原理的には一般的な線型計画問題の直接的な応用として解くこともできるが,変数が多いときには輸送問題特有の方法を用いた方が、計算の簡略化,短時間化等でははるかに効率的であって,時間的,コスト的に非常に有利である。 

輸送型の問題としては,単純にM個の積み出し地からN個の目的地へ製品を輸送するのに必要な最小コストを求めるという,ヒッチコック型の問題が有名である。

 

しかし,本論文では,需要,供給を与えるN個の節点と,これらを任意に連結する独立のコストを持ったM個の枝から成る全く一般的な問題を扱うことにする。

各枝em(i,j)は,節点iから節点jへの向きを持った流れを持つとする。(m=1,2,..,Mで,i,jは1,2,..,Nの選ばれた異なる2つの番号である。)

これらの枝の集まりの全てが,実際に輸送可能な全てのルートを表わしている。一方,各節点n(n=1,2,..,N)は付随する量rnを持つ。

 

n>0 ならnはrnに等しい供給を与える供給点である。rn<0 ならnは-rnに等しい需要を与える需要点である。またrn=0 ならnは中間点である。つまり,rnは節点nにおける代数的供給量である。

任意の枝em(i,j)を通過する流れがあるとき,単位流量当たりのコストがcmであるとする。

 

このとき,最小コスト輸送問題とは,与えられた需要,供給と各枝の容量制限に合致しながら,輸送コストの合計を最小とするために,どの枝を用いて,それら各枝の流量をどのように決定するか?ということを定める問題である。

これらを数式化すると次のようになる。 

各節点nに対し,nから出て行く枝の集合をAn,nに入ってくる枝の集合をBnとするとき,各節点n(n=1,2,..,N)に対して,Σem∈Anm=Σem∈Bnm+rn(1-1)が成立しなければならない。

 

ここに,xmは枝em上の流量である。xmに適当な大きさの制限がある場合には,その制限式も付加する必要がある。

これらの条件の下で,最小コスト問題はΣm=1Mmm(1-2)が最小の値を取ることを要求する。

ここでは,大前提として総需要と総供給の収支のバランスがとれているとする。つまり,Σn=1Nn0 (1-3)と仮定する。

 

そうでない場合は,適切な需給を持ったダミー終点と各節点からこのダミー終点へのコストゼロの枝群を加えることで,需給バランスのとれているケースに帰着できるので,以下Σn=1Nn=0 とする。

 以下では,まず既存の主単体法によって,単純な線型コスト関数を持ち,各枝の流量に上界と下界のある場合の輸送問題を解くアルゴリズムの1例を紹介する。

 

 次に,本論文の主旨であるところの各枝の流量値の絶対値に依存して増加する単位コスト値を持ち,近似的に流量の2次関数型をした準線型コスト関数を持つ輸送問題へとそのアルゴリズムを拡張する。 

2-1.木と可能木解

①節点uとvの間の道とは,節点w1,w2,..,wkと枝e1,e2,..,ek-1から成るネットワークで,u=w1,v=wk かつ枝eiの両端点がwi,wi+1であるようなものである。

②閉路とは,道に始点と終点を結ぶ枝を1つ加えてできるネットワークである。 

③全ての節点の間に道があるとき,ネットワークは連結であるという。 

④木とは,連結でかつ閉路を含まないネットワークのことである。 

⑤ネットワーク{1,2,..,N}の"全ての節点を含む木":Tを問題としているネットワークの1つの極大木という。

 

 極大木はN-1個の枝を持ち,木に属さない枝の流量を勝手に決めることにより,条件(1-1)を満足する{xm}の組が決まる。

⑥可能木解とは,極大木Tに対応する可能解である。

 

 つまり、枝emに対しLmをその流量の下界,Umを流量の上界とするとき,emがTに属さないならxm=Lm,またはxm=Umであって,全てのnについて,条件(1-1)を満足する{xm}の組(m=1,2,..,M)をTに対する可能木解という。

⑦可能木解が得られたとき,全ての枝のうちで可能木解に対応する極大木に含まれるものはN-1本であり,これらの枝を基底という。

 

 極大木に含まれない枝を非基底という。

2-2.双対変数Πnの決定と基底に入る枝の選択

 求めるアルゴリズムに到る最初のステップは,各節点nに対する双対変数 Πnとして全ての基底枝em(i,j)に対し,Πj+cm=Πi(2-1)となるような変数:{Πn}(n=1,2,..,N)の組を計算することである。

 N個の変数Πnに対し,(2-1)はN-1個の方程式系なので,解に定数だけの任意性があるため,例えばΠ=0 と仮定して極大木の枝に沿って次々にΠnを決めることができる。

 次に,em(i,j)が非基底枝の場合(すなわちemがTに属さない場合:¬em∈T)には,xm=LmのときDm=Πi-Πj-cmとおき,これらの枝の集合をL,xm=UmのときDm=Πj-Πi+cmとおき,これらの枝の集合をUとする。

 

 ただしLm=Umのときには,どちらか一方を適当に選ぶ。

 このとき,全てのDmがDm0 を満足するなら,現在の可能木解が求める最小コスト解の1つである。

 なぜなら,Σm∈Anm=Σm∈Bnm+rn (1-1)の条件を満たしながら,非基底についてxm=Lm+Δm,またはxm=Um-Δmm>0)とxmを変化させたとき,(それによって基底のxmは自動的に変化する。)

Σm∈Tj-Πi+cm)xm=0 だから,総コストは,Σm=1Mmm=Σm=1Mj-Πi+cm)xmm+Σm=1Mi-Πj)xm=Σem∈Tj-Πi+cm)xm+Σ¬em∈Tj-Πi+cm)xm+ΣiΠiΣem∈Aim-ΣjΠjΣem∈Bjm=Σ¬em∈Tj-Πi+cm)xm+ΣnΠnem∈Aim-Σem∈Bjm)=Σem∈Umm-Σem∈Lmm+ΣnΠnn-Σ¬em∈TmΔm (2-2)

 そこで,全てのDmがDm0 のとき,任意の非基底em上のΔm>0 の変化に対して,Σcmmは現在の状態より必ず非減少となるため,現在の可能木解が1つの最小コスト解となる。

 したがって,逆にDm0 の枝emがあれば,容量制限を越えることなくxmを変化させることができる場合には,その変化によってコストは必ず減少する。

 

 つまり,ゼロより大きいDmを持つ枝は基底に入る枝の候補である。

 ところで,Dm0 に対応する基底に入る枝を1つ決めて極大木に付加すると,その時点で1つの閉路ができてしまう。

 

 基底に入る枝emの流量xmの変化を±Δとすると,Δ>0 が大きいほどコストの減少は大きいわけであるが,xmの±Δだけの変化に対して閉路内の基底枝の全てがそれぞれ±Δずつ変化するときに限って,(1-1)式のΣem∈Anm=Σem∈Bnm+rnが満足される。

閉路に属する全ての基底についての容量制限Lm≦xm≦Um(em∈T)を満足しつつ,最大の値となるようにΔの値を定めることができる。

 

それにつれて,xm=Lm,またはxm=Umとなって,基底から出て非基底となる1つの枝が得られる。

 

こうして新しい極大木と可能木解が得られる。

入る枝に対してDm0 ,出る枝に対してDm=0 であるから,このプロセスでコストは減少する。

そこで今度は,再び双対変数 Πnを更新しなければならない。この手順は次の通りである。

 

Tに入る枝をeφ,Tから出る枝をeψとすると,新しい極大木はT+eφ-eψと書ける。

 

T+eφ-eψから枝eφを除いたネットワーク(T+eφ-eψ)-eφ=T-eψは,枝eφの端点を1つずつ含む2つの互いに素な木から成る。

φ(u,v)のとき,節点uを含む木をTu,vを含む木をTvとする。

 

φの単位コストがcφなら,σ=Πv-Πu+cφとおいて既知のΠnから更新されたΠnの値Πn*を次式によって求める。

 

Πn*=Πn+σ(n∈Tu),Πn*=Πn (n∈Tv)(2-3)である。

 

これらが更新の手続きである。

 

以下,全てのDmがゼロ以下になるまで上の手順を反復すればよい。

※今日はここまでにして続きは後日にします。

 

参考文献

1.A.I.Ali,R,V.Helgason and H.S.Lall:"Primal Simplex Network Codes:State-of-the-Art Implementation Technology." Networks.Vol.8(1978) pp315-339

 

2.V.Chvatal(V.フバータル;阪田省二郎,藤野和雄,田口 東 訳)「線形計画法」(上)(下)(啓学出版)(1988)

 

3.古林 隆:「線形計画法入門」(産業図書)(1980)

 

http://folomy.jp/heart/「folomy 物理フォーラム」サブマネージャーです。

人気blogランキングへ ← クリックして投票してください。(1クリック=1投票です。1人1日1投票しかできません。)

http://homepage2.nifty.com/toshis-kaiga-auction/健康商品の店 「TRS健康ランド」

にほんブログ村 科学ブログへクリックして投票してください。(ブログ村科学ブログランキング)

にほんブログ村 トラコミュ 物理学へ
    物理学

|

« ブラウン運動と伊藤積分(9) | トップページ | 準線形計画法(ネットワーク輸送問題)(2) »

311 .数値計算・調和解析・離散数学」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: 準線形計画法(ネットワーク輸送問題)(1):

« ブラウン運動と伊藤積分(9) | トップページ | 準線形計画法(ネットワーク輸送問題)(2) »