優(yōu)化建模與LINGO第01章

1、優(yōu)化建模與LINDO/LINGO軟件 第1章引言,原書相關信息 謝金星, 薛毅編著, 清華大學出版社, 2005年7月第1版. ,內(nèi)容提要,1. 優(yōu)化模型的基本概念 2. 優(yōu)化問題的建模實例 3. LINDO/LINGO 軟件簡介,1. 優(yōu)化模型的基本概念,最優(yōu)化是工程技術、經(jīng)濟管理、科學研究、社會生活中經(jīng)常遇到的問題, 如:,優(yōu)化模型和算法的重要意義,結構設計,資源分配,生產(chǎn)計劃,運輸方案,解決優(yōu)化問題的手段,經(jīng)驗積累，主觀判斷,作試驗，比優(yōu)劣,建立數(shù)學模型，求解最優(yōu)策略,最優(yōu)化: 在一定條件下，尋求使目標最大(小)的決策,優(yōu)化問題三要素：決策變量；目標函數(shù)；約束條件,優(yōu)化問題的一般形式,無

2、約束優(yōu)化(沒有約束)與約束優(yōu)化(有約束) 可行解（只滿足約束）與最優(yōu)解(取到最優(yōu)值),局部最優(yōu)解與整體最優(yōu)解,局部最優(yōu)解 (Local Optimal Solution, 如 x1 ) 整體最優(yōu)解 (Global Optimal Solution, 如 x2 ),優(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ù)）

3、規(guī)劃,連續(xù)優(yōu)化,離散優(yōu)化,數(shù)學規(guī)劃,優(yōu)化模型的簡單分類和求解難度,優(yōu)化,線性規(guī)劃,非線性規(guī)劃,二次規(guī)劃,連續(xù)優(yōu)化,整數(shù)規(guī)劃,問題求解的難度增加,2. 優(yōu)化問題的建模實例,50桶牛奶,時間480小時,至多加工100公斤A1,制訂生產(chǎn)計劃，使每天獲利最大,35元可買到1桶牛奶，買嗎？若買，每天最多買多少?,可聘用臨時工人，付出的工資最多是每小時幾元?,A1的獲利增加到 30元/公斤，應否改變生產(chǎn)計劃？,每天：,線性規(guī)劃模型例1.1: 奶制品生產(chǎn)計劃,x1桶牛奶生產(chǎn)A1,x2桶牛奶生產(chǎn)A2,獲利 243x1,獲利 164 x2,原料供應,勞動時間,加工能力,決策變量,目標函數(shù),每天獲利,約束條件,非

4、負約束,線性規(guī)劃模型(LP),時間480小時,至多加工100公斤A1,模型分析與假設,比例性,可加性,連續(xù)性,xi對目標函數(shù)的“貢獻”與xi取值成正比,xi對約束條件的“貢獻”與xi取值成正比,xi對目標函數(shù)的“貢獻”與xj取值無關,xi對約束條件的“貢獻”與xj取值無關,xi取值連續(xù),A1,A2每公斤的獲利是與各自產(chǎn)量無關的常數(shù),每桶牛奶加工出A1,A2的數(shù)量和時間是與各自產(chǎn)量無關的常數(shù),A1,A2每公斤的獲利是與相互產(chǎn)量無關的常數(shù),每桶牛奶加工出A1,A2的數(shù)量和時間是與相互產(chǎn)量無關的常數(shù),加工A1,A2的牛奶桶數(shù)是實數(shù),線性規(guī)劃模型,模型求解,圖解法,約束條件,目標函數(shù),z=c (常數(shù))

5、 等值線,在B(20,30)點得到最優(yōu)解,目標函數(shù)和約束條件是線性函數(shù),可行域為直線段圍成的凸多邊形,目標函數(shù)的等值線為直線,最優(yōu)解一定在凸多邊形的某個頂點取得。,求解LP的基本思想,思路：從可行域的某一頂點開始，只需在有限多個頂點中一個一個找下去，一定能得到最優(yōu)解。,LP的約束和目標函數(shù)均為線性函數(shù),2維,可行域 線段組成的凸多邊形,目標函數(shù) 等值線為直線,最優(yōu)解 凸多邊形的某個頂點,n維,超平面組成的凸多面體,等值線是超平面,凸多面體的某個頂點,LP的通常解法是單純形法(G. B. Dantzig, 1947),內(nèi)點算法(Interior point method) 20世紀80年代人們提

6、出的一類新的算法內(nèi)點算法 也是迭代法，但不再從可行域的一個頂點轉換到另一個頂點，而是直接從可行域的內(nèi)部逼近最優(yōu)解。,LP其他算法,有效集(Active Set)方法 LP是QP的特例（只需令所有二次項為零即可） 可以用QP的算法解QP(如: 有效集方法),線性規(guī)劃模型的解的幾種情況,某廠生產(chǎn)兩個牌號的同一種產(chǎn)品，如何確定產(chǎn)量使利潤最大,二次規(guī)劃模型例1.2：產(chǎn)銷計劃問題,=（100-x1-0.1 x2-2）x1 +（280-0.2x1-2x2-3）x2 =98 x1 + 277 x2 x12 0.3 x1 x2 2x22,約束,x1 + x2 100 x1 2 x2 x1 , x2 0,二次規(guī)

7、劃模型(QP),若還要求產(chǎn)量為整數(shù)，則是整數(shù)二次規(guī)劃模型(IQP),非線性規(guī)劃模型例1.3：選址問題,某公司有6個建筑工地，位置坐標為(ai, bi) (單位：公里),水泥日用量di (單位：噸）,假設：料場和工地之間有直線道路,用例中數(shù)據(jù)計算，最優(yōu)解為,總噸公里數(shù)為136.2,線性規(guī)劃模型(LP),決策變量：ci j (料場j到工地i的運量）12維,選址問題：NLP,2）改建兩個新料場，需要確定新料場位置(xj,yj)和運量cij ，在其它條件不變下使總噸公里數(shù)最小。,決策變量： ci j，(xj,yj)16維,非線性規(guī)劃模型 (NLP),整數(shù)規(guī)劃 - 例1.4: 聘用方案,決策變量：周一至

8、周日每天(新)聘用人數(shù) x1, x2,x7,目標函數(shù)：7天(新)聘用人數(shù)之和,約束條件：周一至周日每天需要人數(shù),連續(xù)工作5天,設系統(tǒng)已進入穩(wěn)態(tài)（不是開始的幾周）,聘用方案,整數(shù)規(guī)劃 模型(IP),丁的蛙泳成績退步到115”2；戊的自由泳成績進步到57”5, 組成接力隊的方案是否應該調(diào)整？,如何選拔隊員組成4100米混合泳接力隊?,0-1規(guī)劃 混合泳接力隊的選拔,例1.5： 5名候選人的百米成績,窮舉法：組成接力隊的方案共有5!=120種。,目標函數(shù),若選擇隊員i參加泳姿j 的比賽，記xij=1, 否則記xij=0,0-1規(guī)劃模型,cij(秒)隊員i 第j 種泳姿的百米成績,約束條件,每人最多入

9、選泳姿之一,每種泳姿有且只有1人,0-1規(guī)劃: 整數(shù)規(guī)劃的特例,整數(shù)規(guī)劃問題一般形式,整數(shù)線性規(guī)劃(ILP) 目標和約束均為線性函數(shù) 整數(shù)非線性規(guī)劃(NLP) 目標或約束中存在非線性函數(shù),整數(shù)規(guī)劃問題的分類,純(全)整數(shù)規(guī)劃(PIP) 決策變量均為整數(shù) 混合整數(shù)規(guī)劃(MIP) 決策變量有整數(shù)，也有實數(shù),0-1規(guī)劃 決策變量只取0或1,取消整數(shù)規(guī)劃中決策變量為整數(shù)的限制（松弛），對應的連續(xù)優(yōu)化問題稱為原問題的松弛問題,整數(shù)規(guī)劃問題對應的松弛問題,下界（對Min問題） 上界（對Max問題）,用連續(xù)優(yōu)化方法求解松弛問題，如果松弛問題最優(yōu)解（分量）全為整數(shù)，則也是原整數(shù)規(guī)劃問題的最優(yōu)解,對松弛問題的最

10、優(yōu)解（分量）舍入為整數(shù)，得到的往往不是原整數(shù)規(guī)劃問題的最優(yōu)解（甚至不是可行解）,IP可行解對應于整點A(2,2)和B(1,1),而最優(yōu)解為A點. 但LP松弛的最優(yōu)解為C(3.5,2.5),去掉整數(shù)限制后，可行域為點（0,0), (6,0), (0,5), P (2.25,3.75) 圍成的4邊形,從LP最優(yōu)解經(jīng)過簡單的 “移動”不一定能得到IP最優(yōu)解,例1.6,基本思想：隱式地枚舉一切可行解（“分而治之”）,所謂分枝，就是逐次對解空間（可行域）進行劃分；而所謂定界，是指對于每個分枝（或稱子域），要計算原問題的最優(yōu)解的下界（對極小化問題）. 這些下界用來在求解過程中判定是否需要對目前的分枝進一步

11、劃分，也就是盡可能去掉一些明顯的非最優(yōu)點，避免完全枚舉.,分枝定界法（B&B: Branch and Bound）,對于極小化問題，在子域上解LP，其最優(yōu)值是IP限定在該子域時的下界；IP任意可行點的函數(shù)值是IP的上界。,這里僅介紹整數(shù)線性規(guī)劃的分枝定界算法,無約束優(yōu)化,更多的優(yōu)化問題,線性規(guī)劃,非線性規(guī)劃,網(wǎng)絡優(yōu)化,組合優(yōu)化,整數(shù)規(guī)劃,不確定規(guī)劃,多目標規(guī)劃,目標規(guī)劃,動態(tài)規(guī)劃,連續(xù)優(yōu)化,離散優(yōu)化,從其他角度分類,應用廣泛：生產(chǎn)和運作管理、經(jīng)濟與金融、圖論和網(wǎng)絡優(yōu)化、目標規(guī)劃問題、對策論、排隊論、存儲論，以及更加綜合、更加復雜的決策問題等 實際問題規(guī)模往往較大，用軟件求解比較方便,3. LI

12、NDO/LINGO軟件簡介,常用優(yōu)化軟件,1. LINDO/LINGO軟件 2. MATLAB優(yōu)化工具箱 / Mathematic的優(yōu)化功能 3. SAS(統(tǒng)計分析)軟件的優(yōu)化功能 4. EXCEL軟件的優(yōu)化功能 5. 其他（如CPLEX等）,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

13、-1規(guī)劃 bintprog 一般IP(暫缺),非線性規(guī)劃 fmincon fminimax fgoalattain fseminf,上下界約束 fminbnd fmincon lsqnonlin lsqcurvefit,約束線性 最小二乘 lsqnonneg lsqlin,約束優(yōu)化,二次規(guī)劃 quadprog,LINDO 公司軟件產(chǎn)品簡要介紹,美國芝加哥(Chicago)大學的Linus Schrage教授于1980年前后開發(fā), 后來成立 LINDO系統(tǒng)公司（LINDO Systems Inc.）， 網(wǎng)址：,LINDO: Linear INteractive and Discrete Opti

14、mizer (V6.1) LINDO API: LINDO Application Programming Interface (V4.1) LINGO: Linear INteractive General Optimizer (V10.0) Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0),演示(試用)版、高級版、超級版、工業(yè)版、擴展版 （求解問題規(guī)模和選件不同）,LINDO/LINGO軟件能求解的模型,優(yōu)化,線性規(guī)劃,非線性規(guī)劃,二次規(guī)劃,連續(xù)優(yōu)化,整數(shù)規(guī)劃,LINDO,LINGO,LINGO軟件的功能與特點,LINGO模型的優(yōu)點,集成了線性(非線性) / 連續(xù)(整數(shù)) 優(yōu)化功能 具有多點搜索 / 全局優(yōu)化功能 提供了靈活的編程語言(矩陣生成器)，可方便地輸入模型 提供與其他數(shù)據(jù)文件的接口 提供與其他編程語言的接口 LINDO API 可用于自主開發(fā) 運行速度較快,LP QP NLP IP 全局優(yōu)化(選) ILP IQP INLP,LINGO軟件的求解過程,LINGO預處理程序,線性優(yōu)化求解程序,非線性優(yōu)化求解程序,分枝定界管理程序,1. 確定常數(shù) 2. 識別類型,1. 單純形算法 2. 內(nèi)點算法(選),1、順序線性規(guī)劃法(SLP) 2、廣義既約梯度法(GRG) (選) 3、多點搜索(Multistart