整數(shù)規(guī)劃及分支定界法課件

第三章整數(shù)規(guī)劃1第三章整數(shù)規(guī)劃13-1整數(shù)規(guī)劃問題

整數(shù)規(guī)劃是一類要求變量取整數(shù)值的數(shù)學規(guī)劃，可分成線性和非線性兩類。

根據(jù)變量的取值性質(zhì)，又可以分為全整數(shù)規(guī)劃，混合整數(shù)規(guī)劃，0-1整數(shù)規(guī)劃等。

23-1整數(shù)規(guī)劃問題2

整數(shù)規(guī)劃是數(shù)學規(guī)劃中一個較弱的分支，目前只能解中等規(guī)模的線性整數(shù)規(guī)劃問題，而非線性整數(shù)規(guī)劃問題，還沒有好的辦法。3整數(shù)規(guī)劃是數(shù)學規(guī)劃中一個較弱的分支，目前只能解中等規(guī)例3-1：一登山隊員做登山準備，他需要攜帶的物品有：食品，氧氣，冰鎬，繩索，帳篷，照相機和通訊設備，每種物品的重要性系數(shù)和重量如下：假定登山隊員可攜帶最大重量為25公斤。4例3-1：一登山隊員做登山準備，他需要攜帶的物品有：食品，氧55解：如果令xi=1表示登山隊員攜帶物品i，xi=0表示登山隊員不攜帶物品i，則問題表示成0-1規(guī)劃:MaxZ=20x1+15x2+18x3+14x4

+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x725xi=1或xi=0i=1,2,….76解：如果令xi=1表示登山隊員攜帶物品i，xi=0表示登山隊例3-2背包問題(KnapsackProblem)一個旅行者,為了準備旅行的必須用品,要在背包內(nèi)裝一些最有用的東西,但有個數(shù)限制,最多只能裝b公斤的物品,而每件物品只能整個攜帶,這樣旅行者給每件物品規(guī)定了一個“價值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其價值為cj.問題變成:在攜帶的物品總重量不超過b公斤條件下,攜帶哪些物品,可使總價值最大?7例3-2背包問題(KnapsackProblem)7解：如果令xj=1表示攜帶物品j，xj=0表示不攜帶物品j，則問題表示成0-1規(guī)劃:MaxZ=Σcjxjs.t.Σajxjb

xj=0或18解：如果令xj=1表示攜帶物品j，xj=0表示不攜帶物品j，數(shù)學模型整數(shù)規(guī)劃(IP)的一般數(shù)學模型:Max(min)Z=Σcjxjs.t.Σaijxjbi(i=1,2,…m)xj0且部分或全部是整數(shù)9數(shù)學模型9解法概述當人們開始接觸整數(shù)規(guī)劃問題時，常會有如下兩種初始想法：因為可行方案數(shù)目有限，因此經(jīng)過一一比較后，總能求出最好方案，例如，背包問題充其量有2n-1種方式；連線問題充其量有n!種方式；實際上這種方法是不可行。10解法概述10設想計算機每秒能比較1000000個方式，那么要比較完20!（大于2*1018）種方式，大約需要800年。比較完260種方式，大約需要360世紀。11設想計算機每秒能比較1000000個方式，那么要比較完20!先放棄變量的整數(shù)性要求，解一個線性規(guī)劃問題，然后用“四舍五入”法取整數(shù)解，這種方法，只有在變量的取值很大時，才有成功的可能性，而當變量的取值較小時，特別是0-1規(guī)劃時，往往不能成功。12先放棄變量的整數(shù)性要求，解一個線性規(guī)劃問題，然后用“四舍五入例3-3求下列問題：MaxZ=3x1+13x2s.t.2x1+9x24011x1-8x282x1,x20,且取整數(shù)值13例3-3求下列問題：13O1234567891054321x1x2I(2,4)B(9.2,2.4)AD可行域OABD內(nèi)整數(shù)點，放棄整數(shù)要求后，最優(yōu)解B(9.2,2.4)Z0=58.8，而原整數(shù)規(guī)劃最優(yōu)解I(2,4)Z0=58，實際上B附近四個整點(9,2)(10,2)(9,3)(10,3)都不是原規(guī)劃最優(yōu)解。14O1234O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如能求出可行域的“整點凸包”（包含所有整點的最小多邊形OEFGHIJ），則可在此凸包上求線性規(guī)劃的解，即為原問題的解。但求“整點凸包”十分困難。EFGHIJ15O1234O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如把可行域分解成五個互不相交的子問題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)

P1P2P416O1234X12X16X2

3X22X13X17X24X23P1P5P4P2P3P17X12X16X23X22X13假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿足整數(shù)性要求，則此解也是原整數(shù)規(guī)劃的最優(yōu)解。以上描述了目前解整數(shù)規(guī)劃問題的兩種基本途徑。18假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿足整數(shù)性要求分枝定界解法（BranchandBoundMethod)原問題的松馳問題：任何整數(shù)規(guī)劃（IP），凡放棄某些約束條件（如整數(shù)要求）后，所得到的問題（P）都稱為（IP）的松馳問題。19分枝定界解法19最通常的松馳問題是放棄變量的整數(shù)性要求后，（P）為線性規(guī)劃問題。20最通常的松馳問題是放棄變量的整數(shù)性要求后，（P）為線分枝定界法步驟一般求解對應的松馳問題，可能會出現(xiàn)下面幾種情況：若所得的最優(yōu)解的各分量恰好是整數(shù)，則這個解也是原整數(shù)規(guī)劃的最優(yōu)解，計算結束。若松馳問題無可行解，則原整數(shù)規(guī)劃問題也無可行解，計算結束。21分枝定界法步驟21若松馳問題有最優(yōu)解，但其各分量不全是整數(shù)，則這個解不是原整數(shù)規(guī)劃的最優(yōu)解，轉下一步。從不滿足整數(shù)條件的基變量中任選一個xl進行分枝，它必須滿足xl

[xl]或xl

[xl]+1中的一個，把這兩個約束條件加進原問題中，形成兩個互不相容的子問題（兩分法）。22若松馳問題有最優(yōu)解，但其各分量不全是整數(shù)，則這個解不是原整數(shù)定界：把滿足整數(shù)條件各分枝的最優(yōu)目標函數(shù)值作為上（max）（下(min)）界，用它來判斷分枝是保留還是剪枝。剪枝：把那些子問題的最優(yōu)值與界值比較，凡不優(yōu)或不能更優(yōu)的分枝全剪掉，直到每個分枝都查清為止。23定界：把滿足整數(shù)條件各分枝的最優(yōu)目標函數(shù)值作為上（max）（例5-6用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20且為整數(shù)用單純形法可解得相應的松馳問題的最優(yōu)解（6/5，21/10），Z=111/10為各分枝的上界。24例5-6用分枝定界法求解：24012344321x1x2分枝：X11,x12P1P22501兩個子問題：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20，x1

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

3x1+4x2124x1+2x29x1,x20，x1

2，整數(shù)用單純形法可解得相應的（P2）的最優(yōu)解（2，1/2）Z=9(1/2)27（P2）MaxZ=4x1+3x227012344321x1x2再對（P1）分枝：X11（P3）x22（P4）x23P1P2P3P42801（P1）兩個子問題：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x22整數(shù)用單純形法可解得相應的（P3）的最優(yōu)解（1，2）Z=1029（P1）兩個子問題：29（P1）兩個子問題：（P4）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x23整數(shù)用單純形法可解得相應的（P4）的最優(yōu)解（0，3）Z=930（P1）兩個子問題：30X12X2

2X11X23P1:(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原問題的最優(yōu)解（1，2）Z=1031X12X22X11X23P1:(1,例5-7用分枝定界法求解：MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20且取整數(shù)用單純形法可解得相應的松馳問題的最優(yōu)解（10/3，4/3），Z=26/3為各分枝的下界。32例5-7用分枝定界法求解：32

0123456

87654321x1x2p33012

0123456

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

3(P2)

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

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

2x1+x28x1+2x26x1,x20x14整數(shù)無可行解。36（P2）36

0123456

87654321x1x2p對(P1)x13選x2進行分枝：(P3)x21無可行解(P4)

x22P437012（P3）MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20，x13，x21整數(shù)無可行解。38（P3）38（P4）MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20，x13，x22整數(shù)用單純形法可解得（P4）的最優(yōu)解（2，2）Z=1039（P4）39X14X21X13X22P1:(3,3/2)Z=9P4:(2,2)Z=10P2:無可行解P3:無可行解P:(10/3,4/3)Z=26/3原問題的最優(yōu)解（2，2）Z=1040X14X21X13X22P1:(3,3第三章整數(shù)規(guī)劃41第三章整數(shù)規(guī)劃13-1整數(shù)規(guī)劃問題

整數(shù)規(guī)劃是一類要求變量取整數(shù)值的數(shù)學規(guī)劃，可分成線性和非線性兩類。

根據(jù)變量的取值性質(zhì)，又可以分為全整數(shù)規(guī)劃，混合整數(shù)規(guī)劃，0-1整數(shù)規(guī)劃等。

423-1整數(shù)規(guī)劃問題2

整數(shù)規(guī)劃是數(shù)學規(guī)劃中一個較弱的分支，目前只能解中等規(guī)模的線性整數(shù)規(guī)劃問題，而非線性整數(shù)規(guī)劃問題，還沒有好的辦法。43整數(shù)規(guī)劃是數(shù)學規(guī)劃中一個較弱的分支，目前只能解中等規(guī)例3-1：一登山隊員做登山準備，他需要攜帶的物品有：食品，氧氣，冰鎬，繩索，帳篷，照相機和通訊設備，每種物品的重要性系數(shù)和重量如下：假定登山隊員可攜帶最大重量為25公斤。44例3-1：一登山隊員做登山準備，他需要攜帶的物品有：食品，氧455解：如果令xi=1表示登山隊員攜帶物品i，xi=0表示登山隊員不攜帶物品i，則問題表示成0-1規(guī)劃:MaxZ=20x1+15x2+18x3+14x4

+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x725xi=1或xi=0i=1,2,….746解：如果令xi=1表示登山隊員攜帶物品i，xi=0表示登山隊例3-2背包問題(KnapsackProblem)一個旅行者,為了準備旅行的必須用品,要在背包內(nèi)裝一些最有用的東西,但有個數(shù)限制,最多只能裝b公斤的物品,而每件物品只能整個攜帶,這樣旅行者給每件物品規(guī)定了一個“價值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其價值為cj.問題變成:在攜帶的物品總重量不超過b公斤條件下,攜帶哪些物品,可使總價值最大?47例3-2背包問題(KnapsackProblem)7解：如果令xj=1表示攜帶物品j，xj=0表示不攜帶物品j，則問題表示成0-1規(guī)劃:MaxZ=Σcjxjs.t.Σajxjb

xj=0或148解：如果令xj=1表示攜帶物品j，xj=0表示不攜帶物品j，數(shù)學模型整數(shù)規(guī)劃(IP)的一般數(shù)學模型:Max(min)Z=Σcjxjs.t.Σaijxjbi(i=1,2,…m)xj0且部分或全部是整數(shù)49數(shù)學模型9解法概述當人們開始接觸整數(shù)規(guī)劃問題時，常會有如下兩種初始想法：因為可行方案數(shù)目有限，因此經(jīng)過一一比較后，總能求出最好方案，例如，背包問題充其量有2n-1種方式；連線問題充其量有n!種方式；實際上這種方法是不可行。50解法概述10設想計算機每秒能比較1000000個方式，那么要比較完20!（大于2*1018）種方式，大約需要800年。比較完260種方式，大約需要360世紀。51設想計算機每秒能比較1000000個方式，那么要比較完20!先放棄變量的整數(shù)性要求，解一個線性規(guī)劃問題，然后用“四舍五入”法取整數(shù)解，這種方法，只有在變量的取值很大時，才有成功的可能性，而當變量的取值較小時，特別是0-1規(guī)劃時，往往不能成功。52先放棄變量的整數(shù)性要求，解一個線性規(guī)劃問題，然后用“四舍五入例3-3求下列問題：MaxZ=3x1+13x2s.t.2x1+9x24011x1-8x282x1,x20,且取整數(shù)值53例3-3求下列問題：13O1234567891054321x1x2I(2,4)B(9.2,2.4)AD可行域OABD內(nèi)整數(shù)點，放棄整數(shù)要求后，最優(yōu)解B(9.2,2.4)Z0=58.8，而原整數(shù)規(guī)劃最優(yōu)解I(2,4)Z0=58，實際上B附近四個整點(9,2)(10,2)(9,3)(10,3)都不是原規(guī)劃最優(yōu)解。54O1234O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如能求出可行域的“整點凸包”（包含所有整點的最小多邊形OEFGHIJ），則可在此凸包上求線性規(guī)劃的解，即為原問題的解。但求“整點凸包”十分困難。EFGHIJ55O1234O1234567891054321x1x2I(2,4)B(9.2,2.4)AD假如把可行域分解成五個互不相交的子問題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)

P1P2P456O1234X12X16X2

3X22X13X17X24X23P1P5P4P2P3P57X12X16X23X22X13假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿足整數(shù)性要求，則此解也是原整數(shù)規(guī)劃的最優(yōu)解。以上描述了目前解整數(shù)規(guī)劃問題的兩種基本途徑。58假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿足整數(shù)性要求分枝定界解法（BranchandBoundMethod)原問題的松馳問題：任何整數(shù)規(guī)劃（IP），凡放棄某些約束條件（如整數(shù)要求）后，所得到的問題（P）都稱為（IP）的松馳問題。59分枝定界解法19最通常的松馳問題是放棄變量的整數(shù)性要求后，（P）為線性規(guī)劃問題。60最通常的松馳問題是放棄變量的整數(shù)性要求后，（P）為線分枝定界法步驟一般求解對應的松馳問題，可能會出現(xiàn)下面幾種情況：若所得的最優(yōu)解的各分量恰好是整數(shù)，則這個解也是原整數(shù)規(guī)劃的最優(yōu)解，計算結束。若松馳問題無可行解，則原整數(shù)規(guī)劃問題也無可行解，計算結束。61分枝定界法步驟21若松馳問題有最優(yōu)解，但其各分量不全是整數(shù)，則這個解不是原整數(shù)規(guī)劃的最優(yōu)解，轉下一步。從不滿足整數(shù)條件的基變量中任選一個xl進行分枝，它必須滿足xl

[xl]或xl

[xl]+1中的一個，把這兩個約束條件加進原問題中，形成兩個互不相容的子問題（兩分法）。62若松馳問題有最優(yōu)解，但其各分量不全是整數(shù)，則這個解不是原整數(shù)定界：把滿足整數(shù)條件各分枝的最優(yōu)目標函數(shù)值作為上（max）（下(min)）界，用它來判斷分枝是保留還是剪枝。剪枝：把那些子問題的最優(yōu)值與界值比較，凡不優(yōu)或不能更優(yōu)的分枝全剪掉，直到每個分枝都查清為止。63定界：把滿足整數(shù)條件各分枝的最優(yōu)目標函數(shù)值作為上（max）（例5-6用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20且為整數(shù)用單純形法可解得相應的松馳問題的最優(yōu)解（6/5，21/10），Z=111/10為各分枝的上界。64例5-6用分枝定界法求解：24012344321x1x2分枝：X11,x12P1P26501兩個子問題：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20，x1

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

3x1+4x2124x1+2x29x1,x20，x1

2，整數(shù)用單純形法可解得相應的（P2）的最優(yōu)解（2，1/2）Z=9(1/2)67（P2）MaxZ=4x1+3x227012344321x1x2再對（P1）分枝：X11（P3）x22（P4）x23P1P2P3P46801（P1）兩個子問題：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x22整數(shù)用單純形法可解得相應的（P3）的最優(yōu)解（1，2）Z=1069（P1）兩個子問題：29（P1）兩個子問題：（P4）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x23整數(shù)用單純形法可解得相應的（P4）的最優(yōu)解（0，3）Z=970（P1）兩個子問題：30X12X2

2X11X23P1:(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原問題的最優(yōu)解（1，2）Z=1071X12X22X11X23P1:(1,例5-7用分枝定界法求解：MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20且取整數(shù)用單純形法可解得相應的松馳問題的最優(yōu)解（10/3，4/3），Z=26/3為各分枝的下界。72例5-7用分枝定界法求解：32

0123456

8