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

双対問題. $({\mathrm{P}}_c)$ の双対問題は
$$({\mathrm{D}}_c)\begin{array}{rl}\text{minimize}& 10y_1+15y_2\\ \text{subject to}& y_1+3y_2\ge 4,\\ & 2y_1+y_2\ge 5,\\ & y_1+2y_2\ge c,\\ & y_1,y_2\ge 0\end{array}$$
である。

最適性の条件. 線形計画法の双対定理（相補性定理）より、主問題の実行可能解 $x^{\ast }$ が最適であるための必要十分条件は、双対問題の実行可能解 $y$ で相補性条件
$$x_j^{\ast }(\text{双対の第 }j\text{ 制約の余裕})=0,y_i(\text{主の第 }i\text{ 制約の余裕})=0$$
を満たすものが存在することである。

まず $x^{\ast }=(4,3,0)$ は実行可能である: $4+6+0=10\le 10$, $12+3+0=15\le 15$, かつ非負。主の 2 つの制約はどちらも等号で成り立つので、$y_1,y_2$ には相補性からの制約はない。

$x_1^{\ast }=4>0$, $x_2^{\ast }=3>0$ なので、双対の第 1・第 2 制約は等号でなければならない:
$$y_1+3y_2=4,2y_1+y_2=5.$$
第 1 式から $y_1=4-3y_2$。第 2 式に代入して $8-6y_2+y_2=5$、よって $y_2=\frac{3}{5}$, $y_1=4-\frac{9}{5}=\frac{11}{5}$。$y$ はこの $1$ 点に限られ、$y_1,y_2\ge 0$ を満たす。

$x_3^{\ast }=0$ なので第 3 制約には相補性からの条件はなく、双対実行可能性として
$$y_1+2y_2=\frac{11}{5}+\frac{6}{5}=\frac{17}{5}\ge c$$
が必要十分である。

したがって $x^{\ast }$ が最適 $⟺c\le \frac{17}{5}$ であり、求める最大値は $\frac{17}{5}$ である。

（確認: このとき主の目的値 $4\cdot 4+5\cdot 3=31$ と双対の目的値 $10\cdot \frac{11}{5}+15\cdot \frac{3}{5}=22+9=31$ が一致する。$c>\frac{17}{5}$ では $x_3$ の被約費用 $c-(y_1+2y_2)$ が正になり、$x_3$ を増やすことで目的値を改善できる。）

$x^{\ast }=(4,3,0)$ は実行可能: $4+6+0=10\le 10$, $12+3+0=15\le 15$ で、2 つの制約とも等号成立。

双対問題は $\min 10y_1+15y_2$ s.t. $y_1+3y_2\ge 4,2y_1+y_2\ge 5,y_1+2y_2\ge c,y_1,y_2\ge 0$。$x^{\ast }$ が最適解 $⟺$ ある双対実行可能解 $y$ が相補性条件を満たす。

$x_1^{\ast }=4>0$, $x_2^{\ast }=3>0$ なので双対の第 1, 2 制約は等号: $y_1+3y_2=4$, $2y_1+y_2=5$。これを解くと $y_2=\frac{3}{5}$, $y_1=\frac{11}{5}$ で、ともに $\ge 0$。$y$ は一意に定まり、2 つの主制約は等号なので $y_1,y_2\ge 0$ の相補性も満たされる。

残る双対実行可能性は第 3 制約 $y_1+2y_2\ge c$、すなわち $c\le \frac{11}{5}+\frac{6}{5}=\frac{17}{5}$（$x_3^{\ast }=0$ なので相補性は不等号のままで可）。

よって $x^{\ast }$ が最適解となる条件は $c\le \frac{17}{5}$ で、最大値は $\frac{17}{5}$。

検算: $c=17/5$ のとき主目的値 $=16+15=31$、双対目的値 $=10\cdot \frac{11}{5}+15\cdot \frac{3}{5}=22+9=31$ で一致。また $c>17/5$ なら、たとえば $x_3$ を増やす方向の基底変更（$x_1,x_2$ を基底に $x_3$ が入る）で簡約費用が正になり $x^{\ast }$ は最適でなくなる。