數(shù)學(xué)建模-初等模型講解

1、數(shù)學(xué)建模講座（2015年11月）線性規(guī)劃(xin xn u hu)與非線性規(guī)劃(xin xn u hu)（基于Lindo/Lingo）共七十八頁(yè)簡(jiǎn)要(jinyo)提綱 優(yōu)化模型簡(jiǎn)介 LINDO公司的主要軟件產(chǎn)品及功能(gngnng)簡(jiǎn)介 LINDO軟件的使用簡(jiǎn)介 LINGO軟件的使用簡(jiǎn)介 建模與求解實(shí)例（結(jié)合軟件使用）共七十八頁(yè)優(yōu)化模型(mxng) 實(shí)際問(wèn)題(wnt)中的優(yōu)化模型x決策變量f(x)目標(biāo)函數(shù)gi(x)0約束條件數(shù)學(xué)規(guī)劃線性規(guī)劃(LP)二次規(guī)劃(QP)非線性規(guī)劃(NLP)純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃共七十八頁(yè)LINDO

2、 公司(n s)軟件產(chǎn)品簡(jiǎn)要介紹 美國(guó)芝加哥(Chicago)大學(xué)的Linus Schrage教授于1980年前后開發(fā), 后來(lái)成立(chngl) LINDO系統(tǒng)公司（LINDO Systems Inc.）， 網(wǎng)址： LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINGO: Linear INteractive General Optimizer (V8.0)LINDO API: LINDO Application Programming Interface (V2.0)Whats Best!: (SpreadSheet e.g.

3、 EXCEL) (V7.0)演示(試用)版、學(xué)生版、高級(jí)版、超級(jí)版、工業(yè)版、擴(kuò)展版 （求解問(wèn)題規(guī)模和選件不同）共七十八頁(yè)LINDO和LINGO軟件(run jin)能求解的優(yōu)化模型 LINGO LINDO優(yōu)化模型(mxng)線性規(guī)劃(LP)非線性規(guī)劃(NLP)二次規(guī)劃(QP)連續(xù)優(yōu)化整數(shù)規(guī)劃(IP)共七十八頁(yè) LP QP NLP IP 全局(qunj)優(yōu)化(選) ILP IQP INLP LINDO/LINGO軟件的求解(qi ji)過(guò)程 LINDO/LINGO預(yù)處理程序線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序1. 確定常數(shù)2. 識(shí)別類型1. 單純形算法2. 內(nèi)點(diǎn)算法(選)1、順序線

4、性規(guī)劃法(SLP) 2、廣義既約梯度法(GRG) (選) 3、多點(diǎn)搜索(Multistart) (選) 共七十八頁(yè)建模時(shí)需要注意的幾個(gè)(j )基本問(wèn)題 1、盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量(binling)2、盡量使用光滑優(yōu)化，減少非光滑約束的個(gè)數(shù) 如：盡量少使用絕對(duì)值、符號(hào)函數(shù)、多個(gè)變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個(gè)數(shù) （如x/y 5 改為x5y）4、合理設(shè)定變量上下界，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級(jí)要適當(dāng) (如小于103)共七十八頁(yè)需要掌握的幾個(gè)重要(zhngyo)方面1、LINDO: 正確閱讀求解報(bào)告（尤

5、其要掌握敏感性分析(fnx)）2、LINGO： 掌握集合(SETS)的應(yīng)用；正確閱讀求解報(bào)告；正確理解求解狀態(tài)窗口； 學(xué)會(huì)設(shè)置基本的求解選項(xiàng)(OPTIONS) ； 掌握與外部文件的基本接口方法共七十八頁(yè)例1 加工奶制品的生產(chǎn)(shngchn)計(jì)劃1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶(ni ni) 時(shí)間480小時(shí) 至多加工100公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到1桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：共七十八頁(yè)1

6、桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶(ni ni)生產(chǎn)A1 x2桶牛奶(ni ni)生產(chǎn)A2 獲利 243x1 獲利 164 x2 原料供應(yīng) 勞動(dòng)時(shí)間 加工能力 決策變量 目標(biāo)函數(shù) 每天獲利約束條件非負(fù)約束 線性規(guī)劃模型(LP)時(shí)間480小時(shí) 至多加工100公斤A1 50桶牛奶 每天共七十八頁(yè)模型(mxng)求解 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED CO

7、ST 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.000000 4) 40.000000 0.000000 NO. ITERATIONS= 220桶牛奶生產(chǎn)(shngchn)A1, 30桶生產(chǎn)A2，利潤(rùn)3360元。 共七十八頁(yè)模型(mxng)求解 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endLingoLindoModel:max =72*x1+64*x2;x1+x

8、250;12*x1+8*x2480;3*x1100;end共七十八頁(yè)模型(mxng)求解 reduced cost值表示當(dāng)該非基變量增加一個(gè)單位時(shí)（其他(qt)非基變量保持不變）目標(biāo)函數(shù)減少的量(對(duì)max型問(wèn)題) 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.000000 4) 40.00

9、0000 0.000000 NO. ITERATIONS= 2也可理解為：為了使該非基變量變成基變量，目標(biāo)函數(shù)中對(duì)應(yīng)系數(shù)應(yīng)增加的量共七十八頁(yè) 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.000000 4) 40.000000 0.000000原料(yunlio)無(wú)剩余時(shí)間(shjin)無(wú)

10、剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三種資源“資源” 剩余為零的約束為緊約束（有效約束） 結(jié)果解釋 共七十八頁(yè) 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.000000 4) 40.000000 0.0000

11、00結(jié)果(ji gu)解釋 最優(yōu)解下“資源(zyun)”增加1單位時(shí)“效益”的增量 原料增1單位, 利潤(rùn)增48 時(shí)間加1單位, 利潤(rùn)增2 能力增減不影響利潤(rùn)影子價(jià)格 35元可買到1桶牛奶，要買嗎？35 ”（或“=”（或“=”）功能相同變量與系數(shù)間可有空格(甚至回車), 但無(wú)運(yùn)算符變量名以字母開頭，不能超過(guò)8個(gè)字符變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件行號(hào)(行名)自動(dòng)產(chǎn)生或人為定義。行名以“）”結(jié)束行中注有“!”符號(hào)的后面部分為注釋(zhsh)。如: ! Its Comment.在模型的任何地方都可以用“TITLE” 對(duì)模型命名（最多72個(gè)字符）

12、，如： TITLE This Model is only an Example共七十八頁(yè)變量不能出現(xiàn)在一個(gè)約束條件的右端表達(dá)式中不接受括號(hào)“( )”和逗號(hào)“,”等任何符號(hào), 例: 400(X1+X2)需寫為400X1+400X2表達(dá)式應(yīng)化簡(jiǎn)，如2X1+3X2- 4X1應(yīng)寫成 -2X1+3X2缺省假定所有變量非負(fù)；可在模型的“END”語(yǔ)句后用“FREE name”將變量name的非負(fù)假定取消可在 “END”后用“SUB” 或“SLB” 設(shè)定變量上下界 例如： “sub x1 10”的作用(zuyng)等價(jià)于“x1=10” 但用“SUB”和“SLB”表示的上下界約束不計(jì)入模型的約束，也不能給出其松

13、緊判斷和敏感性分析。14. “END”后對(duì)0-1變量說(shuō)明：INT n 或 INT name15. “END”后對(duì)整數(shù)變量說(shuō)明：GIN n 或 GIN name使用(shyng)LINDO的一些注意事項(xiàng)共七十八頁(yè)二次規(guī)劃(guhu)(QP)問(wèn)題LINDO可求解二次規(guī)劃(QP)問(wèn)題，但輸入方式較復(fù)雜(fz)，因?yàn)樵贚INDO中不許出現(xiàn)非線性表達(dá)式需要為每一個(gè)實(shí)際約束增加一個(gè)對(duì)偶變量（LAGRANGE乘子），在實(shí)際約束前增加有關(guān)變量的一階最優(yōu)條件，轉(zhuǎn)化為互補(bǔ)問(wèn)題“END”后面使用QCP命令指明實(shí)際約束開始的行號(hào)，然后才能求解建議總是用LINGO解QP注意對(duì)QP和IP: 敏感性分析意義不大共七十八頁(yè)狀

14、態(tài)(zhungti)窗口（LINDO Solver Status） 當(dāng)前狀態(tài)：已達(dá)最優(yōu)解迭代次數(shù)：18次約束不滿足的“量”(不是(b shi)“約束個(gè)數(shù)”)：0當(dāng)前的目標(biāo)值：94最好的整數(shù)解：94整數(shù)規(guī)劃的界：93.5分枝數(shù)：1所用時(shí)間：0.00秒（太快了，還不到0.005秒）刷新本界面的間隔:1(秒)共七十八頁(yè)選項(xiàng)設(shè)置(shzh) Preprocess：預(yù)處理(生成割平面)； Preferred Branch：優(yōu)先的分枝方式： “Default”（缺省方式）、“Up”（向上取整優(yōu)先）、“Down”（向下取整優(yōu)先）； IP Optimality Tol：IP最優(yōu)值允許的誤差上限（一個(gè)百分?jǐn)?shù)，如

15、5%即0.05）； IP Objective Hurdle：IP目標(biāo)函數(shù)的籬笆值，即只尋找比這個(gè)值更優(yōu)最優(yōu)解（如當(dāng)知道當(dāng)前模型(mxng)的某個(gè)整數(shù)可行解時(shí)，就可以設(shè)置這個(gè)值）； IP Var Fixing Tol：固定一個(gè)整數(shù)變量取值所依據(jù)的一個(gè)上限（如果一個(gè)整數(shù)變量的判別數(shù)（REDUCED COST）的值很大，超過(guò)該上限，則以后求解中把該整數(shù)變量固定下來(lái)）。Nonzero Limit：非零系數(shù)的個(gè)數(shù)上限；Iteration Limit：最大迭代步數(shù)；Initial Contraint Tol：約束的初始誤差上限；Final Contraint Tol：約束的最后誤差上限；Entering

16、Var Tol：進(jìn)基變量的REDUCED COST的誤差限；Pivot Size Tol：旋轉(zhuǎn)元的誤差限共七十八頁(yè)LINGO軟件(run jin)簡(jiǎn)介目標(biāo)與約束段 集合(jh)段（SETS ENDSETS） 數(shù)據(jù)段（DATA ENDDATA）初始段（INIT ENDINIT）LINGO模型的構(gòu)成：4個(gè)段LINGO模型的優(yōu)點(diǎn)包含了LINDO的全部功能提供了靈活的編程語(yǔ)言（矩陣生成器）共七十八頁(yè)LINGO模型(mxng) 例：選址問(wèn)題某公司有6個(gè)建筑工地，位置坐標(biāo)為(ai, bi) (單位：公里(n l),水泥日用量di (單位：噸）假設(shè)：料場(chǎng)和工地之間有直線道路共七十八頁(yè)用例中數(shù)據(jù)(shj)計(jì)算

17、，最優(yōu)解為總噸公里數(shù)為136.2線性規(guī)劃(xin xn u hu)模型決策變量：ci j (料場(chǎng)j到工地i的運(yùn)量）12維共七十八頁(yè)選址(xun zh)問(wèn)題：NLP2）改建兩個(gè)新料場(chǎng)，需要確定新料場(chǎng)位置(xj,yj)和運(yùn)量(yn lin)cij ，在其它條件不變下使總噸公里數(shù)最小。決策變量：ci j，(xj,yj)16維非線性規(guī)劃模型共七十八頁(yè)LINGO模型(mxng)的構(gòu)成：4個(gè)段集合(jh)段（SETS ENDSETS）數(shù)據(jù)段（DATA ENDDATA）初始段（INIT ENDINIT） 目標(biāo)與約束段 局部最優(yōu)：89.8835(噸公里 ) LP：移到數(shù)據(jù)段共七十八頁(yè)邊界(binji)共七十八

18、頁(yè)集合(jh)的類型 集合 派生集合 基本集合 稀疏(xsh)集合 稠密集合 元素列表法 元素過(guò)濾法 直接列舉法 隱式列舉法setname /member_list/ : attribute_list;setname(parent_set_list) /member_list/ : attribute_list;SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETSSETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | &

19、2 #GT# &1: BENEFIT, MATCH;ENDSETS共七十八頁(yè)集合(jh)元素的隱式列舉類型隱式列舉格式示例示例集合的元素?cái)?shù)字型1.n1.51, 2, 3, 4, 5字符-數(shù)字型stringM.stringNCar101.car208Car101, car102, , car208星期型dayM.dayNMON.FRIMON, TUE, WED, THU, FRI月份型monthM.monthNOCT.JANOCT, NOV, DEC, JAN年份-月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001, NOV2001, DEC2001,

20、JAN2002共七十八頁(yè)運(yùn)算符的優(yōu)先級(jí) 優(yōu)先級(jí)運(yùn)算符最高#NOT# （負(fù)號(hào)）* /+ （減法）#EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR#最低(=)三類運(yùn)算符： 算術(shù)(sunsh)運(yùn)算符 邏輯運(yùn)算符 關(guān)系運(yùn)算符共七十八頁(yè)集合循環(huán)(xnhun)函數(shù)四個(gè)集合循環(huán)(xnhun)函數(shù)：FOR、SUM 、 MAX、MINfunction( setname ( set_index_list) | condition : expression_list);objective MAX = SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH(

21、I, J);FOR(STUDENTS( I): constraints SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K) =1);FOR(PAIRS( I, J): BIN( MATCH( I, J);MAXB=MAX(PAIRS( I, J): BENEFIT( I, J);MINB=MIN(PAIRS( I, J): BENEFIT( I, J);Example:共七十八頁(yè)狀態(tài)(zhungti)窗口Solver Type:B-and-BGlobal MultistartModel Class: LP， QP，ILP， IQP，

22、PILP, PIQP，NLP，INLP，PINLP State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined共七十八頁(yè)7個(gè)選項(xiàng)卡(可設(shè)置(shzh)80-90個(gè)控制參數(shù))共七十八頁(yè) 程序與數(shù)據(jù)(shj)分離文本文件使用(shyng)外部數(shù)據(jù)文件Cut (or Copy) Paste 方法FILE 輸入數(shù)據(jù)、TEXT輸出數(shù)據(jù)（文本文件）OLE函數(shù)與電子表格軟件（如EXCEL）連接ODBC函數(shù)與數(shù)據(jù)庫(kù)連接LINGO命令腳本文件LG4 （LONGO模型文件）LNG （LONGO模型文件）LT

23、F （LONGO腳本文件）LDT （LONGO數(shù)據(jù)文件）LRP （LONGO報(bào)告文件）常用文件后綴共七十八頁(yè)FILE和TEXT：文本文件輸入輸出MODEL:SETS: MYSET / FILE(myfile.txt) / : FILE(myfile.txt);ENDSETSMIN = SUM( MYSET( I): SHIP( I) * COST( I); FOR( MYSET( I): CON1 SHIP( I) NEED( I); CON2 SHIP( I) NEED( I); CON2 SHIP( I) SUPPLY( I);DATA: MYSET =OLE(D:JXIEBJ2004MC

24、Mmydata.xls,CITIES); COST,NEED,SUPPLY =OLE(mydata.xls); OLE(mydata.xls,SOLUTION)=SHIP; ENDDATAEND mydata.xls文件(wnjin)中必須有下列名稱(及數(shù)據(jù))： CITIES， COST，NEED，SUPPLY，SOLUTION在EXCEL中還可以通過(guò)“宏”自動(dòng)調(diào)用LINGO(略)也可以將EXCEL表格嵌入到LINGO模型中(略)演示 MydataExample.lg4共七十八頁(yè)ODBC ：與數(shù)據(jù)庫(kù)連接(linji)輸入基本(jbn)集合元素：setname/ODBC(datasource ,

25、 tablename , columnname)/輸入派生集合元素：setname/ODBC(source,table , column1, column2)/目前支持下列DBMS: (如為其他數(shù)據(jù)庫(kù)，則需自行安裝驅(qū)動(dòng))ACCESS， DBASE，EXCEL，F(xiàn)OXPRO，ORACLE，PARADOX，SQL SERVER， TEXE FILES使用數(shù)據(jù)庫(kù)之前，數(shù)據(jù)源需要在ODBC管理器注冊(cè)輸入數(shù)據(jù)：Attr_list=ODBC(source,table , column1, column2)輸出數(shù)據(jù)：ODBC(source,table , column1, column2)= Attr_li

26、st具體例子略共七十八頁(yè)建模實(shí)例(shl)與求解最短路(dunl)問(wèn)題下料問(wèn)題露天礦的運(yùn)輸問(wèn)題鋼管運(yùn)輸問(wèn)題共七十八頁(yè)問(wèn)題(wnt)1. 如何下料最節(jié)省 ? 例 鋼管(gnggun)下料 問(wèn)題2. 客戶增加需求：原料鋼管:每根19米 4米50根 6米20根 8米15根 客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過(guò)3種。如何下料最節(jié)省？5米10根 共七十八頁(yè)按照(nzho)客戶需要在一根原料鋼管上安排切割的一種組合。 切割(qig)模式余料1米 4米1根 6米1根 8米1根 余料3米 4米1根 6米1根 6米1根 合理切割模式的余料應(yīng)小于客戶需要鋼

27、管的最小尺寸余料3米 8米1根 8米1根 鋼管下料 共七十八頁(yè)為滿足(mnz)客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)省？合理(hl)切割模式2. 所用原料鋼管總根數(shù)最少 模式4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問(wèn)題1 兩種標(biāo)準(zhǔn)1. 原料鋼管剩余總余量最小共七十八頁(yè)xi 按第i 種模式切割的原料(yunlio)鋼管根數(shù)(i=1,2,7) 約束(yush)滿足需求 決策變量 目標(biāo)1（總余量）按模式2切割12根,按模式5切割15根，余料27米 模式4米根數(shù)6米根數(shù)8米根數(shù)余料140032

28、31013201341203511116030170023需求502015最優(yōu)解：x2=12, x5=15, 其余為0；最優(yōu)值：27整數(shù)約束： xi 為整數(shù)共七十八頁(yè)當(dāng)余料沒(méi)有用處時(shí)，通常(tngchng)以總根數(shù)最少為目標(biāo) 目標(biāo)(mbio)2（總根數(shù)）鋼管下料問(wèn)題1 約束條件不變 最優(yōu)解：x2=15, x5=5, x7=5, 其余為0；最優(yōu)值：25。xi 為整數(shù)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米 雖余料增加8米，但減少了2根 與目標(biāo)1的結(jié)果“共切割27根，余料27米” 相比 共七十八頁(yè)鋼管(gnggun)下料問(wèn)題2對(duì)大規(guī)模問(wèn)題，用模型(mxng)的約

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

30、(yunlio)鋼管總根數(shù)下界： 特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：31 模式排列順序可任定 鋼管下料問(wèn)題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長(zhǎng)19米共七十八頁(yè)LINGO求解(qi ji)整數(shù)非線性規(guī)劃模型Local optimal solution found at iteration: 12211 Objective value: 28.00000Variable Value Reduced CostX1 10.00000 0

31、.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.

32、000000 模式(msh)1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數(shù)為28根。演示cut02a.lg4； cut02b.lg4共七十八頁(yè)如果生產(chǎn)某一類型(lixng)汽車，則至少要生產(chǎn)80輛， 那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？例: 汽車廠生產(chǎn)(shngchn)計(jì)劃 汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量。 制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大。 汽車生產(chǎn)與原油采購(gòu)共七十八頁(yè)設(shè)每月生產(chǎn)小、中、大型汽車(qc

33、h)的數(shù)量分別為x1, x2, x3汽車廠生產(chǎn)(shngchn)計(jì)劃 模型建立 線性規(guī)劃模型(LP)共七十八頁(yè)模型(mxng)求解 3） 模型中增加條件：x1, x2, x3 均為整數(shù)(zhngsh)，重新求解。 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.0000

34、00 0.003226結(jié)果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)=629，與LP最優(yōu)值632.2581相差不大。2）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值z(mì)，通過(guò)比較可能得到更優(yōu)的解。 但必須檢驗(yàn)它們是否滿足約束條件。為什么？共七十八頁(yè)IP可用LINDO直接(zhji)求解整數(shù)規(guī)劃(guhu)(Integer Programming,簡(jiǎn)記IP)“gin 3”表示“前3個(gè)變量為整數(shù)”，等價(jià)于：gin x1gin x2gin x3 IP 的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632 max 2x1+3x2+4x

35、3st1.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 模型求解 IP 結(jié)果輸出共七十八頁(yè)其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)(hnsh)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解(fnji)為8個(gè)LP子模型 汽車廠生產(chǎn)計(jì)劃 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。

36、x1,x2, x3=0 或 80 x1=80，x2= 150，x3=0，最優(yōu)值z(mì)=610共七十八頁(yè)LINDO中對(duì)0-1變量(binling)的限定：int y1int y2int y3 方法2：引入0-1變量，化為整數(shù)(zhngsh)規(guī)劃 M為大的正數(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

37、0.000000 Y3 0.000000 0.000000 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0 或 80 x2=0 或 80 x3=0 或 80最優(yōu)解同前 共七十八頁(yè)NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO, MATLAB)，但是(dnsh)其結(jié)果常依賴于初值的選擇。 方法(fngf)3：化為非線性規(guī)劃 非線性規(guī)劃（Non- Linear Programming，簡(jiǎn)記NLP） 實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí)，才能得到正確的結(jié)果。 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。 x1=0 或 80 x2=0 或 80 x3=0 或 80共七十八頁(yè)應(yīng)

38、如何(rh)安排原油的采購(gòu)和加工 ？ 原油采購(gòu)(cigu)與加工 市場(chǎng)上可買到不超過(guò)1500噸的原油A： 購(gòu)買量不超過(guò)500噸時(shí)的單價(jià)為10000元/噸； 購(gòu)買量超過(guò)500噸但不超過(guò)1000噸時(shí)，超過(guò)500噸的 部分8000元/噸； 購(gòu)買量超過(guò)1000噸時(shí)，超過(guò)1000噸的部分6000元/噸。 售價(jià)4800元/噸 售價(jià)5600元/噸庫(kù)存500噸 庫(kù)存1000噸 汽油甲(A50%) 原油A 原油B 汽油乙 (A60%) 共七十八頁(yè)決策(juc) 變量 目標(biāo)(mbio)函數(shù)問(wèn)題分析 利潤(rùn)：銷售汽油的收入 - 購(gòu)買原油A的支出 難點(diǎn)：原油A的購(gòu)價(jià)與購(gòu)買量的關(guān)系較復(fù)雜甲(A50%) A B 乙(A60

39、%) 購(gòu)買xx11x12x21x224.8千元/噸 5.6千元/噸原油A的購(gòu)買量,原油A, B生產(chǎn)汽油甲,乙的數(shù)量c(x) 購(gòu)買原油A的支出利潤(rùn)(千元)c(x)如何表述？共七十八頁(yè)原油(yunyu)供應(yīng) 約束條件 x 500噸單價(jià)(dnji)為10千元/噸； 500噸 x 1000噸，超過(guò)500噸的8千元/噸；1000噸 x 1500噸，超過(guò)1000噸的6千元/噸。 目標(biāo)函數(shù)購(gòu)買xA B x11x12x21x22庫(kù)存500噸 庫(kù)存1000噸 共七十八頁(yè) 目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃； 對(duì)于(duy)用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解； 想辦法將模型化

40、簡(jiǎn)，用現(xiàn)成的軟件求解。 汽油(qyu)含原油A的比例限制 約束條件甲(A50%) A B 乙(A60%) x11x12x21x22共七十八頁(yè)x1 , x2 , x3 以價(jià)格(jig)10, 8, 6(千元/噸)采購(gòu)A的噸數(shù)目標(biāo)(mbio)函數(shù) 只有當(dāng)以10千元/噸的價(jià)格購(gòu)買x1=500(噸)時(shí)，才能以8千元/噸的價(jià)格購(gòu)買x2方法1 非線性規(guī)劃模型，可以用LINGO求解模型求解x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 500噸 x 1000噸，超過(guò)500噸的8千元/噸增加約束x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 共七十八頁(yè)方法(fngf)1

41、：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;x11 0;x12 0;x21 0;x22 0;x1 0;x2 0;x3 0;end Objective value: 4800.000Variable Value Reduced CostX11 500.0000 0

42、.0000000E+00X21 500.0000 0.0000000E+00X12 0.0000000E+00 0.0000000E+00X22 0.0000000E+00 0.0000000E+00 X1 0.1021405E-13 10.00000 X2 0.0000000E+00 8.000000 X3 0.0000000E+00 6.000000 X 0.0000000E+00 0.0000000E+00 LINGO得到(d do)的是局部最優(yōu)解，還能得到(d do)更好的解嗎？ 用庫(kù)存的500噸原油A、500噸原油B生產(chǎn)汽油甲，不購(gòu)買新的原油A，利潤(rùn)為4,800千元。 共七十八頁(yè)y1

43、, y2 , y3=1 以價(jià)格(jig)10, 8, 6(千元/噸)采購(gòu)A增加(zngji)約束方法2 0-1線性規(guī)劃模型，可用LINDO求解y1,y2,y3 =0或1 OBJECTIVE FUNCTION VALUE 1) 5000.000 VARIABLE VALUE REDUCED COST Y1 1.000000 0.000000 Y2 1.000000 2200.000000 Y3 1.000000 1200.000000 X11 0.000000 0.800000 X21 0.000000 0.800000 X12 1500.000000 0.000000 X22 1000.000

44、000 0.000000 X1 500.000000 0.000000 X2 500.000000 0.000000 X3 0.000000 0.400000 X 1000.000000 0.000000 購(gòu)買1000噸原油A，與庫(kù)存的500噸原油A和1000噸原油B一起，生產(chǎn)汽油乙，利潤(rùn)為5,000千元 。x1 , x2 , x3 以價(jià)格10, 8, 6(千元/噸)采購(gòu)A的噸數(shù)y=0 x=0 x0 y=1優(yōu)于方法1的結(jié)果共七十八頁(yè)b1 b2 b3 b4方法(fngf)3 b1 xb2，x= z1b1+z2b2，z1+z2=1，z1, z20, c(x)= z1c(b1)+z2c(b2).c(

45、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). 直接處理(chl)處理(chl)分段線性函數(shù)c(x) 共七十八頁(yè)IP模型，LINDO求解(qi ji)，得到的結(jié)果與方法2相同.處理分段線性函數(shù)(hnsh)，方法3更具一般性bkxbk+1yk=1,否則,yk=0方法3 bkxbk+1 ,x= zkbk+z k+1 bk+1zk+zk+1 =1

46、，zk, zk+1 0, c(x)= zkc(bk)+zk+1 c(bk+1 ).c(x)x1200090005000050010001500b1 b2 b3 b4對(duì)于k=1,2,3共七十八頁(yè)露天礦里鏟位已分成(fn chn)礦石和巖石: 平均鐵含量不低于25%的為礦石，否則為巖石。每個(gè)鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個(gè)鏟位至多安置一臺(tái)電鏟，電鏟平均裝車時(shí)間5分鐘卡車(kch)在等待時(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時(shí)不應(yīng)發(fā)生卡車等待的情況。 露天礦生產(chǎn)的車輛安排(CUMCM-2003B) 礦石卸點(diǎn)需要的鐵含量要求都為29.5%1%(品位限制），搭配

47、量在一個(gè)班次（8小時(shí)）內(nèi)滿足品位限制即可。卸點(diǎn)在一個(gè)班次內(nèi)不變。卡車載重量為154噸，平均時(shí)速28km,平均卸車時(shí)間為3分鐘。問(wèn)題：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛卡車，分別在哪些路線上各運(yùn)輸多少次 ?共七十八頁(yè)平面(pngmin)示意圖共七十八頁(yè)問(wèn)題(wnt)數(shù)據(jù) 距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝1.900.991.901.131.272.251.482.043.093.51巖場(chǎng)5.895.615.614.563.513.652.462.461.060.57巖石

48、漏0.641.761.271.832.742.604.213.725.056.10倒裝4.423.863.723.162.252.810.781.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量095105100105110125105130135125巖石量125110135105115135105115135125鐵含量30%28%29%32%31%33%32%31%33%31%共七十八頁(yè)問(wèn)題(wnt)分析 與典型的運(yùn)輸問(wèn)題明顯有以下不同：這是運(yùn)輸?shù)V石與巖石兩種物資的問(wèn)題；屬于產(chǎn)量大于銷量的不平衡運(yùn)輸問(wèn)題；為了完成品位約束，礦石要搭配運(yùn)輸；產(chǎn)地、銷地均有單位時(shí)間的流量限制；運(yùn)輸車輛只有(zhyu)一種，每次滿載運(yùn)輸，154噸/車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個(gè)產(chǎn)地作為最后結(jié)果中的產(chǎn)地；最后求出各條路線上的派出車輛數(shù)及安排。近似處理：先求出產(chǎn)位、卸點(diǎn)每條線路上的運(yùn)輸量(MIP模型)然后求出各條路線上的派出車輛數(shù)及安排共七十八頁(yè)模型(mxng)假設(shè)卡車在一