整數(shù)規(guī)劃演示教案

整數(shù)規(guī)劃第1節(jié)整數(shù)規(guī)劃問(wèn)題的特點(diǎn)及其作用第2節(jié)分支定界方法第3節(jié)割平面方法第4節(jié)0-1規(guī)劃第5節(jié)指派（分配）問(wèn)題整數(shù)規(guī)劃（1）§1.整數(shù)規(guī)劃問(wèn)題的提出整數(shù)規(guī)劃:若一個(gè)規(guī)劃的最優(yōu)解要求部分或全部決策變量是整數(shù)的問(wèn)題純整數(shù)規(guī)劃:整數(shù)規(guī)劃中如果所有的變量都為非負(fù)整數(shù),(PureIntegerProgramming)(IntegerProgramming),簡(jiǎn)稱(chēng)IP或稱(chēng)為全整數(shù)規(guī)劃(AllIntegerProgramming)混合整數(shù)規(guī)劃:若整數(shù)規(guī)劃中僅一部分變量限制為整數(shù),

則稱(chēng)為混合整數(shù)規(guī)劃(MixedIntegerProgramming)整數(shù)規(guī)劃（2）0--1規(guī)劃：若整數(shù)規(guī)劃中的變量都僅限制為0或1,則稱(chēng)為0--1規(guī)劃整數(shù)線(xiàn)性規(guī)劃：若整數(shù)規(guī)劃問(wèn)題的目標(biāo)函數(shù)和約束條件都是線(xiàn)性的，則稱(chēng)該整數(shù)規(guī)劃是整數(shù)線(xiàn)性規(guī)劃本章中，我們討論的主要對(duì)象是整數(shù)線(xiàn)性規(guī)劃，下面的討論中將省略線(xiàn)性二字整數(shù)規(guī)劃（3）問(wèn):兩種貨物各托運(yùn)多少箱,可使獲利最大?則其數(shù)學(xué)模型設(shè)x1,x2分別為托運(yùn)甲、乙兩種貨物的數(shù)量例1.某廠擬用集裝箱托運(yùn)甲乙兩種貨物,每箱的體積、重量、可獲利及托運(yùn)限制如下表:貨物體積重量利潤(rùn)

(每箱立方米)(每箱百斤)(每箱百元)

甲5220

乙4510托運(yùn)限制2413

它是一個(gè)純整數(shù)規(guī)劃,整數(shù)規(guī)劃（4）它與線(xiàn)性規(guī)劃的區(qū)別僅在于要求x1,x2為整數(shù)的條件則是否可以把所得的非整數(shù)的最優(yōu)解經(jīng)過(guò)”化整”來(lái)得到整數(shù)規(guī)劃的最優(yōu)解呢?易求出最優(yōu)解為x1=4.8x2=0z*=96若不考慮整數(shù)條件,則變成一個(gè)線(xiàn)性規(guī)劃問(wèn)題但它不是原整數(shù)規(guī)劃的最優(yōu)解.若通過(guò)四舍五入的辦法，得解為x1=5x2=0但它不是可行解故這種辦法不可取的若通過(guò)取整的辦法，得解為x1=4x2=0,z=80但有解x1=4x2=1,z=90整數(shù)規(guī)劃的常見(jiàn)解法：整數(shù)規(guī)劃（5）二、割平面法：常用于求解純整數(shù)規(guī)劃問(wèn)題一、分支定界法：可用于求解純整數(shù)或混合整數(shù)規(guī)劃問(wèn)題；解法的基本思想：(1)通過(guò)求解線(xiàn)性規(guī)劃問(wèn)題來(lái)求得整數(shù)線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解；(2)在使沒(méi)有整數(shù)約束的可行域以“割掉非整數(shù)解，保留需要的所有的整數(shù)可行解”的原則來(lái)壓縮可行域?！?.整數(shù)規(guī)劃的解法一通過(guò)例子來(lái)說(shuō)明分支定界解法的步驟分支定界解法解:

先不考慮條件(5)例即解相應(yīng)的線(xiàn)性規(guī)劃(1)-----(4)的最優(yōu)解分支定界解法(1)稱(chēng)為原問(wèn)題的松馳問(wèn)題用單純形法解上述問(wèn)題得x1=4.809,x2=1.817，z=355.89又由于當(dāng)x1=x2=0時(shí)，是原規(guī)劃的一個(gè)整數(shù)可行解，而此時(shí)z＝0。因此，原問(wèn)題的最優(yōu)值滿(mǎn)足：

0≤z*≤355這就是分支定界解法中的定界含義。分支定界解法(2)9x1+7x2=567x1+20x2=70x22108642ACB0x1z＝40x1+90x2由于最優(yōu)解是非整數(shù)，首先注意其中一個(gè)非整數(shù)變量(可任選),例如x1=4.809，我們可認(rèn)為整數(shù)最優(yōu)解x1是x14或x15,而在4和5之間是不合整數(shù)條件的,于是把原問(wèn)題分解成兩支,各支都增加了約束條件:即區(qū)域也分成兩塊R1和R2最優(yōu)解：x1=4.809,x2=1.817，z=355.89R2R1這就是分支定界解法中的分支含義分支定界解法(3)9x1+7x2=567x1+20x2=70x22108642ACB0x1z＝40x1+90x2R2R1這就是分支定界解法中的分支含義分支定界解法(4)問(wèn)題1有x1=4,x2=2.1z1=349.0問(wèn)題2有x1=5,x2=1.571z2=341.39由于沒(méi)有得到整數(shù)最優(yōu)解,繼續(xù)分解問(wèn)題(1)和問(wèn)題(2)0≤z*≤349分支定界解法(5)先分解問(wèn)題(1)問(wèn)題(3)有x1=4,x2=2z3=340問(wèn)題(4)有x1=1.428,x2=3z4=327.12問(wèn)題1有x1=4,x2=2.1z1=349.0340≤z*≤341分支定界解法(6)因?yàn)閱?wèn)題（3）的最優(yōu)解是整數(shù)解，最優(yōu)值為340但我們可以肯定,原問(wèn)題的最優(yōu)解不會(huì)在問(wèn)題(4)中,那么該整數(shù)解是否為原問(wèn)題的最優(yōu)解？對(duì)問(wèn)題(2)進(jìn)行分解,得問(wèn)題(5)和問(wèn)題(6)：所以問(wèn)題(4)不必去分解了.原問(wèn)題的最優(yōu)解可能在問(wèn)題(2)中,因?yàn)閱?wèn)題(2)的最優(yōu)值大于340這是因?yàn)?問(wèn)題(4)的最優(yōu)值小于問(wèn)題(3)的最優(yōu)值分支定界解法(7)

問(wèn)題(5)有x1=5.44,x2=1,z5=308問(wèn)題(6)

無(wú)可行解原問(wèn)題的最優(yōu)解不會(huì)在問(wèn)題(5)和(6)中,這是因?yàn)閱?wèn)題(5)的最優(yōu)值小于340,(6)沒(méi)有可行解原問(wèn)題的最優(yōu)解:x1=4,x2=2,最優(yōu)值:z*=340原問(wèn)題的松馳問(wèn)題：x1=4.809,x2=1.817，z=355.89分支定界解法(8)

因此，原問(wèn)題的最優(yōu)解:x1=4,x2=2,最優(yōu)值:z*=340問(wèn)題1

z1=349.0x1=4,x2=2.1問(wèn)題2

z2=341.39

x1=5,x2=1.571問(wèn)題3x1=4,x2=2z3=340問(wèn)題4x1=1.428x2=3z4=327.12問(wèn)題5x1=5.44x2=1z5=308問(wèn)題6

無(wú)可行解(2)用單純形法解(IPL);分支定界解法的步驟(3)若求得(IPL)的最優(yōu)解,

(1)稱(chēng)原整數(shù)規(guī)劃問(wèn)題為(IP)稱(chēng)相應(yīng)的線(xiàn)性規(guī)劃(即不考慮整數(shù)條件)為松馳問(wèn)題(IPL)若(IPL)沒(méi)有可行解,則(IP)也沒(méi)可行解.檢查它是否符合整數(shù)條件,

若符合整數(shù)條件,它就是問(wèn)題(IP)的最優(yōu)解;否則轉(zhuǎn)(4)(4)在(IPL)的解中,任選一個(gè)不符整數(shù)條件的變量xj,(i)xjbj

,(ii)xjbj

+1不考慮整數(shù)條件,分別求解這兩個(gè)后繼問(wèn)題(5)在現(xiàn)有的且還沒(méi)有分解后繼問(wèn)題的各可行問(wèn)題中,選目標(biāo)函數(shù)為最優(yōu)的問(wèn)題,重新稱(chēng)這個(gè)問(wèn)題為(IPL),轉(zhuǎn)(3)重復(fù)進(jìn)行若xj=bj非整;

作兩個(gè)后繼問(wèn)題,它們是對(duì)(IPL)分別各增加一個(gè)約束條件:

分支定界解法的注釋(1)在用單純形法繼續(xù)求解后繼問(wèn)題時(shí)，可借助上一級(jí)終表添加約束條件進(jìn)一步計(jì)算，借助單純形法或?qū)ε紗渭冃畏ㄟM(jìn)行計(jì)算；(2)對(duì)分支中最優(yōu)值較大者先分支，得到整數(shù)解的后繼問(wèn)題不必繼續(xù)分支；對(duì)最優(yōu)值低于目前下界的后繼問(wèn)題不必繼續(xù)分支；無(wú)可行解的后繼問(wèn)題不必繼續(xù)分支；當(dāng)所有后繼問(wèn)題都無(wú)法繼續(xù)分支時(shí)，最優(yōu)解才得到。§3.整數(shù)規(guī)劃的解法二考慮純整數(shù)規(guī)劃問(wèn)題：設(shè)其中aij(i=1,2,…,m;j=1,2,…,n)和bi(i=1,2,…,m)皆為整數(shù)（若不為整數(shù)，可乘上一個(gè)倍數(shù)化為整數(shù)）割平面法：(2)用單純形法解(IPL);§3.整數(shù)規(guī)劃的解法二(3)若求得(IPL)的最優(yōu)解,

1.(1)稱(chēng)原整數(shù)規(guī)劃問(wèn)題為(IP)稱(chēng)相應(yīng)的線(xiàn)性規(guī)劃(即不考慮整數(shù)條件)為松馳問(wèn)題(IPL)若(IPL)沒(méi)有可行解,則(IP)也沒(méi)可行解.檢查它是否符合整數(shù)條件,

若符合整數(shù)條件,它就是問(wèn)題(IP)的最優(yōu)解;否則轉(zhuǎn)2割平面法的步驟：2.(1)令xi是(IPL)的最優(yōu)解中取值為非整的一個(gè)基變量，由單純形終表可得：割平面法的步驟（2）(2)將和αij都分解成整數(shù)部分N和非整真分?jǐn)?shù)f之和，即：將(2),(3)代入(1)整理，移項(xiàng)，得(3)考慮整數(shù)約束，(4)式由左邊看是整數(shù)，且0<fi<1,所以有：割平面方程(4)用割平面方程去替代整數(shù)約束求解，具體操作為：將(5)式作為新增加的約束條件，引入松弛變量xn+1,利用對(duì)偶單純形法求解；割平面法的步驟（3）(5)若求得整數(shù)最優(yōu)解，停止計(jì)算；否則，仍有非整分量，從2.(1)開(kāi)始重復(fù)，繼續(xù)添加線(xiàn)性約束條件，相當(dāng)于在已經(jīng)割過(guò)的可行域上進(jìn)一步再割，直到達(dá)到最優(yōu)。注1：割平面方程真正進(jìn)行了切割，至少把非整數(shù)最優(yōu)解這一點(diǎn)割掉了；注2：割平面方程沒(méi)有割掉任何整數(shù)可行解；注3：當(dāng)(IPL)最優(yōu)解中存在多個(gè)非整基變量時(shí)，選擇分?jǐn)?shù)部分為最大的非整基分量所在行構(gòu)造割平面方程，往往可以減少“切割”次數(shù)。割平面法例子：例：用割平面法求解純整數(shù)規(guī)劃：解：求解原問(wèn)題的松弛問(wèn)題,前兩個(gè)不等式中引入非負(fù)松弛變量x3、x4，使兩式變成等式約束：-x1+x2+x3=13x1+x2+x4=4用單純形法求解，得：割平面法例子（2）XBbx1x2x3x4

初表x3x414-13111001-z01100終表x1x23/47/41001-1/43/41/41/5-z-5/200-1/2-1/2由單純形終表中第一行產(chǎn)生割平面方程：松弛問(wèn)題的最優(yōu)解為：x1=3/4,x2=7/4;割平面法例子（3）現(xiàn)考慮整數(shù)約束，得割平面方程為：將它作為新增的約束條件，再解其對(duì)應(yīng)的松弛問(wèn)題，引入松弛變量x5，得到：將原終表中加入一行一列，得：割平面法例子（4）XBbx1x2x3x4x5x1x2x53/47/4-3/4100010-1/43/4-3/41/41/4-1/4001-z-5/200-1/2-1/20XBbx1x2x3x4x5x1x2x31111000100011/301/3-1/121/4-1/3-z-2000-1/3-1/6此時(shí)，x*=(1,1,1,0,0)T已滿(mǎn)足整數(shù)要求，故原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解為：x1=1,x2=1最優(yōu)值為：z*=2割平面法例子（5）下面從幾何角度了解一下本題中可行域的切割過(guò)程：割平面方程為：§4.0--1規(guī)劃例1.在高校籃球聯(lián)賽中,我校男子籃球隊(duì)要從８名隊(duì)員中選擇平均身高最高的出場(chǎng)陣容,隊(duì)員的號(hào)碼、身高及擅長(zhǎng)的位置如下表：0-1變量----若變量只能取值0或1,則稱(chēng)其為0-1變量.通常作為邏輯變量,常被用來(lái)表示系統(tǒng)是否處于某個(gè)特定狀態(tài),或決策時(shí)是否取某個(gè)特定方案.0--1規(guī)劃的數(shù)學(xué)模型(2)同時(shí)，要求出場(chǎng)陣容滿(mǎn)足以下條件：

⑶

如果１號(hào)隊(duì)員和４號(hào)隊(duì)員都上場(chǎng)，則６號(hào)隊(duì)員不能出場(chǎng)⑴

中鋒最多只能上場(chǎng)一個(gè)⑵

至少有一名后衛(wèi)問(wèn)應(yīng)當(dāng)選擇哪5名隊(duì)員上場(chǎng),才能使出場(chǎng)隊(duì)員平均身高最高?試寫(xiě)出上述問(wèn)題的數(shù)學(xué)模型。⑷

２號(hào)隊(duì)員和６號(hào)隊(duì)員必須保留一個(gè)不出場(chǎng)。0--1規(guī)劃的數(shù)學(xué)模型(3)約束條件:⑶

如果１號(hào)隊(duì)員和４號(hào)隊(duì)員都上場(chǎng)，則６號(hào)隊(duì)員不能出場(chǎng)(1）中鋒最多只能上場(chǎng)一個(gè),即⑵至少有一名后衛(wèi)解:設(shè)Xj=1表示第j號(hào)隊(duì)員上場(chǎng),

Xj=0表示第j號(hào)隊(duì)員不上場(chǎng)

j=1,2,...,8⑷

２號(hào)隊(duì)員和６號(hào)隊(duì)員必須保留一個(gè)不出場(chǎng)。(5）籃球比賽恰好5人上場(chǎng)0--1規(guī)劃的數(shù)學(xué)模型故該問(wèn)題的數(shù)學(xué)模型為:其中cj表示第j號(hào)隊(duì)員的身高(j=1,2,…,8)0--1規(guī)劃的數(shù)學(xué)模型(例2)例2.某公司有機(jī)會(huì)對(duì)B1、B2、B3三個(gè)項(xiàng)目進(jìn)行投資。根據(jù)預(yù)算,前兩年每年可投資6(萬(wàn)元),后兩年每年可投資7(萬(wàn)元)。三個(gè)項(xiàng)目每年所需投資額和純利潤(rùn)如下表:

問(wèn)公司應(yīng)對(duì)哪幾個(gè)項(xiàng)目進(jìn)行投資,才能使獲得的利潤(rùn)最大?試建立這個(gè)問(wèn)題的整數(shù)規(guī)劃模型.解:設(shè)0--1規(guī)劃的數(shù)學(xué)模型(例2)故數(shù)學(xué)模型為0--1規(guī)劃的數(shù)學(xué)模型(例3)隊(duì)員的挑選要滿(mǎn)足下列條件:例3.某校籃球隊(duì)準(zhǔn)備從以下六名預(yù)備隊(duì)員中選拔三名為正式隊(duì)員,并使平均的身高盡可能高。這六名預(yù)備隊(duì)員情況如下表所示：⑴

至少補(bǔ)充一名后衛(wèi)隊(duì)員;⑵大李或小田中間恰有一名入選;⑶最多補(bǔ)充一名中鋒;⑷無(wú)論大李或小趙入選,小周就不能入選.試建立這個(gè)問(wèn)題的整數(shù)規(guī)劃模型.0--1規(guī)劃的數(shù)學(xué)模型(例3)解:

設(shè)j=4,5,...,9約束條件:

⑴至少補(bǔ)充一名后衛(wèi)隊(duì)員⑵

大李或小田中間恰有一名入選;(3)最多補(bǔ)充一名中鋒⑷無(wú)論大李或小趙入選,小周就不能入選0--1規(guī)劃的數(shù)學(xué)模型(例3)則數(shù)學(xué)模型為例6.求解下面的0-1型整數(shù)規(guī)劃問(wèn)題：0-1規(guī)劃的解法解：借助隱枚舉法，列表如下：0-1規(guī)劃的解法（2）該問(wèn)題的最優(yōu)解:x1=1,x2=0,x3=1；最優(yōu)值:z*=8×(1,1,1)T×(1,1,0)T×(0,1,1)T8(1,0,1)T×(1,0,0)T×(0,1,0)T

5(0,0,1)T0(0,0,0)T（4）（3）（2）（1）件條束約z值全體組合2.用0-1變量表示含有互相排斥的約束條件例4．某廠擬用運(yùn)貨車(chē)或船托運(yùn)甲乙兩種貨物,每箱的體積、重量、可獲利及托運(yùn)限制如下表:問(wèn):兩種貨物各托運(yùn)多少箱,可使獲利最大?試建立這個(gè)問(wèn)題的整數(shù)規(guī)劃模型.貨物體積重量利潤(rùn)

(每箱立方米)(每箱百斤)(每箱百元)

甲5(7)220

乙4(3)510托運(yùn)限制24(45)13

用0-1變量表示含有互相排斥的約束條件解：設(shè)甲乙兩種貨物分別托運(yùn)x1和x2箱目標(biāo)函數(shù)

z=20x1+10x2約束條件：重量限制

2x1+5x2≤13體積限制：當(dāng)船托運(yùn)時(shí)為7x1+3x2≤45但托運(yùn)時(shí)用汽車(chē)或用船的兩種方式中只能選擇一種故引0-1變量yy=0表示采用車(chē)運(yùn)方式；y=1表示采用船運(yùn)方式體積限制的約束可用以下條件來(lái)代替：當(dāng)汽車(chē)托運(yùn)時(shí)為5x1+4x2≤245x1+4x2≤24+yM7x1+3x2≤45+(1-y)M（其中M是充分大的數(shù)）用0-1變量表示含有互相排斥的約束條件

則數(shù)學(xué)模型為：用0-1變量表示含有互相排斥的約束條件注：若有m個(gè)互相排斥的約束條件（≤型）為了保證這m個(gè)約束條件只有一個(gè)起作用我們引入m個(gè)0-1變量yi(i=1,2,...,m)和一個(gè)充分大的常數(shù)M可用下列m+1個(gè)約束條件表示：用0-1變量表示含有互相排斥的約束條件例5.利用0-1變量把下列各題分別表示成一般線(xiàn)性約束條件用0-1變量表示含有互相排斥的約束條件解：設(shè)用0-1變量表示含有互相排斥的約束條件§5.指派問(wèn)題指派問(wèn)題(或稱(chēng)分配問(wèn)題)(AssignmentProblem)有n項(xiàng)任務(wù)要完成，恰好有n個(gè)人可以分別去完成其中每一項(xiàng),但由于任務(wù)性質(zhì)和各人專(zhuān)長(zhǎng)不同,因此各人去完成不同的各種任務(wù)的效率(或所費(fèi)時(shí)間)就有差別,則應(yīng)當(dāng)如何指派哪個(gè)人去完成哪項(xiàng)任務(wù)使總效率為最高(或所花時(shí)間為最小)?

例1:

有一份說(shuō)明書(shū),要分別譯成英、日、德、俄四種文字（分別稱(chēng)為任務(wù)Ｅ，Ｊ，Ｇ，Ｒ），要交甲、乙、丙、丁四人去完成，每人完成一種翻譯；因各人專(zhuān)業(yè)不同，他們翻譯成不同文字所需時(shí)間如下表，問(wèn)應(yīng)指派哪個(gè)人完成哪項(xiàng)任務(wù)可使總的花費(fèi)時(shí)間為最小？

指派問(wèn)題（2）例2.某游泳隊(duì)有4名運(yùn)動(dòng)員A1,A2,A3,A4,他們的50米自由泳、蛙泳、蝶泳、仰泳的成績(jī)?nèi)缦卤硭?現(xiàn)在要將他們組成一個(gè)450混合接力隊(duì),問(wèn)應(yīng)該分配

A1,A2,A3,A4各游什么項(xiàng)目,才能使總成績(jī)最好?指派問(wèn)題（3）類(lèi)似有：有n項(xiàng)加工任務(wù)，怎么樣指派到n臺(tái)機(jī)床上分別完成的問(wèn)題；有n條航線(xiàn)，怎么樣指定N艘船去航行問(wèn)題....系數(shù)矩陣:對(duì)每個(gè)指派問(wèn)題都有類(lèi)似上述表格中的元素

cij>0，由這些元素構(gòu)成的矩陣為效率矩陣令

則指派問(wèn)題的數(shù)學(xué)模型

表示指派第i個(gè)人去完成第j項(xiàng)任務(wù)

表示不指派第i個(gè)人去完成第j項(xiàng)任務(wù)

指派問(wèn)題（4）指派問(wèn)題是0-1規(guī)劃的特例，也是運(yùn)輸問(wèn)題的特例。指派問(wèn)題的一個(gè)可行解可用一個(gè)矩陣表示：稱(chēng)之為解矩陣若從系數(shù)矩陣（cij）的一行（列）各元素中分別減去該行（列）的最小數(shù)，得到新矩陣（bij），則以（bij）為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。利用此性質(zhì)，可使原系數(shù)矩陣變換為含有很多0元素的新系數(shù)矩陣，而最優(yōu)解保持不變。我們稱(chēng)系數(shù)矩陣中位于不同行不同列的0元素為獨(dú)立的0元素。指派問(wèn)題的最優(yōu)解的性質(zhì)：指派問(wèn)題（5）如下的系數(shù)矩陣中存在4個(gè)獨(dú)立的0元素若能在系數(shù)矩陣（bij）中能找出n個(gè)獨(dú)立的0元素，則令解矩陣（xij）中對(duì)應(yīng)這n個(gè)獨(dú)立的0元素的元素取1，其余元素取0，將其代入目標(biāo)函數(shù)中得到zb=0，它一定是最小。這就是以B為系數(shù)矩陣的指派問(wèn)題的最優(yōu)解，也得到原問(wèn)題的最優(yōu)解。指派問(wèn)題（6）1955年庫(kù)恩（W.W.Kuhn）提出了指派問(wèn)題的解法。他引用了匈牙利數(shù)學(xué)家康尼格（D.Konig）一個(gè)關(guān)于矩陣中0元素的定理：系數(shù)矩陣中的獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少的直線(xiàn)數(shù)目。所以稱(chēng)此解法為匈牙利解法。下面我們介紹匈牙利解法的步驟：匈牙利解法第一步：使系數(shù)矩陣出現(xiàn)0元素

(A)從系數(shù)矩陣的每行元素減去該行的最小元素;(B)再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的最小元素;

由0元素最少的行(或列)開(kāi)始,圈出一個(gè)0元素,用表示,然后劃去同行同列的0元素,用表示,這樣依次做完各行各列,已劃去就不能再圈,第二步：試求最優(yōu)解如果能得到n個(gè),這就完成了求最優(yōu)解的過(guò)程;第三步：作能覆蓋所有0元素的最少數(shù)目的直線(xiàn)集合如果圈出的不夠n個(gè),則轉(zhuǎn)(3)匈牙利解法

(A)對(duì)沒(méi)有的行打號(hào);(B)在已打號(hào)的行中，對(duì)

所在列打號(hào);(C)在已打號(hào)的列中，對(duì)所在行打號(hào);(D)重復(fù)(B)(C),直到再也找不到可以打號(hào)的行或列為止;(E)對(duì)沒(méi)有打號(hào)的行畫(huà)橫線(xiàn),所有打的列畫(huà)縱線(xiàn),這樣就得到了覆蓋所有零元素的最少直線(xiàn)數(shù)目的直線(xiàn)集合.第四步：在沒(méi)有被直線(xiàn)覆蓋的部分中找出最小元素,然后對(duì)沒(méi)畫(huà)直線(xiàn)的行的各元素都減去這最小元素,

對(duì)畫(huà)直線(xiàn)的列的各元素都加上這最小元素,這樣得到新的系數(shù)矩陣;若有n個(gè)不同行不同列的0元素,則求解過(guò)程完成;若沒(méi)有n個(gè)不同行不同列的0元素,轉(zhuǎn)第三步執(zhí)行.匈牙利解法(舉例1)例1解:甲譯俄文；乙譯日文；丙譯英文；丁譯德文總的花費(fèi)時(shí)間為28

由于已有4個(gè)獨(dú)立0元素，故最優(yōu)解為：匈牙利解法(舉例2)

例2

求下表所示效率矩陣的指派問(wèn)題的最小解。解：匈牙利解法(舉例2)

最后一個(gè)矩陣中，已得到5個(gè)獨(dú)立0元素，則得最優(yōu)解為：匈牙利解法(舉例2)最優(yōu)方案為：

甲→B

乙→D

丙→E

丁→C

戊→A

或甲→B

乙→C

丙→E

丁→D

戊→A總的耗費(fèi)時(shí)間為32個(gè)單位。匈牙利解法(舉例2)

解2：

(A)對(duì)沒(méi)有的行打號(hào);(B)在已打號(hào)的行中，對(duì)

所在列打號(hào);(C)在已打號(hào)的列中，對(duì)所在行打號(hào);(D)重復(fù)(B)(C),直到再也找不到可以打號(hào)的行或列為止;(E)對(duì)沒(méi)有打號(hào)的行畫(huà)橫線(xiàn),所有打的列畫(huà)縱線(xiàn),這樣就得到了覆蓋所有零元素的最少直線(xiàn)數(shù)目的直線(xiàn)集合.匈牙利解法(舉例2)(4)在沒(méi)有被直線(xiàn)覆蓋的部分中找出最小元素,然后,對(duì)沒(méi)畫(huà)直線(xiàn)的行的各元素都減去這最小元素,對(duì)畫(huà)直線(xiàn)的列的各元素都加上這最小元素,這樣得到新的系數(shù)矩陣;第3,5行各元素減去2第1列各元素加上2匈牙利解法(舉例2)最優(yōu)方案為：甲→B

乙→D

丙→E丁→D

戊→A

或甲→B

乙→C

丙→E

丁→C

戊→A最后一個(gè)矩陣中，已得到5個(gè)獨(dú)立0元素，則得最優(yōu)解為：總的耗費(fèi)時(shí)間為32個(gè)單位。二．極大化的指派問(wèn)題極大化指派問(wèn)題的數(shù)學(xué)模型

需把它化為極小化問(wèn)題但不能象線(xiàn)性規(guī)劃問(wèn)題那樣，令目標(biāo)函數(shù)的相反數(shù)此時(shí)令bij=M-cij

其中M是足夠大的常數(shù)則系數(shù)