高級運籌學非線性規(guī)劃

1、高 級 運 籌 學Tel:83597002 123Prisoners Dilemma 4運籌學運籌學的研究對象可大致歸納為三類機器、設備、網絡、乃至系統(tǒng)的運用問題，即如何提高運作效率；擁擠現象：交通路口的車輛排隊、服務熱線、飛機著陸、船舶進港、網絡；競爭現象：人與自然的對策、人與人的對抗；5運籌學的分支數學規(guī)劃線性規(guī)劃 非線性規(guī)劃整數規(guī)劃 動態(tài)規(guī)劃圖與網絡流 網絡計劃庫存論排隊論對策論決策論6決策問題的分類確定性、靜態(tài)優(yōu)化問題數學規(guī)劃（單目標、多目標）圖與網絡流決策論（多目標）確定性、動態(tài)優(yōu)化問題動態(tài)規(guī)劃（離散）最優(yōu)控制（離散、連續(xù)）隨機性優(yōu)化問題存儲論排隊論決策論（單目標）多人競爭性決策問題

2、博弈論（對策論）7本課程的主要內容非線性規(guī)劃（一維無約束極值問題）決策論博弈論排隊論庫存論8非線性規(guī)劃問題一般數學描述 目標函數或約束函數中至少有一個是非線性的應用背景有著最廣泛的應用，應該說所有現實問題都是非線性的，線性模型都是經過簡化而來的。機械、電子等行業(yè)的器件最優(yōu)設計問題，如飛行器的結構優(yōu)化設計等；管理科學中的應用問題更是不勝枚舉；系統(tǒng)控制問題。9決策論（decision)著名經濟學家西蒙有一句名言：“管理就是決策”?！皼Q策”一詞本身是一個廣義的概念，本課程介紹的是針對在不確定或隨機環(huán)境下的決策分析方法。應用背景：產品開發(fā)決策問題、風險投資決策問題、開設連鎖店問題等等10博弈論（Gam

3、e Theory)11博弈論博弈論研究的問題是：當一個主體，如一個人或一個企業(yè)的選擇，受到其他人、其他企業(yè)選擇的影響，而且反過來又影響到其他人、其他企業(yè)選擇時的決策問題和均衡問題。博棄論又稱為“對策論”.博弈論可以解釋一些經濟和社會現象，比如家電的價格戰(zhàn)、民航業(yè)的價格戰(zhàn)、國家之間的軍備競賽、“劣幣逐良幣”等等現象。12排隊論銀行、醫(yī)院、機場跑道、港口碼頭、理發(fā)店、通信設備、交通路口等等的排隊現象；排隊論是運籌學的又一個分支，又叫做隨機服務系統(tǒng)理論。它的研究目的是要回答如何改進服務機構、或組織被服務的對象，使得某種指標達到最優(yōu)的問題。比如一個港口應該有多少個碼頭，一個工廠應該有多少維修人員等 。

4、13庫存論存儲物品的現象是為了解決供應（生產）與需求（消費）之間的不協(xié)調的一種措施；由此帶來一些需要決策的問題：庫存量、進貨量（如報童問題）、補貨的時間等等決策量?，F在也是供應鏈管理研究中的熱點問題。14運籌學會與雜志中國運籌學學會(ORSC)The Operations Research Society of China 網站:雜志:,美國運籌與管理學會(IFORMS)Institute for Operations Research and the Management Sciences英文網址： 中文網站： 雜志15Decision AnalysisInformation Systems

5、 ResearchINFORMS Journal on ComputingInterfacesManagement ScienceManufacturing & Service Operations ManagementMarketing ScienceMathematics of Operations ResearchOperations ResearchOrganization ScienceTransportation Science16運籌學軟件LINDO是一種專門用于求解數學規(guī)劃問題的軟件包。由于LINDO執(zhí)行速度很快、易于方便輸入、求解和分析數學規(guī)劃問題。因此在數學、科研和工業(yè)界得

6、到廣泛應用。LINDO主要用于解線性規(guī)劃、非線性規(guī)劃、二次規(guī)劃和整數規(guī)劃等問題。也可以用于一些非線性和線性方程組的求解以及代數方程求根等。LINDO中包含了一種建模語言和許多常用的數學函數，可供使用者建立規(guī)劃問題時調用。一般用LINDO（Linear Interactive and Discrete Optimizer）解決線性規(guī)劃（LPLinear Programming）。整數規(guī)劃（IPInteger Programming）問題。其中LINDO 6 .1 學生版至多可求解多達300個變量和150個約束的規(guī)劃問題。其正式版（標準版）則可求解的變量和約束在1量級以上。17LINGO則用于求解

7、非線性規(guī)劃（NLPNONLINEAR PROGRAMMING）和二次規(guī)則（QPQUARATIC PROGRAMING）其中LINGO 6.0學生版最多可版最多達300個變量和150個約束的規(guī)則問題，其標準版的求解能力亦再104量級以上。雖然LINDO和LINGO不能直接求解目標規(guī)劃問題,但用序貫式算法可分解成一個個LINDO和LINGO能解決的規(guī)劃問題。18非線性規(guī)劃Nonlinear Programming191.1 相關的數學知識一、一般數學描述可行域特別當R=En, 稱為無約束優(yōu)化問題201.1 相關的數學知識二、解的定義全局最優(yōu)解、嚴格全局最優(yōu)解；局部最優(yōu)解（極值點、極小點）三、多元函

8、數的偏導偏導數：指函數沿某個坐標軸方向的變化率；梯度：由各個坐標軸方向組成的向量；方向導數：指函數沿某個給定方向的變化率；常用的求梯度公式211.1 相關的數學知識四、Hessian 矩陣（二階導數矩陣）幾個常用的公式五、正定矩陣定義正定二次函數六、多元函數的Taylor展開221.1 相關的數學知識七、凸函數、凸規(guī)劃凸集(convex set)：凸函數(convex )、凹函數(concave)：定義幾何意義性質判別條件特別：線性函數既是凸函數也是凹函數。凸規(guī)劃(convex programming)231.2 解的最優(yōu)性條件一階必要條件在極值點的梯度=0二階充分條件二階導數矩陣為正定矩陣2

9、41.3下降搜索算法目標函數的等值線（二維，等高線）對二次函數，等值線是一族同心的橢圓；對于非二次函數，在極小點附近，等值線近似一族同心橢圓；具有不同值的等值線不相交；等值線稠密處目標函數變化快，稀疏處變化慢；等值線上一點的梯度與該點的的等值線切線方向相互垂直。251.3下降搜索算法算法：給定一個初始點X0，然后按照一定的規(guī)則產生一個點列Xk，這種產生點列的規(guī)則稱為算法；下降算法的規(guī)則：給定一個初始點X0 ，在點Xk選擇一個方向 (向量) Pk, 并沿此方向選擇一點Xk+1=Xk+tkPk使得f(Xk+1)f(Xk)。261.3下降搜索算法算法步驟中的關鍵要素：給定初始點；確定尋優(yōu)方向；確定一

10、個步長；判別是否滿足終止條件271.4 一維尋優(yōu)方法The One-Dimensional Search Procedure28 一、“成功-失敗”法基本思想“成功”則大步向前，“失敗”則小步后退?？驁D特點簡單易行，對初始點選擇無嚴格限制；適用于不可微的函數；在極小點附近收斂慢；可用此方法來確定一個搜索區(qū)間。29二、牛頓法（切線法）基本思想：適合二階連續(xù)可微的函數，求導數為0的方程根。迭代公式算法步驟特點適用于二階可微函數；最快的收斂速度，二階收斂速度；初始點要求接近極小點；可與“成功-失敗”法聯合使用。30序貫實驗法單峰函數（Unimodal Function,下單峰、單谷) 定義（在極小點

11、左邊單調下降，右邊單調上升）性質( Unimodality，單峰性)基本思想：通過選擇實驗點，計算其函數值，比較實驗點的函數值大小，縮小包含極值點的區(qū)間31二分搜索法The Dichotomy Method without Derivatives基本思想對稱取點，等比例縮小區(qū)間特點：簡單對稱取點，不論取哪個區(qū)間，其長度相等；每次要計算兩次函數值32黃金分割法（0.618法)The Golden Section Search Method基本思想：對稱取點，等比例的縮小區(qū)間，除第一次外，每次只需計算一次函數值，可使區(qū)間縮小。b0a0t11t12b1a1f(t11)f(t12)t22t2133黃金

12、分割法（0.618法)The Golden Section Search Method實驗點的計算公式算法步驟特點：具有相同的區(qū)間縮短率0.618；精度不如Fobonacci分數法；適用于不可微、不連續(xù)函數，可以先用“成功-失敗”法搜索到一個包含極小點的區(qū)間。34Fibonacci分數法The Fibonacci Search Method基本思想對稱取點，利用上次已有的實驗點的函數值；如何選擇實驗點，計算n次函數值能得到多大的區(qū)間縮短率？換句話說，計算n次函數值能將多大的區(qū)間縮短到1。35Fibonacci分數法Fibonacci 數列 (Fibonacci Sequence) F0=1,

13、F1=1, F2=2, F3=5, F4=8, Fk=Fk-1+Fk-2實驗點的計算公式計算步驟算例36Fibonacci 分數法特點：需要預先確定迭代次數n;在計算n次函數值情況下，該方法獲得最大的區(qū)間縮短率，精度最高；適用于不可微、不連續(xù)函數。37作業(yè)P196, 6.13, 6.14381.5 多維無約束尋優(yōu)方法The Multi-Dimensional Search Procedure39下降搜索算法下降算法的規(guī)則：給定一個初始點X0 ，在點Xk選擇一個方向 (向量) Pk, 并沿此方向選擇一點Xk+1=Xk+tkPk使得f(Xk+1)f(Xk)。不同的尋優(yōu)方向選擇方法構成不同的算法；有

14、兩類方法：解析法利用函數的梯度來構造尋優(yōu)方向；直接法利用函數值來構造尋優(yōu)方向；40最速下降法（梯度法）The Steepest descent method The Gradient Method基本思想：以負梯度方向作為尋優(yōu)方向算法步驟：特點：迭代過程簡單，存儲量少，計算量??；即使是正定二次函數也不能有限步收斂；相鄰兩次尋優(yōu)方向是垂直的;尋優(yōu)路線呈鋸齒狀（Zig-Zag)，在極小點附近收斂緩慢;41X0P0P1X1X2P2P3X3X*X442其他解析算法共軛梯度法(Conjugate gradient method) 牛頓法（Newtons method) 變尺度法 （Variable Me

15、tric Method) （擬牛頓法Quasi-Newton method）43有約束優(yōu)化問題的算法解的最優(yōu)性條件Kuhn-Tucker 條件求解算法直接法：可行方向法，梯度投影法等間接法：將有約束問題轉換成一系列的無約束問題來求解，如懲罰函數法，乘子法等44新算法模擬退火算法（Simulating anneal algorithm)模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變?yōu)闊o序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小。用固體退火模擬組合優(yōu)化問題，將內能E模擬為目標函數值f，溫度T

16、演化成控制參數t，即得到解組合優(yōu)化問題的模擬退火算法。 45新算法遺傳算法 (Genetic algorithm)遺傳算法是模擬達爾文的自然選擇學說和自然界的生物進化過程的一種計算模型。它采用簡單的編碼技術來表示各種復雜的結構，并通過對一組編碼表示進行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導學習和確定搜索的方向。一種新型的、隨機性的全局優(yōu)化方法 46新算法粒子群算法 (particle group algorithm)90年代中期,Eberhan博士和Kennedy博士共同發(fā)明了一種新的群體智能計算技術粒子群優(yōu)化算法(Padicle.行為的研究.粒子群優(yōu)化算法的基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解;粒子群優(yōu)化算法是基于一群粒子的智能運動而產生的隨機進化計算方法,其優(yōu)點是算法非常利于理解和應用.47新算法蟻群