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

标签：

• Waseda-University
• Simplex-Method
• Linear-Programming-Duality
• Sensitivity-Analysis
• Maximum-Flow
• Branch-And-Bound
• Knapsack-Problem

Author

祭音Myyura

Description

1. 次の線形計画問題について、単体法、双対問題、最適目的値の一致、第1制約右辺の感度を求めよ。

2. 容量 のネットワークで、頂点0から2への最大流問題とその双対を示し、双対変数の意味を説明せよ。

3. 次の0--1ナップサック問題について、線形緩和解を求め、分枝限定法で解け。

Kai

[小問 1-1]

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

初期表

基底	右辺
	60	1	1	1	0
	80	2	1	0	1
		5	3	0	0

列を選ぶ。比 の小さい 行を pivot 行とする。

第1 pivot 後

基底	右辺
	20	0		1
	40	1		0
		0		0

次に 列を選ぶ。比 と より 行が pivot 行である。

第2 pivot 後

基底	右辺
	40	0	1	2	-1
	20	1	0	-1	1
		0	0	-1	-2

したがって

[小問 1-2]

双対問題は

[小問 1-3]

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

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

[小問 1-4]

第1制約の右辺を とする。影価格は なので

実際、同じ基底では

となるため、この関係は で有効である。正の微小増加に対する目的値の増加率は1である。

[小問 2-1]

枝流量を 、総流量を とすると

最適流は例えば

である。

[小問 2-2]

最大流問題の双対は最小カット問題として表せる。頂点ポテンシャルを 、枝がカットを横切る度合いを とすれば

は頂点 が始点側に属することを表し、 は始点側から終点側へ横切る枝の指示量に対応する。 とするとカット が得られ、、容量は2である。最大流値と最小カット容量がともに2なので最適である。

[小問 3-1]

線形緩和では とする。価値重量比は

なので、順に詰めると

これは整数問題の上界である。

[小問 3-2]

緩和解で分数となった について分枝する。

• ：緩和問題は を与える。これは整数実行可能で、目的値は であるため暫定解とする。
• ：残り容量は1であり、緩和上界は のとき である。暫定値11を超えないので枝刈りする。

したがって最適解は

子問題は上界の大きいものから選ぶ best-bound 法を用いており、分枝変数には現在の緩和解で分数となる変数を選んでいる。