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

标签：

• Waseda-University
• Simplex-Method
• Linear-Programming-Duality
• Sensitivity-Analysis
• Traveling-Salesman-Problem

Author

祭音Myyura

Description

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

   1. pivot の列・行を示して単体法で解け。
   2. 双対問題を示せ。
   3. 主・双対問題の最適目的関数値が一致することを示せ。
   4. 第1制約の右辺を正の微小量だけ増加させたときの最適目的関数値の変化を求めよ。
   5. 最適基底行列の逆行列を積形式で示せ。

2. 有向グラフ上の巡回セールスマン問題を、部分巡回路除去制約を含めて定式化せよ。

Kai

[小問 1-1]

スラック変数 を加える。表の最下段は である。

初期表

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

列を pivot 列とする。比は なので 行が pivot 行である。

第1 pivot 後

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

次に 列を pivot 列とする。比は なので 行が pivot 行である。

第2 pivot 後

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

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

[小問 1-2]

双対問題 は

[小問 1-3]

は双対実行可能であり、目的値は

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

[小問 1-4]

第1制約の右辺を とする。最適双対変数 は第1資源の影価格なので、同じ基底が実行可能な範囲では

実際、最適基底を の順に取ると

したがって ではこの式が成立し、正の微小増加に対する目的値の増加率は1である。

[小問 1-5]

最適基底行列を列 の順に

とする。2回の pivot に対応する行基本変形行列は

よって積形式の逆行列は

[小問 2]

枝 が巡回路に含まれるとき 、それ以外を0とする。定式化は

最初の2組の制約だけでは、全頂点が複数の互いに素な閉路へ分かれる可能性がある。第3組は任意の真部分集合 の内部だけで閉路を完成させることを禁じる部分巡回路除去制約であり、全頂点を1回ずつ通る単一のハミルトン閉路を保証する。