1、整數(shù)規(guī)劃整數(shù)規(guī)劃第第1節(jié)節(jié) 整數(shù)規(guī)劃問題的特點及其作用整數(shù)規(guī)劃問題的特點及其作用第第2節(jié)節(jié) 分支定界方法分支定界方法第第3節(jié)節(jié) 割平面方法割平面方法第第4節(jié)節(jié) 0-1規(guī)劃規(guī)劃第第5節(jié)節(jié) 指派（分配）問題指派（分配）問題整數(shù)規(guī)劃（整數(shù)規(guī)劃（1）1.整數(shù)規(guī)劃問題的提出整數(shù)規(guī)劃問題的提出整數(shù)規(guī)劃整數(shù)規(guī)劃: 若一個規(guī)劃的最優(yōu)解要求部分或全部決策若一個規(guī)劃的最優(yōu)解要求部分或全部決策變量是整數(shù)變量是整數(shù) 的問題的問題純整數(shù)規(guī)劃純整數(shù)規(guī)劃: 整數(shù)規(guī)劃中如果所有的變量都為非負整數(shù)整數(shù)規(guī)劃中如果所有的變量都為非負整數(shù),(Pure Integer Programming)(Integer Programming)

2、,簡稱簡稱IP或稱為或稱為全整數(shù)規(guī)劃全整數(shù)規(guī)劃(All Integer Programming)混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃:若整數(shù)規(guī)劃中僅一部分變量限制為整數(shù)若整數(shù)規(guī)劃中僅一部分變量限制為整數(shù), 則稱為混合整數(shù)規(guī)劃則稱為混合整數(shù)規(guī)劃(Mixed Integer Programming)整數(shù)規(guī)劃（整數(shù)規(guī)劃（2）0-1規(guī)劃：規(guī)劃：若整數(shù)規(guī)劃中的變量都僅限制為若整數(shù)規(guī)劃中的變量都僅限制為0或或1,則稱為則稱為0-1規(guī)劃規(guī)劃整數(shù)線性規(guī)劃：整數(shù)線性規(guī)劃：若整數(shù)規(guī)劃問題的目標函數(shù)和約束條件都是線性的，若整數(shù)規(guī)劃問題的目標函數(shù)和約束條件都是線性的，則稱該整數(shù)規(guī)劃是整數(shù)線性規(guī)劃則稱該整數(shù)規(guī)劃是整數(shù)線性規(guī)劃本章中

3、，我們討論的主要對象是本章中，我們討論的主要對象是整數(shù)線性規(guī)劃，整數(shù)線性規(guī)劃，下面的討論中將省略下面的討論中將省略線性線性二字二字整數(shù)規(guī)劃（整數(shù)規(guī)劃（3）問問:兩種貨物各托運多少箱兩種貨物各托運多少箱,可使獲利最大可使獲利最大?則其數(shù)學模型則其數(shù)學模型設設x1,x2分別為托運甲、分別為托運甲、乙兩種貨物的數(shù)量乙兩種貨物的數(shù)量例例1.某廠擬用集裝箱托運甲乙兩種貨物某廠擬用集裝箱托運甲乙兩種貨物,每箱的體每箱的體 積、重量、積、重量、 可獲利及托運限制如下表可獲利及托運限制如下表:貨物貨物 體積體積 重量重量 利潤利潤 (每箱立方米每箱立方米) (每箱百斤每箱百斤) (每箱百元每箱百元) 甲甲 5

4、 2 20 乙乙 4 5 10托運限制托運限制 24 13 12121212max20105424. . 25130,0,zxxxxstxxxx整數(shù)它是一個純整數(shù)規(guī)劃它是一個純整數(shù)規(guī)劃,整數(shù)規(guī)劃（整數(shù)規(guī)劃（4）它與線性規(guī)劃的區(qū)別僅在于要求它與線性規(guī)劃的區(qū)別僅在于要求x1,x2為整數(shù)的條件為整數(shù)的條件則是否可以把所得的非整數(shù)的最優(yōu)解經(jīng)過則是否可以把所得的非整數(shù)的最優(yōu)解經(jīng)過”化整化整”來得到整數(shù)規(guī)劃的最優(yōu)解呢來得到整數(shù)規(guī)劃的最優(yōu)解呢?易求出最優(yōu)解為易求出最優(yōu)解為x1=4.8 x2=0 z*=96若不考慮整數(shù)條件若不考慮整數(shù)條件,則變成一個線性規(guī)劃問題則變成一個線性規(guī)劃問題但它不是原整數(shù)規(guī)劃的最優(yōu)解

5、但它不是原整數(shù)規(guī)劃的最優(yōu)解.若通過四舍五入的辦法，若通過四舍五入的辦法， 得解為得解為x1=5 x2=0但它不是可行解但它不是可行解故這種辦法不可取的故這種辦法不可取的若通過取整的辦法，若通過取整的辦法， 得解為得解為x1=4 x2=0,z=80但有解但有解x1=4 x2=1,z=90整數(shù)規(guī)劃的常見解法：整數(shù)規(guī)劃的常見解法：整數(shù)規(guī)劃（整數(shù)規(guī)劃（5）二、割平面法：常用于求解純整數(shù)規(guī)劃問題二、割平面法：常用于求解純整數(shù)規(guī)劃問題一、分支定界法：可用于求解純整數(shù)或混合整數(shù)規(guī)劃問一、分支定界法：可用于求解純整數(shù)或混合整數(shù)規(guī)劃問題；題；解法的基本思想：解法的基本思想：(1)通過求解線性規(guī)劃問題來求得整數(shù)線

6、性規(guī)劃問題的最通過求解線性規(guī)劃問題來求得整數(shù)線性規(guī)劃問題的最優(yōu)解；優(yōu)解；(2)在使沒有整數(shù)約束的可行域以在使沒有整數(shù)約束的可行域以“割掉非整數(shù)解，保割掉非整數(shù)解，保留需要的所有的整數(shù)可行解留需要的所有的整數(shù)可行解”的原則來壓縮可行域。的原則來壓縮可行域。2.整數(shù)規(guī)劃的解法一整數(shù)規(guī)劃的解法一通過例子來說明分支定界解法的步驟通過例子來說明分支定界解法的步驟分支定界解法分支定界解法解解: 先不考慮條件先不考慮條件(5)例例即解相應的線性規(guī)劃即解相應的線性規(guī)劃(1)-(4)的最優(yōu)解的最優(yōu)解1212121212max4090 .(1)9756.(2)72070.(3).0,0,.(4),.(5)zxxx

7、xxxstxxx x 整數(shù)分支定界解法分支定界解法(1)稱為原問題的松馳問題稱為原問題的松馳問題用單純形法解上述問題得用單純形法解上述問題得 x1=4.809,x2=1.817， z=355.89又又由于當由于當x1=x2=0時，是原規(guī)劃的一個整數(shù)可時，是原規(guī)劃的一個整數(shù)可行解，而此時行解，而此時z0。12121212max4090.(1)9756.(2). . 72070.(3)0,0,.(4)zxxxxstxxxx因此，原問題的最優(yōu)值滿足：因此，原問題的最優(yōu)值滿足： 0z*355這就是這就是分支定界解法中的定界含義分支定界解法中的定界含義。分支定界解法分支定界解法(2)9x1+7x2=56

8、7x1+20 x2=70 x x2 22 210108 86 64 42 2A AC CB B0 0 x x1 1z40 x1+90 x2由于最優(yōu)解是非整數(shù)，由于最優(yōu)解是非整數(shù)，首先注意其中一個非首先注意其中一個非整數(shù)變量整數(shù)變量(可任選可任選),例例如如x1=4.809，我們可認為整數(shù)最優(yōu)我們可認為整數(shù)最優(yōu)解解x1是是x1 4或或x1 5,而而在在4和和5 之間是不合整之間是不合整數(shù)條件的數(shù)條件的,于是把原問于是把原問題分解成兩支題分解成兩支,各支都各支都增加了約束條件增加了約束條件:即區(qū)域也分成兩塊即區(qū)域也分成兩塊R1和和R2最優(yōu)解：最優(yōu)解： x1=4.809,x2=1.817， z=35

9、5.89R2R1這就是這就是分支定界解法分支定界解法中的分支含義中的分支含義分支定界解法分支定界解法(3)9x1+7x2=567x1+20 x2=70 x x2 22 210108 86 64 42 2A AC CB B0 0 x x1 1z40 x1+90 x2R2R1這就是這就是分支定界解法分支定界解法中的分支含義中的分支含義1212121211max4090.(1)9756.(2)72070.(3). .0,0,.(4)4.(6)zxxxxxxstxxx問題1212121212max4090.(1)9756.(2)72070.(3). .0,0,.(4)5.(7)zxxxxxxs txx

10、x問 題分支定界解法分支定界解法(4)1212121211max4090.(1)9756.(2)72070.(3). .0,0,.(4)4.(6)zxxxxxxs txxx問題1212121212max4090.(1)9756.(2)72070.(3). .0,0,.(4)5.(7)zxxxxxxs txxx問題問題問題1有有 x1=4, x2=2.1 z1=349.0問題問題2有有 x1=5, x2=1.571 z2=341.39由于沒有得到整數(shù)最優(yōu)解由于沒有得到整數(shù)最優(yōu)解,繼續(xù)分解繼續(xù)分解問題問題(1) 和問題和問題(2)0z*349分支定界解法分支定界解法(5)先分解問題先分解問題(1)

11、問題問題(3)有有 x1=4, x2=2 z3=340問題問題(4)有有 x1=1.428, x2=3 z4=327.121212121212(3)max4090.(1)9756.(2)72070.(3). .0,0,.(4)4.(6)2.(8)zxxxxxxs txxxx問題1212121212(4)max4090.(1)9756.(2)72070.(3). .0,0,.(4)4.(6)3.(9)zxxxxxxs txxxx問題問題問題1有有 x1=4, x2=2.1 z1=349.0340z*341分支定界解法分支定界解法(6)因為因為問題（問題（3）的最優(yōu)解是整數(shù)解，最優(yōu)值為）的最優(yōu)解是

12、整數(shù)解，最優(yōu)值為340但我們但我們可以肯定可以肯定, ,原問題的最優(yōu)解原問題的最優(yōu)解不會在問題不會在問題(4)(4)中中, ,那么該整數(shù)解是否為原問題的最優(yōu)解？那么該整數(shù)解是否為原問題的最優(yōu)解？對問題對問題(2)進行分解進行分解,得問題得問題(5)和問題和問題(6)：所以所以問題問題(4)(4)不必去分解了不必去分解了. .原問題的最優(yōu)解原問題的最優(yōu)解可能在問題可能在問題(2)(2)中中, ,因為問題因為問題(2)(2)的最優(yōu)值大于的最優(yōu)值大于340340這是因為這是因為, ,問題問題(4)(4)的最優(yōu)值小于問題的最優(yōu)值小于問題(3)(3)的最優(yōu)值的最優(yōu)值分支定界解法分支定界解法(7) 問題問

13、題(5)有有 x1=5.44, x2=1 , z5=308問題問題(6) 無可行解無可行解12121212125max4090.(1)9756.(2)72070.(3). .0,0,.(4)5.(7)1.(10)zxxxxxxs txxxx問題12121212126max4090.(1)9756.(2)72070.(3). .0,0,.(4)5.(7)2.(11)zxxxxxxs txxxx問題原問題的最優(yōu)解不會在問題原問題的最優(yōu)解不會在問題(5)(5)和和(6)(6)中中, ,這是因為問題這是因為問題(5)(5)的最優(yōu)值小于的最優(yōu)值小于340, 340, (6)沒有可行解沒有可行解原問題的最

14、優(yōu)解原問題的最優(yōu)解: x1=4, x2=2, 最優(yōu)值最優(yōu)值: z*=340原問題的松馳問題：原問題的松馳問題： x1=4.809,x2=1.817， z=355.89分支定界解法分支定界解法(8) 因此，原問題的最優(yōu)解因此，原問題的最優(yōu)解:x1=4, x2=2,最優(yōu)值最優(yōu)值: z*=340問題問題1 z1=349.0 x1=4, x2=2.1問題問題2 z2=341.39 x1=5, x2=1.571問題問題3x1=4, x2=2 z3=340問題問題4x1=1.428x2=3 z4=327.12問題問題5 x1=5.44 x2=1 z5=308問題問題6 無可行解無可行解41x51x22x3

15、2x12x22x(2)用單純形法解用單純形法解(IPL);分支定界解法的步驟分支定界解法的步驟(3)若求得若求得(IPL)的最優(yōu)解的最優(yōu)解, (1)稱原整數(shù)規(guī)劃問題為稱原整數(shù)規(guī)劃問題為(IP)稱相應的線性規(guī)劃稱相應的線性規(guī)劃(即不考慮整數(shù)條件即不考慮整數(shù)條件)為為松馳問題松馳問題(IPL)若若(IPL)沒有可行解沒有可行解 ,則則(IP)也沒可行解也沒可行解. .檢查它檢查它是否符合整數(shù)條件是否符合整數(shù)條件, 若符合整數(shù)條件若符合整數(shù)條件,它就是問題它就是問題(IP)的最優(yōu)解的最優(yōu)解; 否則轉(zhuǎn)否則轉(zhuǎn)(4)(4)在在(IPL)的解中的解中,任選一個不符整數(shù)條件的變量任選一個不符整數(shù)條件的變量xj

16、, (i)xj bj , (ii)xj bj +1不考慮整數(shù)條件不考慮整數(shù)條件,分別求解這兩個后繼問題分別求解這兩個后繼問題(5)在現(xiàn)有的且還沒有分解后繼問題的各可行問題中在現(xiàn)有的且還沒有分解后繼問題的各可行問題中,選目標選目標 函數(shù)為最優(yōu)的問題函數(shù)為最優(yōu)的問題,重新稱這個問題為重新稱這個問題為(IPL), 轉(zhuǎn)轉(zhuǎn)(3)重復進行重復進行若若xj=bj非整非整; 作兩個后繼問題作兩個后繼問題,它們是對它們是對(IPL)分別各增加一個分別各增加一個約束條件約束條件: 分支定界解法的注釋分支定界解法的注釋(1)在用單純形法繼續(xù)求解后繼問題時，可借助上一級終表添在用單純形法繼續(xù)求解后繼問題時，可借助上一

17、級終表添加約束條件進一步計算，借助單純形法或?qū)ε紗渭冃畏ㄟM行加約束條件進一步計算，借助單純形法或?qū)ε紗渭冃畏ㄟM行計算；計算；(2)對分支中最優(yōu)值較大者先分支，得到整數(shù)解的后繼問題不必對分支中最優(yōu)值較大者先分支，得到整數(shù)解的后繼問題不必繼續(xù)分支；對最優(yōu)值低于目前下界的后繼問題不必繼續(xù)分支；繼續(xù)分支；對最優(yōu)值低于目前下界的后繼問題不必繼續(xù)分支；無可行解的后繼問題不必繼續(xù)分支；當所有后繼問題都無法繼無可行解的后繼問題不必繼續(xù)分支；當所有后繼問題都無法繼續(xù)分支時，最優(yōu)解才得到。續(xù)分支時，最優(yōu)解才得到。3.整數(shù)規(guī)劃的解法二整數(shù)規(guī)劃的解法二考慮純整數(shù)規(guī)劃問題：考慮純整數(shù)規(guī)劃問題：設其中設其中aij(i=1

18、,2,m;j=1,2,n)和和bi(i=1,2,m)皆為整數(shù)皆為整數(shù)（若不為整數(shù)，可乘上一個倍數(shù)化為整數(shù)）（若不為整數(shù)，可乘上一個倍數(shù)化為整數(shù)）割平面法：11max1,2,. .01,2,1,2,njjjnijjijjjzc xa xbimstxjnxjn 取整數(shù)(2)用單純形法解用單純形法解(IPL);3.整數(shù)規(guī)劃的解法二整數(shù)規(guī)劃的解法二(3)若求得若求得(IPL)的最優(yōu)解的最優(yōu)解, 1.(1)稱原整數(shù)規(guī)劃問題為稱原整數(shù)規(guī)劃問題為(IP)稱相應的線性規(guī)劃稱相應的線性規(guī)劃(即不考慮整數(shù)條件即不考慮整數(shù)條件)為為松馳問題松馳問題(IPL)若若(IPL)沒有可行解沒有可行解 ,則則(IP)也沒可行

19、解也沒可行解. .檢查它檢查它是否符合整數(shù)條件是否符合整數(shù)條件, 若符合整數(shù)條件若符合整數(shù)條件,它就是問題它就是問題(IP)的最優(yōu)解的最優(yōu)解; 否則轉(zhuǎn)否則轉(zhuǎn)2割平面法的步驟：2.(1)令xi是(IPL)的最優(yōu)解中取值為非整的一個的最優(yōu)解中取值為非整的一個基變量，基變量，由單純形終由單純形終表可得：表可得： 1iijjij Lxxb iK其中K為基變量下標集合，L為非基變量下標集合割平面法的步驟（割平面法的步驟（2）(2)將 和ij都分解成整數(shù)部分N和非整真分數(shù)f之和，即：ib +1213iiiiijijijijbNffNff 其中0其中0將(2),(3)代入(1)整理，移項，得 4iijjii

20、ijjj Lj LxN xNff x(3)考慮整數(shù)約束，(4)式由左邊看是整數(shù)，且0fi0，由這些元素構(gòu)成的矩陣為，由這些元素構(gòu)成的矩陣為效率矩陣效率矩陣令令 則指派問題的數(shù)學模型則指派問題的數(shù)學模型 01jix11,2,.,. .11,2,.,10ijijijijiijjijminzc xxjnstxinx或表示指派第表示指派第i個人去完成第個人去完成第j項任務項任務 表示不指派第表示不指派第i個人去完成第個人去完成第j項任務項任務 指派問題（指派問題（4）指派問題是指派問題是0-1規(guī)劃的特例，也是運輸問題的特例。規(guī)劃的特例，也是運輸問題的特例。指派問題的一個可行指派問題的一個可行解可用一個

21、矩陣表示：解可用一個矩陣表示：稱之為稱之為解矩陣解矩陣若從系數(shù)矩陣（若從系數(shù)矩陣（cij）的一行（列）各元素中分別減去）的一行（列）各元素中分別減去該行（列）的最小數(shù)，得到新矩陣（該行（列）的最小數(shù)，得到新矩陣（bij），則以（），則以（bij）為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。解相同。利用此性質(zhì)利用此性質(zhì)，可使原系數(shù)矩陣變換為含有很多，可使原系數(shù)矩陣變換為含有很多0元素元素的新系數(shù)矩陣，而最優(yōu)解保持不變。我們稱的新系數(shù)矩陣，而最優(yōu)解保持不變。我們稱系數(shù)矩陣系數(shù)矩陣中位于不同行不同列的中位于不同行不同列的0元素為元素為獨立的獨立

22、的0元素元素。1000000101000010)(ijx指派問題的最優(yōu)解的性質(zhì)：指派問題的最優(yōu)解的性質(zhì)：指派問題（指派問題（5）如下的系數(shù)矩陣中如下的系數(shù)矩陣中存在存在4個獨立的個獨立的0元素元素若能在系數(shù)矩陣（若能在系數(shù)矩陣（bij）中能找出）中能找出n個獨立的個獨立的0元素，則元素，則令解矩陣（令解矩陣（xij）中對應這）中對應這n個獨立的個獨立的0元素的元素取元素的元素取1，其余元素取其余元素取0，1790068193088015B00100100()00011000ijXx將其代入目標函數(shù)中得到將其代入目標函數(shù)中得到zb=0，它一定是最小。，它一定是最小。這就是以這就是以B為系數(shù)矩陣的

23、指派問題的最優(yōu)解為系數(shù)矩陣的指派問題的最優(yōu)解，也得，也得到原問題的最優(yōu)解。到原問題的最優(yōu)解。指派問題（指派問題（6）1955年年庫恩（庫恩（W.W.Kuhn）提出了指派問題的解法。）提出了指派問題的解法。他引用了匈牙利數(shù)學家康尼格（他引用了匈牙利數(shù)學家康尼格（D.Konig）一個）一個關(guān)于矩陣中關(guān)于矩陣中0元素的定理：元素的定理：系數(shù)矩陣中的獨立系數(shù)矩陣中的獨立0元素的最多個數(shù)等于能覆蓋所有元素的最多個數(shù)等于能覆蓋所有0元素的最少的直線數(shù)目。元素的最少的直線數(shù)目。所以稱此解法為所以稱此解法為匈牙利解法。匈牙利解法。下面我們介紹匈牙利解法的步驟：下面我們介紹匈牙利解法的步驟：匈牙利解法匈牙利解法

24、第一步：使系數(shù)矩陣出現(xiàn)第一步：使系數(shù)矩陣出現(xiàn)0元素元素 (A)從系數(shù)矩陣的每行元素減去該行的最小元素從系數(shù)矩陣的每行元素減去該行的最小元素;(B)再從所得系數(shù)矩陣的每列元素中減去該列的最小元素再從所得系數(shù)矩陣的每列元素中減去該列的最小元素; 由由0元素最少的行元素最少的行(或列或列)開始開始,圈出一個圈出一個0 元素元素,用用表示表示,然后劃去同行同列的然后劃去同行同列的0元素元素,用用 表示表示,這樣這樣依次做完各行各列依次做完各行各列,已劃去就不能再圈已劃去就不能再圈,第二步：試求最優(yōu)解第二步：試求最優(yōu)解如果能得到如果能得到n個個,這就完成了求最優(yōu)解的過程這就完成了求最優(yōu)解的過程;第三步：

25、作能覆蓋所有第三步：作能覆蓋所有0元素的最少數(shù)目的直線集合元素的最少數(shù)目的直線集合如果圈出的如果圈出的不夠不夠n個個,則轉(zhuǎn)則轉(zhuǎn)(3)匈牙利解法匈牙利解法 (A)對沒有對沒有的的行打行打 號號;(B)在已打在已打 號號的行中，對的行中，對 所在列打所在列打 號號;(C)在已打在已打 號號的列中，對的列中，對所在行打所在行打 號號;(D)重復重復(B)(C),直到再也找不到可以打直到再也找不到可以打 號的行或列為止號的行或列為止;(E)對沒有打?qū)]有打 號的行畫橫線號的行畫橫線,所有打所有打 的列畫縱線的列畫縱線,這樣就這樣就得到了覆蓋所有零元素的最少直線數(shù)目的直線集合得到了覆蓋所有零元素的最少直

26、線數(shù)目的直線集合.第四步：第四步：在沒有被直線覆蓋的部分中在沒有被直線覆蓋的部分中找出最小元素找出最小元素,然后然后 對沒畫直線的行的各元素都對沒畫直線的行的各元素都減去減去這最小元素這最小元素, 對畫直線的列的各元素對畫直線的列的各元素都加上都加上這最小元素這最小元素, 這樣得到新的系數(shù)矩陣這樣得到新的系數(shù)矩陣;若有若有n個不同行不同列的個不同行不同列的0 元素元素,則求解過程完成則求解過程完成;若沒有若沒有n個不同行不同列的個不同行不同列的0元素元素,轉(zhuǎn)轉(zhuǎn)第三步第三步執(zhí)行執(zhí)行.匈牙利解法匈牙利解法(舉例舉例1)例例1 1 解解: :91187131614915144104131527942

27、242410475011100621113000102350960607130甲譯俄文；乙譯日文；丙譯英文；丁譯德文甲譯俄文；乙譯日文；丙譯英文；丁譯德文總的花費時間為總的花費時間為28 由于已有由于已有4個個獨立獨立0元素，元素，故最優(yōu)解為：故最優(yōu)解為：0100000100101000*X匈牙利解法匈牙利解法(舉例舉例2) 例例2 求下表所示效率矩陣的指派問題的最小解求下表所示效率矩陣的指派問題的最小解。解：解：6667491071041066141591412177666989797123341304007113861030002431308匈牙利解法匈牙利解法(舉例舉例2) 341304

28、00711053700002431308最后一個矩陣中，已得到最后一個矩陣中，已得到5個獨立個獨立0元素元素，則得最優(yōu)解為：則得最優(yōu)解為：341304007110537000024313080000100100100000100000010*X匈牙利解法匈牙利解法(舉例舉例2)最優(yōu)方案為：最優(yōu)方案為： 甲甲B B 乙乙D D 丙丙E E 丁丁C C 戊戊A A 或或甲甲B B 乙乙C C 丙丙E E 丁丁D D 戊戊A A總的耗費時間為總的耗費時間為32個單位。個單位。467679107104106614159141217766698979712匈牙利解法匈牙利解法(舉例舉例2) 解解2：56

29、360400892751000003220205 (A)對沒有對沒有的的行打行打 號號;(B)在已打在已打 號號的行中，對的行中，對 所在列打所在列打 號號;(C)在已打在已打 號號的列中，對的列中，對所在行打所在行打 號號;(D)重復重復(B)(C),直到再也找不到可以打直到再也找不到可以打 號的行或列為止號的行或列為止;(E)對沒有打?qū)]有打 號的行畫橫線號的行畫橫線,所有打所有打 的列畫縱線的列畫縱線,這樣就得這樣就得到了覆蓋所有零元素的最少直線數(shù)目的直線集合到了覆蓋所有零元素的最少直線數(shù)目的直線集合. 匈牙利解法匈牙利解法(舉例舉例2)70 2 0243 0 0008 3501 1 8

30、0 0 404 143(4)在沒有被直線覆蓋的部分中找出最小元素在沒有被直線覆蓋的部分中找出最小元素,然后然后, 對沒對沒畫直線的行的各元素都減去這最小元素畫直線的行的各元素都減去這最小元素, 對畫直線的列對畫直線的列的各元素都加上這最小元素的各元素都加上這最小元素, 這樣得到新的系數(shù)矩陣這樣得到新的系數(shù)矩陣; 56360400892751000003220205 第3,5行各元素減去2第1列各元素加上2匈牙利解法匈牙利解法(舉例舉例2)最優(yōu)方案為：最優(yōu)方案為： 甲甲B B 乙乙D D 丙丙E E 丁丁D D 戊戊A A 或或 甲甲B B 乙乙C C 丙丙E E 丁丁C C 戊戊A A最后一個

31、矩陣中，已得到最后一個矩陣中，已得到5個獨立個獨立0元素，則得最優(yōu)解為：元素，則得最優(yōu)解為：總的耗費時間為總的耗費時間為32個單位。個單位。0000100100100000100000010*X二極大化的指派問題二極大化的指派問題極大化指派問題極大化指派問題的數(shù)學模型的數(shù)學模型 11,2,.,. .11,2,.,10ijijijijiijjijMaxzc xxjnstxinx或需把它化為極小化問題需把它化為極小化問題但不能象線性規(guī)劃問題那樣，令目標函數(shù)的相反數(shù)但不能象線性規(guī)劃問題那樣，令目標函數(shù)的相反數(shù)此時令此時令 bij=M-cij 其中其中M是足夠大的常數(shù)是足夠大的常數(shù)則系數(shù)矩陣變?yōu)閯t系數(shù)

32、矩陣變?yōu)?B=（bij） bij0符合匈牙利解法的條件符合匈牙利解法的條件 ，這是因為，這是因為 二極大化的指派問題二極大化的指派問題(2)ijijijijijijxcMxb)(因為因為 iijijijijxcMxiijijxcnM因因nM是常數(shù)，所以當是常數(shù)，所以當 ijijijxb取得最小時，取得最小時， iijijxc便為最大。便為最大。 二極大化的指派問題二極大化的指派問題(3)例例 求系數(shù)矩陣為求系數(shù)矩陣為C的最大指派問題的最大指派問題 8118713161491514410413152C解：解：因因C中最大元素為中最大元素為16，故取，故取M16，令，令 則以則以C為系數(shù)矩陣的最大

33、化指派問題和以為系數(shù)矩陣的最大化指派問題和以B為系數(shù)矩為系數(shù)矩陣的最小化指派問題有相同的最優(yōu)解。陣的最小化指派問題有相同的最優(yōu)解。 816111681671613161616141691615161416416101641613161516216B14 1 3 126 122 17203985 8三人數(shù)和事數(shù)不等的指派問題三人數(shù)和事數(shù)不等的指派問題(1)若人少事多若人少事多這樣人數(shù)和事數(shù)不等的問題轉(zhuǎn)化為相等的情形這樣人數(shù)和事數(shù)不等的問題轉(zhuǎn)化為相等的情形,則可用匈牙利法求解了則可用匈牙利法求解了.則添上一些虛擬的則添上一些虛擬的“人人”。這些虛擬的這些虛擬的“人人”做各事的費用系數(shù)可做各事的費用系數(shù)可取取0這些費用可理解為實際上不會發(fā)生。這些費用可理解為實際上不會發(fā)生。(2)若人多事少若人多事少則添上一些虛擬的則添上一些虛擬的“事事”。這些虛擬的這些虛擬的“事事”被各人做的費用系數(shù)同樣取被各人做的費用系數(shù)同樣取0。四一個人可做幾件事的指派問題四一個人可做幾件事的指派問題若某個人可做幾件事若某個人可做幾件事則則可將該人化作相同的幾個可將該人化作相同的幾個“人人”來接受指派。來接受指派。這幾個這幾個“人人”做一件事的費用系數(shù)當然也取一樣做一件事的費用系數(shù)當然也取一樣。五某事一定不能由某人做的指派問題五某事一定不能由某人做的指派問題若某事一定不能由某個人做，若某事一定不能由某個人做，