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

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

2、(max(min)2111dxxxcxbbxaaxcznjinjjijnjjj中部分或全部取整數(shù)4整數(shù)線性規(guī)劃的幾種類(lèi)型：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/箱箱) 重量重量(百公斤百公斤/箱箱) 利潤(rùn)利潤(rùn)(百元百元/箱箱) 甲甲 5 2 20 乙乙 4 5 10裝運(yùn)限制裝運(yùn)限制 24 13 例例1 1、集裝箱運(yùn)貨、集裝箱運(yùn)貨整數(shù)規(guī)劃的例子：整數(shù)規(guī)劃的例子： 6解：設(shè)解：設(shè)X1 , X2 為甲、乙兩貨物各托運(yùn)箱數(shù)為甲、乙兩貨物各托運(yùn)箱數(shù)5X1+4X2 242X1+5X2 13X1 , X2 0 0X1 , X2為整數(shù)為整數(shù)Max Z = 20 Max Z = 20 X1 + 10 X27例例2 2、背包問(wèn)題、背包問(wèn)題8背包可再裝入背包可再裝入8 8單位重量，單位重量，1010單位體積物品單位體積物品物品物

4、品 名稱名稱 重量重量 體積體積 價(jià)值價(jià)值 1 書(shū)書(shū) 5 2 20 2 攝像機(jī)攝像機(jī) 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 某服務(wù)部門(mén)各時(shí)段（每2小時(shí)為一時(shí)段）需要的服務(wù)員人數(shù)見(jiàn)下表。按規(guī)定服務(wù)員連續(xù)工作8小時(shí)為一班?，F(xiàn)要求安排服務(wù)員的工作時(shí)間，使服務(wù)部門(mén)服務(wù)員總數(shù)最少。時(shí)段12345678服務(wù)員

5、最少人數(shù)10891113853例例3、人員排班、人員排班11解：設(shè)在第j時(shí)段開(kāi)始上班的人數(shù)為 ，則jx,0,35813119810min543215545435432432132121154321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz且為整數(shù)12l解的特點(diǎn) 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃及其松弛問(wèn)題松弛問(wèn)題比較，前者的最優(yōu)解的目標(biāo)函數(shù)值不會(huì)優(yōu)于后者的。例：考慮下面的整數(shù)規(guī)劃問(wèn)題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世紀(jì)世紀(jì)6060年代初由是年代初由是Land DoigLand Doig和和DakinDakin等人提出，是枚等人提出，是枚舉方法基礎(chǔ)上的改進(jìn)。舉方法基礎(chǔ)上的改進(jìn)。l分支定界法的分支定界法的關(guān)鍵關(guān)鍵是分支和定界。是分支和定界。l思路：思路：利用其松弛問(wèn)題的最優(yōu)解（值）來(lái)分支利用其松弛問(wèn)題的最優(yōu)解（值）來(lái)分支定界。定界。15l例：求解整數(shù)規(guī)劃問(wèn)題A0,7020756799040max21212121xxxxxxxxz且為整數(shù)松弛問(wèn)題B設(shè)

7、問(wèn)題A的最優(yōu)目標(biāo)函數(shù)值為 。zz*0,7020756799040max21212121xxxxxxxxz整數(shù)規(guī)劃問(wèn)題A初始上界16l圖解法分析： 、 、 、 、 、 、 、 、 、 、 、0 1 2 3 4 5 6 7 8 9 108 -7 -6 -5 -4 -3 -2 -1 -B35682.181.4021zxx不是問(wèn)題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 是問(wèn)題A解但 zz334910.200.4:1211zxxB22x32x4B3B不是問(wèn)題A解而 剪枝 zz420l圖解法分析： 0 1 2 3 4 5 6 7 432130800.144.5:5215zxxB無(wú)可行解:6B34157.100.5:2212zxxB12x22x5B21l分支定界的全過(guò)程：35682.18

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