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

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

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

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

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

すなわち,各枝は容量制限Ｌ_m≦ｘ_m≦Ｕ_m (Ｌ_m,Ｕ_mは±∞,正,負,0のいずれでも良い)を有するが,この他にｉ＝－ｊ_m,..,0,..,ｋ_mの各値について,ｔ_m,iが存在してｔ_m,i-1≦ｘ_m≦ｔ_m,iの各ｘ_mに対して,単位コストｃ_m,iを持つ。なお,ｔ_m,0＝0 である。

ｅ_mに関わる総コストは,ｘ_m＞ 0 のときは,ｔ_m,lm-1≦ｘ_m≦ｔ_m,lmならばΣ_k=1^lm-1ｃ_m,k(ｔ_m,k－ｔ_m,k-1)＋ｃ_m,lm (ｘ_m－ｔ_m,lm-1)(3-1a)であり,ｘ_m＜ 0 のときは,ｔ_m,-lm-1≦ｘ_m≦ｔ_m,-lmならばΣ_k=0^lmｃ_m,-k(ｔ_m,-k-1－ｔ_m,-k)＋ｃ_m,-lm (ｘ_m－ｔ_m,-lm-1)(3-1ｂ)である。

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

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

基底枝ｅ_m＝(ｉ,ｊ)に対しては,ｔ_m,k-1≦ｘ_m≦ｔ_m,kにおける単位コストｃ_m,kについて双対基底として,Π_j＋ｃ_m,k＝Π_i(3-2)となるように、{Π_n}(ｎ＝1,2,..,Ｎ)の組を計算する。

　次に,ｅ_m＝(ｉ,ｊ)が非基底のとき,ｘ_m＝ｔ_m.k-1ならばＤ_m＝Π_i－Π_j－ｃ_m,k ,ｘ_m＝ｔ_m.kならばＤ_m＝Π_j－Π_i＋ｃ_m,kとおく。 

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

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

つまり,全てのＤ_mがＤ_m≦0 なら,コスト関数においてｘ_mの±Δ_mの変化と共に変化し得る量Σｃ_m,kmｘ_mが(2-2)式と同様に変形されて,Δ_m＞0 の変化に対して必ず非減少となるからである。

そこで次に,得られた暫定的最小コスト解において,非基底枝ｅ_mに対してｘ_mが下界ｔ_m.km-1に等しい場合には,これを上界と見なして,新しいＤ_mの値としてのＤ_m^*をＤ_m^*＝Π_j－Π_i＋ｃ_m,km-1で与える。

Ｄ_m≦0 より－Ｄ_m＝Π_j－Π_i＋ｃ_m,km≧0 であり,単位コストｃ_m,kはｋに関して単調増加であるからＤ_m^*≦－Ｄ_mであるが,もしＤ_m^*＞0 ならｅ_mは基底に入る枝の候補となる。 

同様にｘ_mが上界ｔ_m.kmに等しい場合には,これを下界と見なして,新しいＤ_mの値としてのＤ_m^*をＤ_m^*＝Π_i－Π_j－ｃ_m,km+1で与える。

Ｄ_m≦0 より－Ｄ_m＝Π_i－Π_j－ｃ_m,km≧0 であり,単位コストｃ_m,kはｋに関して単調増加であるから,やはりＤ_m^*≦－Ｄ_mであるが,もしＤ_m^*＞0 ならｅ_mは基底に入る枝の候補となる。 

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

なぜなら,(3-1)式を,ｍ＝1からＭまで加えた総コストはΣ_m{Σ_k≦km-1ｃ_m,k(ｔ_m,k－ｔ_m,k-1)＋ｃ_m,kmｔ_m,km-1}＋Σ_ｅm∈ＵＤ_mｔ_m,km－Σ_ｅm∈ＬＤ_mｔ_m,km-1＋Σ_nΠ_nｒn－Σ_{￢ｅm∈Ｔ}Ｄ_mΔ_m(3-3)と書けるから,Ｄ_m≦0 によりΔ_m＞0 に対しては既に最小であり,上述の操作による非基底枝の境界を越えるΔ_m＜0 の方向へのｘ_mの変化に対しては,コスト関数を(3-3)式の形に変形した場合,ｘ_mの変化Δ_m^*＝－Δ_m＞0 についても,なお更新されたＤ_mの値Ｄ_m^*が全てゼロ以下となるからである。

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

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

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

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

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

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

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

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

流量は,全て非負の値にするため,新しい流量変数をｘ_m'≡ｘ_m－Ｌ_m (ｍ＝1,2,..,Ｍ)(A-1)で与え,上界をＵ_m－Ｌ_mとする。

(1-1)より,ｒ_n＝Σ_ｅm∈Ａnｘ_m－Σ_ｅm∈Ｂnｘ_mであるから,新しい供給量ｒ_n'をｒ_n'＝Σ_ｅm∈Ａnｘ_m'－Σ_ｅm∈Ｂnｘ_m'＝ｒ_n－Σ_ｅm∈ＡnＬ_m＋Σ_ｅm∈ＢnＬ_m (ｎ＝1,2,..,Ｎ)(A-2)と変換して,ｒ_N+1'＝0 とおく。

　人為枝ｅ_M+iはｒ_i'＞0 のとき(ｉ,Ｎ＋1)で,ｒ_i'≦0 のとき(Ｎ＋1,ｉ)とする。

また,全ての枝ｅ_mの単位コストをｐ_m(ｍ＝1,2,..,Ｍ,Ｍ＋1,..,Ｍ＋Ｎ)として,ｅ_mが実枝ならｐ_mに 0 を人為枝なら 1 を与えることにより１つの線型輸送問題ができる。

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

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

　条件:Σ_ｅm∈Ａnｘ_m'－Σ_ｅm∈Ｂnｘ_m'＝ｒ_n'(ｎ＝1,2,..,Ｎ,Ｎ＋1) (A-3); 0≦ｘ_m'≦ Ｕ_m－Ｌ_m (ｍ＝1,2,..,Ｍ)(A-4a);0≦ｘ_m'(ｍ＝Ｍ＋1,..,Ｍ＋Ｎ)(A-4b)

　目的:ｚ＝Σ_m=1^M+Nｐ_mｘ_m'(A-5)を最小化する。

　ただし,ｐ_m＝0 (ｍ＝1,2,..,Ｍ)(A-6a)；ｐ_m＝1(ｍ＝Ｍ＋1,..,Ｍ＋Ｎ)(A-6b)である。

補助問題の初期可能木解はＮ個の基底枝を人為枝ｅ_M+1,ｅ_M+2,．．,ｅ_M+Nとして,それらの流量の初期値をｒ_i'＞0 ならｘ_M+i'＝ ｒ_i'(A-7a),ｒ_i'≦0 ならｘ_M+i'＝－ｒ_i'(A-7b)と設定し,Ｍ個の非基底枝ｅ_m(ｍ＝1,2,..,Ｍ)については,流量をｘ_m'＝0 (ｍ＝1,2,..,Ｍ)(A-8)と設定すれば得られる。

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

以下,ｚ＝0 の場合のみを考える。

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

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

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

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

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

参考文献 

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(Ｖ.フバータル：阪田省二郎,藤野和雄,田口 東 訳)「線形計画法」(上)(下)(啓学出版)(1988)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

← クリックして投票してください。(ブログ村科学ブログランキング）

    物理学