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

方針：$x^{\ast }$ に対応する双対解 $y=(y_1,y_2)$ を相補性条件から求め、すべての変数の被約費用が $0$ 以下になる条件を $c$ の不等式として解く。

手順1：標準形と列ベクトル
スラック変数 $x_3,x_4\geqq 0$ を加えると
$$x_1+x_2+x_3=4,x_1+3x_2+x_4=6$$
となり、目的関数の係数は $(c_1,c_2,c_3,c_4)=(c,2,0,0)$、各変数の列は
$$A_1=\left(\begin{array}{c}1\\ 1\end{array}\right),A_2=\left(\begin{array}{c}1\\ 3\end{array}\right),A_3=\left(\begin{array}{c}1\\ 0\end{array}\right),A_4=\left(\begin{array}{c}0\\ 1\end{array}\right)$$
である。$x^{\ast }=(3,1)$ では $3+1=4$、$3+3\cdot 1=6$ なので、2 つの制約はどちらも等号で成り立ち、$x_3=x_4=0$ である。

手順2：双対解 $y$ を求める
$x_1^{\ast }=3>0$、$x_2^{\ast }=1>0$ なので、相補性条件より $x_1,x_2$ の被約費用は $0$ でなければならない：
$$c-(y_1+y_2)=0,2-(y_1+3y_2)=0.$$
第2式から第1式の $y_1+y_2=c$ を引くと $2y_2=2-c$、よって
$$y_2=\frac{2-c}{2},y_1=c-y_2=\frac{3c-2}{2}.$$

手順3：被約費用 $\leqq 0$ の条件
スラック変数の被約費用は
$$c_3-A_3^{\top }y=-y_1=-\frac{3c-2}{2},c_4-A_4^{\top }y=-y_2=-\frac{2-c}{2}.$$
これらがともに $0$ 以下である条件は
$$\frac{3c-2}{2}\geqq 0,\frac{2-c}{2}\geqq 0⟺\frac{2}{3}\leqq c\leqq 2.$$

手順4：最適性の確認
この範囲では $y\geqq 0$ かつ $A^{\top }y\geqq (c,2)$（等号）なので $y$ は双対問題の実行可能解であり、主の目的関数値 $3c+2$ と双対の目的関数値 $4y_1+6y_2=2(3c-2)+3(2-c)=3c+2$ が一致する。弱双対性より $x^{\ast }$ は最適解である。逆に範囲外では、相補性条件から決まる $y$ が唯一の候補であるのに $y\geqq 0$ を満たさないので、$x^{\ast }$ は最適解でない。

（図形的には、目的関数の法線 $(c,2)$ が 2 本の制約の法線 $(1,1)$ と $(1,3)$ の間にある条件、すなわち傾きの比 $\frac{1}{3}\leqq \frac{c}{2}\leqq 1$ と一致する。）

よって $(\alpha ,\beta )=\left(\frac{2}{3},2\right)$。

実行可能領域の頂点は (0,0), (4,0), (3,1), (0,2) である。ここで (3,1) は x1+x2=4 と x1+3x2=6 の交点（引くと 2x2=2 より x2=1, x1=3）。

(3,1) で有効な制約の法線ベクトルは (1,1) と (1,3)。目的関数の勾配 (c,2) がこの2つの非負結合で表せれば (3,1) は最適解である。
(c,2)=y1(1,1)+y2(1,3), y1,y2≧0 とおくと、c=y1+y2, 2=y1+3y2。
よって y1=2-3y2, c=2-2y2。
y1≧0 より y2≦2/3、y2≧0 より 0≦y2≦2/3。
ゆえに c は 2-4/3=2/3 から 2 の範囲、すなわち 2/3≦c≦2。

検算：各頂点の目的関数値は (0,0):0, (4,0):4c, (3,1):3c+2, (0,2):4。
(3,1)≧(4,0): 3c+2≧4c より c≦2。
(3,1)≧(0,2): 3c+2≧4 より c≧2/3。
(3,1)≧(0,0): c≧-2/3 で、2/3≦c なら成立。
よって 2/3≦c≦2 で、(α,β)=(2/3,2)。