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

CC BY-NC-SA 3.0

3.4 Pablo Meets Dantzig

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

Examle 42

Pabloの場合, $x \geq 5, y \geq 7$だから, $x_1 = x-5, x_2 = y-7$と置き換える.
$15 \leq x + y \leq 25$は3$\leq x_1 + x_2 \leq 13$となるが, $Mx=v$という形ではない.そこで, $x_3 \geq 0, x_4 \geq 4$なる変数をさらに導入して,$c_1 := x_1 + x_2 - x_3 = 3, c_2 := x_1 + x_2 + x_4 = 13$を束縛条件とする.このように,不等式の条件を等式の条件に変換するために加えられる変数をslack variablesという.こうして
$$\left( \begin{array}{} 1 & 1 & -1 & 0 \\ 1 & 1 & 0 & 1 \end{array}\right) \left(\begin{array}{} x_1 \\x_2 \\ x_3 \\ x_4 \end{array} \right) = \left( \begin{array}{} 3 \\ 13\end{array} \right)$$
が拘束条件$Mx=v$となった.$s = 5x + 10y$を最小化するため, 最大化する関数$f$を $$f = -5x - 10y +95 = -s + 95= -5x_1 -10x_2$$
最大化する$x_1, x_2$を求める.
拡大係数行列は
$$\left( \begin{array}{} 1 & 1 & -1& 0 & 0 & 3 \\ 1 & 1 & 0 & 1 & 0 & 13 \\ 5 & 10 & 0& 0 & 1 & 0 \end{array}\right)$$
となる.
第三行の係数がすべて非負だから$x_1, x_2=0$としてしまいたいが,slack valuableの係数が負であると(この場合,第一行の$x_3$)slack valuableが非負であるという条件のもとで解けなくなってしまうので,さらにartificial variables を導入する.大きな$\alpha>0$によって,$f$を$f -\alpha x_5 -\alpha x_6$とすれば,$f$が最大となるのに$x_5, x_6=0$が必要.
拡大係数行列は
$$\left( \begin{array}{} 1 & 1 & -1 & 0 & 1 & 0 & 0 & 3 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 13 \\ 5 & 10 & 0 & 0 & 10 & 10 & 1 & 0 \end{array}\right) \\ \downarrow \mbox{(artificial variablesの消去)} \\ \left( \begin{array}{} 1 & 1 & -1 & 0 & 1 & 0 & 0 & 3 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 13 \\ -15 & -10 & 10 & -10 & 0 & 0& 1 & -160& \end{array}\right) \\ \downarrow \ \ \mbox{(3.3と同じアルゴリズム)} \\ \left( \begin{array}{} 1 & 1 & 1 & 0 & 1 & 0 & 0 & 3 \\ 0 & 0 & 1 & 1 & -1 & 1 & 0 & 10 \\ 0 & 5 & 5 & 0 & 5 & 10 & 1 & -15 \end{array}\right)$$
$x_1 = 3, x_4 = 10$, 他の係数を$0$とすると$f=-15$となって,$\min s = -f+95=110$が解けて,さらに$x=8, y=7$となる.
(正直なんで解けてるのかわからん)