管理學(xué)第3章整數(shù)規(guī)劃課件

第3章整數(shù)規(guī)劃ILP問(wèn)題的概述1第3章整數(shù)規(guī)劃ILP問(wèn)題的概述1整數(shù)規(guī)劃概述在線性規(guī)劃問(wèn)題中，所有的解都假設(shè)為具有連續(xù)型的數(shù)值，即解可以是整數(shù)、分?jǐn)?shù)或帶有小數(shù)點(diǎn)的實(shí)數(shù)。但對(duì)于某些具體的問(wèn)題，常要求最優(yōu)解是整數(shù)的情形。例如，所求的解是機(jī)器臺(tái)數(shù)，完成工作的人數(shù)或裝貨的車數(shù)等，這時(shí)，分?jǐn)?shù)或小數(shù)的解答就不符合要求。為了滿足整數(shù)解的要求，初看起來(lái)，似乎只要把已求得的解經(jīng)過(guò)“舍入化整”就可以，但這常常是不可行的。（因?yàn)榛蟛灰?jiàn)得是可行解。或雖然是可行解，但不一定是最優(yōu)解。）2整數(shù)規(guī)劃概述在線性規(guī)劃問(wèn)題中，所有的解都假設(shè)為具有連續(xù)型的數(shù)整數(shù)規(guī)劃概述求最優(yōu)整數(shù)解的問(wèn)題，稱為整數(shù)規(guī)劃(IntegerProgramming)，簡(jiǎn)稱為IP。整數(shù)規(guī)劃中，如果所有的變量都要求是非負(fù)整數(shù)，就稱為純整數(shù)規(guī)劃(PureIntegerProgramming)或全整數(shù)規(guī)劃(AllIntegerProgramming)。如果僅是其中一部分變量取值為整數(shù)，則稱為混合整數(shù)規(guī)劃(MixedIntegerProgramming)。如果變量只取0或1，則稱為0-1規(guī)劃。由于變量限制為整數(shù)實(shí)質(zhì)上一個(gè)非線性約束，如0、1限制，因此：整數(shù)規(guī)劃問(wèn)題的求解要比一般的線性規(guī)劃困難得多。3整數(shù)規(guī)劃概述求最優(yōu)整數(shù)解的問(wèn)題，稱為整數(shù)規(guī)劃(Intege3.1整數(shù)線性規(guī)劃問(wèn)題整數(shù)規(guī)劃是一類要求變量取整數(shù)值的數(shù)學(xué)規(guī)劃。對(duì)于兩個(gè)變量的整數(shù)規(guī)劃，可以用圖解法，但對(duì)于一般的整數(shù)規(guī)劃問(wèn)題，則需要專門(mén)的方法：割平面法、分枝定界法、(隱枚舉法、匈牙利法)。本章的講解將從圖解法開(kāi)始，引出若干個(gè)啟示后，再學(xué)習(xí)專門(mén)的方法。43.1整數(shù)線性規(guī)劃問(wèn)題整數(shù)規(guī)劃是一類要求變量取整數(shù)值的數(shù)3.1.1整數(shù)規(guī)劃的典型問(wèn)題舉例投資決策問(wèn)題某部門(mén)在今后五年中可用于投資的資金額為B萬(wàn)元，有n(n

2)個(gè)項(xiàng)目，假定每個(gè)最多投資一次，第j個(gè)項(xiàng)目需資金bj萬(wàn)元，將會(huì)獲利cj萬(wàn)元，問(wèn)如何投資使總利潤(rùn)最大。承建宿舍問(wèn)題某建筑公司建兩類宿舍，甲占地0.25

103(m2)，乙占地0.25

103(m2)，已購(gòu)進(jìn)地3

103(m2)。計(jì)劃甲不超過(guò)8幢，乙不超過(guò)4幢，問(wèn)如何建使獲利最大？旅行售貨員問(wèn)題一推銷員從v0出發(fā)，再遍訪v1,v2,…,vn各一次，再返回v0。從vi到vj的差旅費(fèi)為cij，如何使總費(fèi)用最小。背包問(wèn)題等53.1.1整數(shù)規(guī)劃的典型問(wèn)題舉例投資決策問(wèn)題5例1：某工廠在計(jì)劃期內(nèi)要安排甲、乙兩種儀器設(shè)備的生產(chǎn)，已知生產(chǎn)儀器設(shè)備需要A、B兩種材料的消耗以及資源的限制，如右表。問(wèn)題：工廠應(yīng)分別生產(chǎn)多少件甲、乙種儀器設(shè)備才能使工廠獲利最多？解：目標(biāo)函數(shù)：Maxz=x1+x2約束條件：s.t.3x1+2x2≤102x2≤5x1，x2≥0為整數(shù)不考慮整數(shù)約束得到最優(yōu)解：x1=1.667，x2=2.5；z=4.167考慮整數(shù)約束得到最優(yōu)解：x1=2，x2=2；z=4整數(shù)規(guī)劃的最優(yōu)目標(biāo)值小于相應(yīng)線性規(guī)劃的最優(yōu)目標(biāo)值(相當(dāng)于附加一個(gè)約束)3.1.2圖解法求解及啟示6例1：某工廠在計(jì)劃期內(nèi)要安排甲、乙兩種儀器設(shè)備的生產(chǎn)，已知例2：某集裝箱運(yùn)輸公司，箱型標(biāo)準(zhǔn)體積24m3，重量13T,現(xiàn)有兩種貨物可以裝運(yùn)，甲貨物體積5m3、重量2T、每件利潤(rùn)2000元；乙貨物體積4m3、重量5T、每件利潤(rùn)1000元，如何裝運(yùn)獲利最多？maxZ=2000x1+1000x2s.t.5x1+4x2≤242x1+5x2

≤13x1,x2

≥0且為整數(shù)解此LP問(wèn)題，得：X1=4.8，X2=0顯然不是可行解整數(shù)規(guī)劃圖解法x11234567231BAx2B（4，1）才是IP的最優(yōu)解7例2：某集裝箱運(yùn)輸公司，箱型標(biāo)準(zhǔn)體積24m3，重量13T,現(xiàn)圖解法的啟示整數(shù)規(guī)劃與一般線性規(guī)劃之間有聯(lián)系，一般我們稱不加上整數(shù)約束的問(wèn)題為對(duì)應(yīng)整數(shù)規(guī)劃問(wèn)題的松弛問(wèn)題。其解也有聯(lián)系：兩者之間的解不能簡(jiǎn)單的通過(guò)取整得到。如例2：A（4.8，0）點(diǎn)是LP問(wèn)題的可行解，不是IP問(wèn)題的可行解，B（4，1）才是IP的最優(yōu)解，因此純整數(shù)規(guī)劃的可行解就是可行域中的整數(shù)點(diǎn)；非整數(shù)點(diǎn)不是可行解，對(duì)于求解沒(méi)有意義，故切割掉可行域中的非可行解，不妨礙整數(shù)規(guī)劃問(wèn)題的優(yōu)化整數(shù)規(guī)劃的最優(yōu)目標(biāo)值小于相應(yīng)對(duì)于求最大問(wèn)題，整數(shù)規(guī)劃的最優(yōu)目標(biāo)值小于相應(yīng)線性規(guī)劃的最優(yōu)目標(biāo)值，對(duì)于求最小問(wèn)題，線性規(guī)劃的最優(yōu)目標(biāo)值是對(duì)應(yīng)整數(shù)規(guī)劃的下界。如果一般線性規(guī)劃無(wú)解，則對(duì)應(yīng)的整數(shù)規(guī)劃也無(wú)解8圖解法的啟示整數(shù)規(guī)劃與一般線性規(guī)劃之間有聯(lián)系，一般我們稱不加3.1.3：整數(shù)規(guī)劃的模型例3：一登山隊(duì)員做登山準(zhǔn)備，他需要攜帶的物品有：食品，氧氣，冰鎬，繩索，帳篷，照相機(jī)和通訊設(shè)備，每種物品的重要性系數(shù)和重量如下：假定登山隊(duì)員可攜帶最大重量為25公斤。問(wèn)該隊(duì)員應(yīng)如何選擇？序號(hào)1234567物品食品氧氣冰鎬繩索帳篷相機(jī)通訊重量55261224重要系數(shù)20151814841093.1.3：整數(shù)規(guī)劃的模型序號(hào)1234567物品食品氧氣冰鎬請(qǐng)大家試著建立該題的模型！10請(qǐng)大家試著建立該題的模型！10解：如果令xi=1表示登山隊(duì)員攜帶物品i，xi=0表示登山隊(duì)員不攜帶物品i，則問(wèn)題表示成0-1規(guī)劃:MaxZ=20x1+15x2+18x3+14x4

+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6

+4x7

25xi=1或xi=0i=1,2,….711解：如果令xi=1表示登山隊(duì)員攜帶物品i，xi=0表示登山隊(duì)例4：背包問(wèn)題(KnapsackProblem)一個(gè)旅行者，為了準(zhǔn)備旅行的必須用品，要在背包內(nèi)裝一些最有用的東西，但有個(gè)限制，最多只能裝b公斤的物品，而每件物品只能整個(gè)攜帶，這樣旅行者給每件物品規(guī)定了一個(gè)“價(jià)值”以表示其有用的程度。如果共有n件物品，第j件物品aj公斤，其價(jià)值為cj。問(wèn)題變成:在攜帶的物品總重量不超過(guò)b公斤條件下，攜帶哪些物品,可使總價(jià)值最大?12例4：背包問(wèn)題(KnapsackProblem)12解：如果令xj=1表示攜帶物品j，xj=0表示不攜帶物品j，則問(wèn)題表示成0-1規(guī)劃：MaxZ=Σcjxjs.t.Σajxj

b

xj=0或1，j=1,…,n13解：如果令xj=1表示攜帶物品j，xj=0表示不攜帶物品j，整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型整數(shù)規(guī)劃(IP)的一般數(shù)學(xué)模型:max(min)Z=Σcjxjs.t.Σaijxj

bi(i=1,2,…m)xj

0且部分或全部是整數(shù)14整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型14整數(shù)規(guī)劃問(wèn)題的求解方法3.2Gomory割平面法3.3分枝定界法15整數(shù)規(guī)劃問(wèn)題的求解方法3.2Gomory割平面法15解法概述當(dāng)人們開(kāi)始接觸整數(shù)規(guī)劃問(wèn)題時(shí)，常會(huì)有如下兩種初始想法：因?yàn)榭尚蟹桨笖?shù)目有限，因此經(jīng)過(guò)一一比較后，總能求出最好方案，例如，背包問(wèn)題充其量有2n-1種方式；連線問(wèn)題充其量有n!種方式；實(shí)際上這種方法是不可行。16解法概述16設(shè)想計(jì)算機(jī)每秒能比較1000000個(gè)方式，那么要比較完20!（大于2*1018）種方式，大約需要800年。比較完260種方式，大約需要360世紀(jì)。17設(shè)想計(jì)算機(jī)每秒能比較1000000個(gè)方式，那么要比較完20!先放棄變量的整數(shù)性要求，解一個(gè)線性規(guī)劃問(wèn)題，然后用“四舍五入”法取整數(shù)解，這種方法，只有在變量的取值很大時(shí)，才有成功的可能性，而當(dāng)變量的取值較小時(shí)，特別是0-1規(guī)劃時(shí)，往往不能成功。18先放棄變量的整數(shù)性要求，解一個(gè)線性規(guī)劃問(wèn)題，然后用“四舍五入例求下列問(wèn)題：MaxZ=3x1+13x2s.t.2x1+9x2

4011x1-8x2

82x1,x2

0,且取整數(shù)值19例求下列問(wèn)題：19O1234567891054321x1x2I(2,4)B(9.2,2.4)AD可行域OABD內(nèi)整數(shù)點(diǎn)，放棄整數(shù)要求后，最優(yōu)解B(9.2,2.4)Z0=58.8，而原整數(shù)規(guī)劃最優(yōu)解I(2,4)Z0=58，實(shí)際上B附近四個(gè)整點(diǎn)(9,2)(10,2)(9,3)(10,3)都不是原規(guī)劃最優(yōu)解。20O1234O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如能求出可行域的“整點(diǎn)凸包”（包含所有整點(diǎn)的最小多邊形OEFGHIJ），則可在此凸包上求線性規(guī)劃的解，即為原問(wèn)題的解。但求“整點(diǎn)凸包”十分困難。EFGHIJ21O1234O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如把可行域分解成五個(gè)互不相交的子問(wèn)題P1P2P3P4P5之和,P3P5的定義域都是空集,而放棄整數(shù)要求后P1最優(yōu)解I(2,4),Z1=58P2最優(yōu)解(6,3),Z2=57

P4最優(yōu)解(98/11,2),Z4=52(8/11)

P1P2P422O1234X1

2X1

6X2

3X2

2X1

3X1

7X2

4X2

3P1P5P4P2P3P23X12X16X23X22X13假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿足整數(shù)性要求，則此解也是原整數(shù)規(guī)劃的最優(yōu)解。如果求出的解不是整數(shù)，我們采取一定的方法將其割去，再繼續(xù)求解，直至判定無(wú)解或求解出來(lái)；

以上描述了目前解整數(shù)規(guī)劃問(wèn)題的兩種基本途徑。24假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿足整數(shù)性要求3.2割平面法253.2割平面法253.2割平面法

（CuttingPlaceApproach）松馳問(wèn)題：任何整數(shù)規(guī)劃（P），凡放棄某些約束條件（如整數(shù)要求）后，所得到的問(wèn)題（P0）都稱為（P）的松馳問(wèn)題。解法：若P0有最優(yōu)，且為整數(shù)，則P達(dá)最優(yōu)；若P0有最優(yōu)，但不為整，增加一個(gè)割平面條件；若P0無(wú)最優(yōu)，則P無(wú)最優(yōu)。263.2割平面法

（CuttingPlaceAppro割平面條件割平面條件：將由（P0）得到的非整數(shù)解恰在被割掉，而原來(lái)ILP的可行解（均為整數(shù)）都沒(méi)有被割掉。割平面條件的數(shù)學(xué)原理見(jiàn)P88。然后得到LP問(wèn)題（P1），再判斷它的解。如此循環(huán)，直到找到最優(yōu)整數(shù)解。27割平面條件割平面條件：將由（P0）得到的非整數(shù)解恰在被割掉，例：maxx2s.t.3x1+2x2

6-3x1+2x2

0x1，x2

0，整數(shù)-3x1+2x2

=6x1x20-3x1+2x2

=011223圖解法：x2

=1x1

=x228例：maxx2-3x1+2x2=6x1x20-3.3分枝定界法

（BranchandBoundMethod）293.3分枝定界法

（BranchandBoun分枝定界法思想一般求解對(duì)應(yīng)的松馳問(wèn)題，可能會(huì)出現(xiàn)下面幾種情況：若所得的最優(yōu)解的各分量恰好是整數(shù)，則這個(gè)解也是原整數(shù)規(guī)劃的最優(yōu)解，計(jì)算結(jié)束。若松馳問(wèn)題無(wú)可行解，則原整數(shù)規(guī)劃問(wèn)題也無(wú)可行解，計(jì)算結(jié)束。30分枝定界法思想30若松馳問(wèn)題有最優(yōu)解，但其各分量不全是整數(shù)，則這個(gè)解不是原整數(shù)規(guī)劃的最優(yōu)解，轉(zhuǎn)下一步。對(duì)松馳問(wèn)題分解：31若松馳問(wèn)題有最優(yōu)解，但其各分量不全是整數(shù)，則這個(gè)解不是原整數(shù)分枝定界法步驟分枝：從不滿足整數(shù)條件的基變量中任選一個(gè)xl進(jìn)行分枝，它必須滿足xl

[xl]或xl

[xl]+1中的一個(gè)，把這兩個(gè)約束條件加進(jìn)原問(wèn)題中，形成兩個(gè)互不相容的子問(wèn)題（兩分法）。32分枝定界法步驟32定界：把滿足整數(shù)條件各分枝的最優(yōu)目標(biāo)函數(shù)值作為上（下）界，用它來(lái)判斷分枝是保留還是剪枝。剪枝：把那些子問(wèn)題的最優(yōu)值與界值比較，凡不優(yōu)或不能更優(yōu)的分枝全剪掉，直到每個(gè)分枝都查清為止。33定界：把滿足整數(shù)條件各分枝的最優(yōu)目標(biāo)函數(shù)值作為上（下）界，用例用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0整數(shù)用單純形法可解得相應(yīng)的松馳問(wèn)題的最優(yōu)解（6/5，21/10）Z=111/10為各分枝的上界。34例用分枝定界法求解：用單純形法可解得相應(yīng)的松馳問(wèn)題的最012344321x1x2分枝：X1

1,x1

2P1P23501兩個(gè)子問(wèn)題：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0，x1

1，整數(shù)用單純形法可解得相應(yīng)的（P1）的最優(yōu)解（1，9/4）Z=10(3/4)36兩個(gè)子問(wèn)題：36（P2）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0，x1

2，整數(shù)用單純形法可解得相應(yīng)的（P2）的最優(yōu)解（2，1/2）Z=9(1/2)37（P2）MaxZ=4x1+3x237012344321x1x2再對(duì)（P1）分枝：X1

1（P3）x2

2（P4）x2

3P1P2P3P43801（P1）兩個(gè)子問(wèn)題：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0,x1

1,x2

2整數(shù)用單純形法可解得相應(yīng)的（P3）的最優(yōu)解（1，2）Z=1039（P1）兩個(gè)子問(wèn)題：39（P1）兩個(gè)子問(wèn)題：（P4）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0,x1

1,x2

3整數(shù)用單純形法可解得相應(yīng)的（P4）的最優(yōu)解（0，3）Z=940（P1）兩個(gè)子問(wèn)題：40X1

2X2

2X1

1X2

3P1:(1,9/4)Z=10(3/4)P4:(0,3)Z=9P2:(2,1/2)Z=9(1/2)P3:(1,2)Z=10P:(6/5,21/10)Z=111/10原問(wèn)題的最優(yōu)解（1，2）Z=1041X12X22X11X23P1:(1,例用分枝定界法求解：MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0整數(shù)用單純形法可解得相應(yīng)的松馳問(wèn)題的最優(yōu)解（10/3，4/3）Z=26/3為各分枝的下界。42例用分枝定界法求解：42

0123456

87654321x1x2p43012

0123456

87654321x1x2p選x1進(jìn)行分枝：(P1)x1

3(P2)

x1

4為空集P144012（P1）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0x1

3整數(shù)用單純形法可解得（P1）的最優(yōu)解（3，3/2）Z=945（P1）45（P2）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0x1

4整數(shù)無(wú)可行解。46（P2）46

0123456

87654321x1x2p對(duì)(P1)x1

3選x2進(jìn)行分枝：(P3)x2

1無(wú)可行解(P4)

x2

2P447012（P3）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0，x1

3，x2

1整數(shù)無(wú)可行解。48（P3）48（P4）MinZ=x1+4x2s.t.

2x1+x2

8x1+2x2

6x1,x2

0，x1

3，x2

2整數(shù)用單純形法可解得（P4）的最優(yōu)解（2，2）Z=1049（P4）49X1

4X2

1X13X2

2P1:(3,3/2)Z=9P4:(2,2)Z=10P2:無(wú)可行解P3:無(wú)可行解P:(10/3,4/3)Z=26/3原問(wèn)題的最優(yōu)解（2，2）Z=1050X14X21X13X22P1:(3,3分枝定界法是求整數(shù)規(guī)劃的一種常用的有效的方法，既能解決純整數(shù)規(guī)劃的問(wèn)題，也能解決混合整數(shù)規(guī)劃的問(wèn)題。練習(xí)：Minf=-5x1-4x