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

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

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

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

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

托運限制2413問兩種貨物各裝運多少箱，可使獲得利潤最大？返回設(shè)甲、乙兩種貨物裝運箱數(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)是不是可通過把不考慮整數(shù)要求求得的最優(yōu)解經(jīng)過“化整”得到滿足整數(shù)要求的最優(yōu)解呢？容易求得相應(yīng)的線性規(guī)劃問題的最優(yōu)解為

x1=4.8，x2=0，maxz=96現(xiàn)在來分析上述線性規(guī)劃問題的最優(yōu)解是否是整數(shù)規(guī)劃問題的最優(yōu)解因為x1表示的是托運甲種貨物的箱數(shù)，目前得到的最優(yōu)解不是整數(shù)，所以不合條件⑤的要求。是不是可以把所得的非整數(shù)最優(yōu)解經(jīng)過“化整”就可得到合于條件⑤的整數(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)，這當然滿足各約束條件，因而是可行解，但不是最優(yōu)解，因為當x1=4，x2=0,時z=80；而當x1=4，x2=1(這也是可行解)時，z=90。

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

求解問題Aminz=-10x1-20x25x1+8x2≤60 x1≤8 x2≤4x1，x2≥0x1，x2整數(shù)例題演示問題A對應(yīng)的松弛問題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問題B的解為:z0=-136x1=5.6x2=4問題B2為:z1=-135x1=6.00x2=3.75問題B1為:z1=-130x1=5.00x2=4.00-136<=Z*<=-130-136<=Z*<=0-135<=Z*<=-130問題B21為:z1=-132x1=7.2x2=3.00問題B22為:無可行解x2≤3x2≥4問題B211為:z1=-130x1=7.00x2=3.00問題B212為:z1=-130x1=8.00x2=2.50x1≤7x1≥8-132<=Z*<=-130-130<=Z*<=-130分枝定界法一般步驟問題(B)無可行解，則(A)也無可行解，停止；

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

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

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

5x1+4x2≤24(1)

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

7x1+3x2≤45(2)

這兩個條件是互相排斥的。為了統(tǒng)一在一個問題中，引入0-1變量y，令含有互斥約束條件的問題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)式來代替：

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

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

其中M是充分大的數(shù)?？梢则炞C:當y=0時，(3)式就是(1)式，而(4)式自然成立，因而是多余的。當y=1時，(4)式就是(2)式，而(3)式是多余的。引入的變量y不必出現(xiàn)在目標函數(shù)內(nèi)，即認為在目標函數(shù)內(nèi)y的系數(shù)為0。

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

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

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

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

y1+y2+…+ym=m?

1(6)

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

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

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

例:用隱枚舉法求解下列0—1型整數(shù)規(guī)劃該條件稱為過濾條件解：先通過試探找一個可行解，所有可能的可行解約束條件可行解否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的順序使目標函數(shù)中xi的系數(shù)是遞增(不減)的，在上例中，改寫

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

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

有n項任務(wù)，恰好n個人承擔，第i人完成第j項任務(wù)的花費(時間或費用等)為cij，要求確定人和事之間的一一對應(yīng)的指派方案，使總花費最??？指派問題的標準形式及其數(shù)學(xué)模型

例4

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

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

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

標準指派問題是一種特殊的整數(shù)規(guī)劃問題，又是特殊的0-1規(guī)劃問題。

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

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

作法：系數(shù)矩陣各行元素減去所在行的最小元素，再從所得矩陣的各列減去所在列最小元素。(因一行中xij

取值一個1，其余為0，cij

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

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

求表中所示效率矩陣的指派問題的最小解。

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

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

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

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

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

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

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

作業(yè)：2.

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

3.

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

2x1+x2≤9③

x1，x2≥0④

x1，x2整數(shù)⑤

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

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

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

求解整數(shù)規(guī)劃問題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ù)條件⑤。這時z0是問題A的最優(yōu)目標函數(shù)值z*的上界，記作z0=。而在x1=0，x2=0時，顯然是問題A的一個整數(shù)可行解，這時z=0，是z*的一個下界，記作=0，即0≤z*≤356。分枝因為當前均為非整數(shù)，故不滿足整數(shù)要求，任選一個進行分枝。設(shè)選進行分枝，把可行集分成2個子集：因為4與5之間無整數(shù)，故這兩個子集內(nèi)的整數(shù)解必與原可行集合整數(shù)解一致。這一步稱為分枝。這兩個子集的規(guī)劃求解如下：問題B1為:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x1,x2≥0問題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顯然，仍沒有得到全部變量是整數(shù)的解。因z1＞z2，故將改為349，那么必存在最優(yōu)整數(shù)解，得到z*，并且

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

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

70x1≤4x2≥3x1≥

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

再定界：，并將B12剪枝。

340≤z*≤34971繼續(xù)對問題B2