1、第四章第四章 數(shù)學規(guī)劃模型數(shù)學規(guī)劃模型 4.1 奶制品的生產(chǎn)與銷售奶制品的生產(chǎn)與銷售4.2 自來水輸送與貨機裝運自來水輸送與貨機裝運4.3 汽車生產(chǎn)與原油采購汽車生產(chǎn)與原油采購4.4 接力隊選拔和選課策略接力隊選拔和選課策略4.5 飲料廠的生產(chǎn)與檢修飲料廠的生產(chǎn)與檢修4.6 鋼管和易拉罐下料鋼管和易拉罐下料y數(shù)學規(guī)劃模型數(shù)學規(guī)劃模型 實際問題中實際問題中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決策變量決策變量f(x)目標函數(shù)目標函數(shù)gi(x) 0約束條件約束條件多元函數(shù)多元函數(shù)條件極值條件極值 決策變量個數(shù)決策變量個數(shù)n

2、和和約束條件個數(shù)約束條件個數(shù)m較大較大 最優(yōu)解在可行域最優(yōu)解在可行域的邊界上取得的邊界上取得 數(shù)數(shù)學學規(guī)規(guī)劃劃線性規(guī)劃線性規(guī)劃非線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃重點在模型的建立和結果的分析重點在模型的建立和結果的分析優(yōu)化模型與優(yōu)化軟件的重要意義( (最最) )優(yōu)化優(yōu)化: :在一定條件下在一定條件下, ,尋求使目標最大尋求使目標最大( (小小) )的決策的決策 最優(yōu)化是工程技術、經(jīng)濟管理、科學研究、社會生活中經(jīng)常遇到的問題, 如: 結構設計 資源分配 生產(chǎn)計劃 運輸方案解決優(yōu)化問題的手段解決優(yōu)化問題的手段 經(jīng)驗積累，主觀判斷 作試驗，比優(yōu)劣 建立數(shù)學模型(優(yōu)化模型)，求最優(yōu)策略(決策)(最最)

3、優(yōu)化優(yōu)化:在一定條件下在一定條件下,尋求使目標最大尋求使目標最大(小小)的決策的決策CUMCM賽題：約一半以上與優(yōu)化有關，需用軟件求解。(最)優(yōu)化理論是運籌學的基本內(nèi)容運籌學(OR: Operations/Operational Research)管理科學(MS: Management Science)決策科學(DS: Decision Science)優(yōu)化(Optimization), 規(guī)劃(Programming)無無約約束束優(yōu)優(yōu)化化線線性性規(guī)規(guī)劃劃非非線線性性規(guī)規(guī)劃劃網(wǎng)網(wǎng)絡絡優(yōu)優(yōu)化化組組合合優(yōu)優(yōu)化化整整數(shù)數(shù)規(guī)規(guī)劃劃不不確確定定規(guī)規(guī)劃劃多多目目標標規(guī)規(guī)劃劃目目標標規(guī)規(guī)劃劃動動態(tài)態(tài)規(guī)規(guī)劃劃O

4、R/MS/DS優(yōu)化問題的一般形式優(yōu)化問題三要素：決策變量；目標函數(shù)；約束決策變量；目標函數(shù)；約束條件條件可行解（滿足約束）與可行域（可行解的集合）最優(yōu)解（取到最小大值的可行解）約約束束條條件件njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min目標函數(shù)目標函數(shù)決策變量決策變量)(xfMinx給定一個函數(shù)給定一個函數(shù) f( (x),),尋找尋找 x* 使得使得 f( (x*)最小，即最小，即nTnxxxx),(21其中其中局部最優(yōu)解局部最優(yōu)解全局最優(yōu)解全局最優(yōu)解必要條件必要條件0),()(1*Txxnffxfx*f(x)xlxgo充分條件充分條件0)(, 0)(

5、*2*xfxfHessian陣陣nnjixxff22最優(yōu)解在可行域邊界上取得時不能用無約束優(yōu)化方法求解最優(yōu)解在可行域邊界上取得時不能用無約束優(yōu)化方法求解無約束優(yōu)化:最優(yōu)解的分類和條件約束優(yōu)化的簡單分類 線性規(guī)劃線性規(guī)劃(LP) 目標和約束均為線性函數(shù)目標和約束均為線性函數(shù) 非線性規(guī)劃非線性規(guī)劃(NLP) 目標或約束中存在非線性函數(shù)目標或約束中存在非線性函數(shù) 二次規(guī)劃二次規(guī)劃(QP) 目標為二次函數(shù)、約束為線性目標為二次函數(shù)、約束為線性 整數(shù)規(guī)劃整數(shù)規(guī)劃(IP) 決策變量決策變量(全部或部分全部或部分)為整數(shù)為整數(shù) 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃(ILP)，整數(shù)非線性規(guī)劃，整數(shù)非線性規(guī)劃(INLP)

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

7、mization including :Unconstrained nonlinear minimization Constrained nonlinear minimization, including goal attainment problems, minimax problems, and semi-infinite minimization problems Quadratic and linear programmingNonlinear least squares and curve-fitting Nonlinear system of equation solving Co

8、nstrained linear least squares Sparse and structured large-scale problemsMATLAB優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱優(yōu)化工具箱3.0 (MATLAB 7.0 R14)連續(xù)優(yōu)化連續(xù)優(yōu)化離散優(yōu)化離散優(yōu)化無約束優(yōu)化無約束優(yōu)化非線性非線性極小極小fminunc非光滑非光滑(不可不可微微)優(yōu)化優(yōu)化fminsearch非線性非線性方程方程(組組)fzerofsolve全局全局優(yōu)化優(yōu)化暫缺暫缺非線性非線性最小二乘最小二乘lsqnonlinlsqcurvefit線性規(guī)劃線性規(guī)劃linprog純純0-1規(guī)劃規(guī)劃 bintprog一般一

9、般IP(暫缺暫缺)非線性規(guī)劃非線性規(guī)劃fminconfminimaxfgoalattainfseminf上下界約束上下界約束fminbndfminconlsqnonlinlsqcurvefit約束線性約束線性最小二乘最小二乘lsqnonneglsqlin約束優(yōu)化約束優(yōu)化二次規(guī)劃二次規(guī)劃quadprogLINDO 公司軟件產(chǎn)品簡要介紹 美國芝加哥(Chicago)大學的Linus Schrage教授于1980年前后開發(fā), 后來成立LINDO系統(tǒng)公司（LINDO Systems Inc.） 網(wǎng)址：http:/LINDO: Linear INteractive and Discrete Optimi

10、zer (V6.1)LINGO: Linear INteractive General Optimizer (V9.0)LINDO API: LINDO Application Programming Interface (V2.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V7.0)演示(試用)版、學生版、高級版、超級版、工業(yè)版、擴展版求解問題規(guī)模和選件不同LINDO API使用LINDO API可以建立求最佳解的應用程序。LINDO API允許你將強大的線性、整數(shù)或非線性求解引擎掛入你已寫好的應用程序中。 迅速、容易的應用程序開發(fā)迅速、容易的應用程序開發(fā)

11、LINDO API 可以使你容易地將最佳化的功能整合到你自己開發(fā)的應用程序中。LINDO API 附有完整的文件和范例幫助您迅速上手。 強大的求解引擎強大的求解引擎LINDO API 提供的強大求解引擎包括針對線性、非線性 (convex和nonconvex)，二次和整數(shù)的最佳化。 完整的求解程序完整的求解程序LINDO API 提供了你需要的彈性和功能，不管你的應用程序是大或小，簡單或復雜。它包含了數(shù)十個程序(routine) 來公式化、求解、查詢和修改你的問題。 分析不可實行和無邊際模型分析不可實行和無邊際模型(Infeasible and Unbounded Models)LINDO A

12、PI 內(nèi)含工具可以找出導致模型無合理解或無邊際模型的原因。 建立因特網(wǎng)和企業(yè)內(nèi)部網(wǎng)絡的應用程序建立因特網(wǎng)和企業(yè)內(nèi)部網(wǎng)絡的應用程序LINDO API 允許你建立因特網(wǎng)和企業(yè)內(nèi)部網(wǎng)絡的應用程序可同時供多人使用LINDO和LINGO軟件能求解的優(yōu)化模型 LINGO LINDO優(yōu)化模型優(yōu)化模型線性規(guī)劃線性規(guī)劃(LP)非線性規(guī)劃非線性規(guī)劃(NLP)二次規(guī)劃二次規(guī)劃(QP)連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)LINDO/LINGO軟件的求解過程 LP QP NLP IP 全局優(yōu)化全局優(yōu)化(選選) ILP IQP INLP LINDO/LINGO預處理程序預處理程序線性優(yōu)化求解程序線性優(yōu)化求解程序非線性

13、優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序分枝定界管理程序1. 確定常數(shù)確定常數(shù)2. 識別類型識別類型1. 單純形算法單純形算法2. 內(nèi)點算法內(nèi)點算法(選選)1、順序線性規(guī)劃法、順序線性規(guī)劃法(SLP) 2、廣義既約梯度法、廣義既約梯度法(GRG) (選選) 3、多點搜索、多點搜索(Multistart) (選選) 建模時需要注意的幾個基本問題1、盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù) 如：盡量少使用絕對值、符號函數(shù)、多個變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個數(shù)（如x/y 5 改為x5y）4、

14、合理設定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級要適當(如小于103)需要掌握的幾個重要方面1、LINDO: 正確閱讀求解報告（尤其要掌握敏感性分析）2、LINGO： 掌握集合(SETS)的應用； 正確閱讀求解報告； 正確理解求解狀態(tài)窗口； 學會設置基本的求解選項(OPTIONS) ； 掌握與外部文件的基本接口方法DIFFERENCE BETWEEN LINGO AND LINDO LINDO 用于求解線性規(guī)劃和二次規(guī)劃 LINGO 還可用于非線性規(guī)劃求解，一些線性和非線性方程組的求解。 LINDO不提供數(shù)組或類似的數(shù)據(jù)結構。 LINGO包含內(nèi)置的建模語言，允許以簡練、直觀的

15、方式描述較大規(guī)模的優(yōu)化問題，模型中所需要的數(shù)據(jù)可以以一定格式保存在獨立的文件中。文件類型描述 .lg4 LINGO格式的模型文件 二進制格式文件 .lng 文本格式的模型文件（不保存字體、顏色、嵌入對象） .ldt LINGO數(shù)據(jù)文件 .ltf LINGO命令腳本文件 .lgr LINGO報告文件 .ltx LINDO格式的模型文件 .mps 數(shù)學規(guī)劃系統(tǒng)格式的模型文件狀態(tài)窗口Model Class:LP,QP,ILP,IQ,PILP,PIQP,NLP,INLP,PINLPState: Global Optimum Local Optimum Feasible Infeasible Unbou

16、nded Interrupted UndeterminedSolver Type: B-and-B 分支定界 Global 全局最優(yōu) Multistart 多個初始點LINGO軟件簡介LINGO模型的優(yōu)點模型的優(yōu)點 包含了LINDO的全部功能 提供了靈活的編程語言（矩陣生成器）LINGO模型的構成：模型的構成：5個段個段 目標與約束段 集合段（SETS ENDSETS） 數(shù)據(jù)段（DATA ENDDATA） 初始段（INIT ENDINIT） 計算段(CALC ENDCALC) - LINGO9.0企業(yè)生產(chǎn)計劃企業(yè)生產(chǎn)計劃4.1 奶制品的生產(chǎn)與銷售奶制品的生產(chǎn)與銷售 空間層次空間層次工廠級：根據(jù)

17、外部需求和內(nèi)部設備、人力、原料等工廠級：根據(jù)外部需求和內(nèi)部設備、人力、原料等條件，以最大利潤為目標制訂產(chǎn)品生產(chǎn)計劃；條件，以最大利潤為目標制訂產(chǎn)品生產(chǎn)計劃；車間級：根據(jù)生產(chǎn)計劃、工藝流程、資源約束及費車間級：根據(jù)生產(chǎn)計劃、工藝流程、資源約束及費用參數(shù)等，以最小成本為目標制訂生產(chǎn)批量計劃。用參數(shù)等，以最小成本為目標制訂生產(chǎn)批量計劃。時間層次時間層次若短時間內(nèi)外部需求和內(nèi)部資源等不隨時間變化，可若短時間內(nèi)外部需求和內(nèi)部資源等不隨時間變化，可制訂制訂單階段生產(chǎn)計劃單階段生產(chǎn)計劃，否則應制訂多階段生產(chǎn)計劃。，否則應制訂多階段生產(chǎn)計劃。本節(jié)課題本節(jié)課題例例1 加工奶制品的生產(chǎn)計劃加工奶制品的生產(chǎn)計劃1桶

18、牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時間時間480小時小時 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計劃，使每天獲利最大制訂生產(chǎn)計劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應否改變生產(chǎn)計劃？公斤，應否改變生產(chǎn)計劃？ 每天：每天：1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1

19、桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應原料供應 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標函數(shù)目標函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負約束非負約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時間時間480小時小時 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型分析與假設模型分析與假設 比比例例性性 可可加加性性 連續(xù)性連續(xù)性 xi對目標函數(shù)的對目標函數(shù)的“貢獻貢獻”與與xi取值取值成正比成正比 xi對約束條件

20、的對約束條件的“貢獻貢獻”與與xi取值取值成正比成正比 xi對目標函數(shù)的對目標函數(shù)的“貢獻貢獻”與與xj取值取值無關無關 xi對約束條件的對約束條件的“貢獻貢獻”與與xj取值取值無關無關 xi取值連續(xù)取值連續(xù) A1,A2每公斤的獲利是與各每公斤的獲利是與各自產(chǎn)量無關的常數(shù)自產(chǎn)量無關的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量和的數(shù)量和時間是與各自產(chǎn)量無關的常數(shù)時間是與各自產(chǎn)量無關的常數(shù)A1,A2每公斤的獲利是與相每公斤的獲利是與相互產(chǎn)量無關的常數(shù)互產(chǎn)量無關的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量和的數(shù)量和時間是與相互產(chǎn)量無關的常數(shù)時間是與相互產(chǎn)量無關的常數(shù)加工加工A1,A2的牛

21、奶桶數(shù)是實數(shù)的牛奶桶數(shù)是實數(shù) 線性規(guī)劃模型線性規(guī)劃模型模型求解模型求解 圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目標目標函數(shù)函數(shù) Z=0Z=2400Z=3600z=c (常數(shù)常數(shù)) 等值線等值線c在在B(20,30)點得到最優(yōu)解點得到最優(yōu)解目標函數(shù)和約束條件是線性函數(shù)目標函數(shù)和約束條件是線性函數(shù) 可行域為直線段圍成的凸多邊形可行域為直線段圍成的凸多邊形 目標函數(shù)的等值線為直線目標函數(shù)的等值線

22、為直線 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個頂點取得。形的某個頂點取得。 模型求解模型求解 軟件實現(xiàn)軟件實現(xiàn) LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.0000

23、00 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤，利潤3360元。元。 結果解釋結果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.0000

24、00 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結果解釋結果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000

25、 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時單位時“效益效益”的增的增量量 原料增加原料增加1單位單位, 利潤增長利潤增長48 時間增加時間增加1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 48, 應該買！應該買！ 聘用臨時工人付出的工資最多每小時幾元？聘用

26、臨時工人付出的工資最多每小時幾元？ 2元！元！RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10

27、.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最優(yōu)解不變時目標函最優(yōu)解不變時目標函數(shù)系數(shù)允許變化范圍數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(48,72) A1獲利增加到獲利增加到 30元元/千克，應否改變生產(chǎn)計劃千克，應否改變生產(chǎn)計劃 x1系數(shù)由系數(shù)由24 3=72增加增加為為30 3=90，在在允許范圍內(nèi)允許范圍內(nèi) 不變！不變！(約束條件不變約束條件不變)結果解釋結果解釋

28、 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480

29、.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子價格有意義時約束右端的允許變化范圍影子價格有意義時約束右端的允許變化范圍 原料最多增加原料最多增加10 時間最多增加時間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最多買最多買10桶桶!(目標函數(shù)不變目標函數(shù)不變)例例2 奶制品的生產(chǎn)銷售計劃奶制品的生產(chǎn)銷售計劃 在例在例1基礎上深加工基礎上深加工1桶桶牛奶牛奶 3千克千克A1 12小時小時 8小時小時 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公斤公斤 0.8

30、千克千克B12小時小時,3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克B22小時小時,3元元1千克千克獲利獲利32元元/千克千克 制訂生產(chǎn)計劃，使每天凈利潤最大制訂生產(chǎn)計劃，使每天凈利潤最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時時間，應否投小時時間，應否投資？現(xiàn)投資資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？50桶牛奶桶牛奶, 480小時小時 至多至多100公斤公斤A1 B1，B2的獲利經(jīng)常有的獲利經(jīng)常有10%的波動，對計劃有無影響？的波動，對計劃有無影響？1桶桶牛奶牛奶 3千克千克 A1 12小時小時 8小時小時 4千克千克 A2 或或獲利獲利24

31、元元/千克千克 獲利獲利16元元/kg 0.8千克千克 B12小時小時,3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克 B22小時小時,3元元1千克千克獲利獲利32元元/千克千克 出售出售x1 千克千克 A1, x2 千克千克 A2， X3千克千克 B1, x4千克千克 B2原料原料供應供應 勞動勞動時間時間 加工能力加工能力 決策決策變量變量 目標目標函數(shù)函數(shù) 利潤利潤約束約束條件條件非負約束非負約束 0,61xx x5千克千克 A1加工加工B1， x6千克千克 A2加工加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(46

32、56251xxxxxx10051 xx附加約束附加約束 5380 x.x64750 x.x 模型求解模型求解 軟件實現(xiàn)軟件實現(xiàn) LINDO 6.1 5043) 26251xxxx48022)(2)(4)3656251xxxxxx OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000

33、 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2600334) 26521xxxx44804624) 36521xxxxDO RANGE (SENSITIVITY) ANALYSIS? No OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED C

34、OST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2結果解釋結果解釋每

35、天銷售每天銷售168 千克千克A2和和19.2 千克千克B1， 利潤利潤3460.8（元）（元）8桶牛奶加工成桶牛奶加工成A1，42桶桶牛奶加工成牛奶加工成A2，將得到的將得到的24千克千克A1全部全部加工成加工成B1 除加工能力外均除加工能力外均為緊約束為緊約束結果解釋結果解釋 OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.0

36、00000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000增加增加1桶牛奶使利潤增桶牛奶使利潤增長長3.1612=37.925043)26251xxxx600334) 26521xxxx4增加增加1小時時間使利小時時間使利潤增長潤增長3.26 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時時

37、間，小時時間，應否投資？現(xiàn)投資應否投資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？投資投資150元增加元增加5桶牛奶，桶牛奶，可賺回可賺回189.6元。（大于元。（大于增加時間的利潤增長）增加時間的利潤增長）結果解釋結果解釋B1,B2的獲利有的獲利有10%的波動，對計劃有無影響的波動，對計劃有無影響 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INF

38、INITY 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 DO RANGE (SENSITIVITY) ANALYSIS? YesB1獲利下降獲利下降10%，超，超出出X3 系數(shù)允許范圍系數(shù)允許范圍B2獲利上升獲利上升10%，超，超出出X4 系數(shù)允許范圍系數(shù)允許范圍波動對計劃有影響波動對計劃有影響生產(chǎn)計劃應重新制訂：如將生產(chǎn)計劃應

39、重新制訂：如將x3的系數(shù)改為的系數(shù)改為39.6計算，會發(fā)現(xiàn)結果有很大變化。計算，會發(fā)現(xiàn)結果有很大變化。 4.2 自來水輸送與貨機裝運自來水輸送與貨機裝運生產(chǎn)、生活物資從若干供應點運送到一些需求點，生產(chǎn)、生活物資從若干供應點運送到一些需求點，怎樣安排輸送方案使運費最小，或利潤最大；怎樣安排輸送方案使運費最小，或利潤最大；運輸問題運輸問題各種類型的貨物裝箱，由于受體積、重量等限制，各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。其他費用其他費用: :450元元/千噸千噸 應如何分配水庫供水量，公司才能獲利最多？應如何分

40、配水庫供水量，公司才能獲利最多？ 若水庫供水量都提高一倍，公司利潤可增加到多少？若水庫供水量都提高一倍，公司利潤可增加到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費引水管理費例例1 自來水輸送自來水輸送收入：收入：900元元/千噸千噸 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾。?0；40水庫供水量水庫供水量(千噸千噸)小區(qū)基本用水量小區(qū)基本用水量(千噸千噸)小區(qū)額外用水量小區(qū)額外用水量(千噸千噸)（以天計）（以天計）總供水量：總供水量：160確定送水方案確定送水方案

41、使利潤最大使利潤最大問題問題分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾。?0；40 總需求量總需求量(300)每個水庫最大供水量都提高一倍每個水庫最大供水量都提高一倍利潤利潤 = 收入收入(900) 其它費用其它費用( (450) 引水管理費引水管理費利潤利潤(元元/千噸千噸)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZMax供應供應限制限制B, C 類似處理類似處

42、理50:A14131211xxxx10014131211xxxx問題討論問題討論 確定送水方案確定送水方案使利潤最大使利潤最大需求約束可以不變需求約束可以不變求解求解 OBJECTIVE FUNCTION VALUE 1) 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

43、 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 這類問題一般稱為這類問題一般稱為“運輸問題運輸問題”(Transportation Problem)總利潤總利潤 88700（元）（元） A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030如何如何裝運，裝運，使本次飛行使本次飛行獲利最大？獲利最大？ 三個貨艙三個貨艙最大最大載載重重( (噸噸),),最大容積最

44、大容積( (米米3 3) ) 例例2 貨機裝運貨機裝運 重量（噸）重量（噸）空間空間( 米米3/噸）噸）利潤（元利潤（元/噸）噸）貨物貨物1184803100貨物貨物2156503800貨物貨物3235803500貨物貨物4123902850三個貨艙中實際載重必須與其最大三個貨艙中實際載重必須與其最大載載重成比例重成比例 前倉：前倉：10；6800中倉：中倉：16；8700后倉：后倉：8；5300飛機平衡飛機平衡決策決策變量變量 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量( (噸）噸）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉分別代表前、中、后倉)模

45、型假設模型假設 每種貨物可以分割到任意??；每種貨物可以分割到任意小；貨機裝運貨機裝運每種貨物可以在一個或多個貨艙中任意分布；每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 模型建立模型建立 貨艙貨艙容積容積 目標目標函數(shù)函數(shù)( (利潤利潤)約束約束條件條件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx53003905806504804333

46、2313xxxx貨機裝運貨機裝運模型建立模型建立 貨艙貨艙重量重量 1041312111xxxx1642322212xxxx843332313xxxx10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量約束約束條件條件平衡平衡要求要求 81610433323134232221241312111xxxxxxxxxxxx貨物貨物供應供應 18131211xxx15232221xxx23333231xxx12434241xxx貨機裝運貨機裝運模型建立模型建立 10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j

47、 個貨艙的重量個貨艙的重量 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.000000 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 6

48、50.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 貨物貨物2：前倉：前倉10, ,后倉后倉5； 貨物貨物3: : 中倉中倉13, 后倉后倉3；貨物貨物4: : 中倉中倉3。貨機裝運貨機裝運模型求解模型求解 最大利潤約最大利潤約121516元元貨物貨物供應點供應點貨艙貨艙需求點需求點平衡要求平衡要求運輸運輸問題問題運輸問題的擴展運輸問題的擴展 如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)8080輛，輛， 那么最優(yōu)的生產(chǎn)計劃應作何改變？那么最優(yōu)的生產(chǎn)計劃應作何改變？例例1 汽車廠生產(chǎn)計劃汽車廠生產(chǎn)計劃 汽車廠生產(chǎn)

49、三種類型的汽車，已知各類型每輛車對鋼汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量。材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量。 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材（噸）鋼材（噸） 1.5 3 5 600勞動時間（小時）勞動時間（小時） 280 250 400 60000利潤（萬元）利潤（萬元） 2 3 4 制訂月生產(chǎn)計劃，使工廠的利潤最大。制訂月生產(chǎn)計劃，使工廠的利潤最大。4.3 汽車生產(chǎn)與原油采購汽車生產(chǎn)與原油采購設每月生產(chǎn)小、中、大型設每月生產(chǎn)小、中、大型汽車的數(shù)量分別為汽車的數(shù)量分別為x1, x2, x3321432xxxzMax6

50、00535 . 1.321xxxts60000400250280321xxx0,321xxx汽車廠生產(chǎn)計劃汽車廠生產(chǎn)計劃 模型建立模型建立 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材鋼材 1.5 3 5 600時間時間 280 250 400 60000利潤利潤 2 3 4 線性線性規(guī)劃規(guī)劃模型模型(LP)模型模型求解求解 3） 模型中增加條件：模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。均為整數(shù)，重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.00000

51、0 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結果為小數(shù)，結果為小數(shù)，怎么辦？怎么辦？1）舍去小數(shù)：?。┥崛バ?shù)：取x1=64，x2=167，算出目標函數(shù)值，算出目標函數(shù)值z=629，與，與LP最優(yōu)值最優(yōu)值632.2581相差不大。相差不大。2）試探：如取）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數(shù)等，計算函數(shù)值值z，通過比較可能得到更優(yōu)的解。，通過比較可能得到更優(yōu)的解。

52、但必須檢驗它們是否滿足約束條件。為什么？但必須檢驗它們是否滿足約束條件。為什么？IP可用可用LINDO直接求解直接求解整數(shù)規(guī)劃整數(shù)規(guī)劃( (Integer Programming, ,簡記簡記IP) )“gin 3”表示表示“前前3個變量個變量為整數(shù)為整數(shù)”，等價于：，等價于：gin x1gin x2gin x3 IP 的最優(yōu)解的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值，最優(yōu)值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE 1) 632.0

53、000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 321432xxxzMax600535 . 1.321xxxts60000400250280321xxx為非負整數(shù)321,xxx模型求解模型求解 IP 結果輸出結果輸出其中其中3個個子模型應子模型應去掉，然后去掉，然后逐一求解，比較目標函數(shù)值，逐一求解，比較目標函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：再加上整數(shù)約束，得最優(yōu)解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321x

54、xx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0,321xxx方法方法1：分解為：分解為8個個LP子模型子模型 汽車廠生產(chǎn)計劃汽車廠生產(chǎn)計劃 若生產(chǎn)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計劃。輛，求生產(chǎn)計劃。321432xxxzMax600535 . 1.321xxxts60000400250280321xxxx1, ,x2, x3=0 或或 80 x1=80，x2= 150，x3=0，最優(yōu)值，最優(yōu)值z=610LINDO中對中對0-1變量的限定：變量的限定：int y1int y2int y3 方法方法

55、2：引入引入0-1變量，化為整數(shù)規(guī)劃變量，化為整數(shù)規(guī)劃 M為大的正數(shù)，為大的正數(shù)，可取可取1000 OBJECTIVE FUNCTION VALUE 1) 610.0000VARIABLE 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)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計劃。輛，求生產(chǎn)計劃。x1=0 或 8

56、0 x2=0 或 80 x3=0 或 801 , 0,80,11111yyxMyx1 , 0,80,22222yyxMyx1 , 0,80,33333yyxMyx最優(yōu)解同前最優(yōu)解同前 NLP雖然可用現(xiàn)成的數(shù)學軟件求解雖然可用現(xiàn)成的數(shù)學軟件求解( (如如LINGO, , MATLAB) )，但是其結果常依賴于初值的選擇。，但是其結果常依賴于初值的選擇。 方法方法3：化為非線性規(guī)劃化為非線性規(guī)劃 非線性規(guī)劃（非線性規(guī)劃（Non- Linear Programming，簡記，簡記NLP） 實踐表明，本例僅當初值非常接近上面方法算出實踐表明，本例僅當初值非常接近上面方法算出的最優(yōu)解時，才能得到正確的結

57、果。的最優(yōu)解時，才能得到正確的結果。 若生產(chǎn)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計劃。輛，求生產(chǎn)計劃。 x1=0 或 80 x2=0 或 80 x3=0 或 800)80(11xx0)80(22xx0)80(33xx應如何安排原油的采購和加工應如何安排原油的采購和加工 ？ 例例2 原油采購與加工原油采購與加工 市場上可買到不超過市場上可買到不超過1500噸的原油噸的原油A： 購買量不超過購買量不超過500噸時的單價為噸時的單價為10000元元/ /噸；噸； 購買量超過購買量超過500噸但不超過噸但不超過1000噸時，超過噸時，超過500噸的噸的 部分部分8000元元

58、/ /噸；噸； 購買量超過購買量超過1000噸時，超過噸時，超過1000噸的部分噸的部分6000元元/ /噸。噸。 售價售價4800元元/噸噸 售價售價5600元元/噸噸庫存庫存500噸噸 庫存庫存1000噸噸 汽油甲汽油甲(A 50%) 原油原油A 原油原油B 汽油乙汽油乙 (A 60%) 決策決策變量變量 目標目標函數(shù)函數(shù)問題問題分析分析 利潤：銷售汽油的收入利潤：銷售汽油的收入 - - 購買原油購買原油A的支出的支出 難點：原油難點：原油A的購價與購買量的關系較復雜的購價與購買量的關系較復雜)()(6 . 5)( 8 . 422122111xcxxxxzMax甲甲(A 50%) A B

59、乙乙(A 60%) 購買購買xx11x12x21x224.8千元千元/噸噸 5.6千元千元/噸噸原油原油A的購買量的購買量, ,原油原油A, B生產(chǎn)生產(chǎn)汽油汽油甲甲,乙的數(shù)量乙的數(shù)量c(x) 購買原油購買原油A的支出的支出利潤利潤(千元千元)c(x)如何表述？如何表述？原油供應原油供應 約束約束條件條件xxx500121110002221 xx1500 x500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc x 500噸單價為噸單價為10千千元元/ /噸；噸； 500噸噸 x 1000噸，超過噸，超過500噸的噸的8千千元元/ /噸；噸；100

60、0噸噸 x 1500噸，超過噸，超過1000噸的噸的6千千元元/ /噸。噸。 目標目標函數(shù)函數(shù)購買購買x A B x11x12x21x22庫存庫存500噸噸 庫存庫存1000噸噸 目標函數(shù)中目標函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；不是線性函數(shù)，是非線性規(guī)劃； 對于用分段函數(shù)定義的對于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟，一般的非線性規(guī)劃軟件也難以輸入和求解；件也難以輸入和求解； 想辦法將模型化簡，用現(xiàn)成的軟件求解。想辦法將模型化簡，用現(xiàn)成的軟件求解。 汽油含原油汽油含原油A的比例限制的比例限制 5 . 0211111 xxx6 . 0221212 xxx2111xx 221232