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

第三章整數規(guī)劃1ppt精選版第三章整數規(guī)劃1ppt精選版3-1整數規(guī)劃問題

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

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

2ppt精選版3-1整數規(guī)劃問題2ppt精選版

整數規(guī)劃是數學規(guī)劃中一個較弱的分支，目前只能解中等規(guī)模的線性整數規(guī)劃問題，而非線性整數規(guī)劃問題，還沒有好的辦法。3ppt精選版整數規(guī)劃是數學規(guī)劃中一個較弱的分支，目前只能解中等規(guī)例3-1：一登山隊員做登山準備，他需要攜帶的物品有：食品，氧氣，冰鎬，繩索，帳篷，照相機和通訊設備，每種物品的重要性系數和重量如下：假定登山隊員可攜帶最大重量為25公斤。4ppt精選版例3-1：一登山隊員做登山準備，他需要攜帶的物品有：食品，氧5ppt精選版5ppt精選版解：如果令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,….76ppt精選版解：如果令xi=1表示登山隊員攜帶物品i，xi=0表示登山隊例3-2背包問題(KnapsackProblem)一個旅行者,為了準備旅行的必須用品,要在背包內裝一些最有用的東西,但有個數限制,最多只能裝b公斤的物品,而每件物品只能整個攜帶,這樣旅行者給每件物品規(guī)定了一個“價值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其價值為cj.問題變成:在攜帶的物品總重量不超過b公斤條件下,攜帶哪些物品,可使總價值最大?7ppt精選版例3-2背包問題(KnapsackProblem)7解：如果令xj=1表示攜帶物品j，xj=0表示不攜帶物品j，則問題表示成0-1規(guī)劃:MaxZ=Σcjxjs.t.Σajxjb

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

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

P1P2P416ppt精選版O1234X12X16X2

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

[xl]或xl

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

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

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

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

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

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

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

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

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

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

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=1031ppt精選版X12X22X11X23P1:(1,例5-7用分枝定界法求解：MinZ=x1+4x2s.t.

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

0123456

87654321x1x2p33ppt精選版012

0123456

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

3(P2)

x14為空集P134ppt精選版012（P1）MinZ=x1+4x2s.t.

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

2x1+x28x1+2x26x1,x20x14整數無可行解。36ppt精選版（P2）36ppt精選版

0123456

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

x22P437ppt精選版012（P3）MinZ=x1+4x2s.t.

2x1+x28x1+2x26x1,x20，x13，x21整數無可行解。38ppt精選版（P3）38ppt精選版（P4）MinZ=x1+4x2s.t.

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

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

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

42ppt精選版3-1整數規(guī)劃問題2ppt精選版

整數規(guī)劃是數學規(guī)劃中一個較弱的分支，目前只能解中等規(guī)模的線性整數規(guī)劃問題，而非線性整數規(guī)劃問題，還沒有好的辦法。43ppt精選版整數規(guī)劃是數學規(guī)劃中一個較弱的分支，目前只能解中等規(guī)例3-1：一登山隊員做登山準備，他需要攜帶的物品有：食品，氧氣，冰鎬，繩索，帳篷，照相機和通訊設備，每種物品的重要性系數和重量如下：假定登山隊員可攜帶最大重量為25公斤。44ppt精選版例3-1：一登山隊員做登山準備，他需要攜帶的物品有：食品，氧45ppt精選版5ppt精選版解：如果令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,….746ppt精選版解：如果令xi=1表示登山隊員攜帶物品i，xi=0表示登山隊例3-2背包問題(KnapsackProblem)一個旅行者,為了準備旅行的必須用品,要在背包內裝一些最有用的東西,但有個數限制,最多只能裝b公斤的物品,而每件物品只能整個攜帶,這樣旅行者給每件物品規(guī)定了一個“價值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其價值為cj.問題變成:在攜帶的物品總重量不超過b公斤條件下,攜帶哪些物品,可使總價值最大?47ppt精選版例3-2背包問題(KnapsackProblem)7解：如果令xj=1表示攜帶物品j，xj=0表示不攜帶物品j，則問題表示成0-1規(guī)劃:MaxZ=Σcjxjs.t.Σajxjb

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

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

P1P2P456ppt精選版O1234X12X16X2

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

[xl]或xl

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

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

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

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

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

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

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

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

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

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

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=1071ppt精選版X12X22X11X23P1:(1,例5-7用分枝定界法求解：MinZ=x1+4x2s.t.

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

0123456

87