【正文】 jxXbAXtsCXzIP0.m a x??????0.m a xXbAXtsCXzLP及其松弛問題（ LP）的最優(yōu)值是 (IP)的最優(yōu)值的上界 ，可以找到一個整數解、若 XLP2最優(yōu)值的下界是則 IPXCIP IZ最優(yōu)值松弛問題 L0 0LZ最優(yōu)值0LI ZZ ?L1 L2 1LZ最優(yōu)值 2LZ最優(yōu)值01 LL ZZ ? 02 LL ZZ ?1, LI ZZ ? 2LI ZZ ?或通過對（ L0）分枝，使（ IP）的最優(yōu)值 的上界不斷下降， L3 L4 L5 L6 是整數解的最優(yōu)解若某個 00 * ii XL的可行解是則 )(* 0 IPX i Ii ZCX ?0*,有,* 0ikk CXZL ?的最優(yōu)值若的下界即找到 IZ,* kCX將下界改為0, iL關閉是整數解最優(yōu)解 kX *)1(剪枝：的最優(yōu)值若 0* ikk CXZL ?:kL討論子問題0*iCXkL關閉,不是整數解最優(yōu)解 kX *)2(分枝繼續(xù)對 kL下界不斷上升， 上界 =下界 得最優(yōu)值 分枝定界法的基本思路 ： 不斷降低（ IP）最優(yōu)值的上界，提高下界， 當上界等于下界時，得到最優(yōu)解 通過對松弛問題的分枝， 分枝定界法計算過程： :0L討論松弛問題無最優(yōu)解，、 01 L 無最優(yōu)解則 )( IP 結束002022 ),*,**(*2 zxxxX on 最優(yōu)值，、最優(yōu)解 ??為整數解0*)1( X 的最優(yōu)解為，則 )(* 0 IPX中至少有一個是分數，0*)2( X結束是分數設 01*x ：分枝上界 :1L子問題 :2L子問題無最優(yōu)解，、 11 L 剪枝為下界1, z 關閉繼續(xù)分枝1112111 ),*,**(*2 z xxxX n最優(yōu)值 ，、最優(yōu)解 ??為整數解1*)1( X中至少有一個是分數：1*)2( X,* 0ikk CXZL ?的最優(yōu)值若：設已找到下界 0iZ,* kCX將下界改為是整數解最優(yōu)解 kX *)1(剪枝：的最優(yōu)值若 0* ikk CXZL ?:kL討論子問題kL關閉,不是整數解最優(yōu)解 kX *)2(分枝繼續(xù)對 kL當所有的子問題均被關閉或剪枝后 目標函數值最大的整數解既為所求的最優(yōu)解 ?????????????為整數2121212121,0,0.2030m a xxxxxxxxxtsxxz?????????????0,0.2030m a x212121210xxxxxxtsxxzL ：松弛問題 2445 21 ?? XX1352 21 ?? XXX1 X2 甲貨物運輸的箱數 乙貨物運輸的箱數 Max Z = 20X1+10X2 每箱利潤 5X1 + 4X2 =24（體積限制） 2X1 + 5X2 =13 （重量限制） X1=0 , X2 =0 X1, X2 整數（箱數不能為分數） 目標函數等值線 線性規(guī)劃的最優(yōu)解 (,0) 整數規(guī)劃的最優(yōu)解 (4,1) 整數規(guī)劃求解 ?可以想到的解法 ?枚舉法：解決多數問題工作量太大！ ?鄰近點法： ?優(yōu)點： ?簡單，易操作； ?若原問題的最優(yōu)解很大，對找鄰近點的誤差不敏感，則成立； ?缺點：有時候不成立。 分析 ? 以上問題的特點是：變量為整數 ?背包問題：對每一件物品進行取舍，裝或者不裝； ?選址問題：對每一個被選點有兩種選擇，在這里建或者不在這里建； ?投資決策問題：對每一個考慮的項目，投資或者不投資。每個項目需要的資金和利潤已知。問在何處建設倉庫使得各倉庫到所有連鎖店的總距離最小。整數規(guī)劃 回顧：線性規(guī)劃模型 ? 前面指出，線性規(guī)劃在生產實踐中有重要作用，能夠解決許多優(yōu)化問題； ? 用單純性算法能方便地對線性規(guī)劃問題求解 0..m a x???xbAxtsxczT已知： 兩種貨物裝葙 每種貨物裝葙利潤 體積限制 重量限制 決策變量 :兩種貨物各多少箱 Max Z =利潤最大？ 箱數不能為分數 貨物 X1 貨物 X2 限量 體積 5 4 24 重量 2 5 13 利潤 20 10 另一類現實問題 實踐中的其他問題舉例 ? 背包問題：背包的容積一定，現有多種物品待裝，各物品的價值、體積已知，求最優(yōu)配裝方案，使得在不超過背包的容量的前提下裝入物品的價值最大。 ? 選址問題：某商場在全市有數個連鎖店，擬建立 n個倉庫對所有連鎖店供貨，有數個地點作為被選點。 ? 投資決策問題：現有一定的資金，有數個可以考慮的投資項目。問如何選擇投資項目，使得獲得的利潤最大。 ? 這類問題無法用線性規(guī)劃求解！因為線性規(guī)劃的解可能包含小數部分 整數規(guī)劃模型 且部分或全部為整數0..m a x???xbAxtsxczT分析 ? 整數規(guī)劃模型反映了上述例子的特征，適宜解決這類問題； ? 整數規(guī)劃與線性規(guī)劃相比，增加了變量部分或全部為整數的條件。 鄰近點法的反例 且為整數0,45956..85m a x21212121???????xxxxxxtsxxz?原問題的最優(yōu)解 （ ， ） 最優(yōu)值： z= ?利用鄰近點法： ?（ 2， 3） z=34 ?（ 3， 3） z=39 ?（ 2， 4） 無解 ?（ 3， 4） 無解 ?實際上：本問題的最優(yōu)解 （ 0， 5） 最優(yōu)值： z=40 啟示 ? 鄰近點法雖然不成立，但是給我們一個很好的思路！ ? 不要硬碰硬的去直接解決整數規(guī)劃！ ? 先解決它所對應的線性規(guī)劃，從其最優(yōu)解出發(fā)，逐漸向整數規(guī)劃的最優(yōu)解靠攏 分枝定界法的原理 ： 分枝 ?????????????為整數對2121212121,0,0.2030m a xxxxxxxxxtsxxz?????????????0,0.2030m a x)(212121210xxxxxxtsxxzL ：松弛問題, 21 ?? xx松弛問題的最優(yōu)解： 0 1 2 3 4 5 6 7 8 :0L 155, 021 ??? zxx ，:1L3440,6173121???zxx ，4x1+x2= 2x1+3x2= 2321 ??xx：1303 ?z關閉3411 21 ?? xx ，22854 ?z3z?27221 ?? xx ，1305 ?z無可行解剪枝21421 ?? xx ，1302 ?z 剪枝, 21 ?? xx ，最優(yōu)解：:2L3L4L5L剪枝6L1 3 0*23)( 21???ZxxIP最優(yōu)值：，的最優(yōu)解：如何選擇分枝的節(jié)點及分枝變量？ 分枝節(jié)點選擇的原則：盡快找到好的整數解，減少搜索節(jié)點， 提高搜索效率。 ? 若得到非整數的最優(yōu)解，則增加能割去非整數解的線性約束條件(或稱為割平面 )，使得由原可行域被切割掉一部分，這部分只包含非整數解，但沒有切割掉任何整數可行解。 ? 以下僅討論純整數線性規(guī)劃的情形。 第 3節(jié) 割平面解法 ? 現設想，如能找到像 CD那樣的直線去切割域 R(圖 56)，去掉三角形域 ACD，那么具有整數坐標的 C點 (1， 1)就是域 R′的一個極點。 ?圖 56 第 3節(jié) 割平面解法 ? 在原問題的前兩個不等式中增加非負松弛變量 x x4， 使兩式變成等式約束： ?x1+x2+x3 =1 ⑥ 3x1+x2 +x4=4 ⑦ 不考慮條件 ⑤ ， 用單純形表解題 ， 見表 52。 可從最終計算表中得到非整數變量對應的關系式： 474143434141432431??????xxxxxx第 3節(jié) 割平面解法 ? 為了得到整數最優(yōu)解。在上式中 (其實只考慮一式即可 )從等式左邊看是整數；等式右邊也應是整數。)內是正數；所以等式右邊必是非正數。于是整數條件⑤可由下式所代替： 即 ? 3x3? x4≤ ? 3 ⑧ 0414343 43 ??? xx第 3節(jié) 割平面解法 ? 這就得到一個切割方程 (或稱為切割約束 )， 將它作為增加約束條件 ， 再解例 3。 c j 1 1 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 1 1 0 x 1 x 2 x 5 3/4 7/4 3 1 0 0 0 1 0 1/4 3/4 3 1/4 1/4 1 0 0 1 c j z j 5/2 0 0 1/2 1/2 0 第 3節(jié) 割平面解法 ? 這從表 53的 b列中可看到 ， 這時得到的是非可行解 ， 于是需要用對偶單純形法繼續(xù)進行計算 。 c j 1 1 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 1 1 0 x 1 x 2 x 3 1 1 1 1 0 0 0 1 0 0 0 1 1/3 0 1/3 1/12 1/4 1/3