整數規劃的難度遠大於一般線性規劃(PPT 16頁)

整數規劃
整數規劃的難度遠大於一般線性規劃
4.1 整數規劃簡介
要求所有 xj 的解為整數，稱為純整數規劃
要求部分 xj 的解為整數，稱為混合整數規劃
對應沒有整數解要求的線性規劃稱之為鬆弛問題
整數規劃的解是可數個的，最優解不一定發生在極點
整數規劃的最優解不會優於其鬆弛問題的最優解
4.2 整數規劃的分枝定解法
4.2.1 思路與解題步驟
隻解鬆弛問題
1、在全部可行性域上解鬆弛問題
若鬆弛問題最優解為整數解，則其也是整數規劃的最優解
2、分枝過程
若鬆弛問題最優解中某個 xk=bk 不是整數，令 ? bk ? 為 bk 的整數部分
構造兩個新的約束條件 xk? ? bk ? 和 xk? ? bk ?+1，分別加於原鬆弛問題，形成兩個新的整數規劃
3、求解分枝的鬆弛問題 — 定界過程
設兩個分枝的鬆弛問題分別為問題 1 和問題 2 ，它們的最優解有如下情況

..............................