第二章整數規劃
§1 概論
1.1 定義
規劃中的變數（部分或全部）限制為整數時，稱為整數規劃。若**性規劃模型中，變數限制為整數，則稱為整數線性規劃。目前所流行的求解整數規劃的方法，往往只適用於整數線性規劃。
目前還沒有一種方法能有效地求解一切整數規劃。
1.2 整數規劃的分類
如不加特殊說明，一般指整數線性規劃。對於整數線性規劃模型大致可分為兩類：
1o 變數全限制為整數時，稱純（完全）整數規劃。
2o 變數部分限制為整數的，稱混合整數規劃。
3o 變數只能取0或1時，稱之為0-1整數規劃。
整數規劃特點
（） 原線性規劃有最優解，當自變數限制為整數後，其整數規劃解出現下述情況：
原線性規劃最優解全是整數，則整數規劃最優解與線性規劃最優解一致。
整數規劃無可行解。
例1 原線性規劃為
其最優實數解為：。
有可行解（當然就存在最優解），但最優解值一定不會優於原線性規劃的最優值。
例2 原線性規劃為
其最優實數解為：。
若限制整數得：。
（） 整數規劃最優解不能按照實數最優解簡單取整而獲得。
1.3 求解方法分類：
（）分枝定界法—可求純或混合整數線性規劃。
（）割平面法—可求純或混合整數線性規劃。
（）隱列舉法—求解「0-1」整數規劃：
過濾隱列舉法；
分枝隱列舉法。
（）匈牙利法—解決指派問題（「0-1」規劃特殊情形）。
（）蒙特卡洛法—求解各種型別規劃。
下面將簡要介紹常用的幾種求解整數規劃的方法。
§2 分枝定界法
對有約束條件的最優化問題（其可行解為有限數）的可行解空間恰當地進行系統搜尋，這就是分枝與定界內容。通常，把全部可行解空間反覆地分割為越來越小的子集，稱為分枝；並且對每個子集內的解集計算乙個目標下界（對於最小值問題），這稱為定界。在每次分枝後，凡是界限不優於已知可行解集目標值的那些子集不再進一步分枝，這樣，許多子集可不予考慮，這稱剪枝。
這就是分枝定界法的主要思路。
分枝定界法可用於解純整數或混合的整數規劃問題。在二十世紀六十年代初由land doig和dakin等人提出。由於這方法靈活且便於用計算機求解，所以現在它已是解整數規劃的重要方法。
目前已成功地應用於求解生產進度問題、旅行推銷員問題、工廠選址問題、揹包問題及分配問題等。
設有最大化的整數規劃問題，與它相應的線性規劃為問題，從解問題開始，若其最優解不符合的整數條件，那麼的最優目標函式必是的最優目標函式的上界，記作；而的任意可行解的目標函式值將是的乙個下界。分枝定界法就是將的可行域分成子區域再求其最大值的方法。逐步減小和增大，最終求到。
現用下例來說明：
例3 求解下述整數規劃
解 （）先不考慮整數限制，即解相應的線性規劃，得最優解為：
可見它不符合整數條件。這時是問題的最優目標函式值的上界，記作。而顯然是問題的乙個整數可行解，這時，是的乙個下界，記作，即。
（）因為當前均為非整數，故不滿足整數要求，任選乙個進行分枝。設選進行分枝，把可行集分成2個子集：
， 因為4與5之間無整數，故這兩個子集內的整數解必與原可行集合整數解一致。這一步稱為分枝。這兩個子集的規劃及求解如下：
問題：最優解為：。
問題：最優解為：。
再定界：。
（）對問題再進行分枝得問題和，它們的最優解為
再定界：，並將剪枝。
（）對問題再進行分枝得問題和，它們的最優解為
無可行解。
將剪枝。
於是可以斷定原問題的最優解為：
從以上解題過程可得用分枝定界法求解整數規劃（最大化）問題的步驟為：
開始，將要求解的整數規劃問題稱為問題，將與它相應的線性規劃問題稱為問題。
（）解問題可能得到以下情況之一：
（a）沒有可行解，這時也沒有可行解，則停止．
（b）有最優解，並符合問題的整數條件，的最優解即為的最優解，則停止。
（c）有最優解，但不符合問題的整數條件，記它的目標函式值為。
（）用觀察法找問題的乙個整數可行解，一般可取，試探，求得其目標函式值，並記作。以表示問題的最優目標函式值；這時有
進行迭代。
第一步：分枝，在的最優解中任選乙個不符合整數條件的變數，其值為，以表示小於的最大整數。構造兩個約束條件
和 將這兩個約束條件，分別加入問題，求兩個後繼規劃問題和。不考慮整數條件求解這兩個後繼問題。
定界，以每個後繼問題為一分枝標明求解的結果，與其它問題的解的結果中，找出最優目標函式值最大者作為新的上界。從已符合整數條件的各分支中，找出目標函式值為最大者作為新的下界，若無作用。
第二步：比較與剪枝，各分枝的最優目標函式中若有小於者，則剪掉這枝，即以後不再考慮了。若大於，且不符合整數條件，則重複第一步驟。一直到最後得到為止。得最優整數解。
§3型整數規劃
型整數規劃是整數規劃中的特殊情形，它的變數僅取值0或1。這時稱為變數，或稱二進位制變數。僅取值0或1這個條件可由下述約束條件：
整數所代替，是和一般整數規劃的約束條件形式一致的。在實際問題中，如果引入變數，就可以把有各種情況需要分別討論的線性規劃問題統一在乙個問題中討論了。我們先介紹引入變數的實際問題，再研究解法。
3.1 引入變數的實際問題
3.1.1 投資場所的選定——相互排斥的計畫
例4 某公司擬在市東、西、南三區建立門市部。擬議中有7個位置（點）可供選擇。規定
在東區：由三個點中至多選兩個；
在西區：由兩個點中至少選乙個；
在南區：由兩個點中至少選乙個。
如選用點，裝置投資估計為元，每年可獲利潤估計為元，但投資總額不能超過元。問應選擇哪幾個點可使年利潤為最大？
解題時先引入變數令.
於是問題可列寫成：
3.1.2 相互排斥的約束條件
① 有兩個相互排斥的約束條件
或。為了統一在乙個問題中，引入變數，則上述約束條件可改寫為：
其中是充分大的數。
② 約束條件
或可改寫為
③ 如果有個互相排斥的約束條件：
為了保證這個約束條件只有乙個起作用，我們引入個變數和乙個充分大的常數，而下面這一組個約束條件
1）2）
就合於上述的要求。這是因為，由於（2），個中只有乙個能取0值，設，代入（1），就只有的約束條件起作用，而別的式子都是多餘的。
3.1.3 關於固定費用的問題（fixed cost problem）
在討論線性規劃時，有些問題是要求使成本為最小。那時總設固定成本為常數，並**性規劃的模型中不必明顯列出。但有些固定費用（固定成本）的問題不能用一般線性規劃來描述，但可改變為混合整數規劃來解決，見下例。
例5 某工廠為了生產某種產品，有幾種不同的生產方式可供選擇，如選定的生產方式投資高（選購自動化程度高的裝置），由於產量大，因而分配到每件產品的變動成本就降低；反之，如選定的生產方式投資低，將來分配到每件產品的變動成本可能增加。所以必須全面考慮。今設有三種方式可供選擇，令
表示採用第種方式時的產量；
表示採用第種方式時每件產品的變動成本；
表示採用第種方式時的固定成本。
為了說明成本的特點，暫不考慮其它約束條件。採用各種生產方式的總成本分別為
.在構成目標函式時，為了統一在乙個問題中討論，現引入變數，令
3）於是目標函式
（3）式這個規定可表為下述3個線性約束條件：
4）其中是個充分大的常數。（4）式說明，當時必須為1；當時只有為0時才有意義，所以（4）式完全可以代替（3）式。
3.2型整數規劃解法之一（過濾隱列舉法）
解型整數規劃最容易想到的方法，和一般整數規劃的情形一樣，就是窮舉法，即檢查變數取值為0或1的每一種組合，比較目標函式值以求得最優解，這就需要檢查變數取值的個組合。對於變數個數較大（例如），這幾乎是不可能的。因此常設計一些方法，只檢查變數取值的組合的一部分，就能求到問題的最優解。
這樣的方法稱為隱列舉法（implicit enumeration），分枝定界法也是一種隱列舉法。當然，對有些問題隱列舉法並不適用，所以有時窮舉法還是必要的。
下面舉例說明一種解型整數規劃的隱列舉法。
例6求解思路及改進措施：
（） 先試探性求乙個可行解，易看出滿足約束條件，故為乙個可行解，且相應的目標函式值為。
（） 因為是求極大值問題，故求最優解時，凡是目標值的解不必檢驗是否滿足約束條件即可刪除，因它肯定不是最優解，於是應增加乙個約束條件（目標值下界）：
，稱該條件為過濾條件(filtering contraint)。從而原問題等價於：
若用全部列舉法，3個變數共有8種可能的組合，我們將這8種組合依次檢驗它是否滿足條件(a)—(e)，對某個組合，若它不滿足(a)，即不滿足過濾條件，則(b)—(e)即可行性條件不必再檢驗；若它滿足(a)—(e)且相應的目標值嚴格大於3，則進行（）。
（） 改進過濾條件。
（） 由於對每個組合首先計算目標值以驗證過濾條件，故應優先計算目標值大的組合，這樣可提前抬高過濾門檻，以減少計算量。
按上述思路與方法，例6的求解過程可由下表來表示：
從而得最優解，最優值。
§4 蒙特卡洛法（隨機取樣法）
前面介紹的常用的整數規劃求解方法，主要是針對線性整數規劃而言，而對於非線性整數規劃目前尚未有一種成熟而有效的求解方法，因為非線性規劃本身的通用有效解法尚未找到，更何況是非線性整數規劃。
求解整數規劃演算法
求解整數規劃演算法 分枝定界法原理 步驟 將要求解的整數規劃問題稱為i l，與它相應的線性規劃問題稱為問題l。解問題l，可能得到以下情況之一 a l沒有可行解，這時i l也沒有可行解 b l有最優解，且解變數都是整數，因而它也是i l的最優解，則停止 c l有最優解，但不符合i l中的整數條件，記它...
實驗三 求解線性規劃和整數規劃模型
數學建模 實驗指導 姓名 吳家猛 班號 ap08055 學號 ap0805530 五邑大學資訊工程學院 二 一o年十一月 實驗3 指導書 實驗專案名稱 求解線性規劃和整數規劃模型 所屬課程名稱 數學建模 實驗計畫學時 2學時 一 實驗目的 掌握使用數學軟體lingo或matlab等軟體求解線性規劃和...
非線性規劃理論和演算法
非線性最優化理論與演算法 第一章引論 本章首先給出了一些常見的最優化問題和非線性最優化問題解的定義，並且根據不同的條件對其進行了劃分。接著給出了求解非線性優化問題的方法，如 法等，同時又指出乙個好的數值方法應對一些指標有好的特性，如收斂速度與二次終止性 穩定性等。隨後給出了在非線性最優化問題的理論分...