早稲田大学創造理工学研究科経営システム工学専攻 2017年7月実施オペレーションズリサーチ問題7

标签：

Author

祭音Myyura

次の線形計画問題 $(P)$ について答えよ。

\begin{array}{ll} \text{minimize}&z=-3x_1-2x_2\\ \text{subject to} &x_1+x_2+x_3=9,\\ &3x_1+x_2+x_4=18,\\ &x_1+x_5=7,\\ &x_1,x_2,x_3,x_4,x_5\geq0. \end{array}

$w=-z=3x_1+2x_2$ の最大化問題とみなす。 $x_3,x_4,x_5$ はスラック変数であり、表の最下段は $c_j-z_j$ である。

基底	$c_B$	右辺	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
$x_3$	0	9	1	1	1	0	0
$x_4$	0	18	3	1	0	1	0
$x_5$	0	7	1	0	0	0	1
$c_j-z_j$			3	2	0	0	0

$x_1$ 列を選び、比 $9/1,18/3,7/1$ の最小値から $x_4$ 行を pivot 行とする。

基底	$c_B$	右辺	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
$x_3$	0	3	0	$2/3$	1	$-1/3$	0
$x_1$	3	6	1	$1/3$	0	$1/3$	0
$x_5$	0	1	0	$-1/3$	0	$-1/3$	1
$c_j-z_j$			0	1	0	-1	0

次に $x_2$ 列を選ぶ。正の係数に対する比は $3/(2/3)=9/2$ と $6/(1/3)=18$ なので、 $x_3$ 行を pivot 行とする。

基底	$c_B$	右辺	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
$x_2$	2	$9/2$	0	1	$3/2$	$-1/2$	0
$x_1$	3	$9/2$	1	0	$-1/2$	$1/2$	0
$x_5$	0	$5/2$	0	0	$1/2$	$-1/2$	1
$c_j-z_j$			0	0	$-3/2$	$-1/2$	0

すべての $c_j-z_j\leq0$ なので最適である。したがって

\boxed{ (x_1,x_2,x_3,x_4,x_5) =\left(\frac92,\frac92,0,0,\frac52\right) }

であり、

\boxed{w^*=\frac{45}{2}},\qquad \boxed{z^*=-\frac{45}{2}}.

等式制約に対する双対変数を $y_1,y_2,y_3$ とすると、本来これらは自由変数である。各スラック変数 $x_3,x_4,x_5\geq0$ に対応する双対制約から、さらに $y_1,y_2,y_3\leq0$ が課される。双対問題は

\begin{array}{ll} \text{maximize} &9y_1+18y_2+7y_3\\ \text{subject to} &y_1+3y_2+y_3\leq-3,\\ &y_1+y_2\leq-2,\\ &y_1,y_2,y_3\leq0. \end{array}

同値に $u_i=-y_i\geq0$ とおけば、 $w$ の最大化問題に対する双対

\begin{array}{ll} \text{minimize} &9u_1+18u_2+7u_3\\ \text{subject to} &u_1+3u_2+u_3\geq3,\\ &u_1+u_2\geq2,\\ &u_1,u_2,u_3\geq0 \end{array}

を得る。

双対の実行可能解

(u_1,u_2,u_3)=\left(\frac32,\frac12,0\right)

では、2本の制約がともに等号で成立し、目的値は

9\cdot\frac32+18\cdot\frac12+7\cdot0 =\frac{45}{2}=w^*.

元の双対変数では $y=(-3/2,-1/2,0)$ であり、

9y_1+18y_2+7y_3=-\frac{45}{2}=z^*.

主・双対の実行可能解の目的値が一致したため、弱双対性から両者は最適である。