第5章整數規劃
有一類線性規劃問題的變數只能取整數，比如人或機器裝置不可分割，因此必需取整數。這時線性規劃問題稱為整數規劃。如果有的變數要求必需是整數，有的變數不要求必需是整數，則線性規劃問題稱為混合整數規劃問題。
5.2 分枝定界法
求整數規劃較好的方法是分支定界法。下面介紹常用的分枝定界法。
1.分枝定界法的基本原理
分枝定界法是目前解整數線性規劃問題的比較有效的方法，它既適用於純整數規劃問題，也適用於混合整數規劃問題。
先不考慮對變數的整數約束，這時問題稱為整數規劃問題的鬆弛模型，記為lp,原整數規劃問題記為ip。說明分枝定界法以前，先看以下事實：
（1） 如果lp有乙個整數最優解，則它就是ip的最優解。
（2） 如果lp沒有可行解，則ip也沒有可行解。
（3） 對於求最大，lp的最大值，一定是ip的最大值的上界；對於求最小，lp的最小值，一定是ip的最小值的下界。
（4） 如果在求解過程中得到了乙個整數解，和相應的目標函式的值，則對於求最大，它是目標函式最優值的乙個下界；對於求最小，它是目標函式最優值的乙個上界。
分枝定界法是從解鬆弛的線性規劃問題lp開始,為求整數解，將可行域分解為子區域，解相應的子問題，這個過程叫做分枝，然後不斷降低上界，提高下界，這個過程稱為定界，分枝和定界逐步迭代最終搜尋到最優整數解。
分枝定界法基本思想是從解鬆弛的線性規劃問題lp開始,lp已經有很好的軟體求解。對於最大化問題lp問題的解是ip問題的解的上界。如果lp的最優解滿足整數要求，就得到了ip的最優解。
否則，如果要求是整數的某個變數不是整數，可以通過舍和入將可行域分解為兩個子區域，得到兩個相應的子問題，這個過程叫做分枝。分別求解得到兩個子問題的鬆弛問題，其最優解如果滿足整數條件就不再繼續分枝，其目標函式的值是原問題的目標函式值的乙個下界。對於不滿足整數約束的分枝繼續進行新的分枝。
在這個過程中不斷降低上界，提高下界，這個過程稱為定界。分枝和定界逐步迭代最終搜尋到原ip問題最優解。
分枝提供了逐步搜尋整數最優解的方法，定界可以提高搜尋的效率。
2.分枝定界法的計算過程
第1步：解ip的鬆弛問題lp:
(1) 若lp沒有可行解，則ip也沒有可行解，計算停止；
(2) 若lp有最優解並符合ip的整數條件，即得到了ip的最優解，計算停止；
(3) 若lp有最優解,但不符合ip的整數條件，以表示與相應的目標函式的最大值，進行下一步
第2步：定界：以表示ip的最優解對應的最大值，則有
再用觀察法找出ip 的乙個可行解，並以它對應的目標函式值作為的下界，於是得到界
第3步：分枝：在lp的最優解中任選乙個不符合整數條件的變數，例如，構造兩個約束條件：
將這兩個條件分別加入ip構成兩個子問題ip1和ip2,再解這兩個子問題相應的鬆弛問題lp1和lp2。
第4步：修改上下界：
（1） 在各分枝問題中取目標函式最大的作為新的上界，
（2） 從已符合整數條件的分枝上找目標函式最大的作為下界。如果它好於現行的下界，則用它作為新的下界。
第5步：比較與剪枝：
各分枝的鬆弛問題的目標函式的最大值，如果小於的下界，則這一枝剪掉，此後不再考慮，若其最大值大於的下界，但不符合整數條件，返回第3步，繼續分枝。
如此迭代直到整數最優解。
下面通過求解例5-1具體說明分枝定界法的各個步驟：
給整數規劃問題
它的可行域如圖5-1所示。
圖5-1問題lp的可行域
第1步：解ip的鬆弛問題lp:()
應用linprog函式解lp:
>> f=[-3 -2];
a=[2 3;1 0.5];
b=[14; 4.5];[x,fval]=linprog(f,a,b)
optimization terminated.
x = 3.2500
2.5000
fval =
-14.7500
得到最優解：，對應的目標函式值為。這個解不是ip的可行解，進行第2步。
第2步：定界：確定為解的上界。取，得到ip的乙個可行解，對應的目標函式的值為，取為下界。於是得到
第3步：分枝：在lp的最優解中任選乙個不符合整數條件的變數，，構造兩個約束條件：
將這兩個條件你別加入ip構成兩個子問題ip1和ip2,
ip1:
ip2:
再解這兩個子問題相應的鬆弛問題lp1和lp2。
lp1:
lp2:
lp1和lp2的可行域如圖5-2所示。
圖5-2問題lp1和lp2的可行域
注意 lp1和lp2的兩個可行域包含了原整數規劃問題的所有可行解，被捨棄的區域內不包含原整數規劃問題的任何可行解（圖中沒有x號）。
應用linprog函式解lp1：
>> f=[-3 -2];
a=[2 3;1 0.5];
a1=[a;0 1];
b=[14; 4.5];
b1=[b;2];
[x,fval]=linprog(f,a1,b1)
optimization terminated.
x = 3.5000
2.0000
fval =
-14.5000
問題lp1的最優解為，相應的。
應用linprog函式解lp2：
>> f=[-3 -2];
a=[2 3;1 0.5];
a2=[a;0 -1];
b=[14; 4.5];
b2=[b;-3];
[x,fval]=linprog(f,a2,b2)
optimization terminated.
x = 2.5000
3.0000
fval =:
-13.5000
問題lp2的最優解為，相應的。
第4步：修改上下界：
取作為新的上界，修改後的上下界為
第5步：比較與剪枝：
問題lp1和lp2的解都不是原問題的可行解，剪掉目標函式較小的lp2分枝，,取目標函式值較大的lp1繼續分枝。
在lp1中分別加約束和，得到問題lp11和lp12。
lp11:
lp12:
lp11和lp12的可行域如圖5-3所示。
圖5-3問題lp11和lp12的可行域
應用linprog函式解lp11:
>> f=[-3 -2];
a=[2 3;1 0.5];
a1=[a;0 1];
a11=[a1;1 0];
b=[14; 4.5];
b1=[b;2];
b11=[b1;3];
[x,fval]=linprog(f,a11,b11)
optimization terminated.
x = 3.0000
2.0000
fval =
-13.0000
lp11的最優解為，相應的目標函式值，
應用linprog函式解lp12:
>> f=[-3 -2];
a=[2 3;1 0.5];
a1=[a;0 1];
a12=[a1;-1 0];
b=[14; 4.5];
b1=[b;2];
b12=[b1;-4];
[x,fval]=linprog(f,a12,b12)
optimization terminated.
x = 4.0000
1.0000
fval =
-14.0000
lp12的最優解為，相應的目標函式值。
分枝lp11的目標函式值比較小，應該剪去，剩下的一枝lp12的解滿足整數要求，已經得到原ip問題的最優解：，相應的目標函式值。
整個求解過程可以由圖5-4表示。.
剪枝（停止對這一枝的進一步考察）的3個原則：
（1） 目標函式的值小於等於當前的z的下界，
（2） 鬆弛問題沒有可行解，
（3） 鬆弛問題的最優解已經滿足整數要求，如果它好於現行的可行解，則用它作為新的下界。
由於分枝定界法既可以解純整數規劃問題又能解混合整數規劃問題，並且便於用計算機輔助求解，因此它已經成為求解整數規劃問題的重要方法。
整數規劃部分複習題
1. 為什麼研究整數規劃？舉乙個實際中的整數規劃問題的例子。
2. 簡述分枝定界法的主要思想。
3. 在分枝定界法中如何確定整數規劃目標函式的最大值的上界和下界？
運籌學介紹
運籌學 operation research or operation research原意是操作研究 作業研究 運用研究 作戰研究，譯作運籌學，是借用了 史記 運籌策於帷幄之中，決勝於千里之外 一語中 運籌 二字，既顯示其軍事的起源，也表明它在我國已 早有萌芽。運籌學作為一門現代科學，是在第二次世...
運籌學基礎
填空題一1決策過程的第一步即是觀察問題所處的環境，一般而言，問題域所處的環境有內部環境和外部環境兩方面。2簡單移動平均法的計算公式為而加權移動平均的計算公式為 3悲觀主義遠側也稱最大最小原則，樂觀主義原則也稱最大最大原則。4安全庫存量也可稱為保險庫存量，是為了預防缺貨而儲存的額外庫存量。5網路圖中乙...
運籌學基礎
第一章導論 1.1概述 1.1.1運籌學與管理決策 運籌學是一門研究如何有效地組織和管理人機系統的科學。分析程式有兩種基本形式 定性的和定量的。定性分析的技巧是企業領導固有的，隨著經驗的積累而增強。運籌學的定義 運籌學利用計畫方法和有關多學科的要求，把複雜功能關係表示成數學模型，其目的是通過定量分析...