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

标签：

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

Author

祭音Myyura

Description

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

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

Kai

[小問 1]

の最大化問題へ変換し、スラック変数 を加える。表の最下段は である。

初期表

基底		右辺
	0	4	1	1	2	1	0	0
	0	5	2	0	2	0	1	0
	0	7	2	1	3	0	0	1
			3	2	4	0	0	0

列を選び、比 の最小値から 行を pivot 行とする。

第1 pivot 後

基底		右辺
	4	2			1		0	0
	0	1	1	-1	0	-1	1	0
	0	1			0		0	1
			1	0	0	-2	0	0

列を選び、比 の最小値から 行を pivot 行とする。

第2 pivot 後

基底		右辺
	4		0	1	1	1		0
	3	1	1	-1	0	-1	1	0
	0		0	0	0	-1		1
			0	1	0	-1	-1	0

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

第3 pivot 後

基底		右辺
	2		0	1	1	1		0
	3		1	0	1	0		0
	0		0	0	0	-1		1
			0	0	-1	-2		0

すべての なので最適である。したがって

[小問 2]

元の最小化問題 の双対変数を とすると、双対問題 は

同値に とおけば、 の最大化問題に対する通常の双対

となる。

[小問 3]

双対の実行可能解

を取ると、左辺は

であり、目的値は

すなわち元の双対変数では で

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