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

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

蒙特卡洛法實驗準備*2022/11/23第三部分整數(shù)規(guī)劃*2022/11/222例1整數(shù)規(guī)劃問題某廠擬購進甲、乙兩類機床生產(chǎn)新產(chǎn)品。已知甲、乙機床進價分別為2萬元和3萬元；安裝占地面積分別為4m2和2m2；投后的收益分別為300元/日和200元/日。廠方目前僅有資金14萬元，安裝面積18m2。為使收益最大，廠方應(yīng)購進甲、乙機床各多少臺？實例一整數(shù)規(guī)劃問題甲型乙型現(xiàn)有量進價（萬元）2315占地面積（m2）4218利潤（百元）32*例1整數(shù)規(guī)劃問題某廠擬購進甲、乙兩類機床生產(chǎn)新產(chǎn)品。已3設(shè)設(shè)應(yīng)購進甲、乙機床臺數(shù)分別為x1和x2，工廠的收益為z。整數(shù)規(guī)劃(IP)1.模型建立s.t.實例一整數(shù)規(guī)劃問題*設(shè)設(shè)應(yīng)購進甲、乙機床臺數(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ù)限制，問題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，算出目標函數(shù)值z=13。2）試探：如取x1=4，x2=1時，z=14，如取x1=3，x2=3時，不滿足約束條件，通過比較得到模型的最優(yōu)整數(shù)解。解法一：實例一整數(shù)規(guī)劃問題*formatshort先不考慮解的整數(shù)限制，問題B的2.51）不考慮解的整數(shù)限制，問題B的最優(yōu)解：x1=3.25，x2=2.5，

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

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

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

2.模型求解因為2與3之間無整數(shù)，故這兩個子集的整數(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ù)規(guī)劃問題*2.模型求解B2最優(yōu)解：x1=4，x2=1，z2=14

B84）對問題B1在進行分枝，得問題B11和B122.模型求解

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

9求解問題B11和B12

得到：2.模型求解

5）此時由于所有子問題的目標值均小于或等于z2，故問題A的目標函數(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ù)規(guī)劃問題*求解問題B11和B12得到：2.模型求解

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

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

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

分枝定界法*2022/11/23

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

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

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

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

單位可變費用100321C300432B500842A資源量IIIIII

單耗量資源產(chǎn)品例5—固定費用問題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則問題的模型為s.t.

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

同理，如果不生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj=0，只有yj為0才有意義，因此，相應(yīng)的固定費用不應(yīng)在目標函數(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ī)劃解法只檢查變量取值的組合的一部分的方法。

：求解下列問題隱枚舉法(a)(b)(c)(d)例6*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法(a)例6*2022/11/2290-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。*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法(x1,x2,x3)z值abc300-1型整數(shù)規(guī)劃解法為了使最優(yōu)解盡可能早出現(xiàn)，可先將目標函數(shù)中各變量的順序按其系數(shù)大小重新排列，這樣可進一步減少計算量。隱枚舉法按目標函數(shù)中各變量系數(shù)的大小重新排列各變量最大化問題：由小到大最小化問題：由大到小*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法按目標函數(shù)中各變量系數(shù)的大小重31解法二（優(yōu)化）：重新排列xj的順序(系數(shù)遞減)0-1型整數(shù)規(guī)劃解法*解法二（優(yōu)化）：重新排列xj的順序(系數(shù)遞減)0-1型整數(shù)320-1型整數(shù)規(guī)劃計算表目標函數(shù)z＝3x1－2x2＋5x3＝5x3＋3x1－2x2

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

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

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

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

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

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

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

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

解題步驟：

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

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

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

解題步驟：

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

4.按照所建立的模型進行仿真試驗、計算，求出問題的隨機解。

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

解題步驟：*2022/11/2271蒙特卡洛法—整數(shù)規(guī)劃例：隨機變量x={0，1，2}表示每分鐘到達超市收款臺的人數(shù)，有分布列模擬十分鐘內(nè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ī)劃例：隨機變量x={0，1，2}表示每72如下圖，正方形的面積A=1；1/4圓的面積B=π/4。我們想象有一個容器在正方形中夾有一個極薄的圓弧隔板。下小雨時搬至屋外，經(jīng)一定時間后，稱1/4圓的容器內(nèi)的水重C，與作為一個整體的正方形中的水重D。C與D之比應(yīng)該等于B與A之比，即可得

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

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

蒙特卡洛法—整數(shù)規(guī)劃*讓計算機來模擬雨點落下：

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

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

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

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

實驗要求

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

蒙特卡洛法實驗準備*2022/11/23第三部分整數(shù)規(guī)劃*2022/11/2279例1整數(shù)規(guī)劃問題某廠擬購進甲、乙兩類機床生產(chǎn)新產(chǎn)品。已知甲、乙機床進價分別為2萬元和3萬元；安裝占地面積分別為4m2和2m2；投后的收益分別為300元/日和200元/日。廠方目前僅有資金14萬元，安裝面積18m2。為使收益最大，廠方應(yīng)購進甲、乙機床各多少臺？實例一整數(shù)規(guī)劃問題甲型乙型現(xiàn)有量進價（萬元）2315占地面積（m2）4218利潤（百元）32*例1整數(shù)規(guī)劃問題某廠擬購進甲、乙兩類機床生產(chǎn)新產(chǎn)品。已80設(shè)設(shè)應(yīng)購進甲、乙機床臺數(shù)分別為x1和x2，工廠的收益為z。整數(shù)規(guī)劃(IP)1.模型建立s.t.實例一整數(shù)規(guī)劃問題*設(shè)設(shè)應(yīng)購進甲、乙機床臺數(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ù)限制，問題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，算出目標函數(shù)值z=13。2）試探：如取x1=4，x2=1時，z=14，如取x1=3，x2=3時，不滿足約束條件，通過比較得到模型的最優(yōu)整數(shù)解。解法一：實例一整數(shù)規(guī)劃問題*formatshort先不考慮解的整數(shù)限制，問題B的2.821）不考慮解的整數(shù)限制，問題B的最優(yōu)解：x1=3.25，x2=2.5，

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

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

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

2.模型求解因為2與3之間無整數(shù)，故這兩個子集的整數(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ù)規(guī)劃問題*2.模型求解B2最優(yōu)解：x1=4，x2=1，z2=14

B854）對問題B1在進行分枝，得問題B11和B122.模型求解

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

86求解問題B11和B12

得到：2.模型求解

5）此時由于所有子問題的目標值均小于或等于z2，故問題A的目標函數(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ù)規(guī)劃問題*求解問題B11和B12得到：2.模型求解

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

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

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

分枝定界法*2022/11/23

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

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

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

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

單位可變費用100321C300432B500842A資源量IIIIII

單耗量資源產(chǎn)品例5—固定費用問題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則問題的模型為s.t.

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

同理，如果不生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj=0，只有yj為0才有意義，因此，相應(yīng)的固定費用不應(yīng)在目標函數(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ī)劃解法只檢查變量取值的組合的一部分的方法。

：求解下列問題隱枚舉法(a)(b)(c)(d)例6*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法(a)例6*2022/11/21060-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。*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法(x1,x2,x3)z值abc1070-1型整數(shù)規(guī)劃解法為了使最優(yōu)解盡可能早出現(xiàn)，可先將目標函數(shù)中各變量的順序按其系數(shù)大小重新排列，這樣可進一步減少計算量。隱枚舉法按目標函數(shù)中各變量系數(shù)的大小重新排列各變量最大化問題：由小到大最小化問題：由大到小*2022/11/230-1型整數(shù)規(guī)劃解法隱枚舉法按目標函數(shù)中各變量系數(shù)的大小重108解法二（優(yōu)化）：重新排列xj的順序(系數(shù)遞減)0-1型整數(shù)規(guī)劃解法*解法二（優(yōu)化）：重新排列xj的順序(系數(shù)遞減)0-1型整數(shù)1090-1型整數(shù)規(guī)劃計算表目標函數(shù)z＝3x1－2x2＋5x3＝5x3＋3x1－2x2

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

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

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

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

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

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

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