PowerPoint プレゼンテーション

ネットワーク理論講義補助資料
Text.
組合せ最適化とアルゴリズム
4.2 節 多面体的アプローチ
pp. 111-115
• Part 4では組合せ最適化の種々の技法を解説
• ここでは,分枝限定法の線形計画緩和を強化す
るためのアプローチの基礎となる多面体論の基
礎について,最大安定集合問題を例として解説.
• 最大安定集合問題については,グラフの定義の
説明用として1.1節(pp.2-4)で紹介ずみ.
最大安定集合問題の多面体表現
1
3
x3
(0,0,1)
2
x
(0,1,0) 2
問題
x1
(1,0,0)
多面体表現
2000年12月
第11回 多面体論
2
多面体と小数解
(0.5,0.5,0.5)
多面体
2000年12月
小数解
第11回 多面体論
3
切除平面法の概念(1)
線形計画の最適解
線形計画の実行可能領域
切除平面
整数計画多面体
側面
2000年12月
第11回 多面体論
4
切除平面法の概念(2)
黒丸を切らないように
白い紙を切り取る
線形計画の最適解
2000年12月
第11回 多面体論
5
妥当不等式
最適解を除かない不等式=妥当不等式(valid inequality)
クマさん問題の場合,
クマさんの部分集合Sで
 si  b
iS
を満たすものに対して
 xi  S 1
iS
2000年12月
が妥当不等式である,
第11回 多面体論
6