第五章-整數(shù)規(guī)劃運(yùn)籌學(xué)教程

1、第五章 整數(shù)規(guī)劃,§1 整數(shù)規(guī)劃問(wèn)題的提出§2 分枝定界法§3   割平面法§4 0-1型整數(shù)規(guī)劃§5 指派問(wèn)題,第五章 整數(shù)規(guī)劃（重點(diǎn)和難點(diǎn)）,1、理解整數(shù)規(guī)劃的數(shù)學(xué)模型2、了解整數(shù)規(guī)劃模型的類(lèi)型3、了解整數(shù)規(guī)劃的求解方法4、掌握分枝的思想和步驟（重點(diǎn)和難點(diǎn)）5、理解割平面法的思想和步驟5、了解0-1規(guī)劃的隱枚舉法6、掌握指派問(wèn)題的數(shù)學(xué)模型和求解方法（

2、重點(diǎn)和難點(diǎn)）,§1 整數(shù)規(guī)劃問(wèn)題的提出,理解整數(shù)規(guī)劃的數(shù)學(xué)模型了解整數(shù)規(guī)劃模型的類(lèi)型了解整數(shù)規(guī)劃的求解方法掌握分枝的思想和步驟了解0-1規(guī)劃的隱枚舉法掌握指派問(wèn)題的數(shù)學(xué)模型和求解方法,背包問(wèn)題 一背有容量為250 cm3的背包的小偷進(jìn)入庫(kù)房（或某戶(hù)人家或機(jī)房），他需要從若干物品中選擇一定數(shù)量裝入背包帶走?？蛇x的物品有7種，其價(jià)值、體積及最大的數(shù)量入下表:,,問(wèn)小偷應(yīng)如何選擇物品才能使價(jià)值最大？,令xi

3、表示小偷選擇物品i的數(shù)量，則背包問(wèn)題的數(shù)學(xué)模型為,體積約束,數(shù)量約束,整數(shù)約束,例1 某廠(chǎng)擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表5-1：?jiǎn)杻煞N貨物各托運(yùn)多少箱,可使利潤(rùn)最大?,問(wèn)題分析,設(shè)x1,x2分別為甲乙兩種貨物的托運(yùn)箱數(shù)(非負(fù)整數(shù)),則Max z=20x1+10x25x1+4x2≤242x1+5x2 ≤13x1，x2≥0， x1，x2整數(shù)。求解線(xiàn)性規(guī)劃的最優(yōu)解得： x1=

4、4.8，x2=0，Max z=96 。四舍五入得x1=5，x2=0，但不是可行解，取整x1=4，x2=0是可行解，z=80,是不是最優(yōu)解呢？不是，因?yàn)榭尚薪鈞1=4，x2=1對(duì)應(yīng)的z=90。那么，如何求整數(shù)規(guī)劃的最優(yōu)解，這就是本章的主要內(nèi)容。,什么是整數(shù)規(guī)劃？,1、一個(gè)線(xiàn)性規(guī)劃如果有某些決策變量是整數(shù)，則稱(chēng)為整數(shù)規(guī)劃（Integer programming)；2、整數(shù)規(guī)劃的類(lèi)型：純整數(shù)規(guī)劃；混合整數(shù)規(guī)劃；0-1（整數(shù)）規(guī)劃

5、。,整數(shù)規(guī)劃的可行解，最優(yōu)解,x232 +1 + + + + + 1 2 3 4 5 6 7 x1,,,,,,,,,,§2 分枝定界法,對(duì)于整數(shù)規(guī)劃問(wèn)題，如果是兩個(gè)自變量則可以用圖解法（要比線(xiàn)性規(guī)劃難）。當(dāng)可行區(qū)域有界時(shí)，整數(shù)可行解的個(gè)數(shù)為有限個(gè)，因此，可把所有的整

6、數(shù)可行解求出來(lái)，目標(biāo)函數(shù)值最大者對(duì)應(yīng)的可行解就為最優(yōu)解，這種方法稱(chēng)為枚舉法。但是，當(dāng)變量較多時(shí)，可行整數(shù)解的個(gè)數(shù)也很多，其計(jì)算量仍然很大。例如指派n人做n件事的問(wèn)題就有n!個(gè)可行解，當(dāng)n=10時(shí)，可行解超過(guò)300萬(wàn)個(gè)，當(dāng)n=20時(shí)，可行解超過(guò)2*1018個(gè)，枚舉法就不行了。因此，下面要給出整數(shù)規(guī)劃的有效求解方法。,求解整數(shù)規(guī)劃的方法,分枝定界法；割平面法；其它算法。,分枝定界法,設(shè)有極大型的整數(shù)線(xiàn)性規(guī)劃問(wèn)題，記為 ILP ，與之

7、對(duì)應(yīng)的普通線(xiàn)性規(guī)劃問(wèn)題記為 LP 。分枝定界法求解 ILP 問(wèn)題的基本思路是：1、先從求解LP 問(wèn)題開(kāi)始，如果 LP 的解不符合整數(shù)條件，那么 LP 的最優(yōu)目標(biāo)值必然構(gòu)成ILP 最優(yōu)目標(biāo)值的一個(gè)上界，記為 ；2、而 ILP 的任意可行解的目標(biāo)值都將是最優(yōu)目標(biāo)值的一個(gè)下界，記為 z 。所謂分枝定界法就是將LP 問(wèn)題的可行域劃分為兩個(gè)子域（分枝，中間去掉了一塊沒(méi)有整數(shù)可行解的部分），使上界 逐步減小，而通過(guò)獲得更好的整數(shù)可行解使下

8、界 z 逐步增大，最終求得最優(yōu)解 z* 。,例2,求解 AMax z=40x1+90x29x1+7x2≤567x1+20x2 ≤70x1，x2≥0x1，x2整數(shù)解 先不考慮整數(shù)約束,用求解線(xiàn)性規(guī)劃B：返回Max z=40x1+90x29x1+7x2≤567x1+20x2 ≤70x1，x2≥0得最優(yōu)解得x1=4.81，x2=1.82,最優(yōu)值 z0=356.如果x1，x2是整數(shù),則就是最優(yōu)解,否則分枝定。,如何分枝和

9、定界,（定界） ,由于z0=356是原整數(shù)規(guī)劃去掉整數(shù)約束的最大值，因此它就是原整數(shù)規(guī)劃的目標(biāo)函數(shù)值的上界,即 z≤ 356(為什么)；找一個(gè)整數(shù)規(guī)劃的可行解x1=0，x2=0,對(duì)應(yīng)的目標(biāo)函數(shù)值 0,則它是整數(shù)規(guī)劃最優(yōu)值的下界,因此0 ≤ z≤ 356.（分枝）選擇任一非整數(shù)變量(只選一個(gè)), x1=4.81,將x1≤4， x1 ≥5分別添加到線(xiàn)性規(guī)劃B得到兩個(gè)新的原整數(shù)規(guī)劃B1,B2:每次對(duì)一個(gè)線(xiàn)性規(guī)劃問(wèn)題進(jìn)行分枝一次，就定界一次

10、。,分枝,B1 Max z=20x1+10x2 x25x1+4x2≤242x1+5x2 ≤13x1 ≤ 4x1，x2≥0B2 Max z=20x1+10x25x1+4x2≤24 x12x1+5x2 ≤13x1 ≥ 5x1，x2≥0LP,,,,,,,

11、,,,,,,,B1,B,4<x1<5,B2,,,,解得,修改上界和下界,得0 ≤ z≤ max(z1,z2)= max(349,341)=349,對(duì)B1和B2再分枝定界,B1B3 B4B2B5 B6,,,,,B3,B4,B3Max z=20x1+10x25x1+4x2≤242x1+5x2 ≤13x1 ≤ 4, X2≤2；x1，x2≥0B4Max z=20x1+10x25x1

12、+4x2≤242x1+5x2 ≤13x1 ≤ 4, X2 ≥3x1，x2≥0,最優(yōu)解X1=4,x2=2：整數(shù)可行解Z3=340,最優(yōu)解X1=1.42,x2=3Z4=327,定界340≤ Z≤max(z2,z3,z4)=z2=341由于B4的最優(yōu)解小于目前的整數(shù)解340，因此分解已無(wú)必要。,B5, B6,B5Max z=20x1+10x25x1+4x2≤242x1+5x2 ≤13x1 ≥ 5, X2≤1；x

13、1，x2≥0B6Max z=20x1+10x25x1+4x2≤242x1+5x2 ≤13x1 ≥ 5, X2 ≥2x1，x2≥0,最優(yōu)解X1=5.44,x2=1：整數(shù)可行解Z5=308,無(wú)可行解,最終定界340≤ Z≤max(z3,z4, z5)=340,Z=340為最優(yōu)值，最優(yōu)解X1=4,x2=2,圖5-4,B最優(yōu)解X1=4.81,x2=1.82Z0=356,B1(x1≤4）最優(yōu)解X1=4,x2=2.1Z1

14、=349,B2（x1≥5）最優(yōu)解X1=5,x2=1.57Z2=341,定界0≤ Z≤356,定界0≤ Z≤349,B3(x2≤2）最優(yōu)解X1=4,x2=2Z3=340,B4(x2≥3）最優(yōu)解X1=1.42,x2=3Z4=327,,,,,,定界340≤ Z≤341,B5（x2≤1）最優(yōu)解X1=5,x2=1.57Z2=308,B6（x2≥2）無(wú)可行解,定界340≤ Z≤340,,,§3   割平

15、面法,1、分枝定界法本質(zhì)上是一種對(duì)線(xiàn)性規(guī)劃可行域的分割方法，只是分割方式比較單一和規(guī)范。每次從對(duì)應(yīng)線(xiàn)性規(guī)劃的最優(yōu)解出發(fā)，選定某個(gè)取非整數(shù)值的變量，挖掉其中的小數(shù)部分，將原可行域一分為二。如此反復(fù)進(jìn)行，直到發(fā)現(xiàn)最優(yōu)整數(shù)解為止。 2、割平面法的思路也是采用求解對(duì)應(yīng)線(xiàn)性規(guī)劃的方法去解整數(shù)規(guī)劃的問(wèn)題。通過(guò)增加適當(dāng)?shù)募s束條件，從原可行域中切割掉不含整數(shù)解的部分。但其切割方式靈活多樣，每次切割可以切一刀，也可以同時(shí)切幾刀。旨在造成一個(gè)具有整數(shù)坐標(biāo)

16、的頂點(diǎn)，恰好對(duì)應(yīng)著原問(wèn)題的最優(yōu)解,用割平面法求解純整數(shù)規(guī)劃問(wèn)題,max z=3x1-x23x1-2x2=102x1+x2=0x1,x2為整數(shù),割平面約束：-1/7x3-2/7x5<=-6/7,,割平面約束：-1/4x4-1/4x6<=-3/4,,§4 0-1型整數(shù)規(guī)劃,什么叫0-1規(guī)劃0-1變量的作用(重點(diǎn)和難點(diǎn))(1)相互排斥計(jì)劃(2)相互排斥的約束條件(3)固定費(fèi)用的表示0-1型整數(shù)規(guī)劃的解法

17、,什么叫0-1規(guī)劃,0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情況，它的變量xi僅取0或1，這時(shí)xi稱(chēng)為0-1變量或二進(jìn)制變量（binary),xi僅取0或1這個(gè)條件可由下述約束條件所取代： xi≤1, xi ≥0， Xi整數(shù)。但是，0-1變量還有許多其它作用。下面舉例說(shuō)明。,4.1 引入0-1變量的實(shí)際問(wèn)題,1、投資場(chǎng)所的選定-相互排斥的計(jì)劃例4 某公司擬在市東、西、南三區(qū)建立門(mén)市部，擬議中有7個(gè)位置（點(diǎn)）Ai(i=1,

18、2,…,7)可供選擇。要求在東區(qū)， A1， A2， A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)， A4， A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)， A6， A7兩個(gè)點(diǎn)中至少選一個(gè)。如選用Ai，設(shè)備投資估計(jì)為bi元,每年可獲利潤(rùn)估計(jì)為ci元，但投資總額不能超過(guò)B元，問(wèn)可選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)最大？,解:,(1)設(shè)決策變量,先引入0-1變量xi (i =1，2，…，7)令,投資總額不超過(guò)B,A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè),A4，A5兩個(gè)點(diǎn)中至少選

19、一個(gè),A6，A7兩個(gè)店中至少選一個(gè),收益最大,(2)用決策變量表達(dá)目標(biāo)函數(shù)和約束條件,同濟(jì)考研題,2、相互排斥的約束條件,在本章開(kāi)始的例1中，關(guān)于運(yùn)貨的體積限制為5x1+4x2≤24 (5.9)今設(shè)運(yùn)貨的方式有車(chē)運(yùn)和船運(yùn)兩種，上面的條件系用車(chē)運(yùn)時(shí)的限制條件，如用船運(yùn)時(shí)關(guān)于體積的限制條件為7x1+3x2≤45 (5.10)這兩個(gè)條件是相互排斥的，為了統(tǒng)一在一個(gè)問(wèn)題中，引入0-1變量y,令,① 二者擇一,如例1中體積

20、約束：,車(chē)運(yùn) 5x1 + 4x2 ? 24 船運(yùn) 7x1 + 3x2 ? 45,引入0-1變量y ，令 體積約束為： 5x1 + 4x2 ? 24 + yM 7x1 + 3x2 ? 45 + (1-y)M

21、 y = 0或1其中M為充分大的數(shù)。,車(chē)運(yùn) y =0船運(yùn) y=1,2. 相互排斥的約束條件,這m個(gè)約束條件變?yōu)閙+1個(gè)約束條件和m個(gè)變量。,第i個(gè)約束條件起作用,第i個(gè)約束條件不起作用。,有m個(gè)互相排斥的約束條件： ( i =1，…，m),引入m個(gè)0-1變量yi ，,只有一個(gè)條件起作用,② 多者擇一,問(wèn)題：如果要兩個(gè)或最多兩個(gè)約束條件成立呢

22、？,相互排斥的約束條件,5x1+4x2≤24+yM7x1+3x2≤45+(1-y)MM是充分大的常數(shù),y=0或1。如果有m個(gè)相互排斥的約束條件（≤）ai1x1+ ai2x2+…+ ainxn ≤bi , (i=1,2,…,m)為了保證這m個(gè)約束條件只有一個(gè)起作用，引入m 個(gè)0-1變量yi (i=1,2,…,m)和充分大的常數(shù)M,而下面的m+1個(gè)約束條件ai1x1+ ai2x2+…+ ainxn ≤bi+ yiM, (i=1,

23、2,…,m)y1+ y2+…+ ym=m-1就合于上述要求。,3、關(guān)于固定費(fèi)用問(wèn)題,在討論線(xiàn)性規(guī)劃時(shí)，有些問(wèn)題是要求使成本最少的方案，那時(shí)總設(shè)固定成本為常數(shù)，并在線(xiàn)性規(guī)劃的模型中不必明顯列出。但有些固定成本的問(wèn)題不能用一般線(xiàn)性規(guī)劃來(lái)描述，但可改為混合整數(shù)規(guī)劃來(lái)解決。,,例5 某工廠(chǎng)為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的生產(chǎn)方式投資成本高(選購(gòu)自動(dòng)化程度高的設(shè)備)，由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動(dòng)成本就減低；反之

24、，如選定的生產(chǎn)方式投資低，將來(lái)分配到每件產(chǎn)品的變動(dòng)成本可能增加，所以必須全面考慮。今設(shè)有三種方式可供選擇，令xj表示采用第j種方式時(shí)的產(chǎn)量；cj 表示采用第j種方式時(shí)每件產(chǎn)品的變動(dòng)成本；kj 表示采用第j種方式時(shí)的固定成本。,3.  關(guān)于固定費(fèi)用的問(wèn)題,采用各種生產(chǎn)方式的成本分別為,引入0—1變量yj,令,當(dāng)采用第j種生產(chǎn)方式，即xj>0時(shí)不采用第j種生產(chǎn)方式，即xj=0時(shí),于是目標(biāo)為,Min Z =(k1

25、y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3),上式這個(gè)規(guī)定可由下述三個(gè)線(xiàn)性約束條件表示,xj≤yj M j=1,2,3,暫不考慮其它條件,Y=1,不同于目標(biāo)函數(shù),例 6 某服裝廠(chǎng)可生產(chǎn)三種服裝：西服、襯衫和羽絨服。生產(chǎn)不同種類(lèi)的服裝要使用不同種類(lèi)的設(shè)備，該服裝廠(chǎng)可從專(zhuān)業(yè)租賃公司租用這些設(shè)備。設(shè)備租金和其它經(jīng)濟(jì)參數(shù)如下：,假定市場(chǎng)需求不成問(wèn)題，服裝廠(chǎng)每月可用的人工工時(shí)為2000小時(shí)，該廠(chǎng)如何安排生產(chǎn)可使

26、每月的利潤(rùn)最大？,解：該問(wèn)題需要兩類(lèi)決策變量，一類(lèi)決定是否租賃設(shè)備的決策變量yi,另一類(lèi)是反映個(gè)類(lèi)服裝生產(chǎn)數(shù)量的變量xj。 這兩類(lèi)變量的關(guān)系為xi＞0,yi應(yīng)等于1；若yi=0,xi也必須為0。不租設(shè)備就不能進(jìn)行生產(chǎn)。,4.背包問(wèn)題 一登山隊(duì)員做登山準(zhǔn)備，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相機(jī)和通訊設(shè)備。每件物品的重要性系數(shù)和重量見(jiàn)下表，假定登山隊(duì)員可攜帶的最大重量為25千克。,令xi=1表示登

27、山隊(duì)員攜帶物品i，xi=0表示不攜帶物品i。則問(wèn)題可寫(xiě)為：,,背包問(wèn)題的一般形式：,一維背包問(wèn)題,體積限制：二維背包問(wèn)題,投資選擇問(wèn)題。已知每個(gè)項(xiàng)目的投資額和投資回報(bào)率的期望值，如何在資金有限的情況下選擇投資回報(bào)期望值最大的投資方案？,工件排序問(wèn)題產(chǎn)品2的加工總時(shí)間不得超過(guò)d.現(xiàn)要求確定各件產(chǎn)品在機(jī)床上的加工方案,使在最短的時(shí)間內(nèi)加工完全部產(chǎn)品.,x11+a11≤x13,X13+a13 ≤x14X21+a21 ≤x22 ,X22+a

28、22 ≤x24X32+a32 ≤x33,X11+a11 ≤x21+My1,X21+a21 ≤x11+M(1-y1) X22+a22 ≤x32+My2, X32+a32 ≤x22+M(1-y2)X13+a13 ≤x33+My3, X33+a33 ≤x13+M(1-y3)X14+a14 ≤x24+My4, X24+a24 ≤x14+M(1-y4)X24+a24-x21 ≤d目標(biāo)函數(shù)：W=max{x14+a14,x24+a24,

29、x33+a33}Min z=ww≥x14+a14 w≥ x24+a24 w≥ x33+a33,工廠(chǎng)A1和A2生產(chǎn)某種物資.由于以該種物資供不應(yīng)求,故需要再建立一家分廠(chǎng).相應(yīng)的建廠(chǎng)方案有A3和A4兩個(gè).這種物資的需求地有B1、B2、B3、B4四個(gè)。工廠(chǎng)A3或A4開(kāi)工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬(wàn)元或1500萬(wàn)元?，F(xiàn)要決定建設(shè)工廠(chǎng)A3還是A4，才能使今后每年的總費(fèi)用（即全部物資運(yùn)費(fèi)和新工廠(chǎng)生產(chǎn)費(fèi)用和）最少。,,y=1,若建

30、工廠(chǎng)A3; y=0，若建工廠(chǎng)A4。X11+x21+x31+x41=350;X12+x22+x32+x42=400;X13+x23+x33+x43=300;X14+x24+x34+x44=150;X11+x12+x13+x14=400;X21+x22+x23+x24=600;X31+x32+x33+x34=200y;X41+x42+x43+x44=200(1-y);,4.2 0-1型整數(shù)規(guī)劃的解法,解0-1型整數(shù)規(guī)劃最容易

31、想到的方法，和整數(shù)規(guī)劃的情形一樣，就是窮舉法，求出所有的可行解，比較最優(yōu)目標(biāo)值以求得最優(yōu)解，對(duì)于有n個(gè)變量的0-1規(guī)劃，可行解可能有2n個(gè)，當(dāng)n較大時(shí)，實(shí)際上難以做到。因此常設(shè)計(jì)一些方法，只檢查變量取值的一部分，就能求出問(wèn)題的最優(yōu)解，這樣的方法稱(chēng)為隱枚舉法，分枝定界法也是一種隱枚舉法，當(dāng)然，對(duì)有些問(wèn)題隱枚舉法并不適用。,例6,Max z=3x1-2x2+5x3X1+2x2-x3≤2 （1） x1+4x2+x3≤4

32、 （2）x1+x2≤3 （3）4x2+x3 ≤6 （4）x1，x2，x3≥0 （5）解 先觀(guān)察法找一個(gè)可行解，容易看出（x1，x2，x3）=（1，0，0）是一個(gè)可行解， z=3.為求最優(yōu)解，對(duì)于極大化問(wèn)題，當(dāng)然最優(yōu)解必須滿(mǎn)足3x1-2x2+5x3 ≥3，于是3成為最優(yōu)解的一個(gè)“擂臺(tái)?？闪斜碛?jì)算如下：,表5-5,,為進(jìn)一步減

33、少運(yùn)算量，常按目標(biāo)函數(shù)中各變量系數(shù)的大小順序重新排列各變量，以使最優(yōu)解較早出現(xiàn)。對(duì)于最大化問(wèn)題，可按由小到大的順序排列；對(duì)于最小化問(wèn)題，則相反。,§5 指派問(wèn)題,在生活中經(jīng)常遇到這樣的問(wèn)題，某單位需完成n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)這些任務(wù)。由于每人的專(zhuān)長(zhǎng)不同，各人完成任務(wù)不同（或所費(fèi)時(shí)間），效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高（或所需總時(shí)間最?。?。這問(wèn)題稱(chēng)為指派問(wèn)題或分派問(wèn)題（Assig

34、nment problem）。,,例7 有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字。分別記得E、J、G、R。現(xiàn)有甲、乙、丙、丁四人。他們將中文說(shuō)明書(shū)翻譯成不同語(yǔ)種的說(shuō)明書(shū)所需時(shí)間如表5-7所示，問(wèn)應(yīng)指派何人去完成何工作，使所需總時(shí)間最少？,表5-7,,類(lèi)似有：有n項(xiàng)加工任務(wù)，怎樣指派到n臺(tái)機(jī)床上分別完成的問(wèn)題；有n條航線(xiàn)，怎樣指定n艘船去航行問(wèn)題…等等。對(duì)應(yīng)每個(gè)指派問(wèn)題，需有類(lèi)似表5-7那樣的數(shù)表，稱(chēng)為效率矩陣或系數(shù)矩陣，其元素c

35、ij>（≥）0（i,j=1,2.…,n）表示指派第i人去完成第j項(xiàng)任務(wù)時(shí)的效率（或時(shí)間、成本等）。解題時(shí)需引入變量xij；其取值只能是1或0。并令 1 當(dāng)指派第i人去完成第j項(xiàng)任務(wù) xij= 0 當(dāng)不指派第i人去完成第j項(xiàng)任務(wù),,當(dāng)問(wèn)題要求極小化時(shí)數(shù)學(xué)模型是：,①

36、 ②(5.19) ③ xij=1或0 約束條件②說(shuō)明第j項(xiàng)任務(wù)只能由1人去完成；約束條件③說(shuō)明第i人只能完成1項(xiàng)任務(wù)。滿(mǎn)足約束條件②-④的可行解xij也可寫(xiě)成表格或矩陣形式，稱(chēng)為解矩陣。,如例7的一個(gè)可行解（矩陣）是：,顯然，這不是最優(yōu)。解矩陣(xij)中各行各列的元素之和都是1。,指派問(wèn)題是

37、0-1規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例；即n=m，ai=bj=1.當(dāng)然可用整數(shù)規(guī)劃，0-1規(guī)劃或運(yùn)輸問(wèn)題的解法去求解，這就如同用單純型法求解運(yùn)輸問(wèn)題一樣是不合算的。利用指派問(wèn)題的特點(diǎn)可有更簡(jiǎn)便的解法。指派問(wèn)題的最優(yōu)解的性質(zhì):若從系數(shù)矩陣(cij)的一行（列）各元素中分別減去一個(gè)常數(shù) ，得到新矩陣(bij)，那么以(bij)為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。,指派問(wèn)題求解的思想,利用上面這個(gè)性質(zhì)可使原系數(shù)矩陣變換為

38、非負(fù)但含有很多0元素的新系數(shù)矩陣，而最優(yōu)解保持不變。在系數(shù)矩陣(bij)中，我們關(guān)心位于不同行不同列的0元素，以下簡(jiǎn)稱(chēng)為獨(dú)立的0元素。若能在系數(shù)矩(bij)中找出n個(gè)獨(dú)立的0元素。則令解矩陣(xij)中對(duì)應(yīng)這n個(gè)獨(dú)立的0元素的元素（位置）取值為1，其它元素取值為0，將其代入目標(biāo)函數(shù)中得到zb=0。它一定是最小值。這就是以(bij)為系數(shù)矩陣的指派問(wèn)題的最優(yōu)解。也就是原問(wèn)題的最優(yōu)解。,匈牙利算法,庫(kù)恩(W.W.Kuhn)于1955

39、年提出了指派問(wèn)題的解法，他引用了匈牙利數(shù)學(xué)家康尼格(D.Konig)一個(gè)關(guān)于矩陣中0元素的定理：系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線(xiàn)數(shù)。這解法稱(chēng)為匈牙利算法。以后在方法上雖有不斷改進(jìn)，但仍沿用這名稱(chēng)。以下用例7來(lái)說(shuō)明指派問(wèn)題的解法。,匈牙利算法的步驟,第一步：使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。（1）從系數(shù)矩陣的每行元素減去該行的最小元素；（2）再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的

40、最小元素。若某行（列）已有0元素，那就不必再減,例7的計(jì)算為,min 4 2,,,第二步：進(jìn)行試指派，以尋求最優(yōu)解。為此，按以下步驟進(jìn)行。經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素，但需找出n個(gè)獨(dú)立的0元素。若能找出，就以這些獨(dú)立0元素對(duì)應(yīng)解矩(xij)中的元素為1，其余為0，這就得到最優(yōu)解。當(dāng)n較小時(shí)，可用觀(guān)察法、試探法去找出n個(gè)獨(dú)立0元素。若n較大時(shí)，就必須按一定的步驟去找，,第二

41、步 試指派,常用的步驟為：,（1）   從只有一個(gè)0元素的行（列）開(kāi)始，給這個(gè)0元素加圈，記作◎。這表示對(duì)這行所代表的人，只有一種任務(wù)可指派。然后劃去◎所在列（行）的其它0元素，記作φ。這表示這列所代表的任務(wù)已指派完，不必再考慮別人了,（2）給只有一個(gè)0元素列（行）的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作ф（3）反復(fù)進(jìn)行（1），（2）兩步，直到所有0元素都被圈出和劃掉為止。,（4

42、）若仍有沒(méi)有劃圈的0元素，且同行（例）的0元素至少有兩個(gè)（表示對(duì)這人可以從兩項(xiàng)任務(wù)中指派其一）。這可用不同的方案去試探。從剩有0元素最少的行（列）開(kāi)始，比較這行各0 元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈（表示選擇性多的要“禮讓”選擇性少）。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。,（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問(wèn)題的最優(yōu)解已得到。若m<n，則轉(zhuǎn)

43、入下一步(增加0元素)。,現(xiàn)用的例7的（bij）矩陣，按上述步驟進(jìn)行運(yùn)算，按步驟(1)，選給b22加圈，加后給b31加圈，劃掉b11,b41，按步驟（2），給b43，劃掉b44,最后給b14加圈，得到,可見(jiàn)m=n=4，所以得最優(yōu)解為,這表示：指定甲譯出俄文，乙譯出日文，丙譯出英文，丁譯出德文。所需總時(shí)間最少,例8 求表5-8所示效率矩陣的指派問(wèn)題的最小解。,解題時(shí)按上述第一步，將這系數(shù)矩陣進(jìn)行變換。,經(jīng)一次運(yùn)算即得每行每列都有0 元

44、素的系數(shù)矩陣，,,再按上述步驟運(yùn)算，得到：,這里◎的個(gè)數(shù)m=4，n＝5;所以解題沒(méi)有完成，這時(shí)應(yīng)按以下步驟繼續(xù)進(jìn)行。,第三步：作最少的直線(xiàn)覆蓋所有0元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立元素?cái)?shù)。為此按以步驟進(jìn)行：（1）對(duì)沒(méi)有◎的行打√號(hào)；（2）對(duì)已打√號(hào)的行中所有含0 元素的列打√號(hào)；（3）再對(duì)打有√號(hào)的列中含◎元素的行打√號(hào)；（4）重復(fù)（2），（3）直到得不出新的打√號(hào)的行、列為止；（5）對(duì)沒(méi)有打√號(hào)的行畫(huà)一橫線(xiàn)，有打√的

45、列畫(huà)一縱線(xiàn)，這就得到覆蓋所有0元素的最少直線(xiàn)數(shù)。,令這直線(xiàn)數(shù)為l。若l<m，說(shuō)明必須再變換當(dāng)前的系數(shù)矩陣，才能找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步；若l=n，m<n，應(yīng)回到第二步（4），另行試探。,在例8中，對(duì)矩①按以下次序進(jìn)行：先在第五行旁打√，接著可判斷應(yīng)在第1列下打√，接著在第3行旁打√，經(jīng)檢查不能再打√了。對(duì)沒(méi)有打√行，畫(huà)一直線(xiàn)以覆蓋0元素，已打√的列畫(huà)一直線(xiàn)以覆蓋0元素。得,由此可見(jiàn)l=4<n，所以應(yīng)繼續(xù)

46、對(duì)②矩陣進(jìn)行變換，轉(zhuǎn)第四步。,第四步：對(duì)②矩陣進(jìn)行變換的目的是增加0元素。(1)在沒(méi)有被直線(xiàn)覆蓋的部分中找出最小元素;(2) 在打√行各元素中都減去這最小元素;(3)在打√列的各元素都加上這最小元素，以保證原來(lái)0元素不變。這樣得到新系數(shù)矩陣（它的最優(yōu)解和原問(wèn)題相同）。若得到n個(gè)獨(dú)立的0元素，則已得最優(yōu)解，否則回到第三步重復(fù)進(jìn)行。,在例8的矩陣②中，在沒(méi)有被覆蓋部分（第3、5行）中找出最小元素為2，然后在第3、5行各元素分別減去

47、2，給第1列各元素加2，得到新矩陣③。按第二步，找出所有獨(dú)立的0元素。得到矩陣④,它具有n個(gè)獨(dú)立0元素，這就得到了最優(yōu)解，相應(yīng)的解矩為,由解矩陣得最優(yōu)指派方案 甲－B，乙－D，丙－E，丁－C，戊－A本例還可以得到另一最優(yōu)指派方案 甲－B，乙－C，丙－E,?。璂,戊－A所需總時(shí)間為Min z＝32,當(dāng)指派問(wèn)題的系數(shù)矩陣，經(jīng)過(guò)變換得到了同行和同列中都有兩個(gè)或兩個(gè)以上0元素時(shí)。這時(shí)可以任選一行（列）中某一個(gè)0元

48、素，再劃去同行（列）的其它0元素。這時(shí)會(huì)出現(xiàn)多重解。,指派問(wèn)題的其它模型,1、最大化問(wèn)題2、人數(shù)與任務(wù)數(shù)不同的問(wèn)題若人少事多，可以添加上一些虛擬的人，這些虛擬人做各事得費(fèi)用取0。若人多事少，可以添加一些虛擬的事，這些虛擬的事被個(gè)人做的費(fèi)用系數(shù)同樣也取0.3、每人可做幾件事若某個(gè)人可以做幾件事，則可將該人化作相同的幾個(gè)人接受指派。這幾個(gè)人做同一件事得費(fèi)用系數(shù)一樣4、某事一定不能由某人做的指派問(wèn)題。如某事一定不能由某人做，則可

49、將相應(yīng)的費(fèi)用系數(shù)取作足夠大的數(shù)M。,,某公司要建設(shè)5家新商店，決定由A1、A2、A3三家公司承建。根據(jù)實(shí)際情況，每家建筑公司可以承建一家或兩家商店，求使總費(fèi)用最少的指派方案。,練習(xí)題,目標(biāo)1：滿(mǎn)足三種維生素的每日最小需要量目標(biāo)2：使每日攝入的膽固醇最少目標(biāo)3：使每日購(gòu)買(mǎi)的食品的費(fèi)用最少。,出場(chǎng)陣容滿(mǎn)足以下條件：只能有一名中鋒上場(chǎng)至少一名后衛(wèi)如1號(hào)和4號(hào)均上場(chǎng)，則6號(hào)不出場(chǎng)；2號(hào)和8號(hào)至少一個(gè)不出場(chǎng)；應(yīng)選擇哪5名隊(duì)員上場(chǎng)，才能