運籌學-4-整數(shù)規(guī)劃

運籌學運籌帷幄之中決勝千里之外整數(shù)規(guī)劃IntegerProgramming第四章第四章整數(shù)規(guī)劃本章主要內(nèi)容：整數(shù)問題規(guī)劃及其數(shù)學模型整數(shù)規(guī)劃問題的求解0-1型整數(shù)規(guī)劃問題指派問題第四章整數(shù)規(guī)劃在很多場合，我們建立最優(yōu)化模型時，實際問題要求決策變量只能取整數(shù)值而非連續(xù)取值。此時，這類最優(yōu)化模型就稱為整數(shù)規(guī)劃（離散最優(yōu)化）模型。

整數(shù)規(guī)劃的求解往往比線性規(guī)劃求解困難得多，而且，一般來說不能簡單地將相應的線性規(guī)劃的解取整來獲得。第四章整數(shù)規(guī)劃線性規(guī)劃模型：實際問題要求xi為整數(shù)！如機器的臺數(shù)，人數(shù)等第四章整數(shù)規(guī)劃例:勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價50元/個，椅子售價30元/個，生產(chǎn)桌子和椅子需要木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4個小時，油漆工2小時。生產(chǎn)一個椅子需要木工3個小時，油漆工1小時。該廠每月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？第四章整數(shù)規(guī)劃純整數(shù)規(guī)劃第四章整數(shù)規(guī)劃例（背包問題）一個旅行者，為了準備旅行的必備物品，要在背包里裝一些有用的東西，但他最多只能攜帶b公斤的東西，而每件物品都只能整件攜帶，于是他給每件物品規(guī)定了一個“價值”，以表示其有用程度。如果共有m件物品，第i件件物品的重量為bi，價值為ci，問題就變成：在攜帶的物品總重量不超過b公斤的條件下，攜帶哪些物品可使總價值最大?第四章整數(shù)規(guī)劃9解：Z表示所帶物品的總價值攜帶物品的總重量數(shù)學模型：0-1規(guī)劃第四章整數(shù)規(guī)劃第四章整數(shù)規(guī)劃解：數(shù)學模型：混合型整數(shù)規(guī)劃第四章整數(shù)規(guī)劃例

工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應求，故需要再建一家工廠。相應的建廠方案有A3和A4兩個。這種物資的需求地有B1,B2,B3,B4四個。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運費cij，見下表：B1B2B3B4年生產(chǎn)能力A12934400A28357600A37612200A44525200年需求量350400300150工廠A3或A4開工后，每年的生產(chǎn)費用估計分別為1200萬或1500萬元?，F(xiàn)要決定應該建設工廠A3還是A4，才能使今后每年的總費用最少。第四章整數(shù)規(guī)劃解：這是一個物資運輸問題，特點是事先不能確定應該建A3還是A4中哪一個，因而不知道新廠投產(chǎn)后的實際生產(chǎn)物資。為此，引入0-1變量：再設xij為由Ai運往Bj的物資數(shù)量，單位為千噸；z表示總費用，單位萬元。則該規(guī)劃問題的數(shù)學模型可以表示為：第四章整數(shù)規(guī)劃混合整數(shù)規(guī)劃問題第四章整數(shù)規(guī)劃整數(shù)線性規(guī)劃問題的種類：

純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃?；旌险麛?shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。

0-1型整數(shù)線性規(guī)劃：決策變量只能取值0或1的整數(shù)線性規(guī)劃。第四章整數(shù)規(guī)劃純整數(shù)規(guī)劃的數(shù)學模型：0--1規(guī)劃的數(shù)學模型：第四章整數(shù)規(guī)劃例×√√√√Z=130√√√√，可行且Z=140不可行可行第四章整數(shù)規(guī)劃（IP）（IP）問題的松弛問題第四章整數(shù)規(guī)劃∩≤松弛問題的最優(yōu)值是原整數(shù)規(guī)劃的目標函數(shù)值的上界第四章整數(shù)規(guī)劃例

設整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。第四章整數(shù)規(guī)劃用圖解法求出最優(yōu)解為：x1＝3/2,x2

=10/3，且有Z=29/6

現(xiàn)求整數(shù)解(最優(yōu)解):如用舍入取整法可得到4個點即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。x1x2⑴⑵33(3/2,10/3)

按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如右圖所示。其中(2,2),(3,1)點的目標函數(shù)值最大，即為Z=4。第四章整數(shù)規(guī)劃-分支定界法1）求整數(shù)規(guī)劃的松弛問題最優(yōu)解； 若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否則轉(zhuǎn)下一步；2）分支與定界： 任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束：xi≤[xi]和xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界。 檢查所有分枝的解及目標函數(shù)值，若某分枝的解是整數(shù)并且目標函數(shù)值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計算，若還存在非整數(shù)解并且目標值大于(max)整數(shù)解的目標值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。分支定界法的解題步驟：上界x1≤[x*01]x1≥[x*01]+1當所有的子問題均被關閉或剪枝后目標函數(shù)值最大的整數(shù)解既為所求的最優(yōu)解一、分枝定界法的原理：1、分枝··················012345678·松弛問題的可行域增加x1≤3增加x1≥4L1L2x1≤3x1≥4父問題子問題結(jié)論1：（IP）的最優(yōu)解一定在某個子問題中父問題的最優(yōu)值≤3：子問題中的整數(shù)解都是（IP）的可行解子問題的最優(yōu)解2：子問題的可行域父問題的可行域∩2、定界1、（LP）的最優(yōu)值是(IP)的最優(yōu)值的上界IP松弛問題L0L1L2通過對（L0）分枝，使（IP）的最優(yōu)值的上界不斷下降，L3L4L5L6下界不斷上升，上界=下界得最優(yōu)值··················012345678·x1≤3x1≥4z=30x1+20x24x1+x2=16.52x1+3x2=14.5x2≤2x2≥3x1≤2x1≥3混合型x1≤3x1≥4L0的最優(yōu)單純型表：x1x2x3x4常數(shù)項檢00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x5100013000x1≤3x1≥4x1≤2x1≥3x2≤2x2≥3x1x2x3x4解檢00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x5100013000x1x2x3x4解檢00-5-5Z-155x2012/5-1/55/2x110-1/103/107/2x5x5001/10-3/101-1/2000x1x2x3x4解檢00-20/30-50/3Z-440/3x2011/30-2/317/6x110001300-1/31-10/35/3x4x5x2≤2x2+x6=2x1x2x3x4x5

解檢00-20/30-50/3Z-440/3x2011/30-2/317/6x1100013x400-1/31-10/35/3x60100012x60000x1x2x3x4x5

x6

解檢00-20/30-50/30Z-440/3x2011/30-2/3017/6x11000103x400-1/31-10/305/3x600-1/302/31-5/6x1x2x3x4x5

x6

解檢0000-30-20Z-130x20100012x11000103x40001-4-15/2x30010-2-35/2x2≥3X2-x6=3x1x2x3x4x5

解檢00-20/30-50/3Z-440/3x2011/30-2/317/6x1100013x400-1/31-10/35/3x60-10001-3x60000x1x2x3x4x5

x6

解檢00-20/30-50/30Z-440/3x2011/30-2/3017/6x11000103x400-1/31-10/305/3x6001/30-2/31-1/6-X2+x6=-3x1x2x3x4x5

x6

解檢00-1500-25Z-285/2x201000-13x1101/2003/211/4x400-210-55/2x500-1/201-3/21/4x1x2x3x4x5

x6

解檢00-1500-25Z-285/2x201000-13x1101/2003/211/4x400-210-55/2x500-1/201-3/21/4x1≤2x1+x7=2X700000x710000012x1x2x3x4x5

x6

x7

解檢00-20/3000-50/3Z-130x2011/3000-2/37/2x110000012x400-1/3100-10/35x5000010-11x6001/3001-2/31/200-1/200-3/21-3/4如何選擇分枝的節(jié)點及分枝變量？1、分枝節(jié)點選擇的原則：盡快找到好的整數(shù)解，減少搜索節(jié)點，提高搜索效率。方法：（1）深探法：（2）廣探法：最后打開的節(jié)點最先選擇選擇有最大目標函數(shù)值的節(jié)點繼續(xù)向下分枝2、分枝變量選擇的原則：尋找那些對問題影響最大的變量首先分枝（1）按目標函數(shù)系數(shù)選擇：選擇目標函數(shù)系數(shù)絕對值最大的變量首先分枝（2）按非整數(shù)變量選擇：選擇與整數(shù)值相差最大的非整數(shù)變量進行分枝（3）按人為給定的順序選擇x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3第四章整數(shù)規(guī)劃-割平面法割平面法的基本思想：若整數(shù)規(guī)劃IP的松弛規(guī)劃L0的最優(yōu)解不是整數(shù)解，對L0增加一個約束條件，得線性規(guī)劃L1，此過程縮小了松弛規(guī)劃的可行解域，在切去松弛規(guī)劃的最優(yōu)解的同時，保留松弛規(guī)劃的任一整數(shù)解，因此整數(shù)規(guī)劃IP的解均在L1中，若L1的最優(yōu)解為整數(shù)解，則得IP的最優(yōu)解。若L1的最優(yōu)解不是整數(shù)解，重復以上步驟，由于可行解域在不斷縮小，且保留IP所有的整數(shù)解，總可以在有限次后得到IP的最優(yōu)解.················割平面39問題：如何尋找割平面？增加的約束方程須滿足什么條件才能使：1、割掉松弛規(guī)劃的最優(yōu)解2、保留所有的整數(shù)解40二、割平面法41L0的最優(yōu)單純形表：x1…xi…xmxm+1…xm+j…xn解檢0…0…0λ1…λm+j…λnz-z0x11…0…0a1m+1…a1m+j…a1nb10︰︰︰︰︰︰︰︰xi0…1…0aim+1…aim+j…ainbi0︰︰︰︰︰︰︰︰xm0…0…1amm+1…amm+j…amnbm0源方程42------對應于生成行i的割平面43L0的最優(yōu)單純形表：x1…xi…xmxm+1…xm+j…xn解檢0…0…0λ1…λm+j…λnz-z0x11…0…0a1m+1…a1m+j…a1nb10︰︰︰︰︰︰︰︰xi0…1…0aim+1…aim+j…ainbi0︰︰︰︰︰︰︰︰xm0…0…1amm+1…amm+j…amnbm0生成行對應于生成行i的割平面非基變量44b010.500-0.5100-1.75103.255.500-1011310-0.25000.751.500-0.500-1.5z-9對應第2行的割平面：對應第4行的割平面：45非基變量46如何求解？47x1…xi…xmxm+1…xm+j…xn解檢0…0…0c1…cm+j…cnz-z0x11…0…0a1m+1…a1m+j…a1nb10︰︰︰︰︰︰︰︰xi0…1…0aim+1…aim+j…ainbi0︰︰︰︰︰︰︰︰xm0…0…1amm+1…amm+j…amnbm0ss0…0…0-fim+1…-fim+j…-fin1–fi0

00︰0︰0對偶單純形法48割平面計算步驟第一步：用單純形法解整數(shù)問題IP的松弛問題L0若L0沒有最優(yōu)解，則IP沒有最優(yōu)解。停止若L0有最優(yōu)解X0:(1)X0是整數(shù)解，則X0也是IP的最優(yōu)解，停止(2)X0不是整數(shù)解，轉(zhuǎn)第二步第二步：求割平面方程49第三步：將割平面加到L0得L1第四步：解L1在L0的最優(yōu)單純形表中增加一行一列，得L1的單純形表，用對偶單純形法求解，若其解是整數(shù)解，則該解也是原整數(shù)規(guī)劃的最優(yōu)解否則將該解記為X0，返回第二步50例用割平面法求解IP解：IP問題的松弛規(guī)劃的標準型：X1X2X3X400-2.25-1.75Z-37.5X2010.25-0.251.5X1100.1250.3753.75

X5000X500-0.125-0.3751-0.75X1X2X3X4X5ZX2

X1

X4

000.3331-2.6672100013010.3330-0.667200-1.6670-4.667z-34整數(shù)最優(yōu)值：Z=3451

例：用割平面法求解解：IP的松弛規(guī)劃的標準型X1X2X3X400-28/11-15/11Z-63X2017/221/227/2X110-1/223/229/2

X500-7/22-1/221-1/2X5000X1X2X3X4X5X2

X1X3

0011/7-22/7

11/71001/7-1/732/7010013000-1-8Z-59非整數(shù)52X1X2X3X4X5X2

X1X3

0011/7-22/711/71001/7-1/732/7010013000-1-8Z-59X6000-1/7-6/71-4/7X60000X1X2X3X4X5X60000-2-7Z-55X20100113X11000-114X30010-411X4

00016-7

4整數(shù)最優(yōu)值：Z=5553作業(yè)：分別用分枝定界法和割平面法求解整數(shù)規(guī)劃：最優(yōu)值為：Z=454第四章整數(shù)規(guī)劃-0-1整數(shù)規(guī)劃0—1型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量xi僅取值0或1。這時xi稱為0—1變量，或稱二進制變量。xi僅取值0或1這個條件可由下述約束條件：

xi≤1

xi≥0，整數(shù)所代替，和一般整數(shù)規(guī)劃的約束條件形式一致的。第四章整數(shù)規(guī)劃-0-1整數(shù)規(guī)劃投資場所的選擇—相互排斥的計劃例：某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個位置（點）Ai（i=1，2，…，7）可供選擇。規(guī)定在東區(qū)，由A1，A2，A3三個點中至多選兩個；在西區(qū)，由A4，A5兩個點中至少選一個；在南區(qū)，由A6，A7兩個點中至少選一個。如選用Ai點，設備投資估計為bi元，每年可獲利潤估計為Ci元，但投資總額不能超過B元。問應選擇哪幾個點可使年利潤為最大？第四章整數(shù)規(guī)劃-0-1整數(shù)規(guī)劃令xi=1，2，…，7（三點中最多選兩點）（兩點中至少選一點）（兩點中至少選一點）決策變量：投資項目AiORnot投資項目Ai利潤第四章整數(shù)規(guī)劃-0-1整數(shù)規(guī)劃（1）兩個約束中，只有一個起作用。例：a11x1+a12x2<B1a21x1+a22x2<B2

例

含有相互排斥的約束條件的問題解：引入0-1變量Y1,Y2和足夠大的正數(shù)M，則a11x1+a12x2<B1+M1Y1a21x1+a22x2<B2+M2Y2Y1+Y2=1第四章整數(shù)規(guī)劃-0-1整數(shù)規(guī)劃（2）互相排斥的多個約束中，只有一個起作用ai1x1+ai2x2+…+ainxn

bi(i=1,…,m)互相排斥m個約束，只有一個起作用:ai1x1+…+ainxn

bi+yiM

(i=1,…,m)y1+…+ym=m-1yi為0或1M>0（3）若a個約束條件中只能有b個起作用。則令0－1變量之和為a-b。注意：可用統(tǒng)一M，但M的取值必須足夠的大。第四章整數(shù)規(guī)劃-0-1整數(shù)規(guī)劃1問題的提出:已知：兩種貨物裝箱每種貨物裝箱利潤體積限制重量限制決策變量:兩種貨物各多少箱MaxZ=利潤最大？箱數(shù)不能為分數(shù)貨物X1貨物X2限量體積5424重量2513利潤2010相互排斥的約束條件第四章整數(shù)規(guī)劃-0-1整數(shù)規(guī)劃互相排斥的約束條件（假設有車、船2種運輸方式）用車運的體積約束用船運的體積約束第四章整數(shù)規(guī)劃-0-1整數(shù)規(guī)劃固定費用的問題在討論線性規(guī)劃時，有些問題是要求使成本為最小。那時總設固定成本為常數(shù)，并在線性規(guī)劃的模型中不必明顯列出。但有些固定費用（固定成本）的問題不能用一般線性規(guī)劃來描述，但可改變?yōu)榛旌险麛?shù)規(guī)劃來解決。第四章整數(shù)規(guī)劃-0-1整數(shù)規(guī)劃例

固定費用問題解：設Xj是第j種產(chǎn)品的產(chǎn)量。Yj是0－1變量，表示是（Yj=1）否（Yj=0）生產(chǎn)第j種產(chǎn)品。

單耗量產(chǎn)品資源IIIIII資源量A248500B234300C123100單件可變費用456固定費用100150200單件售價81012第四章整數(shù)規(guī)劃-0-1整數(shù)規(guī)劃maxZ=4X1+5X2+6X3–100Y1

–150Y2

–200Y32X1+4X2+8X35002X1+3X2+4X3300X1+2X2+3X3100X1

M1Y1X2

M2Y2X3

M3

Y3X1,

X2,

X30整數(shù)Y1,Y2,Y3為0－1變量，M1,M2,M3為任意大正數(shù)。

s.t.第四章整數(shù)規(guī)劃-隱枚舉法在整數(shù)規(guī)劃模型中，若變量取值為0或1兩個特殊的數(shù)值，則稱此類模型為0—1的使用及建立模型的方法。隱枚舉法基本思想：隱枚舉法是分枝定界法思想的延伸。通過放松主約束條件（而非變量符號限制條件）求得最優(yōu)解，再檢查是否滿足約束條件，再經(jīng)過分枝與剪枝等工作迭代出最優(yōu)解。第四章整數(shù)規(guī)劃-隱枚舉法在2n個可能的變量組合中，往往只有一部分是可行解。只要發(fā)現(xiàn)某個變量組合不滿足其中一個約束條件時，就不必再去檢驗其他約束條件是否可行。對于可行解，其目標函數(shù)值也有優(yōu)劣之分。若已發(fā)現(xiàn)一個可行解，則根據(jù)它的目標函數(shù)值可以產(chǎn)生一個過濾條件，對于目標函數(shù)值比它差的變量組合不必再去檢驗它的可行性。在以后的求解過程中，每當發(fā)現(xiàn)比原來更好的可行解，則替換原來的過濾條件。第四章整數(shù)規(guī)劃-隱枚舉法0-1規(guī)劃求解MaxZ=3X1－2X2

＋5X3X1+2X2

－X3<=2（1）X1+4X2+X3<=4（2）X1+X2<=3（3）

4X2+X3<=6（4）X1,X2,X3=0或者1（5）解：觀察（X1,X2,X3

）＝（1，0，0）滿足約束（1）－（5）相應Z=3增加一個約束,目標值>=33X1－2X2

＋5X3>=3（*）稱為過濾條件（FilteringConstraint）第四章整數(shù)規(guī)劃-隱枚舉法

逐一檢查如下點是否滿足約束條件？

約束條件（左邊）滿足約束條件?Z值約束（*）左約束（1）左約束（2）左約束（3）左約束（4）左（0，0，0）0不（0，0，1）5－1101是5（0，1，0）-2不（1，0，0）31110是（0，1，1）31不（1，0，1）80211是8（1，1，0）1不（1，1，1）62不于是最優(yōu)解（X1,X2,X3

）＝（1，0，1）MaxZ=83X1－2X2

＋5X3>=3（*）稱為過濾條件（FilteringConstraint）第四章整數(shù)規(guī)劃-隱枚舉法MaxZ=－2X2

＋3X1

＋5X3

目標函數(shù)按系數(shù)遞增（－2，3，5）

約束條件也按上面決定的順序－2X2

＋3X1

＋5X3>=3

（*）

2X2

＋X1－X3<=2（1）

4X2+

X1＋X3<=4（2）

X2

＋X1

<=3

（3）

4X2+

X3<=6

（4）

X1,X2,X3=0或者1

（5）解：變量（X1,X2,X3）按下面順序容易更早發(fā)現(xiàn)最優(yōu)解：（0，0，0）（0，0，1）（0，1，0）（0，1，1）…….

逐一檢查如下點是否滿足約束條件？

約束條件（左邊）滿足條件?Z值（*）左（1）左（2）左（3）左（4）左（0，0，0）0<3不（0，0，1）5>3－1101是5改進過濾條件，用：3X1－2X2

＋5X3>=5（*）為過濾條件

逐一檢查如下點是否滿足約束條件？

約束條件（左邊）滿足條件?Z值（*）左（1）左（2）左（3）左（4）左（0，1，0）3不（0，1，1）80211是8這里已經(jīng)更換了x1,x2的位置(x2,x1,x3)再改進過濾條件，用：3X1－2X2

＋5X3>=8（*）為過濾條件

逐一檢查如下點是否滿足約束條件？

約束條件（左邊）滿足條件?Z值（*）左（1）左（2）左（3）左（4）左（1，0，0）-2<8不

（1，0，1）3<8不

（1，1，0）1<8不（1，1，1）6<8不這里已經(jīng)更換了x1,x2的位置(x2,x1,x3)MaxZ=－2X2＋3X1

＋5X3

目標函數(shù)按系數(shù)遞增（－2，3，5）約束條件也按上面決定的順序－2X2＋3X1

＋5X3>=3（*）

2X2＋X1－X3<=2（1）

4X2+

X1＋X3<=4

（2）

X2

＋X1

<=3（3）

4X2+

X3

<=6（4）

X1,X2,X3=0或者1

（5）解：變量（X1,X2,X3

）按下面順序容易更早發(fā)現(xiàn)最優(yōu)解：（1，0，1）對應目標函數(shù)系數(shù)（3，-2，5）負系數(shù)的Xi取0，正系數(shù)的Xi取1這時目標函數(shù)達到最大值，但不一定滿足約束條件；如果滿足約束條件，則不必檢驗其他解，一步直達。這里已經(jīng)更換了x1,x2的位置第四章整數(shù)規(guī)劃-隱枚舉法在解決0-1規(guī)劃問題時，為了進一步減少運算量，常按目標函數(shù)中各變量系數(shù)的大小順序重新排列各變量，以使最優(yōu)解有可能較早出現(xiàn)。

對于最大化問題，可按目標函數(shù)中各變量系數(shù)由小到大的順序排列。對于最小化問題，可按目標函數(shù)中各變量系數(shù)由大到小的順序排列。第四章整數(shù)規(guī)劃-隱枚舉法求解0—1整數(shù)規(guī)劃

maxf(x)=3x1-2x2+5x3

s.t.x1+2x2-x3≤2

x1+4x2+x3≤4

x1+x2

≤3

4x2+x3≤6

x1,x2,x3=0或1

第四章整數(shù)規(guī)劃-隱枚舉法求解0-1整數(shù)規(guī)劃

minf(x)=3x1+7x2-x3+x4s.t.2x1-x2+

x3-

x4

≥1

x1-x2+6x3+

4x4

≥8

5x1+3x2+

x4

≥5

x1,x2,x3,x4=0或1

設有n個工作，要由n個人來承擔，每個工作只能由一個人承擔，且每個人只能承擔一個工作。cij表示第i個人做第j件事的費用,求總費用最低的指派方案。費用12…j…n12…i…n指派問題模型：i=1,2,…,nj=1,2,…,n第i個人做第j件事Z表示總費用i=1,2,…,n;j=1,2,…,n第i個人不做第j件事1、指派問題的數(shù)學模型76i=1,2,…,nj=1,2,…,n當n=4時，有16變量，8個約束方程77例：現(xiàn)有4份工作，4個人應聘，由于各人技術專長不同，他們承擔各項工作所需費用如下表所示，且規(guī)定每人只能做一項工作，每一項工作只能由一人承擔，試求使總費用最小的分派方案。工作人費用123412343545676889810101091110第i人做第j件事Z表示總費用i=1,2,3,4;j=1,2,3,4第i人不做第j件事782、費用矩陣

設有n個工作，要由n個人來承擔，每個工作只能由一個人承擔，且每個人只能承擔一個工作。cij表示第i個人做第j件事的費用,求總費用最低的指派方案。費用12…j…n12…i…ncij表示第i個人做第j件事的費用費用矩陣79例：現(xiàn)有4份工作，4個人應聘，由于個人的技術專長不同，他們承擔各項工作所需費用如下表所示，且規(guī)定每人只能做一項工作，每一項工作只能由一個人承擔，試求使總費用最小的分派方案。工作人收費用1234123435456768898101010911費用矩陣對應一個5個人5個工作的指派問題第2個人做第4個工作的費用5第4個人做第2個工作的費用080定理：在費用矩陣C=（cij）的任一行（列）中減去一個常數(shù)或加上一個常數(shù)不改變本問題的最優(yōu)解。n個人n個工作的指派問題1-b3、匈牙利法n個人n個工作的指派問題281i=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n-b8283-bi=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n84任務：對C的行和列減去某個常數(shù)，將C化的盡可能簡單，簡單到可一眼看出該問題的最優(yōu)解-b85指派問題的最優(yōu)解：若C中有n個位于不同行不同列的零元素，則令這些零元素對應的變量取1，其余變量取零，既得指派問題的最優(yōu)解i=1,2,3,4j=1,2,3,4可行解最優(yōu)解86匈牙利法的基本思路：對費用矩陣C的行和列減去某個常數(shù)，將C化成有n個位于不同行不同列的零元素，令這些零元素對應的變量取1，其余變量取零，即得指派問題的最優(yōu)解87例：有一份說明書要分別譯成英、日、德、俄四種文字，現(xiàn)交給甲、乙丙、丁四個人去完成，每人完成一種。由于個人的專長不同，翻譯成不同文字所需的時間（小時數(shù)）如右表，問應派哪個人去完成哪個任務，可使總花費時間最少？工作人時間英日德俄甲乙丙丁2151341041415914161378119-2-4-9-7最優(yōu)方案：

甲翻譯俄文，乙翻譯日文丙翻譯英文，丁翻譯德文總費用：28小時-4-288-2-4-9-7-4-2最優(yōu)解的取法：從含0元素最少的行或列開始，圈出一個0元素，用○表示，然后劃去該○所在的行和列中的其余0元素，用×表示，依次類推，若能得到n個○，則得最優(yōu)解X089例：求費用矩陣為右表的指派問題的最優(yōu)解工作人費用ABCDE甲乙丙丁戊12797989666717121412151466104107106-7-6-7-6-4得4個○，且不存在沒打×的0修改方法！90對n階費用矩陣C，若C有n個位于不同行不同列的零元素，即可得最優(yōu)解X0。否則，對C進行調(diào)整。-2+2-2最優(yōu)指派方案：甲做B工作，乙做C工作丙做A工作，丁做D工作戊做E工作？？91當C沒有n個位于不同行不同列的零元素時，對C進行調(diào)整。第一步：做能復蓋所有0元素的最小直線集合：1）對沒有○的行打√號2）對打√號的行上所有0元素的列打√號3）再對打√號的列上所有○的行打√號4）重復以上步驟直到得不出新的打√號為止5）對沒有打√號的行畫橫線，所有打√號的列畫縱線，所得到的直線既是復蓋所有0元素的最小直線集合具體步驟：√√√92第二步：在沒有被直線復蓋的元素中找出最小元素，讓打√號的列加上這個元素，打√號的行減去這個元素第三步：對所得到的矩陣畫○，若能得到n個○，則得最優(yōu)解，否則重復以上步驟，直至得到n個○。√√√+2-2-293例：求費用矩陣為下表的指派問題的最優(yōu)解工作人費用ABCDE甲乙丙丁戊12797989666717121412151466104107106-7-6-7-6-4√√√+2-2-2最優(yōu)指派方案：甲做B工作乙做C工作,丙做A工作丁做D工作,戊做E工作=3294匈牙利法的具體步驟：第一步：變換指派問題的費用矩陣，使其在各行各列都出現(xiàn)0元素：方法：首先每行元素減去該行的最小元素，然后每列減去該列的最小元素第二步：進行試指派（畫○）方法：從含0元素最少的行或列開始，圈出一個0

元素，用○表示，然后劃去該○所在的行和列中的其余0元素，用×表示，依次類推。若矩陣中的○的個數(shù)等于n，則得最優(yōu)解若矩陣中的○的個數(shù)<n，則進行第三步95第三步：做能覆蓋所有0元素的最小直線集合：1）對沒有○的行打√號2）對打√號的行上所有0元素的列打√號3）再對打√號的列上所有○的行打√號4）重復以上步驟直到得不出新的打√號為止5）對沒有打√號的行畫橫線，所有打√號的列畫縱線，所得到的直線既是復蓋所有0元素的最小直線集合第四步：在沒有被直線復蓋的元素中找出最小元素，讓打√號的列加上這個元素，打√號的行減去這個元素。轉(zhuǎn)第一步96

例：現(xiàn)有4份工作，4個人應聘，由于個人的技術專長不同，他們承擔各項工作所需費用如下表所示，且規(guī)定每人只能做一項工作，每一項工作只能由一個人承擔，試求使總費用最小的分派方案。工作人收費用1234123415182124192322182617161919212317最優(yōu)方案：第一個人做第一件事；

第二個人做第四件事；第三個人做第三件事；第四個人做第二件事；總費用：7097√√√√√√√√984、一般的指派問題(1)求maxZ的指派問題(2)人數(shù)與工作數(shù)不等的指派問題(3)一個人可做幾件事的指派問題(4)某事一定由（不能由）某人做的指派問題99收益12…j…n12…i…n指派問題模型：i=1,2,…,nj=1,2,…,n第i個人做第j人件事Z表示總收益i=1,2,…,n;j=1,2,…,n第i個人不做第j人件事

設有n個工作，要由n個人來承擔，每個工作只能由一個人承擔，且每個人只能承擔一個工作。cij表示第i個人做第j件事的收益,求總收益最大的指派方案。(1)求maxZ的指派問題100工作人收益12…j…n12…i…n指派問題最大化的數(shù)學模型：i=1,2,…,nj=1,2,…,n指派問題最小化的數(shù)學模型：i=1,2,…,nj=1,2,…,n用匈牙利法101i=1,2,…,nj=1,2,…,ni=1,2,…,nj=1,2,…,n102對maxZ的指派問題工作人收益12…j…n12…i…n用匈牙利法求C