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

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

整數(shù)規(guī)劃是一類(lèi)要求變量取整數(shù)值的數(shù)學(xué)規(guī)劃，可分成線(xiàn)性和非線(xiàn)性?xún)深?lèi)。

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

2ppt精選版3-1整數(shù)規(guī)劃問(wèn)題2ppt精選版

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

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

P1P2P416ppt精選版O1234X12X16X2

3X22X13X17X24X23P1P5P4P2P3P17ppt精選版X12X16X23X22X13假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿(mǎn)足整數(shù)性要求，則此解也是原整數(shù)規(guī)劃的最優(yōu)解。以上描述了目前解整數(shù)規(guī)劃問(wèn)題的兩種基本途徑。18ppt精選版假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿(mǎn)足整數(shù)性要求分枝定界解法（BranchandBoundMethod)原問(wèn)題的松馳問(wèn)題：任何整數(shù)規(guī)劃（IP），凡放棄某些約束條件（如整數(shù)要求）后，所得到的問(wèn)題（P）都稱(chēng)為（IP）的松馳問(wèn)題。19ppt精選版分枝定界解法19ppt精選版最通常的松馳問(wèn)題是放棄變量的整數(shù)性要求后，（P）為線(xiàn)性規(guī)劃問(wèn)題。20ppt精選版最通常的松馳問(wèn)題是放棄變量的整數(shù)性要求后，（P）為線(xiàn)分枝定界法步驟一般求解對(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é)束。21ppt精選版分枝定界法步驟21ppt精選版若松馳問(wèn)題有最優(yōu)解，但其各分量不全是整數(shù)，則這個(gè)解不是原整數(shù)規(guī)劃的最優(yōu)解，轉(zhuǎn)下一步。從不滿(mǎn)足整數(shù)條件的基變量中任選一個(gè)xl進(jìn)行分枝，它必須滿(mǎn)足xl

[xl]或xl

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

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

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

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

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

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

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

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

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

1,x23整數(shù)用單純形法可解得相應(yīng)的（P4）的最優(yōu)解（0，3）Z=930ppt精選版（P1）兩個(gè)子問(wèn)題：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原問(wèn)題的最優(yōu)解（1，2）Z=1031ppt精選版X12X22X11X23P1:(1,例5-7用分枝定界法求解：MinZ=x1+4x2s.t.

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

0123456

87654321x1x2p33ppt精選版012

0123456

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

3(P2)

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

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

2x1+x28x1+2x26x1,x20x14整數(shù)無(wú)可行解。36ppt精選版（P2）36ppt精選版

0123456

87654321x1x2p對(duì)(P1)x13選x2進(jìn)行分枝：(P3)x21無(wú)可行解(P4)

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

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

2x1+x28x1+2x26x1,x20，x13，x22整數(shù)用單純形法可解得（P4）的最優(yōu)解（2，2）Z=1039ppt精選版（P4）39ppt精選版X14X21X13X22P1:(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=1040ppt精選版X14X21X13X22P1:(3,3第三章整數(shù)規(guī)劃41ppt精選版第三章整數(shù)規(guī)劃1ppt精選版3-1整數(shù)規(guī)劃問(wèn)題

整數(shù)規(guī)劃是一類(lèi)要求變量取整數(shù)值的數(shù)學(xué)規(guī)劃，可分成線(xiàn)性和非線(xiàn)性?xún)深?lèi)。

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

42ppt精選版3-1整數(shù)規(guī)劃問(wèn)題2ppt精選版

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

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

P1P2P456ppt精選版O1234X12X16X2

3X22X13X17X24X23P1P5P4P2P3P57ppt精選版X12X16X23X22X13假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿(mǎn)足整數(shù)性要求，則此解也是原整數(shù)規(guī)劃的最優(yōu)解。以上描述了目前解整數(shù)規(guī)劃問(wèn)題的兩種基本途徑。58ppt精選版假如放棄整數(shù)要求后，用單純形法求得最優(yōu)解，恰好滿(mǎn)足整數(shù)性要求分枝定界解法（BranchandBoundMethod)原問(wèn)題的松馳問(wèn)題：任何整數(shù)規(guī)劃（IP），凡放棄某些約束條件（如整數(shù)要求）后，所得到的問(wèn)題（P）都稱(chēng)為（IP）的松馳問(wèn)題。59ppt精選版分枝定界解法19ppt精選版最通常的松馳問(wèn)題是放棄變量的整數(shù)性要求后，（P）為線(xiàn)性規(guī)劃問(wèn)題。60ppt精選版最通常的松馳問(wèn)題是放棄變量的整數(shù)性要求后，（P）為線(xiàn)分枝定界法步驟一般求解對(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é)束。61ppt精選版分枝定界法步驟21ppt精選版若松馳問(wèn)題有最優(yōu)解，但其各分量不全是整數(shù)，則這個(gè)解不是原整數(shù)規(guī)劃的最優(yōu)解，轉(zhuǎn)下一步。從不滿(mǎn)足整數(shù)條件的基變量中任選一個(gè)xl進(jìn)行分枝，它必須滿(mǎn)足xl

[xl]或xl

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

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

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

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

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

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

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

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

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

1,x23整數(shù)用單純形法可解得相應(yīng)的（P4）的最優(yōu)解（0，3）Z=970ppt精選版（P1）兩個(gè)子問(wèn)題：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原問(wèn)題的最優(yōu)解（1，2）Z=1071ppt精選版X12X22X11X23P1:(1,例5-7用分枝定界法求解：MinZ=x1+4x2s.t.

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

0123456

87