最優(yōu)化理論-第3章-整數(shù)規(guī)劃

第3章整數(shù)規(guī)劃哈爾濱工程大學(xué)理學(xué)院戴運(yùn)桃Email:peach0040@126.com3.1整數(shù)規(guī)劃定義規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒(méi)有一種方法能有效地求解一切整數(shù)規(guī)劃。整數(shù)規(guī)劃的數(shù)學(xué)模型若要求所有xj

的解為整數(shù)，稱為純整數(shù)規(guī)劃若要求部分xj

的解為整數(shù)，稱為混合整數(shù)規(guī)劃對(duì)應(yīng)沒(méi)有整數(shù)解要求的線性規(guī)劃稱之為松弛問(wèn)題整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問(wèn)題的最優(yōu)解引例

某廠擬用火車裝運(yùn)甲、乙兩種貨物集裝箱，每箱的體積、重量、可獲利潤(rùn)以及裝運(yùn)所受限制如下：貨物集裝箱體積(米3)重量(百斤)利潤(rùn)(百元) 甲5220乙4510

托運(yùn)限制2413問(wèn)兩種貨物各裝運(yùn)多少箱，可使獲得利潤(rùn)最大？返回設(shè)甲、乙兩種貨物裝運(yùn)箱數(shù)分別為x1和x2。顯然，x1、x2都要求為整數(shù),于是可建立整數(shù)規(guī)劃模型如下：

Maxz＝20x1+10x2(1)5x1+4x2≤24(2)2x1+5x2≤13(3)

x1,x2≥0(4)

x1,x2為整數(shù)

(5)是不是可通過(guò)把不考慮整數(shù)要求求得的最優(yōu)解經(jīng)過(guò)“化整”得到滿足整數(shù)要求的最優(yōu)解呢？容易求得相應(yīng)的線性規(guī)劃問(wèn)題的最優(yōu)解為

x1=4.8，x2=0，maxz=96現(xiàn)在來(lái)分析上述線性規(guī)劃問(wèn)題的最優(yōu)解是否是整數(shù)規(guī)劃問(wèn)題的最優(yōu)解因?yàn)閤1表示的是托運(yùn)甲種貨物的箱數(shù)，目前得到的最優(yōu)解不是整數(shù)，所以不合條件⑤的要求。是不是可以把所得的非整數(shù)最優(yōu)解經(jīng)過(guò)“化整”就可得到合于條件⑤的整數(shù)最優(yōu)解呢?如將(x1=4.8，x2=0)湊整為(x1=5，x2=0)，這樣就破壞了條件②(關(guān)于體積的限制)，因而它不是可行解；如將(x1=4.8，x2=0)舍去尾數(shù)0.8，變?yōu)?x1=4，x2=0)，這當(dāng)然滿足各約束條件，因而是可行解，但不是最優(yōu)解，因?yàn)楫?dāng)x1=4，x2=0,時(shí)z=80；而當(dāng)x1=4，x2=1(這也是可行解)時(shí)，z=90。

圖中畫(+)號(hào)的點(diǎn)表示可行的整數(shù)解。湊整得到的(5，0)點(diǎn)不在可行域內(nèi)，而C點(diǎn)又不合于條件⑤。為了滿足題中要求，表示目標(biāo)函數(shù)的z的等值線必須向原點(diǎn)平行移動(dòng)，直到第一次遇到帶“+”號(hào)B點(diǎn)(x1=4，x2=1)為止。這樣，z的等值線就由z=96變到z=90，它們的差值為Δz=96-90=6，表示利潤(rùn)的降低，這是由于變量的不可分性(裝箱)所引起的。由上例看出，將其相應(yīng)的線性規(guī)劃的最優(yōu)解經(jīng)過(guò)“化整”來(lái)解原整數(shù)線性規(guī)劃，雖是最容易想到的，但常常得不到整數(shù)線性規(guī)劃的最優(yōu)解，甚至根本不是可行解。因此有必要對(duì)整數(shù)線性規(guī)劃的解法進(jìn)行專門研究。在求解整數(shù)線性規(guī)劃時(shí)，如果可行域是有界的，首先容易想到的方法就是窮舉所有可行的整數(shù)解，即列出圖中所有標(biāo)有“+”的整數(shù)點(diǎn)，然后比較它們的目標(biāo)函數(shù)值，從而確定最優(yōu)解。對(duì)于規(guī)模較小的問(wèn)題，變量個(gè)數(shù)很少，可行解的組合數(shù)也較小時(shí)，這個(gè)方法是可行的，也是有效的。如在例1中，變量只有x1和x2。由條件②，x1所能取的整數(shù)值為0、1、2、3、4共5個(gè)；由條件③，x2所能取的整數(shù)值為0、1、2共3個(gè)。因此所有可能的整數(shù)組合(不都是可行的)數(shù)是3×5=15個(gè)，窮舉法還是勉強(qiáng)可用的。對(duì)于大型問(wèn)題，可行的整數(shù)組合數(shù)會(huì)很大。例如在指派問(wèn)題中，將n項(xiàng)任務(wù)指派n個(gè)人去完成，不同的指派方案共有n!種，當(dāng)n=10時(shí)，可能的指派方案數(shù)超過(guò)300萬(wàn)；當(dāng)n=20，超過(guò)2×1018。顯然，窮舉法是不可取的。應(yīng)尋找僅檢查可行的整數(shù)組合的一部分，就能定出最優(yōu)的整數(shù)解的方法。分支定界解法就是其中之一。分枝定界法可用于解純整數(shù)或混合整數(shù)線性規(guī)劃問(wèn)題。20世紀(jì)60年代初由LandDoig和Dakin等提出，是解整數(shù)線性規(guī)劃的重要方法之一。分枝定界法繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解為止?；舅枷肜?/p>

求解問(wèn)題Aminz=-10x1-20x25x1+8x2≤60 x1≤8 x2≤4x1，x2≥0x1，x2整數(shù)例題演示問(wèn)題A對(duì)應(yīng)的松弛問(wèn)題Bminz=-10x1-20x25x1+8x2≤60 x1≤8 x2≤4x1，x2≥0B1minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≤5

分枝B2minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≥6

B21minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≥6

x2≤3分枝B22minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≥6

x2≥4

B211minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≥6

x2≤3x1≤7分枝B212minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≥6

x2≤3

x1≥8x1≤5x1≥6問(wèn)題B的解為:z0=-136x1=5.6x2=4問(wèn)題B2為:z1=-135x1=6.00x2=3.75問(wèn)題B1為:z1=-130x1=5.00x2=4.00-136<=Z*<=-130-136<=Z*<=0-135<=Z*<=-130問(wèn)題B21為:z1=-132x1=7.2x2=3.00問(wèn)題B22為:無(wú)可行解x2≤3x2≥4問(wèn)題B211為:z1=-130x1=7.00x2=3.00問(wèn)題B212為:z1=-130x1=8.00x2=2.50x1≤7x1≥8-132<=Z*<=-130-130<=Z*<=-130分枝定界法一般步驟問(wèn)題(B)無(wú)可行解，則(A)也無(wú)可行解，停止；

0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊形式，它的變量xj僅取值0或1。這種只能取0或1的變量稱為0-1變量或二進(jìn)制變量。3.20-1整數(shù)規(guī)劃

例：某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置Ai（i=1，2,…,7）可供選擇規(guī)定在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由A4，A5，兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由A6，A7，兩個(gè)點(diǎn)中至少選一個(gè)。如果選擇Ai點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤(rùn)ci元，但投資總額不能超過(guò)B元。問(wèn)應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大？則該問(wèn)題的數(shù)學(xué)模型為：

在整數(shù)規(guī)劃中，如果變量xi僅取0或1，這時(shí)變量xi稱為0—1變量，這時(shí)的整數(shù)規(guī)劃稱為0—1型整數(shù)規(guī)劃。28在本章開始的例1中，關(guān)于運(yùn)貨的體積限制為

5x1+4x2≤24(1)

今設(shè)運(yùn)貨有車運(yùn)和船運(yùn)兩種方式，上面的條件系用車運(yùn)時(shí)的限制條件，如用船運(yùn)時(shí)關(guān)于體積的限制條件為

7x1+3x2≤45(2)

這兩個(gè)條件是互相排斥的。為了統(tǒng)一在一個(gè)問(wèn)題中，引入0-1變量y，令含有互斥約束條件的問(wèn)題Maxz＝20x1+10x2(1)5x1+4x2≤24(2)2x1+5x2≤13(3)

x1,x2≥0(4)

x1,x2為整數(shù)(5)29

于是，(1)式和(2)式可由下述條件(3)式和(4)式來(lái)代替：

5x1+4x2≤24+yM(3)

7x1+3x2≤45+(1?y)M(4)

其中M是充分大的數(shù)。可以驗(yàn)證:當(dāng)y=0時(shí)，(3)式就是(1)式，而(4)式自然成立，因而是多余的。當(dāng)y=1時(shí)，(4)式就是(2)式，而(3)式是多余的。引入的變量y不必出現(xiàn)在目標(biāo)函數(shù)內(nèi)，即認(rèn)為在目標(biāo)函數(shù)內(nèi)y的系數(shù)為0。

30如果有m個(gè)互相排斥的約束條件(≤型)：αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m

為了保證這m個(gè)約束條件只有一個(gè)起作用，我們引入m個(gè)0-1變量yi(i=1,2,…，m)和一個(gè)充分大的常數(shù)M，且下面這一組m+1個(gè)約束條件

αi1x１+αi2x2+…+αinxn≤bi+yiM

i=1,2,…，m(5)

y1+y2+…+ym=m?

1(6)

就合乎上述的要求。這是因?yàn)?，由?6)式，m個(gè)yi中只有一個(gè)能取0值，設(shè)yi*=0，代入(5)式，就只有i=i*這個(gè)約束條件起作用，而別的式子都是多余的。

對(duì)于0-1型整數(shù)規(guī)劃，一般采用隱枚舉法，而不必采用完全枚舉法。包括:

(1)只要發(fā)現(xiàn)某個(gè)變量組合不滿足其中一個(gè)約束條件時(shí)，就不必再去檢驗(yàn)其他約束條件是否可行。(2)若已發(fā)現(xiàn)一個(gè)可行解，則可根據(jù)它的目標(biāo)函數(shù)值產(chǎn)生一個(gè)過(guò)濾條件，對(duì)于目標(biāo)函數(shù)值比它差的變量組合就不必再去檢驗(yàn)它的可行性；在以后的求解中每當(dāng)發(fā)現(xiàn)更好的可行解就替換原來(lái)的過(guò)濾條件。0-1型整數(shù)規(guī)劃的解法

例:用隱枚舉法求解下列0—1型整數(shù)規(guī)劃該條件稱為過(guò)濾條件解：先通過(guò)試探找一個(gè)可行解，所有可能的可行解約束條件可行解否Z值(0，0，0)(0，0，1)(0，1，0)(1，0，0)(0，1，1)(1，0，1)(1，1，0)(1，1，1)

0

5

-1

1

0

1

√

5

-2

3

1

1

1

0

√

5

3

1

5×

8

0

2

1

1

√

8

1

6

2

6

×所有可能的可行解約束條件可行解否Z值(0，0，0)(0，0，1)(0，1，0)(1，0，0)(0，1，1)(1，0，1)(1，1，0)(1，1，1)

0

√

5

-1

1

0

1

√

5

-2

3

3

8

0

2

1

1

√

8

1

6

0

0

0

0

0所有可能的可行解約束條件可行解否Z值(1，0，1)(1，1，1)(0，1，1)(1，0，0)(0，1，1)(1，1，0)(0，0，0)(0，1，0)

8

√

6

5

3

3

1

0

-2

0

2

1

1

836注意：一般常重新排列xi的順序使目標(biāo)函數(shù)中xi的系數(shù)是遞增(不減)的，在上例中，改寫

z=3x1?2x2+5x3=?2x2+3x1+5x3

因?yàn)?2，3，5是遞增的序，變量(x2，x1，x3)也按下述順序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)，…，這樣，最優(yōu)解容易比較早的發(fā)現(xiàn)。再結(jié)合過(guò)濾條件的改進(jìn)，更可使計(jì)算簡(jiǎn)化。37z=3x1?2x2+5x3=?2x2+3x1+5x3指派問(wèn)題指派問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型匈牙利解法求解指派問(wèn)題一般的指派問(wèn)題

有n項(xiàng)任務(wù)，恰好n個(gè)人承擔(dān)，第i人完成第j項(xiàng)任務(wù)的花費(fèi)(時(shí)間或費(fèi)用等)為cij，要求確定人和事之間的一一對(duì)應(yīng)的指派方案，使總花費(fèi)最?。恐概蓡?wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型

例4

有一份中文說(shuō)明書，需譯成英、日、德、俄四種文字。分別記作E、J、G、R?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說(shuō)明書翻譯成不同語(yǔ)種的說(shuō)明書所需時(shí)間如下表。問(wèn)應(yīng)指派何人去完成何工作，使所需總時(shí)間最少？指派問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型指派問(wèn)題的系數(shù)矩陣如下：Cij的含義可以不同，如費(fèi)用、成本、時(shí)間等。為建立標(biāo)準(zhǔn)指派問(wèn)題的數(shù)學(xué)模型，引入n×n個(gè)0-1變量：指派問(wèn)題的數(shù)學(xué)模型可寫成如下形式：若派第i人做第j事0若不派第i人做第j事

（ij=1，2,…，n）第j項(xiàng)工作由一個(gè)人做第i人做一項(xiàng)工作指派問(wèn)題的每個(gè)可行解，可用矩陣表示如下：矩陣X中，每行各元素中只有1個(gè)元素為1,其余各元素等0；每列各元素中也只有1個(gè)元素為1,其余各元素等0。指派問(wèn)題有n！個(gè)可行解。匈牙利法解題步驟

1955年，庫(kù)恩利用匈牙利數(shù)學(xué)家康尼格的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問(wèn)題的一種算法，稱為匈牙利解法。

標(biāo)準(zhǔn)指派問(wèn)題是一種特殊的整數(shù)規(guī)劃問(wèn)題，又是特殊的0-1規(guī)劃問(wèn)題。

匈牙利解法的關(guān)鍵是利用了指派問(wèn)題最優(yōu)解的如下性質(zhì)：若從指派問(wèn)題的系數(shù)矩陣C的某行（或某列）各元素分別減去該行（或列）的最小元素，得到一個(gè)新的矩陣C’，則以C’和C為系數(shù)矩陣的兩個(gè)指派問(wèn)題有相同的最優(yōu)解。

（系數(shù)矩陣的變化并不影響數(shù)學(xué)模型的約束方程組，而只是目標(biāo)函數(shù)值減少了常數(shù)k，所以最優(yōu)解不變）匈牙利法-2-4-9-7若某行(列)已有0元素，那就不必再減了。例1的計(jì)算為：1.使系數(shù)矩陣各行、各列出現(xiàn)零元素

作法：系數(shù)矩陣各行元素減去所在行的最小元素，再?gòu)乃镁仃嚨母髁袦p去所在列最小元素。(因一行中xij

取值一個(gè)1，其余為0，cij

同時(shí)減去一常數(shù)不影響xij取值)。匈牙利法解題步驟如下：-4-2

這就保證每行每列至少有一個(gè)0元素，同時(shí)不出現(xiàn)負(fù)元素。2.試求最優(yōu)解。作法：由獨(dú)立0元素的行（列）開始，獨(dú)立0元素處畫標(biāo)記，在有的行列中劃去其它0元素；再在剩余的0元素中重復(fù)此做法，直至不能標(biāo)記為止。（1）當(dāng)遇到在所有的行和列中，0元素都不止一個(gè)時(shí)（存在0元素的閉回路），可任選其中一個(gè)0元素加圈，同時(shí)劃去同行和同列中其他0元素。（2）如能找出n個(gè)位于不同行不同列的零元素，令對(duì)應(yīng)的xij=1，其余xij=0，得最優(yōu)解，結(jié)束；否則，看下面的例題轉(zhuǎn)第3步。例

求表中所示效率矩陣的指派問(wèn)題的最小解。

任務(wù)人ABCDE甲127979乙89666丙71712149丁15146610戊4107109經(jīng)行運(yùn)算即可得每行每列都有0元素的系數(shù)矩陣。

再按上述步驟運(yùn)算，得到：所畫0元素少于n，未得到最優(yōu)解。

3.作能覆蓋所有0元素的最少直線數(shù)的直線集合(1)對(duì)沒(méi)有的行打號(hào)；(2)對(duì)已打號(hào)的行中所有0元素的所在列打號(hào)；(3)再對(duì)打有號(hào)的列中0元素的所在行打號(hào)；(4)重復(fù)(2),(3)直到得不出新的打號(hào)的行(列)為止；(5)對(duì)沒(méi)有打號(hào)的行畫一橫線，對(duì)打號(hào)的列畫一縱線，這就得到覆蓋所有0元素的最少直線數(shù)

4.未被直線覆蓋的最小元素為cij0,在打號(hào)行中各元素都減去cij0,打號(hào)列中的各元素都加上cij0。Cij=2

解為5.返回步驟2，重復(fù)上述步驟。一般的指派問(wèn)題在實(shí)際應(yīng)用中，常會(huì)遇到各種非標(biāo)準(zhǔn)形式的指派問(wèn)題。通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利解法求解。最大化指派問(wèn)題設(shè)最大化指派問(wèn)題系數(shù)矩陣C中最大元素為m。令矩陣B=(bij)=(m-cij),則以B為系數(shù)矩陣的最小化指派問(wèn)題和以C為系數(shù)矩陣的原最大化指派問(wèn)題有相同的最優(yōu)解。人數(shù)和事數(shù)不等的指派問(wèn)題若人少事多，則添上一些虛擬的“人”。這些虛擬的人作各事的費(fèi)用系數(shù)可取0，理解為這些費(fèi)用實(shí)際上不會(huì)發(fā)生。若人多事少，則添上一些虛擬的“事”。這些虛擬的事被各人做的費(fèi)用系數(shù)同樣也取0。一個(gè)人可做幾件事的指派問(wèn)題若某個(gè)人可做幾件事，則可將該人看做相同的幾個(gè)人來(lái)接受指派。這幾個(gè)人作同一件事的費(fèi)用系數(shù)當(dāng)然都一樣。某事一定不能由某人作的指派問(wèn)題若某事一定不能由某個(gè)人做，則可將相應(yīng)的費(fèi)用系數(shù)取做足夠大的數(shù)M。例

：某大型工程有五個(gè)工程項(xiàng)目，決定向社會(huì)公開招標(biāo)，建設(shè)公司A1，A2，A3參加招標(biāo)承建，根據(jù)實(shí)際情況，可允許每家建設(shè)公司承建一項(xiàng)或二項(xiàng)工程。求使總費(fèi)用最少的指派方案。上面的系數(shù)矩陣有6行5列，為了使“人”和“事”的數(shù)目相同，引入一件虛擬的事B6，使之成為標(biāo)準(zhǔn)指派問(wèn)題的系數(shù)矩陣：解：由于每家建筑公司最多可以承建兩項(xiàng)，因此可把每家建筑公司看成兩家建筑公司，其系數(shù)矩陣為然后，用匈牙利解法求解。可得費(fèi)用最省為4+7+9+8+7=35（百萬(wàn)元）1.

用圖解法和單純形法求解線性規(guī)劃問(wèn)題

作業(yè)：2.

用單純形法求解線性規(guī)劃問(wèn)題

3.

求解整數(shù)規(guī)劃問(wèn)題maxz=3x1+2x2①2x1+3x2≤14②

2x1+x2≤9③

x1，x2≥0④

x1，x2整數(shù)⑤

4.設(shè)有A、B、C、D四人去完成甲、乙、丙、丁四項(xiàng)任務(wù)，不同的人完成不同的任務(wù)時(shí)間不同，資料如下，求總時(shí)間最小的分配方案。ABCD甲乙丙丁

5.設(shè)有A、B、C、D四人去完成甲、乙、丙、丁四項(xiàng)任務(wù)，不同的人完成不同的任務(wù)贏得不同，資料如下，求總贏得最大的分配方案。ABCD甲乙丙丁

6.設(shè)有A、B、C、D、E五人去完成甲、乙、丙、丁四項(xiàng)任務(wù)，每人完成各項(xiàng)工作如表所示。規(guī)定每項(xiàng)工作只能有一個(gè)人去完成，每人最多承擔(dān)一項(xiàng)工作，又假定D因某種原因決定不承擔(dān)丁項(xiàng)目，問(wèn)應(yīng)該如何分配，才能使4項(xiàng)工作總得花費(fèi)時(shí)間最少？ABCDE甲乙丙丁例

求解整數(shù)規(guī)劃問(wèn)題Amaxz=3x1+2x2①2x1+3x2≤

70

②2x1+x2≤70③x1，x2≥0④x1，x2整數(shù)⑤解：先不考慮條件⑤，即解相應(yīng)的線性規(guī)劃B,①～④(見圖，得最優(yōu)解x1=4.81，x2=1.82，z0=356

可見它不符合整數(shù)條件⑤。這時(shí)z0是問(wèn)題A的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上界，記作z0=。而在x1=0，x2=0時(shí)，顯然是問(wèn)題A的一個(gè)整數(shù)可行解，這時(shí)z=0，是z*的一個(gè)下界，記作=0，即0≤z*≤356。分枝因?yàn)楫?dāng)前均為非整數(shù)，故不滿足整數(shù)要求，任選一個(gè)進(jìn)行分枝。設(shè)選進(jìn)行分枝，把可行集分成2個(gè)子集：因?yàn)?與5之間無(wú)整數(shù)，故這兩個(gè)子集內(nèi)的整數(shù)解必與原可行集合整數(shù)解一致。這一步稱為分枝。這兩個(gè)子集的規(guī)劃求解如下：?jiǎn)栴}B1為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x1,x2≥0問(wèn)題B2為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≥5x1,x2≥

068

x1≤4，x1≥5B1:z1=349x1=4.00x2=2.10B2:z2=341x1=5.00x2=1.5769顯然，仍沒(méi)有得到全部變量是整數(shù)的解。因z1＞z2，故將改為349，那么必存在最優(yōu)整數(shù)解，得到z*，并且

0≤z*≤349繼續(xù)對(duì)問(wèn)題B1和B2進(jìn)行分解。因z1＞z2，故先分解B1為兩支。增加條件x2≤2，稱為問(wèn)題B11；增加條件x2≥3，稱為問(wèn)題B21。相當(dāng)于在圖中再去掉x2＞2與x2＜3之間的區(qū)域，進(jìn)行第二次迭代。問(wèn)題B11為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≤2x1,x2≥0問(wèn)題B12為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≥3x1≥

0z11=340x1=4.00x2=2.00z12=327x1=1.42x2=3.00對(duì)問(wèn)題B1再進(jìn)行分枝得問(wèn)題B11和B12，它們的最優(yōu)解為:

再定界：，并將B12剪枝。

340≤z*≤34971繼續(xù)對(duì)問(wèn)題B2