運(yùn)籌學(xué)-4-整數(shù)規(guī)劃

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

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

工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應(yīng)求，故需要再建一家工廠。相應(yīng)的建廠方案有A3和A4兩個(gè)。這種物資的需求地有B1,B2,B3,B4四個(gè)。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運(yùn)費(fèi)cij，見下表：B1B2B3B4年生產(chǎn)能力A12934400A28357600A37612200A44525200年需求量350400300150工廠A3或A4開工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬或1500萬元。現(xiàn)要決定應(yīng)該建設(shè)工廠A3還是A4，才能使今后每年的總費(fèi)用最少。第四章整數(shù)規(guī)劃解：這是一個(gè)物資運(yùn)輸問題，特點(diǎn)是事先不能確定應(yīng)該建A3還是A4中哪一個(gè)，因而不知道新廠投產(chǎn)后的實(shí)際生產(chǎn)物資。為此，引入0-1變量：再設(shè)xij為由Ai運(yùn)往Bj的物資數(shù)量，單位為千噸；z表示總費(fèi)用，單位萬元。則該規(guī)劃問題的數(shù)學(xué)模型可以表示為：第四章整數(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ù)學(xué)模型：0--1規(guī)劃的數(shù)學(xué)模型：第四章整數(shù)規(guī)劃例×√√√√Z=130√√√√，可行且Z=140不可行可行第四章整數(shù)規(guī)劃（IP）（IP）問題的松弛問題第四章整數(shù)規(guī)劃∩≤松弛問題的最優(yōu)值是原整數(shù)規(guī)劃的目標(biāo)函數(shù)值的上界第四章整數(shù)規(guī)劃例

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

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

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

按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有限集，如右圖所示。其中(2,2),(3,1)點(diǎn)的目標(biāo)函數(shù)值最大，即為Z=4。第四章整數(shù)規(guī)劃-分支定界法1）求整數(shù)規(guī)劃的松弛問題最優(yōu)解； 若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否則轉(zhuǎn)下一步；2）分支與定界： 任意選一個(gè)非整數(shù)解的變量xi，在松弛問題中加上約束：xi≤[xi]和xi≥[xi]+1組成兩個(gè)新的松弛問題，稱為分枝。新的松弛問題具有特征：當(dāng)原問題是求最大值時(shí)，目標(biāo)值是分枝問題的上界；當(dāng)原問題是求最小值時(shí)，目標(biāo)值是分枝問題的下界。 檢查所有分枝的解及目標(biāo)函數(shù)值，若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值大于（max）等于其它分枝的目標(biāo)值，則將其它分枝剪去不再計(jì)算，若還存在非整數(shù)解并且目標(biāo)值大于(max)整數(shù)解的目標(biāo)值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。分支定界法的解題步驟：上界x1≤[x*01]x1≥[x*01]+1當(dāng)所有的子問題均被關(guān)閉或剪枝后目標(biāo)函數(shù)值最大的整數(shù)解既為所求的最優(yōu)解一、分枝定界法的原理：1、分枝··················012345678·松弛問題的可行域增加x1≤3增加x1≥4L1L2x1≤3x1≥4父問題子問題結(jié)論1：（IP）的最優(yōu)解一定在某個(gè)子問題中父問題的最優(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ù)項(xiàng)檢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é)點(diǎn)及分枝變量？1、分枝節(jié)點(diǎn)選擇的原則：盡快找到好的整數(shù)解，減少搜索節(jié)點(diǎn)，提高搜索效率。方法：（1）深探法：（2）廣探法：最后打開的節(jié)點(diǎn)最先選擇選擇有最大目標(biāo)函數(shù)值的節(jié)點(diǎn)繼續(xù)向下分枝2、分枝變量選擇的原則：尋找那些對問題影響最大的變量首先分枝（1）按目標(biāo)函數(shù)系數(shù)選擇：選擇目標(biāo)函數(shù)系數(shù)絕對值最大的變量首先分枝（2）按非整數(shù)變量選擇：選擇與整數(shù)值相差最大的非整數(shù)變量進(jìn)行分枝（3）按人為給定的順序選擇x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3第四章整數(shù)規(guī)劃-割平面法割平面法的基本思想：若整數(shù)規(guī)劃IP的松弛規(guī)劃L0的最優(yōu)解不是整數(shù)解，對L0增加一個(gè)約束條件，得線性規(guī)劃L1，此過程縮小了松弛規(guī)劃的可行解域，在切去松弛規(guī)劃的最優(yōu)解的同時(shí)，保留松弛規(guī)劃的任一整數(shù)解，因此整數(shù)規(guī)劃IP的解均在L1中，若L1的最優(yōu)解為整數(shù)解，則得IP的最優(yōu)解。若L1的最優(yōu)解不是整數(shù)解，重復(fù)以上步驟，由于可行解域在不斷縮小，且保留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------對應(yīng)于生成行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生成行對應(yīng)于生成行i的割平面非基變量44b010.500-0.5100-1.75103.255.500-1011310-0.25000.751.500-0.500-1.5z-9對應(yīng)第2行的割平面：對應(yīng)第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割平面計(jì)算步驟第一步：用單純形法解整數(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ī)劃的標(biāo)準(zhǔn)型：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ī)劃的標(biāo)準(zhǔn)型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。這時(shí)xi稱為0—1變量，或稱二進(jìn)制變量。xi僅取值0或1這個(gè)條件可由下述約束條件：

xi≤1

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

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

bi+yiM

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

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

單耗量產(chǎn)品資源IIIIII資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價(jià)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兩個(gè)特殊的數(shù)值，則稱此類模型為0—1的使用及建立模型的方法。隱枚舉法基本思想：隱枚舉法是分枝定界法思想的延伸。通過放松主約束條件（而非變量符號(hào)限制條件）求得最優(yōu)解，再檢查是否滿足約束條件，再經(jīng)過分枝與剪枝等工作迭代出最優(yōu)解。第四章整數(shù)規(guī)劃-隱枚舉法在2n個(gè)可能的變量組合中，往往只有一部分是可行解。只要發(fā)現(xiàn)某個(gè)變量組合不滿足其中一個(gè)約束條件時(shí)，就不必再去檢驗(yàn)其他約束條件是否可行。對于可行解，其目標(biāo)函數(shù)值也有優(yōu)劣之分。若已發(fā)現(xiàn)一個(gè)可行解，則根據(jù)它的目標(biāo)函數(shù)值可以產(chǎn)生一個(gè)過濾條件，對于目標(biāo)函數(shù)值比它差的變量組合不必再去檢驗(yàn)它的可行性。在以后的求解過程中，每當(dāng)發(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）相應(yīng)Z=3增加一個(gè)約束,目標(biāo)值>=33X1－2X2

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

逐一檢查如下點(diǎn)是否滿足約束條件？

約束條件（左邊）滿足約束條件?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

目標(biāo)函數(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）…….

逐一檢查如下點(diǎn)是否滿足約束條件？

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

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

逐一檢查如下點(diǎn)是否滿足約束條件？

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

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

逐一檢查如下點(diǎn)是否滿足約束條件？

約束條件（左邊）滿足條件?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

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

對于最大化問題，可按目標(biāo)函數(shù)中各變量系數(shù)由小到大的順序排列。對于最小化問題，可按目標(biāo)函數(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

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

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

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

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

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

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

設(shè)有n個(gè)工作，要由n個(gè)人來承擔(dān)，每個(gè)工作只能由一個(gè)人承擔(dān)，且每個(gè)人只能承擔(dān)一個(gè)工作。cij表示第i個(gè)人做第j件事的收益,求總收益最大的指派方案。(1)求maxZ的指派問題100工作人收益12…j…n12…i…n指派問題最大化的數(shù)學(xué)模型：i=1,2,…,nj=1,2,…,n指派問題最小化的數(shù)學(xué)模型：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