高級運籌學非線性規劃第一頁，共四十九頁，2022年，8月28日

第二頁，共四十九頁，2022年，8月28日

第三頁，共四十九頁，2022年，8月28日

Prisoner’sDilemma第四頁，共四十九頁，2022年，8月28日

運籌學運籌學的研究對象可大致歸納為三類機器、設備、網絡、乃至系統的運用問題，即如何提高運作效率；擁擠現象：交通路口的車輛排隊、服務熱線、飛機著陸、船舶進港、網絡；競爭現象：人與自然的對策、人與人的對抗；第五頁，共四十九頁，2022年，8月28日

運籌學的分支數學規劃線性規劃√非線性規劃整數規劃√動態規劃圖與網絡流√網絡計劃庫存論排隊論對策論決策論第六頁，共四十九頁，2022年，8月28日

決策問題的分類確定性、靜態優化問題數學規劃（單目標、多目標）圖與網絡流決策論（多目標）確定性、動態優化問題動態規劃（離散）最優控制（離散、連續）隨機性優化問題存儲論排隊論決策論（單目標）多人競爭性決策問題博弈論（對策論）第七頁，共四十九頁，2022年，8月28日

本課程的主要內容非線性規劃（一維無約束極值問題）決策論博弈論排隊論庫存論第八頁，共四十九頁，2022年，8月28日

非線性規劃問題一般數學描述

目標函數或約束函數中至少有一個是非線性的應用背景有著最廣泛的應用，應該說所有現實問題都是非線性的，線性模型都是經過簡化而來的。機械、電子等行業的器件最優設計問題，如飛行器的結構優化設計等；管理科學中的應用問題更是不勝枚舉；系統控制問題。第九頁，共四十九頁，2022年，8月28日

決策論（decision)著名經濟學家西蒙有一句名言：“管理就是決策”。“決策”一詞本身是一個廣義的概念，本課程介紹的是針對在不確定或隨機環境下的決策分析方法。應用背景：產品開發決策問題、風險投資決策問題、開設連鎖店問題等等第十頁，共四十九頁，2022年，8月28日

博弈論（GameTheory)

第十一頁，共四十九頁，2022年，8月28日

博弈論博弈論研究的問題是：當一個主體，如一個人或一個企業的選擇，受到其他人、其他企業選擇的影響，而且反過來又影響到其他人、其他企業選擇時的決策問題和均衡問題。博棄論又稱為“對策論”.博弈論可以解釋一些經濟和社會現象，比如家電的價格戰、民航業的價格戰、國家之間的軍備競賽、“劣幣逐良幣”等等現象。第十二頁，共四十九頁，2022年，8月28日

排隊論銀行、醫院、機場跑道、港口碼頭、理發店、通信設備、交通路口等等的排隊現象；排隊論是運籌學的又一個分支，又叫做隨機服務系統理論。它的研究目的是要回答如何改進服務機構、或組織被服務的對象，使得某種指標達到最優的問題。比如一個港口應該有多少個碼頭，一個工廠應該有多少維修人員等。第十三頁，共四十九頁，2022年，8月28日

庫存論存儲物品的現象是為了解決供應（生產）與需求（消費）之間的不協調的一種措施；由此帶來一些需要決策的問題：庫存量、進貨量（如報童問題）、補貨的時間等等決策量。現在也是供應鏈管理研究中的熱點問題。第十四頁，共四十九頁，2022年，8月28日

運籌學會與雜志中國運籌學學會(ORSC)TheOperationsResearchSocietyofChina網站雜志:<運籌學學報>,<運籌與管理>美國運籌與管理學會(IFORMS)InstituteforOperationsResearchandtheManagementSciences英文網址：

中文網站：

雜志第十五頁，共四十九頁，2022年，8月28日

DecisionAnalysisInformationSystemsResearchINFORMSJournalonComputingInterfacesManagementScienceManufacturing&ServiceOperationsManagementMarketingScienceMathematicsofOperationsResearchOperationsResearchOrganizationScienceTransportationScience第十六頁，共四十九頁，2022年，8月28日

運籌學軟件LINDO是一種專門用于求解數學規劃問題的軟件包。由于LINDO執行速度很快、易于方便輸入、求解和分析數學規劃問題。因此在數學、科研和工業界得到廣泛應用。LINDO主要用于解線性規劃、非線性規劃、二次規劃和整數規劃等問題。也可以用于一些非線性和線性方程組的求解以及代數方程求根等。LINDO中包含了一種建模語言和許多常用的數學函數，可供使用者建立規劃問題時調用。

一般用LINDO（LinearInteractiveandDiscreteOptimizer）解決線性規劃（LP—LinearProgramming）。整數規劃（IP—IntegerProgramming）問題。其中LINDO6.1學生版至多可求解多達300個變量和150個約束的規劃問題。其正式版（標準版）則可求解的變量和約束在1量級以上。第十七頁，共四十九頁，2022年，8月28日

LINGO則用于求解非線性規劃（NLP—NON—LINEARPROGRAMMING）和二次規則（QP—QUARATICPROGRAMING）其中LINGO6.0學生版最多可版最多達300個變量和150個約束的規則問題，其標準版的求解能力亦再10^4量級以上。雖然LINDO和LINGO不能直接求解目標規劃問題,但用序貫式算法可分解成一個個LINDO和LINGO能解決的規劃問題。

第十八頁，共四十九頁，2022年，8月28日非線性規劃NonlinearProgramming第十九頁，共四十九頁，2022年，8月28日

1.1相關的數學知識一、一般數學描述可行域特別當R=En,稱為無約束優化問題第二十頁，共四十九頁，2022年，8月28日

1.1相關的數學知識二、解的定義全局最優解、嚴格全局最優解；局部最優解（極值點、極小點）三、多元函數的偏導偏導數：指函數沿某個坐標軸方向的變化率；梯度：由各個坐標軸方向組成的向量；方向導數：指函數沿某個給定方向的變化率；常用的求梯度公式第二十一頁，共四十九頁，2022年，8月28日

1.1相關的數學知識四、Hessian矩陣（二階導數矩陣）幾個常用的公式五、正定矩陣定義正定二次函數六、多元函數的Taylor展開第二十二頁，共四十九頁，2022年，8月28日

1.1相關的數學知識七、凸函數、凸規劃凸集(convexset)：凸函數(convex)、凹函數(concave)：定義幾何意義性質判別條件特別：線性函數既是凸函數也是凹函數。凸規劃(convexprogramming)第二十三頁，共四十九頁，2022年，8月28日

1.2解的最優性條件一階必要條件在極值點的梯度=0二階充分條件二階導數矩陣為正定矩陣第二十四頁，共四十九頁，2022年，8月28日

1.3下降搜索算法目標函數的等值線（二維，等高線）對二次函數，等值線是一族同心的橢圓；對于非二次函數，在極小點附近，等值線近似一族同心橢圓；具有不同值的等值線不相交；等值線稠密處目標函數變化快，稀疏處變化慢；等值線上一點的梯度與該點的的等值線切線方向相互垂直。第二十五頁，共四十九頁，2022年，8月28日

1.3下降搜索算法算法：給定一個初始點X0，然后按照一定的規則產生一個點列{Xk}，這種產生點列的規則稱為算法；下降算法的規則：給定一個初始點X0，在點Xk選擇一個方向(向量)Pk,并沿此方向選擇一點Xk+1=Xk+tkPk使得f(Xk+1)<f(Xk)。第二十六頁，共四十九頁，2022年，8月28日

1.3下降搜索算法算法步驟中的關鍵要素：給定初始點；確定尋優方向；確定一個步長；判別是否滿足終止條件第二十七頁，共四十九頁，2022年，8月28日1.4一維尋優方法TheOne-DimensionalSearchProcedure第二十八頁，共四十九頁，2022年，8月28日

一、“成功-失敗”法基本思想“成功”則大步向前，“失敗”則小步后退。框圖特點簡單易行，對初始點選擇無嚴格限制；適用于不可微的函數；在極小點附近收斂慢；可用此方法來確定一個搜索區間。第二十九頁，共四十九頁，2022年，8月28日

二、牛頓法（切線法）基本思想：適合二階連續可微的函數，求導數為0的方程根。迭代公式算法步驟特點適用于二階可微函數；最快的收斂速度，二階收斂速度；初始點要求接近極小點；可與“成功-失敗”法聯合使用。第三十頁，共四十九頁，2022年，8月28日

序貫實驗法單峰函數（UnimodalFunction,下單峰、單谷)

定義（在極小點左邊單調下降，右邊單調上升）性質(Unimodality，單峰性)基本思想：通過選擇實驗點，計算其函數值，比較實驗點的函數值大小，縮小包含極值點的區間第三十一頁，共四十九頁，2022年，8月28日

二分搜索法

TheDichotomyMethodwithoutDerivatives基本思想對稱取點，等比例縮小區間特點：簡單對稱取點，不論取哪個區間，其長度相等；每次要計算兩次函數值第三十二頁，共四十九頁，2022年，8月28日

黃金分割法（0.618法)

TheGoldenSectionSearchMethod基本思想：對稱取點，等比例的縮小區間，除第一次外，每次只需計算一次函數值，可使區間縮小。b0a0t11t12b1a1f(t11)<f(t12)t22t21第三十三頁，共四十九頁，2022年，8月28日

黃金分割法（0.618法)

TheGoldenSectionSearchMethod實驗點的計算公式算法步驟特點：具有相同的區間縮短率0.618；精度不如Fobonacci分數法；適用于不可微、不連續函數，可以先用“成功-失敗”法搜索到一個包含極小點的區間。第三十四頁，共四十九頁，2022年，8月28日

Fibonacci分數法

TheFibonacciSearchMethod基本思想對稱取點，利用上次已有的實驗點的函數值；如何選擇實驗點，計算n次函數值能得到多大的區間縮短率？換句話說，計算n次函數值能將多大的區間縮短到1。第三十五頁，共四十九頁，2022年，8月28日

Fibonacci分數法Fibonacci數列(FibonacciSequence)F0=1,F1=1,F2=2,F3=5,F4=8,……Fk=Fk-1+Fk-2實驗點的計算公式計算步驟算例第三十六頁，共四十九頁，2022年，8月28日

Fibonacci分數法特點：需要預先確定迭代次數n;在計算n次函數值情況下，該方法獲得最大的區間縮短率，精度最高；適用于不可微、不連續函數。第三十七頁，共四十九頁，2022年，8月28日

作業P196,6.13,6.14第三十八頁，共四十九頁，2022年，8月28日1.5多維無約束尋優方法TheMulti-DimensionalSearchProcedure第三十九頁，共四十九頁，2022年，8月28日

下降搜索算法下降算法的規則：給定一個初始點X0，在點Xk選擇一個方向(向量)Pk,并沿此方向選擇一點Xk+1=Xk+tkPk使得f(Xk+1)<f(Xk)。不同的尋優方向選擇方法構成不同的算法；有兩類方法：解析法——利用函數的梯度來構造尋優方向；直接法——利用函數值來構造尋優方向；第四十頁，共四十九頁，2022年，8月28日

最速下降法（梯度法）

TheSteepestdescentmethod

TheGradientMethod基本思想：以負梯度方向作為尋優方向算法步驟：特點：迭代過程簡單，存儲量少，計算量小；即使是正定二次函數也不能有限步收斂；相鄰兩次尋優方向是垂直的;尋優路線呈鋸齒狀（Zig-Zag)，在極小點附近收斂緩慢;第四十一頁，共四十九頁，2022年，8月28日

X0P0P1X1X2P2P3X3X*X4第四十二頁，共四十九頁，2022年，8月28日

其他解析算法共軛梯度法(Conjugategradientmethod)牛頓法（Newton’smethod)

變尺度法（VariableMetricMethod)（擬牛頓法Quasi-Newtonmethod）第四十三頁，共四十九頁，2022年，8月28日

有約束優化問題的算法解的最優性條件Kuhn-Tucker條件求解算法直接法：可行方向法，梯度投影法等間接法：將有約束問題轉換成一系列的無約束問題來求解，如懲罰函數法，乘子法等第四十四頁，共四十九頁，2022年，8月28日

新算法模擬退火算法（Simulatingannealalgorithm)模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火算法。

第四十五頁，共四十九頁，2022年，8月28日

新算法遺傳算法(Geneticalgorithm)遺傳算法是模擬達爾文的自然選擇學說和自然界的生物進化過程的一種計算