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

标签：

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

Author

祭音Myyura

Description

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

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

Kai

[小問 1]

の最大化問題とみなす。 はスラック変数であり、表の最下段は である。

初期表

基底		右辺
	0	9	1	1	1	0	0
	0	18	3	1	0	1	0
	0	7	1	0	0	0	1
			3	2	0	0	0

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

第1 pivot 後

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

次に 列を選ぶ。正の係数に対する比は と なので、 行を pivot 行とする。

第2 pivot 後

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

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

であり、

[小問 2]

等式制約に対する双対変数を とすると、本来これらは自由変数である。各スラック変数 に対応する双対制約から、さらに が課される。双対問題は

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

を得る。

[小問 3]

双対の実行可能解

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

元の双対変数では であり、

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