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

変数が 5 個で制約が 2 本なので、変数が 2 個になる双対問題を解き、相補性条件から主問題の最適解を求める。

双対問題 $(\mathrm{P})$ は「$\min {\mathbf{c}}^T\mathbf{x}$, $A\mathbf{x}\ge \mathbf{b}$, $\mathbf{x}\ge 0$」の形なので、双対問題 $(\mathrm{D})$ は「$\max {\mathbf{b}}^T\mathbf{y}$, $A^T\mathbf{y}\le \mathbf{c}$, $\mathbf{y}\ge 0$」である。具体的には
$$(\mathrm{D})\begin{array}{rlr}\text{maximize}& 5y_1+3y_2& \\ \text{subject to}& y_1+y_2\le 3& (1)\\ & 2y_1-y_2\le 2& (2)\\ & y_1+3y_2\le 8& (3)\\ & 3y_1+y_2\le 5& (4)\\ & 2y_1+2y_2\le 7& (5)\\ & y_1,y_2\ge 0& \end{array}$$
となる。$(k)$ は $x_k$ の列に対応する制約である。

双対問題の最適値 $(\mathrm{D})$ の任意の実行可能解について、$(1)$ を 2 倍して $(4)$ を足すと
$$5y_1+3y_2=2(y_1+y_2)+(3y_1+y_2)\le 2\cdot 3+5=11$$
である。等号は $(1)$, $(4)$ がともに等号のとき、すなわち $y_1+y_2=3,3y_1+y_2=5$ のときで、辺々引くと $2y_1=2$ より $y_1=1$, $y_2=2$。この点は
$(2)$: $2-2=0<2$、$(3)$: $1+6=7<8$、$(5)$: $2+4=6<7$、$y_1,y_2>0$
を満たすので実行可能である。よって $(\mathrm{D})$ の最適解は ${\mathbf{y}}^{\ast }=(1,2)$ ただ 1 つで、最適値は $11$ である。強双対定理より $(\mathrm{P})$ の最適値も $11$ である。

相補性条件 $\mathbf{x}$ が $(\mathrm{P})$ の最適解なら、${\mathbf{y}}^{\ast }$ との間で相補性条件が成り立つ。
- $(2),(3),(5)$ は ${\mathbf{y}}^{\ast }$ で等号が成り立たない（余裕がある）ので、対応する $x_2=x_3=x_5=0$。
- $y_1^{\ast }>0,y_2^{\ast }>0$ なので、$(\mathrm{P})$ の 2 本の制約はともに等号で成り立つ。

よって
$$x_1+3x_4=5,x_1+x_4=3$$
辺々引くと $2x_4=2$、$x_4=1$、$x_1=2$。これは $x_1,x_4\ge 0$ を満たす。

確認 $\mathbf{x}=(2,0,0,1,0)$ は制約 $2+3=5\ge 5$、$2+1=3\ge 3$ を満たし、目的関数値は $3\cdot 2+5\cdot 1=11$ で双対の最適値と一致するので、弱双対定理から最適解である。また上の議論から、どの最適解も $x_2=x_3=x_5=0,x_1=2,x_4=1$ を満たさなければならないので、最適解はこれただ 1 つである。

答え: $(x_1,x_2,x_3,x_4,x_5)=(2,0,0,1,0)$

双対問題を解く。$(\mathrm{D})$: maximize $5y_1+3y_2$ subject to
$y_1+y_2\le 3$ ($x_1$), $2y_1-y_2\le 2$ ($x_2$), $y_1+3y_2\le 8$ ($x_3$), $3y_1+y_2\le 5$ ($x_4$), $2y_1+2y_2\le 7$ ($x_5$), $y_1,y_2\ge 0$。

頂点を調べる。$x_1$ と $x_4$ の制約が等号の点は $y_1+y_2=3$, $3y_1+y_2=5$ より $(y_1,y_2)=(1,2)$。ほかの制約: $2-2=0\le 2$, $1+6=7\le 8$, $2+4=6\le 7$ をすべて満たすので実行可能で、目的関数値は $5+6=11$。
$x_1$ の境界線上では目的関数は $5y_1+3(3-y_1)=9+2y_1$ で $y_1$ とともに増えるが、$x_4$ の制約から $y_1\le 1$。他の頂点: $(5/3,4/3)$ は $x_4$ に違反、$(7/5,4/5)$ は値 $9.4$、$(1/2,5/2)$ は値 $10$、$(0,8/3)$ は値 $8$ で、いずれも $11$ 以下。よって双対の最適値は $11$、最適解は $(1,2)$。

相補性条件: $y_1,y_2>0$ より主問題の 2 本の制約は等号。双対で等号でない制約（$x_2$: $0<2$、$x_3$: $7<8$、$x_5$: $6<7$）に対応する主変数は $x_2=x_3=x_5=0$。残りは
$x_1+3x_4=5$, $x_1+x_4=3$ より $x_4=1$, $x_1=2$。

検算: 制約 1: $2+3=5\ge 5$、制約 2: $2+1=3\ge 3$ で実行可能。目的関数 $3\cdot 2+5\cdot 1=11$ で双対の最適値と一致（強双対性）。