CC BY-NC-SA 3.0
3.4 Pablo Meets Dantzig
線形関数f(x1,...,xn)を最大化するxi≥0を
Mx=v,x:=(x1,...,xn)T
を満たすように探すのがDantzig’s algorithmだが,これをこのまま適用できない場合もある
Examle 42
Pabloの場合, x≥5,y≥7だから, x1=x−5,x2=y−7と置き換える.
15≤x+y≤25は3≤x1+x2≤13となるが, Mx=vという形ではない.そこで, x3≥0,x4≥4なる変数をさらに導入して,c1:=x1+x2−x3=3,c2:=x1+x2+x4=13を束縛条件とする.このように,不等式の条件を等式の条件に変換するために加えられる変数をslack variablesという.こうして
(11−101101)(x1x2x3x4)=(313)
が拘束条件Mx=vとなった.s=5x+10yを最小化するため, 最大化する関数fをf=−5x−10y+95=−s+95=−5x1−10x2
最大化するx1,x2を求める.
拡大係数行列は
(11−100311010135100010)
となる.
第三行の係数がすべて非負だからx1,x2=0としてしまいたいが,slack valuableの係数が負であると(この場合,第一行のx3)slack valuableが非負であるという条件のもとで解けなくなってしまうので,さらにartificial variables を導入する.大きなα>0によって,fをf−αx5−αx6とすれば,fが最大となるのにx5,x6=0が必要.
拡大係数行列は
(11−10100311010101351000101010)↓(artificial variablesの消去)(11−101003110101013−15−1010−10001−160)↓ (3.3と同じアルゴリズム)(111010030011−1101005505101−15)
x1=3,x4=10, 他の係数を0とするとf=−15となって,mins=−f+95=110が解けて,さらにx=8,y=7となる.
(正直なんで解けてるのかわからん)
0 件のコメント:
コメントを投稿