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

$(\mathrm{P})$ と $(\mathrm{D})$ の最適解の組は、次の相補性条件を満たす。
- 主の第 $i$ 制約に余裕がある（不等号が等号でない）なら $y_i=0$
- $x_j^{\ast }>0$ なら双対の第 $j$ 制約は等号で成り立つ

手順1：主の制約の余裕を調べる。 $(x_1^{\ast },x_2^{\ast })=(3,2)$ を代入すると
$$x_1+x_2=5(=5),2x_1+x_2=8(=8),x_1+3x_2=9(<12).$$
第 3 制約には余裕があるので $y_3=0$ である。第 1・第 2 制約は等号なので、ここからは $y_1,y_2$ について何もわからない。

手順2：$x_j^{\ast }>0$ に対応する双対制約を等号にする。 $x_1^{\ast }=3>0$ より双対の第 1 制約は等号、$x_2^{\ast }=2>0$ より双対の第 2 制約も等号である。$y_3=0$ を代入して
$$y_1+2y_2=5,y_1+y_2=4.$$

手順3：連立方程式を解く。 上の式から下の式を引いて $y_2=1$、よって $y_1=3$。この連立方程式の解はただ 1 つなので、$(\mathrm{D})$ の最適解はこれ以外にない。

確認： $y=(3,1,0)$ は $y\geqq 0$ を満たし、双対の制約 $3+2+0=5\geqq 5$, $3+1+0=4\geqq 4$ も満たすので実行可能である。弱双対性より、$(\mathrm{D})$ の任意の実行可能解の目的関数値は $(\mathrm{P})$ の任意の実行可能解の目的関数値以上である。ここで双対の目的関数値は $5\cdot 3+8\cdot 1+12\cdot 0=23$、主の目的関数値は $5\cdot 3+4\cdot 2=23$ で一致するので、$(3,1,0)$ より小さい値をとる $(\mathrm{D})$ の実行可能解は存在せず、$(3,1,0)$ は $(\mathrm{D})$ の最適解である。

したがって $(y_1,y_2,y_3)=(3,1,0)$。

最適解 $(x_1^{\ast },x_2^{\ast })=(3,2)$ を (P) の制約に代入する。
- $x_1+x_2=5$ より第1制約は等号（有効）。
- $2x_1+x_2=8$ より第2制約も等号（有効）。
- $x_1+3x_2=9<12$ より第3制約は不等号が厳密に成り立つ（有効でない）。

相補性条件より、第3制約のスラックが正なので $y_3=0$。
また $x_1^{\ast }=3>0,x_2^{\ast }=2>0$ なので、(D) の第1・第2制約はともに等号で成り立つ。
$y_1+2y_2=5$ かつ $y_1+y_2=4$。
これを解くと $y_2=1$、$y_1=3$。

検算：$y_1,y_2,y_3=(3,1,0)\geqq 0$。
第1制約：$3+2+0=5\geqq 5$ で成立。
第2制約：$3+1+0=4\geqq 4$ で成立。
双対目的関数値：$5\cdot 3+8\cdot 1+12\cdot 0=23$。
主問題の目的関数値：$5\cdot 3+4\cdot 2=23$。
値が一致するので、強双対性より $(3,1,0)$ は (D) の最適解である。