1、第四章 數學規劃模型 4.1 奶制品的生產與銷售4.2 自來水輸送與貨機裝運4.3 汽車生產與原油采購4.4 接力隊選拔和選課策略4.5 飲料廠的生產與檢修4.6 鋼管和易拉罐下料數學規劃模型 實際問題中的優化模型x決策變量f(x)目標函數gi(x)0約束條件多元函數條件極值 決策變量個數n和約束條件個數m較大 最優解在可行域的邊界上取得 數學規劃線性規劃非線性規劃整數規劃重點在模型的建立和結果的分析企業生產計劃4.1 奶制品的生產與銷售 空間層次工廠級：根據外部需求和內部設備、人力、原料等條件，以最大利潤為目標制訂產品生產計劃；車間級：根據生產計劃、工藝流程、資源約束及費用參數等，以最小成本

2、為目標制訂生產批量計劃.時間層次若短時間內外部需求和內部資源等不隨時間變化，可制訂單階段生產計劃，否則應制訂多階段生產計劃.本節課題例1 加工奶制品的生產計劃1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶 時間480小時 至多加工100公斤A1 制訂生產計劃，使每天獲利最大 35元可買到1桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到 30元/公斤，應否改變生產計劃？ 每天：問題1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產A1

3、x2桶牛奶生產A2 獲利 243x1 獲利 164 x2 原料供應 勞動時間 加工能力 決策變量 目標函數 每天獲利約束條件非負約束 線性規劃模型(LP)時間480小時 至多加工100公斤A1 50桶牛奶 每天基本模型模型分析與假設 比例性 可加性 連續性 xi對目標函數的“貢獻”與xi取值成正比 xi對約束條件的“貢獻”與xi取值成正比 xi對目標函數的“貢獻”與xj取值無關 xi對約束條件的“貢獻”與xj取值無關 xi取值連續 A1,A2每公斤的獲利是與各自產量無關的常數每桶牛奶加工A1,A2的數量, 時間是與各自產量無關的常數A1,A2每公斤的獲利是與相互產量無關的常數每桶牛奶加工A1,

4、A2的數量,時間是與相互產量無關的常數加工A1,A2的牛奶桶數是實數 線性規劃模型模型求解 圖解法 x1x20ABCDl1l2l3l4l5約束條件目標函數 Z=0Z=2400Z=3600z=c (常數) 等值線c在B(20,30)點得到最優解目標函數和約束條件是線性函數 可行域為直線段圍成的凸多邊形 目標函數的等值線為直線 最優解一定在凸多邊形的某個頂點取得。 模型求解 軟件實現 LINGO model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end Global optimal solution fou

5、nd. 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 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 20桶牛奶生產A1, 30桶生產A2，利潤3360元。 結果解釋 Global optimal solu

6、tion 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 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 model:max = 72*x1+64*x2;milk x1 + x250;time

7、12*x1+8*x2480;cpct 3*x1100;end三種資源“資源” 剩余為零的約束為緊約束（有效約束） 原料無剩余時間無剩余加工能力剩余40結果解釋 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 1 3360.000 1.000000 MILK 0.000000

8、48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000最優解下“資源”增加1單位時“效益”的增量 影子價格 35元可買到1桶牛奶，要買嗎?35 48, 應該買！ 聘用臨時工人付出的工資最多每小時幾元? 2元！原料增加1單位, 利潤增長48 時間增加1單位, 利潤增長2 加工能力增長不影響利潤Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase D

9、ecrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000 最優解不變時目標函數系數允許變化范圍 敏感性分析 (“LINGO|Ranges” ) x1系數范圍(64,96) x2系

10、數范圍(48,72) A1獲利增加到 30元/公斤，應否改變生產計劃? x1系數由24 3=72增加為303=90，在允許范圍內 不變！(約束條件不變)結果解釋 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Ro

11、w Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000影子價格有意義時約束右端的允許變化范圍 原料最多增加10 時間最多增加53 35元可買到1桶牛奶, 每天最多買多少?最多買10桶!(目標函數不變)充分條件 !例2 奶制品的生產銷售計劃 在例1基礎上深加工1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 0.8公斤B

12、12小時,3元1公斤獲利44元/公斤 0.75公斤B22小時,3元1公斤獲利32元/公斤 制訂生產計劃，使每天凈利潤最大 30元可增加1桶牛奶，3元可增加1小時時間，應否投資？現投資150元，可賺回多少？50桶牛奶, 480小時 至多100公斤A1 B1，B2的獲利經常有10%的波動，對計劃有無影響？ 每天銷售10公斤A1的合同必須滿足，對利潤有什么影響？1桶牛奶 3kg A1 12小時 8小時 4kg A2 或獲利24元/kg 獲利16元/kg 0.8kg B12小時,3元1kg獲利44元/kg 0.75kg B22小時,3元1kg獲利32元/kg 出售x1 kg A1, x2 kg A2，

13、 x3 kg B1, x4 kg B2原料供應 勞動時間 加工能力 決策變量 目標函數 利潤約束條件非負約束 x5 kg A1加工B1， x6 kg A2加工B2附加約束 基本模型模型求解 軟件實現 LINGO Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.00000

14、0 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Val

15、ue Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.000

16、00結果解釋每天銷售168 kgA2和19.2 kgB1， 利潤3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，將得到的24kgA1全部加工成B1 除加工能力外均為緊約束結果解釋Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.000

17、00 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000增加1桶牛奶使利潤增長3.1612=37.92增加1小時時間使利潤增長3.26 30元可增加1桶牛奶，3元可增加1小時時間，應否投資？現投資150元，可賺回多少？投資150元增加5桶牛奶,可賺回189.6元。(大于

18、增加時間的利潤增長)結果解釋B1,B2的獲利有10%的波動，對計劃有無影響 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X

19、5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY 敏感性分析 B1獲利下降10%，超出X3 系數允許范圍B2獲利上升10%，超出X4 系數允許范圍波動對計劃有影響生產計劃應重新制訂：如將x3的系數改為39.6計算，會發現結果有很大變化。 Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000

20、 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000結果解釋x1從0開始增加一個單位時，最優目標函數值將減少1.68Reduced Cost有意

21、義也是有條件的(LINGO沒有給出)每天銷售10公斤A1的合同必須滿足，對利潤有什么影響？公司利潤減少1.6810=16.8（元）最優利潤為 3460.8 16.8 = 3444 奶制品的生產與銷售 由于產品利潤、加工時間等均為常數，可建立線性規劃模型. 線性規劃模型的三要素：決策變量、目標函數、約束條件. 用LINGO求解，輸出豐富，利用影子價格和靈敏性分析可對結果做進一步研究. 建模時盡可能利用原始的數據信息，把盡量多的計算留給計算機去做（分析例2的建模）.4.2 自來水輸送與貨機裝運生產、生活物資從若干供應點運送到一些需求點，怎樣安排輸送方案使運費最小，或利潤最大?運輸問題各種類型的貨物

22、裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數量最少?其他費用:450元/千噸 應如何分配水庫供水量，公司才能獲利最多？ 若水庫供水量都提高一倍，公司利潤可增加到多少？ 元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費例1 自來水輸送收入：900元/千噸 支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水庫供水量(千噸)小區基本用水量(千噸)小區額外用水量(千噸)（以天計）總供水量：160確定送水方案使利潤最大問題分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：1

23、0；40 總需求量(300)每個水庫最大供水量都提高一倍利潤 = 收入(900) 其它費用(450) 引水管理費利潤(元/千噸)甲乙丙丁A290320230280B310320260300C260250220/供應限制B, C 類似處理問題討論 確定送水方案使利潤最大需求約束可以不變求解部分結果：Objective Value: 88700.00 Variable Value Reduced Cost X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21

24、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)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030供應點需求點物資供需平衡或不平衡如何裝運，使本次飛行獲利最大？ 三個貨艙最大載重(噸),最大容積(米3) 例2 貨機裝運重量（

25、噸）空間( 米3/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850三個貨艙中實際載重必須與其最大載重成比例. 前倉：10；6800中倉：16；8700后倉：8；5300飛機平衡WET=(10,16,8), VOL=(6800,8700,5300); w=(18,15,23,12), v=(480,650, 580,390), p=(3100,3800,3500,2850).已知參數 i=1,2,3,4（貨物）j=1,2,3 (分別代表前、中、后倉)貨艙j的重量限制WETj體積限制VOLj第i種貨物的重量wi，體積vi，利潤pi貨

26、機裝運決策變量 xij-第i 種貨物裝入第j 個貨艙的重量(噸）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉)模型假設 每種貨物可以分割到任意小；貨機裝運每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并保證不留空隙； 所給出的數據都是精確的，沒有誤差. 模型建立 貨艙容積 目標函數(利潤)約束條件貨機裝運模型建立 貨艙重量 10；680016；87008；5300 xij-第i 種貨物裝入第j 個貨艙的重量約束條件平衡要求 貨物供應 貨機裝運模型建立 10；680016；87008；5300 xij-第i 種貨物裝入第j 個貨艙的重量j,k=1,2,3; jk !定

27、義集合及變量;sets: cang/1.3/:WET,VOL; wu/1.4/:w,v,p; link(wu,cang):x;endsets!對已知變量賦值;data: WET=10,16,8; VOL=6800,8700,5300; w=18,15,23,12; v=480,650, 580,390; p=3100,3800,3500,2850;enddatamax=sum(wu(i):p(i)*sum(cang(j):x(i,j);for(wu(i):sum(cang(j):x(i,j)w(i);for(cang(j):sum(wu(i):x(i,j)WET(j);for(cang(j):

28、sum(wu(i):v(i)*x(i,j)VOL(j);for(cang(j):for(cang(k)|k #GT# j:!#GT#是大于等于的含義;sum(wu(i):x(i,j)/WET(j)=sum(wu(i):x(i,k)/WET(k););END貨機裝運LINGO程序 Global optimal solution found. Objective value: 121515.8 Total solver iterations: 12Variable Value Reduced Cost X( 1, 1) 0.000000 400.0000 X( 1, 2) 0.000000 57.

29、89474 X( 1, 3) 0.000000 400.0000 X( 2, 1) 7.000000 0.000000 X( 2, 2) 0.000000 239.4737 X( 2, 3) 8.000000 0.000000 X( 3, 1) 3.000000 0.000000 X( 3, 2) 12.94737 0.000000 X( 3, 3) 0.000000 0.000000 X( 4, 1) 0.000000 650.0000 X( 4, 2) 3.052632 0.000000 X( 4, 3) 0.000000 650.0000貨物2：前倉7,后倉8； 貨物3: 前倉3, 中倉

30、13；貨物4: 中倉3。貨機裝運模型求解 最大利潤約121516元貨物供應點貨艙需求點裝載平衡要求運輸問題運輸問題的擴展 如果生產某一類型汽車，則至少要生產80輛， 那么最優的生產計劃應作何改變？例1 汽車廠生產計劃 汽車廠生產三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現有量. 小型 中型 大型 現有量鋼材（噸） 1.5 3 5 600勞動時間（小時） 280 250 400 60000利潤（萬元） 2 3 4 制訂月生產計劃，使工廠的利潤最大.4.3 汽車生產與原油采購設每月生產小、中、大型汽車的數量分別為x1, x2, x3汽車廠生產計劃 模型建立 小型 中型

31、 大型 現有量鋼材 1.5 3 5 600時間 280 250 400 60000利潤 2 3 4 線性規劃模型(LP)模型求解 3）模型中增加條件：x1, x2, x3 均為整數，重新求解. Objective Value: 632.2581 Variable Value Reduced Cost X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 Row Slack or Surplus Dual Price 2 0.000000 0.731183 3 0.000000 0.003226結果為小數，怎么辦？1）

32、舍去小數：取x1=64，x2=167，算出目標函數值 z=629，與LP最優值632.2581相差不大.2）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數值z，通過比較可能得到更優的解. 但必須檢驗它們是否滿足約束條件. 為什么？IP可用LINGO直接求解整數規劃(Integer Programming,簡記IP)IP 的最優解x1=64，x2=168，x3=0，最優值z=632 max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;gin(x1);gin(x2);gin(x3); Globa

33、l optimal solution found. Objective value: 632.0000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost X1 64.00000 -2.000000 X2 168.0000 -3.000000 X3 0.000000 -4.000000模型求解 IP 結果輸出其中3個子模型應去掉，然后逐一求解，比較目標函數值，再加上整數約束，得最優解：方法1：分解為8個LP子模型 汽車廠生產計劃 若生產某類汽車，則至少生產80輛，求生產計劃.x1,x2,

34、 x3=0 或 80 x1=80，x2= 150，x3=0，最優值z=610LINGO中對0-1變量的限定：bin(y1); bin(y2); bin(y3);方法2：引入0-1變量，化為整數規劃 M為大的正數,本例可取1000 Objective Value: 610.0000 Variable Value Reduced Cost X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000

35、 若生產某類汽車，則至少生產80輛，求生產計劃.x1=0 或 80 x2=0 或 80 x3=0 或 80最優解同前 max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x30;x2*(x2-80)0;x3*(x3-80)0;gin(x1);gin(x2);gin(x3);方法3：化為非線性規劃 非線性規劃（Non- Linear Programming，簡記NLP） 若生產某類汽車，則至少生產80輛，求生產計劃. x1=0 或 80 x2=0 或 80 x3=0 或 80最優解同前.一般地，整數規劃和非線性規劃的求解比線性規劃困難

36、得多，特別是問題規模較大或者要求得到全局最優解時. 汽車廠生產計劃 決策變量為整數, 建立整數規劃模型. 求解整數規劃和非線性規劃比線性規劃困難得多 (即便用數學軟件) . 當整數變量取值很大時, 可作為連續變量處理, 問題簡化為線性規劃. 對于類似于“x=0 或 80”這樣的條件，通常引入0-1變量處理，盡量不用非線性規劃（特別是引入的整數變量個數較少時）.應如何安排原油的采購和加工 ？ 例2 原油采購與加工 市場上可買到不超過1500噸的原油A： 購買量不超過500噸時的單價為10000元/噸； 購買量超過500噸但不超過1000噸時，超過500噸的 部分8000元/噸； 購買量超過100

37、0噸時，超過1000噸的部分6000元/噸. 售價4800元/噸 售價5600元/噸庫存500噸 庫存1000噸 汽油甲(A50%) 原油A 原油B 汽油乙 (A60%) 決策變量 目標函數問題分析 利潤：銷售汽油的收入購買原油A的支出. 難點：原油A的購價與購買量的關系較復雜.甲(A50%) A B 乙(A60%) 購買xx11x12x21x224.8千元/噸 5.6千元/噸原油A的購買量,原油A, B生產汽油甲,乙的數量c(x) 購買原油A的支出利潤(千元)c(x)如何表述？原油供應 約束條件 x 500噸單價為10千元/噸； 500噸 x 1000噸，超過500噸的8千元/噸；1000噸

38、 x 1500噸，超過1000噸的6千元/噸. 目標函數購買xA B x11x12x21x22庫存500噸 庫存1000噸 目標函數中c(x)不是線性函數，是非線性規劃； 對于用分段函數定義的c(x)，一般的非線性規劃軟件也難以輸入和求解； 想辦法將模型化簡，用現成的軟件求解. 汽油含原油A的比例限制 約束條件甲(A50%) A B 乙(A60%) x11x12x21x22x1 , x2 , x3 以價格10, 8, 6(千元/噸)采購A的噸數目標函數 只有當以10千元/噸的價格購買x1=500(噸)時，才能以8千元/噸的價格購買x2方法1 非線性規劃模型，可以用LINGO求解模型求解x= x

39、1+x2+x3, c(x) = 10 x1+8x2+6x3 500噸 x 1000噸，超過500噸的8千元/噸增加約束x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 類似地有方法1：LINGO求解Model:Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3;x11+x12 x + 500;x21+x22 0; 2*x12 - 3*x22 0;x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0; x1 500;x2 500;x3 0 y=1與方法1（全

40、局最優解）的結果相同引入0-1變量b1 b2 b3 b4方法3 b1 xb2，x= z1b1+z2b2，z1+z2=1，z1, z20, c(x)= z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2 x b3，x= z2b2+z3b3， z2+z3=1，z2, z3 0, c(x)= z2c(b2)+z3c(b3). b3 x b4，x= z3b3+z4b4，z3+z4=1，z3, z4 0, c(x)= z3c(b3)+z4c(b4). 直接處理處理分段線性函數c(x) IP模型，LINGO求解，得到的結果與方法2相同.bkxbk+1yk=1,

41、否則,yk=0方法3 bkxbk+1 ,x= zkbk+z k+1 bk+1zk+zk+1 =1，zk, zk+1 0, c(x)= zkc(bk)+zk+1 c(bk+1 ).c(x)x1200090005000050010001500b1 b2 b3 b4對于k=1,2,3 方法3: 直接處理分段線性函數，方法更具一般性. 分段函數無法直接用非線性規劃方法或軟件求解.原油采購與加工 方法1: 增加約束化為非線性規劃,可以用LINGO 求解, 但可能得到的是局部最優解. 方法2: 引入0-1變量, 化為線性規劃模型, 可用LINGO求解.分派問題4.4 接力隊選拔和選課策略 若干項任務分給一

42、些候選人來完成，每人的專長不同,完成每項任務取得的效益或需要的資源不同，如何分派任務使獲得的總效益最大，或付出的總資源最少? 若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有相互制約關系，如何在滿足一定條件下作出抉擇，使得收益最大或成本最小?討論:丁的蛙泳成績退步到115”2；戊的自由泳成績進步到57”5, 組成接力隊的方案是否應該調整？如何選拔隊員組成4100米混合泳接力隊?例1 混合泳接力隊的選拔 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”

43、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.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人 模型求解 MODEL:sets: person/1.5/; position/1.4/; link(person,posi

44、tion): c, x;endsetsdata: c= 66.8, 75.6, 87, 58.6, 57.2, 66, 66.4, 53, 78, 67.8, 84.6, 59.4, 70, 74.2, 69.6, 57.2, 67.4, 71, 83.8, 62.4;enddata輸入LINGO求解 min=sum(link: c*x);for(person(i): sum(position(j):x(i,j)=1;);for(position(i): sum(person(j):x(j,i)=1;);for(link: bin(x);END 模型求解 最優解：x14 = x21 = x32

45、 = x43 = 1, 其它變量為0;成績為253.2(秒)=413”2 輸入LINGO求解 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.丁蛙泳c43 = 69.675.2 (秒)，戊自由泳c54= 62.4 57.5 (秒), 方案是否調整？ 敏感性分析？新方案:乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳IP一般沒有與LP相類似的理論，LINGO輸出的敏感性分析結果通常是沒有意義的.最優解：x

46、21 = x32 = x43 = x51 = 1, 成績為417”7 c43, c54 的新數據重新輸入模型，用LINGO求解 原分配方案:甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.討論混合泳接力隊的選拔 指派(Assignment)問題：有若干項任務, 每項任務必有且只能有一人承擔，每人只能承擔一項，不同人員承擔不同任務的效益(或成本)不同，怎樣分派各項任務使總效益最大(或總成本最小)? 人員數量與任務數量相等 人員數量大于任務數量(本例) 人員數量小于任務數量 ?建立0-1規劃模型是常用方法 為了選修課程門數最少，應學習哪些課程 ？ 例2 選課策略要求至少選兩門數學課、三門運籌學課和兩門計

47、算機課 課號課名學分所屬類別先修課要求1微積分5數學2線性代數4數學3最優化方法4數學；運籌學微積分；線性代數4數據結構3數學；計算機計算機編程5應用統計4數學；運籌學微積分；線性代數6計算機模擬3計算機；運籌學計算機編程7計算機編程2計算機8預測理論2運籌學應用統計9數學實驗3運籌學；計算機微積分；線性代數選修課程最少，且學分盡量多，應學習哪些課程 ？ 0-1規劃模型 決策變量 目標函數 xi=1 選修課號i 的課程（xi=0 不選） 選修課程總數最少 約束條件最少2門數學課，3門運籌學課，2門計算機課.課號課名所屬類別1微積分數學2線性代數數學3最優化方法數學；運籌學4數據結構數學；計算機

48、5應用統計數學；運籌學6計算機模擬計算機；運籌學7計算機編程計算機8預測理論運籌學9數學實驗運籌學；計算機先修課程要求最優解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它為0；6門課程，總學分21. 0-1規劃模型 約束條件x3=1必有x1 = x2 =1模型求解（LINGO） 課號課名先修課要求1微積分2線性代數3最優化方法微積分；線性代數4數據結構計算機編程5應用統計微積分；線性代數6計算機模擬計算機編程7計算機編程8預測理論應用統計9數學實驗微積分；線性代數學分最多多目標優化的處理方法：化成單目標優化。兩目標(多目標)規劃 討論：選修課程最少，學分盡量多，應學習

49、哪些課程？ 課程最少 以學分最多為目標,不管課程多少. 以課程最少為目標,不管學分多少.最優解如上，6門課程，總學分21 .最優解顯然是選修所有9門課程 .多目標規劃 在課程最少的前提下以學分最多為目標.最優解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它為0；總學分由21增至22.注意：最優解不唯一！課號課名學分1微積分52線性代數43最優化方法44數據結構35應用統計46計算機模擬37計算機編程28預測理論29數學實驗3 LINGO不能告訴優化問題的解是否唯一.可將x9 =1 易為x6 =1增加約束 ，以學分最多為目標求解.多目標規劃 對學分數和課程數加權形成一個

50、目標，如三七開. 最優解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1，其它為0；總學分28.課號課名學分1微積分52線性代數43最優化方法44數據結構35應用統計46計算機模擬37計算機編程28預測理論29數學實驗3 討論與思考最優解與1=0，2=1的結果相同學分最多.多目標規劃 最優解與1=1，2=0的結果相同課程最少. 選 課 策 略用0-1變量表示策略選擇是常用的方法 “要選甲 (x1)必選乙 (x2)” 可用x1 x2描述. “要選甲 (x1)必不選乙 (x2)” 怎樣描述? “甲乙二人至多選一人” 怎樣描述? “甲乙二人至少選一人” 怎樣描述?

51、雙(多)目標規劃的處理方法 加權組合成一個新目標, 化為單目標規劃. 一個目標作為約束, 解另一個目標的規劃.問題1 公司應該與哪些候選企業建立代理關系 ？ 例3 銷售代理的開發與中斷公司未來5年的業務量分別為400，500，600，700和800 問題2 若目前全部建立了代理關系，應如何進行調整 ？ 候選代理1候選代理2候選代理3候選代理4年最大業務量350250300200一次性費用(萬元)100809070年運行費用(萬元)7.54.06.53.0代理1代理2代理3代理4臨時中斷費用(萬元)5342重新恢復費用(萬元)5419問題的建模決策變量 目標函數 xit=1 在第t年初(首次)與

52、代理i建立代理關系 xit=0 否 總費用（建立代理 運行費用）最小 公司可在任一年開始與代理建立代理關系. 代理關系一旦建立，將長期保持.假 設 建立代理運行費用問題的建模約束條件公司每年的業務量必須能夠由足夠的代理承擔 第1年第2年第3年第4年第5年問題的求解LINGO求解結果x11= x21= x44=1(其他變量為0)，最小總費用313.5萬元公司應在第1年初與代理1、2建立代理關系;在第4年初與代理4建立代理關系. 假定公司一旦與候選代理建立代理關系，則這一關系將長期保持 i=1,2,3,4： 問題2的建模決策變量 目標函數 xit=1 第t年代理i從事代理業務； xit=0 否 總

53、費用（運行費+中斷費恢復費）最小公司目前已與所有代理建立代理關系.公司每年初可中斷或恢復代理關系.假 設 yit=1 第t年與代理i中斷代理關系； yit=0 否 zit=1 第t年與代理i恢復代理關系； zit=0 否 yit=1 第t年與代理i中斷代理關系； yit=0 否 zit=1 第t年與代理i恢復代理關系； zit=0 否 問題2的建模約束條件業務量約束、業務中斷約束、業務恢復約束 業務量約束：每年公司的業務量由足夠的代理承擔 業務中斷約束：某年運行，下一年不運行，則需中斷如果xit=1而xi,t+1=0，則yi,t+1=1 業務恢復約束：某年不運行，下一年運行，則需恢復如果xit

54、=0而xi,t+1=1，則zi,t+1=1 問題2的求解模型分析xit的值：x11= x12= x13= x14= x15= x23= x24= x25= x41= x42= x43= x44= x45=1 (其他為0); 最小總費用86.5萬元.公司應在第1年初臨時中斷與代理2、3的代理關系，而在第3年初重新恢復與代理2的代理關系. LINGO求解結果可只要求xit為0-1變量，最優解中yit (zit)自然是0-1變量 設法減少整數變量數目4.5 飲料廠的生產與檢修單階段生產計劃多階段生產計劃 生產批量問題 企業生產計劃考慮與產量無關的固定費用.給優化模型求解帶來新的困難.外部需求和內部資

55、源隨時間變化 安排生產計劃, 滿足每周的需求, 使4周總費用最小.存貯費:每周每千箱飲料 0.2 (千元). 例1 飲料廠的生產與檢修計劃 在4周內安排一次設備檢修，占用當周15千箱生產能力，能使檢修后每周增產5千箱，檢修應排在哪一周? 周次需求量(千箱)生產能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計100135某種飲料4周的需求量、生產能力和成本問題分析 除第4周外每周的生產能力超過每周的需求； 生產成本逐周上升；前幾周應多生產一些. 周次需求能力11530225403354542520合計100135成本5.05.15.45.5 飲料

56、廠在第1周開始時沒有庫存； 從費用最小考慮, 第4周末不能有庫存； 周末有庫存時需支出一周的存貯費； 每周末的庫存量等于下周初的庫存量. 模型假設 目標函數約束條件產量、庫存與需求平衡 決策變量 能力限制 非負限制 模型建立x1 x4：第14周的生產量y1 y3：第13周末庫存量周次需求能力11530225403354542520成本5.05.15.45.5存貯費:0.2(千元/周千箱) 模型求解 4周生產計劃的總費用為528 (千元) 最優解： x1 x4：15，40，25，20； y1 y3： 0，15，5 .周次需求能力11530225403354542520成本5.05.15.45.5

57、產量15402520庫存01550LINGO求解討論 增加庫存量(y1 y3)為決策變量使模型清晰并便于檢查.檢修計劃0-1變量wt ：wt=1 檢修安排在第t周(t=1,2,3,4） 在4周內安排一次設備檢修,占用當周15千箱生產能力,能使檢修后每周增產5千箱，檢修應排在哪一周? 檢修安排在任一周均可周次需求能力11530225403354542520成本5.05.15.45.5約束條件能力限制 產量、庫存與需求平衡條件不變 增加約束條件：檢修1次檢修計劃目標函數不變0-1變量 wt=1 檢修安排在第t周LINGO求解總費用由528降為527(千元) 檢修所導致的生產能力提高的作用, 需要更

58、長的時間才能得到充分體現 .最優解：w1=1, w2 , w3, w4=0; x1 x4：15,45,15,25； y1 y3：0,20,0 .討論 引入0-1變量表示檢修例2 飲料的生產批量問題 安排生產計劃, 滿足每周的需求, 使4周總費用最小.存貯費:每周每千箱飲料 0.2 (千元) (與例1同) . 飲料廠使用同一條生產線輪流生產多種飲料。若某周開工生產某種飲料, 需支出生產準備費8千元. 某種飲料4周的需求量、生產能力和成本(與例1同)周次需求量(千箱)生產能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計100135ct 時段t 生產

59、費用(元/件);ht 時段t (末)存貯費(元/件)st 時段t 生產準備費(元)；dt 時段t 市場需求(件)；Mt 時段t 生產能力(件).假設初始庫存為0.制訂生產計劃, 滿足需求并使T個時段的總費用最小.決策變量 xt 時段t 生產量；yt 時段t (末)存貯量；問題分析與例1的主要差別:需考慮與生產數量無關的費用生產準備費模型建立wt =1 時段t 開工生產 (wt =0 不開工).混合0-1規劃模型 目標函數約束條件模型建立 ct 生產費,ht 存貯費,st 準備費,dt 需求量, Mt 生產能力,xt 生產量,yt 存貯量,wt 開工生產0-1變量. 滿足需求 既含可變費用(生產

60、成本、存貯費)又含固定費用(生產準備費)的多階段生產計劃問題.最優解：x1 x4：15，40，45，0；總費用：554.0(千元) 將所給參數代入模型，用LINGO求解模型求解與例1的最優解： x1 x4：15,45,15,25 的區別!生產批量(Lot-sizing)問題 關鍵是引入0-1變量wt表示時段t是否開工生產.生產中通過切割、剪裁、沖壓等手段，將原材料加工成規定大小的成材.6 鋼管和易拉罐下料原料下料問題優化問題: 按照工藝要求，確定下料方案，使所用材料最省，或利潤最大.問題1. 如何下料最節省 ? 例1 鋼管下料 問題2. 客戶增加需求：原料鋼管:每根19米 4米50根 6米20