1、第五章 整數(shù)規(guī)劃§1 整數(shù)規(guī)劃的數(shù)學(xué)模型及特點要求一部分或全部決策變量必須取整數(shù)值得規(guī)劃問題稱為整數(shù)規(guī)劃。其模型為： Max(或min)z=中部分或全部取整數(shù) s.t若要求決策變量只能取值0或1的整數(shù)規(guī)劃稱為0-1型整數(shù)線性規(guī)劃。 §5 指 派 問 題一 指派問題的標(biāo)準(zhǔn)形式及數(shù)學(xué)模型在現(xiàn)實生活中，有各種性質(zhì)的指派問題。例如，有若干項工作需要分配給若干人（或部門）來完成；有若干項合同需要選擇若干個投標(biāo)者來承包；有若干班級需要安排在各教室上課等等。諸如此類的問題，它們的基本要求是在滿足特定的指派要求條件下，使指派方案的總體效果最佳。由于指派問題的多樣性，有必要定義指派問題的標(biāo)準(zhǔn)

2、形式。指派問題的標(biāo)準(zhǔn)形式（以人和事為例）是：有n個人和n件事，已知第i個人作第j件事的費用為，要求確定人和事之間的一一對應(yīng)的指派方案，是完成這n件事的總費用最少。為了建立標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型，引入個0-1變量：若指派第i人作第j件事若不指派第i人作第j事i，j=1,2,n 這樣，問題的數(shù)學(xué)模型可寫成 （5.1）（5.4）（5.2） s.t （5.3）其中，（5.1）表示每件事必優(yōu)且只有一個人去做，（5.2）表示每個人必做且只做一件事。注： 指派問題是產(chǎn)量（）、銷量（）相等，且=1，i，j=1,2,n的運輸問題。 有時也稱為第i個人完成第j件工作所需的資源數(shù)，稱之為效率系數(shù)（或價值系數(shù)）。并稱

3、矩陣 C= = （5.5）為效率矩陣（或價值系數(shù)矩陣）。并稱決策變量排成的n×n矩陣X= （5.6）為決策變量矩陣。(5.6)的特征是它有n個1，其它都是0。這n個1位于不同行、不同列。每一種情況為指派問題的一個可行解。共n!個解。其總的費用 z =CX 這里的表示兩矩陣對應(yīng)元素的積，然后相加。問題是：把這n個1放到X的個位置的什么地方可使耗費的總資源最少？（解最優(yōu)）例1 已知效率矩陣 C= 則 X（1）= ， X（2）= 都是指派問題的最優(yōu)解例12/P-149：某商業(yè)公司計劃開辦五家新商店。為了盡早建成營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知建筑公司Ai（i=1，2，5）對新

4、商店Bj（1，2，5）的建造費用的報價（萬元）為（i，j=1,2,5）,見表5-9。商業(yè)公司應(yīng)當(dāng)對5家建筑公司怎樣分派建筑任務(wù)，才能使總的建筑費用最少？表5-9B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106解：這是一標(biāo)準(zhǔn)的指派問題。若設(shè)0-1變量i,j=1,2,5當(dāng)Ai不承建Bj時當(dāng)Ai承建Bj時=則問題的數(shù)學(xué)模型為 Min z=4+8+10+6 s.t 若看成運輸問題，且如上所述，則表5-9為商店公司B1B2B3B4B5任務(wù)A1（4）（8）（7）（15）（12）1A2（7）(9)(17)(14)(10)1A3(6)(9)(12)

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

6、新的效率矩陣，則以為效率矩陣的新的指派問題與原指派問題的最優(yōu)解相同。但其最優(yōu)解比原最優(yōu)解之減少t.證明：設(shè)式（5.1）（5.4）為原指派問題。現(xiàn)在C矩陣的第k行個元素東減去同一常數(shù)t,記新的指派問題的目標(biāo)函數(shù)為.則有=+=+ =+-t=-t·1=Z-t因此有 Min =min(Z-t)=minZ-t而新問題的約束方程同原指派問題。因此其最優(yōu)解比相同，而最優(yōu)解差一個常數(shù)。推論：若將指派問題的效率矩陣每一行即每一列分別減去各行及各列的最小元素，則得到新指派問題與原指派問題有相同的最優(yōu)解。證明：結(jié)論是顯然的。只要反復(fù)運用定理1便可得證。當(dāng)將效率矩陣的每一行都減去各行的最小元素，將所得的矩陣

7、的每一列在減去當(dāng)前列中最小元素，則最后得到新效率矩陣中必然出現(xiàn)一些零元素。設(shè)=0，從第i行來看，它表示第i個人去干第j項工作效率（相對）最好。而從第j列來看，這個0表示第j項工作以第i人來干效率(相對)最高。定義：在效率矩陣C中，有一組在不同行不同列的零元素，稱為獨立零元素組，此時每個元素稱為獨立零元素。例2: 已知 C= 則=0，=0，=0，=0是一個獨立零元素組，=0，=0，=0，=0分別稱為獨立零元素。=0，=0，=0，=0也是一個獨立零元素組，而=0，=0，=0，=0就不是一個獨立零元素組，因為=0與=0這兩個零元素位于同一列中。根據(jù)以上對效率矩陣中零元素的分析，對效率矩陣C中出現(xiàn)的的

8、獨立零元素組中零元素所處的位置，在決策變量矩陣中令相應(yīng)的=1，其余的=0。就可找到指派問題的一個最優(yōu)解。就上例中 X（1）= ，就是一個最優(yōu)解。同理 X（2）= 也是一個最優(yōu)解。但是在有的問題中發(fā)現(xiàn)效率矩陣C中獨立零元素的個數(shù)不夠n個，這樣就無法求出最優(yōu)指派方案，需作進一步的分析。首先給出下述定理。定理2 效率矩陣C中獨立零元素的最多個數(shù)等于能覆蓋所有零元素的最少直線數(shù)。我們不證它，說一下意思：例3：已知矩陣C1= ，C2= ，C3= 分別用最少直線去覆蓋各自矩陣中的零元素：C1= ， C2= ， C3= 可見，C1最少需要4條線，C2最少需要4條線，C3最少需要5條線，方能劃掉矩陣中所有的零

9、。即它們獨立零元素組中零元素最多分別為4，4，5。三 匈牙利法求解步驟：我們以例題來說明指派問題如何求解：例4 給定效率矩陣 C= 求解該指派問題。解：）變換效率矩陣，將各行各列都減去當(dāng)前各行、各列中最小元素。min 列變換行變換7942C= = Min 0 0 4 2這樣得到的新矩陣中，每行每列都必然出現(xiàn)零元素。）用圈0法求出新矩陣中獨立零元素。（1）進行行檢驗對進行逐行檢驗，對每行只有一個未標(biāo)記的零元素時，用記號將該零元素圈起。然后將被圈起的零元素所在的列的其它未標(biāo)記的零元素用記號×劃去。如中第2行、第3行都只有一個未標(biāo)記的零元素，用分別將它們?nèi)ζ稹Ｈ缓笥?#215;劃去第1列其

10、它未被標(biāo)記的零元素（第2列沒有），見 =在第i行只有一個零元素=0時，表示第i人干第j件工作效率最好。因此優(yōu)先指派第i人干第j項工作，而劃去第j列其它未標(biāo)記的零元素，表示第j項工作不再指派其它人去干（即使其它人干該項工作也相對有最好的效率）。重復(fù)行檢驗，直到每一行都沒有未被標(biāo)記的零元素或至少有兩個未被標(biāo)記的零元素時為止。本題中第1行此時也只有1個未被標(biāo)記的零元素。因此圈起中第1行第4列的零元素，然后用×劃去第4列中未被標(biāo)記的零元素。這是第4行也只有一個未被標(biāo)記的零元素，再用圈起，見 =（2）進行列檢驗 與進行行檢驗相似，對進行了行檢驗的矩陣逐列進行檢驗，對每列只有一個未被標(biāo)記的零元素

11、，用記號將該元素圈起，然后技改元素所在行的其他未被標(biāo)記的零元素打×。重復(fù)上述列檢驗，直到每一列都沒有未被標(biāo)記的零元素或有兩個未被標(biāo)記的零元素為止。這時可能出現(xiàn)以下三種情況：每一行均有圈0出現(xiàn)，圈0的個數(shù)m恰好等于n,即m=n.存在未標(biāo)記的零元素，但他們所在的行和列中，為標(biāo)記過的零元素均至少有兩個。不存在未被標(biāo)記過的零元素，當(dāng)圈0的個數(shù)m< n.) 進行試指派若情況出現(xiàn)，則可進行試指派：令圈0為止的決策變量取值為1，其他決策變量取值均為零，得到一個最優(yōu)指派方案，停止計算。上例中得到后，出現(xiàn)了情況，可令=1，=1，=1，=1，其余=0。即為最優(yōu)指派。若情況出現(xiàn)，則在對每行、每列的其

12、它未被標(biāo)記的零元素任選一個，加上標(biāo)記，即圈上該零元素。然后給同行、同列的其它未被標(biāo)記的零元素加標(biāo)記×。然后再進行行、列檢驗，可能出現(xiàn)情況或，出現(xiàn)情況則由上述得到一最優(yōu)指派，停止計算。若情況出現(xiàn)，則要轉(zhuǎn)入下一步。）：做最少直線覆蓋當(dāng)前所有零元素。我們還以例12來說明過程：已知例12指派問題的系數(shù)矩陣為： 先對各行元素分別減去本行的最小元素，然后對各列也如此，即列變換行變換C =此時，中各行各列都已出現(xiàn)零元素。 為了確定中的獨立零元素，對加圈，即=由于只有4個獨立零元素，少于系數(shù)矩陣階數(shù)n=5,不能進行指派，為了增加獨立零元素的個數(shù)，需要對矩陣作進一步的變換，變換步驟如下：（1）對中所有

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

14、得到矩陣。 =）：回到步驟），對已增加了零元素的矩陣，再用圈0法找出獨立零元素組。=中已有5個獨立零元素，故可確定指派問題的最優(yōu)方案。本例的最優(yōu)解為承建X*=也就是說，最優(yōu)指派方案是：讓A1 B3 A2 B2 A3 B1 A4 B4 A5 B5這樣按排能使總的建造費最少，為 z=79666=34（萬元）四 一般的指派問題在實際應(yīng)用中，常會遇到非標(biāo)準(zhǔn)形式，解決的思路是：先化成標(biāo)準(zhǔn)形式，然后再用匈牙利法求解。1 最大化的指派問題其一般形式為 s.t 處理辦法：設(shè)最大化的指派問題的系數(shù)矩陣為C=，m=max,令B=，則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)矩陣的原最大化指派問題有相同的最優(yōu)解。例

15、5：某工廠有4名工人A1，A2，A3，A4，分別操作4臺車床B1，B2，B3，B4。每小時單產(chǎn)量如下表，求產(chǎn)值最大的分配方案。車床工人B1 B2 B3 B4A1A2A3A410 9 8 73 4 5 62 1 1 24 3 5 6解：C=，m=max10,9,8,7,5,6=10,B= =中的數(shù)=n=4, 所以 X= （5。7）即為最優(yōu)解。從而產(chǎn)值最大的分配方案也為（5.7），最大產(chǎn)值為 Z=10615=222 人數(shù)和事數(shù)不等的指派問題。 若人數(shù)< 事數(shù)，添一些虛擬的“人”，此時這些虛擬的“人”做各件事的費用系數(shù)取為0，理解為這些費用實際上不會發(fā)生。 若人數(shù)> 事數(shù)，添一些虛擬的“

16、事”，此時這些虛擬的“事”被各個人做的費用系數(shù)同樣也取為0。例6：現(xiàn)有4個人，5件工作。每人做每件工作所耗時間如下表：工作工人B1B2B3B4B5A11011428A2711101412A35691214A4131511107問指派那個人去完成哪項工作，可是總消耗最小？解：添加虛擬人A5，構(gòu)造標(biāo)準(zhǔn)耗時陣：行變換C= =所圈0數(shù)=4< 5=n,下找最少覆蓋0的直線。= 從未劃去的元素中找最小者：4，3，7，5，1，4，7，9=1。未劃去的行減去此最小者1，劃去的列加上次最小者1，得。=個數(shù)=n,從而的一最優(yōu)指派：=從而最少耗時為 z=2767=223.一個人可做幾件事的指派問題。若某人可作

17、幾件事，則可將該人化作相同的幾個“人”來接受指派。這幾個“人”做同一件事的費用系數(shù)當(dāng)然一樣。例6：對例12的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司A4和A5，讓技術(shù)力量較強的建筑公司A1、A2、A3來承建。根據(jù)實際情況，可以允許每家建筑公司承建一家或兩家商店。求使總費用最少的指派方案。B1 B2 B3 B4 B5解：反映投標(biāo)費用的系數(shù)矩陣為：A1A2A3 B1 B2 B3 B4 B5由于每家建筑公司最多可承建兩家新商店，因此，把每家建筑公司化作相同的兩家建筑公司（和，i=1，2，3）。這樣，系數(shù)矩陣變?yōu)椋?上面的系數(shù)矩陣有6行5列，為了使“人”和“事”的數(shù)目相同，引入一件虛擬事，

18、使之成為標(biāo)準(zhǔn)的指派問題，其系數(shù)矩陣為： B1 B2 B3 B4 B5 B6C= 列變換C =的數(shù)=5< 6=n,下找0元素的最少直線覆蓋。 -1 -1= =從而得一最優(yōu)指派：B4B5A3B2B6=A2B1B3A1承建商店公司 = 總費用為z=74978=35(萬元)4某事不能由某人去做的指派問題某事不能由某人去做，可將此人做此時的費用取作足夠大的M。例7：分配甲、乙、丙、丁四個人去完成A、B、C、D、E五項任務(wù)，每人完成各項任務(wù)的時間如下表。由于任務(wù)重，人數(shù)少，考慮：a). 任務(wù)E必須完成，其它4項任務(wù)可選3項完成。但甲不能做A項工作。b) 其中有一人完成兩項，其他人每人完成一項。試分別

19、確定最優(yōu)分配方案，使完成任務(wù)的總時間最少。任務(wù)人A B C D E甲乙丙丁25 29 31 42 3739 38 26 20 3334 27 28 40 3224 42 36 23 45解：這是一人數(shù)與工作不等的指派問題，若用匈牙利法求解，需作一下處理。a) 由于任務(wù)數(shù)大于人數(shù)，所以需要有一個虛擬的人，設(shè)為戊。因為工作E必須完成，故設(shè)戊完成E的時間為M（M為非常大的數(shù)），即戊不能做工作E，其余的假想時間為0，建立的效率矩陣表如下：任務(wù)人A B C D E甲乙丙丁戊M 29 31 42 3739 38 26 20 3334 27 28 40 3224 42 36 23 45 0 0 0 0 M用匈牙利