數(shù)學(xué)模型(第四版)課件第四章.ppt

1、第四章 數(shù)學(xué)規(guī)劃模型,4.1 奶制品的生產(chǎn)與銷售 4.2 自來水輸送與貨機(jī)裝運(yùn) 4.3 汽車生產(chǎn)與原油采購 4.4 接力隊選拔和選課策略 4.5 飲料廠的生產(chǎn)與檢修 4.6 鋼管和易拉罐下料,數(shù)學(xué)規(guī)劃模型,實(shí)際問題中 的優(yōu)化模型,x決策變量,f(x)目標(biāo)函數(shù),gi(x)0約束條件,多元函數(shù)條件極值,決策變量個數(shù)n和 約束條件個數(shù)m較大,最優(yōu)解在可行域 的邊界上取得,數(shù)學(xué)規(guī)劃,線性規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃,重點(diǎn)在模型的建立和結(jié)果的分析,優(yōu)化模型與優(yōu)化軟件的重要意義,(最)優(yōu)化:在一定條件下,尋求使目標(biāo)最大(小)的決策 最優(yōu)化是工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究、社會生活中經(jīng)常遇到的問題, 如: 結(jié)構(gòu)

2、設(shè)計 資源分配 生產(chǎn)計劃 運(yùn)輸方案 解決優(yōu)化問題的手段 經(jīng)驗積累，主觀判斷 作試驗，比優(yōu)劣 建立數(shù)學(xué)模型(優(yōu)化模型)，求最優(yōu)策略(決策) (最)優(yōu)化:在一定條件下,尋求使目標(biāo)最大(小)的決策 CUMCM賽題：約一半以上與優(yōu)化有關(guān)，需用軟件求解。,(最)優(yōu)化理論是運(yùn)籌學(xué)的基本內(nèi)容,運(yùn)籌學(xué)(OR: Operations/Operational Research) 管理科學(xué)(MS: Management Science) 決策科學(xué)(DS: Decision Science) 優(yōu)化(Optimization), 規(guī)劃(Programming),無約束優(yōu)化,線性規(guī)劃,非線性規(guī)劃,網(wǎng)絡(luò)優(yōu)化,組合優(yōu)化,整數(shù)

3、規(guī)劃,不確定規(guī)劃,多目標(biāo)規(guī)劃,目標(biāo)規(guī)劃,動態(tài)規(guī)劃,OR/MS/DS,優(yōu)化問題的一般形式,優(yōu)化問題三要素：決策變量；目標(biāo)函數(shù)；約束條件,可行解（滿足約束）與可行域（可行解的集合） 最優(yōu)解（取到最小大值的可行解）,給定一個函數(shù) f(x),尋找 x* 使得 f(x*)最小，即,其中,局部最優(yōu)解,全局最優(yōu)解,必要條件,最優(yōu)解在可行域邊界上取得時不能用無約束優(yōu)化方法求解,無約束優(yōu)化:最優(yōu)解的分類和條件,約束優(yōu)化的簡單分類, 線性規(guī)劃(LP) 目標(biāo)和約束均為線性函數(shù) 非線性規(guī)劃(NLP) 目標(biāo)或約束中存在非線性函數(shù) 二次規(guī)劃(QP) 目標(biāo)為二次函數(shù)、約束為線性 整數(shù)規(guī)劃(IP) 決策變量(全部或部分)為整

4、數(shù) 整數(shù)線性規(guī)劃(ILP)，整數(shù)非線性規(guī)劃(INLP) 純整數(shù)規(guī)劃(PIP), 混合整數(shù)規(guī)劃(MIP) 一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃,數(shù)學(xué)規(guī)劃,連 續(xù) 優(yōu) 化,離 散 優(yōu) 化,常用優(yōu)化軟件,1. LINDO/LINGO軟件 2. MATLAB優(yōu)化工具箱 3. EXCEL軟件的優(yōu)化功能 4. SAS(統(tǒng)計分析)軟件的優(yōu)化功能 5. 其他,MATLAB優(yōu)化工具箱能求解的優(yōu)化模型,The toolbox includes routines for many types of optimization including : Unconstrained nonlinear minimization

5、 Constrained nonlinear minimization, including goal attainment problems, minimax problems, and semi-infinite minimization problems Quadratic and linear programming Nonlinear least squares and curve-fitting Nonlinear system of equation solving Constrained linear least squares Sparse and structured la

6、rge-scale problems,MATLAB優(yōu)化工具箱能求解的優(yōu)化模型,優(yōu)化工具箱3.0 (MATLAB 7.0 R14),連續(xù)優(yōu)化,離散優(yōu)化,無約束優(yōu)化,非線性 極小 fminunc,非光滑(不可 微)優(yōu)化 fminsearch,非線性 方程(組) fzero fsolve,全局 優(yōu)化 暫缺,非線性 最小二乘 lsqnonlin lsqcurvefit,線性規(guī)劃 linprog,純0-1規(guī)劃 bintprog 一般IP(暫缺),非線性規(guī)劃 fmincon fminimax fgoalattain fseminf,上下界約束 fminbnd fmincon lsqnonlin lsqcu

7、rvefit,約束線性 最小二乘 lsqnonneg lsqlin,約束優(yōu)化,二次規(guī)劃 quadprog,LINDO 公司軟件產(chǎn)品簡要介紹,美國芝加哥(Chicago)大學(xué)的Linus Schrage教授于1980年前后開發(fā), 后來成立LINDO系統(tǒng)公司（LINDO Systems Inc.） 網(wǎng)址：,LINDO: Linear INteractive and Discrete Optimizer (V6.1) LINGO: Linear INteractive General Optimizer (V9.0) LINDO API: LINDO Application Programming

8、Interface (V2.0) Whats Best!: (SpreadSheet e.g. EXCEL) (V7.0),演示(試用)版、學(xué)生版、高級版、超級版、工業(yè)版、擴(kuò)展版 求解問題規(guī)模和選件不同,LINDO API,使用LINDO API可以建立求最佳解的應(yīng)用程序。LINDO API允許你將強(qiáng)大的線性、整數(shù)或非線性求解引擎掛入你已寫好的應(yīng)用程序中。 迅速、容易的應(yīng)用程序開發(fā) LINDO API 可以使你容易地將最佳化的功能整合到你自己開發(fā)的應(yīng)用程序中。LINDO API 附有完整的文件和范例幫助您迅速上手。 強(qiáng)大的求解引擎 LINDO API 提供的強(qiáng)大求解引擎包括針對線性、非線性 (

9、convex和nonconvex)，二次和整數(shù)的最佳化。 完整的求解程序 LINDO API 提供了你需要的彈性和功能，不管你的應(yīng)用程序是大或小，簡單或復(fù)雜。它包含了數(shù)十個程序(routine) 來公式化、求解、查詢和修改你的問題。 分析不可實(shí)行和無邊際模型(Infeasible and Unbounded Models) LINDO API 內(nèi)含工具可以找出導(dǎo)致模型無合理解或無邊際模型的原因。 建立因特網(wǎng)和企業(yè)內(nèi)部網(wǎng)絡(luò)的應(yīng)用程序 LINDO API 允許你建立因特網(wǎng)和企業(yè)內(nèi)部網(wǎng)絡(luò)的應(yīng)用程序可同時供多人使用,LINDO和LINGO軟件能求解的優(yōu)化模型,LINGO,LINDO,優(yōu)化模型,線性規(guī)劃

10、 (LP),非線性規(guī)劃 (NLP),二次規(guī)劃 (QP),連續(xù)優(yōu)化,整數(shù)規(guī)劃(IP),LINDO/LINGO軟件的求解過程,LP QP NLP IP 全局優(yōu)化(選) ILP IQP INLP,LINDO/LINGO預(yù)處理程序,線性優(yōu)化求解程序,非線性優(yōu)化求解程序,分枝定界管理程序,1. 確定常數(shù) 2. 識別類型,1. 單純形算法 2. 內(nèi)點(diǎn)算法(選),1、順序線性規(guī)劃法(SLP) 2、廣義既約梯度法(GRG) (選) 3、多點(diǎn)搜索(Multistart) (選),建模時需要注意的幾個基本問題,1、盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量 2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù) 如：盡量少使用

11、絕對值、符號函數(shù)、多個變量求最大/最小值、四舍五入、取整函數(shù)等 3、盡量使用線性模型，減少非線性約束和非線性變量的個數(shù)（如x/y 5 改為x5y） 4、合理設(shè)定變量上下界，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級要適當(dāng)(如小于103),需要掌握的幾個重要方面,1、LINDO: 正確閱讀求解報告（尤其要掌握敏感性分析） 2、LINGO： 掌握集合(SETS)的應(yīng)用； 正確閱讀求解報告； 正確理解求解狀態(tài)窗口； 學(xué)會設(shè)置基本的求解選項(OPTIONS) ； 掌握與外部文件的基本接口方法,DIFFERENCE BETWEEN LINGO AND LINDO,LINDO 用于求解線性規(guī)劃和二次

12、規(guī)劃 LINGO 還可用于非線性規(guī)劃求解，一些線性和非線性方程組的求解。 LINDO不提供數(shù)組或類似的數(shù)據(jù)結(jié)構(gòu)。 LINGO包含內(nèi)置的建模語言，允許以簡練、直觀的方式描述較大規(guī)模的優(yōu)化問題，模型中所需要的數(shù)據(jù)可以以一定格式保存在獨(dú)立的文件中。,文件類型描述,.lg4 LINGO格式的模型文件 二進(jìn)制格式文件 .lng 文本格式的模型文件（不保存字體、顏色、嵌入對象） .ldt LINGO數(shù)據(jù)文件 .ltf LINGO命令腳本文件 .lgr LINGO報告文件 .ltx LINDO格式的模型文件 .mps 數(shù)學(xué)規(guī)劃系統(tǒng)格式的模型文件,狀態(tài)窗口,Model Class: LP,QP,ILP,IQ,

13、PILP,PIQP,NLP,INLP,PINLP,State: Global Optimum Local Optimum Feasible Infeasible Unbounded Interrupted Undetermined,Solver Type: B-and-B 分支定界 Global 全局最優(yōu) Multistart 多個初始點(diǎn),LINGO軟件簡介,LINGO模型的優(yōu)點(diǎn) 包含了LINDO的全部功能 提供了靈活的編程語言（矩陣生成器） LINGO模型的構(gòu)成：5個段 目標(biāo)與約束段 集合段（SETS ENDSETS） 數(shù)據(jù)段（DATA ENDDATA） 初始段（INIT ENDINIT）

14、計算段(CALC ENDCALC) - LINGO9.0,企業(yè)生產(chǎn)計劃,4.1 奶制品的生產(chǎn)與銷售,空間層次,工廠級：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤為目標(biāo)制訂產(chǎn)品生產(chǎn)計劃；,車間級：根據(jù)生產(chǎn)計劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計劃.,時間層次,若短時間內(nèi)外部需求和內(nèi)部資源等不隨時間變化，可制訂單階段生產(chǎn)計劃，否則應(yīng)制訂多階段生產(chǎn)計劃.,例1 加工奶制品的生產(chǎn)計劃,50桶牛奶,時間480小時,至多加工100公斤A1,制訂生產(chǎn)計劃，使每天獲利最大,35元可買到1桶牛奶，買嗎？若買，每天最多買多少?,可聘用臨時工人，付出的工資最多是每小時幾元?,A

15、1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計劃？,每天：,問題,x1桶牛奶生產(chǎn)A1,x2桶牛奶生產(chǎn)A2,獲利 243x1,獲利 164 x2,原料供應(yīng),勞動時間,加工能力,決策變量,目標(biāo)函數(shù),每天獲利,約束條件,非負(fù)約束,線性規(guī)劃模型(LP),時間480小時,至多加工100公斤A1,基本模型,模型分析與假設(shè),比例性,可加性,連續(xù)性,xi對目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比,xi對約束條件的“貢獻(xiàn)”與xi取值成正比,xi對目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無關(guān),xi對約束條件的“貢獻(xiàn)”與xj取值無關(guān),xi取值連續(xù),A1,A2每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù),每桶牛奶加工A1,A2的數(shù)量, 時間是與各

16、自產(chǎn)量無關(guān)的常數(shù),A1,A2每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù),每桶牛奶加工A1,A2的數(shù)量,時間是與相互產(chǎn)量無關(guān)的常數(shù),加工A1,A2的牛奶桶數(shù)是實(shí)數(shù),線性規(guī)劃模型,模型求解,圖解法,約束條件,目標(biāo)函數(shù),z=c (常數(shù)) 等值線,在B(20,30)點(diǎn)得到最優(yōu)解,目標(biāo)函數(shù)和約束條件是線性函數(shù),可行域為直線段圍成的凸多邊形,目標(biāo)函數(shù)的等值線為直線,最優(yōu)解一定在凸多邊形的某個頂點(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 opti

17、mal 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,20桶牛奶生產(chǎn)A1, 30桶生產(chǎn)A2，利潤3360元。,結(jié)果解釋,Glo

18、bal 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,model: max = 72*x1+64*x2; mi

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

20、0000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000,最優(yōu)解下“資源”增加1單位時“效益”的增量,影子價格,35元可買到1桶牛奶，要買嗎?,35 48, 應(yīng)該買！,聘用臨時工人付出的工資最多每小時幾元?,2元！,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 72.00000 24.00000 8.00

21、0000 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,最優(yōu)解不變時目標(biāo)函數(shù)系數(shù)允許變化范圍,Options-General Solver-Dual Computations 敏感性分析 (“LINGO|Ranges” ),x1系數(shù)范圍(64

22、,96),x2系數(shù)范圍(48,72),A1獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計劃?,x1系數(shù)由24 3=72增加為303=90，在允許范圍內(nèi),不變！,(約束條件不變),結(jié)果解釋,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 Sid

23、e 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,影子價格有意義時約束右端的允許變化范圍,原料最多增加10,時間最多增加53,35元可買到1桶牛奶, 每天最多買多少?,最多買10桶!,(目標(biāo)函數(shù)不變),充分條件 !,例2 奶制品的生產(chǎn)銷售計劃,在例1基礎(chǔ)上深加工,制訂生產(chǎn)計劃，使每天凈利潤最大,30元可增加1桶牛奶，3元可增加1小

24、時時間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？,50桶牛奶, 480小時,至多100公斤A1,B1，B2的獲利經(jīng)常有10%的波動，對計劃有無影響？,每天銷售10公斤A1的合同必須滿足，對利潤有什么影響？,出售x1 kg A1, x2 kg A2，,x3 kg B1, x4 kg B2,原料供應(yīng),勞動時間,加工能力,決策變量,目標(biāo)函數(shù),利潤,約束條件,非負(fù)約束,x5 kg A1加工B1， x6 kg A2加工B2,附加約束,基本模型,模型求解,軟件實(shí)現(xiàn),LINGO,Global optimal solution found. Objective value: 3460.800 Total sol

25、ver 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.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000

26、000 44.00000 6 0.000000 32.00000,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 Pri

27、ce 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,結(jié)果解釋,每天銷售168 kgA2和19.2 kgB1， 利潤3460.8（元）,8桶牛奶加工成A1，42桶牛奶加工成A2， 將得到的24kgA1全部加工成B1,除加工能力外均為緊約束,結(jié)果解釋,Global optimal solution found. Objective value: 3460.800 Total solver

28、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.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000

29、44.00000 6 0.000000 32.00000,增加1桶牛奶使利潤增長3.1612=37.92,增加1小時時間使利潤增長3.26,30元可增加1桶牛奶，3元可增加1小時時間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？,投資150元增加5桶牛奶,可賺回189.6元。(大于增加時間的利潤增長),結(jié)果解釋,B1,B2的獲利有10%的波動，對計劃有無影響,Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Incr

30、ease 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 X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY ,B1獲利下降10%，超出X3 系數(shù)允許范圍,B2獲利上升10%，超出X4 系數(shù)允許范圍,波動對計劃有影響,生產(chǎn)計劃應(yīng)重新制訂：如將x3的系數(shù)改為39.6計算，會發(fā)現(xiàn)結(jié)果有很大變化。,Global

31、 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.000000 3.

32、160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000,結(jié)果解釋,x1從0開始增加一個單位時，最優(yōu)目標(biāo)函數(shù)值將減少1.68,Reduced Cost有意義也是有條件的(LINGO沒有給出),每天銷售10公斤A1的合同必須滿足，對利潤有什么影響？,公司利潤減少 1.6810=16.8（元）,最優(yōu)利潤為 3460.8 16.8 = 3444,奶制品的生產(chǎn)與銷售,由于產(chǎn)品利潤、加工時間等均為常數(shù)，可建立線性規(guī)劃模型.,線性規(guī)劃模型的三要素：決策變量、目標(biāo)函數(shù)、約束條件.,

33、用LINGO求解，輸出豐富，利用影子價格和靈敏性分析可對結(jié)果做進(jìn)一步研究.,建模時盡可能利用原始的數(shù)據(jù)信息，把盡量多的計算留給計算機(jī)去做（分析例2的建模）.,4.2 自來水輸送與貨機(jī)裝運(yùn),生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤最大?,運(yùn)輸問題,各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少?,其他費(fèi)用:450元/千噸,應(yīng)如何分配水庫供水量，公司才能獲利最多？,若水庫供水量都提高一倍，公司利潤可增加到多少？,例1 自來水輸送,收入：900元/千噸,支出,總供水量：160,確定送水方案使利潤最大,問題分析, 總需求量：1

34、20+180=300,總收入900160=144,000(元),收入：900元/千噸,其他費(fèi)用:450元/千噸,支出,引水管理費(fèi),其他支出450160=72,000(元),供應(yīng)限制,約束條件,需求限制,線性規(guī)劃模型(LP),目標(biāo)函數(shù),水庫i 向j 區(qū)的日供水量為 xij（x34=0）,決策變量,模型建立,確定3個水庫向4個小區(qū)的供水量,模型求解,部分結(jié)果： Objective Value: 24400.00 Variable Value Reduced Cost X11 0.000000 30.000000 X12 50.000000 0.000000 X13 0.000000 50.0000

35、00 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.000000 0.000000 X32 0.000000 10.000000 X33 10.000000 0.000000,利潤=總收入-其它費(fèi)用-引水管理費(fèi)=144000-72000-24400 = 47600（元）,引水管理費(fèi) 24400(元),目標(biāo)函數(shù),總供水量(320) 總需求量(300),每個水庫最大供水量都提高一倍,利潤 = 收入(90

36、0) 其它費(fèi)用(450) 引水管理費(fèi),供應(yīng)限制,B, C 類似處理,問題討論,確定送水方案使利潤最大,需求約束可以不變,求解,部分結(jié)果： 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 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0

37、.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000,運(yùn)輸問題,總利潤 88700（元）,供需平衡或不平衡,如何裝運(yùn)，使本次飛行獲利最大？,三個貨艙最大載重(噸),最大容積(米3),例2 貨機(jī)裝運(yùn),三個貨艙中實(shí)際載重必須與其最大載重成比例.,飛機(jī)平衡,WET=(10,16,8), VOL=(6800,8700,5300); w=(18,15,23,12), v=(480,650, 580,390), p=(3100,3800,3500,2850).,已知參數(shù),i=1,2,3,4（貨物） j=1,

38、2,3 (分別代表前、中、后倉) 貨艙j的重量限制WETj 體積限制VOLj 第i種貨物的重量wi，體積vi，利潤pi,貨機(jī)裝運(yùn),決策變量,xij-第i 種貨物裝入第j 個貨艙的重量(噸） i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉),模型假設(shè),每種貨物可以分割到任意小；,貨機(jī)裝運(yùn),每種貨物可以在一個或多個貨艙中任意分布；,多種貨物可以混裝，并保證不留空隙；,所給出的數(shù)據(jù)都是精確的，沒有誤差.,模型建立,貨艙容積,目標(biāo)函數(shù)(利潤),約束條件,貨機(jī)裝運(yùn),模型建立,貨艙重量,xij-第i 種貨物裝入第j 個貨艙的重量,約束條件,平衡要求,貨物供應(yīng),貨機(jī)裝運(yùn),模型建立,xij-第i

39、 種貨物裝入第j 個貨艙的重量,j,k=1,2,3; jk,!定義集合及變量; 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; enddata max=sum(wu(i):p(i)*sum(cang(j):x(i,j); for(wu(i):sum(cang(j):x(i,j)w(i); for(can

40、g(j):sum(wu(i):x(i,j)WET(j); for(cang(j):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,貨機(jī)裝運(yùn),LINGO程序,Global optimal solution found. Objective value: 121515.8 Total solver iterations: 12 Variable Value Reduced Cost

41、 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) 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(

42、 4, 3) 0.000000 650.0000,貨物2：前倉7,后倉8； 貨物3: 前倉3, 中倉13；貨物4: 中倉3。,貨機(jī)裝運(yùn),模型求解,最大利潤約121516元,貨物供應(yīng)點(diǎn) 貨艙需求點(diǎn),裝載平衡要求,如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛， 那么最優(yōu)的生產(chǎn)計劃應(yīng)作何改變？,例1 汽車廠生產(chǎn)計劃,汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量.,制訂月生產(chǎn)計劃，使工廠的利潤最大.,4.3 汽車生產(chǎn)與原油采購,設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1, x2, x3,汽車廠生產(chǎn)計劃,模型建立,線性規(guī)劃模型(LP),模型求解,3）模型中增加條件

43、：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 Surplus 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

44、；x1=64，x2=168等，計算函數(shù)值z，通過比較可能得到更優(yōu)的解.,但必須檢驗它們是否滿足約束條件. 為什么？,IP可用LINGO直接求解,整數(shù)規(guī)劃(Integer Programming,簡記IP),IP 的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z=632,max=2*x1+3*x2+4*x3; 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 sol

45、ver 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個子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：,方法1：分解為8個LP子模型,汽車廠生產(chǎn)計劃,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃.,x1,x2, x3=0 或 80,x1=80，x2= 150，x3=0，最優(yōu)值z=610,LINGO中對0-1變量的限定： bin(

46、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.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)計劃.,x1=0 或 80,最優(yōu)解同前,max=2*x1+3*x2+4*

47、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，簡記NLP）,若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃.,x1=0 或 80,最優(yōu)解同前.,一般地，整數(shù)規(guī)劃和非線性規(guī)劃的求解比線性規(guī)劃困難得多，特別是問題規(guī)模較大或者要求得到全局最優(yōu)解時.,汽車廠生產(chǎn)計劃,決策變量為整數(shù), 建立整數(shù)規(guī)劃模型.,求解整數(shù)規(guī)劃和非線性規(guī)劃比線性規(guī)劃困難得多 (即便用數(shù)學(xué)軟件) .,當(dāng)整數(shù)變量取值很大時, 可作為連續(xù)變量處理, 問題

48、簡化為線性規(guī)劃.,對于類似于“x=0 或 80”這樣的條件，通常引入0-1變量處理，盡量不用非線性規(guī)劃（特別是引入的整數(shù)變量個數(shù)較少時）.,應(yīng)如何安排原油的采購和加工 ？,例2 原油采購與加工,市場上可買到不超過1500噸的原油A： 購買量不超過500噸時的單價為10000元/噸； 購買量超過500噸但不超過1000噸時，超過500噸的 部分8000元/噸； 購買量超過1000噸時，超過1000噸的部分6000元/噸.,決策變量,目標(biāo)函數(shù),問題分析,利潤：銷售汽油的收入購買原油A的支出. 難點(diǎn)：原油A的購價與購買量的關(guān)系較復(fù)雜.,原油A的購買量,原油A, B生產(chǎn)汽油甲,乙的數(shù)量,c(x) 購買

49、原油A的支出,利潤(千元),c(x)如何表述？,原油供應(yīng),約束條件,x 500噸單價為10千元/噸； 500噸 x 1000噸，超過500噸的8千元/噸； 1000噸 x 1500噸，超過1000噸的6千元/噸.,目標(biāo)函數(shù),目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃； 對于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解； 想辦法將模型化簡，用現(xiàn)成的軟件求解.,汽油含原油A的比例限制,約束條件,x1 , x2 , x3 以價格10, 8, 6(千元/噸)采購A的噸數(shù),目標(biāo)函數(shù),只有當(dāng)以10千元/噸的價格購買x1=500(噸)時，才能以8千元/噸的價格購買x2,方法1,非線性規(guī)劃

50、模型，可以用LINGO求解,模型求解,x= x1+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 0; 2*x12 - 3*x22 0; x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0; x1 500; x2 500; x3

51、500; end,Local optimal solution found. Objective value: 4800.000 Total solver iterations: 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得

52、到的是局部最優(yōu)解,還能得到更好的解嗎？,用庫存的500噸原油A、500噸原油B生產(chǎn)汽油甲，不購買新的原油A，利潤為4800千元。,方法1：LINGO求解,計算全局最優(yōu)解 ： 選LINGO|Options菜單； 在彈出的選項卡中選擇“General Solver”； 然后找到選項“Use Global Solver”將其選中； 應(yīng)用或保存；重新求解。,Global optimal solution found. Objective value: 5000.000 Extended solver steps: 1 Total solver iterations: 43 Variable Value

53、 Reduced Cost X11 0.000000 0.000000 X21 0.000000 0.900000 X12 1500.000 0.000000 X22 1000.000 0.000000 X1 500.0000 0.000000 X2 500.0000 0.000000 X3 0.000000 0.000000 X 1000.000 0.000000,還有其他建模和求解方法嗎？,購買1000噸原油A，與庫存的500噸原油A和1000噸原油B一起，共生產(chǎn)2500噸汽油乙，利潤為5000千元 。,y1, y2 , y3=1 以價格10, 8, 6(千元/噸)采購A,增加約束,方法2

54、,0-1線性規(guī)劃模型, 可用LINGO求解.,y1,y2,y3 =0或1,購買1000噸原油A，與庫存的500噸原油A和1000噸原油B一起，生產(chǎn)汽油乙，利潤為5000千元 。,x1 , x2 , x3 以價格10, 8, 6(千元/噸)采購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

55、= z3b3+z4b4， z3+z4=1，z3, z4 0, c(x)= z3c(b3)+z4c(b4).,直接處理處理分段線性函數(shù)c(x),IP模型，LINGO求解，得到的結(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 ).,對于k=1,2,3,方法3: 直接處理分段線性函數(shù)，方法更具一般性.,分段函數(shù)無法直接用非線性規(guī)劃方法或軟件求解.,原油采購與加工,方法1: 增加約束化為非線性規(guī)劃,可以用LINGO 求解, 但可能得到的是局部最優(yōu)解.,方法2: 引入0-1變量, 化為線性規(guī)劃模型, 可用LINGO求解.,分派問題,4.4 接力隊選拔和選課策略,若干項任務(wù)分給一些候選人來完成，每人的專長不同,完成每項任務(wù)取得的效益或需要的資源不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少?,若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有相互制約關(guān)系，如何在滿足一定條件下作出抉擇，使得收益最大或成本最小?,討論:丁的蛙泳成績退步到115”2；戊的自由泳成績進(jìn)步到57”5, 組成接力隊的方案是否應(yīng)該調(diào)整？,如何選拔隊員組成4100米混合泳接