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

數(shù)學(xué)建模整數(shù)規(guī)劃2023/4/10第1頁，共78頁，2023年，2月20日，星期五數(shù)學(xué)建模2023/4/10第2頁，共78頁，2023年，2月20日，星期五第三部分整數(shù)規(guī)劃應(yīng)用實(shí)例分析整數(shù)規(guī)劃問題的幾種求解方法分枝界定法隱枚舉法匈牙利法

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

最優(yōu)值：z=14.75。2.模型求解設(shè)整數(shù)規(guī)劃問題為A，與它相應(yīng)的線性規(guī)劃為問題B，先來求解問題B。1）舍去小數(shù)：取x1=3，x2=2，算出目標(biāo)函數(shù)值z=13。2）試探：如取x1=4，x2=1時(shí)，z=14，如取x1=3，x2=3時(shí)，不滿足約束條件，通過比較得到模型的最優(yōu)整數(shù)解。解法一：實(shí)例一整數(shù)規(guī)劃問題第6頁，共78頁，2023年，2月20日，星期五1）不考慮解的整數(shù)限制，問題B的最優(yōu)解：x1=3.25，x2=2.5，

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

解法二：設(shè)整數(shù)規(guī)劃問題為A，與它相應(yīng)的線性規(guī)劃為問題B實(shí)例一整數(shù)規(guī)劃問題第7頁，共78頁，2023年，2月20日，星期五

2.模型求解因?yàn)?與3之間無整數(shù)，故這兩個(gè)子集的整數(shù)解必與原可行集合整數(shù)解一致，這一步驟稱為分枝。對問題A分枝構(gòu)成兩個(gè)子問題稱為B1和B2。問題B1數(shù)學(xué)模型：s.t.問題B2數(shù)學(xué)模型：s.t.實(shí)例一整數(shù)規(guī)劃問題第8頁，共78頁，2023年，2月20日，星期五2.模型求解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ī)劃問題第9頁，共78頁，2023年，2月20日，星期五4）對問題B1在進(jìn)行分枝，得問題B11和B122.模型求解

問題B11數(shù)學(xué)模型：s.t.問題B12數(shù)學(xué)模型：s.t.實(shí)例一整數(shù)規(guī)劃問題第10頁，共78頁，2023年，2月20日，星期五求解問題B11和B12

得到：2.模型求解

5）此時(shí)由于所有子問題的目標(biāo)值均小于或等于z2，故問題A的目標(biāo)函數(shù)最優(yōu)值z*=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ī)劃問題第11頁，共78頁，2023年，2月20日，星期五整數(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ī)劃。2023/4/10第12頁，共78頁，2023年，2月20日，星期五整數(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ī)劃無可行解。③有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值變差。（ii）整數(shù)規(guī)劃最優(yōu)解不能按照實(shí)數(shù)最優(yōu)解簡單取整而獲得。2023/4/10第13頁，共78頁，2023年，2月20日，星期五整數(shù)規(guī)劃整數(shù)規(guī)劃求解方法分類（1）分枝定界法—可求純或混合整數(shù)線性規(guī)劃。（2）割平面法—可求純或混合整數(shù)線性規(guī)劃。（3）隱枚舉法—求解“0-1”整數(shù)規(guī)劃：①過濾隱枚舉法；②分枝隱枚舉法。（4）匈牙利法—解決指派問題（特殊“0-1”規(guī)劃）。（5）蒙特卡洛法—求解各種類型規(guī)劃。2023/4/10第14頁，共78頁，2023年，2月20日，星期五分枝定界法（1）分枝：通常，把全部可行解空間反復(fù)地分割為越來越小的子集，稱為分枝；（2）定界：并且對每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界（對于最小值問題），這稱為定界。（3）剪枝：在每次分枝后，凡是界限超出已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝，這樣，許多子集可不予考慮，這稱剪枝。求解生產(chǎn)進(jìn)度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題。分枝定界法2023/4/10第15頁，共78頁，2023年，2月20日，星期五分枝定界法步驟（1）求解整數(shù)規(guī)劃問題A對應(yīng)的線性規(guī)劃問題B（松弛問題）；（2）分枝，在松弛問題B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量xj，其值為bj，以[bj]表示小于bj的最大整數(shù)，構(gòu)造兩個(gè)約束條件

將這兩個(gè)約束條件，分別加入問題B，求兩個(gè)后繼規(guī)劃問題B1和B2。分枝定界法2023/4/10第16頁，共78頁，2023年，2月20日，星期五

分枝定界法2023/4/10第17頁，共78頁，2023年，2月20日，星期五···············1234567·松弛問題的可行域增加x1≤3增加x1≥4L1L2分枝定界法例2第18頁，共78頁，2023年，2月20日，星期五x1≤3x1≥4父問題子問題結(jié)論1：（IP）的最優(yōu)解一定在某個(gè)子問題中父問題的最優(yōu)值≤3：子問題中的整數(shù)解都是（IP）的可行解子問題的最優(yōu)解2：子問題的可行域父問題的可行域∩第19頁，共78頁，2023年，2月20日，星期五x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3···············1234567·4x1+x2=16.52x1+3x2=14.5z=30x1+20x2第20頁，共78頁，2023年，2月20日，星期五某公司擬在市東、西、南三區(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元，每年可獲利潤估計(jì)為ci元，但投資總額不能超過B元。問應(yīng)選擇哪些點(diǎn)可使年利潤最大？0-1變量例3投資場所的選定—0-1變量第21頁，共78頁，2023年，2月20日，星期五s.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變量第22頁，共78頁，2023年，2月20日，星期五0-1型整數(shù)規(guī)劃0-1型整數(shù)規(guī)劃決策變量只能取0或1的整數(shù)規(guī)劃，叫做0-1整數(shù)規(guī)劃。決策變量稱為0-1變量(二進(jìn)制變量、邏輯變量)。0-1變量作為邏輯變量，常被用來表示系統(tǒng)是否處于某個(gè)特定狀態(tài)，或者決策時(shí)是否取某個(gè)特定方案。在實(shí)際問題中引入0-1變量，可以把各種情況需要分別討論的數(shù)學(xué)規(guī)劃問題統(tǒng)一在一個(gè)問題中討論了。2023/4/10第23頁，共78頁，2023年，2月20日，星期五

某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運(yùn)所受限制如表格所示。問兩種貨物各托運(yùn)多少箱，可使獲得利潤為最大?貨物甲乙托運(yùn)限制體積每箱（米3）5424重量每箱（百公斤）2513利潤每箱（百元）20100-1型整數(shù)規(guī)劃例4—互相排斥的計(jì)劃第24頁，共78頁，2023年，2月20日，星期五0-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，可獲得的利潤為z。設(shè)變量y表示運(yùn)貨的方式，當(dāng)y為1時(shí)，用車運(yùn)，y為0時(shí)，用船運(yùn)。M是充分大的數(shù)2023/4/10第25頁，共78頁，2023年，2月20日，星期五0-1型整數(shù)規(guī)劃

模型分析有多個(gè)相互排斥的約束條件2023/4/10第26頁，共78頁，2023年，2月20日，星期五相互排斥的約束條件如果有m個(gè)互相排斥的約束條件（<=型）：為了保證這個(gè)約束條件只有一個(gè)起作用，我們引入m個(gè)0-1變量和一個(gè)充分大的常數(shù)M，下面這一組m+1個(gè)約束條件符合上述要求。0-1型整數(shù)規(guī)劃第27頁，共78頁，2023年，2月20日，星期五有三種自然資源被用于生產(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)用問題0-1型整數(shù)規(guī)劃第28頁，共78頁，2023年，2月20日，星期五解：設(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則問題的模型為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ī)劃2023/4/10第29頁，共78頁，2023年，2月20日，星期五0-1型整數(shù)規(guī)劃解法只檢查變量取值的組合的一部分的方法。

：求解下列問題隱枚舉法(a)(b)(c)(d)例62023/4/10第30頁，共78頁，2023年，2月20日，星期五0-1型整數(shù)規(guī)劃解法解法一：隱枚舉法(x1,x2,x3)z值abcd過濾條件(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。2023/4/10第31頁，共78頁，2023年，2月20日，星期五0-1型整數(shù)規(guī)劃解法為了使最優(yōu)解盡可能早出現(xiàn)，可先將目標(biāo)函數(shù)中各變量的順序按其系數(shù)大小重新排列，這樣可進(jìn)一步減少計(jì)算量。隱枚舉法按目標(biāo)函數(shù)中各變量系數(shù)的大小重新排列各變量最大化問題：由小到大最小化問題：由大到小2023/4/10第32頁，共78頁，2023年，2月20日，星期五解法二（優(yōu)化）：重新排列xj的順序(系數(shù)遞減)0-1型整數(shù)規(guī)劃解法第33頁，共78頁，2023年，2月20日，星期五0-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ì)算逐漸改變過濾條件(該例因最大值的點(diǎn)滿足其他四個(gè)約束，即找到最大化問題的最好的整數(shù)解。就不需驗(yàn)證計(jì)算第二大值的點(diǎn)是否滿足約束條件)0-1型整數(shù)規(guī)劃解法過濾隱枚舉法第34頁，共78頁，2023年，2月20日，星期五步驟1：將問題轉(zhuǎn)化為如下標(biāo)準(zhǔn)形式：其中cj≥0，且c1≤c2≤…≤cn。例7求解0-1整數(shù)規(guī)劃（選學(xué)-分枝隱枚舉法）0-1型整數(shù)規(guī)劃解法第35頁，共78頁，2023年，2月20日，星期五⑵如約束條件為≤，兩邊同乘(-1)；如約束條件為等式，可令變量，代入目標(biāo)函數(shù)和其它約束條件中，將xn消掉。⑶按目標(biāo)函數(shù)中系數(shù)由小到大的順序重新排列變量，并將約束條件中的排列順序做相應(yīng)改變。

⑴如目標(biāo)函數(shù)為maxz，令，可化為。如某個(gè)變量的系數(shù)為負(fù)，令，使系數(shù)變正。0-1型整數(shù)規(guī)劃解法步驟1：將問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式：第36頁，共78頁，2023年，2月20日，星期五調(diào)整后的0-1規(guī)劃問題變?yōu)椋?a)(b)

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

令，得＝-10，但不滿足兩個(gè)約束條件。0-1型整數(shù)規(guī)劃解法第37頁，共78頁，2023年，2月20日，星期五

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

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

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

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

解題步驟：

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

2.