優(yōu)化模型與優(yōu)化軟件簡介課件

簡要提綱1.優(yōu)化模型與優(yōu)化軟件簡介2.LINDO公司的主要軟件產(chǎn)品及功能簡介3.LINDO/LINGO軟件的使用簡介4.建模與求解實例（結(jié)合軟件使用）簡要提綱1.優(yōu)化模型與優(yōu)化軟件簡介1.優(yōu)化模型與優(yōu)化軟件簡介1.優(yōu)化模型與優(yōu)化軟件簡介

最優(yōu)化是工程技術(shù)、經(jīng)濟管理、科學研究、社會生活中經(jīng)常遇到的問題,如:優(yōu)化模型和優(yōu)化軟件的重要意義結(jié)構(gòu)設計資源分配生產(chǎn)計劃運輸方案解決優(yōu)化問題的手段

經(jīng)驗積累，主觀判斷

作試驗，比優(yōu)劣

建立數(shù)學模型(優(yōu)化模型)，求最優(yōu)策略(決策)(最)優(yōu)化:在一定條件下,尋求使目標最大(小)的決策

CUMCM賽題：約70%以上與優(yōu)化有關(guān)，需用軟件求解最優(yōu)化是工程技術(shù)、經(jīng)濟管理、科學研究、社會生活中經(jīng)常遇到的運籌學(OR:Operations/OperationalResearch)管理科學(MS:ManagementScience)決策科學(DS:DecisionScience)(最)優(yōu)化理論是運籌學的基本內(nèi)容無約束優(yōu)化OR/MS/DS優(yōu)化(Optimization),規(guī)劃(Programming)線性規(guī)劃非線性規(guī)劃網(wǎng)絡優(yōu)化組合優(yōu)化整數(shù)規(guī)劃不確定規(guī)劃多目標規(guī)劃目標規(guī)劃動態(tài)規(guī)劃運籌學(OR:Operations/Operational優(yōu)化問題三要素：決策變量；目標函數(shù)；約束條件約束條件決策變量優(yōu)化問題的一般形式可行解（滿足約束）與可行域（可行解的集合）最優(yōu)解（取到最小／大值的可行解）目標函數(shù)優(yōu)化問題三要素：決策變量；目標函數(shù)；約束條件約束條件決策變量無約束優(yōu)化:最優(yōu)解的分類和條件給定一個函數(shù)f(x),尋找x*使得f(x*)最小，即其中局部最優(yōu)解全局最優(yōu)解必要條件x*f(x)xlxgo充分條件Hessian陣最優(yōu)解在可行域邊界上取得時不能用無約束優(yōu)化方法求解無約束優(yōu)化:最優(yōu)解的分類和條件給定一個函數(shù)f(x),尋找約束優(yōu)化的簡單分類

線性規(guī)劃(LP)

目標和約束均為線性函數(shù)

非線性規(guī)劃(NLP)

目標或約束中存在非線性函數(shù)

二次規(guī)劃(QP)

目標為二次函數(shù)、約束為線性

整數(shù)規(guī)劃(IP)

決策變量(全部或部分)為整數(shù)整數(shù)線性規(guī)劃(ILP)，整數(shù)非線性規(guī)劃(INLP)

純整數(shù)規(guī)劃(PIP),混合整數(shù)規(guī)劃(MIP)

一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃連續(xù)優(yōu)化離散優(yōu)化數(shù)學規(guī)劃約束優(yōu)化的線性規(guī)劃(LP)目標和約束均為線常用優(yōu)化軟件1.LINDO/LINGO軟件2.MATLAB優(yōu)化工具箱3.EXCEL軟件的優(yōu)化功能4.SAS(統(tǒng)計分析)軟件的優(yōu)化功能5.其他常用優(yōu)化軟件1.LINDO/LINGO軟件MATLAB優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱3.0(MATLAB7.0R14)連續(xù)優(yōu)化離散優(yōu)化無約束優(yōu)化非線性極小fminunc非光滑(不可微)優(yōu)化fminsearch非線性方程(組)fzerofsolve全局優(yōu)化暫缺非線性最小二乘lsqnonlinlsqcurvefit線性規(guī)劃linprog純0-1規(guī)劃bintprog一般IP(暫缺)非線性規(guī)劃fminconfminimaxfgoalattainfseminf上下界約束fminbndfminconlsqnonlinlsqcurvefit約束線性最小二乘lsqnonneglsqlin約束優(yōu)化二次規(guī)劃quadprogMATLAB優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱3.0(M2.LINDO公司的主要軟件產(chǎn)品及功能簡介優(yōu)化模型與優(yōu)化軟件簡介課件LINDO公司軟件產(chǎn)品簡要介紹

美國芝加哥(Chicago)大學的LinusSchrage教授于1980年前后開發(fā),后來成立LINDO系統(tǒng)公司（LINDOSystemsInc.），網(wǎng)址：

LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V9.0)LINDOAPI:LINDOApplicationProgrammingInterface(V3.0)What’sBest!:(SpreadSheete.g.EXCEL)(V8.0)演示(試用)版、學生版、高級版、超級版、工業(yè)版、擴展版…（求解問題規(guī)模和選件不同）LINDO公司軟件產(chǎn)品簡要介紹美國芝加哥(ChicagoLINDO和LINGO軟件能求解的優(yōu)化模型LINGOLINDO優(yōu)化模型線性規(guī)劃(LP)非線性規(guī)劃(NLP)二次規(guī)劃(QP)連續(xù)優(yōu)化整數(shù)規(guī)劃(IP)LINDO和LINGO軟件能求解的優(yōu)化模型優(yōu)化模型線性規(guī)劃非LPQPNLPIP全局優(yōu)化(選)

ILPIQPINLP

LINDO/LINGO軟件的求解過程LINDO/LINGO預處理程序線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序1.確定常數(shù)2.識別類型1.單純形算法2.內(nèi)點算法(選)1、順序線性規(guī)劃法(SLP)2、廣義既約梯度法(GRG)(選)

3、多點搜索(Multistart)(選)LPQPNLPIP建模時需要注意的幾個基本問題

1、盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù)如：盡量少使用絕對值、符號函數(shù)、多個變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個數(shù)（如x/y<5改為x<5y）4、合理設定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級要適當(如小于103)建模時需要注意的幾個基本問題1、盡量使用實數(shù)優(yōu)化，減少整數(shù)3.LINDO/LINGO軟件的使用簡介優(yōu)化模型與優(yōu)化軟件簡介課件需要掌握的幾個重要方面1、LINDO:

正確閱讀求解報告（尤其要掌握敏感性分析）2、LINGO： 掌握集合(SETS)的應用； 正確閱讀求解報告； 正確理解求解狀態(tài)窗口； 學會設置基本的求解選項(OPTIONS)； 掌握與外部文件的基本接口方法需要掌握的幾個重要方面1、LINDO:例1加工奶制品的生產(chǎn)計劃1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時間480小時至多加工100公斤A1

制訂生產(chǎn)計劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?

可聘用臨時工人，付出的工資最多是每小時幾元?A1的獲利增加到30元/公斤，應否改變生產(chǎn)計劃？每天：例1加工奶制品的生產(chǎn)計劃1桶牛奶3公斤A112小1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應

勞動時間

加工能力

決策變量

目標函數(shù)

每天獲利約束條件非負約束

線性規(guī)劃模型(LP)時間480小時至多加工100公斤A1

50桶牛奶每天1桶牛奶3公斤A112小時8小時4公斤A2或獲利2模型求解

max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。模型求解max72x1+64x2OBJEC模型求解

reducedcost值表示當該非基變量增加一個單位時（其他非基變量保持不變）目標函數(shù)減少的量(對max型問題)

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解為：為了使該非基變量變成基變量，目標函數(shù)中對應系數(shù)應增加的量模型求解reducedcost值表示當該非基變量增加一個OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000原料無剩余時間無剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三種資源“資源”剩余為零的約束為緊約束（有效約束）結(jié)果解釋

OBJECTIVEFUNCTIONVALUE原料OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000結(jié)果解釋

最優(yōu)解下“資源”增加1單位時“效益”的增量原料增1單位,利潤增48時間加1單位,利潤增2能力增減不影響利潤影子價格35元可買到1桶牛奶，要買嗎？35<48,應該買！

聘用臨時工人付出的工資最多每小時幾元？2元！OBJECTIVEFUNCTIONVALRANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時目標系數(shù)允許變化范圍DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)A1獲利增加到30元/千克，應否改變生產(chǎn)計劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)結(jié)果解釋

RANGESINWHICHTHEBASISISU結(jié)果解釋

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加5335元可買到1桶牛奶，每天最多買多少？最多買10桶？(目標函數(shù)不變)注意:充分但可能不必要結(jié)果解釋RANGESINWHICHTHEBASIS使用LINDO的一些注意事項“>”（或“<”）號與“>=”（或“<=”）功能相同變量與系數(shù)間可有空格(甚至回車),但無運算符變量名以字母開頭，不能超過8個字符變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）目標函數(shù)所在行是第一行，第二行起為約束條件行號(行名)自動產(chǎn)生或人為定義。行名以“）”結(jié)束行中注有“!”符號的后面部分為注釋。如:

!It’sComment.在模型的任何地方都可以用“TITLE”對模型命名（最多72個字符），如：

TITLEThisModelisonlyanExample使用LINDO的一些注意事項“>”（或“<”）號與“>=”（變量不能出現(xiàn)在一個約束條件的右端表達式中不接受括號“()”和逗號“,”等任何符號,例:400(X1+X2)需寫為400X1+400X2表達式應化簡，如2X1+3X2-4X1應寫成-2X1+3X2缺省假定所有變量非負；可在模型的“END”語句后用“FREEname”將變量name的非負假定取消可在“END”后用“SUB”或“SLB”設定變量上下界例如：“subx110”的作用等價于“x1<=10”

但用“SUB”和“SLB”表示的上下界約束不計入模型的約束，也不能給出其松緊判斷和敏感性分析。14.“END”后對0-1變量說明：INTn

或INTname15.“END”后對整數(shù)變量說明：GINn

或GINname使用LINDO的一些注意事項變量不能出現(xiàn)在一個約束條件的右端使用LINDO的一些注意事項二次規(guī)劃(QP)問題LINDO可求解二次規(guī)劃(QP)問題，但輸入方式較復雜，因為在LINDO中不許出現(xiàn)非線性表達式需要為每一個實際約束增加一個對偶變量（LAGRANGE乘子），在實際約束前增加有關(guān)變量的一階最優(yōu)條件，轉(zhuǎn)化為互補問題“END”后面使用QCP命令指明實際約束開始的行號，然后才能求解建議總是用LINGO解QP[注意]對QP和IP:敏感性分析意義不大二次規(guī)劃(QP)問題LINDO可求解二次規(guī)劃(QP)問題，但狀態(tài)窗口（LINDOSolverStatus）當前狀態(tài)：已達最優(yōu)解迭代次數(shù)：18次約束不滿足的“量”(不是“約束個數(shù)”)：0當前的目標值：94最好的整數(shù)解：94整數(shù)規(guī)劃的界：93.5分枝數(shù)：1所用時間：0.00秒（太快了，還不到0.005秒）刷新本界面的間隔:1(秒)狀態(tài)窗口（LINDOSolverStatus）當前狀態(tài)選項設置

Preprocess：預處理(生成割平面)；

PreferredBranch：優(yōu)先的分枝方式：“Default”（缺省方式）、“Up”（向上取整優(yōu)先）、“Down”（向下取整優(yōu)先）；

IPOptimalityTol：IP最優(yōu)值允許的誤差上限（一個百分數(shù)，如5%即0.05）；

IPObjectiveHurdle：IP目標函數(shù)的籬笆值，即只尋找比這個值更優(yōu)最優(yōu)解（如當知道當前模型的某個整數(shù)可行解時，就可以設置這個值）；

IPVarFixingTol：固定一個整數(shù)變量取值所依據(jù)的一個上限（如果一個整數(shù)變量的判別數(shù)（REDUCEDCOST）的值很大，超過該上限，則以后求解中把該整數(shù)變量固定下來）。NonzeroLimit：非零系數(shù)的個數(shù)上限；IterationLimit：最大迭代步數(shù)；InitialContraintTol：約束的初始誤差上限；FinalContraintTol：約束的最后誤差上限；EnteringVarTol：進基變量的REDUCEDCOST的誤差限；PivotSizeTol：旋轉(zhuǎn)元的誤差限選項設置Preprocess：預處理(生成割平面)；NonReport/Statistics第一行：模型有5行（約束4行），4個變量，兩個整數(shù)變量（沒有0-1變量），從第4行開始是二次規(guī)劃的實際約束。第二行：非零系數(shù)19個，約束中非零系數(shù)12個(其中6個為1或-1)，模型密度為0.760(密度=非零系數(shù)/[行數(shù)＊(變量數(shù)＋１)])

。第三行的意思：按絕對值看，系數(shù)最小、最大分別為0.3和277。第四行的意思：模型目標為極小化；小于等于、等于、大于等于約束分別有２、０、２個；廣義上界約束（GUBS）不超過１個；變量上界約束（VUBS）不少于０個。所謂GUBS，是指一組不含有相同變量的約束；所謂VUBS，是指一個蘊涵變量上界的約束，如從約束X1+X2-X3=0可以看出，若X3=0，則X1=0，X2=0（因為有非負限制），因此X1+X2-X3=0是一個VUBS約束。第五行的意思：只含１個變量的約束個數(shù)=０個；冗余的列數(shù)=０個ROWS=5VARS=4INTEGERVARS=2(0=0/1)QCP=4NONZEROS=19CONSTRAINTNONZ=12(6=+-1)DENSITY=0.760SMALLESTANDLARGESTELEMENTSINABSOLUTEVALUE=0.300000277.000OBJ=MIN,NO.<,=,>:202,GUBS<=1VUBS>=0SINGLECOLS=0REDUNDANTCOLS=0 Report/Statistics第一行：模型有5行（約束4LINDO行命令、命令腳本文件批處理：可以采用命令腳本（行命令序列）WINDOWS環(huán)境下行命令的意義不大Example演示用FILE/TAKECOMMANDS(F11)命令調(diào)入必須是以LINDOPACKED形式（壓縮）保存的文件FILE/SAVE命令SAVE行命令LINDO行命令、命令腳本文件批處理：可以采用命令腳本（行命LINGO軟件簡介

目標與約束段集合段（SETSENDSETS）數(shù)據(jù)段（DATAENDDATA）初始段（INITENDINIT）計算段(CALCENDCALC)-LINGO9.0LINGO模型的構(gòu)成：5個段LINGO模型的優(yōu)點

包含了LINDO的全部功能提供了靈活的編程語言（矩陣生成器）LINGO軟件簡介目標與約束段LINGO模型的構(gòu)成：5個段LINGO模型—

例：選址問題某公司有6個建筑工地，位置坐標為(ai,bi)(單位：公里),水泥日用量di

(單位：噸）假設：料場和工地之間有直線道路LINGO模型—例：選址問題某公司有6個建筑工地，位置坐用例中數(shù)據(jù)計算，最優(yōu)解為總噸公里數(shù)為136.2線性規(guī)劃模型決策變量：cij(料場j到工地i的運量）~12維用例中數(shù)據(jù)計算，最優(yōu)解為總噸公里數(shù)為136.2線性規(guī)劃模型決選址問題：NLP2）改建兩個新料場，需要確定新料場位置(xj,yj)和運量cij

，在其它條件不變下使總噸公里數(shù)最小。決策變量：cij，(xj,yj)~16維非線性規(guī)劃模型選址問題：NLP2）改建兩個新料場，需要確定新料場位置(xjLINGO模型的構(gòu)成：4個段集合段（SETSENDSETS）數(shù)據(jù)段（DATAENDDATA）初始段（INITENDINIT）目標與約束段

局部最優(yōu)：89.8835(噸公里

)LP：移到數(shù)據(jù)段LINGO模型的構(gòu)成：4個段集合段（SETSENDS邊界邊界集合的類型

集合派生集合基本集合稀疏集合稠密集合元素列表法元素過濾法直接列舉法隱式列舉法setname[/member_list/][:attribute_list];setname(parent_set_list)[/member_list/][:attribute_list];SETS:CITIES/A1,A2,A3,B1,B2/;ROADS(CITIES,CITIES)/ A1,B1A1,B2A2,B1A3,B2/:D;ENDSETSSETS:STUDENTS/S1..S8/;PAIRS(STUDENTS,STUDENTS)|&2#GT#&1:BENEFIT,MATCH;ENDSETS集合的類型集合元素的隱式列舉類型隱式列舉格式示例示例集合的元素數(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,JAN2002集合元素的隱式列舉類型隱式列舉格式示例示例集合的元素數(shù)字型1運算符的優(yōu)先級優(yōu)先級運算符最高#NOT#—（負號）^*/+—（減法）#EQ##NE##GT##GE##LT##LE##AND##OR#最低<(=)=>(=)三類運算符：算術(shù)運算符邏輯運算符關(guān)系運算符運算符的優(yōu)先級優(yōu)先級運算符最高#NOT#—（負號）集合循環(huán)函數(shù)四個集合循環(huán)函數(shù)：FOR、SUM、MAX、MIN@function(setname[(set_index_list)[|condition]]:expression_list);[objective]MAX=@SUM(PAIRS(I,J):BENEFIT(I,J)*MATCH(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:集合循環(huán)函數(shù)四個集合循環(huán)函數(shù)：FOR、SUM、MAX、M狀態(tài)窗口SolverType:B-and-BGlobalMultistartModelClass:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLPState:GlobalOptimumLocalOptimumFeasibleInfeasibleUnboundedInterruptedUndetermined狀態(tài)窗口SolverType:ModelClass:St7個選項卡(可設置80-90個控制參數(shù))7個選項卡(可設置80-90個控制參數(shù))

程序與數(shù)據(jù)分離文本文件使用外部數(shù)據(jù)文件Cut(orCopy)–Paste方法@FILE

輸入數(shù)據(jù)、@TEXT輸出數(shù)據(jù)（文本文件）@OLE函數(shù)與電子表格軟件（如EXCEL）連接@ODBC函數(shù)與數(shù)據(jù)庫連接LINGO命令腳本文件LG4（LONGO模型文件）LNG（LONGO模型文件）LTF（LONGO腳本文件）LDT（LONGO數(shù)據(jù)文件）LRP（LONGO報告文件）常用文件后綴文使用外部數(shù)據(jù)文件Cut(orCopy)–Paste@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)<SUPPLY(I));DATA:COST=@FILE(‘myfile.txt’);NEED=@FILE(‘myfile.txt’);SUPPLY=@FILE(‘myfile.txt’);@TEXT(‘result.txt’)=SHIP,@DUAL(SHIP),@DUAL(CON1);ENDDATAENDmyfile.txt文件的內(nèi)容、格式：Seattle,Detroit,Chicago,Denver~COST,NEED,SUPPLY,SHIP~12,28,15,20~1600,1800,1200,1000~1700,1900,1300,1100演示MyfileExample.lg4@FILE和@TEXT：文本文件輸入輸出MODEL:myfi@OLE：與EXCEL連接MODEL:SETS:MYSET:COST,SHIP,NEED,SUPPLY;ENDSETSMIN=@SUM(MYSET(I):SHIP(I)*COST(I));@FOR(MYSET(I):[CON1]SHIP(I)>NEED(I);[CON2]SHIP(I)<SUPPLY(I));DATA:MYSET=@OLE('D:\JXIE\BJ2004MCM\mydata.xls','CITIES');COST,NEED,SUPPLY=@OLE(mydata.xls);@OLE(mydata.xls,'SOLUTION')=SHIP;ENDDATAENDmydata.xls文件中必須有下列名稱(及數(shù)據(jù))：

CITIES，COST，NEED，SUPPLY，SOLUTION在EXCEL中還可以通過“宏”自動調(diào)用LINGO(略)也可以將EXCEL表格嵌入到LINGO模型中(略)演示MydataExample.lg4@OLE：與EXCEL連接MODEL:mydat@ODBC：與數(shù)據(jù)庫連接輸入基本集合元素：setname/@ODBC([‘datasource’[,‘tablename’[,‘columnname’]]])/輸入派生集合元素：setname/@ODBC([‘source’[,‘table’[,‘column1’[,‘column2’…]]]])/目前支持下列DBMS:(如為其他數(shù)據(jù)庫，則需自行安裝驅(qū)動)ACCESS，DBASE，EXCEL，F(xiàn)OXPRO，ORACLE，PARADOX，SQLSERVER，TEXEFILES使用數(shù)據(jù)庫之前，數(shù)據(jù)源需要在ODBC管理器注冊輸入數(shù)據(jù)：Attr_list=@ODBC([‘source’[,‘table’[,‘column1’[,‘column2’…]]]])輸出數(shù)據(jù)：@ODBC([‘source’[,‘table’[,‘column1’[,‘column2’…]]]])=Attr_list具體例子略@ODBC：與數(shù)據(jù)庫連接輸入基本集合元素：目前支持下列DB4.建模與求解實例（結(jié)合軟件使用）優(yōu)化模型與優(yōu)化軟件簡介課件建模實例與求解最短路問題下料問題飛機定位露天礦的運輸問題鋼管運輸問題電力市場的堵塞管理建模實例與求解最短路問題例最短路問題求各點到T的最短路56774968658336C1B1C2B2A1A2A3TS6shortestPath.lg4例最短路問題求各點到T的最短路56774968658336問題1.如何下料最節(jié)省?例鋼管下料問題2.客戶增加需求：原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標準是什么？由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)?。?米10根問題1.如何下料最節(jié)省?例鋼管下料問題2.客按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根鋼管下料按照客戶需要在一根原料鋼管上安排切割的一種組合。切割模式余為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)省？合理切割模式2.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問題1兩種標準1.原料鋼管剩余總余量最小為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)約束滿足需求決策變量

目標1（總余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015最優(yōu)解：x2=12,x5=15,

其余為0；最優(yōu)值：27整數(shù)約束：xi為整數(shù)xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)當余料沒有用處時，通常以總根數(shù)最少為目標目標2（總根數(shù)）鋼管下料問題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根與目標1的結(jié)果“共切割27根，余料27米”相比當余料沒有用處時，通常以總根數(shù)最少為目標目標2（總根數(shù)）鋼鋼管下料問題2對大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過3種?，F(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復雜。決策變量

xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長的鋼管的數(shù)量鋼管下料問題2對大規(guī)模問題，用模型的約束條件界定合理模式增加滿足需求模式合理：每根余料不超過3米整數(shù)非線性規(guī)劃模型鋼管下料問題2目標函數(shù)（總根數(shù)）約束條件整數(shù)約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數(shù)滿足需求模式合理：每根余料不超過3米整數(shù)非線性規(guī)劃模型鋼管下增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：

特殊生產(chǎn)計劃：對每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：31模式排列順序可任定

鋼管下料問題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長19米增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：特殊生產(chǎn)LINGO求解整數(shù)非線性規(guī)劃模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數(shù)為28根。演示cut02a.lg4；cut02b.lg4LINGO求解整數(shù)非線性規(guī)劃模型Localoptimal0yxVOR2x=629,y=375309.00(1.30)864.3(2.0)飛機x=?,y=?VOR1x=764,y=1393161.20(0.80)VOR3x=1571,y=25945.10(0.60)北DMEx=155,y=987飛機與監(jiān)控臺（圖中坐標和測量距離的單位是“公里”）實例:飛機精確定位問題0yxVOR2309.00(1.30)864.3(2.0)飛機精確定位模型xiyi原始的(或d4）VO20（2.81347弧度）0.80（0.0140弧度）VOR262937545.10（0.78714弧度）0.60（0.0105弧度）VOR31571259309.00（5.39307弧度）1.30（0.0227弧度）DME155987d4=864.3（km）2.0（km）飛機精確定位模型xiyi原始的(或d4）VOR飛機精確定位模型第1類模型:不考慮誤差因素超定方程組，非線性最小二乘！量綱不符！？

飛機精確定位模型第1類模型:不考慮誤差因素超定方程組，量綱飛機精確定位模型第2類模型:考慮誤差因素(作為硬約束)Minx;Miny;Maxx;Maxy.

以距離為約束，優(yōu)化角度誤差之和（或平方和）；或以角度為約束，優(yōu)化距離誤差.非線性規(guī)劃

？

？僅部分考慮誤差!角度與距離的“地位”不應不同！有人也可能會采用其他目標，如：

誤差非均勻分布！

飛機精確定位模型第2類模型:考慮誤差因素(作為硬約束)Mi飛機精確定位模型誤差一般服從什么分布？正態(tài)分布！不同的量綱如何處理？無約束非線性最小二乘模型歸一化處理！shili0702.m飛機坐標(978.31，723.98),誤差平方和0.6685(<<4)角度需要進行預處理，如利用Matlab的atan2函數(shù),值域(-pi,pi)第3類模型:考慮誤差因素(作為軟約束);且歸一化飛機精確定位模型誤差一般服從什么分布？正態(tài)分布！不同的量綱如飛機精確定位模型小技巧:LINGO中沒有atan2函數(shù),怎么辦？可以直接利用@tan函數(shù)！exam0507c.lg4同前面的模型/結(jié)果飛機坐標(980.21，727.30),誤差平方和2.6與前面的結(jié)果有所不同,為什么?哪個模型合理些?最后:思考以下模型:exam0507d.lg4飛機精確定位模型小技巧:LINGO中沒有atan2函數(shù),露天礦里鏟位已分成礦石和巖石:平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘卡車在等待時所耗費的能量也是相當可觀的，原則上在安排時不應發(fā)生卡車等待的情況。露天礦生產(chǎn)的車輛安排(CUMCM-2003B)

礦石卸點需要的鐵含量要求都為29.5%1%(品位限制），搭配量在一個班次（8小時）內(nèi)滿足品位限制即可。卸點在一個班次內(nèi)不變?？ㄜ囕d重量為154噸，平均時速28km,平均卸車時間為3分鐘。問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次?露天礦里鏟位已分成礦石和巖石:平均鐵含量不低于25%的為礦平面示意圖平面示意圖問題數(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巖場5.895.615.614.563.513.652.462.461.060.57巖石漏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礦石量0．951．051．001．051．101．251．051．301．351．25巖石量1．251．101．351．051．151．351．051．151．351．25鐵含量30%28%29%32%31%33%32%31%33%31%問題數(shù)據(jù)距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位問題分析與典型的運輸問題明顯有以下不同：這是運輸?shù)V石與巖石兩種物資的問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；為了完成品位約束，礦石要搭配運輸；產(chǎn)地、銷地均有單位時間的流量限制；運輸車輛只有一種，每次滿載運輸，154噸/車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個產(chǎn)地作為最后結(jié)果中的產(chǎn)地；最后求出各條路線上的派出車輛數(shù)及安排。近似處理：先求出產(chǎn)位、卸點每條線路上的運輸量(MIP模型)然后求出各條路線上的派出車輛數(shù)及安排問題分析與典型的運輸問題明顯有以下不同：近似處理：模型假設卡車在一個班次中不應發(fā)生等待或熄火后再啟動的情況；在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認為只要平均時間能完成任務，就認為不沖突。我們不排時地進行討論；空載與重載的速度都是28km/h，耗油相差很大；卡車可提前退出系統(tǒng)，等等。如理解為嚴格不等待，難以用數(shù)學規(guī)劃模型來解個別參數(shù)隊找到了可行解（略）模型假設卡車在一個班次中不應發(fā)生等待或熄火后再啟動的情況；如符號xij

：從i鏟位到j號卸點的石料運量（車）單位：噸；cij

：從i號鏟位到j號卸點的距離公里；Tij:從i號鏟位到號j卸點路線上運行一個周期平均時間分；Aij

：從號鏟位到號卸點最多能同時運行的卡車數(shù)輛；Bij

：從號鏟位到號卸點路線上一輛車最多可運行的次數(shù)次；pi：i號鏟位的礦石鐵含量p=(30,28,29,32,31,33,32,31,33,31)%qj:j號卸點任務需求，q=(1.2,1.3,1.3,1.9,1.3)*10000噸cki

：i號鏟位的鐵礦石儲量萬噸cyi

：i號鏟位的巖石儲量萬噸fi:描述第i號鏟位是否使用的0-1變量，取1為使用；0為關(guān)閉。(近似)符號xij：從i鏟位到j號卸點的石料運量（車）優(yōu)化模型（1）道路能力(卡車數(shù))約束（2）電鏟能力約束（3）卸點能力約束（4）鏟位儲量約束（5）產(chǎn)量任務約束（6）鐵含量約束（7）電鏟數(shù)量約束（8）整數(shù)約束.xij為非負整數(shù)fi為0-1整數(shù)優(yōu)化模型（1）道路能力(卡車數(shù))約束.xij為非負整數(shù)計算結(jié)果（LINGO軟件）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦漏135411倒Ⅰ4243巖場7015巖漏8143倒Ⅱ13270鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏0.8671.8620.314倒場Ⅰ1.0771.162巖場1.8920.326巖石漏1.8411.229倒場Ⅱ0.6840.11.489cumcm2003b1.lg4注:LINGO8.0本來是可以得到最優(yōu)解的，但有些

LINGO8.0可能出現(xiàn)系統(tǒng)錯誤,可能是系統(tǒng)BUG計算結(jié)果（LINGO軟件）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位計算結(jié)果（派車）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏1(29)倒場Ⅰ1(39)1(37)巖場1(37)巖石漏1(44)1(35)倒場Ⅱ1(47)結(jié)論：鏟位1、2、3、4、8、9、10處各放置一臺電鏟。一共使用了13輛卡車；總運量為85628.62噸公里；巖石產(chǎn)量為32186噸；礦石產(chǎn)量為38192噸。此外：6輛聯(lián)合派車（方案略）計算結(jié)果（派車）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟最大化產(chǎn)量結(jié)論：（略）目標函數(shù)變化此外：車輛數(shù)量（20輛）限制（其實上面的模型也應該有）最大化產(chǎn)量結(jié)論：目標函數(shù)變化建模實例與求解交通流的均衡問題（另附）鋼管運輸問題（另附）電力市場的堵塞管理（另附）建模實例與求解交通流的均衡問題（另附）CUMCM其他優(yōu)化賽題飛行管理問題空洞探測問題鉆井布局問題搶渡長江問題等等CUMCM其他優(yōu)化賽題飛行管理問題主要參考文獻謝金星,薛毅:優(yōu)化建模與LINDO/LINGO軟件,清華大學出版社,2005年7月出版./~jxie/lindo主要參考文獻謝金星,薛毅:優(yōu)化建模與LINDO/LING

Thankyouforyourattendance!

祝大家在數(shù)學建模學習與競賽活動中取得優(yōu)異的成績！清華大學數(shù)學科學系清華大學數(shù)學科學系簡要提綱1.優(yōu)化模型與優(yōu)化軟件簡介2.LINDO公司的主要軟件產(chǎn)品及功能簡介3.LINDO/LINGO軟件的使用簡介4.建模與求解實例（結(jié)合軟件使用）簡要提綱1.優(yōu)化模型與優(yōu)化軟件簡介1.優(yōu)化模型與優(yōu)化軟件簡介1.優(yōu)化模型與優(yōu)化軟件簡介

最優(yōu)化是工程技術(shù)、經(jīng)濟管理、科學研究、社會生活中經(jīng)常遇到的問題,如:優(yōu)化模型和優(yōu)化軟件的重要意義結(jié)構(gòu)設計資源分配生產(chǎn)計劃運輸方案解決優(yōu)化問題的手段

經(jīng)驗積累，主觀判斷

作試驗，比優(yōu)劣

建立數(shù)學模型(優(yōu)化模型)，求最優(yōu)策略(決策)(最)優(yōu)化:在一定條件下,尋求使目標最大(小)的決策

CUMCM賽題：約70%以上與優(yōu)化有關(guān)，需用軟件求解最優(yōu)化是工程技術(shù)、經(jīng)濟管理、科學研究、社會生活中經(jīng)常遇到的運籌學(OR:Operations/OperationalResearch)管理科學(MS:ManagementScience)決策科學(DS:DecisionScience)(最)優(yōu)化理論是運籌學的基本內(nèi)容無約束優(yōu)化OR/MS/DS優(yōu)化(Optimization),規(guī)劃(Programming)線性規(guī)劃非線性規(guī)劃網(wǎng)絡優(yōu)化組合優(yōu)化整數(shù)規(guī)劃不確定規(guī)劃多目標規(guī)劃目標規(guī)劃動態(tài)規(guī)劃運籌學(OR:Operations/Operational優(yōu)化問題三要素：決策變量；目標函數(shù)；約束條件約束條件決策變量優(yōu)化問題的一般形式可行解（滿足約束）與可行域（可行解的集合）最優(yōu)解（取到最?。笾档目尚薪猓┠繕撕瘮?shù)優(yōu)化問題三要素：決策變量；目標函數(shù)；約束條件約束條件決策變量無約束優(yōu)化:最優(yōu)解的分類和條件給定一個函數(shù)f(x),尋找x*使得f(x*)最小，即其中局部最優(yōu)解全局最優(yōu)解必要條件x*f(x)xlxgo充分條件Hessian陣最優(yōu)解在可行域邊界上取得時不能用無約束優(yōu)化方法求解無約束優(yōu)化:最優(yōu)解的分類和條件給定一個函數(shù)f(x),尋找約束優(yōu)化的簡單分類

線性規(guī)劃(LP)

目標和約束均為線性函數(shù)

非線性規(guī)劃(NLP)

目標或約束中存在非線性函數(shù)

二次規(guī)劃(QP)

目標為二次函數(shù)、約束為線性

整數(shù)規(guī)劃(IP)

決策變量(全部或部分)為整數(shù)整數(shù)線性規(guī)劃(ILP)，整數(shù)非線性規(guī)劃(INLP)

純整數(shù)規(guī)劃(PIP),混合整數(shù)規(guī)劃(MIP)

一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃連續(xù)優(yōu)化離散優(yōu)化數(shù)學規(guī)劃約束優(yōu)化的線性規(guī)劃(LP)目標和約束均為線常用優(yōu)化軟件1.LINDO/LINGO軟件2.MATLAB優(yōu)化工具箱3.EXCEL軟件的優(yōu)化功能4.SAS(統(tǒng)計分析)軟件的優(yōu)化功能5.其他常用優(yōu)化軟件1.LINDO/LINGO軟件MATLAB優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱3.0(MATLAB7.0R14)連續(xù)優(yōu)化離散優(yōu)化無約束優(yōu)化非線性極小fminunc非光滑(不可微)優(yōu)化fminsearch非線性方程(組)fzerofsolve全局優(yōu)化暫缺非線性最小二乘lsqnonlinlsqcurvefit線性規(guī)劃linprog純0-1規(guī)劃bintprog一般IP(暫缺)非線性規(guī)劃fminconfminimaxfgoalattainfseminf上下界約束fminbndfminconlsqnonlinlsqcurvefit約束線性最小二乘lsqnonneglsqlin約束優(yōu)化二次規(guī)劃quadprogMATLAB優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱3.0(M2.LINDO公司的主要軟件產(chǎn)品及功能簡介優(yōu)化模型與優(yōu)化軟件簡介課件LINDO公司軟件產(chǎn)品簡要介紹

美國芝加哥(Chicago)大學的LinusSchrage教授于1980年前后開發(fā),后來成立LINDO系統(tǒng)公司（LINDOSystemsInc.），網(wǎng)址：

LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V9.0)LINDOAPI:LINDOApplicationProgrammingInterface(V3.0)What’sBest!:(SpreadSheete.g.EXCEL)(V8.0)演示(試用)版、學生版、高級版、超級版、工業(yè)版、擴展版…（求解問題規(guī)模和選件不同）LINDO公司軟件產(chǎn)品簡要介紹美國芝加哥(ChicagoLINDO和LINGO軟件能求解的優(yōu)化模型LINGOLINDO優(yōu)化模型線性規(guī)劃(LP)非線性規(guī)劃(NLP)二次規(guī)劃(QP)連續(xù)優(yōu)化整數(shù)規(guī)劃(IP)LINDO和LINGO軟件能求解的優(yōu)化模型優(yōu)化模型線性規(guī)劃非LPQPNLPIP全局優(yōu)化(選)

ILPIQPINLP

LINDO/LINGO軟件的求解過程LINDO/LINGO預處理程序線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序1.確定常數(shù)2.識別類型1.單純形算法2.內(nèi)點算法(選)1、順序線性規(guī)劃法(SLP)2、廣義既約梯度法(GRG)(選)

3、多點搜索(Multistart)(選)LPQPNLPIP建模時需要注意的幾個基本問題

1、盡量使用實數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù)如：盡量少使用絕對值、符號函數(shù)、多個變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個數(shù)（如x/y<5改為x<5y）4、合理設定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級要適當(如小于103)建模時需要注意的幾個基本問題1、盡量使用實數(shù)優(yōu)化，減少整數(shù)3.LINDO/LINGO軟件的使用簡介優(yōu)化模型與優(yōu)化軟件簡介課件需要掌握的幾個重要方面1、LINDO:

正確閱讀求解報告（尤其要掌握敏感性分析）2、LINGO： 掌握集合(SETS)的應用； 正確閱讀求解報告； 正確理解求解狀態(tài)窗口； 學會設置基本的求解選項(OPTIONS)； 掌握與外部文件的基本接口方法需要掌握的幾個重要方面1、LINDO:例1加工奶制品的生產(chǎn)計劃1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時間480小時至多加工100公斤A1

制訂生產(chǎn)計劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?

可聘用臨時工人，付出的工資最多是每小時幾元?A1的獲利增加到30元/公斤，應否改變生產(chǎn)計劃？每天：例1加工奶制品的生產(chǎn)計劃1桶牛奶3公斤A112小1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應

勞動時間

加工能力

決策變量

目標函