ネットワーク理論講義補助資料 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 iS を満たすものに対して xi S 1 iS 2000年12月 が妥当不等式である, 第11回 多面体論 6
© Copyright 2024 ExpyDoc