« 準線形計画法(ネットワーク輸送問題)(2) | トップページ | 目をそらす姑息な手段 »

2007年7月16日 (月)

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

 さて,本題である私のオリジナル:準線型輸送問題のアルゴリズムに入ります。

 

3.流量値依存の準線型コスト関数を持つ輸送問題を解くアルゴリズム 

2では,各枝emの単位コストcmが流量xmの値に関係なく,一定であるようなごく一般的な線型輸送問題を扱った。

 

本節では,cmの値がxmと共に単調増加し,コスト関数が下に凸の折れ線となるような輸送問題が解けるようにアルゴリズムを拡張する。 

すなわち,各枝は容量制限Lm≦xm≦Um (Lm,Umは±∞,正,負,0のいずれでも良い)を有するが,この他にi=-jm,..,0,..,kmの各値について,tm,iが存在してtm,i-1≦xm≦tm,iの各xmに対して,単位コストcm,iを持つ。なお,tm,00 である。

mに関わる総コストは,xm 0 のときは,tm,lm-1≦xm≦tm,lmならばΣk=1lm-1m,k(tm,k-tm,k-1)+cm,lm (xm-tm,lm-1)(3-1a)であり,xm 0 のときは,tm,-lm-1≦xm≦tm,-lmならばΣk=0lmm,-k(tm,-k-1-tm,-k)+cm,-lm (xm-tm,-lm-1)(3-1b)である。

まず,条件(1-1)と全ての容量制限を満足する1つの初期可能木解が得られたとする。

 

このとき.この可能木解で現在の各枝emの流量xmの値によって暫定的な上界tm,kと,下界tm,k-1,および単位コストcm,kを定めることができるので,とりあえずこれらの値を固定しておく。 

基底枝em(i,j)に対しては,tm,k-1≦xm≦tm,kにおける単位コストcm,kについて双対基底として,Πj+cm,k=Πi(3-2)となるように、{Πn}(n=1,2,..,N)の組を計算する。

 次に,m(i,j)が非基底のとき,m=tm.k-1ならばDm=Πi-Πj-cm,k ,xm=tm.kならばDm=Πj-Πim,kとおく。 

固定した暫定的な上界,下界,単位コストに対して,全てのmがDm0 となるまで,通常の主単体法の更新を繰り返す。

 

全てのmがゼロ以下となったときには,2-2で記述した論旨によって,暫定的な容量制限内に流量が留まっている限りにおいて,コストは最小になる。

 

つまり,全てのmがDm0 なら,コスト関数においてxmの±Δmの変化と共に変化し得る量Σcm,kmm(2-2)式と同様に変形されて,Δm>0 の変化に対して必ず非減少となるからである。

そこで次に,得られた暫定的最小コスト解において,非基底枝mに対してmが下界tm.km-1に等しい場合には,これを上界と見なして,新しいDmの値としてのDm*をDm*=Πj-Πim,km-1で与える。

 

m0 より-Dm=Πj-Πim,km0 であり,単位コストm,kはkに関して単調増加であるからDm*≦-Dmであるが,もしDm*0 ならmは基底に入る枝の候補となる。 

同様にmが上界tm.kmに等しい場合には,これを下界と見なして,新しいDmの値としてのDm*をDm*=Πi-Πjm,km+1で与える。

 

m0 より-Dm=Πi-Πjm,km0 であり,単位コストm,kはkに関して単調増加であるから,やはりDm*≦-Dmであるが,もしDm*0 ならmは基底に入る枝の候補となる。 

もし,以上のような操作で得られたDm*が,なおゼロ以下ならば既に得られている可能木解が求める最小コスト解である。

 

なぜなら,(3-1)式を,m=1からMまで加えた総コストはΣmk≦km-1m,k(tm,k-tm,k-1)+cm,kmm,km-1}+Σm∈Umm,km-Σm∈Lmm,km-1+ΣnΠnn-Σ¬em∈TmΔm(3-3)と書けるから,Dm≦0 によりΔm>0 に対しては既に最小であり,上述の操作による非基底枝の境界を越えるΔm<0 の方向へのmの変化に対しては,コスト関数を(3-3)式の形に変形した場合,xmの変化Δm*=-Δm0 についても,なお更新されたDmの値Dm*が全てゼロ以下となるからである。

しかも,上に示したように,境界を越える区間変更の操作に対して,DmあるいはDm*は必ず非増加であるから,ある操作で全てのDm*がゼロ以下なら,続く操作でも常にDm*がゼロ以下という性質が保持される。

こうした説明からは,得られた解が最小コスト解ではなく,極小コスト解であることしか証明されないように見えるが,単位コスト関数が単調でありコスト関数が滑らかな変動をするため,Δmの値が大きく境界を越えた場合でも既述の計算式が若干の修正を除いて保持されることを考慮すると,全てのDm*がゼロ以下という結果が得られた場合,求める最小コスト解が得られたとして良いことがわかる。

一方,Dm*0 の枝emが発見されれば,それを基底に入る枝として新しい暫定的上界,下界,単位コストを設定し,基底から出る枝を選んで通常の主単体更新の手続きを繰り返せば良い。

実際の計算機におけるアルゴリズムも2-3に示した手順に暫定的上界,下界,単位コストを用いるという僅かな変更を行なうだけで容易に拡張することができる。

.付録 初期可能木解の便利な求め方

 輸送問題において、主要な課題である更新の手続きに関する方法を考察してきたが、実際のアルゴリズムでは(1-1)式と容量制限を満足する初期可能木解(初期極大木)を求めるのも重要な課題である。

本節では、V.Chvatalの方法を参考にして,一般的で簡単かつ便利な初期可能木解の発見方法を紹介する。

まず,もとのN個の節点に番号N+1のダミーの人為節点を付加し,さらにもとの節点1,2,..,Nと,この人為節点を結ぶN本のダミーの人為枝eM+1,eM+2,..,eM+Nを付加する。

 

流量は,全て非負の値にするため,新しい流量変数をxm'≡xm-Lm (m=1,2,..,M)(A-1)で与え,上界をUm-Lmとする。

(1-1)より,rn=Σem∈Anm-Σem∈Bnmであるから,新しい供給量rn'をrn'=Σem∈Anm'-Σem∈Bnm'=rn-Σem∈Anm+Σem∈Bnm (n=1,2,..,N)(A-2)と変換して,rN+1'=0 とおく。

 人為枝eM+iはri'>0 のとき(i,N+1)で,ri'≦0 のとき(N+1,i)とする。

 

また,全ての枝emの単位コストをpm(m=1,2,..,M,M+1,..,M+N)として,emが実枝ならpmに 0 を人為枝なら 1 を与えることにより1つの線型輸送問題ができる。

 この最小コスト輸送問題を,もとの問題(主問題と呼ぶ。)に対して補助問題と呼ぶ。

 補助問題をまとめると,次のように表わせる。: 

 条件:Σm∈Anm'-Σem∈Bnm'=rn'(n=1,2,..,N,N+1) (A-3); 0≦xm'≦ Um-Lm (m=1,2,..,M)(A-4a);0≦xm'(m=M+1,..,M+N)(A-4b)

 

 目的:z=Σm=1M+Nmm'(A-5)を最小化する。

 

 ただし,pm0 (m=1,2,..,M)(A-6a);m1(m=M+1,..,M+N)(A-6b)である。

補助問題の初期可能木解はN個の基底枝を人為枝eM+1,eM+2,..,eM+Nとして,それらの流量の初期値をri'>0 ならxM+i'= ri'(A-7a),ri'≦0 ならxM+i'=-ri'(A-7b)と設定し,M個の非基底枝em(m=1,2,..,M)については,流量をxm'=0 (m=1,2,..,M)(A-8)と設定すれば得られる。

2で示した主単体法の更新を,この補助問題に反復適用して,得られた最小コストzが正の数ならば,もとの主問題は不可能であって可能解は存在しないが,zがゼロとなる場合には主問題の可能解が存在する。

以下,z=0 の場合のみを考える。

補助問題の最小コスト解では,極大木に属する基底枝はN本であるから,少なくとも1本の基底枝は人為節点を端点に持つ人為枝である。

人為枝が1本だけの場合は,残りのN-1本の基底枝が元の主問題の基底枝となり,主問題の極大木を形成する可能木解がただちに得られる。

補助問題の基底枝の中に人為枝が2本以上ある場合には,z=0 よりそれらの人為枝の流量は全てゼロであるはずだから,人為枝の代わりに他のゼロ流量の非基底枝を加えてもz=Σpmm'に対する解としては,同値なものが得られる。

ここでの補助問題の極大木は,いくつかの実基底枝のみから成る部分木群を,人為節点N+1を通る2本ずつの人為枝で結びつけたものとなるが,これらの部分木間の流量はゼロであるから,部分木同士を連結するために基底人為枝の代わりに,流量ゼロの適切な非基底枝をおきかえれば,実枝のみを基底とする主問題の極大木が得られるはずである。

ひとたび人為枝を含まない極大木Tが得られれば,補助問題の解の一部分である{xm'}(m=1,2,..,M)の各々に{Lm}の各々を加えることによって初期可能木解{xm}を求めることができる。

参考文献 

1.     A.I.Ali,R.V.Helgason and 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)

     以上が1991年頃に仕事上で書いた大したこともない数値計算の1論文です。

実は,この頃私は友人と共同で理進ゼミという大学受験塾を始めて,この塾の講師兼経営者とある会社の嘱託社員の掛け持ちをしていました。

 

この塾の共同経営者で数学と化学担当講師は,本業が東京理科大事務官だったのですが,彼にこの論文とか「次元控除法によるポアソン方程式の解法」とか,その頃書いた論文を自慢げに見せたところ,「どこかのお金持ちたちが,最近もっとつまらない論文で理科大で博士号を取っている。これくらいの内容なら簡単に理学博士が取れるから推薦してあげよう。」と言われました。 

博士号なんて「足の裏の飯の粒」に過ぎないもので,これは「取らないと気持ち悪いが取っても大したことはない。」という例えですが,当時,私は修士号しか持っていないし,取っておけば将来これを使って詐欺師をやるわけではないが,何かの金儲けの種とかの役に立つかもしれない,という色気を出して彼に頼んでみました。

 

ただ申請が通っても38万円余りの手数料を取られるという話だったので本当かなという疑問も持ちました。

それで論文がこれだけでは少ないかなと思い,この2つに論文ではないけれど「風速と拡散係数が高さのベキの拡散方程式の解析解」という,かつて窒素酸化物総量規制マニュアルに載せる低煙源拡散式=JEAモデル(環境庁モデル)を作った際に書いた報文と,それを中国人の研究員と役人に説明したときの英文の資料を加え,さらに1976年の修士論文「三重三元クォーク模型の束縛ポテンシャル」および当時指導教官であったK助教授と共に書いた「Quark Molecule」という昔の雑誌への投稿論文を加えて提出しました。

結局,教授会まで行ったけど,その最終審査で論文の数が少ない,という理由で却下されたらしいということだったので,ある意味でお金を取られないのでホッとしたという記憶があります。 

そもそも,問題は論文の数ではなくて中味だろうし,内容を読んでもいないし理解もしてないな,などと思いましたが,論文の内容にもそれほど自信がなかったので別にいいかなと思い直しました。

 

しかし,彼の話だとお金持ちならもっとつまらない論文でもかまわないらしい,ということだったし,私の内容なら間単に取れるということだった(随分話が違う)ので「私学というか,この世界も所詮はお金か」と改めて感じたものです。

 

もっとも,自慢じゃないけど私は免許とか資格とか"お上から頂くもの"は全て大嫌いなので,それを取ろうとしたこともほとんどなくて,そういうものは卒業証書以外にはありませんから,基本的には生活費の足しになるという理由以外では博士も不要です。

 

まあ,私も就職してからは,論文やレポートは専門とは程遠い,流体力学関係か数値計算関係のものばかり書いていました。

 

そういえば1976年の修士論文「三重三元クォーク模型の束縛ポテンシャル」や「Quark Molecule」も,心ならずも私の本当の専門である量子電磁力学(QED)や場の量子論(QFT)におけるカイラル・カレントに関わるWard-Takahashi identityから生ずるAdler-Jackew anomaly,すなわち,トライアングル・アノマリーとは全く異なる題材のものです。

これらは,当時,本当の専門では修士論文の題材が見つからず,仕方なく丁度その頃発見されたJ/ψ粒子(これは後にチャームの発見と同定されました。)がカラー8重項のグルオンの1つではないか,などと推測をした結果であり,もともとは量子力学のシッフの古いアイデアを流用したものです。

つまり,これらはユニタリ群のカシミア演算子の既約表現に対する固有値の関数としてカラー・クォークや反クォークによるN体共鳴としての素粒子の質量公式を導くことにより,現在の技術ではエキゾチック粒子がなぜ発見されないか?という理由を群論的に考察したもので,私にとっては専門違いなので不本意なものでした。

 

(エキゾチック粒子とは,クォークそれ自身やクォーク4体以上のハドロン,あるいはカラー1重項以外の粒子です。) 

 

なお,「Quark Molecule」については1976年6月の「素粒子論研究」に掲載されています。

 

まあ,これを読むことが可能な人には実名がばれてしまうけど別に秘密じゃないから,ばれてもいいです。

私が自分の本当の細かい専門であると自認していた分野は,典型的な例としてはπ0 2γの崩壊確率として観測される量である量子電磁力学の摂動の1次の発散をくりこんだ結果として現われるアノマリーです。

 

(もしもカレントがカイラルでなければファりィの定理(Furry)によって,1次のような奇数次の摂動の計算結果は常にゼロになります。)

 

もっとも,これがカラー・クォークに関する話題と全く無関係というわけではありません。

アノマリーの存在はカラー・クォークのカラーが3色しかなく,したがってカラー対称性がユニタリ群としてはSU(3)に限られることの証拠になっています。

 

また,トフフト(t'Hooft)によって素粒子の理論がこうしたアノマリーからフリーになるためには,クォークのフレーバーとレプトンの世代数が完全に一致しなければならないことも示されています。

  

こうした重要な事実も,このアノマリーの存在から言えることです。

 

(2006年5/11の記事「波動関数の位相と電磁場」参照。。)

 

ところで,素粒子論とか宇宙論とか純理論的なことをやってきても,そうした知識や経験は,それ専門の研究所か大学ではなくて普通の科学計算のシミュレーションやアセスメントをやる程度の民間会社では全然役に立たないのじゃないか,と思われるかもしれませんが,実際にはしっかりと役に立ちました。

 

まあ,いろいろとあるのですが,典型例としては4次元時空の非ユークリッド幾何学が中心の一般相対性理論でさえ,ちゃんと利用できるということがあります。

 

つまり,山や谷などの起伏のあるでこぼこの地表面が境界であるような空間領域での気流などを解析する際に,2次元曲面を表わすためにメトリック・テンソルを使うのが非常に有効な手段となり,気体の運動を測地線の方程式のようなもので表現できることがわかります。

無駄話が長くなりましたが,この項目については終わりにします。

 

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

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

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

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

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

|

« 準線形計画法(ネットワーク輸送問題)(2) | トップページ | 目をそらす姑息な手段 »

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

コメント

この記事へのコメントは終了しました。

トラックバック


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

« 準線形計画法(ネットワーク輸送問題)(2) | トップページ | 目をそらす姑息な手段 »