1、實(shí)際問(wèn)題中 的優(yōu)化模型,x決策變量,f(x)目標(biāo)函數(shù),gi(x)0約束條件,多元函數(shù)條件極值,決策變量個(gè)數(shù)n和 約束條件個(gè)數(shù)m較大,最優(yōu)解在可行域 的邊界上取得,數(shù)學(xué)規(guī)劃,線性規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃,重點(diǎn)在模型的建立和結(jié)果的分析,第四章 數(shù)學(xué)規(guī)劃模型,第四章 數(shù)學(xué)規(guī)劃模型,4.1 奶制品的生產(chǎn)與銷售 4.2 自來(lái)水輸送與貨機(jī)裝運(yùn) 4.3 汽車生產(chǎn)與原油采購(gòu) 4.4 接力隊(duì)選拔和選課策略 4.5 飲料廠的生產(chǎn)與檢修 4.6 鋼管和易拉罐下料 4.7 廣告投入與升級(jí)調(diào)薪 4.8 投資的風(fēng)險(xiǎn)與收益,企業(yè)生產(chǎn)計(jì)劃,4.1 奶制品的生產(chǎn)與銷售,空間層次,工廠級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條

2、件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；,車間級(jí)：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃.,時(shí)間層次,若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，可制訂單階段生產(chǎn)計(jì)劃，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃.,例1 加工奶制品的生產(chǎn)計(jì)劃,50桶牛奶,時(shí)間480h,至多加工100kgA1,制訂生產(chǎn)計(jì)劃，使每天獲利最大,35元可買到1桶牛奶，買嗎？若買，每天最多買多少?,可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?,A1的獲利增加到 30元/kg，應(yīng)否改變生產(chǎn)計(jì)劃？,每天：,問(wèn)題,x1桶牛奶生產(chǎn)A1,x2桶牛奶生產(chǎn)A2,獲利 243x1,獲利 164 x2,原料供應(yīng),勞動(dòng)時(shí)

3、間,加工能力,決策變量,目標(biāo)函數(shù),每天獲利,約束條件,非負(fù)約束,線性規(guī)劃模型(LP),時(shí)間480h,至多加工100kgA1,基本模型,模型分析與假設(shè),比例性,可加性,連續(xù)性,xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比,xi對(duì)約束條件的“貢獻(xiàn)”與xi取值成正比,xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無(wú)關(guān),xi對(duì)約束條件的“貢獻(xiàn)”與xj取值無(wú)關(guān),xi取值連續(xù),A1,A2每千克的獲利是與各自產(chǎn)量無(wú)關(guān)的常數(shù),每桶牛奶加工A1,A2的數(shù)量, 時(shí)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù),A1,A2每千克的獲利是與相互產(chǎn)量無(wú)關(guān)的常數(shù),每桶牛奶加工A1,A2的數(shù)量,時(shí)間是與相互產(chǎn)量無(wú)關(guān)的常數(shù),加工A1,A2的牛奶桶數(shù)是實(shí)數(shù),線性規(guī)

4、劃模型,模型求解,圖解法,約束條件,目標(biāo)函數(shù),z=c (常數(shù)) 等值線,在B(20,30)點(diǎn)得到最優(yōu)解.,目標(biāo)函數(shù)和約束條件是線性函數(shù),可行域?yàn)橹本€段圍成的凸多邊形,目標(biāo)函數(shù)的等值線為直線,最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得.,模型求解,軟件實(shí)現(xiàn),LINGO,model: max = 72*x1+64*x2; milk x1 + x250; time 12*x1+8*x2480; cpct 3*x1100; end,Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variab

5、le 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桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤(rùn)3360元.,結(jié)果解釋,Global optimal solution found. Objective value: 3360.000 Total solver iterations:

6、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 12*x1+8*x2480; cpct 3*x1100; end,三種資源,“資源” 剩余為零的約束為緊約束（有效約束）

7、,結(jié)果解釋,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 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,最優(yōu)解下“資源”增加1單位“效益”的增

8、量,35元可買到1桶牛奶，要買嗎?,35 48, 應(yīng)該買！,聘用臨時(shí)工人付出的工資最多每小時(shí)幾元?,2元！,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowa

9、ble RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000,最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍,敏感性分析 (“LINGO|Ranges” ),x1系數(shù)范圍(64,96),x2系數(shù)范圍(48,72),A1獲利增加到 30元/kg，應(yīng)否改變生產(chǎn)計(jì)劃?,x1系數(shù)由24 3=72增加為303=90，在允許范圍內(nèi),不變！,(約束條件不變),結(jié)果解釋,Ranges in which the basis is unchan

10、ged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease 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

11、 CPCT 100.0000 INFINITY 40.00000,影子價(jià)格有意義時(shí)約束右端的允許變化范圍,原料最多增加10,時(shí)間最多增加53,35元可買到1桶牛奶, 每天最多買多少?,最多買10桶!,目標(biāo)函數(shù)不變,充分條件 !,例2 奶制品的生產(chǎn)銷售計(jì)劃,在例1基礎(chǔ)上深加工,制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大,30元可增加1桶牛奶，3元可增加1h時(shí)間，應(yīng)否投資？現(xiàn) 投資150元，可賺回多少？,50桶牛奶, 480h,至多100kgA1,B1，B2的獲利經(jīng)常有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響？,每天銷售10kgA1的合同必須滿足，對(duì)利潤(rùn)有什么影響？,出售x1 kg A1, x2 kg A2，,x3 kg

12、 B1, x4 kg B2,原料供應(yīng),勞動(dòng)時(shí)間,加工能力,決策變量,目標(biāo)函數(shù),利潤(rùn),約束條件,非負(fù)約束,x5 kg A1加工B1， x6 kg A2加工B2,附加約束,基本模型,模型求解,軟件實(shí)現(xiàn),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.000000

13、 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,Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Val

14、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

15、00,結(jié)果解釋,每天銷售168 kgA2和19.2 kgB1， 利潤(rùn)3460.8（元）,8桶牛奶加工成A1，42桶牛奶加工成A2， 將得到的24kgA1全部加工成B1,除加工能力外均為緊約束,結(jié)果解釋,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

16、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,增加1桶牛奶使利潤(rùn)增長(zhǎng)3.1612=37.92,增加1h時(shí)間使利潤(rùn)增長(zhǎng)3.26,30元可增加1桶牛奶，3元可增加1h時(shí)間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？,投資150元增加5桶牛奶,可賺回189

17、.6元(大于增加時(shí)間的利潤(rùn)增長(zhǎng)).,結(jié)果解釋,B1,B2的獲利有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 24.00000 1.68000 INFINITY X2 16.00000 8.15000 2.10000 X3 44.00000 19.75000 3.166667 X4 32.00000 2.026667 INFINITY

18、X5 -3.00000 15.80000 2.533333 X6 -3.00000 1.52000 INFINITY ,B1獲利下降10%，超出X3 系數(shù)允許范圍,B2獲利上升10%，超出X4 系數(shù)允許范圍,波動(dòng)對(duì)計(jì)劃有影響,生產(chǎn)計(jì)劃應(yīng)重新制訂：如將x3的系數(shù)改為39.6計(jì)算，會(huì)發(fā)現(xiàn)結(jié)果有很大變化.,敏感性分析,結(jié)果解釋,x1從0開(kāi)始增加一個(gè)單位時(shí)，最優(yōu)目標(biāo)函數(shù)值將減少1.68,Reduced Cost是有意義、有條件的(LINGO沒(méi)有給出),每天銷售10kgA1的合同必須滿足， 對(duì)利潤(rùn)有什么影響？,公司利潤(rùn)減少 1.6810=16.8（元）,最優(yōu)利潤(rùn)為 3460.8 16.8 = 3444,

19、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.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000

20、000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000,小結(jié)與評(píng)注,由于產(chǎn)品利潤(rùn)、加工時(shí)間等均為常數(shù)，可 建立線性規(guī)劃模型.,線性規(guī)劃模型的三要素：決策變量、目標(biāo) 函數(shù)、約束條件.,用LINGO求解，輸出豐富，利用影子價(jià)格 和靈敏性分析可對(duì)結(jié)果做進(jìn)一步研究.,建模時(shí)盡可能利用原始的數(shù)據(jù)信息，把盡量 多的計(jì)算留給計(jì)算機(jī)去做（分析例2的建模）.,4.2 自來(lái)水輸送與貨機(jī)裝運(yùn),生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大?

21、,運(yùn)輸問(wèn)題,各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少?,其他費(fèi)用:450元/ 103t,應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？,若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？,例1 自來(lái)水輸送,收入：900元/103t,支出,總供水量：160,確定送水方案使利潤(rùn)最大,問(wèn)題分析, 總需求量：120+180=300,總收入900160=144000(元),收入：900元/ 103t,其他費(fèi)用:450元/ 103t,支出,引水管理費(fèi),其他支出450160=72000(元),供應(yīng)限制,約束條件,需求限制,線性規(guī)劃模型(LP),目標(biāo)函數(shù),水庫(kù)i 向j 區(qū)的日

22、供水量為 xij（x34=0）,決策變量,模型建立,確定3個(gè)水庫(kù)向4個(gè)小區(qū)的供水量,模型求解,部分結(jié)果： Objective Value: 24400.00 Variable Value Reduced Cost X11 0.000000 30.000000 X12 50.000000 0.000000 X13 0.000000 50.000000 X14 0.000000 20.000000 X21 0.000000 10.000000 X22 50.000000 0.000000 X23 0.000000 20.000000 X24 10.000000 0.000000 X31 40.00

23、0000 0.000000 X32 0.000000 10.000000 X33 10.000000 0.000000,利潤(rùn)=總收入-其他費(fèi)用-引水管理費(fèi)=144000-72000-24400 = 47600（元）,引水管理費(fèi) 24400(元),目標(biāo)函數(shù),總供水量(320) 總需求量(300),每個(gè)水庫(kù)最大供水量都提高一倍,利潤(rùn) = 收入(900) 其他費(fèi)用(450) 引水管理費(fèi),供應(yīng)限制,B, C 類似處理,問(wèn)題討論,確定送水方案使利潤(rùn)最大,需求約束可以不變,模型求解,部分結(jié)果： Objective Value: 88700.00 Variable Value Reduced Cost X1

24、1 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,運(yùn)輸問(wèn)題,總利潤(rùn) 88700（元）,供需平衡或不平衡,如何裝運(yùn)，使本次飛行獲利最大？,三個(gè)貨艙最

25、大載重(t),最大容積(m3),例2 貨機(jī)裝運(yùn),三個(gè)貨艙中實(shí)際載重必須與其最大載重成比例.,飛機(jī)平衡,模型假設(shè),每種貨物可以分割到任意小；,每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；,多種貨物可以混裝，并保證不留空隙；,所給出的數(shù)據(jù)都是精確的，沒(méi)有誤差.,第i種貨物的重量wi, 體積vi, 利潤(rùn)pi (i=1,2,3,4),已知參數(shù),貨艙j的重量限制WETj , 體積限制VOLj, (j=1,2,3 分別代表前、中、后倉(cāng)),貨艙容積,目標(biāo)函數(shù)(利潤(rùn)),約束條件,模型建立,貨艙重量,xij-第i 種貨物裝入第j 個(gè)貨艙的重量 i=1,2,3,4, j=1,2,3,決策變量,約束條件,平衡要求,貨物

26、供應(yīng),模型建立,xij-第i 種貨物裝入第j 個(gè)貨艙的重量,j,k=1,2,3; jk,Global optimal solution found. Objective value: 121515.8 Total solver iterations: 12 Variable Value Reduced Cost X( 1, 1) 0.000000 400.0000 X( 1, 2) 0.000000 57.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)

27、 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：前倉(cāng)7,后倉(cāng)8； 貨物3: 前倉(cāng)3, 中倉(cāng)13；貨物4: 中倉(cāng)3.,模型求解,最大利潤(rùn)約121516元,貨物供應(yīng)點(diǎn) 貨艙需求點(diǎn),裝載平衡要求,如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛， 那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？,例1 汽車廠

28、生產(chǎn)計(jì)劃,汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量.,制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大.,4.3 汽車生產(chǎn)與原油采購(gòu),設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1, x2, x3,模型建立,線性規(guī)劃模型(LP),模型求解,3）模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解.,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 S

29、urplus Dual Price 2 0.000000 0.731183 3 0.000000 0.003226,結(jié)果為小數(shù)，怎么辦？,1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值 z=629，與LP最優(yōu)值632.2581相差不大.,2）試探：如取x1=65，x2=167；x1=64，x2=168等， 計(jì)算函數(shù)值z(mì)，通過(guò)比較可能得到更優(yōu)的解.,但必須檢驗(yàn)它們是否滿足約束條件. 為什么？,IP可用LINGO直接求解,整數(shù)規(guī)劃(Integer Programming,簡(jiǎn)記IP),IP 的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632,max=2*x1+3*x2+4*x3;

30、 1.5*x1+3*x2+5*x3600; 280*x1+250*x2+400*x3 60000; gin(x1);gin(x2);gin(x3);,Global 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 結(jié)果輸出,其中3個(gè)子模型應(yīng)去

31、掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：,方法1：分解為8個(gè)LP子模型,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.,x1,x2, x3=0 或 80,x1=80，x2= 150，x3=0，最優(yōu)值z(mì)=610,LINGO中對(duì)0-1變量的限定： bin(y1); bin(y2); bin(y3);,方法2：引入0-1變量，化為整數(shù)規(guī)劃,M為大的正數(shù),本例可取1000,Objective Value: 610.0000 Variable Value Reduced Cost X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.

32、000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.,x1=0 或 80,最優(yōu)解同前,max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x30; x2*(x2-80)0; x3*(x3-80)0; gin(x1);gin(x2);gin(x3);,方法3：化為非線性規(guī)劃,非線性規(guī)劃（Non- Linear Programming，簡(jiǎn)記NLP）,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.,x1=0 或 80,最優(yōu)解同前.,

33、一般地，整數(shù)規(guī)劃和非線性規(guī)劃的求解比線性規(guī)劃困難得多，特別是問(wèn)題規(guī)模較大或者要求得到全局最優(yōu)解時(shí).,決策變量為整數(shù), 建立整數(shù)規(guī)劃模型.,求解整數(shù)規(guī)劃和非線性規(guī)劃比線性規(guī)劃困難得多 (即便用數(shù)學(xué)軟件) .,當(dāng)整數(shù)變量取值很大時(shí), 可作為連續(xù)變量處理, 問(wèn)題簡(jiǎn)化為線性規(guī)劃.,對(duì)于類似于“x=0 或 80”這樣的條件，通常引入0-1變量處理，盡量不用非線性規(guī)劃（特別是引入的整數(shù)變量個(gè)數(shù)較少時(shí)）.,小結(jié)與評(píng)注,應(yīng)如何安排原油的采購(gòu)和加工 ？,市場(chǎng)上可買到不超過(guò)1500t的原油A： 購(gòu)買量不超過(guò)500t時(shí)的單價(jià)為10000元/t； 購(gòu)買量超過(guò)500t但不超過(guò)1000t時(shí)，超過(guò)500t的 部分8000元

34、/t； 購(gòu)買量超過(guò)1000t時(shí)，超過(guò)1000t的部分6000元/t.,例2 原油采購(gòu)與加工,決策變量,目標(biāo)函數(shù),問(wèn)題分析,利潤(rùn)：銷售汽油的收入購(gòu)買原油A的支出. 難點(diǎn)：原油A的購(gòu)價(jià)與購(gòu)買量的關(guān)系較復(fù)雜.,原油A的購(gòu)買量,原油A, B生產(chǎn)汽油甲,乙的數(shù)量,c(x) 購(gòu)買原油A的支出,利潤(rùn)(千元),c(x)如何表述？,原油供應(yīng),約束條件,x 500，單價(jià)為10千元/t； 500 x 1000，超過(guò)500t的8千元/t； 1000 x 1500，超過(guò)1000t的6千元/t.,目標(biāo)函數(shù),汽油含原油A的比例限制,約束條件,目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；,對(duì)于用分段函數(shù)定義的c(x)，一般

35、的非線性規(guī)劃 軟件也難以輸入和求解；,想辦法將模型化簡(jiǎn)，用現(xiàn)成的軟件求解.,x1 , x2 , x3 以價(jià)格10, 8, 6(千元/t)采購(gòu)A的噸數(shù),目標(biāo)函數(shù),只有當(dāng)以10千元/t的價(jià)格購(gòu)買x1=500(t)時(shí)，才能以8千元/t的價(jià)格購(gòu)買x2,方法1,非線性規(guī)劃模型，可以用LINGO求解,模型求解,x= x1+x2+x3, c(x) = 10 x1+8x2+6x3,500 x 1000，超過(guò)500t的8千元/t,類似地有,方法1：LINGO求解,Local optimal solution found. Objective value: 4800.000 Total solver iterat

36、ions: 14 Variable Value Reduced Cost X11 500.0000 0.000000 X21 500.0000 0.000000 X12 0.000000 0.2666667 X22 0.000000 0.000000 X1 0.000000 0.4000000 X2 0.000000 0.000000 X3 0.000000 0.000000 X 0.000000 0.000000,LINGO得到的是局部最優(yōu)解,還能得到更好的解嗎？,用庫(kù)存的500t原油A、500t原油B生產(chǎn)汽油甲，不購(gòu)買新的原油A，利潤(rùn)為4800千元.,方法1：LINGO求解,計(jì)算全局最優(yōu)解

37、 ： 選LINGO|Options菜單； 在彈出的選項(xiàng)卡中選擇“General Solver”； 然后找到選項(xiàng)“Use Global Solver”將其選中； 應(yīng)用或保存；重新求解。,Global optimal solution found. Objective value: 5000.000 Extended solver steps: 1 Total solver iterations: 43 Variable Value Reduced Cost X11 0.000000 0.000000 X21 0.000000 0.900000 X12 1500.000 0.000000 X22

38、1000.000 0.000000 X1 500.0000 0.000000 X2 500.0000 0.000000 X3 0.000000 0.000000 X 1000.000 0.000000,還有其他建模和求解方法嗎？,購(gòu)買1000t原油A，與庫(kù)存的500t原油A和1000t原油B一起，共生產(chǎn)2500t汽油乙，利潤(rùn)為5000千元 .,y1, y2 , y3=1 以價(jià)格10, 8, 6(千元/t)采購(gòu)A,增加約束,方法2,0-1線性規(guī)劃模型, 可用LINGO求解.,y1,y2,y3 =0或1,購(gòu)買1000t原油A，與庫(kù)存的500t原油A和1000t原油B一起，生產(chǎn)汽油乙，利潤(rùn)為5000

39、千元 .,x1 , x2 , x3 以價(jià)格10, 8, 6(千元/t)采購(gòu)A的噸數(shù),與方法1（全局最優(yōu)解）的結(jié)果相同,引入0-1變量,模型求解,b1 b2 b3 b4,方法3,b1 xb2，x= z1b1+z2b2， z1+z2=1，z1, z20, c(x)= z1c(b1)+z2c(b2).,b2 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).,直接處理處理分段線性函數(shù)c(x),IP模型，LIN

40、GO求解，得到的結(jié)果與方法2相同.,bkxbk+1yk=1,否則,yk=0,方法3,bkxbk+1 ,x= zkbk+z k+1 bk+1 zk+zk+1 =1，zk, zk+1 0, c(x)= zkc(bk)+zk+1 c(bk+1 ).,對(duì)于k=1,2,3,方法3: 直接處理分段線性函數(shù)，方法更具一般性.,分段函數(shù)無(wú)法直接用非線性規(guī)劃方法或軟件求解.,方法1: 增加約束化為非線性規(guī)劃,可以用LINGO 求解, 但可能得到的是局部最優(yōu)解.,方法2: 引入0-1變量, 化為線性規(guī)劃模型, 可用 LINGO求解.,小結(jié)與評(píng)注,分派問(wèn)題,4.4 接力隊(duì)選拔和選課策略,若干項(xiàng)任務(wù)分給一些候選人來(lái)完

41、成，每人的專長(zhǎng)不同,完成每項(xiàng)任務(wù)取得的效益或需要的資源不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少?,若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個(gè)策略之間有相互制約關(guān)系，如何在滿足一定條件下作出抉擇，使得收益最大或成本最小?,如何選拔隊(duì)員組成4100m混合泳接力隊(duì)?,例1 混合泳接力隊(duì)的選拔,5名候選人4種泳姿的百米成績(jī),窮舉法：組成接力隊(duì)的方案共有5!=120種.,討論:丁的蛙泳成績(jī)退步到 ；戊的自由泳成績(jī)進(jìn)步到 , 組成接力隊(duì)的方案是否應(yīng)該調(diào)整？,目標(biāo)函數(shù),若選擇隊(duì)員i參加泳姿j 的比賽，記xij=1, 否則記xij=0,0-1規(guī)劃模型,cij隊(duì)員i第j 種泳姿

42、的百米成績(jī)(s),約束條件,每人最多入選泳姿之一,每種泳姿有且只有1人,模型求解,最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其他變量為0;,LINGO求解,甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.,成績(jī)?yōu)?53.2(s)=,丁蛙泳c43 = 69.675.2 (s)，戊自由泳c54= 62.4 57.5 (s), 方案是否調(diào)整？,敏感性分析？,新方案:乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳,IP一般沒(méi)有與LP相類似的理論，LINGO輸出的敏感性分析結(jié)果通常是沒(méi)有意義的.,c43, c54 的新數(shù)據(jù)重新輸入模型，用LINGO求解,原分配方案: 甲 自由泳、乙 蝶泳、丙 仰

43、泳、丁 蛙泳.,討論,最優(yōu)解：x21 = x32 = x43 = x51 = 1, 成績(jī)?yōu)?混合泳接力隊(duì)的選拔,指派(Assignment)問(wèn)題：有若干項(xiàng)任務(wù), 每項(xiàng)任務(wù)必有且只能有一人承擔(dān)，每人只能承擔(dān)一項(xiàng)，不同人員承擔(dān)不同任務(wù)的效益(或成本)不同，怎樣分派各項(xiàng)任務(wù)使總效益最大(或總成本最小)?,人員數(shù)量與任務(wù)數(shù)量相等,人員數(shù)量大于任務(wù)數(shù)量(本例),人員數(shù)量小于任務(wù)數(shù)量 ?,建立0-1規(guī)劃模型是常用方法,為了選修課程門(mén)數(shù)最少，應(yīng)學(xué)習(xí)哪些課程 ？,要求至少選兩門(mén)數(shù)學(xué)課、三門(mén)運(yùn)籌學(xué)課和兩門(mén)計(jì)算機(jī)課,選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程 ？,例2 選課策略,0-1規(guī)劃模型,決策變量,目標(biāo)函數(shù)

44、,xi=1 選修課號(hào)i 的課程（xi=0 不選）,選修課程總數(shù)最少,約束條件,最少2門(mén)數(shù)學(xué)課，3門(mén)運(yùn)籌學(xué)課， 2門(mén)計(jì)算機(jī)課.,先修課程要求,最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其他為0；6門(mén)課程，總學(xué)分21.,0-1規(guī)劃模型,約束條件,x3=1必有x1 = x2 =1,模型求解（LINGO）,學(xué)分最多,多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化.,兩目標(biāo)(多目標(biāo))規(guī)劃,討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？,課程最少,以學(xué)分最多為目標(biāo),不管課程多少.,以課程最少為目標(biāo),不管學(xué)分多少.,多目標(biāo)規(guī)劃,在課程最少的前提下以學(xué)分最多為目標(biāo).,最優(yōu)解： x1 =

45、 x2 = x3 = x5 = x7 = x9 =1, 其他為0；總學(xué)分由21增至22.,注意：最優(yōu)解不唯一！,LINGO不能告訴優(yōu)化問(wèn)題的解是否唯一.,可將x9 =1 易為x6 =1,多目標(biāo)規(guī)劃,對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開(kāi).,最優(yōu)解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1， 其他為0；總學(xué)分28.,討論與思考,最優(yōu)解與1=0，2=1的結(jié)果相同學(xué)分最多.,多目標(biāo)規(guī)劃,最優(yōu)解與1=1，2=0的結(jié)果相同課程最少.,選 課 策 略,用0-1變量表示策略選擇是常用的方法,“要選甲 (x1)必選乙 (x2)” 可用x1 x2描述.,“要選甲 (

46、x1)必不選乙 (x2)” 怎樣描述?,“甲乙二人至多選一人” 怎樣描述?,“甲乙二人至少選一人” 怎樣描述?,雙(多)目標(biāo)規(guī)劃的處理方法,加權(quán)組合成一個(gè)新目標(biāo), 化為單目標(biāo)規(guī)劃.,一個(gè)目標(biāo)作為約束, 解另一個(gè)目標(biāo)的規(guī)劃.,4.5 飲料廠的生產(chǎn)與檢修,單階段生產(chǎn)計(jì)劃,多階段生產(chǎn)計(jì)劃,生產(chǎn)批量問(wèn)題,企業(yè)生產(chǎn)計(jì)劃,考慮與產(chǎn)量無(wú)關(guān)的固定費(fèi)用.,給優(yōu)化模型求解帶來(lái)新的困難.,安排生產(chǎn)計(jì)劃, 滿足每周的需求, 使4周總費(fèi)用最小.,存貯費(fèi):每周每千箱飲料 0.2 (千元).,例1 飲料廠的生產(chǎn)與檢修計(jì)劃,4周內(nèi)安排一次設(shè)備檢修,占用當(dāng)周15千箱生產(chǎn)能力, 能使檢修后每周增產(chǎn)5千箱,檢修應(yīng)排在哪一周?,某種

47、飲料4周的需求量、生產(chǎn)能力和成本,問(wèn)題分析,除第4周外每周的生產(chǎn)能力超過(guò)每周的需求； 生產(chǎn)成本逐周上升； 前幾周應(yīng)多生產(chǎn)一些.,飲料廠在第1周開(kāi)始時(shí)沒(méi)有庫(kù)存； 從費(fèi)用最小考慮, 第4周末不能有庫(kù)存； 周末有庫(kù)存時(shí)需支出一周的存貯費(fèi)； 每周末的庫(kù)存量等于下周初的庫(kù)存量.,模型假設(shè),目標(biāo)函數(shù),約束條件,產(chǎn)量、庫(kù)存與需求平衡,決策變量,能力限制,非負(fù)限制,模型建立,x1 x4：第14周的生產(chǎn)量,y1 y3：第13周末庫(kù)存量,存貯費(fèi):0.2(千元/周千箱),模型求解,4周生產(chǎn)計(jì)劃的總費(fèi)用為528 (千元),最優(yōu)解： x1 x4：15，40，25，20； y1 y3： 0，15，5 .,LINGO求解,

48、討論,增加庫(kù)存量(y1 y3)為決策變量使模型清晰并便于檢查.,檢修計(jì)劃,0-1變量wt ：wt=1 檢修安排在第t周(t=1,2,3,4）,在4周內(nèi)安排一次設(shè)備檢修,占用當(dāng)周15千箱生產(chǎn)能力,能使檢修后每周增產(chǎn)5千箱，檢修應(yīng)排在哪一周?,檢修安排在任一周均可,約束條件,能力限制,產(chǎn)量、庫(kù)存與需求平衡條件不變,增加約束條件：檢修1次,檢修計(jì)劃,目標(biāo)函數(shù)不變,0-1變量 wt=1 檢修安排在第t周,LINGO求解,總費(fèi)用由528降為527(千元),檢修所導(dǎo)致的生產(chǎn)能力提高的作用, 需要更長(zhǎng)的時(shí)間才能得到充分體現(xiàn) .,最優(yōu)解：w1=1, w2 , w3, w4=0; x1 x4：15,45,15,

49、25； y1 y3：0,20,0 .,討論,引入0-1變量表示檢修,例2 飲料的生產(chǎn)批量問(wèn)題,安排生產(chǎn)計(jì)劃, 滿足每周的需求, 使4周總費(fèi)用最小.,存貯費(fèi):每周每千箱飲料 0.2 (千元) (與例1同) .,飲料廠使用同一條生產(chǎn)線輪流生產(chǎn)多種飲料. 若某周開(kāi)工生產(chǎn)某種飲料, 需支出生產(chǎn)準(zhǔn)備費(fèi)8千元.,某種飲料4周的需求量、生產(chǎn)能力和成本(與例1同),ct 時(shí)段t 生產(chǎn)費(fèi)用(元/件);ht 時(shí)段t (末)存貯費(fèi)(元/件) st 時(shí)段t 生產(chǎn)準(zhǔn)備費(fèi)(元)；dt 時(shí)段t 市場(chǎng)需求(件)； Mt 時(shí)段t 生產(chǎn)能力(件).,假設(shè)初始庫(kù)存為0.,制訂生產(chǎn)計(jì)劃, 滿足需求并使T個(gè)時(shí)段的總費(fèi)用最小.,決策變量

50、,xt 時(shí)段t 生產(chǎn)量；yt 時(shí)段t (末)存貯量；,問(wèn)題分析,與例1的主要差別:,需考慮與生產(chǎn)數(shù)量無(wú)關(guān)的費(fèi)用生產(chǎn)準(zhǔn)備費(fèi),模型建立,wt =1 時(shí)段t 開(kāi)工生產(chǎn) (wt =0 不開(kāi)工).,混合0-1規(guī)劃模型,目標(biāo)函數(shù),約束條件,模型建立,ct 生產(chǎn)費(fèi),ht 存貯費(fèi),st 準(zhǔn)備費(fèi),dt 需求量, Mt 生產(chǎn)能力,xt 生產(chǎn)量,yt 存貯量,wt 開(kāi)工生產(chǎn)0-1變量., 滿足需求,既含可變費(fèi)用(生產(chǎn)成本、存貯費(fèi))又含固定費(fèi)用(生產(chǎn)準(zhǔn)備費(fèi))的多階段生產(chǎn)計(jì)劃問(wèn)題.,最優(yōu)解：x1 x4：15，40，45，0；總費(fèi)用：554.0(千元),將所給參數(shù)代入模型，用LINGO求解,模型求解,與例1的最優(yōu)解： x

51、1 x4：15,45,15,25 的區(qū)別!,生產(chǎn)批量(lot-sizing)問(wèn)題,關(guān)鍵是引入0-1變量wt表示時(shí)段t是否開(kāi)工生產(chǎn).,生產(chǎn)中通過(guò)切割、剪裁、沖壓等手段，將原材料加工成規(guī)定大小的成材.,4.6 鋼管和易拉罐下料,原料下料問(wèn)題,優(yōu)化問(wèn)題: 按照工藝要求，確定下料方案，使所用材料最省，或利潤(rùn)最大.,問(wèn)題1. 如何下料最節(jié)省 ?,例1 鋼管下料,問(wèn)題2. 客戶增加需求：,節(jié)省的標(biāo)準(zhǔn)是什么？,由于采用不同切割模式太多, 會(huì)增加生產(chǎn)和管理成本,規(guī)定切割模式不能超過(guò)3種. 如何下料最節(jié)??？,按照客戶需要在一根原料鋼管上安排切割的一種組合,如:,切割模式,合理切割模式的余料應(yīng)小于客戶需要鋼管的最

52、小尺寸.,鋼管下料,為滿足客戶需要，按照哪些種合理模式切割，每種模式切割多少根原料鋼管，最為節(jié)?。?合理切割模式,2. 所用原料鋼管總根數(shù)最少 .,鋼管下料問(wèn)題1,節(jié)省的 兩種標(biāo)準(zhǔn),1. 原料鋼管剩余總余量最小 .,xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,7),約束,滿足需求,決策變量,目標(biāo)1（總余量）,按模式2切割12根,按模式5切割15根,共27根,余料27m.,最優(yōu)解：x2=12, x5=15, 其余為0； 最優(yōu)值：27.,整數(shù)約束： xi 為整數(shù),目標(biāo)2（總根數(shù)）,鋼管下料問(wèn)題1,約束條件不變,最優(yōu)解：x2=15, x5=5, x7=5, 其余為0； 最優(yōu)值：25.,xi 為整

53、數(shù),按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35m .,目標(biāo)2切割減少了2根, 但余料增加8m, 為什么?,與目標(biāo)1的結(jié)果“共切割27根，余料27m” 相比.,若余料沒(méi)有用處, 通常以總根數(shù)最少為目標(biāo).,鋼管下料問(wèn)題1,目標(biāo)1(總余量) x2=12, x5=15, 共27根,余27m,目標(biāo)2(總根數(shù)) x2=15, x5=5, x7=5, 共25根, 余35m,按照目標(biāo)1比需求多生產(chǎn)1根4m、7根6m, 共46m, 正好等于2根原料(38m)再加8m.,原料鋼管:每根19m,若多生產(chǎn)的也視為余料, 則總余量最小等價(jià)于總根數(shù)最少.,鋼管下料問(wèn)題2,對(duì)大規(guī)模問(wèn)題，用模

54、型的約束條件界定合理模式.,增加一種需求：10根5m ；切割模式不超過(guò)3種.,現(xiàn)有4種需求：50根4m, 10根5m, 20根6m,15根8m，用枚舉法確定合理切割模式，過(guò)于復(fù)雜.,決策變量,xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,3).,r1i, r2i, r3i, r4i 第i 種切割模式下，每根原料鋼管生產(chǎn)4m、5m、6m和8m長(zhǎng)的鋼管的數(shù)量.,滿足需求,模式合理：每根余料不超過(guò)3m,整數(shù)非線性規(guī)劃模型,鋼管下料問(wèn)題2,目標(biāo)函數(shù)（總根數(shù)）,約束條件,整數(shù)約束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)為整數(shù),增加約束，縮小可行域，便于求解.,原料鋼管總

55、根數(shù)下界：,特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管 模式1：切割成4根4m鋼管，需13根； 模式2：切割成1根5m和2根6m鋼管，需10根； 模式3：切割成2根8m鋼管，需8根. 原料鋼管總根數(shù)上界：13+10+8=31,模式排列順序可任定,鋼管下料問(wèn)題2,需求：50根4m，10根5m，20根6m，15根8m,每根原料鋼管長(zhǎng)19m,LINGO求解整數(shù)非線性規(guī)劃模型,Local optimal solution found. Objective value: 28.00000 Variable Value Reduced Cost X( 1) 10.00000 1.000000 X( 2) 10.0000

56、0 1.000000 X( 3) 8.000000 1.000000 R( 1, 1) 3.000000 0.000000 R( 1, 2) 2.000000 0.000000 R( 1, 3) 0.000000 0.000000 R( 2, 1) 0.000000 0.000000 R( 2, 2) 1.000000 0.000000 R( 2, 3) 0.000000 0.000000 R( 3, 1) 1.000000 0.000000 R( 3, 2) 1.000000 0.000000 R( 3, 3) 0.000000 0.000000 R( 4, 1) 0.000000 0.000000 R( 4, 2) 0.000000 0.000000 R( 4, 3) 2.000000 0.000000,也是全局最優(yōu)解 模式1：每根原料鋼管切割成 3根4m和1根6m鋼管, 共10根; 模式2：每根原料鋼管切