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

标签：

• Waseda-University
• Shortest-Path-Problem
• Linear-Programming-Duality

Author

祭音Myyura

Description

頂点集合 、枝集合

を持つ有向グラフを考える。枝上の数字は費用である。

1. 頂点1から頂点4への最短路問題を線形計画問題として定式化せよ。
2. その双対問題を示せ。
3. 最適解において相補性条件が成立することを示せ。

Kai

[小問 1]

枝 を通る流量を とし、頂点1から1単位を送り、頂点4で1単位を受け取る最小費用流として定式化する。

最後の保存式は他の3式から従うが、各頂点の意味を明示するため記している。

3本の候補経路の費用は

なので、最適解は

[小問 2]

各頂点のフロー保存式に対応する自由変数を とする。双対問題は

ポテンシャルには定数を加えても制約と目的値が変わらないため、 と固定してよい。

[小問 3]

双対解

は実行可能で、目的値は である。正のフローを持つ3枝では

と双対制約が等号になる。一方、フローが0の枝では

したがって全枝について

が成立する。これは相補性条件であり、主・双対目的値もともに6なので両解は最適である。