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

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

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

3、表示小偷選擇物品i的數(shù)量，則背包問題的數(shù)學(xué)模型為,體積約束,數(shù)量約束,整數(shù)約束,例1 某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運(yùn)所受限制如表5-1：問兩種貨物各托運(yùn)多少箱,可使利潤最大?,問題分析,設(shè)x1,x2分別為甲乙兩種貨物的托運(yùn)箱數(shù)(非負(fù)整數(shù)),則Max z=20x1+10x25x1+4x2≤242x1+5x2 ≤13x1，x2≥0， x1，x2整數(shù)。求解線性規(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對應(yīng)的z=90。那么，如何求整數(shù)規(guī)劃的最優(yōu)解，這就是本章的主要內(nèi)容。,什么是整數(shù)規(guī)劃？,1、一個線性規(guī)劃如果有某些決策變量是整數(shù)，則稱為整數(shù)規(guī)劃（Integer programming)；2、整數(shù)規(guī)劃的類型：純整數(shù)規(guī)劃；混合整數(shù)規(guī)劃；0-1（整數(shù)）規(guī)劃

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

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

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

8、界 z 逐步增大，最終求得最優(yōu)解 z* 。,例2,求解 AMax z=40x1+90x29x1+7x2≤567x1+20x2 ≤70x1，x2≥0x1，x2整數(shù)解 先不考慮整數(shù)約束,用求解線性規(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(為什么)；找一個整數(shù)規(guī)劃的可行解x1=0，x2=0,對應(yīng)的目標(biāo)函數(shù)值 0,則它是整數(shù)規(guī)劃最優(yōu)值的下界,因此0 ≤ z≤ 356.（分枝）選擇任一非整數(shù)變量(只選一個), x1=4.81,將x1≤4， x1 ≥5分別添加到線性規(guī)劃B得到兩個新的原整數(shù)規(guī)劃B1,B2:每次對一個線性規(guī)劃問題進(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,對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，因此分解已無必要。,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,無可行解,最終定界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）無可行解,定界340≤ Z≤340,,,§3   割平

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

16、的頂點(diǎn)，恰好對應(yīng)著原問題的最優(yōu)解,用割平面法求解純整數(shù)規(guī)劃問題,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，這時xi稱為0-1變量或二進(jìn)制變量（binary),xi僅取0或1這個條件可由下述約束條件所取代： xi≤1, xi ≥0， Xi整數(shù)。但是，0-1變量還有許多其它作用。下面舉例說明。,4.1 引入0-1變量的實(shí)際問題,1、投資場所的選定-相互排斥的計(jì)劃例4 某公司擬在市東、西、南三區(qū)建立門市部，擬議中有7個位置（點(diǎn)）Ai(i=1,

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

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

20、約束：,車運(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ù)。,車運(yùn) y =0船運(yùn) y=1,2. 相互排斥的約束條件,這m個約束條件變?yōu)閙+1個約束條件和m個變量。,第i個約束條件起作用,第i個約束條件不起作用。,有m個互相排斥的約束條件： ( i =1，…，m),引入m個0-1變量yi ，,只有一個條件起作用,② 多者擇一,問題：如果要兩個或最多兩個約束條件成立呢

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

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

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

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

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

27、山隊(duì)員攜帶物品i，xi=0表示不攜帶物品i。則問題可寫為：,,背包問題的一般形式：,一維背包問題,體積限制：二維背包問題,投資選擇問題。已知每個項(xiàng)目的投資額和投資回報(bào)率的期望值，如何在資金有限的情況下選擇投資回報(bào)期望值最大的投資方案？,工件排序問題產(chǎn)品2的加工總時間不得超過d.現(xiàn)要求確定各件產(chǎn)品在機(jī)床上的加工方案,使在最短的時間內(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,工廠A1和A2生產(chǎn)某種物資.由于以該種物資供不應(yīng)求,故需要再建立一家分廠.相應(yīng)的建廠方案有A3和A4兩個.這種物資的需求地有B1、B2、B3、B4四個。工廠A3或A4開工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬元或1500萬元?，F(xiàn)要決定建設(shè)工廠A3還是A4，才能使今后每年的總費(fèi)用（即全部物資運(yùn)費(fèi)和新工廠生產(chǎn)費(fèi)用和）最少。,,y=1,若建

30、工廠A3; y=0，若建工廠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)解，對于有n個變量的0-1規(guī)劃，可行解可能有2n個，當(dāng)n較大時，實(shí)際上難以做到。因此常設(shè)計(jì)一些方法，只檢查變量取值的一部分，就能求出問題的最優(yōu)解，這樣的方法稱為隱枚舉法，分枝定界法也是一種隱枚舉法，當(dāng)然，對有些問題隱枚舉法并不適用。,例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）解 先觀察法找一個可行解，容易看出（x1，x2，x3）=（1，0，0）是一個可行解， z=3.為求最優(yōu)解，對于極大化問題，當(dāng)然最優(yōu)解必須滿足3x1-2x2+5x3 ≥3，于是3成為最優(yōu)解的一個“擂臺?？闪斜碛?jì)算如下：,表5-5,,為進(jìn)一步減

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

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

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

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

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

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

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

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

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

42、）若仍有沒有劃圈的0元素，且同行（例）的0元素至少有兩個（表示對這人可以從兩項(xiàng)任務(wù)中指派其一）。這可用不同的方案去試探。從剩有0元素最少的行（列）開始，比較這行各0 元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈（表示選擇性多的要“禮讓”選擇性少）。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。,（5）若◎元素的數(shù)目m等于矩陣的階數(shù)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加圈，得到,可見m=n=4，所以得最優(yōu)解為,這表示：指定甲譯出俄文，乙譯出日文，丙譯出英文，丁譯出德文。所需總時間最少,例8 求表5-8所示效率矩陣的指派問題的最小解。,解題時按上述第一步，將這系數(shù)矩陣進(jìn)行變換。,經(jīng)一次運(yùn)算即得每行每列都有0 元

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

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

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

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

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

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