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

続きです。線形輸送問題のアルゴリズムの１例,を具体的に述べます。これはプログラムそのものを記述したものなので,少々冗長で退屈なものです。

実際にプログラムを組む必要がないなら,必ずしも全てを追跡する必要はないと思います。まあこんな感じのものである,ということで眺めてみてください。

2-3.計算機における実際のアルゴリズム

　計算機で実際に輸送問題を解くアルゴリズムの例としてAli,Helgason,Kennington,Lallによるものを紹介しておく。

　まず,節点の１つ：１を根と呼び固定しておく。

節点ｉの深さｄ_iとは,iから単純経路によって根に到るまでの枝の個数である。ｄ₁＝0 と定義する。

節点ｉの先行点ｐ_iとは,ｉから根までの単純経路上にあって,深さが(ｄ_i－1)の節点のことである。ｐ₁＝0 と定義する。

節点ｊは,ｊから根までの間に節点ｉがあるときｉの継続点と呼ばれる。Ｕ_iをｉの全ての継続点の集合とする。

一方,ｆを節点集合Ｖ＝{1,2,..,Ｎ}からＶの上への１対１の写像であるとする。Ｕ_i≠φでｆ(ｊ)＝ｉのとき,{ｆ(ｋ):ｊ＋1≦ｋ≦ｊ＋|Ｕ_i|}＝Ｕ_i (ただし,|Ａ|は有限集合Ａの元の個数)が成立すれば,この写像ｆを１つの継続点配列と呼ぶ。

１つの継続点配列が与えられたとき,節点ｉの糸ｓ_iとは,この配列でｉに続く節点,つまりｆ(ｊ)＝ｉならｆ(ｊ＋1)のことである。配列の最後の糸は根１であると定義する。

ｉに根付く極大木の最後の節点をｎ_iとすると,ｎ_iは次の条件のうちの１つを満足しなければならない。：(ａ)ｓ_ni＝１(ｂ)ｐ_ｓniは節点ｉから根までの道の上にある。

※(注)つまり,ｓ_ni≠１ならｐ_sni≠0 であり,ｓ_niから根までの道の上でのｓ_niの先行点がｐ_ｓniなので,ｐ_ｓniはもちろんｓ_niから根までを結ぶ道の上にある。

　そしてｓ_niはｎ_iから根１までをつなぐ|Ｕ_ni|個の点のうちのｎ_i以外のどれか１つである。

　しかもｎ_iはｉに根付く極大木の最後の節点だからｓ_niはi→ｎ_i→１という道の上にあり,ｐ_ｓniはｓ_ni→１なる道の上にあるから,結局ｐ_ｓniはｉと根１を結ぶ道の上にあることになる。

次にｅ_klがｉとｐ_iを結ぶ枝であるとする。

ｅ_kl＝(ｐ_i,ｉ)のとき,ｍ_i＝ｋ_i ,ｅ_kl＝(ｉ,ｐ_i)のとき,ｍ_i＝－ｋ_ｉ と定義する。ｅ_kl上の流量はα_iで表わすことにする。

基底に入る枝をｅ_φ＝(ｕ,ｖ)とするとき,更新手順は以下の「アルゴリズム１」および「アルゴリズム２」に示す通りである。

(１)アルゴリズム１

① 初期化

ａ. γ₁とγ₂を初期化する。

ｘ_φ＝Ｌ_φならγ₁＝－1,γ₂＝1；

ｘ_φ＝Ｕ_φならγ₁＝1,γ₂＝－1とおく。

ｂ．Δを臨界値としておく。

Δ＝Ｕ_φ－Ｌ_φ とおく。

ｃ.δ₁とδ₂を初期化する。

δ₁＝ｕ,δ₂＝ｖとおく。

② min(ｄ_u,ｄ_v)より大きい深さラベルを持つｕからｖへの部分経路上の最大許容流量変動Δを決定する。

ａ.最大深さラベルを持つ節点から始める。

ｄ_u－ｄ_v＜0 ならｄ＝ｄ_v－ｄ_u ,μ＝2とおく。ｄ_u－ｄ_v＝0 なら③へ進む。ｄ_u－ｄ_v＞0 ならｄ＝ｄ_u－ｄ_v ,μ＝1とおく。

ｂ．δ,γと計数を設定する。

δ＝δ_μ,γ＝γ_μ,ｋ＝1とする。

ｃ.増加流か減少流か？

ｍ_δγ＞0 ならｅへ進む。

ｄ.増加流

Ｕ_|ｍδ|－α_δ＞Δなら,δ＝ｐ_δとしてｆに進む。さもなければ,Δ＝Ｕ_|ｍδ|－α_δ,λ＝δ,δ＝ｐ_δとしてｆに進む。

ｅ.減少流

α_δ－Ｌ_|ｍδ|＞Δなら,δ＝ｐ_δとする。さもなければ,Δ＝α_δ－Ｌ_|ｍδ|,λ＝δ,δ＝ｐ_δとする。

ｆ.δの深さ＝min(ｄ_u,ｄ_v)

ｋ＜ｄならｋ＝ｋ＋1とおきｃに進む。

ｇ. δ_μの再設定

δ_μ＝δとおく。

③ｕからｖへの残りの道の上での最大許容流量変動Δの決定

ａ.道の終わりか？

δ₁＝δ₂なら,ｗ＝δ₁として終了する。さもなければｋ＝1とおく。

ｂ.δのロード

δ＝δ_k とおく。

ｃ.増加流か減少流か？

ｍ_δγ_k＞0 ならｅへ進む。

ｄ.増加流

Ｕ_|ｍδ|－α_δ＞Δなら,δ_k＝ｐ_δとしてｆに進む。さもなければ,Δ＝Ｕ_|ｍδ|－α_δ,μ＝ｋ,λ＝δ,δ_k＝ｐ_δとしてｆに進む。

ｅ.減少流

α_δ－Ｌ_|ｍδ|＞Δなら,δ_k＝ｐ_δとする。さもなければ,Δ＝α_δ－Ｌ_|ｍδ|,μ＝ｋ,λ＝δ,δ_k＝ｐ_δとする。

ｆ.両側を調べたか？

ｋ＝1ならｋ＝2として,ｂへ進む。さもなければａへ進む。

「アルゴリズム１」の終了時には,最大許容流量変動Δ,出る枝ｅ_|ｍλ|が定まり,ｕからｖへの道はｕからｗの道とｖからｗの道によって与えられる。

これに続く更新のアルゴリズムは次の通りである。

(２)アルゴリズム２

① 全更新が必要か否か？

Δ≠Ｕ_φ－Ｌ_φなら③へ進む。

②更新流の再設定

ａ.閉路に対する初期設定

δ₁＝ｕ,δ₂＝ｖ,ｋ＝1とする。

ｂ.枝ｅ_φの流量更新

ｘ_φ＝Ｕ_φならｘ_φ＝Ｌ_φとする。さもなければｘ_φ＝Ｕ_φとする。

ｃ.パラメータの初期化

δ＝δ_k,γ＝γ_kΔとおく。

ｄ.節点かｗか？

δ＝ｗならｈへ進む。

ｅ.増加流か減少流か？

ｍ_δ＞0 ならβ＝1,ｍ_δ＜0 ならβ＝－1とおく。

ｆ.更新流の再設定

α_δ＝α_δ－γβとおきかえる。

ｇ.次の先行点

δ＝ｐ_δとしｄに進む。

ｈ.ｋ＝1ならｋ＝2とおきｃに進む。さもなければ終了する。

③初期化

ａ.双対変数の変更

σ＝Ｄ_φとおく。

ｂ.入る枝の更新流量は？

ｘ_φ＝Ｕ_φなら,Δ'＝Ｕ_φ－Δ,σ＝－σとする。さもなければ,Δ'＝Ｌ_φ＋Δとする。

C.ｑ,ｑ'の初期化

μ＝1ならｑ＝ｕ,ｑ'＝ｖ,ε＝－φ,σ＝－σとする。さもなければｑ＝ｖ,ｑ'＝ｕ,ε＝φとする。

ｄ.ｉ,ｊ,γの初期化

ｉ＝ｑ,ｊ＝－ｐ,γ＝γ_kΔとおく。

ｅ.λの先行点のセーブ

λ'＝ｐ_λとしておく。

ｆ.ｑ'の深さラベルをセーブ

Ｆ＝ｄ_q'＋1としておく。

④ｉにおける双対変数、流量、枝ラベルの更新

ａ.双対変数の更新

Π_i＝Π_i＋σとおく。

ｂ.流量のセーブ

α'＝α_iとしておく。

ｃ.流量の更新

α_i＝Δ'とする。

ｄ.流れの方向のセーブ

ｍ_i＞0 ならβ＝1, ｍ_i＜0 ならβ＝－1とおく。

ｅ.枝のセーブ

ｍ＝|ｍ_i|と枝番号をセーブする。

ｆ.枝ラベルの更新

ｍ_i＝εとする。

ｇ. ｉの深さｄ_{i ,}およびＦとｄ_iの差をセーブする。

Ｆ'＝ｄ_i,Ｌ＝Ｆ－ｄ_iとしておく。

ｈ. ｉの深さの更新

ｄ_i＝Ｆとする。

⑤ｉの最後の継続点を決定し,双対変数と深さラベルを更新する。

ａ. ｉから始める。

ｚ＝ｉ,ｘ＝ｓ_iとおく。

ｂ. ｘは１つの継続点か否か？

ｄ_x≦Ｆ'なら⑥へ進む。

ｃ.双対変数とｘの深さの更新

Π_x＝Π_x＋σ,ｄ_x＝ｄ_x＋Ｌと更新する。

ｄ.続く糸

ｚ＝ｘ,ｘ＝ｓ_xとしてｂへ進む。

⑥節点ｉに対して,その"逆糸＝親"を発見する。

ａ. ｊから始める。

ｒ＝ｊとおく。

ｂ. ｒは逆糸か？

ｓ_r＝iならば⑦へ進む。

ｃ.続く糸

ｒ＝ｓ_rとしてｂに進む。

⑦先行点順列と糸の更新

ａ.最終更新か？

ｉ＝λならｉに進む。

ｂ. ｊに対する更新流量の決定

Δ'＝α'－γβとおきかえる。

ｃ. ｊの枝ラベルを決める。

ε＝－βｍとする。

ｄ. ｒとｚの糸の更新

ｓ_r＝ｘ,ｓ_z＝ｊとおく。

ｅ. ｉをセーブする。

ｒ＝ｉとおく。

ｆ. ｉの更新

ｉ＝ｊとおく。

ｇ. ｊの更新

ｊ＝ｐ_jとおく。

ｈ. ｉの先行点の更新

ｐ_i＝ｒ,Ｆ＝Ｆ＋1として④へと進む。

ｉ. ｒとｚの糸の更新

ｓ_r＝ｘ,ｓ_z＝ｓ_q'とする。

ｊ. ｑ'の糸の更新

ｓ_q'＝ｑとする。

ｋ. ｑの先行点の更新

ｐ_q＝ｑ'とする。

⑧ｑ'からλ'までの道の上の流量の更新

ａを次のように変えてｂを削除することを除いて②と同じである。

ａ.閉路に対する設定

μ＝1ならδ₁＝λ',δ₂＝ｑ',ｋ＝1とおく。さもなければ,δ₁＝ｑ',δ₂＝λ',ｋ＝1とおく。

以上である。

※     ここまでが,既存の「線型コスト関数に対する輸送問題のアルゴリズム」の１例です。今回はここまでにして,次回は「準線型コスト関数」に対するオリジナルな内容を述べる予定です。

参考文献

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)

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

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

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

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

    物理学