1、.第五章整數(shù)規(guī)劃§ 1 整數(shù)規(guī)劃的數(shù)學(xué)模型及特點(diǎn)要求一部分或全部決策變量必須取整數(shù)值得規(guī)劃問(wèn)題稱為整數(shù)規(guī)劃。其模型為：nMax( 或 min)z=c jx jj1naijxij(, )bii1,2,mj 1s.tx j0j1,2,nx1 , x2 ,xn中部分或全部取整數(shù)若要求決策變量只能取值0 或 1 的整數(shù)規(guī)劃稱為0-1 型整數(shù)線性規(guī)劃。§ 5 指派問(wèn)題一 指派問(wèn)題的標(biāo)準(zhǔn)形式及數(shù)學(xué)模型在現(xiàn)實(shí)生活中， 有各種性質(zhì)的指派問(wèn)題。 例如，有若干項(xiàng)工作需要分配給若干人（或部門）來(lái)完成； 有若干項(xiàng)合同需要選擇若干個(gè)投標(biāo)者來(lái)承包；有若干班級(jí)需要安排在各教室上課等等。 諸如此類的問(wèn)題，

2、它們的基本要求是在滿足特定的指派要求條件下，使指派方案的總體效果最佳。由于指派問(wèn)題的多樣性，有必要定義指派問(wèn)題的標(biāo)準(zhǔn)形式。指派問(wèn)題的標(biāo)準(zhǔn)形式（以人和事為例）是：有 n 個(gè)人和n 件事，已知第i 個(gè)人作第j件事的費(fèi)用為cij (i , j1,2,n) ，要求確定人和事之間的一一對(duì)應(yīng)的指派方案，是完成這n件事的總費(fèi)用最少。為了建立標(biāo)準(zhǔn)指派問(wèn)題的數(shù)學(xué)模型，引入n 2 個(gè) 0-1 變量：0 若不指派第 i 人作第 j 事xiji 人作第 j件事i ， j=1,2, n1 若指派第這樣，問(wèn)題的數(shù)學(xué)模型可寫成nnmin zcij xij（5.1 ）i 1j 1n（ 5.2）xij 1j 1,2,ni 1

3、ns.txij 1i1,2,n（5.3）j 1xij0,1i , j1,2,n（ 5.4）其中，（ 5.1）表示每件事必優(yōu)且只有一個(gè)人去做，（ 5.2）表示每個(gè)人必做且只做一件事。注：1指派問(wèn)題是產(chǎn)量（ai ）、銷量（ b j ）相等，且ai =b j =1，i ， j=1,2,n 的運(yùn)輸;.問(wèn)題。 有時(shí)也稱 cij 為第 i個(gè)人完成第 j 件工作所需的資源數(shù)，稱之為 效率系數(shù) （或價(jià)值系2數(shù)）。并稱矩陣c11c12c1nC=(cij ) n n =c21c22c2n（5.5 ）cn1cn 2cnn為效率矩陣（或價(jià)值系數(shù)矩陣）。并稱決策變量 xij 排成的 n×n 矩陣x11x12x

4、1 nX= (xij ) nn =x21x22x2 n（ 5.6）xn1xn 2xnn為決策變量矩陣 。(5.6) 的特征是它有n 個(gè) 1，其它都是 0。這 n 個(gè) 1 位于不同行、不同列。每一種情況為指派問(wèn)題的一個(gè)可行解。共n!個(gè)解。其總的費(fèi)用 z =C X這里的 表示兩矩陣對(duì)應(yīng)元素的積，然后相加。問(wèn)題是： 把這 n 個(gè) 1 放到 X 的 n2 個(gè)位置的什么地方可使耗費(fèi)的總資源最少？（解最優(yōu)）例 1已知效率矩陣50202300C=56704800則01000100X（1）= 0 00 1 ，X（2）=00101000100000100001都是指派問(wèn)題的最優(yōu)解例 12/P-149 ：某商業(yè)公

5、司計(jì)劃開(kāi)辦五家新商店。為了盡早建成營(yíng)業(yè)，商業(yè)公司決定由5 家建筑公司分別承建。已知建筑公司Ai （ i=1 ， 2， 5）對(duì)新商店Bj （ 1，2， 5）的建造費(fèi)用的報(bào)價(jià)（萬(wàn)元）為cij （ i ， j=1,2,5） , 見(jiàn)表 5-9 。商業(yè)公司應(yīng)當(dāng)對(duì)5 家建筑公司怎樣分派建筑任務(wù)，才能使總的建筑費(fèi)用最少？表 5-9;.cijB 1B2B 3B4B5A 14871512A 279171410A 3691287A 46714610A 56912106解：這是一標(biāo)準(zhǔn)的指派問(wèn)題。若設(shè)1當(dāng) A i 承建 Bj 時(shí)xij =當(dāng) A i 不承建 B j 時(shí)00-1 變量i,j=1,2,5則問(wèn)題的數(shù)學(xué)模型為

6、Min z=4 x11 +8 x12 +10 x54 +6 x555xij1j1,2,5i 15s.txij1i1,2,5j1xij0,1i , j1,2,5若看成運(yùn)輸問(wèn)題，且xij 如上所述，則表5-9 為商 B 1B2B3B4B 5任務(wù)店公司A 1（ 4）（8） （7）（ 15） （ 12）1x11x12x13x14x15A 2（ 7）(9)(17)(14)(10)1x21x22x23x24x25A 3(6)(9)(12)(8)(7)1x31x32x33x34x35A 4(6)(7)(14)(6)(10)1x41x42x43x44x45A 5(6)(9)(12)(10)(6)1x51x52

7、x53x54x55;.所選的公司數(shù)111115當(dāng)然，第一行的 1 應(yīng)放在（ 1， 1）位置，此位置同時(shí)是第一列的費(fèi)用最小。但一般情況下沒(méi)有這么好。需找一適合一般的方法。二 匈牙利解法原理：雖然指派問(wèn)題是一類特殊的整數(shù)規(guī)劃問(wèn)題，又是特殊的 0-1 規(guī)劃問(wèn)題和特殊的運(yùn)輸問(wèn)題，因此， 它可以用多種相應(yīng)的解法來(lái)求解。 但是，這些解法都沒(méi)有充分利用指派問(wèn)題的特殊性質(zhì)，有效地減少計(jì)算量。 1955 年，庫(kù)恩（ W.W.Kuhn ）提出了匈牙利法。定理 1：設(shè)指派問(wèn)題的效率矩陣為C= (cij ) n n ，若將該矩陣的某一行 （或某一列）的各個(gè)元素都減去統(tǒng)一常數(shù)t（ t 可正可負(fù)），得到新的效率矩陣C(c

8、ij ) n n ，則以 C 為效率矩陣的新的指派問(wèn)題與原指派問(wèn)題的最優(yōu)解相同。但其最優(yōu)解比原最優(yōu)解之減少t.證明： 設(shè)式（ 5.1 ）（ 5.4 ）為原指派問(wèn)題?，F(xiàn)在C矩陣的第 k 行個(gè)元素東減去同一常數(shù) t, 記新的指派問(wèn)題的目標(biāo)函數(shù)為Z .則有nnnnnnnnZ =cij xij=cijxij +cij xij =cij xij+(ckjt) xkji 1j 1i 1j 1j 1i 1j 1j 1i ki knnnnnn=cij xij+ckjxkj -txkj=cij xij-t · 1=Z-ti 1j 1j 1j 1i 1j 1i k因此有MinZ =min(Z-t)=mi

9、nZ-t而新問(wèn)題的約束方程同原指派問(wèn)題。因此其最優(yōu)解比相同，而最優(yōu)解差一個(gè)常數(shù)。推論：若將指派問(wèn)題的效率矩陣每一行即每一列分別減去各行及各列的最小元素，則得到新指派問(wèn)題與原指派問(wèn)題有相同的最優(yōu)解。證明： 結(jié)論是顯然的。只要反復(fù)運(yùn)用定理1 便可得證。當(dāng)將效率矩陣的每一行都減去各行的最小元素，將所得的矩陣的每一列在減去當(dāng)前列中最小元素，則最后得到新效率矩陣C中必然出現(xiàn)一些零元素。設(shè)c ij，從第i行來(lái)看，它=0表示第 i 個(gè)人去干第 j項(xiàng)工作效率（相對(duì)）最好。而從第j列來(lái)看， 這個(gè) 0表示第 j項(xiàng)工作以第 i 人來(lái)干效率 ( 相對(duì) ) 最高。定義 ：在效率矩陣C 中，有一組在不同行不同列的零元素，

10、稱為獨(dú)立零元素組，此時(shí)每個(gè)元素稱為獨(dú)立零元素。例2: 已知50202300C=56704800則 c12 =0， c24=0， c31=0， c43 =0是一個(gè)獨(dú)立零元素組，c12 =0， c24 =0， c31 =0 ，c43 =0 分別稱為獨(dú)立零元素。 c12 =0， c23 =0， c31 =0， c44 =0也是一個(gè)獨(dú)立零元素組，而;. c14 =0， c23 =0 ， c31 =0， c44 =0就不是一個(gè)獨(dú)立零元素組，因?yàn)閏14 =0 與 c44 =0 這兩個(gè)零元素位于同一列中。根據(jù)以上對(duì)效率矩陣中零元素的分析，對(duì)效率矩陣C 中出現(xiàn)的的獨(dú)立零元素組中零元素所處的位置，在決策變量矩陣

11、中令相應(yīng)的xij =1，其余的 xij =0。就可找到指派問(wèn)題的一個(gè)最優(yōu)解。就上例中0100X （1）= 0001，10000010就是一個(gè)最優(yōu)解。同理0100X=0010（2）10000001也是一個(gè)最優(yōu)解。但是在有的問(wèn)題中發(fā)現(xiàn)效率矩陣 C 中獨(dú)立零元素的個(gè)數(shù)不夠 n 個(gè)，這樣就無(wú)法求出最優(yōu)指派方案，需作進(jìn)一步的分析。首先給出下述定理。定理 2 效率矩陣 C 中獨(dú)立零元素的最多個(gè)數(shù)等于能覆蓋所有零元素的最少直線數(shù)。我們不證它，說(shuō)一下意思：例 3：已知矩陣502502027020203000430002302072， C3=0335C1=56，C2=0550780046800448040636

12、5041430分別用最少直線去覆蓋各自矩陣中的零元素：50205020270202230004300023000 5 572，C3=0335C1 =56， C2=07480046800448000636504143可見(jiàn)， C1 最少需要4 條線， C2最少需要4 條線， C3最少需要 5 條線，方能劃掉矩陣中所有的零。即它們獨(dú)立零元素組中零元素最多分別為4， 4，5。三 匈牙利法求解步驟：;.我們以例題來(lái)說(shuō)明指派問(wèn)題如何求解：例 4 給定效率矩陣2151341041415C=914161378119求解該指派問(wèn)題。解： ）變換效率矩陣，將各行各列都減去當(dāng)前各行、各列中最小元素。min21513

13、41041415C=9141613781192013112013704行變換列變換60101160690574053= C92701420100Min0042這樣得到的新矩陣C 中，每行每列都必然出現(xiàn)零元素。）用圈 0 法求出新矩陣C 中獨(dú)立零元素。（ 1）進(jìn)行行檢驗(yàn)對(duì) C 進(jìn)行逐行檢驗(yàn)，對(duì)每行只有一個(gè)未標(biāo)記的零元素時(shí)，用記號(hào)將該零元素圈起。然后將被圈起的零元素所在的列的其它未標(biāo)記的零元素用記號(hào)×劃去。如C 中第 2 行、第3 行都只有一個(gè)未標(biāo)記的零元素，用分別將它們?nèi)ζ?。然后?#215;劃去第1 列其它未被標(biāo)記的零元素（第2 列沒(méi)有），見(jiàn) C013706069C= C053201

14、00在第 i 行只有一個(gè)零元素cij =0 時(shí)，表示第i 人干第 j 件工作效率最好。因此優(yōu)先指派第 i 人干第 j 項(xiàng)工作， 而劃去第 j 列其它未標(biāo)記的零元素， 表示第 j 項(xiàng)工作不再指派其它人去干（即使其它人干該項(xiàng)工作也相對(duì)有最好的效率）。重復(fù)行檢驗(yàn)， 直到每一行都沒(méi)有未被標(biāo)記的零元素或至少有兩個(gè)未被標(biāo)記的零元素時(shí)為止。本題 C 中第 1 行此時(shí)也只有1 個(gè)未被標(biāo)記的零元素。因此圈起C 中第 1 行第 4 列的零元素 c14 ，然后用×劃去第4 列中未被標(biāo)記的零元素。這是第4 行也只有一個(gè)未被標(biāo)記的零元素 c43 ，再用圈起，見(jiàn)C;.013706069C= C05320100（

15、2）進(jìn)行列檢驗(yàn)與進(jìn)行行檢驗(yàn)相似，對(duì)進(jìn)行了行檢驗(yàn)的矩陣逐列進(jìn)行檢驗(yàn)，對(duì)每列只有一個(gè)未被標(biāo)記的零元素， 用記號(hào)將該元素圈起， 然后技改元素所在行的其他未被標(biāo)記的零元素打×。 重復(fù)上述列檢驗(yàn)，直到每一列都沒(méi)有未被標(biāo)記的零元素或有兩個(gè)未被標(biāo)記的零元素為止。這時(shí)可能出現(xiàn)以下三種情況： 每一行均有圈0 出現(xiàn)，圈 0 的個(gè)數(shù) m恰好等于 n, 即 m=n.1 存在未標(biāo)記的零元素，但他們所在的行和列中，為標(biāo)記過(guò)的零元素均至少有兩個(gè)。2 不存在未被標(biāo)記過(guò)的零元素，當(dāng)圈0 的個(gè)數(shù) m< n.3) 進(jìn)行試指派0 為止的決策變量取值為1，其他決策變量取值若情況 出現(xiàn)，則可進(jìn)行試指派：令圈1均為零，得到

16、一個(gè)最優(yōu)指派方案，停止計(jì)算。上例中得到 C后，出現(xiàn)了情況 1 ，可令 x14 =1， x22 =1， x31=1 ， x43 =1，其余 xij =0。即為最優(yōu)指派。若情況2 出現(xiàn)，則在對(duì)每行、每列的其它未被標(biāo)記的零元素任選一個(gè)，加上標(biāo)記，即圈上該零元素。然后給同行、同列的其它未被標(biāo)記的零元素加標(biāo)記×。然后再進(jìn)行行、列檢驗(yàn)，可能出現(xiàn)情況1 或3 ，出現(xiàn)情況1 則由上述得到一最優(yōu)指派，停止計(jì)算。若情況3 出現(xiàn)，則要轉(zhuǎn)入下一步。 ）：做最少直線覆蓋當(dāng)前所有零元素。我們還以例12 來(lái)說(shuō)明過(guò)程：已知例 12 指派問(wèn)題的系數(shù)矩陣為：487151279171410C691287671481069

17、12106先對(duì)各行元素分別減去本行的最小元素，然后對(duì)各列也如此，即043118030118行變換021073列變換01773C= C0 3 6210232101804005040364002340此時(shí)， C 中各行各列都已出現(xiàn)零元素。為了確定 C 中的獨(dú)立零元素，對(duì)C 加圈，即;.03011801773C = 023210050402340由于只有4 個(gè)獨(dú)立零元素，少于系數(shù)矩陣階數(shù)n=5, 不能進(jìn)行指派，為了增加獨(dú)立零元素的個(gè)數(shù)，需要對(duì)矩陣作進(jìn)一步的變換，變換步驟如下：（ 1）對(duì) C 中所有不含圈0 元素的行打 ，如第 3 行。（ 2）對(duì)打 的行中，所有零元素所在的列打，如第1 列。（ 3）對(duì)

18、所有打列中圈0 元素所在行打，如第2 行。（ 4）重復(fù)上述（ 2），（ 3）步，直到不能進(jìn)一步打?yàn)橹埂＃?5）對(duì)未打的每一行劃一直線，如第1，3， 5 行。對(duì)已打的每一列劃一縱線，如第 1 列，既得到覆蓋當(dāng)前0 元素的最少直線數(shù)。見(jiàn)C。0301180301180177301773C=0232102321=C00504005040234002340）：對(duì)矩陣 C作進(jìn)一步變換，以增加0 元素。在未被直線覆蓋過(guò)的元素中找最小元素，將打行的各元素減去這個(gè)最小元素，將打裂的各元素加上這個(gè)最小元素（以避免打行中出現(xiàn)負(fù)元素） ，這樣就增加了零元素的個(gè)數(shù)。如 C中未被直線覆蓋過(guò)的元素中，最小元素為 c21 =

19、c35 =1，對(duì)打的第2，3 行各元素都減去2，對(duì)打的第1 列各元素都加上1，得到矩陣 C。03011 81301181066200662C1121001 210=C00504105040234012340）：回到步驟） ，對(duì)已增加了零元素的矩陣，再用圈0 法找出獨(dú)立零元素組 = 012101050412340C中已有 5 個(gè)獨(dú)立零元素，故可確定指派問(wèn)題的最優(yōu)方案。本例的最優(yōu)解為;.0010001000X*= 100000001000001也就是說(shuō)，最優(yōu)指派方案是：讓A 1承建B 3A 2B2A 3B1A 4B4A 5B5這樣按排能使總的建造費(fèi)最少，為z=79 6 6

20、6=34（萬(wàn)元）四 一般的指派問(wèn)題在實(shí)際應(yīng)用中，常會(huì)遇到非標(biāo)準(zhǔn)形式，解決的思路是：先化成標(biāo)準(zhǔn)形式，然后再用匈牙利法求解。1 最大化的指派問(wèn)題其一般形式為nnmax zcij xiji 1j 1nxij1j1,2,ni1s.tnxij1i1,2,nj1xij0,1i, j1,2,n處理辦法：設(shè)最大化的指派問(wèn)題的系數(shù)矩陣為C= (cij )n n ， m=max c11 , c12 , cnn , 令B=(Bij )n n =(m cij ) n n ，則以 B 為系數(shù)矩陣的最小化指派問(wèn)題和以C 為系數(shù)矩陣的原最大化指派問(wèn)題有相同的最優(yōu)解。例 5：某工廠有 4 名工人 A 1， A 2，A 3，

21、A 4，分別操作 4 臺(tái)車床 B1， B 2， B3， B 4。每小時(shí)單產(chǎn)量如下表，求產(chǎn)值最大的分配方案。車床B 1B2B3B4工人A 110987A 23456A 32112A 44356;.10987解： C= (cij ) n n =3456， m=max 10,9,8,7,5,6 =10,21124356012301230013B=(Bij )n n =(10cij ) n n =76543210310089980110000=0675423102200= BB 中的數(shù) =n=4,所以10000001（5。 7）X=10000010即為最優(yōu)解。從而產(chǎn)值最大的分配方案也為（5.7 ），最

22、大產(chǎn)值為Z=10 6 1 5=222 人數(shù)和事數(shù)不等的指派問(wèn)題。1 若人數(shù) < 事數(shù)，添一些虛擬的 “人”，此時(shí)這些虛擬的 “人” 做各件事的費(fèi)用系數(shù)取為 0，理解為這些費(fèi)用實(shí)際上不會(huì)發(fā)生。2 若人數(shù) > 事數(shù)，添一些虛擬的“事” ，此時(shí)這些虛擬的“事”被各個(gè)人做的費(fèi)用系數(shù)同樣也取為 0。例 6：現(xiàn)有 4 個(gè)人， 5 件工作。每人做每件工作所耗時(shí)間如下表：工作B1B2B3B4B5工人A10114281A7111014122A56912143A1315111074問(wèn)指派那個(gè)人去完成哪項(xiàng)工作，可是總消耗最??？解：添加虛擬人A5，構(gòu)造標(biāo)準(zhǔn)耗時(shí)陣：;.1011428892067111014

23、12行變換04375C= 569121401479= C13 1511107684300000000000所圈 0 數(shù) =4< 5=n,下找最少覆蓋0 的直線。8920604375C = 014796843000000從未劃去的元素中找最小者： 4，3，7， 5， 1，4，7， 9 =1。未劃去的行減去此最小者 1，劃去的列加上次最小者 1，得 C 。9920603264C = 003687843010000個(gè)數(shù) =n,從而的一最優(yōu)指派：0001010000X=010000000100100從而最少耗時(shí)為z=2 7 67=223. 一個(gè)人可做幾件事的指派問(wèn)題。若某人可作幾件事，則可將該人

24、化作相同的幾個(gè)“人”來(lái)接受指派。這幾個(gè)“人”做同一件事的費(fèi)用系數(shù)當(dāng)然一樣。例 6：對(duì)例 12 的指派問(wèn)題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司 A 4 和 A 5，讓技術(shù)力量較強(qiáng)的建筑公司 A 1、A 2、A 3 來(lái)承建。根據(jù)實(shí)際情況，可以允許每家建筑公司承建一家或兩家商店。求使總費(fèi)用最少的指派方案。解：反映投標(biāo)費(fèi)用的系數(shù)矩陣為：B1B2B3B4B54871512A179171410A2691287A3由于每家建筑公司最多可承建兩家新商店，因此，把每家建筑公司化作相同的兩家建筑公司（ Ai 和 Ai ， i=1 ， 2，3）。這樣，系數(shù)矩陣變?yōu)椋築1B2B3B4B5;.487151248

25、71512791714107917141069121276912127上面的系數(shù)矩陣有 6 行 5 列，為了使“人”和“事”的數(shù)目相同，引入一件虛擬事，使之成為標(biāo)準(zhǔn)的指派問(wèn)題，其系數(shù)矩陣為：BB2B3BB5B1464871512048715120C=79171410079171410069128706912870000750000750列變換3110630= CC3110630215000215000C 的數(shù) =5< 6=n, 下找 0 元素的最少直線覆蓋。000750000750C=3110630-13110630 -1215000215000000751000751209520= C

26、209520215001215001從而得一最優(yōu)指派：001000承建100000公司商店010000A1B 1X =00001B 30000010A2B 2000100B 6= B 4A3B 5;.總費(fèi)用為z=7 4 9 7 8=35( 萬(wàn)元 )4某事不能由某人去做的指派問(wèn)題某事不能由某人去做，可將此人做此時(shí)的費(fèi)用取作足夠大的M 。例 7：分配甲、乙、丙、丁四個(gè)人去完成 A 、 B、 C、 D、 E 五項(xiàng)任務(wù)，每人完成各項(xiàng)任務(wù)的時(shí)間如下表。由于任務(wù)重，人數(shù)少，考慮：a). 任務(wù) E 必須完成，其它4 項(xiàng)任務(wù)可選3 項(xiàng)完成。但甲不能做A 項(xiàng)工作。b) 其中有一人完成兩項(xiàng)，其他人每人完成一項(xiàng)。試

27、分別確定最優(yōu)分配方案，使完成任務(wù)的總時(shí)間最少。任務(wù)ABCDE人甲2529314237乙3938262033丙3427284032丁2442362345解：這是一人數(shù)與工作不等的指派問(wèn)題，若用匈牙利法求解，需作一下處理。a) 由于任務(wù)數(shù)大于人數(shù)，所以需要有一個(gè)虛擬的人，設(shè)為戊。因?yàn)楣ぷ鱁 必須完成，故設(shè)戊完成 E 的時(shí)間為 M （ M 為非常大的數(shù)） ，即戊不能做工作E，其余的假想時(shí)間為 0，建立的效率矩陣表如下：任ABCDE務(wù)人甲M29314237乙3938262033丙3427284032丁2442362345戊0000M用匈牙利法求解過(guò)程如下：M29314237M021383938262033 行變換19186013 列變換C=34272840327011352442362345119130220000M0000MM021331918608701130119130170000M由于數(shù) =4<5=階數(shù)，下找最少覆蓋0 的直線;.M021331918608C =