數(shù)學(xué)建模-整數(shù)規(guī)劃課件

數(shù)學(xué)建模*2022/11/23*2022/11/221第三部分整數(shù)規(guī)劃應(yīng)用實(shí)例分析整數(shù)規(guī)劃問(wèn)題的幾種求解方法分枝界定法隱枚舉法匈牙利法

蒙特卡洛法實(shí)驗(yàn)準(zhǔn)備*2022/11/23第三部分整數(shù)規(guī)劃*2022/11/222例1整數(shù)規(guī)劃問(wèn)題某廠擬購(gòu)進(jìn)甲、乙兩類機(jī)床生產(chǎn)新產(chǎn)品。已知甲、乙機(jī)床進(jìn)價(jià)分別為2萬(wàn)元和3萬(wàn)元；安裝占地面積分別為4m2和2m2；投后的收益分別為300元/日和200元/日。廠方目前僅有資金14萬(wàn)元，安裝面積18m2。為使收益最大，廠方應(yīng)購(gòu)進(jìn)甲、乙機(jī)床各多少臺(tái)？實(shí)例一整數(shù)規(guī)劃問(wèn)題甲型乙型現(xiàn)有量進(jìn)價(jià)（萬(wàn)元）2315占地面積（m2）4218利潤(rùn)（百元）32*例1整數(shù)規(guī)劃問(wèn)題某廠擬購(gòu)進(jìn)甲、乙兩類機(jī)床生產(chǎn)新產(chǎn)品。已3設(shè)設(shè)應(yīng)購(gòu)進(jìn)甲、乙機(jī)床臺(tái)數(shù)分別為x1和x2，工廠的收益為z。整數(shù)規(guī)劃(IP)1.模型建立s.t.實(shí)例一整數(shù)規(guī)劃問(wèn)題*設(shè)設(shè)應(yīng)購(gòu)進(jìn)甲、乙機(jī)床臺(tái)數(shù)分別為x1和x2，工廠的收益為z。整4formatshortc=[-3;-2];a=[2,3;4,2];b=[14;18];lb=[0;0];[x,Fval]=linprog(c,a,b,[],[],lb)先不考慮解的整數(shù)限制，問(wèn)題B的最優(yōu)解：x1=3.25，x2=2.5，

最優(yōu)值：z=14.75。2.模型求解設(shè)整數(shù)規(guī)劃問(wèn)題為A，與它相應(yīng)的線性規(guī)劃為問(wèn)題B，先來(lái)求解問(wèn)題B。1）舍去小數(shù)：取x1=3，x2=2，算出目標(biāo)函數(shù)值z(mì)=13。2）試探：如取x1=4，x2=1時(shí)，z=14，如取x1=3，x2=3時(shí)，不滿足約束條件，通過(guò)比較得到模型的最優(yōu)整數(shù)解。解法一：實(shí)例一整數(shù)規(guī)劃問(wèn)題*formatshort先不考慮解的整數(shù)限制，問(wèn)題B的2.51）不考慮解的整數(shù)限制，問(wèn)題B的最優(yōu)解：x1=3.25，x2=2.5，

最優(yōu)值：z=14.752.模型求解

解法二：設(shè)整數(shù)規(guī)劃問(wèn)題為A，與它相應(yīng)的線性規(guī)劃為問(wèn)題B實(shí)例一整數(shù)規(guī)劃問(wèn)題*1）不考慮解的整數(shù)限制，問(wèn)題B的最優(yōu)解：x1=3.25，x26

2.模型求解因?yàn)?與3之間無(wú)整數(shù)，故這兩個(gè)子集的整數(shù)解必與原可行集合整數(shù)解一致，這一步驟稱為分枝。對(duì)問(wèn)題A分枝構(gòu)成兩個(gè)子問(wèn)題稱為B1和B2。問(wèn)題B1數(shù)學(xué)模型：s.t.問(wèn)題B2數(shù)學(xué)模型：s.t.實(shí)例一整數(shù)規(guī)劃問(wèn)題*

2.模型求解因?yàn)?與3之間無(wú)整數(shù)，故這兩個(gè)子集的整數(shù)解72.模型求解B2最優(yōu)解：

x1=4，x2=1，z2=14

B1最優(yōu)解：

x1=3，x2=8/3，z1=43/3圖解法（單純形法）求得的最優(yōu)解分別為：實(shí)例一整數(shù)規(guī)劃問(wèn)題*2.模型求解B2最優(yōu)解：x1=4，x2=1，z2=14

B84）對(duì)問(wèn)題B1在進(jìn)行分枝，得問(wèn)題B11和B122.模型求解

問(wèn)題B11數(shù)學(xué)模型：s.t.問(wèn)題B12數(shù)學(xué)模型：s.t.實(shí)例一整數(shù)規(guī)劃問(wèn)題*4）對(duì)問(wèn)題B1在進(jìn)行分枝，得問(wèn)題B11和B122.模型求解

9求解問(wèn)題B11和B12

得到：2.模型求解

5）此時(shí)由于所有子問(wèn)題的目標(biāo)值均小于或等于z2，故問(wèn)題A的目標(biāo)函數(shù)最優(yōu)值z(mì)*=z2=14，最優(yōu)解為x1=4，x2=1。B11最優(yōu)解：

x1=3，x2=2，z11=13B12最優(yōu)解：

x1=2.5，x2=3，z12=13.5實(shí)例一整數(shù)規(guī)劃問(wèn)題*求解問(wèn)題B11和B12得到：2.模型求解

5）此時(shí)由于所10整數(shù)規(guī)劃整數(shù)規(guī)劃（IntegerProgramming）數(shù)學(xué)規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。整數(shù)規(guī)劃分類：（1）變量全限制為整數(shù)時(shí)，稱純（完全）整數(shù)規(guī)劃。（2）

變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。*2022/11/23整數(shù)規(guī)劃整數(shù)規(guī)劃（IntegerProgramming）*11整數(shù)規(guī)劃整數(shù)規(guī)劃特點(diǎn)（i）原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況：①原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。②整數(shù)規(guī)劃無(wú)可行解。③有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值變差。（ii）整數(shù)規(guī)劃最優(yōu)解不能按照實(shí)數(shù)最優(yōu)解簡(jiǎn)單取整而獲得。*2022/11/23整數(shù)規(guī)劃整數(shù)規(guī)劃特點(diǎn)*2022/11/2212整數(shù)規(guī)劃整數(shù)規(guī)劃求解方法分類（1）分枝定界法—可求純或混合整數(shù)線性規(guī)劃。（2）割平面法—可求純或混合整數(shù)線性規(guī)劃。（3）隱枚舉法—求解“0-1”整數(shù)規(guī)劃：①過(guò)濾隱枚舉法；②分枝隱枚舉法。（4）匈牙利法—解決指派問(wèn)題（特殊“0-1”規(guī)劃）。（5）蒙特卡洛法—求解各種類型規(guī)劃。*2022/11/23整數(shù)規(guī)劃整數(shù)規(guī)劃求解方法分類*2022/11/2213分枝定界法（1）分枝：通常，把全部可行解空間反復(fù)地分割為越來(lái)越小的子集，稱為分枝；（2）定界：并且對(duì)每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界（對(duì)于最小值問(wèn)題），這稱為定界。（3）剪枝：在每次分枝后，凡是界限超出已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝，這樣，許多子集可不予考慮，這稱剪枝。求解生產(chǎn)進(jìn)度問(wèn)題、旅行推銷員問(wèn)題、工廠選址問(wèn)題、背包問(wèn)題及分配問(wèn)題。分枝定界法*2022/11/23分枝定界法分枝定界法*2022/11/2214分枝定界法步驟（1）求解整數(shù)規(guī)劃問(wèn)題A對(duì)應(yīng)的線性規(guī)劃問(wèn)題B（松弛問(wèn)題）；（2）分枝，在松弛問(wèn)題B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量xj，其值為bj，以[bj]表示小于bj的最大整數(shù)，構(gòu)造兩個(gè)約束條件

將這兩個(gè)約束條件，分別加入問(wèn)題B，求兩個(gè)后繼規(guī)劃問(wèn)題B1和B2。分枝定界法*2022/11/23分枝定界法步驟分枝定界法*2022/11/2215

分枝定界法*2022/11/23

分枝定界法*2022/11/2216···············1234567·松弛問(wèn)題的可行域增加x1≤3增加x1≥4L1L2分枝定界法例2*·····17x1≤3x1≥4父問(wèn)題子問(wèn)題結(jié)論1：（IP）的最優(yōu)解一定在某個(gè)子問(wèn)題中父問(wèn)題的最優(yōu)值≤3：子問(wèn)題中的整數(shù)解都是（IP）的可行解子問(wèn)題的最優(yōu)解2：子問(wèn)題的可行域父問(wèn)題的可行域∩*x1≤3x1≥4父問(wèn)題子問(wèn)題結(jié)論1：（IP）的最優(yōu)解18x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3···············1234567·4x1+x2=16.52x1+3x2=14.5z=30x1+20x2*x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3·19某公司擬在市東、西、南三區(qū)建立門市部，擬議中有7個(gè)位置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元，每年可獲利潤(rùn)估計(jì)為ci元，但投資總額不能超過(guò)B元。問(wèn)應(yīng)選擇哪些點(diǎn)可使年利潤(rùn)最大？0-1變量例3投資場(chǎng)所的選定—0-1變量*0-1變量例3投資場(chǎng)所的選定—0-1變量*20s.t.1.模型建立目標(biāo)函數(shù)：約束條件：在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。0-1變量*s.t.1.模型建立目標(biāo)函數(shù)：約束條件：在東區(qū)，由A1，A210-1型整數(shù)規(guī)劃0-1型整數(shù)規(guī)劃決策變量只能取0或1的整數(shù)規(guī)劃，叫做0-1整數(shù)規(guī)劃。決策變量稱為0-1變量(二進(jìn)制變量、邏輯變量)。0-1變量作為邏輯變量，常被用來(lái)表示系統(tǒng)是否處于某個(gè)特定狀態(tài)，或者決策時(shí)是否取某個(gè)特定方案。在實(shí)際問(wèn)題中引入0-1變量，可以把各種情況需要分別討論的數(shù)學(xué)規(guī)劃問(wèn)題統(tǒng)一在一個(gè)問(wèn)題中討論了。*2022/11/230-1型整數(shù)規(guī)劃0-1型整數(shù)規(guī)劃*2022/11/2222

某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表格所示。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最大?貨物甲乙托運(yùn)限制體積每箱（米3）5424重量每箱（百公斤）2513利潤(rùn)每箱（百元）20100-1型整數(shù)規(guī)劃例4—互相排斥的計(jì)劃*某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲230-1型整數(shù)規(guī)劃

1.模型建立+(1-y)M+yM假設(shè)現(xiàn)在有車運(yùn)和船運(yùn)兩種運(yùn)輸方式，但只能選擇一種運(yùn)輸方式，如用車運(yùn)時(shí)關(guān)于體積的限制條件為5x1+4x2≤24(車)。如用船運(yùn)時(shí)關(guān)于體積的限制條件為7x1+3x2≤45(船)。（這兩條件互相排斥）。設(shè)甲、乙兩種貨物的托運(yùn)箱數(shù)分別為x1，x2，可獲得的利潤(rùn)為z。設(shè)變量y表示運(yùn)貨的方式，當(dāng)y為1時(shí)，用車運(yùn)，y為0時(shí)，用船運(yùn)。M是充分大的數(shù)*2022/11/230-1型整數(shù)規(guī)劃1.模型建立+(1-y)M+yM240-1型整數(shù)規(guī)劃

模型分析有多個(gè)相互排斥的約束條件*2022/11/230-1型整數(shù)規(guī)劃模型分析有多個(gè)相互排斥的約束條件*202225相互排斥的約束條件如果有m個(gè)互相排斥的約束條件（<=型）：為了保證這個(gè)約束條件只有一個(gè)起作用，我們引入m個(gè)0-1變量和一個(gè)充分大的常數(shù)M，下面這一組m+1個(gè)約束條件符合上述要求。0-1型整數(shù)規(guī)劃*相互排斥的約束條件如果有m個(gè)互相排斥的約束條件（<=型）：26有三種自然資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費(fèi)用及售價(jià)、資源單位消耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用如下表。要求制訂一個(gè)生產(chǎn)計(jì)劃，使總收益最大。－12108單位售價(jià)－200150100固定費(fèi)用－654

單位可變費(fèi)用100321C300432B500842A資源量IIIIII

單耗量資源產(chǎn)品例5—固定費(fèi)用問(wèn)題0-1型整數(shù)規(guī)劃*有三種自然資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變27解：設(shè)xj是第j種產(chǎn)品的產(chǎn)量，j=1，2，3；再設(shè)若生產(chǎn)第j種產(chǎn)品（即xj>0）若不生產(chǎn)第j種產(chǎn)品（即xj=0）j=1，2，3則問(wèn)題的模型為s.t.

如果生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj＞0，由xj≤Mjyj知，yj＝1。因此，相應(yīng)的固定費(fèi)用在目標(biāo)函數(shù)中將被考慮。

同理，如果不生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj=0，只有yj為0才有意義，因此，相應(yīng)的固定費(fèi)用不應(yīng)在目標(biāo)函數(shù)中被考慮。0-1型整數(shù)規(guī)劃*2022/11/23解：設(shè)xj是第j種產(chǎn)品的產(chǎn)量，j=1，2，3；再設(shè)若生產(chǎn)第j280-1型整數(shù)規(guī)劃解法只檢查變量取值的組合的一部分的方法。

：求解下列問(wèn)題隱枚舉法(a)(b)(c)(d)例6*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法(a)例6*2022/11/2290-1型整數(shù)規(guī)劃解法解法一：隱枚舉法(x1,x2,x3)z值abcd過(guò)濾條件(0,0,0)0√√√√Z≥0(0,0,1)5√√√√Z≥5(0,1,0)-2(0,1,1)3(1,0,0)3Z≥8(1,0,1)√√√√(1,1,0)81(1,1,1)6所以，最優(yōu)解(x1，x2，x3)T=(1，0，1)T，maxz=8。*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法(x1,x2,x3)z值abc300-1型整數(shù)規(guī)劃解法為了使最優(yōu)解盡可能早出現(xiàn)，可先將目標(biāo)函數(shù)中各變量的順序按其系數(shù)大小重新排列，這樣可進(jìn)一步減少計(jì)算量。隱枚舉法按目標(biāo)函數(shù)中各變量系數(shù)的大小重新排列各變量最大化問(wèn)題：由小到大最小化問(wèn)題：由大到小*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法按目標(biāo)函數(shù)中各變量系數(shù)的大小重31解法二（優(yōu)化）：重新排列xj的順序(系數(shù)遞減)0-1型整數(shù)規(guī)劃解法*解法二（優(yōu)化）：重新排列xj的順序(系數(shù)遞減)0-1型整數(shù)320-1型整數(shù)規(guī)劃計(jì)算表目標(biāo)函數(shù)z＝3x1－2x2＋5x3＝5x3＋3x1－2x2

最大值的上限是8，第二大的值是5…5x3＋3x1－2x2≥8⑤點(diǎn)(x3,x1,x2)約束條件滿足條件?是∨否×z值⑤①②③④(1,1,0)8∨∨∨∨∨8隱枚舉法：共計(jì)算5次(均滿足約束條件)。（最優(yōu)解為1，0，1，最優(yōu)值8）可根據(jù)計(jì)算逐漸改變過(guò)濾條件(該例因最大值的點(diǎn)滿足其他四個(gè)約束，即找到最大化問(wèn)題的最好的整數(shù)解。就不需驗(yàn)證計(jì)算第二大值的點(diǎn)是否滿足約束條件)0-1型整數(shù)規(guī)劃解法過(guò)濾隱枚舉法*0-1型整數(shù)規(guī)劃計(jì)算表目標(biāo)函數(shù)z＝3x1－2x2＋5x3＝33步驟1：將問(wèn)題轉(zhuǎn)化為如下標(biāo)準(zhǔn)形式：其中cj≥0，且c1≤c2≤…≤cn。例7求解0-1整數(shù)規(guī)劃（選學(xué)-分枝隱枚舉法）0-1型整數(shù)規(guī)劃解法*步驟1：將問(wèn)題轉(zhuǎn)化為如下標(biāo)準(zhǔn)形式：其中cj≥0，且c1≤c34⑵如約束條件為≤，兩邊同乘(-1)；如約束條件為等式，可令變量，代入目標(biāo)函數(shù)和其它約束條件中，將xn消掉。⑶按目標(biāo)函數(shù)中系數(shù)由小到大的順序重新排列變量，并將約束條件中的排列順序做相應(yīng)改變。

⑴如目標(biāo)函數(shù)為maxz，令，可化為。如某個(gè)變量的系數(shù)為負(fù)，令，使系數(shù)變正。0-1型整數(shù)規(guī)劃解法步驟1：將問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式：*⑵如約束條件為≤，兩邊同乘(-1)；如約束條件為等式，35調(diào)整后的0-1規(guī)劃問(wèn)題變?yōu)椋?a)(b)

步驟2：令所有變量取0，求出目標(biāo)函數(shù)值，并代入約束條件中檢查是否可行，如果可行即為問(wèn)題的最優(yōu)解；否則轉(zhuǎn)下一步。

令，得＝-10，但不滿足兩個(gè)約束條件。0-1型整數(shù)規(guī)劃解法*調(diào)整后的0-1規(guī)劃問(wèn)題變?yōu)椋?a)(b)步驟2：令所36

步驟3：分支和定界。依次令各變量分別取0或1，將問(wèn)題劃分為兩個(gè)子問(wèn)題，分別檢查解是否可行，如不可行繼續(xù)對(duì)邊界值較小的子問(wèn)題分支，直到找出一個(gè)可行解為止，這時(shí)得到值的一個(gè)上界。分支過(guò)程見下圖所示：0-1型整數(shù)規(guī)劃解法*步驟3：分支和定界。依次令各變量分別取0或1，將問(wèn)題劃37步驟4：考察所有子問(wèn)題，有以下四種情況：

⑴若某個(gè)子問(wèn)題的邊界值對(duì)應(yīng)原問(wèn)題的可行解，則將它的邊界值與保留的值作比較，并取較優(yōu)的一個(gè)作為新的值。如所有子問(wèn)題都已考察完畢，則保留下來(lái)的值及其對(duì)應(yīng)的解即為0-1整數(shù)規(guī)劃問(wèn)題的最優(yōu)解。⑵若某個(gè)子問(wèn)題的邊界值大于保留下來(lái)的值，不管其是否可行，則將這一分支剪掉。⑶若某個(gè)子問(wèn)題不可行（在該分支中的上級(jí)變量的值已經(jīng)確定的情況下，其余變量不管取什么值都無(wú)法滿足所有約束時(shí)，該枝的分枝已無(wú)可行解），則將這一分支剪掉。⑷若某個(gè)子問(wèn)題可行且邊界值優(yōu)于值，但該邊界值對(duì)應(yīng)的解不是可行解，則該問(wèn)題待考察。如有多個(gè)問(wèn)題待考察，優(yōu)先對(duì)其中最優(yōu)值最大的一個(gè)子問(wèn)題進(jìn)行考察，轉(zhuǎn)步驟3。0-1型整數(shù)規(guī)劃解法*步驟4：考察所有子問(wèn)題，有以下四種情況：⑴若某個(gè)子38

分支③邊界值=-6＜-4，但相應(yīng)的解不可行，需繼續(xù)分支。過(guò)程如上圖所示。0-1型整數(shù)規(guī)劃解法*分支③邊界值=-6＜-4，但相應(yīng)的解不可行，需繼續(xù)39上述求解過(guò)程也可用表格表示：(0，1，0，1，0)(0，1，1，0，0)(0，0，1，0，0)(1，0，1，0，0)(1，1，0，0，0)(0，1，0，0，0)(1，0，0，0，0)(0，0，0，0，0)

＞-4，剪枝1⑨

＞-4，剪枝-1⑧不可行，剪枝×-5⑦

＞-4，剪枝-3⑤可行≤-4√√-4④×-6③×√-8②×-10①ba備注約束條件z值序號(hào)0-1型整數(shù)規(guī)劃解法*上述求解過(guò)程也可用表格表示：(0，1，0，1，0)(0，140所以，最優(yōu)解：即原問(wèn)題的最優(yōu)解為：分枝隱枚舉法0-1型整數(shù)規(guī)劃解法*所以，最優(yōu)解：即原問(wèn)題的最優(yōu)解為：分枝隱枚舉法0-1型41指派問(wèn)題（0-1型）一、指派問(wèn)題擬派n人去做n項(xiàng)工作，由于每人的專長(zhǎng)不同，各人完成不同任務(wù)效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高的問(wèn)題，這類問(wèn)題稱為指派問(wèn)題(分派問(wèn)題、分配問(wèn)題)B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人任務(wù)cij表示第i個(gè)人完成第j項(xiàng)任務(wù)的效率。*指派問(wèn)題（0-1型）一、指派問(wèn)題B1B2BnA1c11c1242二、指派問(wèn)題的數(shù)學(xué)模型=(Cij)指派問(wèn)題系數(shù)矩陣B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人任務(wù)解：設(shè)指派問(wèn)題（0-1型）*二、指派問(wèn)題的數(shù)學(xué)模型=(Cij)B1B2BnA1c11c143某單位現(xiàn)在Ａ、Ｂ、Ｃ、Ｄ四項(xiàng)工作需完成，現(xiàn)在甲、乙、丙、丁四個(gè)人均可完成這四項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)所用的時(shí)間如右表所示，問(wèn)應(yīng)指派何人去完成何項(xiàng)任務(wù)，使所需時(shí)間最少？甲215134乙1041415丙9141613丁78119ABCD任務(wù)人員滿足所有約束條件的可行解xij也可寫成表格或矩陣形式，稱為解矩陣(xij)=本例的一個(gè)可行解矩陣(cij)=例8指派問(wèn)題指派問(wèn)題（0-1型）*某單位現(xiàn)在Ａ、Ｂ、Ｃ、Ｄ四項(xiàng)工作需完成，現(xiàn)在甲、乙、丙、丁四44指派問(wèn)題數(shù)學(xué)模型的性質(zhì)：若從指派問(wèn)題的系數(shù)的系數(shù)矩陣（cij）的一行（列）各元素中分別減去該行（列）的最小元素，得到新矩陣（bij），那么以（bij）為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。獨(dú)立的0元素：位于不同行不同列的0元素稱為獨(dú)立的0元素。結(jié)論：若能在系數(shù)矩陣(bij)中找出n個(gè)獨(dú)立的0元素；則令解矩陣(xij)中對(duì)應(yīng)這n個(gè)獨(dú)立的0元素取值為1，其它元素取值為0。將其代入目標(biāo)函數(shù)中得到zk=0，它一定是最小。這就是以(bij)為系數(shù)矩陣的指派問(wèn)題的最優(yōu)解，也就得到了問(wèn)題的最優(yōu)解。指派問(wèn)題（0-1型）*指派問(wèn)題數(shù)學(xué)模型的性質(zhì)：若從指派問(wèn)題的系數(shù)的系45三、指派問(wèn)題的解法（匈牙利法）第一步:使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行各列都出現(xiàn)０元素。（１）從系數(shù)矩陣的每行元素減去該行的最小元素；（２）再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的最小元素。2497min24min指派問(wèn)題（0-1型）*三、指派問(wèn)題的解法（匈牙利法）第一步:使指派問(wèn)題的系數(shù)矩陣經(jīng)46經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；只需找出n個(gè)獨(dú)立的0元素，若能找出，就以這些獨(dú)立的0元素對(duì)應(yīng)解矩陣中的元素為1，其它作為0，這就得到最優(yōu)解。找獨(dú)立0元素的步驟如下：第二步：進(jìn)行試指派，以尋求最優(yōu)解。0（1）從只有一個(gè)0元素的行開始，給這個(gè)0元素加圈，記作◎.然后再劃去◎所在列的其它0元素，記作。（2）給只有一個(gè)0元素的列的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作。0指派問(wèn)題（0-1型）*經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；只需找47（3）反復(fù)(1),(2)兩步，直到所有0元素都被圈出和劃掉為止。（4）若各行各列均有多于2個(gè)的0元素未被圈出或劃掉，任選其中任意一個(gè)0元素加圈。（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么指派問(wèn)題的最優(yōu)解已得到，若m<n，則轉(zhuǎn)入下一步。第二步：進(jìn)行試指派，以尋求最優(yōu)解。指派問(wèn)題（0-1型）*（3）反復(fù)(1),(2)兩步，直到所有0元素都被圈出和劃掉為48min76746指派問(wèn)題（0-1型）*min76746指派問(wèn)題（0-1型）*49第三步：作最少的直線覆蓋所有0元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立0元素?cái)?shù)。（5）對(duì)沒(méi)有打√號(hào)的行畫一橫線，有打√號(hào)的列畫一縱線，這就得到覆蓋所有0元素的最少直線。（1）對(duì)沒(méi)有◎的行打√號(hào)；（2）對(duì)已打√號(hào)的行中所有含劃0元素的列打√號(hào)；（3）再對(duì)打有√號(hào)的列中含◎元素的行打√號(hào)；（4）重復(fù)(2)、(3)直到得不出新的打√號(hào)的行、列為止；√√√指派問(wèn)題（0-1型）*第三步：作最少的直線覆蓋所有0元素，以確定該系數(shù)矩陣中能找到50第四步：對(duì)第三步所得矩陣進(jìn)行變換，目的是增加0元素。在沒(méi)有被直線覆蓋的部分中找出最小元素。然后在打√行各元素中都減去該最小元素，而在打√列的各元素都加上該最小元素（以保證原來(lái)的0元素不變）。這樣得到新系數(shù)矩陣。重復(fù)第二步。指派問(wèn)題（0-1型）√√√*第四步：對(duì)第三步所得矩陣進(jìn)行變換，目的是增加0元素。在沒(méi)51第五步：系數(shù)矩陣(bij)中找出n個(gè)獨(dú)立的0元素；則令解矩陣(xij)中對(duì)應(yīng)這n個(gè)獨(dú)立的0元素取值為1，其它元素取值為0。∵獨(dú)立0元素的個(gè)數(shù)等于系數(shù)矩陣的階數(shù)∴得到了最優(yōu)解最優(yōu)解矩陣為：指派問(wèn)題（0-1型）*第五步：系數(shù)矩陣(bij)中找出n個(gè)獨(dú)立的0元素；則令解矩陣52練習(xí)：有4個(gè)工人，要指派他們分別完成4項(xiàng)工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表：ABCD甲乙丙丁15192619182317212122162324181917工作工人指派問(wèn)題（0-1型）*練習(xí)：有4個(gè)工人，要指派他們分別完成4項(xiàng)工作，每人做各項(xiàng)工作53解：用匈牙利法求解過(guò)程如下：min15181617√√√min1√√√√√指派問(wèn)題（0-1型）*解：用匈牙利法求解過(guò)程如下：min15181617√√√mi54四、非標(biāo)準(zhǔn)形式的指派問(wèn)題（選學(xué)）1、最大化指派問(wèn)題2、人數(shù)和事數(shù)不等的指派問(wèn)題3、一個(gè)人可做幾件事的指派問(wèn)題4、某事一定不能由某人做的指派問(wèn)題指派問(wèn)題（0-1型）*四、非標(biāo)準(zhǔn)形式的指派問(wèn)題（選學(xué)）1、最大化指派問(wèn)題指派問(wèn)題（551、求最大化的指派問(wèn)題令bij=M-cij其中：M是足夠大的常數(shù)（cij中最大元素）用匈牙利法求解（bij）即可。所得最小解就是原問(wèn)題的最大解。指派問(wèn)題（0-1型）*1、求最大化的指派問(wèn)題令bij=M-cij指派問(wèn)題（0-1型562、人數(shù)和任務(wù)數(shù)不等的指派問(wèn)題若人少任務(wù)多，則添上一些虛擬的“人”。這些虛擬的“人”完成各任務(wù)的費(fèi)用系數(shù)可取0，理解為這些費(fèi)用實(shí)際上不會(huì)發(fā)生。若人多任務(wù)少，則添上一些虛擬的“任務(wù)”，這些虛擬的“任務(wù)”由各人完成的費(fèi)用系數(shù)同樣也取0。指派問(wèn)題（0-1型）*2、人數(shù)和任務(wù)數(shù)不等的指派問(wèn)題若人少任務(wù)多，則添上一些虛擬的573、一個(gè)人可做幾件事的指派問(wèn)題若某個(gè)人可完成幾項(xiàng)任務(wù)，則可將人化作相同的幾個(gè)“人”，來(lái)接受指派，這幾個(gè)“人”完成同一項(xiàng)任務(wù)的費(fèi)用系數(shù)都一樣。4、某項(xiàng)任務(wù)一定不能由某人完成的指派問(wèn)題若某項(xiàng)任務(wù)一定不能由某個(gè)人完成，則可將相應(yīng)的費(fèi)用系數(shù)取作足夠大的數(shù)M。指派問(wèn)題（0-1型）*3、一個(gè)人可做幾件事的指派問(wèn)題若某個(gè)人可完成幾項(xiàng)任務(wù)，則58例9：分配甲、乙、丙、丁四個(gè)人去完成五項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)時(shí)間如下表所示。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個(gè)人可兼完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)。試確定總花費(fèi)時(shí)間為最少的指派方案。ABCDE甲2529314237乙3938262033丙3427284032丁2442362345指派問(wèn)題（0-1型）*例9：分配甲、乙、丙、丁四個(gè)人去完成五項(xiàng)任務(wù)。每人完成各項(xiàng)任591、m約束條件中只有k個(gè)起作用設(shè)m個(gè)約束條件可表示為：定義又M為任意大的正數(shù)，得指派問(wèn)題（0-1型）*1、m約束條件中只有k個(gè)起作用設(shè)m個(gè)約束條件可表示為：定義又602、約束條件的右端項(xiàng)可能是r個(gè)值中的某一個(gè)即定義指派問(wèn)題（0-1型）*2、約束條件的右端項(xiàng)可能是r個(gè)值中的某一個(gè)即定義指派問(wèn)題（0613、兩組條件中滿足其中一組若x1≤4，則x2≥1；否則（即x1>4）,x2≤3又M為任意大正數(shù)，則問(wèn)題可表達(dá)為：指派問(wèn)題（0-1型）*3、兩組條件中滿足其中一組若x1≤4，則x2≥1；否則（即x624、用以表示固定費(fèi)用的函數(shù)生產(chǎn)費(fèi)用函數(shù)：引入變量yj指派問(wèn)題（0-1型）*4、用以表示固定費(fèi)用的函數(shù)生產(chǎn)費(fèi)用函數(shù)：引入變量yj指派問(wèn)題63例10東方大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室聘用4名大學(xué)生（代號(hào)1、2、3、4）和2名研究生（代號(hào)5、6）值班答疑。已知每人從周一至周五每天最多可安排的值班時(shí)間及每人每h值班的報(bào)酬如下表學(xué)生代號(hào)報(bào)酬（元/h)每天最多可安排的值班時(shí)間周一周二周三周四周五12345610109.99.810.811.306070606083055604048006063應(yīng)用舉例*例10東方大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室聘用4名大學(xué)生（代號(hào)1、2、64該實(shí)驗(yàn)室開放時(shí)間是上午8點(diǎn)至晚上10點(diǎn)，開放時(shí)間內(nèi)須有且僅需一名學(xué)生值班，規(guī)定大學(xué)生每周值班不少于8h，研究生每周不少于7h，每名學(xué)生每周值班不超過(guò)3次，每次值班不少于2h，每天安排值班的學(xué)生不超過(guò)3人且其中必須有一名研究生，試為該實(shí)驗(yàn)室安排一張人員的值班表，使總支付的報(bào)酬最少解：設(shè)xij為學(xué)生i在周j的值班時(shí)間，安排學(xué)生i在周j值班否則用aij代表學(xué)生i在周j最多可安排的值班時(shí)間，ci為學(xué)生i的每h的報(bào)酬，則其數(shù)學(xué)模型為應(yīng)用舉例*該實(shí)驗(yàn)室開放時(shí)間是上午8點(diǎn)至晚上10點(diǎn)，開放時(shí)間內(nèi)須有解：65不超過(guò)可安排時(shí)間大學(xué)生每周值班不少于8h研究生每周值班不少于7h實(shí)驗(yàn)室每天開放14h每名學(xué)生一周值班不超過(guò)3次每天值班不超過(guò)3人每天有一名研究生值班應(yīng)用舉例*不超過(guò)可安排時(shí)間大學(xué)生每周值班不少于8h研究生每周值班不少于66學(xué)生代號(hào)一二三四五123456674685622263最優(yōu)結(jié)果為總支付報(bào)酬每周727.5元值班方案為：應(yīng)用舉例*學(xué)生代號(hào)一二三四67蒙特卡洛法—整數(shù)規(guī)劃蒙特卡洛法(MonteCarlomethod)也稱為隨機(jī)取樣法，進(jìn)行大統(tǒng)計(jì)量（N→∞）的統(tǒng)計(jì)實(shí)驗(yàn)方法或計(jì)算機(jī)隨機(jī)模擬方法。當(dāng)所求解問(wèn)題是某種隨機(jī)事件出現(xiàn)的概率，或者是某個(gè)隨機(jī)變量的期望值時(shí)，通過(guò)某種“實(shí)驗(yàn)”的方法，以這種事件出現(xiàn)的頻率估計(jì)這一隨機(jī)事件的概率，或者得到這個(gè)隨機(jī)變量的某些數(shù)字特征，并將其作為問(wèn)題的解。大數(shù)定理：均勻分布的算術(shù)平均收斂于真值中心極限定理：置信水平下的統(tǒng)計(jì)誤差

*2022/11/23蒙特卡洛法—整數(shù)規(guī)劃蒙特卡洛法(MonteCarlome68MonteCarlo方法的基本思想很早以前就被人們所發(fā)現(xiàn)和利用。早在17世紀(jì)，人們就知道用事件發(fā)生的“頻率”來(lái)決定事件的“概率”。19世紀(jì)人們用投針試驗(yàn)的方法來(lái)決定圓周率π。本世紀(jì)40年代計(jì)算機(jī)的出現(xiàn)、特別是近年來(lái)高速計(jì)算機(jī)的出現(xiàn)，使得用數(shù)學(xué)方法在計(jì)算機(jī)上大量、快速地模擬這樣的試驗(yàn)成為可能。使用蒙特卡羅方法估算π值.放置30000個(gè)隨機(jī)點(diǎn)后,π的估算值與真實(shí)值相差0.07%.蒙特卡洛法—整數(shù)規(guī)劃*MonteCarlo方法的基本思想很早以前就被人們所發(fā)現(xiàn)和69蒙特卡洛法—整數(shù)規(guī)劃求解問(wèn)題可以分為兩類:確定性問(wèn)題和隨機(jī)性問(wèn)題。

解題步驟：

1.根據(jù)提出的問(wèn)題構(gòu)造一個(gè)簡(jiǎn)單、適用的概率模型或隨機(jī)模型，使問(wèn)題的解對(duì)應(yīng)于該模型中隨機(jī)變量的某些特征（如概率、均值和方差等），所構(gòu)造的模型在主要特征參量方面要與實(shí)際問(wèn)題或系統(tǒng)相一致

2.根據(jù)模型中各個(gè)隨機(jī)變量的分布，在計(jì)算機(jī)上產(chǎn)生隨機(jī)數(shù)，實(shí)現(xiàn)一次模擬過(guò)程所需的足夠數(shù)量的隨機(jī)數(shù)。通常先產(chǎn)生均勻分布的隨機(jī)數(shù)，然后生成服從某一分布的隨機(jī)數(shù)，方可進(jìn)行隨機(jī)模擬試驗(yàn)。

*2022/11/23蒙特卡洛法—整數(shù)規(guī)劃求解問(wèn)題可以分為兩類:確定性問(wèn)題和隨機(jī)性70蒙特卡洛法—整數(shù)規(guī)劃

解題步驟：

3.根據(jù)概率模型的特點(diǎn)和隨機(jī)變量的分布特性，設(shè)計(jì)和選取合適的抽樣方法，并對(duì)每個(gè)隨機(jī)變量進(jìn)行抽樣（包括直接抽樣、分層抽樣、相關(guān)抽樣、重要抽樣等）。

4.按照所建立的模型進(jìn)行仿真試驗(yàn)、計(jì)算，求出問(wèn)題的隨機(jī)解。

5.統(tǒng)計(jì)分析模擬試驗(yàn)結(jié)果，給出問(wèn)題的概率解以及解的精度估計(jì)。*2022/11/23蒙特卡洛法—整數(shù)規(guī)劃

解題步驟：*2022/11/2271蒙特卡洛法—整數(shù)規(guī)劃例：隨機(jī)變量x={0，1，2}表示每分鐘到達(dá)超市收款臺(tái)的人數(shù)，有分布列模擬十分鐘內(nèi)顧客到達(dá)收款臺(tái)的狀況。xk012pk

0.40.30.3r=rand(1,10);fori=1:10;ifr(i)<0.4n(i)=0;elseif0.4<=r(i)&r(i)<0.7n(i)=1;elsen(i)=2;endendendr,n*2022/11/23蒙特卡洛法—整數(shù)規(guī)劃例：隨機(jī)變量x={0，1，2}表示每72如下圖，正方形的面積A=1；1/4圓的面積B=π/4。我們想象有一個(gè)容器在正方形中夾有一個(gè)極薄的圓弧隔板。下小雨時(shí)搬至屋外，經(jīng)一定時(shí)間后，稱1/4圓的容器內(nèi)的水重C，與作為一個(gè)整體的正方形中的水重D。C與D之比應(yīng)該等于B與A之比，即可得

例10求π的近似值蒙特卡洛法—整數(shù)規(guī)劃*

例10求π的近似值蒙特卡洛法—整數(shù)規(guī)劃*73讓計(jì)算機(jī)來(lái)模擬雨點(diǎn)落下：產(chǎn)生偽隨機(jī)數(shù)x和y，讓x的值的范圍在0～1之間；讓y的值的范圍也在0～1之間，模擬雨點(diǎn)落在正方形中，當(dāng)然會(huì)有的雨點(diǎn)落在1/4圓中。數(shù)以百萬(wàn)計(jì)雨點(diǎn)可以累計(jì)得到C和D，從而上述公式算出π的近似值。關(guān)鍵點(diǎn)：落入扇形區(qū)的判據(jù)

蒙特卡洛法—整數(shù)規(guī)劃*讓計(jì)算機(jī)來(lái)模擬雨點(diǎn)落下：

蒙特卡洛法—整數(shù)規(guī)劃*74蒙特卡洛法—整數(shù)規(guī)劃

%隨機(jī)模擬方法%c=0;x=0;y=0;pai;fori=1:20000x=rand(1,1);%雨點(diǎn)在x方向的位置y=rand(1,1);%雨點(diǎn)在y方向的位置if(x*x+y*y<=1.0)c=(c+1);endendpai=(4*c/20000)模型求解*2022/11/23蒙特卡洛法—整數(shù)規(guī)劃%隨機(jī)模擬方法%模型求解*2022/1175實(shí)驗(yàn)準(zhǔn)備問(wèn)題

習(xí)題2.3生產(chǎn)計(jì)劃安排（P18）準(zhǔn)備工作：1、matlab軟件的熟悉2、矩陣的表示

和基本操作3、隨機(jī)數(shù)產(chǎn)生函數(shù)的用法

實(shí)驗(yàn)要求

獨(dú)立完成實(shí)驗(yàn)報(bào)告寫出完整的模型假設(shè)、模型建立、模型求解（源代碼）、模型結(jié)果、模型分析（結(jié)果說(shuō)明什么問(wèn)題？達(dá)到建模目的？適用范圍？模型是否合理？）*2022/11/23實(shí)驗(yàn)準(zhǔn)備問(wèn)題*2022/11/2276謝謝！*2022/11/23*2022/11/2277數(shù)學(xué)建模*2022/11/23*2022/11/2278第三部分整數(shù)規(guī)劃應(yīng)用實(shí)例分析整數(shù)規(guī)劃問(wèn)題的幾種求解方法分枝界定法隱枚舉法匈牙利法

蒙特卡洛法實(shí)驗(yàn)準(zhǔn)備*2022/11/23第三部分整數(shù)規(guī)劃*2022/11/2279例1整數(shù)規(guī)劃問(wèn)題某廠擬購(gòu)進(jìn)甲、乙兩類機(jī)床生產(chǎn)新產(chǎn)品。已知甲、乙機(jī)床進(jìn)價(jià)分別為2萬(wàn)元和3萬(wàn)元；安裝占地面積分別為4m2和2m2；投后的收益分別為300元/日和200元/日。廠方目前僅有資金14萬(wàn)元，安裝面積18m2。為使收益最大，廠方應(yīng)購(gòu)進(jìn)甲、乙機(jī)床各多少臺(tái)？實(shí)例一整數(shù)規(guī)劃問(wèn)題甲型乙型現(xiàn)有量進(jìn)價(jià)（萬(wàn)元）2315占地面積（m2）4218利潤(rùn)（百元）32*例1整數(shù)規(guī)劃問(wèn)題某廠擬購(gòu)進(jìn)甲、乙兩類機(jī)床生產(chǎn)新產(chǎn)品。已80設(shè)設(shè)應(yīng)購(gòu)進(jìn)甲、乙機(jī)床臺(tái)數(shù)分別為x1和x2，工廠的收益為z。整數(shù)規(guī)劃(IP)1.模型建立s.t.實(shí)例一整數(shù)規(guī)劃問(wèn)題*設(shè)設(shè)應(yīng)購(gòu)進(jìn)甲、乙機(jī)床臺(tái)數(shù)分別為x1和x2，工廠的收益為z。整81formatshortc=[-3;-2];a=[2,3;4,2];b=[14;18];lb=[0;0];[x,Fval]=linprog(c,a,b,[],[],lb)先不考慮解的整數(shù)限制，問(wèn)題B的最優(yōu)解：x1=3.25，x2=2.5，

最優(yōu)值：z=14.75。2.模型求解設(shè)整數(shù)規(guī)劃問(wèn)題為A，與它相應(yīng)的線性規(guī)劃為問(wèn)題B，先來(lái)求解問(wèn)題B。1）舍去小數(shù)：取x1=3，x2=2，算出目標(biāo)函數(shù)值z(mì)=13。2）試探：如取x1=4，x2=1時(shí)，z=14，如取x1=3，x2=3時(shí)，不滿足約束條件，通過(guò)比較得到模型的最優(yōu)整數(shù)解。解法一：實(shí)例一整數(shù)規(guī)劃問(wèn)題*formatshort先不考慮解的整數(shù)限制，問(wèn)題B的2.821）不考慮解的整數(shù)限制，問(wèn)題B的最優(yōu)解：x1=3.25，x2=2.5，

最優(yōu)值：z=14.752.模型求解

解法二：設(shè)整數(shù)規(guī)劃問(wèn)題為A，與它相應(yīng)的線性規(guī)劃為問(wèn)題B實(shí)例一整數(shù)規(guī)劃問(wèn)題*1）不考慮解的整數(shù)限制，問(wèn)題B的最優(yōu)解：x1=3.25，x283

2.模型求解因?yàn)?與3之間無(wú)整數(shù)，故這兩個(gè)子集的整數(shù)解必與原可行集合整數(shù)解一致，這一步驟稱為分枝。對(duì)問(wèn)題A分枝構(gòu)成兩個(gè)子問(wèn)題稱為B1和B2。問(wèn)題B1數(shù)學(xué)模型：s.t.問(wèn)題B2數(shù)學(xué)模型：s.t.實(shí)例一整數(shù)規(guī)劃問(wèn)題*

2.模型求解因?yàn)?與3之間無(wú)整數(shù)，故這兩個(gè)子集的整數(shù)解842.模型求解B2最優(yōu)解：

x1=4，x2=1，z2=14

B1最優(yōu)解：

x1=3，x2=8/3，z1=43/3圖解法（單純形法）求得的最優(yōu)解分別為：實(shí)例一整數(shù)規(guī)劃問(wèn)題*2.模型求解B2最優(yōu)解：x1=4，x2=1，z2=14

B854）對(duì)問(wèn)題B1在進(jìn)行分枝，得問(wèn)題B11和B122.模型求解

問(wèn)題B11數(shù)學(xué)模型：s.t.問(wèn)題B12數(shù)學(xué)模型：s.t.實(shí)例一整數(shù)規(guī)劃問(wèn)題*4）對(duì)問(wèn)題B1在進(jìn)行分枝，得問(wèn)題B11和B122.模型求解

86求解問(wèn)題B11和B12

得到：2.模型求解

5）此時(shí)由于所有子問(wèn)題的目標(biāo)值均小于或等于z2，故問(wèn)題A的目標(biāo)函數(shù)最優(yōu)值z(mì)*=z2=14，最優(yōu)解為x1=4，x2=1。B11最優(yōu)解：

x1=3，x2=2，z11=13B12最優(yōu)解：

x1=2.5，x2=3，z12=13.5實(shí)例一整數(shù)規(guī)劃問(wèn)題*求解問(wèn)題B11和B12得到：2.模型求解

5）此時(shí)由于所87整數(shù)規(guī)劃整數(shù)規(guī)劃（IntegerProgramming）數(shù)學(xué)規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。整數(shù)規(guī)劃分類：（1）變量全限制為整數(shù)時(shí)，稱純（完全）整數(shù)規(guī)劃。（2）

變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。*2022/11/23整數(shù)規(guī)劃整數(shù)規(guī)劃（IntegerProgramming）*88整數(shù)規(guī)劃整數(shù)規(guī)劃特點(diǎn)（i）原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況：①原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。②整數(shù)規(guī)劃無(wú)可行解。③有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值變差。（ii）整數(shù)規(guī)劃最優(yōu)解不能按照實(shí)數(shù)最優(yōu)解簡(jiǎn)單取整而獲得。*2022/11/23整數(shù)規(guī)劃整數(shù)規(guī)劃特點(diǎn)*2022/11/2289整數(shù)規(guī)劃整數(shù)規(guī)劃求解方法分類（1）分枝定界法—可求純或混合整數(shù)線性規(guī)劃。（2）割平面法—可求純或混合整數(shù)線性規(guī)劃。（3）隱枚舉法—求解“0-1”整數(shù)規(guī)劃：①過(guò)濾隱枚舉法；②分枝隱枚舉法。（4）匈牙利法—解決指派問(wèn)題（特殊“0-1”規(guī)劃）。（5）蒙特卡洛法—求解各種類型規(guī)劃。*2022/11/23整數(shù)規(guī)劃整數(shù)規(guī)劃求解方法分類*2022/11/2290分枝定界法（1）分枝：通常，把全部可行解空間反復(fù)地分割為越來(lái)越小的子集，稱為分枝；（2）定界：并且對(duì)每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界（對(duì)于最小值問(wèn)題），這稱為定界。（3）剪枝：在每次分枝后，凡是界限超出已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝，這樣，許多子集可不予考慮，這稱剪枝。求解生產(chǎn)進(jìn)度問(wèn)題、旅行推銷員問(wèn)題、工廠選址問(wèn)題、背包問(wèn)題及分配問(wèn)題。分枝定界法*2022/11/23分枝定界法分枝定界法*2022/11/2291分枝定界法步驟（1）求解整數(shù)規(guī)劃問(wèn)題A對(duì)應(yīng)的線性規(guī)劃問(wèn)題B（松弛問(wèn)題）；（2）分枝，在松弛問(wèn)題B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量xj，其值為bj，以[bj]表示小于bj的最大整數(shù)，構(gòu)造兩個(gè)約束條件

將這兩個(gè)約束條件，分別加入問(wèn)題B，求兩個(gè)后繼規(guī)劃問(wèn)題B1和B2。分枝定界法*2022/11/23分枝定界法步驟分枝定界法*2022/11/2292

分枝定界法*2022/11/23

分枝定界法*2022/11/2293···············1234567·松弛問(wèn)題的可行域增加x1≤3增加x1≥4L1L2分枝定界法例2*·····94x1≤3x1≥4父問(wèn)題子問(wèn)題結(jié)論1：（IP）的最優(yōu)解一定在某個(gè)子問(wèn)題中父問(wèn)題的最優(yōu)值≤3：子問(wèn)題中的整數(shù)解都是（IP）的可行解子問(wèn)題的最優(yōu)解2：子問(wèn)題的可行域父問(wèn)題的可行域∩*x1≤3x1≥4父問(wèn)題子問(wèn)題結(jié)論1：（IP）的最優(yōu)解95x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3···············1234567·4x1+x2=16.52x1+3x2=14.5z=30x1+20x2*x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3·96某公司擬在市東、西、南三區(qū)建立門市部，擬議中有7個(gè)位置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元，每年可獲利潤(rùn)估計(jì)為ci元，但投資總額不能超過(guò)B元。問(wèn)應(yīng)選擇哪些點(diǎn)可使年利潤(rùn)最大？0-1變量例3投資場(chǎng)所的選定—0-1變量*0-1變量例3投資場(chǎng)所的選定—0-1變量*97s.t.1.模型建立目標(biāo)函數(shù)：約束條件：在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。0-1變量*s.t.1.模型建立目標(biāo)函數(shù)：約束條件：在東區(qū)，由A1，A980-1型整數(shù)規(guī)劃0-1型整數(shù)規(guī)劃決策變量只能取0或1的整數(shù)規(guī)劃，叫做0-1整數(shù)規(guī)劃。決策變量稱為0-1變量(二進(jìn)制變量、邏輯變量)。0-1變量作為邏輯變量，常被用來(lái)表示系統(tǒng)是否處于某個(gè)特定狀態(tài)，或者決策時(shí)是否取某個(gè)特定方案。在實(shí)際問(wèn)題中引入0-1變量，可以把各種情況需要分別討論的數(shù)學(xué)規(guī)劃問(wèn)題統(tǒng)一在一個(gè)問(wèn)題中討論了。*2022/11/230-1型整數(shù)規(guī)劃0-1型整數(shù)規(guī)劃*2022/11/2299

某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表格所示。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最大?貨物甲乙托運(yùn)限制體積每箱（米3）5424重量每箱（百公斤）2513利潤(rùn)每箱（百元）20100-1型整數(shù)規(guī)劃例4—互相排斥的計(jì)劃*某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲1000-1型整數(shù)規(guī)劃

1.模型建立+(1-y)M+yM假設(shè)現(xiàn)在有車運(yùn)和船運(yùn)兩種運(yùn)輸方式，但只能選擇一種運(yùn)輸方式，如用車運(yùn)時(shí)關(guān)于體積的限制條件為5x1+4x2≤24(車)。如用船運(yùn)時(shí)關(guān)于體積的限制條件為7x1+3x2≤45(船)。（這兩條件互相排斥）。設(shè)甲、乙兩種貨物的托運(yùn)箱數(shù)分別為x1，x2，可獲得的利潤(rùn)為z。設(shè)變量y表示運(yùn)貨的方式，當(dāng)y為1時(shí)，用車運(yùn)，y為0時(shí)，用船運(yùn)。M是充分大的數(shù)*2022/11/230-1型整數(shù)規(guī)劃1.模型建立+(1-y)M+yM1010-1型整數(shù)規(guī)劃

模型分析有多個(gè)相互排斥的約束條件*2022/11/230-1型整數(shù)規(guī)劃模型分析有多個(gè)相互排斥的約束條件*2022102相互排斥的約束條件如果有m個(gè)互相排斥的約束條件（<=型）：為了保證這個(gè)約束條件只有一個(gè)起作用，我們引入m個(gè)0-1變量和一個(gè)充分大的常數(shù)M，下面這一組m+1個(gè)約束條件符合上述要求。0-1型整數(shù)規(guī)劃*相互排斥的約束條件如果有m個(gè)互相排斥的約束條件（<=型）：103有三種自然資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費(fèi)用及售價(jià)、資源單位消耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用如下表。要求制訂一個(gè)生產(chǎn)計(jì)劃，使總收益最大。－12108單位售價(jià)－200150100固定費(fèi)用－654

單位可變費(fèi)用100321C300432B500842A資源量IIIIII

單耗量資源產(chǎn)品例5—固定費(fèi)用問(wèn)題0-1型整數(shù)規(guī)劃*有三種自然資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變104解：設(shè)xj是第j種產(chǎn)品的產(chǎn)量，j=1，2，3；再設(shè)若生產(chǎn)第j種產(chǎn)品（即xj>0）若不生產(chǎn)第j種產(chǎn)品（即xj=0）j=1，2，3則問(wèn)題的模型為s.t.

如果生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj＞0，由xj≤Mjyj知，yj＝1。因此，相應(yīng)的固定費(fèi)用在目標(biāo)函數(shù)中將被考慮。

同理，如果不生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj=0，只有yj為0才有意義，因此，相應(yīng)的固定費(fèi)用不應(yīng)在目標(biāo)函數(shù)中被考慮。0-1型整數(shù)規(guī)劃*2022/11/23解：設(shè)xj是第j種產(chǎn)品的產(chǎn)量，j=1，2，3；再設(shè)若生產(chǎn)第j1050-1型整數(shù)規(guī)劃解法只檢查變量取值的組合的一部分的方法。

：求解下列問(wèn)題隱枚舉法(a)(b)(c)(d)例6*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法(a)例6*2022/11/21060-1型整數(shù)規(guī)劃解法解法一：隱枚舉法(x1,x2,x3)z值abcd過(guò)濾條件(0,0,0)0√√√√Z≥0(0,0,1)5√√√√Z≥5(0,1,0)-2(0,1,1)3(1,0,0)3Z≥8(1,0,1)√√√√(1,1,0)81(1,1,1)6所以，最優(yōu)解(x1，x2，x3)T=(1，0，1)T，maxz=8。*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法(x1,x2,x3)z值abc1070-1型整數(shù)規(guī)劃解法為了使最優(yōu)解盡可能早出現(xiàn)，可先將目標(biāo)函數(shù)中各變量的順序按其系數(shù)大小重新排列，這樣可進(jìn)一步減少計(jì)算量。隱枚舉法按目標(biāo)函數(shù)中各變量系數(shù)的大小重新排列各變量最大化問(wèn)題：由小到大最小化問(wèn)題：由大到小*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法按目標(biāo)函數(shù)中各變量系數(shù)的大小重108解法二（優(yōu)化）：重新排列xj的順序(系數(shù)遞減)0-1型整數(shù)規(guī)劃解法*解法二（優(yōu)化）：重新排列xj的順序(系數(shù)遞減)0-1型整數(shù)1090-1型整數(shù)規(guī)劃計(jì)算表目標(biāo)函數(shù)z＝3x1－2x2＋5x3＝5x3＋3x1－2x2

最大值的上限是8，第二大的值是5…5x3＋3x1－2x2≥8⑤點(diǎn)(x3,x1,x2)約束條件滿足條件?是∨否×z值⑤①②③④(1,1,0)8∨∨∨∨∨8隱枚舉法：共計(jì)算5次(均滿足約束條件)。（最優(yōu)解為1，0，1，最優(yōu)值8）可根據(jù)計(jì)算逐漸改變過(guò)濾條件(該例因最大值的點(diǎn)滿足其他四個(gè)約束，即找到最大化問(wèn)題的最好的整數(shù)解。就不需驗(yàn)證計(jì)算第二大值的點(diǎn)是否滿足約束條件)0-1型整數(shù)規(guī)劃解法過(guò)濾隱枚舉法*0-1型整數(shù)規(guī)劃計(jì)算表目標(biāo)函數(shù)z＝3x1－2x2＋5x3＝110步驟1：將問(wèn)題轉(zhuǎn)化為如下標(biāo)準(zhǔn)形式：其中cj≥0，且c1≤c2≤…≤cn。例7求解0-1整數(shù)規(guī)劃（選學(xué)-分枝隱枚舉法）0-1型整數(shù)規(guī)劃解法*步驟1：將問(wèn)題轉(zhuǎn)化為如下標(biāo)準(zhǔn)形式：其中cj≥0，且c1≤c111⑵如約束條件為≤，兩邊同乘(-1)；如約束條件為等式，可令變量，代入目標(biāo)函數(shù)和其它約束條件中，將xn消掉。⑶按目標(biāo)函數(shù)中系數(shù)由小到大的順序重新排列變量，并將約束條件中的排列順序做相應(yīng)改變。

⑴如目標(biāo)函數(shù)為maxz，令，可化為。如某個(gè)變量的系數(shù)為負(fù)，令，使系數(shù)變正。0-1型整數(shù)規(guī)劃解法步驟1：將問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式：*⑵如約束條件為≤，兩邊同乘(-1)；如約束條件為等式，112調(diào)整后的0-1規(guī)劃問(wèn)題變?yōu)椋?a)(b)

步驟2：令所有變量取0，求出目標(biāo)函數(shù)值，并代入約束條件中檢查是否可行，如果可行即為問(wèn)題的最優(yōu)解；否則轉(zhuǎn)下一步。

令，得＝-10，但不滿足兩個(gè)約束條件。0-1型整數(shù)規(guī)劃解法*調(diào)整后的0-1規(guī)劃問(wèn)題變?yōu)椋?a)(b)步驟2：令所113

步驟3：分支和定界。依次令各變量分別取0或1，將問(wèn)題劃分為兩個(gè)子問(wèn)題，分別檢查解是否可行，如不可行繼續(xù)對(duì)邊界值較小的子問(wèn)題分支，直到找出一個(gè)可行解為止，這時(shí)得到值的一個(gè)上界。分支過(guò)程見下圖所示：0-1型整數(shù)規(guī)劃解法*步驟3：分支和定界。依次令各變量分別取0或1，將問(wèn)題劃114步驟4：考察所有子問(wèn)題，有以下四種情況：

⑴若某個(gè)子問(wèn)題的邊界值對(duì)應(yīng)原問(wèn)題的可行解，則將它的邊界值與保留的值作比較，并取較優(yōu)的一個(gè)作為新的值。如所有子問(wèn)題都已考察完畢，則保留下來(lái)的值及其對(duì)應(yīng)的解即為0-1整數(shù)規(guī)劃問(wèn)題的最優(yōu)解。⑵若某個(gè)子問(wèn)題的邊界值大于保留下來(lái)的值，不管其是否可行，則將這一分支剪掉。⑶若某個(gè)子問(wèn)題不可行（在該分支中的上級(jí)變量的值已經(jīng)確定的情況下，其余變量不管取什么值都無(wú)法滿足所有約束時(shí)，該枝的分枝已無(wú)可行解），則將這一分支剪掉。⑷若某個(gè)子問(wèn)題可行且邊界值優(yōu)于值，但該邊界值對(duì)應(yīng)的解不是可行解，則該問(wèn)題待考察。如有多個(gè)問(wèn)題待考察，優(yōu)先對(duì)其中最優(yōu)值最大的一個(gè)子問(wèn)題進(jìn)行考察，轉(zhuǎn)步驟3。0-1型整數(shù)規(guī)劃解法*步驟4：考察所有子問(wèn)題，有以下四種情況：⑴若某個(gè)子115

分支③邊界值=-6＜-4，但相應(yīng)的解不可行，需繼續(xù)分支。過(guò)程如上圖所示。0-1型整數(shù)規(guī)劃解法*分支③邊界值=-6＜-4，但相應(yīng)的解不可行，需繼續(xù)116上述求解過(guò)程也可用表格表示：(0，1，0，1，0)(0，1，1，0，0)(0，0，1，0，0)(1，0，1，0，0)(1，1，0，0，0)(0，1，0，0，0)(1，0，0，0，0)(0，0，0，0，0)

＞-4，剪枝1⑨

＞-4，剪枝-1⑧不可行，剪枝×-5⑦

＞-4，剪枝-3⑤可行≤-4√√-4④×-6③×√-8②×-10①ba備注約束條件z值序號(hào)0-1型整數(shù)規(guī)劃解法*上述求解過(guò)程也可用表格表示：(0，1，0，1，0)(0，1117所以，最優(yōu)解：即原問(wèn)題的最優(yōu)解為：分枝隱枚舉法0-1型整數(shù)規(guī)劃解法*所以，最優(yōu)解：即原問(wèn)題的最優(yōu)解為：分枝隱枚舉法0-1型118指派問(wèn)題（0-1型）一、指派問(wèn)題擬派n人去做n項(xiàng)工作，由于每人的專長(zhǎng)不同，各人完成不同任務(wù)效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高的問(wèn)題，這類問(wèn)題稱為指派問(wèn)題(分派問(wèn)題、分配問(wèn)題)B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人任務(wù)cij表示第i個(gè)人完成第j項(xiàng)任務(wù)的效率。*指派問(wèn)題（0-1型）一、指派問(wèn)題B1B2BnA1c11c12119二、指派問(wèn)題的數(shù)學(xué)模型=(Cij)指派問(wèn)題系數(shù)矩陣B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnn人任務(wù)解：設(shè)指派問(wèn)題（0-1型）*二、指派問(wèn)題的數(shù)學(xué)模型=(Cij)B1B2BnA1c11c1120某單位現(xiàn)在Ａ、Ｂ、Ｃ、Ｄ四項(xiàng)工作需完成，現(xiàn)在甲、乙、丙、丁四個(gè)人均可完成這四項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)所用的時(shí)間如右表所示，問(wèn)應(yīng)指派何人去完成何項(xiàng)任務(wù)，使所需時(shí)間最少？甲215134乙1041415丙9141613丁78119ABCD任務(wù)人員滿足所有約束條件的可行解xij也可寫成表格或矩陣形式，稱為解矩陣(xij)=本例的一個(gè)可行解矩陣(cij)=例8指派問(wèn)題指派問(wèn)題（0-1型）*某單位現(xiàn)在Ａ、Ｂ、Ｃ、Ｄ四項(xiàng)工作需完成，現(xiàn)在甲、乙、丙、丁四121指派問(wèn)題數(shù)學(xué)模型的性質(zhì)：若從指派問(wèn)題的系數(shù)的系數(shù)矩陣（cij）的一行（列）各元素中分別減去該行（列）的最小元素，得到新矩陣（bij），那么以（bij）為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。獨(dú)立的0元素：位于不同行不同列的0元素稱為獨(dú)立的0元素。結(jié)論：若能在系數(shù)矩陣(bij)中找出n個(gè)獨(dú)立的0元素；則令解矩陣(xij)中對(duì)應(yīng)這n個(gè)獨(dú)立的0元素取值為1，其它元素取值為0。將其代入目標(biāo)函數(shù)中得到zk=0，它一定是最小。這就是以(bij)為系數(shù)矩陣的指派問(wèn)題的最優(yōu)解，也就得到了問(wèn)題的最優(yōu)解。指派問(wèn)題（0-1型）*指派問(wèn)題數(shù)學(xué)模型的性質(zhì)：若從指派問(wèn)題的系數(shù)的系122三、指派問(wèn)題的解法（匈牙利法）第一步:使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行各列都出現(xiàn)０元素。（１）從系數(shù)矩陣的每行元素減去該行的最小元素；（２）再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的最小元素。2497min24min指派問(wèn)題（0-1型）*三、指派問(wèn)題的解法（匈牙利法）第一步:使指派問(wèn)題的系數(shù)矩陣經(jīng)123經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；只需找出n個(gè)獨(dú)立的0元素，若能找出，就以這些獨(dú)立的0元素對(duì)應(yīng)解矩陣中的元素為1，其它作為0，這就得到最優(yōu)解。找獨(dú)立0元素的步驟如下：第二步：進(jìn)行試指派，以尋求最優(yōu)解。0（1）從只有一個(gè)0元素的行開始，給這個(gè)0元素加圈，記作◎.然后再劃去◎所在列的其它0元素，記作。（2）給只有一個(gè)0元素的列的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作。0指派問(wèn)題（0-1型）*經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；只需找124（3）反復(fù)(1),(2)兩步，直到所有0元素都被圈出和劃掉為止。（4）若各行各列均有多于2個(gè)的0元素未被圈出或劃掉，任選其中任意一個(gè)0元素加圈。（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么指派問(wèn)題的最優(yōu)解已得到，若m<n，則轉(zhuǎn)入下一步。第二步：進(jìn)行試指派，以尋求最優(yōu)解。指派問(wèn)題（0-1型）*（3）反復(fù)(1),(2)兩步，直到所有0元素都被圈出和劃掉為125min76746指派問(wèn)題（0-1型）*min76746指派問(wèn)題（0-1型）*126第三步：作最少的直線覆蓋所有0元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立0元素?cái)?shù)。（5）對(duì)沒(méi)有打√號(hào)的行畫一橫線，有打√號(hào)的列畫一縱線，這就得到覆蓋所有0元素的最少直線。（1）對(duì)沒(méi)有◎的行打√號(hào)；（2）對(duì)已打√號(hào)的行中所有含劃0元素的列打√號(hào)；（3）再對(duì)打有√號(hào)的列中含◎元素的行打√號(hào)；（4）重復(fù)(2)、(3)直到得不出新的打√號(hào)的行、列為止；√√√指派問(wèn)題（0-1型）*第三步：作最少的直線覆蓋所有0元素，以確定該系數(shù)矩陣中能找到127第四步：對(duì)第三步所得矩陣進(jìn)行變換，目的是增加0元素。在沒(méi)有被直線覆蓋的部分中找出最小元素。然后在打√行各元素中都減去該最小元素，而在打√列的各元素都加上該最小元素（以保證原來(lái)的0元素不變）。這樣得到新系數(shù)矩陣。重復(fù)第二步。指派問(wèn)題（0-1型）√√√*第四步：對(duì)第三步所得矩陣進(jìn)行變換，目的是增加0元素。在沒(méi)128第五步：系數(shù)矩陣(bij)中找出n個(gè)獨(dú)立的0元素；則令解矩陣(xij)中對(duì)應(yīng)這n個(gè)獨(dú)立的0元素取值為1，其它元素取值為0?！擢?dú)立0元素的個(gè)數(shù)等于系數(shù)矩陣的階數(shù)∴得到了最優(yōu)解最優(yōu)解矩陣為：指派問(wèn)題（0-1型）*第五步：系數(shù)矩陣(bij)中找出n個(gè)獨(dú)立的0元素；則令解矩陣129練習(xí)：有4個(gè)工人，要指派他們分別完成4項(xiàng)工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表：ABCD甲乙丙丁15192619182317212122162324181917工作工人指派問(wèn)題（0-1型）*練習(xí)：有4個(gè)工人，要指派他們分別完成4項(xiàng)工作，每人做各項(xiàng)工作130解：用匈牙利法求解過(guò)程如下：min15181617√√√min1√√√√√指派問(wèn)題（0-1型）*解：用匈牙利法求解過(guò)程如下：min15181617√√√mi131四、非標(biāo)準(zhǔn)形式的指派問(wèn)題（選學(xué)）1、最大化指派問(wèn)題2、人數(shù)和事數(shù)不等的指派問(wèn)題3、一個(gè)人可做幾件事的指派問(wèn)題4、某事一定不能由某人做的指派問(wèn)題指派問(wèn)題（0-1型）*四、非標(biāo)準(zhǔn)形式的指派問(wèn)題（選學(xué)）1、最大化指派問(wèn)題指派問(wèn)題（1321、求最大化的指派問(wèn)題令bij=M-cij其中：M是足夠大的常數(shù)（cij中最大元素）用匈牙利法求解（bij）即可。所得最小解就是原問(wèn)題的最大解。指派問(wèn)題（0-1型）*1、求最大化的指派問(wèn)題令bij=M-cij指派問(wèn)題（0-1型1332、人數(shù)和任務(wù)數(shù)不等的指派問(wèn)題若人少任務(wù)多，則添上一些虛擬的“人”。這些虛擬的“人”完成各任務(wù)的費(fèi)用系數(shù)可取0，理解為這些費(fèi)用實(shí)際上不會(huì)發(fā)生。若人多任務(wù)少，則添上一些虛擬的“任務(wù)”，這些虛擬的“任務(wù)”由各人完成的費(fèi)用系數(shù)同樣也取0。指派問(wèn)題（0-1型）*2、人數(shù)和任務(wù)數(shù)不等的指派問(wèn)題若人少任務(wù)多，則添上一些虛擬的1343、一個(gè)人可做幾件事的指派問(wèn)題若某個(gè)人可完成幾項(xiàng)任務(wù)，則可將人化作相同的幾個(gè)“人”，來(lái)接受指派，這幾個(gè)“人”完成同一項(xiàng)任務(wù)的費(fèi)用系數(shù)都一樣。4