1、課程內容和目的： 了解數學規劃模型的一般理論，介紹一些典型的規劃模型，如生產計劃安排問題、資源配置問題、運輸問題、下料問題、指派問題、選址問題等。能通過分析建立一些實際問題的數學規劃模型，會用工具軟件熟練求解線性規劃，整數規劃，非線性規劃等問題。教學難點和重點： 重點掌握規劃模型的三要素，建立規劃模型的方法以及工具求解。難點是模型求解算法的理解和如何將實際問題逐步轉換成規劃問題。課程學時：10學時第四章第四章 數學規劃模型數學規劃模型數學規劃模型數學規劃模型 實際問題中實際問題中的優化模型的優化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決

2、策變量決策變量f(x)目標函數目標函數gi(x) 0約束條件約束條件多元函數多元函數條件極值條件極值 決策變量個數決策變量個數n和和約束條件個數約束條件個數m較大較大 最優解在可行域最優解在可行域的邊界上取得的邊界上取得 數數學學規規劃劃線性規劃線性規劃非線性規劃非線性規劃整數規劃整數規劃重點在模型的建立和結果的分析重點在模型的建立和結果的分析4.1 4.1 線性規劃模型線性規劃模型 線性規劃(LP)研究的實際問題多種多樣的，它在工農業生產、經濟管理、優化設計與控制等領域都有廣泛應用。如資源分配問題、生產計劃問題、物資運輸問題、合理下料問題、庫存問題、勞動力安排問題、最優設計問題等等。線性規劃

3、模型的求解方法目前仍以單純形法為主要方法，該方法于1947年由美國數學家丹齊齊格（G.B.Dantzig）提出，經過60多年的發展完善，已經形成比較成熟的算法，同時配合計算機技術的廣泛應用使得該方法得到空前的普及應用。目前，大多數數學軟件都可以求解一般線性規劃模型，這一節主要采用Matlab和Lingo軟件。 問題提出 : 加工廠用牛奶生產A1、A2兩種奶制品，1桶牛奶可以在設備甲上用12小時加工成3公斤A1，或者在設備乙上用8小時加工成4公斤A2。根據市場需求，生產的A1、A2能全部售出，且每公斤A1獲利24元，每公斤A2獲利16元。現在加工廠每天能得到50桶牛奶的供應，每天正式工人總的勞動

4、時間為480小時，并且設備甲每天至多能加工100公斤A1，設備乙的加工能力沒有限制。試為該廠制定一個生產計劃，使每天獲利最大，并進一步討論以下3個附加問題： 1）若用35元可以額外購買到1桶牛奶，是否作這項投資？若投資，每天最多購買多少桶牛奶？ 2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時幾元？ 3）由于市場需求變化，每公斤A1的獲利增加到30元，應否改變生產計劃？案例1：奶制品的生產與銷售 案例分析案例分析1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時間時間480小時小時 至多加工至多加工100公斤公斤A

5、1 制訂生產計劃，使每天獲利最大制訂生產計劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應否改變生產計劃？公斤，應否改變生產計劃？ 每天：每天：1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶桶牛奶生產牛奶生產A1 x2桶桶牛奶生產牛奶生產A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應原料供應 5021 xx勞動時間勞動時間 4808

6、1221 xx加工能力加工能力 10031x決策變量決策變量 目標函數目標函數 216472xxzMax每天獲利每天獲利約束條件約束條件非負約束非負約束 0,21xx線性線性規劃規劃模型模型(LP)時間時間480小時小時 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天5021 xx48081221 xx10031x0,21xx直線直線AB下方下方直線直線BC下方下方直線直線CD左側左側平面左上角平面左上角約約束束條條件件216472maxxxz目標目標函數函數 在在B(20,30)點得到最優解點得到最優解z=c (常數常數) 等值線等值線最大利潤為最大利潤為72*20+64*3

7、0=3360元元20桶牛奶生產桶牛奶生產A1,30桶牛奶生產桶牛奶生產A2模型求解模型求解-圖解法圖解法x1x20l1l2l3l4l5問問1：35元可買到元可買到1桶牛奶，買嗎？桶牛奶，買嗎？最大利潤為最大利潤為72*20+64*30=3360元元最大利潤為最大利潤為72*18+64*33=3408元元增加增加1桶牛奶，利潤增加桶牛奶，利潤增加48元。元。 4835買！買！1250 xx1251xx35元可買到元可買到1桶牛奶，若買，每天最多買多少桶牛奶，若買，每天最多買多少? 10桶當直線當直線AB向上平移到向上平移到x1+x2=60的位置時，可行域將不再變化。的位置時，可行域將不再變化。再

8、增加牛奶供應時，因加工時間有限（超過了藍色線），無法再增加牛奶供應時，因加工時間有限（超過了藍色線），無法得到加工。得到加工。1250 xx1260 xx問問2：可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? 12128480 xx12128481xx最大利潤為最大利潤為3360元元最大利潤為最大利潤為3362元元增加增加1小時的工作時間，利潤增加小時的工作時間，利潤增加2元元。2元元問問3： A1的獲利增加到的獲利增加到 30元元/kg，應否改變生產計劃？，應否改變生產計劃？ 不改變不改變獲利的改變，引起等值獲利的改變，引起等值線線z=c傾斜程度的改變

9、，傾斜程度的改變，只要傾斜程度介于只要傾斜程度介于AB和和BC的傾斜程度之間，則的傾斜程度之間，則生產計劃不變。生產計劃不變。12max24 316 4zxx A2獲利固定，獲利固定，A1獲利允許的變化范圍為獲利允許的變化范圍為64/3, 32。A1獲利固定，獲利固定，A2獲利允許的變化范圍為獲利允許的變化范圍為12, 18。12max30 316 4zxx 注：模型求解模型求解 軟件實現軟件實現 LINGO 9.0 max =72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; Global optimal solution found. Objective

10、value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost （變量（變量) (取值）取值） （檢驗系數）（檢驗系數） X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price （行（行) (松弛或剩余變量取值）松弛或剩余變量取值） (對偶或影子價格）對偶或影子價格） 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000D

11、O RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產桶牛奶生產A1, 30桶生產桶生產A2，利潤，利潤3360元。元。 結果解釋結果解釋 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost （變量（變量) (取值）取值） （檢驗系數）（檢驗系數） X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price （

12、行（行) (松弛或剩余變量取值）松弛或剩余變量取值） (對偶或影子價格）對偶或影子價格） 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40三三種種資資源源“資源資源” 剩余為零的約束為剩余為零的約束為緊約束緊約束（有效約束）（有效約束） max =72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;結果解釋結果解釋 Global optimal solution found. Objec

13、tive value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000最優解下最優解下“資源資源”增加增加1單位時單位時“效益效益”的增的增量量 原料增加原料增加1單位單位, 利潤增長利潤增長48 時間增加時間增

14、加1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 120095.7x1+93x2+89.7x3+95.2x4+90.6x5+74.2x6+88.5x7+92.9x81750781x1+2106x2+5100 x3+93x4+8x6+278x8245040 x1+9x2+4x3+4x4+183.6x5+6x6+0.2x7+21x842240 x1+460 x2+290 x3+90 x4+190 x5+240 x6+280 x7+210 x82101.8x1+2.4x2+2.6x3+0.9x

15、4+1.7x5+4.6x6+3.9x7+1.2x817.5x1+x2+x3+x4+x5+x6+x7+x8=150 x120 x510 x335x230 x430 x630 x730 x830end: 模模型型求求解解 在Lindo6.1中輸入如下程序語句 LP OPTIMUM FOUND AT STEP 22 OBJECTIVE FUNCTION VALUE 1) 635.0000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 X3 35.000000 0.000000 X4 30.000000

16、0.000000 X5 5.000000 0.000000 X6 0.000000 1.000000 X7 0.000000 6.000000 X8 30.000000 0.000000運行后得到如下結果：可見最佳的食物搭配方案為一周安排20千克小白菜，30千克菠菜，35千克胡蘿卜，30千克小黃瓜，5千克豆芽和30千克蕃茄，方案最小費用為635元。小白菜菠菜胡蘿卜小黃瓜豆芽玉米香菇蕃茄結結果果分分析析生產、生活物資從若干供應點運送到一些需求點，生產、生活物資從若干供應點運送到一些需求點，怎樣安排輸送方案使運費最小，或利潤最大；怎樣安排輸送方案使運費最小，或利潤最大；運輸問題運輸問題(Trans

17、portation Problem)各種類型的貨物裝箱，由于受體積、重量等限制，各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數量最少。如何搭配裝載，使獲利最高，或裝箱數量最少。案例3：自來水輸送與貨機裝運問題其他費用其他費用: :450元元/千噸千噸 應如何分配水庫供水量，公司才能獲利最多？應如何分配水庫供水量，公司才能獲利最多？ 若水庫供水量都提高一倍，公司利潤可增加到多少？若水庫供水量都提高一倍，公司利潤可增加到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費引水管理費例例1 自來水輸

18、送自來水輸送收入：收入：900元元/千噸千噸 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水庫供水量水庫供水量(千噸千噸)小區基本用水量小區基本用水量(千噸千噸)小區額外用水量小區額外用水量(千噸千噸)（以天計）（以天計）總供水量：總供水量：160確定送水方案確定送水方案使利潤最大使利潤最大問題問題分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40 總需求量總需求量(300)每個水庫最大供水量都提高一每個水庫最大供水量都提高一倍倍利潤利潤 = 收入收入(900) 其它費用其它費用(

19、 (450) 引水管理費引水管理費利潤利潤(元元/千噸千噸)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZMax供應供應限制限制B, C 類似處理類似處理50:A14131211xxxx10014131211xxxx問題討論問題討論 確定送水方案確定送水方案使利潤最大使利潤最大需求約束可以不變需求約束可以不變求解求解 OBJECTIVE FUNCTION VALUE 1) 88700.00 VARIABLE VALU

20、E REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 總利潤總利潤 88700（元）（元） A(100)B(120)

21、C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030如何如何裝運，裝運，使本次飛行使本次飛行獲利最大？獲利最大？ 三個貨艙三個貨艙最大最大載載重重( (噸噸),),最大容積最大容積( (米米3 3) ) 例例2 貨機裝運貨機裝運 重量（噸）重量（噸）空間空間( 米米3/噸）噸）利潤（元利潤（元/噸）噸）貨物貨物1184803100貨物貨物2156503800貨物貨物3235803500貨物貨物4123902850三個貨艙中實際載重必須與其最大三個貨艙中實際載重必須與其最大載載重成比例重成比例 前倉：前倉：10；6800中倉：中倉：16；

22、8700后倉：后倉：8；5300飛機平衡飛機平衡決策決策變量變量 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量( (噸）噸）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉分別代表前、中、后倉)模型假設模型假設 每種貨物可以分割到任意小；每種貨物可以分割到任意小；貨機裝運貨機裝運每種貨物可以在一個或多個貨艙中任意分布；每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 模型建立模型建立 貨艙貨艙容積容積 目標目標函數函數( (利潤利潤)約束約束條件條件 )(2850)(3500)(3800)(3100

23、434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx530039058065048043332313xxxx貨機裝運貨機裝運模型建立模型建立 貨艙貨艙重量重量 1041312111xxxx1642322212xxxx843332313xxxx10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量約束約束條件條件平衡平衡要求要求 81610433323134232221241312111xxxxxxxx

24、xxxx貨物貨物供應供應 18131211xxx15232221xxx23333231xxx12434241xxx貨機裝運貨機裝運模型建立模型建立 10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量 OBJECTIVE FUNCTION VALUE 1) 121515.8 VARIABLE VALUE REDUCED COST X11 0.000000 400.000000 X12 0.000000 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.00000

25、0 239.473679 X23 5.000000 0.000000 X31 0.000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.000000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 貨物貨物2：前倉：前倉10, ,后倉后倉5； 貨物貨物3: : 中倉中倉13, 后倉后倉3；貨物貨物4: : 中倉中倉3。貨機裝運貨機裝運模型求解模型求解 最大利潤約最大利潤約121516元元貨物貨物供應點供應點貨艙貨艙需求點需求點平衡要求平衡要求運輸運輸

26、問題問題運輸問題的擴展運輸問題的擴展4.2 4.2 整數規劃模型整數規劃模型 實際問題中經常遇到貨物是不可分割的，如人，動物，整體裝配的設備等，這時候除了題目本身的約束外，還要加上決策變量的整數約束，這就是這節要介紹的整數規劃問題（Integer Programing ）。 整數規劃又可分為線性整數規劃和非線性整數規劃，這一節只介紹線性整數規劃。整數線性規劃中如果所有決策變量都是整數，則稱為純整數規劃；若只有部分變量為整數，則稱為混合整數規劃；若決策變量只能取0或1，則稱為0-1規劃。 求解整數規劃的算法主要是分枝定界法和割平面法，這兩種方法都是以求解線性規劃的方法為基礎。而0-1規劃的求解使

27、用隱枚舉法，它不需要用單純形法先求解線性規劃，而是依次檢查變量等于0或1的某種組合，以便使目前最好的可行解不斷加以改進，最終獲得最優解。 整數規劃的求解主要使用Lindo和Lingo軟件。 如果生產某一類型汽車，則至少要生產如果生產某一類型汽車，則至少要生產8080輛，輛， 那么最優的生產計劃應作何改變？那么最優的生產計劃應作何改變？汽車廠生產三種類型的汽車，已知各類型每輛車對鋼汽車廠生產三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現有量。材、勞動時間的需求，利潤及工廠每月的現有量。 小型小型 中型中型 大型大型 現有量現有量鋼材（噸）鋼材（噸） 1.5 3 5 6

28、00勞動時間（小時）勞動時間（小時） 280 250 400 60000利潤（萬元）利潤（萬元） 2 3 4 制訂月生產計劃，使工廠的利潤最大。制訂月生產計劃，使工廠的利潤最大。案例4：汽車生產計劃制定設每月生產小、中、大型設每月生產小、中、大型汽車的數量分別為汽車的數量分別為x1, x2, x3321432xxxzMax600535 . 1.321xxxts60000400250280321xxx0,321xxx汽車廠生產計劃汽車廠生產計劃 小型小型 中型中型 大型大型 現有量現有量鋼材鋼材 1.5 3 5 600時間時間 280 250 400 60000利潤利潤 2 3 4 線性線性規劃

29、規劃模型模型(LP)模型建立模型建立3） 模型中增加條件：模型中增加條件：x1, x2, x3 均為整數，重新求解。均為整數，重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.000000 0.003226結果為小數，結果為小數，怎么辦？怎么辦？1）舍去小數：

30、取）舍去小數：取x1=64，x2=167，算出目標函數值，算出目標函數值z=629，與，與LP最優值最優值632.2581相差不大。相差不大。2）試探：如取）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數等，計算函數值值z，通過比較可能得到更優的解。，通過比較可能得到更優的解。 但必須檢驗它們是否滿足約束條件。為什么？但必須檢驗它們是否滿足約束條件。為什么？模模型型求求解解IP可用可用LINDO直接求解直接求解整數規劃整數規劃( (Integer Programming, ,簡記簡記IP) )“gin 3”表示表示“前前3個變量個變量為整數為整數”，等價于：，等價于：

31、gin x1gin x2gin x3 IP 的最優解的最優解x1=64，x2=168，x3=0，最優值，最優值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE 1) 632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 321432xxxzMax600535 . 1.321xxxts6000040

32、0250280321xxx為非負整數321,xxxIP 結果輸出結果輸出模型求解模型求解其中其中3個個子模型應子模型應去掉，然后去掉，然后逐一求解，比較目標函數值，逐一求解，比較目標函數值，再加上整數約束，得最優解：再加上整數約束，得最優解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0,321xxx方法方法1：分解為：分解為8個個LP子模型子模型 汽車廠生產計劃汽車廠生產計劃 若生產某類汽車，則至少生產若生產某類汽車，則至少生產8080輛，求生產計

33、劃。輛，求生產計劃。321432xxxzMax600535 . 1.321xxxts60000400250280321xxxx1, ,x2, x3=0 或或 80 x1=80，x2= 150，x3=0，最優值，最優值z=610LINDO中對中對0-1變量的限定：變量的限定：int y1int y2int y3 方法方法2：引入引入0-1變量，化為整數規劃變量，化為整數規劃 M為大的正數，為大的正數，可取可取1000 OBJECTIVE FUNCTION VALUE 1) 610.0000VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2

34、150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000 若生產某類汽車，則至少生產若生產某類汽車，則至少生產8080輛，求生產計劃。輛，求生產計劃。x1=0 或 80 x2=0 或 80 x3=0 或 801 , 0,80,11111yyxMyx1 , 0,80,22222yyxMyx1 , 0,80,33333yyxMyx最優解同前最優解同前 案例5：鐵路平板車裝貨問題 有有七七種規格的包裝箱要裝到種規格的包裝箱要裝到兩輛兩輛鐵路平板車上

35、去。包裝箱的鐵路平板車上去。包裝箱的寬和高寬和高是一樣的，但是一樣的，但厚度厚度(t，以厘米計，以厘米計)及重量及重量(w，以公斤計，以公斤計)是是不同的。下表給出了每種包裝箱的厚度、重量以及數量。下圖不同的。下表給出了每種包裝箱的厚度、重量以及數量。下圖中每輛平板車有中每輛平板車有10.2米長的地方可用來裝包裝箱（象面包片那米長的地方可用來裝包裝箱（象面包片那樣樣)，載重為，載重為40噸。由于當地貨運的限制，對噸。由于當地貨運的限制，對C5,C6,C7類的包裝類的包裝箱的總數有一定的限制：這類箱子所占的空間箱的總數有一定的限制：這類箱子所占的空間(厚度厚度)不能超過不能超過302.7厘米。試

36、把包裝箱裝到平板車上去使得厘米。試把包裝箱裝到平板車上去使得浪費的空間最小浪費的空間最小。問問題題描描述述七種規格的包裝箱參數p 所有包裝箱的總重量為89噸，大于兩輛平板車的總載重量80，所以只能選擇性的裝載貨物. p 浪費空間是指平板車可裝車長度10.2m與每輛車所有包裝箱厚度總和的差值，可以等效的把浪費空間最小轉化成兩輛車裝車總量最大. p 包裝箱的重量和厚度受到平板車裝載條件的限制以及貨物總量的限制. 問題分析問題分析p 貨物是不可拆分的，所以這是一個典型的整數線性規劃問題.p 兩輛平板車之間存在相互的制約關系，在考慮一輛平板車時，必須同時考慮第二輛平板車. 問題分析問題分析p 對題目中

37、“由于當地貨運的限制，對C5,C6,C7類的包裝箱的總數有一定的限制：這類箱子所占的空間(厚度)不能超過302.7厘米。”可以理解成每輛車這三類貨物的裝車總數不超過302.7厘米，也可以是兩輛車裝載三類貨物的總量不超過302.7厘米. 模型假設模型假設1.各個貨物之間排列時靠在一起,包裝箱之間的空隙不計；2.裝載的過程中不考慮貨物在車上的排列次序及各個貨物的重量分布，排除因局部過重而造成平板車失衡的情況；3.鐵路平板車只能放置一列(排)包裝箱；4.兩輛平板車裝載C5,C6,C7三類包裝箱的總厚度不超過302.7厘米。 模型建立模型建立決策變量設xij表示第i輛平板車裝載Cj包裝箱的件數,i=1

38、,2;j=1,2,7. jjjnwt,分別表示包裝箱的厚度、單個重量和可供裝車的件數.參數變量裝車總厚度記為T，則目標函數可表示為： 目標函數2171maxijijjxtT約束條件各種包裝箱可供裝車數量的限制：7 , 1,21jnxijij平板車載重限制：2 , 1,4071ixwjijj厚度限制：2 , 1, 2 .1071ixtjijj模型建立模型建立約束條件兩輛車對包裝箱C5,C6,C7的特殊限制：027. 32175ijijjxt所有決策變量都是整數變量: Zijx模型求解模型求解 該整數規劃模型可以利用Lindo和Lingo求解。求解之前注意到20.4-3.027=17.373m，而

39、前4類貨物的總長度恰為17.373m。因此在滿足約束條件的情況下，應盡量將C1C4四類箱子裝完，以保證兩輛車浪費的空間最小。所以在求解時將前四類箱子的數量約束改成等式。max 0.487x11+0.52x12+0.613x13+0.72x14+0.487x15+0.52x16+0.64x17 +0.487x21+0.52x22+0.613x23+0.72x24+0.487x25+0.52x26+0.64x27st x11+x21=8 x12+x22=7 x13+x23=9 x14+x24=6 x15+x256 x16+x264 x17+x278 2x11+3x12+x13+0.5x14+4x1

40、5+2x16+x1740 2x21+3x22+x23+0.5x24+4x25+2x26+x2740 0.487x11+0.52x12+0.613x13+0.72x14+0.487x15+0.52x16+0.64x1710.2 0.487x21+0.52x22+0.613x23+0.72x24+0.487x25+0.52x26+0.64x2710.2 0.487x15+0.52x16+0.64x17+0.487x25+0.52x26+0.64x2750;x1+x260;x2+x350;x3+x440;x4+x520;x5+x630;gin(x1);gin(x2);gin(x3);gin(x4);

41、gin(x5);gin(x6);end Global optimal solution found. Objective value: 130.0000 Extended solver steps: 0 Total solver iterations: 7Variable Value Reduced Cost X1 50.00000 1.000000 X2 10.00000 1.000000 X3 40.00000 1.000000 X4 0.000000 1.000000 X5 30.00000 1.000000 X6 0.000000 1.000000計算結果：Lingo程序(方式一):

42、Global optimal solution found. Objective value: 130.0000 Extended solver steps: 0 Total solver iterations: 6 Variable Value Reduced CostREQUIRED( 1) 60.00000 0.000000REQUIRED( 2) 50.00000 0.000000REQUIRED( 3) 40.00000 0.000000REQUIRED( 4) 20.00000 0.000000REQUIRED( 5) 30.00000 0.000000REQUIRED( 6) 5

43、0.00000 0.000000DRIVER( 1) 50.00000 1.000000DRIVER( 2) 10.00000 1.000000DRIVER( 3) 40.00000 1.000000DRIVER( 4) 0.000000 1.000000DRIVER( 5) 30.00000 1.000000DRIVER( 6) 0.000000 1.000000求求解解結結果果即6個班次依次需要的司乘人員數量分別為：x1=50；x2=10；x3=40；x4=0；x5=30；x6=0。共計至少需要130名司乘人員。 生產中通過切割、剪裁、沖壓等生產中通過切割、剪裁、沖壓等手段，將原材料加工成

44、所需大小手段，將原材料加工成所需大小原料下料問題原料下料問題按照工藝要求，確定下料方案，按照工藝要求，確定下料方案，使所用材料最省，或利潤最大使所用材料最省，或利潤最大案例7：下料問題 I 問題問題. 如何下料最節省如何下料最節省 ? 例例1 鋼管下料鋼管下料 原料鋼管原料鋼管: :每根每根19米米 4米米50根根 6米米20根根 8米米15根根 工地需求工地需求節省的標準是什么？節省的標準是什么？問問題題描描述述 某建筑工地需要一批不同型號的鋼管，其中4m的50根，6m的20根，8m的15根。現在從鋼管廠進貨的原料都是19m的，需要對這些原料進行合理的切割。問怎樣切割使得既滿足工地需求，又使

45、浪費材料最小？按照客戶需要在一根原料鋼管上安排切割的一些組合按照客戶需要在一根原料鋼管上安排切割的一些組合: : 切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料應小于客戶需要鋼管的最小尺寸。的余料應小于客戶需要鋼管的最小尺寸。余料余料3米米 8米米1根根 8米米1根根 鋼管下料鋼管下料 為滿足客戶需要，按照哪些種合理模式，每種模式為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節省？切割多少根原料鋼管，最為節省？合理切割模式合理切割模式2. 所用原料鋼管總

46、根數最少所用原料鋼管總根數最少 模式模式 4米鋼管根數米鋼管根數6米鋼管根數米鋼管根數8米鋼管根數米鋼管根數余料余料(米米)14003231013201341203511116030170023鋼管下料問題鋼管下料問題兩種兩種標準標準1. 原料鋼管剩余總余量最小原料鋼管剩余總余量最小xi 按第按第i 種模式切割的原料鋼管根數種模式切割的原料鋼管根數( (i= =1,2,7) ) 約束約束滿足需求滿足需求 決策決策變量變量 目標目標1（總余量）（總余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12

47、根根, ,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根數根數6米米根數根數8米米根數根數余余料料14003231013201341203511116030170023需需求求502015最優解：最優解：x2=12, x5=15, 其余為其余為0；最優值：最優值：27。整數約束：整數約束： xi 為整數為整數model:sets:pattern/1.7/:residu,number;type/1.3/:required;link(pattern,type):aa;endsetsdata:residu=3 1 3 3 1 1 3;required=50 20 15;aa=4

48、 0 0 3 1 0 2 0 1 1 2 0 1 1 1 0 3 0 0 0 2; enddata!目標函數(總余量最小)min=sum(pattern:residu*number);!工地需求;for(type(i): sum(pattern(j): aa(j,i)*number(j)required(i);!各變量整數約束;for(pattern:gin(number);end鋼管切割問題的Lingo程序當余料沒有用處時，當余料沒有用處時，通常以總根數最少為目標通常以總根數最少為目標 76543212xxxxxxxZMin目標目標2（總根數）（總根數）鋼管下料問題鋼管下料問題1 1 約束條

49、約束條件不變件不變 最優解：最優解：x2=15, x5=5, x7=5, 其余為其余為0；最優值：最優值：25。5023454321xxxxx20326542xxxx152753xxxxi 為整數按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 雖余料增加雖余料增加8米，但減少了米，但減少了2根根 與與目標目標1的結果的結果“共切割共切割27根，余料根，余料27米米” 相比相比 板材板材規格規格2：長方形，長方形，32 28cm，2萬張。萬張。例例2 易拉罐下料易拉罐下料每周工作每周工作40小時，每只易拉罐利潤小

50、時，每只易拉罐利潤0.10元，原料余料損失元，原料余料損失0.001元元 / cm2（不能裝配的罐身、蓋、底也是余料）（不能裝配的罐身、蓋、底也是余料） 模式模式1：1.5秒秒模式模式2：2秒秒模式模式3：1秒秒上蓋上蓋下底下底罐罐身身罐身高罐身高10cm，上上蓋蓋、下底直、下底直徑均徑均5cm。 板材規格板材規格1：正方形，邊長正方形，邊長24cm，5萬張。萬張。如何安排每周生產？如何安排每周生產？ 1015.7模式模式4：3秒秒1015.7 罐身個數罐身個數底、蓋底、蓋個數個數余料損失余料損失（cm2）沖壓時間沖壓時間（秒）（秒）模式模式1110222.61.5模式模式224183.32模

51、式模式3016261.81模式模式446169.53模式模式1: 正方形正方形邊長邊長24cm 問題分析問題分析計算各種模式下的余料損失計算各種模式下的余料損失 上、下底直徑上、下底直徑d=5cm，罐身高罐身高h=10cm。 模式模式1 余料損失余料損失 242-10 d2/4 - dh=222.6 cm2問題分析問題分析目標目標: :易拉罐利潤扣除原料余料損失后的凈利潤最大易拉罐利潤扣除原料余料損失后的凈利潤最大 約束：約束：每周工作時間不超過每周工作時間不超過40小時；小時； 原料數量：原料數量：規格規格1（模式（模式1 3）5萬張，萬張， 規格規格2（模式（模式4）2萬張；萬張； 罐身和

52、底、蓋的配套組裝罐身和底、蓋的配套組裝 。注意注意：不能裝配的罐身、上下底也是余料：不能裝配的罐身、上下底也是余料決策決策變量變量 xi 按照第按照第i 種模式生產的張數種模式生產的張數( (i= =1,2,3,4) )；y1 一周生產的易拉罐個數；一周生產的易拉罐個數；y2 不配套的罐身個數；不配套的罐身個數；y3 不配套的底、蓋個數。不配套的底、蓋個數。 模型建立模型建立目標目標 約束約束條件條件 )6 .191 .1575 .1698 .2613 .1836 .222(001. 01 . 03243211yyxxxxyMax時間約束時間約束 144000325 . 14321xxxx原料

53、約束原料約束 ,50000321xxx200004x產量產量余料余料時間時間x1222.61.5x2183.32x3261.81x4169.53模型建立模型建立y1 易拉罐個數；易拉罐個數；y2 不配套的罐身；不配套的罐身；y3 不配套的底、蓋。不配套的底、蓋。每只易拉罐利潤每只易拉罐利潤0.10元，元，余料損失余料損失0.001元元 / cm2罐身罐身面積面積 dh=157.1 cm2 底蓋底蓋面積面積 d2/4=19.6 cm2(40小時小時)約束約束條件條件 配套約束配套約束 2/ )516410(,42min43214211xxxxxxxy1421242yxxx/p>

54、10yxxxxy,424211xxxy2/ )516410(43211xxxxyy1 易拉罐個數；易拉罐個數；y2 不配套的罐身；不配套的罐身；y3 不配套的底、蓋。不配套的底、蓋。罐身罐身底、蓋底、蓋1102401645產量產量x1x2x3x4雖然雖然xi和和y1，y2，y3應是整數，但是因生產量很大，應是整數，但是因生產量很大，可以把它們看成實數，從而用線性規劃模型處理可以把它們看成實數，從而用線性規劃模型處理 。將所有決策變量擴大將所有決策變量擴大10000倍（倍（xi 萬張，萬張，yi 萬件）萬件） LINDO發出警告信息：發出警告信息：“數據之間的數量級差別太大，數據之間的數量級差別

55、太大，建議進行預處理，縮小數據之間的差別建議進行預處理，縮小數據之間的差別”模式模式2生產生產40125張，張，模式模式3生產生產3750張，張，模式模式4生產生產20000張，張，共產易拉罐共產易拉罐160250個個( (罐身和底、蓋無剩余罐身和底、蓋無剩余) )，凈利潤為凈利潤為4298元元 , 5321xxx24x模型求解模型求解 OBJECTIVE FUNCTION VALUE 1) 0.4298337VARIABLE VALUE REDUCED COST Y1 16.025000 0.000000 X1 0.000000 0.000050 X2 4.012500 0.000000 X

56、3 0.375000 0.000000 X4 2.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484 , 4 .14325 . 14321xxxx下料問題的建模總結下料問題的建模總結 確定下料模式確定下料模式 構造優化模型構造優化模型 規格不太多，可枚舉下料模式，建立整數線性規劃模型，規格不太多，可枚舉下料模式，建立整數線性規劃模型，否則要構造整數非線性規劃模型，求解困難，可用否則要構造整數非線性規劃模型，求解困難，可用縮小縮小可行域可行域的方法進行化簡，但要保證最優解的存在。的方法進行化簡，但要保證最優解的存在。一維問題（如鋼管

57、下料）一維問題（如鋼管下料）二維問題（如易拉罐下料）二維問題（如易拉罐下料）具體問題具體分析（比較復雜具體問題具體分析（比較復雜 ）分派問題分派問題若干項任務分給一些候選人來完成，每人的專長不同，若干項任務分給一些候選人來完成，每人的專長不同，完成每項任務取得的效益或需要的資源就不同，如何分完成每項任務取得的效益或需要的資源就不同，如何分派任務使獲得的總效益最大，或付出的總資源最少。派任務使獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有成本不同，各個策略之間有相互制約關系相互制約關系，如

58、何在滿，如何在滿足一定條件下作出決擇，使得收益最大或成本最小。足一定條件下作出決擇，使得收益最大或成本最小。案例8：接力隊選拔和選課策略0-1規劃模型規劃模型 丁的蛙泳成績退步到丁的蛙泳成績退步到115”2；戊的自由泳成績進；戊的自由泳成績進步到步到57”5, 組成接力隊的方案是否應該調整組成接力隊的方案是否應該調整？如何選拔隊員組成如何選拔隊員組成4 4 100100米混合泳接力隊米混合泳接力隊? ?例例1 混合泳接力隊的選拔混合泳接力隊的選拔 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106

59、”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候選人的名候選人的百米成績百米成績窮舉法窮舉法：組成接力隊的方案共有組成接力隊的方案共有5!=120種種。目標目標函數函數若選擇隊員若選擇隊員i參加泳姿參加泳姿j 的比賽，記的比賽，記xij=1, , 否則記否則記xij=0 0-1規劃模型規劃模型 cij( (秒秒) )隊員隊員i 第第j 種泳姿的百米成績種泳姿的百米成績約束約束條件條件每人每人最多最多入選泳姿之一入選泳姿之一 ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.

60、484.669.683.8j=458.65359.457.262.44151jiijijxcZMin每種泳姿每種泳姿有且只有有且只有1 1人人 5, 1, 141ixjij4, 1, 151jxiij模型求解模型求解 最優解：最優解：x14 = x21 = x32 = x43 = 1, 其它變量為其它變量為0;成績為成績為253.2( (秒秒) )=413”2 MIN 66.8x11+75.6x12+87x13+58.6x14 + +67.4x51+71 x52+83.8x53+62.4x54SUBJECT TO x11+x12+x13+x14 =1 x41+x42+x43+x44 =1 x1