整數(shù)規(guī)劃1-概念、分支定界法

1、整數(shù)規(guī)劃整數(shù)規(guī)劃- Integer Programming（IP）l整數(shù)規(guī)劃的數(shù)學模型及解的特點整數(shù)規(guī)劃的數(shù)學模型及解的特點l分支定界法、割平面法分支定界法、割平面法l0-10-1整數(shù)規(guī)劃整數(shù)規(guī)劃l指派問題指派問題2 整數(shù)規(guī)劃的數(shù)學模型及解的特點整數(shù)規(guī)劃的數(shù)學模型及解的特點l整數(shù)規(guī)劃數(shù)學模型的一般形式: 一部分或全部一部分或全部決策變量取整數(shù)值的規(guī)劃問題 整數(shù)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃中不考慮整數(shù)條件不考慮整數(shù)條件時對應的規(guī)劃問題 該整數(shù)規(guī)劃的松弛問題該整數(shù)規(guī)劃的松弛問題松弛問題為線性規(guī)劃的整數(shù)規(guī)劃問題 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃3l整數(shù)線性規(guī)劃一般形式：整數(shù)線性規(guī)劃一般形式：)(,)(0)(),()

2、(max(min)2111dxxxcxbbxaaxcznjinjjijnjjj中部分或全部取整數(shù)4整數(shù)線性規(guī)劃的幾種類型：l純整數(shù)線性規(guī)劃(pure integer linear programming):全部全部決策變量都必須取整數(shù)值。決策變量都必須取整數(shù)值。l混合整數(shù)線性規(guī)劃(mixed integer linear programming)：決策變量中決策變量中一部分一部分必須取整數(shù)值必須取整數(shù)值，另一部分另一部分可以不取整數(shù)值?？梢圆蝗≌麛?shù)值。l0-1型整數(shù)線性規(guī)劃(zero-one integer linear programming)：決策變量只能取值決策變量只能取值 0 0 或或

3、 1 1 。5 貨物貨物 體積體積(米米3/箱箱) 重量重量(百公斤百公斤/箱箱) 利潤利潤(百元百元/箱箱) 甲甲 5 2 20 乙乙 4 5 10裝運限制裝運限制 24 13 例例1 1、集裝箱運貨、集裝箱運貨整數(shù)規(guī)劃的例子：整數(shù)規(guī)劃的例子： 6解：設解：設X1 , X2 為甲、乙兩貨物各托運箱數(shù)為甲、乙兩貨物各托運箱數(shù)5X1+4X2 242X1+5X2 13X1 , X2 0 0X1 , X2為整數(shù)為整數(shù)Max Z = 20 Max Z = 20 X1 + 10 X27例例2 2、背包問題、背包問題8背包可再裝入背包可再裝入8 8單位重量，單位重量，1010單位體積物品單位體積物品物品物

4、品 名稱名稱 重量重量 體積體積 價值價值 1 書書 5 2 20 2 攝像機攝像機 3 1 30 3 枕頭枕頭 1 4 10 4 休閑食品休閑食品 2 3 18 5 衣服衣服 4 5 15 9解：解：Xi為是否帶第為是否帶第 i 種物品種物品maxZ=20X1 + 30X2 +10X3+18X4 +15X55X1+3X2 +X3 +2X4 +4X5 82X1+X2 +4X3 +3X4 +5X5 10Xi為為0, 110 某服務部門各時段（每2小時為一時段）需要的服務員人數(shù)見下表。按規(guī)定服務員連續(xù)工作8小時為一班?，F(xiàn)要求安排服務員的工作時間，使服務部門服務員總數(shù)最少。時段12345678服務員

5、最少人數(shù)10891113853例例3、人員排班、人員排班11解：設在第j時段開始上班的人數(shù)為 ，則jx,0,35813119810min543215545435432432132121154321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz且為整數(shù)12l解的特點 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃及其松弛問題松弛問題比較，前者的最優(yōu)解的目標函數(shù)值不會優(yōu)于后者的。例：考慮下面的整數(shù)規(guī)劃問題0,823324max21212121xxxxxxxxz且取整數(shù)13從圖上分析：0 1 2 3 4 5 6 7 8BPC1A2A3A4A*A整數(shù)規(guī)劃最優(yōu)解14分支定界法分支定界法l分支定界法分支定界法是

6、一種隱枚舉方法（是一種隱枚舉方法（implicit implicit enumerationenumeration）或部分枚舉方法，在）或部分枚舉方法，在2020世紀世紀6060年代初由是年代初由是Land DoigLand Doig和和DakinDakin等人提出，是枚等人提出，是枚舉方法基礎上的改進。舉方法基礎上的改進。l分支定界法的分支定界法的關鍵關鍵是分支和定界。是分支和定界。l思路：思路：利用其松弛問題的最優(yōu)解（值）來分支利用其松弛問題的最優(yōu)解（值）來分支定界。定界。15l例：求解整數(shù)規(guī)劃問題A0,7020756799040max21212121xxxxxxxxz且為整數(shù)松弛問題B設

7、問題A的最優(yōu)目標函數(shù)值為 。zz*0,7020756799040max21212121xxxxxxxxz整數(shù)規(guī)劃問題A初始上界16l圖解法分析： 、 、 、 、 、 、 、 、 、 、 、0 1 2 3 4 5 6 7 8 9 108 -7 -6 -5 -4 -3 -2 -1 -B35682.181.4021zxx不是問題A解但 0*zz4:11xB5:12xB356,0zz0,7020756799040max21212121xxxxxxxxz17l圖解法分析： 0 1 2 3 4 5 6 7 43214:11xB2B18l圖解法分析： 0 1 2 3 4 5 6 7 43214:11xB34

8、910.200.4:1211zxxB34157.100.5:2212zxxB349 0zz2B35682.181.4021zxx51x41x19l圖解法分析： 432134000.200.4:3213zxxB32700.342.1:4214zxxB 0 1 2 3 4 5 6 7 是問題A解但 zz334910.200.4:1211zxxB22x32x4B3B不是問題A解而 剪枝 zz420l圖解法分析： 0 1 2 3 4 5 6 7 432130800.144.5:5215zxxB無可行解:6B34157.100.5:2212zxxB12x22x5B21l分支定界的全過程：35682.18

9、1.4:021zxxB34910.200.4:1211zxxB34157.100.5:2212zxxB34000.200.4:3213zxxB32700.342.1:4214zxxB356,0zz3490zz341340zz41x51x22x32x22l分支定界的全過程：30800.144.5:5215zxxB無可行解:6B12x22x34910.200.4:1211zxxB34157.100.5:2212zxxB34000.200.4:3213zxxB32700.342.1:4214zxxB3490zz341340zz22x32x340* zz23步驟：l步驟1、整數(shù)規(guī)劃問題為A，其松弛問題為B 設 為問題A的初始下界（min問題 為上界）