最適化・線形計画法の問題

双対問題　$(\mathrm{P})$ は「$\max {\mathbf{c}}^{\mathsf{T}}\mathbf{x}$, $A\mathbf{x}\le \mathbf{b}$, $\mathbf{x}\ge 0$」の形なので、双対問題は「$\min {\mathbf{b}}^{\mathsf{T}}\mathbf{y}$, $A^{\mathsf{T}}\mathbf{y}\ge \mathbf{c}$, $\mathbf{y}\ge 0$」である。
$$(\mathrm{D})\begin{array}{rl}\text{minimize}& 10y_1+22y_2+24y_3\\ \text{subject to}& y_1+2y_2+y_3\ge 2,\\ & y_1+y_2+3y_3\ge 2,\\ & y_1+3y_2+y_3\ge 3,\\ & y_1+4y_2+y_3\ge 4,\\ & y_1,y_2,y_3\ge 0.\end{array}$$

$(\mathrm{P})$ の最適解（単体法）　スラック変数 $s_1,s_2,s_3\ge 0$ を入れ、$\mathbf{x}=0$ から始める。

目的関数の係数が最大の $x_4$ を増やす。比は $10/1=10$, $22/4=\frac{11}{2}$, $24/1=24$ なので第 $2$ 制約で止まり、
$$x_4=\frac{11}{2}-\frac{1}{2}{x}_1-\frac{1}{4}{x}_2-\frac{3}{4}{x}_3-\frac{1}{4}{s}_2.$$
これを代入すると
$$\begin{array}{rl}z& =22+x_2-s_2,\\ s_1& =\frac{9}{2}-\frac{1}{2}{x}_1-\frac{3}{4}{x}_2-\frac{1}{4}{x}_3+\frac{1}{4}{s}_2,\\ s_3& =\frac{37}{2}-\frac{1}{2}{x}_1-\frac{11}{4}{x}_2-\frac{1}{4}{x}_3+\frac{1}{4}{s}_2.\end{array}$$
次に $x_2$ を増やす。比は $s_1$ の式で $\frac{9}{2}÷\frac{3}{4}=6$, $x_4$ の式で $\frac{11}{2}÷\frac{1}{4}=22$, $s_3$ の式で $\frac{37}{2}÷\frac{11}{4}=\frac{74}{11}$ なので $s_1$ の式で止まり、
$$x_2=6-\frac{2}{3}{x}_1-\frac{1}{3}{x}_3-\frac{4}{3}{s}_1+\frac{1}{3}{s}_2.$$
これを代入すると
$$z=28-\frac{2}{3}{x}_1-\frac{1}{3}{x}_3-\frac{4}{3}{s}_1-\frac{2}{3}{s}_2$$
となり、非基底変数の係数がすべて負なので最適である。最適解は $x_1=x_3=0$, $x_2=6$, $x_4=\frac{11}{2}-\frac{6}{4}=4$、最適値は $28$。このとき第 $3$ 制約は $0+18+0+4=22<24$ でスラック $s_3=2>0$ である。

相補性条件　${\mathbf{x}}^{\ast }=(0,6,0,4)$ が $(\mathrm{P})$ の最適解なので、$(\mathrm{D})$ のどの最適解 $\mathbf{y}$ も ${\mathbf{x}}^{\ast }$ と相補性条件をみたす。
- $x_2^{\ast }=6>0$ より $(\mathrm{D})$ の第 $2$ 制約は等号：$y_1+y_2+3y_3=2$。
- $x_4^{\ast }=4>0$ より $(\mathrm{D})$ の第 $4$ 制約は等号：$y_1+4y_2+y_3=4$。
- $(\mathrm{P})$ の第 $3$ 制約に余裕がある（$22<24$）ので $y_3=0$。

よって $y_1+y_2=2$, $y_1+4y_2=4$ を解いて $3y_2=2$ より $y_2=\frac{2}{3}$, $y_1=\frac{4}{3}$。$(\mathrm{D})$ の最適解はこの $1$ 通りしかありえない。

確認　$\mathbf{y}=\left(\frac{4}{3},\frac{2}{3},0\right)$ は
$$\frac{4}{3}+\frac{4}{3}=\frac{8}{3}\ge 2,\frac{4}{3}+\frac{2}{3}=2\ge 2,\frac{4}{3}+2=\frac{10}{3}\ge 3,\frac{4}{3}+\frac{8}{3}=4\ge 4$$
と $\mathbf{y}\ge 0$ をみたし実行可能で、目的関数値は $10\cdot \frac{4}{3}+22\cdot \frac{2}{3}=\frac{40+44}{3}=28$ となり $(\mathrm{P})$ の最適値と一致する。弱双対定理より $(\mathrm{D})$ の値はつねに $28$ 以上なので、これは $(\mathrm{D})$ の最適解である（単体法の最終辞書で $s_1,s_2,s_3$ の係数の符号を変えたもの $\frac{4}{3},\frac{2}{3},0$ とも一致する）。

以上より $(y_1,y_2,y_3)=\left(\frac{4}{3},\frac{2}{3},0\right)$。

双対問題 (D) は、$y_1,y_2,y_3\ge 0$ のもとで $10y_1+22y_2+24y_3$ を最小化する問題で、制約は
$y_1+2y_2+y_3\ge 2$, $y_1+y_2+3y_3\ge 2$, $y_1+3y_2+y_3\ge 3$, $y_1+4y_2+y_3\ge 4$ である。

まず (P) の最適解の見当をつける。$x_2,x_4$ を基底に取り、第 1, 2 制約を等号とすると $x_2+x_4=10$, $x_2+4x_4=22$ より $x_4=4$, $x_2=6$, $x_1=x_3=0$。第 3 制約は $18+4=22\le 24$ で成り立つ。目的関数値は $12+16=28$。

相補性より、第 3 制約は余裕があるので $y_3=0$。$x_2,x_4>0$ なので双対の第 2, 4 制約は等号になる。
$y_1+y_2=2$, $y_1+4y_2=4$ より $3y_2=2$, $y_2=\frac{2}{3}$, $y_1=\frac{4}{3}$。

確認として、双対の全制約を調べる。
- 第 1: $\frac{4}{3}+\frac{4}{3}+0=\frac{8}{3}\ge 2$ (成り立つ)
- 第 2: $\frac{4}{3}+\frac{2}{3}=2\ge 2$ (等号)
- 第 3: $\frac{4}{3}+2=\frac{10}{3}\ge 3$ (成り立つ)
- 第 4: $\frac{4}{3}+\frac{8}{3}=4\ge 4$ (等号)

双対の目的関数値は $10\cdot \frac{4}{3}+22\cdot \frac{2}{3}=\frac{40+44}{3}=28$ で、(P) の値 28 と一致するので、弱双対性から両者とも最適である。

別の方法の検算として、第 4 制約を等号とすると $y_1+y_3=4-4y_2$、目的関数は $40-18y_2+14y_3$、第 2 制約から $y_3\ge \max (0,(3y_2-2)/2)$。$y_2\le \frac{2}{3}$ では $40-18y_2$ で減少、$y_2>\frac{2}{3}$ では $26+3y_2$ で増加するので、$y_2=\frac{2}{3}$ で最小 28 となり、同じ結果を得る。

よって $(y_1,y_2,y_3)=\left(\frac{4}{3},\frac{2}{3},0\right)$。