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

标签：

• Waseda-University
• Simplex-Method
• Linear-Programming-Duality

Author

祭音Myyura

Description

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

$$\begin{array}{ll} \text{minimize}&z=-3x_1-2x_2-4x_3\\ \text{subject to} &x_1+x_2+2x_3\leq4,\\ &2x_1+2x_3\leq5,\\ &2x_1+x_2+3x_3\leq7,\\ &x_1,x_2,x_3\geq0. \end{array}$$

1. 単体法の計算過程と pivot の列・行を示して解け。
2. 双対問題を示せ。
3. 主問題と双対問題の最適目的関数値が一致することを示せ。

Kai

[小問 1]

$w=-z=3x_1+2x_2+4x_3$ の最大化問題へ変換し、スラック変数 $s_1,s_2,s_3$ を加える。表の最下段は $c_j-z_j$ である。

初期表

基底	$c_B$	右辺	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$
$s_1$	0	4	1	1	2	1	0	0
$s_2$	0	5	2	0	2	0	1	0
$s_3$	0	7	2	1	3	0	0	1
$c_j-z_j$			3	2	4	0	0	0

$x_3$ 列を選び、比 $4/2,5/2,7/3$ の最小値から $s_1$ 行を pivot 行とする。

第1 pivot 後

基底	$c_B$	右辺	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$
$x_3$	4	2	$1/2$	$1/2$	1	$1/2$	0	0
$s_2$	0	1	1	-1	0	-1	1	0
$s_3$	0	1	$1/2$	$-1/2$	0	$-3/2$	0	1
$c_j-z_j$			1	0	0	-2	0	0

$x_1$ 列を選び、比 $2/(1/2),1/1,1/(1/2)$ の最小値から $s_2$ 行を pivot 行とする。

第2 pivot 後

基底	$c_B$	右辺	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$
$x_3$	4	$3/2$	0	1	1	1	$-1/2$	0
$x_1$	3	1	1	-1	0	-1	1	0
$s_3$	0	$1/2$	0	0	0	-1	$-1/2$	1
$c_j-z_j$			0	1	0	-1	-1	0

$x_2$ 列を選ぶ。正の係数を持つのは $x_3$ 行だけなので、そこを pivot 行とする。

第3 pivot 後

基底	$c_B$	右辺	$x_1$	$x_2$	$x_3$	$s_1$	$s_2$	$s_3$
$x_2$	2	$3/2$	0	1	1	1	$-1/2$	0
$x_1$	3	$5/2$	1	0	1	0	$1/2$	0
$s_3$	0	$1/2$	0	0	0	-1	$-1/2$	1
$c_j-z_j$			0	0	-1	-2	$-1/2$	0

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

$$\boxed{ (x_1,x_2,x_3)=\left(\frac52,\frac32,0\right),\qquad w^*=\frac{21}{2},\qquad z^*=-\frac{21}{2} }.$$

[小問 2]

元の最小化問題 $(P)$ の双対変数を $y_1,y_2,y_3\leq0$ とすると、双対問題 $(D)$ は

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

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

$$\begin{array}{ll} \text{minimize} &4u_1+5u_2+7u_3\\ \text{subject to} &u_1+2u_2+2u_3\geq3,\\ &u_1+u_3\geq2,\\ &2u_1+2u_2+3u_3\geq4,\\ &u_1,u_2,u_3\geq0 \end{array}$$

となる。

[小問 3]

双対の実行可能解

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

を取ると、左辺は

$$A^{\mathsf T}u=(3,2,5)^{\mathsf T}\geq(3,2,4)^{\mathsf T}$$

であり、目的値は

$$4\cdot2+5\cdot\frac12+7\cdot0 =\frac{21}{2}=w^*.$$

すなわち元の双対変数では $y=(-2,-1/2,0)$ で

$$4y_1+5y_2+7y_3=-\frac{21}{2}=z^*.$$

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