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

手順1：双対問題を作る。

$(\mathrm{P})$ は $\max c^{\top }x,Ax\leqq b,x\geqq 0$ の形であり、
$$A=\left(\begin{array}{cc}1& 1\\ 1& 3\end{array}\right),b=\left(\begin{array}{c}4\\ 6\end{array}\right),c=\left(\begin{array}{c}2\\ 3\end{array}\right)$$
である。双対問題は $\min b^{\top }y,A^{\top }y\geqq c,y\geqq 0$ である。$A^{\top }=\left(\begin{array}{cc}1& 1\\ 1& 3\end{array}\right)$ なので
$$(\mathrm{D})\begin{array}{rl}\text{minimize}& 4y_1+6y_2\\ \text{subject to}& y_1+y_2\geqq 2,\\ & y_1+3y_2\geqq 3,\\ & y_1\geqq 0,y_2\geqq 0\end{array}$$
となる。

手順2：主問題 $(\mathrm{P})$ を解く。

実行可能領域は 4 点 $(0,0),(4,0),(3,1),(0,2)$ を頂点とする四角形である（$(3,1)$ は $x_1+x_2=4$ と $x_1+3x_2=6$ の交点：辺々引いて $2x_2=2$、$x_2=1$、$x_1=3$）。各頂点での $2x_1+3x_2$ の値は
$$0,8,2\cdot 3+3\cdot 1=9,6$$
なので、$(\mathrm{P})$ の最大値は $9$（$x=(3,1)$ のとき）である。

手順3：双対定理で $(\mathrm{D})$ の最適値を求め、確かめる。

強双対定理より、$(\mathrm{P})$ に最適解があれば $(\mathrm{D})$ にも最適解があり、両者の最適値は一致する。よって $(\mathrm{D})$ の最小値は $9$ である。

実際に確かめる。$(\mathrm{D})$ の 2 つの制約を等号で解くと $y_1+y_2=2,y_1+3y_2=3$ より $y_2=\frac{1}{2},y_1=\frac{3}{2}$。これは $y\geqq 0$ を満たし実行可能で、
$$4\cdot \frac{3}{2}+6\cdot \frac{1}{2}=6+3=9$$
である。弱双対性より、$(\mathrm{P})$ の任意の実行可能解 $x$ と $(\mathrm{D})$ の任意の実行可能解 $y$ について $2x_1+3x_2\leqq 4y_1+6y_2$ が成り立つ。$x=(3,1)$ を使うと $(\mathrm{D})$ の目的関数値はつねに $9$ 以上であり、$y=\left(\frac{3}{2},\frac{1}{2}\right)$ で $9$ が実現される。したがって $(\mathrm{D})$ の最適値は $9$ である。

双対問題 (D) は次のとおり。
$$\text{minimize }4y_1+6y_2\text{subject to }{y}_1+y_2\geqq 2,y_1+3y_2\geqq 3,y_1\geqq 0,y_2\geqq 0$$

(P) を解く。実行可能領域の頂点は $(0,0)$、$(4,0)$、$(0,2)$、$(3,1)$ である。$(3,1)$ は $x_1+x_2=4$ と $x_1+3x_2=6$ の交点。
目的関数 $2x_1+3x_2$ の値はそれぞれ $0,8,6,9$ なので、(P) の最適値は $9$（$(x_1,x_2)=(3,1)$）。

(D) を直接解く。2 つの不等式制約を等号にすると $y_1+y_2=2$、$y_1+3y_2=3$ より $y_2=\frac{1}{2}$、$y_1=\frac{3}{2}$。このとき目的関数は $4\cdot \frac{3}{2}+6\cdot \frac{1}{2}=6+3=9$。

検算として、(D) の頂点 $(0,2)$ は $y_1+3y_2=6\geqq 3$ を満たし、目的関数は $12$。$(3,0)$ は $y_1+y_2=3\geqq 2$ を満たし、目的関数は $12$。どちらも $9$ より大きい。したがって最小値は $9$ で、強双対性により (P) の最適値と一致する。

答え: $9$