Loading [MathJax]/jax/output/HTML-CSS/jax.js

2017年5月27日土曜日

Linear Algebra (D. Cherney et al.) 二日目

CC BY-NC-SA 3.0

3.4 Pablo Meets Dantzig

線形関数f(x1,...,xn)を最大化するxi0
Mx=v,x:=(x1,...,xn)T
を満たすように探すのがDantzig’s algorithmだが,これをこのまま適用できない場合もある

Examle 42

Pabloの場合, x5,y7だから, x1=x5,x2=y7と置き換える.
15x+y25は3x1+x213となるが, Mx=vという形ではない.そこで, x30,x44なる変数をさらに導入して,c1:=x1+x2x3=3,c2:=x1+x2+x4=13を束縛条件とする.このように,不等式の条件を等式の条件に変換するために加えられる変数をslack variablesという.こうして
(11101101)(x1x2x3x4)=(313)
が拘束条件Mx=vとなった.s=5x+10yを最小化するため, 最大化する関数ff=5x10y+95=s+95=5x110x2
最大化するx1,x2を求める.
拡大係数行列は
(11100311010135100010)
となる.
第三行の係数がすべて非負だからx1,x2=0としてしまいたいが,slack valuableの係数が負であると(この場合,第一行のx3)slack valuableが非負であるという条件のもとで解けなくなってしまうので,さらにartificial variables を導入する.大きなα>0によって,ffαx5αx6とすれば,fが最大となるのにx5,x6=0が必要.
拡大係数行列は
(1110100311010101351000101010)(artificial variablesの消去)(1110100311010101315101010001160)  (3.3と同じアルゴリズム)(111010030011110100550510115)
x1=3,x4=10, 他の係数を0とするとf=15となって,mins=f+95=110が解けて,さらにx=8,y=7となる.
(正直なんで解けてるのかわからん)

0 件のコメント:

コメントを投稿