第4章整數(shù)規(guī)劃

1、Chap 4-1 整數(shù)規(guī)劃問(wèn)題的解法概述1整數(shù)規(guī)劃問(wèn)題數(shù)學(xué)模型整數(shù)規(guī)劃問(wèn)題數(shù)學(xué)模型整數(shù)規(guī)劃（Integer Programming）IP最近發(fā)展起來(lái)的規(guī)劃論中的一個(gè)分支，是數(shù)學(xué)規(guī)劃的一個(gè)重要分支，研究的是一類要求其部分或全部變量取整數(shù)的最優(yōu)性問(wèn)題。本內(nèi)容研究是整數(shù)線性規(guī)劃問(wèn)題。整數(shù)規(guī)劃的分類：全整數(shù)規(guī)劃（純整數(shù)規(guī)劃全整數(shù)規(guī)劃（純整數(shù)規(guī)劃）混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃整數(shù)規(guī)劃的數(shù)學(xué)模型), 2 , 1( , ) ( 1mibxanjijijnjjjxc1 zmin max / 且為整數(shù), 0 jx目標(biāo)函數(shù)約束條件變量限制條件整數(shù)線性規(guī)劃一般簡(jiǎn)稱為整數(shù)規(guī)劃2.用單純形法求得的解用單純形法求得的解“舍入

2、化整舍入化整”為為整數(shù)不一定是可行解或整數(shù)最優(yōu)解整數(shù)不一定是可行解或整數(shù)最優(yōu)解 舉例：某廠擬用集裝箱托運(yùn)甲、乙兩種舉例：某廠擬用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲得的利潤(rùn)貨物，每箱的體積、重量、可獲得的利潤(rùn)及托運(yùn)的限制如下表：及托運(yùn)的限制如下表： 問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)最大？問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)最大？ 貨物體積重量利潤(rùn)甲5220乙4510托運(yùn)限制2413 ?如何求解如何求解IP解：設(shè)x1，x2分別為甲、乙兩種貨物托運(yùn)箱數(shù)。用數(shù)學(xué)式可表達(dá)如下： (5) 2 x,1 x (4) 02 x,1x (3) 132x512x (2) 242x415x (1)

3、2x101x20zmax為整數(shù)解其LPP(1)-(4)，得最優(yōu)解為：x1=4.8 x2=0 max z=96 是不是可以把所得的非整數(shù)的最優(yōu)解經(jīng)過(guò)是不是可以把所得的非整數(shù)的最優(yōu)解經(jīng)過(guò)“舍舍入化整入化整”就可以得到適合于（就可以得到適合于（5）的整數(shù)最優(yōu)解）的整數(shù)最優(yōu)解呢呢？如將（如將（x1=4.8 , x2=0）湊整為（）湊整為（x1=5 ，x2=0），），這樣就破壞了條件（這樣就破壞了條件（2）的限制，因而它不是可）的限制，因而它不是可行解；行解；如將（如將（x1=4.8 , x2=0）舍尾為（）舍尾為（x1=4 , x2=0），），這當(dāng)然滿足各約束條件，因而是可行解，但不是這當(dāng)然滿足各約束

4、條件，因而是可行解，但不是最優(yōu)解，因?yàn)椋鹤顑?yōu)解，因?yàn)椋寒?dāng)（當(dāng)（x1=4 , x2=0）時(shí)，）時(shí)，z=80，當(dāng)（當(dāng)（x1=4 , x2=1）（這也是可行解）時(shí)，）（這也是可行解）時(shí)，z=90 3. 幾個(gè)基本概念1) 分解分解用用R（P）表示問(wèn)題（）表示問(wèn)題（P）的可行域，若條件）的可行域，若條件（1） （2） R(Pi) R(Pj) = (空集空集) (1ijm)成立，成立，則稱問(wèn)題（則稱問(wèn)題（P）被分解為子問(wèn)題）被分解為子問(wèn)題(P1)、(P2)、 、（Pm）之和。）之和。 最常用的分解方式是兩分法。最常用的分解方式是兩分法。),()(1PRiPRmiU2) 衍生衍生由原來(lái)問(wèn)題按某種方式產(chǎn)生出來(lái)

5、的問(wèn)題稱由原來(lái)問(wèn)題按某種方式產(chǎn)生出來(lái)的問(wèn)題稱為原來(lái)問(wèn)題的衍生問(wèn)題，每個(gè)衍生問(wèn)題都有為原來(lái)問(wèn)題的衍生問(wèn)題，每個(gè)衍生問(wèn)題都有一個(gè)母問(wèn)題（產(chǎn)生此衍生問(wèn)題的直接前輩）。一個(gè)母問(wèn)題（產(chǎn)生此衍生問(wèn)題的直接前輩）。衍生問(wèn)題的性質(zhì)：衍生問(wèn)題中至少有一個(gè)衍生問(wèn)題的性質(zhì)：衍生問(wèn)題中至少有一個(gè)與母問(wèn)題有相同的最優(yōu)解。與母問(wèn)題有相同的最優(yōu)解。如果母問(wèn)題具有多個(gè)最優(yōu)解，則應(yīng)要求其如果母問(wèn)題具有多個(gè)最優(yōu)解，則應(yīng)要求其最優(yōu)解集的某一個(gè)非空子集必須是組成它的最優(yōu)解集的某一個(gè)非空子集必須是組成它的衍生問(wèn)題之一的最優(yōu)解。衍生問(wèn)題之一的最優(yōu)解。常用的衍生方法常用的衍生方法 ：分枝、切割：分枝、切割3) 松馳（松馳（Relaxati

6、on）對(duì)問(wèn)題對(duì)問(wèn)題P，記舍棄，記舍棄P的某些約束條件后所得的某些約束條件后所得的問(wèn)題為的問(wèn)題為P，則稱，則稱P為為P的松馳問(wèn)題。的松馳問(wèn)題。在整數(shù)線性規(guī)劃問(wèn)題中，通常是刪去自變量在整數(shù)線性規(guī)劃問(wèn)題中，通常是刪去自變量為整數(shù)這一要求而得到其松馳問(wèn)題，之所以要為整數(shù)這一要求而得到其松馳問(wèn)題，之所以要構(gòu)造如此松馳線性規(guī)劃問(wèn)題，是因?yàn)樗神Y問(wèn)題構(gòu)造如此松馳線性規(guī)劃問(wèn)題，是因?yàn)樗神Y問(wèn)題的解空間是連續(xù)的（凸集），解法要比原整數(shù)的解空間是連續(xù)的（凸集），解法要比原整數(shù)規(guī)劃簡(jiǎn)單多，可用單純形法。規(guī)劃簡(jiǎn)單多，可用單純形法。 松馳問(wèn)題的性質(zhì)：松馳問(wèn)題的性質(zhì)：A、 若松馳問(wèn)題若松馳問(wèn)題沒(méi)有可行解沒(méi)有可行解，則原問(wèn)題也

7、一，則原問(wèn)題也一定沒(méi)有可行解；定沒(méi)有可行解；B 、松馳問(wèn)題目標(biāo)函數(shù)的最優(yōu)值給出原問(wèn)題、松馳問(wèn)題目標(biāo)函數(shù)的最優(yōu)值給出原問(wèn)題目標(biāo)函數(shù)最優(yōu)值的一個(gè)目標(biāo)函數(shù)最優(yōu)值的一個(gè)上上(下下)界界。具體來(lái)講就是，對(duì)極大具體來(lái)講就是，對(duì)極大(小小)化目標(biāo)函數(shù)而言，化目標(biāo)函數(shù)而言，P的目標(biāo)函數(shù)的極大的目標(biāo)函數(shù)的極大(小小)值不大于值不大于(小于小于)P目標(biāo)目標(biāo)函數(shù)的極大函數(shù)的極大(小小)值。值。C、 若松馳問(wèn)題的某個(gè)最優(yōu)解是原問(wèn)題的可若松馳問(wèn)題的某個(gè)最優(yōu)解是原問(wèn)題的可行解，則它也原問(wèn)題的一個(gè)行解，則它也原問(wèn)題的一個(gè)最優(yōu)解最優(yōu)解。 4.求解整數(shù)規(guī)劃問(wèn)題的一般框架求解整數(shù)規(guī)劃問(wèn)題的一般框架 A 、逐次生成一個(gè)個(gè)原問(wèn)題的衍

8、生問(wèn)題，對(duì)、逐次生成一個(gè)個(gè)原問(wèn)題的衍生問(wèn)題，對(duì)每個(gè)衍生問(wèn)題又伴隨一個(gè)比它更容易求解的松每個(gè)衍生問(wèn)題又伴隨一個(gè)比它更容易求解的松馳問(wèn)題（衍生問(wèn)題稱為松馳問(wèn)題的原問(wèn)題）馳問(wèn)題（衍生問(wèn)題稱為松馳問(wèn)題的原問(wèn)題）B、 通過(guò)松馳問(wèn)題的解來(lái)確定它的原問(wèn)題歸通過(guò)松馳問(wèn)題的解來(lái)確定它的原問(wèn)題歸宿，即其原問(wèn)題已被解決（包括已得整數(shù)解或宿，即其原問(wèn)題已被解決（包括已得整數(shù)解或被舍棄）呢，還是要再生成一個(gè)或多個(gè)它的衍被舍棄）呢，還是要再生成一個(gè)或多個(gè)它的衍生問(wèn)題來(lái)替代。生問(wèn)題來(lái)替代。C 、再選擇一個(gè)至此尚未被舍或得解的原問(wèn)、再選擇一個(gè)至此尚未被舍或得解的原問(wèn)題的衍生問(wèn)題，重復(fù)以上步驟直至不再剩有未題的衍生問(wèn)題，重復(fù)以

9、上步驟直至不再剩有未解決的衍生問(wèn)題為止。解決的衍生問(wèn)題為止。 Chap 4-2 分枝定界法窮舉法窮舉法求小型整數(shù)規(guī)劃問(wèn)題求小型整數(shù)規(guī)劃問(wèn)題1、分枝定界法的基本思路、分枝定界法的基本思路設(shè)有最大化的整數(shù)規(guī)劃問(wèn)題設(shè)有最大化的整數(shù)規(guī)劃問(wèn)題A，與它相應(yīng)的線，與它相應(yīng)的線性規(guī)劃為問(wèn)題性規(guī)劃為問(wèn)題B（松馳問(wèn)題），從解問(wèn)題（松馳問(wèn)題），從解問(wèn)題B開(kāi)始，開(kāi)始，若其最優(yōu)解不符合若其最優(yōu)解不符合A的整數(shù)條件，那么的整數(shù)條件，那么B的最優(yōu)目的最優(yōu)目標(biāo)函數(shù)必是標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù)的最優(yōu)目標(biāo)函數(shù)z*的上界，記為的上界，記為 而而A的任意可行解的目標(biāo)函數(shù)值將是的任意可行解的目標(biāo)函數(shù)值將是z*的一個(gè)下界的一個(gè)下界Z。

10、分枝定界法就是將分枝定界法就是將B的可行域分成子區(qū)域（稱為的可行域分成子區(qū)域（稱為分枝分枝衍生方法）的方法，逐步減少上界和增加下衍生方法）的方法，逐步減少上界和增加下界，最終求得界，最終求得z*。 Z2、分枝定界法的計(jì)算步驟 假定要求解的問(wèn)題是極大化問(wèn)題，其計(jì)算步驟為：假定要求解的問(wèn)題是極大化問(wèn)題，其計(jì)算步驟為：第一步：任找一整數(shù)可行解，算出其目標(biāo)函數(shù)值，第一步：任找一整數(shù)可行解，算出其目標(biāo)函數(shù)值，以這個(gè)值為目標(biāo)函數(shù)最優(yōu)值現(xiàn)時(shí)的下界以這個(gè)值為目標(biāo)函數(shù)最優(yōu)值現(xiàn)時(shí)的下界Z。然后，解該整數(shù)規(guī)劃對(duì)應(yīng)的線性規(guī)劃問(wèn)題，即其松然后，解該整數(shù)規(guī)劃對(duì)應(yīng)的線性規(guī)劃問(wèn)題，即其松馳問(wèn)題。若松馳問(wèn)題的最優(yōu)解滿足整數(shù)條件

11、，這個(gè)解馳問(wèn)題。若松馳問(wèn)題的最優(yōu)解滿足整數(shù)條件，這個(gè)解就是原來(lái)整數(shù)規(guī)劃問(wèn)題的最優(yōu)解；就是原來(lái)整數(shù)規(guī)劃問(wèn)題的最優(yōu)解；若松馳問(wèn)題的最優(yōu)解不滿足整數(shù)條件，則轉(zhuǎn)下一步。若松馳問(wèn)題的最優(yōu)解不滿足整數(shù)條件，則轉(zhuǎn)下一步。這時(shí)目標(biāo)函數(shù)值，給出原整數(shù)規(guī)劃問(wèn)題最優(yōu)目標(biāo)函這時(shí)目標(biāo)函數(shù)值，給出原整數(shù)規(guī)劃問(wèn)題最優(yōu)目標(biāo)函數(shù)值的現(xiàn)時(shí)的一個(gè)上界。數(shù)值的現(xiàn)時(shí)的一個(gè)上界。z至此，完成了第一步至此，完成了第一步“定界定界”工作，并且有工作，并且有Zz* Z第二步：第二步： 將整數(shù)規(guī)劃問(wèn)題衍生為兩個(gè)子問(wèn)將整數(shù)規(guī)劃問(wèn)題衍生為兩個(gè)子問(wèn)題，即進(jìn)行題，即進(jìn)行“分枝分枝”。（形成樹(shù)狀圖）。（形成樹(shù)狀圖）由松馳問(wèn)題最優(yōu)解的非整數(shù)分量中選取一由松

12、馳問(wèn)題最優(yōu)解的非整數(shù)分量中選取一要求取整的分量，假定它為要求取整的分量，假定它為xj，其值等于，其值等于bj，用下述方法構(gòu)造兩個(gè)子問(wèn)題：在上面整數(shù)用下述方法構(gòu)造兩個(gè)子問(wèn)題：在上面整數(shù)規(guī)劃問(wèn)題中分別增加以下兩個(gè)約束條件之一規(guī)劃問(wèn)題中分別增加以下兩個(gè)約束條件之一1.xj bj2.xj bj+1 其中，其中， bj為數(shù)值不大于為數(shù)值不大于bj的最大整數(shù)的最大整數(shù)bj xj 0，故用，故用5代替代替0作為新的過(guò)濾值。作為新的過(guò)濾值。 考慮考慮(x2,x1,x3)=(0,1,0)處，處，z =3，因?yàn)椋驗(yàn)?5，檢驗(yàn)其是可行解，從而以檢驗(yàn)其是可行解，從而以8代替代替5作為新的過(guò)濾值。作為新的過(guò)濾值。 注

13、意到，注意到，z= -2x2+3x1+5x33x1+5x3=8，因此目標(biāo)函，因此目標(biāo)函數(shù)值不會(huì)超過(guò)數(shù)值不會(huì)超過(guò)8，即過(guò)濾值，即過(guò)濾值8不能再改進(jìn)。所以目標(biāo)不能再改進(jìn)。所以目標(biāo)函數(shù)的最優(yōu)值函數(shù)的最優(yōu)值z(mì)*=8，X*= (x2,x1,x3)=（0,1,1) 。上述解題過(guò)程列于下表中：(1 1 1)(1 1 0)(1 0 1)(1 0 0)85(0 1 1)35(0 1 0)50(0 0 1)0(0 0 0)(4)(3)(2)(1)Z值約束條件過(guò)濾條件解(x2,x1,x3) (新過(guò)濾值)(最后過(guò)濾值)(初過(guò)濾值)Chap 4-4 分派問(wèn)題分派問(wèn)題又稱指派問(wèn)題、分配問(wèn)題。分派問(wèn)題又稱指派問(wèn)題、分配問(wèn)題

14、。語(yǔ)言模型：有語(yǔ)言模型：有n項(xiàng)任務(wù)需完成，有項(xiàng)任務(wù)需完成，有n 個(gè)人個(gè)人可以承擔(dān)這些任務(wù)，可以承擔(dān)這些任務(wù)，由于每個(gè)的專長(zhǎng)不同，各人完成任務(wù)不同由于每個(gè)的專長(zhǎng)不同，各人完成任務(wù)不同（或所費(fèi)時(shí)間），效率也不同，（或所費(fèi)時(shí)間），效率也不同，于是產(chǎn)生應(yīng)分派哪個(gè)人去完成哪項(xiàng)任務(wù)，于是產(chǎn)生應(yīng)分派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成使完成n項(xiàng)任務(wù)的總效率最高（或所需總時(shí)項(xiàng)任務(wù)的總效率最高（或所需總時(shí)間最?。┑囊活悊?wèn)題。間最?。┑囊活悊?wèn)題。 1、分派問(wèn)題的數(shù)學(xué)模型舉例：有舉例：有5個(gè)工人，要分派他們?nèi)ネ瓿蓚€(gè)工人，要分派他們?nèi)ネ瓿?項(xiàng)工作，每人做各項(xiàng)工作所消耗的時(shí)間如項(xiàng)工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示，問(wèn)應(yīng)

15、分派哪個(gè)人去完成哪項(xiàng)工下表所示，問(wèn)應(yīng)分派哪個(gè)人去完成哪項(xiàng)工作，可使總消耗時(shí)間最?。孔?，可使總消耗時(shí)間最小？ 工作工人AB CDE156845234661355798467576574628解：要解決這個(gè)問(wèn)題，我們引入0-1變量xij，并令 否則項(xiàng)工作時(shí)；個(gè)工人完成第當(dāng)分派第, 0ji, 1xij用z表示5個(gè)工人分別完成5項(xiàng)工作所消耗的總時(shí)間，則可得出該問(wèn)題的數(shù)學(xué)模型： 5 , . .1,ji, , 1/051 5 , . .1,i 151 5 , . .1,j 1.155x144x138x126x115x zmin ?ijxjijxiijx每項(xiàng)工作只能由一人去完成每項(xiàng)工作只能由一人去完成每人只

16、能完成一項(xiàng)工作每人只能完成一項(xiàng)工作價(jià)值系數(shù)表（或效益表）- 表4-8系數(shù)矩陣（或效益矩陣）C現(xiàn)假定一分派問(wèn)題的效益矩陣的元素為cij，則其數(shù)學(xué)模型為：1/0 1 ,.1,i 1 1 ,.1,j 1 11ijcmin?ijxjnijxinijxninjijxznn模型的特點(diǎn)？模型的特點(diǎn)？特殊的特殊的0-1規(guī)劃規(guī)劃特殊的運(yùn)輸問(wèn)題特殊的運(yùn)輸問(wèn)題2、分派問(wèn)題的解法匈牙利法、分派問(wèn)題的解法匈牙利法最優(yōu)解性質(zhì)：最優(yōu)解性質(zhì)：假定假定C =(cij)為分派問(wèn)題的價(jià)值系數(shù)矩陣。為分派問(wèn)題的價(jià)值系數(shù)矩陣?，F(xiàn)將它的某一行（或某一列）的各個(gè)元素都有減現(xiàn)將它的某一行（或某一列）的各個(gè)元素都有減去一個(gè)常數(shù)去一個(gè)常數(shù)a，得

17、到一新價(jià)值系數(shù)矩陣，得到一新價(jià)值系數(shù)矩陣C=(cij)。新價(jià)值系數(shù)矩陣新價(jià)值系數(shù)矩陣C所代表的分派問(wèn)題與原價(jià)值系所代表的分派問(wèn)題與原價(jià)值系數(shù)矩陣數(shù)矩陣C所代表的分派問(wèn)題，它們的最優(yōu)解所代表的分派問(wèn)題，它們的最優(yōu)解X*相同相同（但目標(biāo)函數(shù)值不相等）。（但目標(biāo)函數(shù)值不相等）。匈牙利法的基本思路：匈牙利法的基本思路：最優(yōu)解性質(zhì)。最優(yōu)解性質(zhì)。修改價(jià)值系數(shù)矩陣的行和列，修改價(jià)值系數(shù)矩陣的行和列，使得在每行、每列至少有一個(gè)零元素。使得在每行、每列至少有一個(gè)零元素。經(jīng)過(guò)修改后，直到在不同行、不同列中經(jīng)過(guò)修改后，直到在不同行、不同列中都至少有一個(gè)零元素都至少有一個(gè)零元素(稱為獨(dú)立稱為獨(dú)立0元素元素)，就可從中

18、得到一個(gè)最優(yōu)分派方案，就可從中得到一個(gè)最優(yōu)分派方案，該最優(yōu)方案為：取獨(dú)立零元素所對(duì)應(yīng)的該最優(yōu)方案為：取獨(dú)立零元素所對(duì)應(yīng)的變量等于變量等于1，其它變量等于，其它變量等于0即分派問(wèn)題的最優(yōu)解。即分派問(wèn)題的最優(yōu)解。?如何找出如何找出n個(gè)獨(dú)立零元素個(gè)獨(dú)立零元素：匈牙利法：匈牙利法3、 匈牙利法的計(jì)算步驟Step1：通過(guò)變換使價(jià)值系數(shù)矩陣的每行、每列都：通過(guò)變換使價(jià)值系數(shù)矩陣的每行、每列都出現(xiàn)出現(xiàn)0元素元素1.從每行元素減去該行的最小元素從每行元素減去該行的最小元素2.從每列元素減去該列的最小元素從每列元素減去該列的最小元素8 2 6 4 76 7 5 7 68 9 7 5 51 6 6 4 35 4

19、8 6 5c0-4-1-5-5-26 0 4 2 51 2 0 2 13 4 2 0 00 5 5 3 21 0 4 2 11c舉例舉例Step2：以最小的：以最小的m條直線（水平或垂直的）條直線（水平或垂直的）去覆蓋（或劃去）所得價(jià)值系數(shù)矩陣中的所去覆蓋（或劃去）所得價(jià)值系數(shù)矩陣中的所有有0元素。元素。【定性方法定性方法】 -從零元素最多的行或列先劃從零元素最多的行或列先劃6 0 4 2 51 2 0 2 13 4 2 0 00 5 5 3 21 0 4 2 11cStep3、若、若m=n，停止計(jì)算，停止計(jì)算可從上述價(jià)值系數(shù)矩陣的可從上述價(jià)值系數(shù)矩陣的0元中找到一組元中找到一組位于不同行且不

20、同列的位于不同行且不同列的0元元(獨(dú)立獨(dú)立0元素元素)。令對(duì)應(yīng)于這組令對(duì)應(yīng)于這組0元位置的變量元位置的變量xij=1，其余，其余的變量的變量xij=0，就得到了一個(gè)最優(yōu)解，就得到了一個(gè)最優(yōu)解，這時(shí)用初始價(jià)值系數(shù)矩陣的元素置換相應(yīng)這時(shí)用初始價(jià)值系數(shù)矩陣的元素置換相應(yīng)的的0元并求和，就得到了目標(biāo)函數(shù)最優(yōu)值。元并求和，就得到了目標(biāo)函數(shù)最優(yōu)值。6 0 4 2 51 2 0 2 13 4 2 0 00 5 5 3 21 0 4 2 11c=1若若mn，則從未被則從未被m條直線覆蓋的元素中找出最小元素條直線覆蓋的元素中找出最小元素從所有未直線被覆蓋的元素中將它減去，并將從所有未直線被覆蓋的元素中將它減去，

21、并將這個(gè)最小元素加在同時(shí)被水平直線和垂直直線覆蓋這個(gè)最小元素加在同時(shí)被水平直線和垂直直線覆蓋的元素上，的元素上，這樣又得到了新的價(jià)值系數(shù)矩陣，然后轉(zhuǎn)回第這樣又得到了新的價(jià)值系數(shù)矩陣，然后轉(zhuǎn)回第3步（劃直線）。步（劃直線）。-1-1-1+1+1為了確定出位于不同行不同列的一組為了確定出位于不同行不同列的一組0元素元素首先從僅含一個(gè)首先從僅含一個(gè)0元素的行或列開(kāi)始元素的行或列開(kāi)始逐步定出不同行不同列的逐步定出不同行不同列的0元素位置（獨(dú)立元素位置（獨(dú)立0元元素）。素）。6 0 3 1 42 3 0 2 14 5 2 0 00 5 4 2 11 0 3 1 02cm=n,最優(yōu)最優(yōu)解為：最優(yōu)解為：x1

22、1=x25=x32=x43=x54=1,其它其它xij=0 , z*=18Step2：進(jìn)行試分派，以尋求最優(yōu)解，分別為：1.從只有一個(gè)0元素的行(或列)開(kāi)始，圈這個(gè)零元素，用表示；2.然后劃去所在列（行）的其它零元素，用表示。3.反復(fù)進(jìn)行，直到全部零元素處理完為止。4.若的數(shù)目m=n，那么分派問(wèn)題的最優(yōu)得到，最優(yōu)解為：取所有 所對(duì)應(yīng)的變量為1，其它為0；否則轉(zhuǎn)下一步。6 0 4 2 51 2 0 2 13 4 2 0 00 5 5 3 21 0 4 2 11cm=4n沒(méi)有得到 最優(yōu)解匈牙利法匈牙利法-定量方法定量方法Step3：作最小的直線覆蓋所有0元素：1.對(duì)無(wú)的行打“”；2.對(duì)打“”行上的

23、所有含0元素（0）的列打“”；3.對(duì)打“”列上含的行打“”；4.重復(fù)2.3步驟，直到得不出新的打“”的行和列為止；5.對(duì)無(wú)“”的行劃?rùn)M線，有“”的列劃豎線即得最小直線數(shù)；6 0 4 2 51 2 0 2 13 4 2 0 00 5 5 3 21 0 4 2 11c6.在未被直線覆蓋的所有元素中找出 最小元素，然后將未被直線覆蓋的元素均減去，橫豎線交叉的元素加上，其它元素不變，得新的效益矩陣，轉(zhuǎn)step2。反復(fù)進(jìn)行，直至得出最優(yōu)解。6 0 4 2 51 2 0 2 13 4 2 0 00 5 5 3 21 0 4 2 11c=15 0 3 1 41 3 0 2 13 5 2 0 00 6 5 3 20 0 3 1 02c6 0 4 2 51 2 0 2 13 4 2 0 00 5 5 3 21 0 4 2 11c=1m=n,最優(yōu)x11=x25=x32=x43=x54=1,