2017年5月28日日曜日

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

CC BY-NC-SA 3.0

3.4 Pablo Meets Dantzig

線形関数を最大化する

を満たすように探すのがDantzig’s algorithmだが,これをこのまま適用できない場合もある

Examle 42

Pabloの場合, だから, と置き換える.
は3となるが, という形ではない.そこで, なる変数をさらに導入して,を束縛条件とする.このように,不等式の条件を等式の条件に変換するために加えられる変数をslack variablesという.こうして

が拘束条件となった.を最小化するため, 最大化する関数
最大化するを求める.
拡大係数行列は

となる.
第三行の係数がすべて非負だからとしてしまいたいが,slack valuableの係数が負であると(この場合,第一行の)slack valuableが非負であるという条件のもとで解けなくなってしまうので,さらにartificial variables を導入する.大きなによって,とすれば,が最大となるのにが必要.
拡大係数行列は

, 他の係数をとするととなって,が解けて,さらにとなる.
(正直なんで解けてるのかわからん)

0 件のコメント:

コメントを投稿