清華大學-謝金星-optimizatio-lindo北戴河.ppt

數(shù)學建模講座 清華大學 謝金星 優(yōu)化建模與LINDO/LINGO優(yōu)化軟件,簡要提綱,1. 優(yōu)化模型與優(yōu)化軟件簡介 2. LINDO公司的主要軟件產品及功能簡介 3. LINDO / LINGO軟件的使用簡介 4. 建模與求解實例（結合軟件使用）,1. 優(yōu)化模型與優(yōu)化軟件簡介,最優(yōu)化是工程技術、經濟管理、科學研究、社會生活中經常遇到的問題, 如:,優(yōu)化模型和優(yōu)化軟件的重要意義,結構設計,資源分配,生產計劃,運輸方案,解決優(yōu)化問題的手段,經驗積累，主觀判斷,作試驗，比優(yōu)劣,建立數(shù)學模型(優(yōu)化模型)，求最優(yōu)策略(決策),(最)優(yōu)化:在一定條件下,尋求使目標最大(小)的決策,CUMCM賽題：約70%以上與優(yōu)化有關，需用軟件求解,運籌學(OR: Operations/Operational Research) 管理科學(MS: Management Science) 決策科學 (DS: Decision Science),(最)優(yōu)化理論是運籌學的基本內容,無約束優(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ī)劃,優(yōu)化問題三要素：決策變量；目標函數(shù)；約束條件,優(yōu)化問題的一般形式,可行解（滿足約束）與可行域（可行解的集合） 最優(yōu)解（取到最小大值的可行解）,無約束優(yōu)化:最優(yōu)解的分類和條件,給定一個函數(shù) f(x),尋找 x* 使得 f(x*)最小，即,其中,局部最優(yōu)解,全局最優(yōu)解,必要條件,最優(yōu)解在可行域邊界上取得時不能用無約束優(yōu)化方法求解,約束優(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)化軟件,1. LINDO/LINGO軟件 2. MATLAB優(yōu)化工具箱 3. EXCEL軟件的優(yōu)化功能 4. SAS(統(tǒng)計分析)軟件的優(yōu)化功能 5. 其他,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 lsqcurvefit,約束線性 最小二乘 lsqnonneg lsqlin,約束優(yōu)化,二次規(guī)劃 quadprog,2. LINDO公司的主要軟件產品及功能簡介,LINDO 公司軟件產品簡要介紹,美國芝加哥(Chicago)大學的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 Interface (V3.0) Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0),演示(試用)版、學生版、高級版、超級版、工業(yè)版、擴展版 （求解問題規(guī)模和選件不同）,LINDO和LINGO軟件能求解的優(yōu)化模型,LINGO,LINDO,優(yōu)化模型,線性規(guī)劃 (LP),非線性規(guī)劃 (NLP),二次規(guī)劃 (QP),連續(xù)優(yōu)化,整數(shù)規(guī)劃(IP),LP QP NLP IP 全局優(yōu)化(選) ILP IQP INLP,LINDO/LINGO軟件的求解過程,LINDO/LINGO預處理程序,線性優(yōu)化求解程序,非線性優(yōu)化求解程序,分枝定界管理程序,1. 確定常數(shù) 2. 識別類型,1. 單純形算法 2. 內點算法(選),1、順序線性規(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、合理設定變量上下界，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級要適當 (如小于103),3. LINDO / LINGO軟件的使用簡介,需要掌握的幾個重要方面,1、LINDO: 正確閱讀求解報告（尤其要掌握敏感性分析） 2、LINGO： 掌握集合(SETS)的應用； 正確閱讀求解報告； 正確理解求解狀態(tài)窗口； 學會設置基本的求解選項(OPTIONS) ； 掌握與外部文件的基本接口方法,例1 加工奶制品的生產計劃,50桶牛奶,時間480小時,至多加工100公斤A1,制訂生產計劃，使每天獲利最大,35元可買到1桶牛奶，買嗎？若買，每天最多買多少?,可聘用臨時工人，付出的工資最多是每小時幾元?,A1的獲利增加到 30元/公斤，應否改變生產計劃？,每天：,x1桶牛奶生產A1,x2桶牛奶生產A2,獲利 243x1,獲利 164 x2,原料供應,勞動時間,加工能力,決策變量,目標函數(shù),每天獲利,約束條件,非負約束,線性規(guī)劃模型(LP),時間480小時,至多加工100公斤A1,模型求解,max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end,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 NO. ITERATIONS= 2,DO RANGE (SENSITIVITY) ANALYSIS?,No,20桶牛奶生產A1, 30桶生產A2，利潤3360元。,模型求解,reduced cost值表示當該非基變量增加一個單位時（其他非基變量保持不變）目標函數(shù)減少的量(對max型問題),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 NO. ITERATIONS= 2,也可理解為： 為了使該非基變量變成基變量，目標函數(shù)中對應系數(shù)應增加的量,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,原料無剩余,時間無剩余,加工能力剩余40,max 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end,三種資源,“資源” 剩余為零的約束為緊約束（有效約束）,結果解釋,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,結果解釋,最優(yōu)解下“資源”增加1單位時“效益”的增量,原料增1單位, 利潤增48,時間加1單位, 利潤增2,能力增減不影響利潤,影子價格,35元可買到1桶牛奶，要買嗎？,35 48, 應該買！,聘用臨時工人付出的工資最多每小時幾元？,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.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最優(yōu)解不變時目標系數(shù)允許變化范圍,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系數(shù)范圍(64,96),x2系數(shù)范圍(48,72),A1獲利增加到 30元/千克，應否改變生產計劃,x1系數(shù)由243= 72 增加為303= 90，在允許范圍內,不變！,(約束條件不變),結果解釋,結果解釋,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.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子價格有意義時約束右端的允許變化范圍,原料最多增加10,時間最多增加53,35元可買到1桶牛奶，每天最多買多少？,最多買10桶？,(目標函數(shù)不變),注意: 充分但可能不必要,使用LINDO的一些注意事項,“”（或“=”（或“=”）功能相同 變量與系數(shù)間可有空格(甚至回車), 但無運算符 變量名以字母開頭，不能超過8個字符 變量名不區(qū)分大小寫（包括LINDO中的關鍵字） 目標函數(shù)所在行是第一行，第二行起為約束條件 行號(行名)自動產生或人為定義。行名以“）”結束 行中注有“!”符號的后面部分為注釋。如: ! Its Comment. 在模型的任何地方都可以用“TITLE” 對模型命名（最多72個字符），如： TITLE This Model is only an Example,變量不能出現(xiàn)在一個約束條件的右端 表達式中不接受括號“( )”和逗號“,”等任何符號, 例: 400(X1+X2)需寫為400X1+400X2 表達式應化簡，如2X1+3X2- 4X1應寫成 -2X1+3X2 缺省假定所有變量非負；可在模型的“END”語句后用“FREE name”將變量name的非負假定取消 可在 “END”后用“SUB” 或“SLB” 設定變量上下界 例如： “sub x1 10”的作用等價于“x1=10” 但用“SUB”和“SLB”表示的上下界約束不計入模型的約束，也不能給出其松緊判斷和敏感性分析。 14. “END”后對0-1變量說明：INT n 或 INT name 15. “END”后對整數(shù)變量說明：GIN n 或 GIN name,使用LINDO的一些注意事項,二次規(guī)劃(QP)問題,LINDO可求解二次規(guī)劃(QP)問題，但輸入方式較復雜，因為在LINDO中不許出現(xiàn)非線性表達式 需要為每一個實際約束增加一個對偶變量（LAGRANGE乘子），在實際約束前增加有關變量的一階最優(yōu)條件，轉化為互補問題 “END”后面使用QCP命令指明實際約束開始的行號，然后才能求解 建議總是用LINGO解QP 注意對QP和IP: 敏感性分析意義不大,狀態(tài)窗口（LINDO Solver Status）,當前狀態(tài)：已達最優(yōu)解 迭代次數(shù)：18次 約束不滿足的“量”(不是“約束個數(shù)”)：0 當前的目標值：94 最好的整數(shù)解：94 整數(shù)規(guī)劃的界：93.5 分枝數(shù)：1 所用時間：0.00秒（太快了，還不到0.005秒） 刷新本界面的間隔:1(秒),選項設置,Preprocess：預處理(生成割平面)； Preferred Branch：優(yōu)先的分枝方式： “Default”（缺省方式）、 “Up”（向上取整優(yōu)先）、 “Down”（向下取整優(yōu)先）； IP Optimality Tol：IP最優(yōu)值允許的誤差上限（一個百分數(shù)，如5%即0.05）； IP Objective Hurdle：IP目標函數(shù)的籬笆值，即只尋找比這個值更優(yōu)最優(yōu)解（如當知道當前模型的某個整數(shù)可行解時，就可以設置這個值）； IP Var Fixing Tol：固定一個整數(shù)變量取值所依據(jù)的一個上限（如果一個整數(shù)變量的判別數(shù)（REDUCED COST）的值很大，超過該上限，則以后求解中把該整數(shù)變量固定下來）。,Nonzero Limit： 非零系數(shù)的個數(shù)上限； Iteration Limit： 最大迭代步數(shù)； Initial Contraint Tol： 約束的初始誤差上限； Final Contraint Tol： 約束的最后誤差上限； Entering Var Tol： 進基變量的REDUCED COST的誤差限； Pivot Size Tol： 旋轉元的誤差限,Report/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= 5 VARS= 4 INTEGER VARS= 2( 0 = 0/1) QCP= 4 NONZEROS= 19 CONSTRAINT NONZ= 12( 6 = +-1) DENSITY=0.760 SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE= 0.300000 277.000 OBJ=MIN, NO. : 2 0 2, GUBS = 0 SINGLE COLS= 0 REDUNDANT COLS= 0,LINDO行命令、命令腳本文件,批處理：可以采用命令腳本（行命令序列）,WINDOWS環(huán)境下行命令的意義不大,Example 演示,用FILE / TAKE COMMANDS (F11) 命令調入,必須是以LINDO PACKED形式（壓縮）保存的文件,FILE / SAVE命令,SAVE行命令,LINGO軟件簡介,目標與約束段 集合段（SETS ENDSETS） 數(shù)據(jù)段（DATA ENDDATA） 初始段（INIT ENDINIT） 計算段 (CALC ENDCALC) - LINGO9.0,LINGO模型的構成：5個段,LINGO模型的優(yōu)點,包含了LINDO的全部功能 提供了靈活的編程語言（矩陣生成器）,LINGO模型 例：選址問題,某公司有6個建筑工地，位置坐標為(ai, bi) (單位：公里),水泥日用量di (單位：噸）,假設：料場和工地之間有直線道路,用例中數(shù)據(jù)計算，最優(yōu)解為,總噸公里數(shù)為136.2,線性規(guī)劃模型,決策變量：ci j (料場j到工地i的運量）12維,選址問題：NLP,2）改建兩個新料場，需要確定新料場位置(xj,yj)和運量cij ，在其它條件不變下使總噸公里數(shù)最小。,決策變量： ci j，(xj,yj)16維,非線性規(guī)劃模型,LINGO模型的構成：4個段,集合段（SETS ENDSETS）,數(shù)據(jù)段（DATA ENDDATA）,初始段（INIT ENDINIT）,目標與 約束段,局部最優(yōu)：89.8835(噸公里 ),LP：移到數(shù)據(jù)段,邊界,集合的類型,集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素過濾法 直接列舉法 隱式列舉法,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; ENDSETS,SETS: STUDENTS /S1S8/; PAIRS( STUDENTS, STUDENTS) | ENDSETS,集合元素的隱式列舉,運算符的優(yōu)先級,三類運算符： 算術運算符 邏輯運算符 關系運算符,集合循環(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:,狀態(tài)窗口,Solver Type: B-and-B Global Multistart,Model Class: LP， QP，ILP， IQP，PILP, PIQP，NLP，INLP，PINLP,State: Global Optimum Local Optimum Feasible Infeasible Unbounded Interrupted Undetermined,7個選項卡(可設置80-90個控制參數(shù)),程序與數(shù)據(jù)分離,文 本 文 件,使用外部數(shù)據(jù)文件,Cut (or Copy) 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報告文件）,常用文件后綴,FILE和TEXT：文本文件輸入輸出,MODEL: SETS: MYSET / FILE(myfile.txt) / : FILE(myfile.txt); ENDSETS MIN = 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); ENDDATA END,myfile.txt文件 的內容、格式： Seattle,Detroit,Chicago,Denver COST,NEED,SUPPLY,SHIP 12,28,15,20 1600,1800,1200,1000 1700,1900,1300,1100,演示 MyfileExample.lg4,OLE ：與EXCEL連接,MODEL: SETS: MYSET: COST,SHIP,NEED,SUPPLY; ENDSETS MIN = SUM( MYSET( I): SHIP( I) * COST( I); FOR( MYSET( I): CON1 SHIP( I) NEED( I); CON2 SHIP( I) SUPPLY( I); DATA: MYSET =OLE(D:JXIEBJ2004MCMmydata.xls,CITIES); COST,NEED,SUPPLY =OLE(mydata.xls); OLE(mydata.xls,SOLUTION)=SHIP; ENDDATA END,mydata.xls文件中必須有下列名稱(及數(shù)據(jù))： CITIES， COST，NEED，SUPPLY，SOLUTION,在EXCEL中還可以通過“宏”自動調用LINGO(略) 也可以將EXCEL表格嵌入到LINGO模型中(略),演示 MydataExample.lg4,ODBC ：與數(shù)據(jù)庫連接,輸入基本集合元素： setname/ODBC(datasource , tablename , columnname)/ 輸入派生集合元素： setname/ODBC(source,table , column1, column2)/,目前支持下列DBMS: (如為其他數(shù)據(jù)庫，則需自行安裝驅動) ACCESS， DBASE，EXCEL，F(xiàn)OXPRO，ORACLE， PARADOX，SQL SERVER， TEXE FILES,使用數(shù)據(jù)庫之前，數(shù)據(jù)源需要在ODBC管理器注冊,輸入數(shù)據(jù)： Attr_list=ODBC(source,table , column1, column2) 輸出數(shù)據(jù)： ODBC(source,table , column1, column2)= Attr_list,具體例子略,4. 建模與求解實例（結合軟件使用）,建模實例與求解,最短路問題 下料問題 飛機定位 露天礦的運輸問題 鋼管運輸問題 電力市場的堵塞管理,例 最短路問題,求各點到T的最短路,問題1. 如何下料最節(jié)省 ?,例 鋼管下料,問題2. 客戶增加需求：,節(jié)省的標準是什么？,由于采用不同切割模式太多，會增加生產和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)??？,按照客戶需要在一根原料鋼管上安排切割的一種組合。,切割模式,合理切割模式的余料應小于客戶需要鋼管的最小尺寸,鋼管下料,為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)??？,合理切割模式,2. 所用原料鋼管總根數(shù)最少,鋼管下料問題1,兩種標準,1. 原料鋼管剩余總余量最小,xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,7),約束,滿足需求,決策變量,目標1（總余量）,按模式2切割12根,按模式5切割15根，余料27米,最優(yōu)解：x2=12, x5=15, 其余為0； 最優(yōu)值：27,整數(shù)約束： xi 為整數(shù),當余料沒有用處時，通常以總根數(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的結果“共切割27根，余料27米” 相比,鋼管下料問題2,對大規(guī)模問題，用模型的約束條件界定合理模式,增加一種需求：5米10根；切割模式不超過3種。,現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復雜。,決策變量,xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,3),r1i, r2i, r3i, r4i 第i 種切割模式下，每根原料鋼管生產4米、5米、6米和8米長的鋼管的數(shù)量,滿足需求,模式合理：每根余料不超過3米,整數(shù)非線性規(guī)劃模型,鋼管下料問題2,目標函數(shù)（總根數(shù)）,約束條件,整數(shù)約束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)為整數(shù),增加約束，縮小可行域，便于求解,原料鋼管總根數(shù)下界：,特殊生產計劃：對每根原料鋼管 模式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米,LINGO求解整數(shù)非線性規(guī)劃模型,Local optimal solution found at iteration: 12211 Objective value: 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.000000 1.000000 R11 3.000000 0.000000 R12 2.000000 0.000000 R13 0.000000 0.000000 R21 0.000000 0.000000 R22 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.000000,模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根； 模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根； 模式3：每根原料鋼管切割成2根8米鋼管，共8根。 原料鋼管總根數(shù)為28根。,演示cut02a.lg4； cut02b.lg4,0,y,x,VOR2 x=629, y=375,309.00 (1.30),864.3(2.0),飛機 x=?, y=?,VOR1 x=764, y=1393,161.20 (0.80),VOR3 x=1571, y=259,45.10 (0.60),北,DME x=155, y=987,飛機與監(jiān)控臺（圖中坐標和測量距離的單位是“公里”）,實例: 飛機精確定位問題,飛機精確定位模型,飛機精確定位模型,第1類模型: 不考慮誤差因素,超定方程組， 非線性最小二乘！,量綱不符！ ？,飛機精確定位模型,第2類模型: 考慮誤差因素(作為硬約束),Min x; Min y; Max x; Max y.,以距離為約束，優(yōu)化角度誤差之和（或平方和）； 或以角度為約束，優(yōu)化距離誤差.,非線性規(guī)劃,？,？ 僅部分考慮誤差! 角度與距離的“地位”不應不同！,有人也可能會采用其他目標，如：,誤差非均勻分布！,飛機精確定位模型,誤差一般服從什么分布？,正態(tài)分布！,不同的量綱如何處理？,無約束非線性最小二乘模型,歸一化處理！,shili0702.m,飛機坐標(978.31，723.98), 誤差平方和0.6685 ( 4),角度需要進行預處理，如利用 Matlab的atan2函數(shù), 值域(-pi, pi),第3類模型: 考慮誤差因素(作為軟約束); 且歸一化,飛機精確定位模型,小技巧: LINGO中沒有atan2函數(shù), 怎么辦？,可以直接利用tan函數(shù)！,exam0507c.lg4,同前面的模型/結果,飛機坐標(980.21，727.30 ), 誤差平方和2.6 與前面的結果有所不同, 為什么? 哪個模型合理些?,最后: 思考以下模型:,exam0507d.lg4,露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘,卡車在等待時所耗費的能量也是相當可觀的，原則上在安排時不應發(fā)生卡車等待的情況。,露天礦生產的車輛安排(CUMCM-2003B),礦石卸點需要的鐵含量要求都為29.5%1%(品位限制），搭配量在一個班次（8小時）內滿足品位限制即可。卸點在一個