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

手順 1：点 $(3,1)$ が実行可能で、どの制約が等号かを確認する。

$x_1+x_2=3+1=4$、$x_1+3x_2=3+3=6$ なので、2 つの制約はどちらも等号で成り立ち（余裕がない）、$x_1,x_2\ge 0$ も満たす。よって $(3,1)$ は実行可能解である。

手順 2：対応する双対解 $y=(y_1,y_2)$ を求める。

双対問題は
$$\text{minimize}4y_1+6y_2,y_1+y_2\ge c,y_1+3y_2\ge 2,y_1,y_2\ge 0$$
である。$x_1=3>0$, $x_2=1>0$ なので、相補性条件から双対の 2 つの制約はともに等号になる：
$$y_1+y_2=c,y_1+3y_2=2.$$
2 式目から 1 式目を引くと $2y_2=2-c$ より $y_2=\frac{2-c}{2}$。すると $y_1=c-\frac{2-c}{2}=\frac{3c-2}{2}$。

手順 3：すべての変数の被約費用 $c_j-A_j^{\top }y\le 0$ を条件として書く。

スラック変数 $s_1,s_2$ を加えた標準形で考える。
- $x_1$：$c-(y_1+y_2)=0\le 0$（手順 2 で等号にしたので成り立つ）
- $x_2$：$2-(y_1+3y_2)=0\le 0$（同様に成り立つ）
- $s_1$（係数 $0$、列 $(1,0{)}^{\top }$）：$0-y_1\le 0$ すなわち $y_1\ge 0$
- $s_2$（係数 $0$、列 $(0,1{)}^{\top }$）：$0-y_2\le 0$ すなわち $y_2\ge 0$

手順 4：不等式を解く。

$y_1=\frac{3c-2}{2}\ge 0$ より $c\ge \frac{2}{3}$。$y_2=\frac{2-c}{2}\ge 0$ より $c\le 2$。

このとき $y$ は双対実行可能で、主の目的関数値 $3c+2$ と双対の目的関数値 $4\cdot \frac{3c-2}{2}+6\cdot \frac{2-c}{2}=3c+2$ が一致するので、弱双対性により $(3,1)$ は最適解である。逆に範囲外では $y_1<0$ または $y_2<0$ となり、$(3,1)$ は最適でない（図で見ると、目的関数の勾配 $(c,2)$ が 2 本の制約の法線 $(1,1)$ と $(1,3)$ の間から外れる）。

よって $\frac{2}{3}\le c\le 2$ であり、$p=\frac{2}{3}$, $q=2$。

実行可能領域は、頂点 $(0,0),(4,0),(3,1),(0,2)$ をもつ四角形である。$(3,1)$ は 2 つの制約 $x_1+x_2=4$ と $x_1+3x_2=6$ の交点で、どちらも等号が成り立つ。

双対問題は、$\min 4y_1+6y_2$ subject to $y_1+y_2\ge c,y_1+3y_2\ge 2,y_1,y_2\ge 0$ である。

$(3,1)$ では $x_1>0,x_2>0$ なので、相補性より双対の 2 つの制約は等号になる。すなわち $y_1+y_2=c,y_1+3y_2=2$ である。また主問題の 2 つの制約は等号なので、$y_1,y_2$ への条件はない。

これを解くと $2y_2=2-c$ より $y_2=(2-c)/2$、$y_1=c-y_2=(3c-2)/2$ となる。

双対実行可能性（$y_1\ge 0,y_2\ge 0$）は次のとおり。
- $y_1\ge 0$ より $c\ge 2/3$
- $y_2\ge 0$ より $c\le 2$

したがって $2/3\le c\le 2$ である。

検算として、頂点での目標関数値を比べる。
- $(3,1)$: $3c+2$
- $(4,0)$: $4c$
- $(0,2)$: $4$
- $(0,0)$: $0$

$3c+2\ge 4c$ より $c\le 2$、$3c+2\ge 4$ より $c\ge 2/3$ となり、一致する。

よって $p=2/3,q=2$ である。