« 準線形計画法(ネットワーク輸送問題)(1) | トップページ | 準線形計画法(ネットワーク輸送問題)(3) »

2007年7月15日 (日)

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

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

 

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

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

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

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

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

節点iの先行点piとは,iから根までの単純経路上にあって,深さが(di1)の節点のことである。p1=0 と定義する。

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

 

一方,fを節点集合V={1,2,..,N}からVの上への1対1の写像であるとする。Ui≠φでf(j)=iのとき,{f(k):j+1≦k≦j+|Ui|}=Ui (ただし,|A|は有限集合Aの元の個数)が成立すれば,この写像fを1つの継続点配列と呼ぶ。

1つの継続点配列が与えられたとき,節点iの糸siとは,この配列でiに続く節点,つまりf(j)=iならf(j+1)のことである。配列の最後の糸は根1であると定義する。

iに根付く極大木の最後の節点をniとすると,niは次の条件のうちの1つを満足しなければならない。:(a)sni=1(b)psniは節点iから根までの道の上にある。

(注)つまり,sni≠1ならpsni≠0 であり,sniから根までの道の上でのsniの先行点がpsniなので,psniはもちろんsniから根までを結ぶ道の上にある。

 

 そしてsniはniから根1までをつなぐ|Uni|個の点のうちのni以外のどれか1つである。

 

 しかもniはiに根付く極大木の最後の節点だからsniはi→ni→1という道の上にあり,psniはsni→1なる道の上にあるから,結局psniはiと根1を結ぶ道の上にあることになる。

次にeklがiとpiを結ぶ枝であるとする。

 

kl(pi,i)のとき,mi=ki ,ekl=(i,pi)のとき,mi=-k と定義する。ekl上の流量はαiで表わすことにする。

基底に入る枝をeφ(u,v)とするとき,更新手順は以下の「アルゴリズム1」および「アルゴリズム2」に示す通りである。

(1)アルゴリズム1

 

① 初期化

. γ1とγ2を初期化する。

φ=Lφならγ1=-1,γ2=1;

φ=Uφならγ1=1,γ2=-1とおく。

b.Δを臨界値としておく。

Δ=Uφ-Lφ とおく。

1とδ2を初期化する。

δ1=u2=vとおく。

min(du,dv)より大きい深さラベルを持つuからvへの部分経路上の最大許容流量変動Δを決定する。

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

u-dv0 ならd=dv-du ,μ=2とおく。du-dv=0 なら③へ進む。du-dv>0 ならd=du-dv ,μ=1とおく。

b.δ,γと計数を設定する。

δ=δμ,γ=γμ,k=1とする。

.増加流か減少流か?

δγ>0 ならeへ進む。

.増加流

|mδ|-αδ>Δなら,δ=pδとしてfに進む。さもなければ,Δ=U|mδ|-αδ,λ=δ,δ=pδとしてfに進む。

.減少流

αδ-L|mδ|>Δなら,δ=pδとする。さもなければ,Δ=αδ-L|mδ|,λ=δ,δ=pδとする。

.δの深さ=min(du,dv)

k<dならk=k+1とおきcに進む。

. δμの再設定

δμ=δとおく。

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

.道の終わりか?

δ1=δ2なら,w=δ1として終了する。さもなければk=1とおく。

.δのロード

δ=δk とおく。

.増加流か減少流か?

δγk0 ならeへ進む。

.増加流

|mδ|-αδ>Δなら,δk=pδとしてfに進む。さもなければ,Δ=U|mδ|-αδ,μ=k,λ=δ,δk=pδとしてfに進む。

.減少流

αδ-L|mδ|>Δなら,δk=pδとする。さもなければ,Δ=αδ-L|mδ|,μ=k,λ=δ,δk=pδとする。

.両側を調べたか?

k=1ならk=2として,bへ進む。さもなければaへ進む。

「アルゴリズム1」の終了時には,最大許容流量変動Δ,出る枝e|mλ|が定まり,uからvへの道はuからwの道とvからwの道によって与えられる。

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

(2)アルゴリズム2

① 全更新が必要か否か?

Δ≠Uφ-Lφなら③へ進む。

②更新流の再設定

.閉路に対する初期設定

δ1=u2=v,k=1とする。

.枝eφの流量更新

φ=Uφならxφ=Lφとする。さもなければxφ=Uφとする。

.パラメータの初期化

δ=δk,γ=γkΔとおく。

d.節点かwか?

δ=wならhへ進む。

.増加流か減少流か?

δ0 ならβ=1,mδ<0 ならβ=-1とおく。

f.更新流の再設定

αδ=αδ-γβとおきかえる。

g.次の先行点

δ=pδとしdに進む。

h.k=1ならk=2とおきcに進む。さもなければ終了する。

③初期化

a.双対変数の変更

σ=Dφとおく。

b.入る枝の更新流量は?

φ=Uφなら,Δ'=Uφ-Δ,σ=-σとする。さもなければ,Δ'=Lφ+Δとする。

C.q,q'の初期化

μ=1ならq=u,q'=v,ε=-φ,σ=-σとする。さもなければq=v,q'=u,ε=φとする。

d.i,j,γの初期化

i=q,j=-p,γ=γkΔとおく。

e.λの先行点のセーブ

λ'=pλとしておく。

f.q'の深さラベルをセーブ

F=dq'1としておく。

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

.双対変数の更新

Πi=Πi+σとおく。

.流量のセーブ

α'=αiとしておく。

c.流量の更新

αi=Δ'とする。

d.流れの方向のセーブ

i0 ならβ=1, mi<0 ならβ=-1とおく。

e.枝のセーブ

m=|mi|と枝番号をセーブする。

 

.枝ラベルの更新

i=εとする。

g. iの深さdi ,およびFとdiの差をセーブする。

'=di,L=F-diとしておく。

h. iの深さの更新

i=Fとする。

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

a. iから始める。

z=i,x=siとおく。

b. xは1つの継続点か否か?

x≦F'なら⑥へ進む。

c.双対変数とxの深さの更新

Πx=Πx+σ,dx=dx+Lと更新する。

d.続く糸

z=x,x=sxとしてbへ進む。

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

. jから始める。

r=jとおく。

b. rは逆糸か?

riならば⑦へ進む。

.続く糸

r=srとしてbに進む。

⑦先行点順列と糸の更新

.最終更新か?

i=λならiに進む。

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

Δ'=α'-γβとおきかえる。

c. jの枝ラベルを決める。

ε=-βmとする。

d. rとzの糸の更新

r=x,sz=jとおく。

e. iをセーブする。

r=iとおく。

f. iの更新

i=jとおく。

g. jの更新

j=pjとおく。

h. iの先行点の更新

i=r,F=F+1として④へと進む。

i. rとzの糸の更新

r=x,sz=sq'とする。

j. q'の糸の更新

q'=qとする。

k. qの先行点の更新

q=q'とする。

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

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

a.閉路に対する設定

μ=1ならδ1=λ',δ2=q',k=1とおく。さもなければ,δ1=q',δ2=λ',k=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(V.フバータル:阪田省二郎,藤野和雄,田口 東 訳)「線形計画法」(上)(下)(啓学出版)(1988)

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

 

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

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

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

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

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

|

« 準線形計画法(ネットワーク輸送問題)(1) | トップページ | 準線形計画法(ネットワーク輸送問題)(3) »

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

コメント

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

トラックバック


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

« 準線形計画法(ネットワーク輸送問題)(1) | トップページ | 準線形計画法(ネットワーク輸送問題)(3) »