高級運籌學(xué)非線性規(guī)劃第一頁，共四十九頁，編輯于2023年，星期六

第二頁，共四十九頁，編輯于2023年，星期六

第三頁，共四十九頁，編輯于2023年，星期六

Prisoner’sDilemma第四頁，共四十九頁，編輯于2023年，星期六

運籌學(xué)運籌學(xué)的研究對象可大致歸納為三類機器、設(shè)備、網(wǎng)絡(luò)、乃至系統(tǒng)的運用問題，即如何提高運作效率；擁擠現(xiàn)象：交通路口的車輛排隊、服務(wù)熱線、飛機著陸、船舶進港、網(wǎng)絡(luò)；競爭現(xiàn)象：人與自然的對策、人與人的對抗；第五頁，共四十九頁，編輯于2023年，星期六

運籌學(xué)的分支數(shù)學(xué)規(guī)劃線性規(guī)劃√非線性規(guī)劃整數(shù)規(guī)劃√動態(tài)規(guī)劃圖與網(wǎng)絡(luò)流√網(wǎng)絡(luò)計劃庫存論排隊論對策論決策論第六頁，共四十九頁，編輯于2023年，星期六

決策問題的分類確定性、靜態(tài)優(yōu)化問題數(shù)學(xué)規(guī)劃（單目標(biāo)、多目標(biāo)）圖與網(wǎng)絡(luò)流決策論（多目標(biāo)）確定性、動態(tài)優(yōu)化問題動態(tài)規(guī)劃（離散）最優(yōu)控制（離散、連續(xù)）隨機性優(yōu)化問題存儲論排隊論決策論（單目標(biāo)）多人競爭性決策問題博弈論（對策論）第七頁，共四十九頁，編輯于2023年，星期六

本課程的主要內(nèi)容非線性規(guī)劃（一維無約束極值問題）決策論博弈論排隊論庫存論第八頁，共四十九頁，編輯于2023年，星期六

非線性規(guī)劃問題一般數(shù)學(xué)描述

目標(biāo)函數(shù)或約束函數(shù)中至少有一個是非線性的應(yīng)用背景有著最廣泛的應(yīng)用，應(yīng)該說所有現(xiàn)實問題都是非線性的，線性模型都是經(jīng)過簡化而來的。機械、電子等行業(yè)的器件最優(yōu)設(shè)計問題，如飛行器的結(jié)構(gòu)優(yōu)化設(shè)計等；管理科學(xué)中的應(yīng)用問題更是不勝枚舉；系統(tǒng)控制問題。第九頁，共四十九頁，編輯于2023年，星期六

決策論（decision)著名經(jīng)濟學(xué)家西蒙有一句名言：“管理就是決策”?！皼Q策”一詞本身是一個廣義的概念，本課程介紹的是針對在不確定或隨機環(huán)境下的決策分析方法。應(yīng)用背景：產(chǎn)品開發(fā)決策問題、風(fēng)險投資決策問題、開設(shè)連鎖店問題等等第十頁，共四十九頁，編輯于2023年，星期六

博弈論（GameTheory)

第十一頁，共四十九頁，編輯于2023年，星期六

博弈論博弈論研究的問題是：當(dāng)一個主體，如一個人或一個企業(yè)的選擇，受到其他人、其他企業(yè)選擇的影響，而且反過來又影響到其他人、其他企業(yè)選擇時的決策問題和均衡問題。博棄論又稱為“對策論”.博弈論可以解釋一些經(jīng)濟和社會現(xiàn)象，比如家電的價格戰(zhàn)、民航業(yè)的價格戰(zhàn)、國家之間的軍備競賽、“劣幣逐良幣”等等現(xiàn)象。第十二頁，共四十九頁，編輯于2023年，星期六

排隊論銀行、醫(yī)院、機場跑道、港口碼頭、理發(fā)店、通信設(shè)備、交通路口等等的排隊現(xiàn)象；排隊論是運籌學(xué)的又一個分支，又叫做隨機服務(wù)系統(tǒng)理論。它的研究目的是要回答如何改進服務(wù)機構(gòu)、或組織被服務(wù)的對象，使得某種指標(biāo)達(dá)到最優(yōu)的問題。比如一個港口應(yīng)該有多少個碼頭，一個工廠應(yīng)該有多少維修人員等。第十三頁，共四十九頁，編輯于2023年，星期六

庫存論存儲物品的現(xiàn)象是為了解決供應(yīng)（生產(chǎn)）與需求（消費）之間的不協(xié)調(diào)的一種措施；由此帶來一些需要決策的問題：庫存量、進貨量（如報童問題）、補貨的時間等等決策量?，F(xiàn)在也是供應(yīng)鏈管理研究中的熱點問題。第十四頁，共四十九頁，編輯于2023年，星期六

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

中文網(wǎng)站：

雜志第十五頁，共四十九頁，編輯于2023年，星期六

DecisionAnalysisInformationSystemsResearchINFORMSJournalonComputingInterfacesManagementScienceManufacturing&ServiceOperationsManagementMarketingScienceMathematicsofOperationsResearchOperationsResearchOrganizationScienceTransportationScience第十六頁，共四十九頁，編輯于2023年，星期六

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

一般用LINDO（LinearInteractiveandDiscreteOptimizer）解決線性規(guī)劃（LP—LinearProgramming）。整數(shù)規(guī)劃（IP—IntegerProgramming）問題。其中LINDO6.1學(xué)生版至多可求解多達(dá)300個變量和150個約束的規(guī)劃問題。其正式版（標(biāo)準(zhǔn)版）則可求解的變量和約束在1量級以上。第十七頁，共四十九頁，編輯于2023年，星期六

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

第十八頁，共四十九頁，編輯于2023年，星期六非線性規(guī)劃NonlinearProgramming第十九頁，共四十九頁，編輯于2023年，星期六

1.1相關(guān)的數(shù)學(xué)知識一、一般數(shù)學(xué)描述可行域特別當(dāng)R=En,稱為無約束優(yōu)化問題第二十頁，共四十九頁，編輯于2023年，星期六

1.1相關(guān)的數(shù)學(xué)知識二、解的定義全局最優(yōu)解、嚴(yán)格全局最優(yōu)解；局部最優(yōu)解（極值點、極小點）三、多元函數(shù)的偏導(dǎo)偏導(dǎo)數(shù)：指函數(shù)沿某個坐標(biāo)軸方向的變化率；梯度：由各個坐標(biāo)軸方向組成的向量；方向?qū)?shù)：指函數(shù)沿某個給定方向的變化率；常用的求梯度公式第二十一頁，共四十九頁，編輯于2023年，星期六

1.1相關(guān)的數(shù)學(xué)知識四、Hessian矩陣（二階導(dǎo)數(shù)矩陣）幾個常用的公式五、正定矩陣定義正定二次函數(shù)六、多元函數(shù)的Taylor展開第二十二頁，共四十九頁，編輯于2023年，星期六

1.1相關(guān)的數(shù)學(xué)知識七、凸函數(shù)、凸規(guī)劃凸集(convexset)：凸函數(shù)(convex)、凹函數(shù)(concave)：定義幾何意義性質(zhì)判別條件特別：線性函數(shù)既是凸函數(shù)也是凹函數(shù)。凸規(guī)劃(convexprogramming)第二十三頁，共四十九頁，編輯于2023年，星期六

1.2解的最優(yōu)性條件一階必要條件在極值點的梯度=0二階充分條件二階導(dǎo)數(shù)矩陣為正定矩陣第二十四頁，共四十九頁，編輯于2023年，星期六

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

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

1.3下降搜索算法算法步驟中的關(guān)鍵要素：給定初始點；確定尋優(yōu)方向；確定一個步長；判別是否滿足終止條件第二十七頁，共四十九頁，編輯于2023年，星期六1.4一維尋優(yōu)方法TheOne-DimensionalSearchProcedure第二十八頁，共四十九頁，編輯于2023年，星期六

一、“成功-失敗”法基本思想“成功”則大步向前，“失敗”則小步后退?？驁D特點簡單易行，對初始點選擇無嚴(yán)格限制；適用于不可微的函數(shù)；在極小點附近收斂慢；可用此方法來確定一個搜索區(qū)間。第二十九頁，共四十九頁，編輯于2023年，星期六

二、牛頓法（切線法）基本思想：適合二階連續(xù)可微的函數(shù)，求導(dǎo)數(shù)為0的方程根。迭代公式算法步驟特點適用于二階可微函數(shù)；最快的收斂速度，二階收斂速度；初始點要求接近極小點；可與“成功-失敗”法聯(lián)合使用。第三十頁，共四十九頁，編輯于2023年，星期六

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

定義（在極小點左邊單調(diào)下降，右邊單調(diào)上升）性質(zhì)(Unimodality，單峰性)基本思想：通過選擇實驗點，計算其函數(shù)值，比較實驗點的函數(shù)值大小，縮小包含極值點的區(qū)間第三十一頁，共四十九頁，編輯于2023年，星期六

二分搜索法

TheDichotomyMethodwithoutDerivatives基本思想對稱取點，等比例縮小區(qū)間特點：簡單對稱取點，不論取哪個區(qū)間，其長度相等；每次要計算兩次函數(shù)值第三十二頁，共四十九頁，編輯于2023年，星期六

黃金分割法（0.618法)

TheGoldenSectionSearchMethod基本思想：對稱取點，等比例的縮小區(qū)間，除第一次外，每次只需計算一次函數(shù)值，可使區(qū)間縮小。b0a0t11t12b1a1f(t11)<f(t12)t22t21第三十三頁，共四十九頁，編輯于2023年，星期六

黃金分割法（0.618法)

TheGoldenSectionSearchMethod實驗點的計算公式算法步驟特點：具有相同的區(qū)間縮短率0.618；精度不如Fobonacci分?jǐn)?shù)法；適用于不可微、不連續(xù)函數(shù)，可以先用“成功-失敗”法搜索到一個包含極小點的區(qū)間。第三十四頁，共四十九頁，編輯于2023年，星期六

Fibonacci分?jǐn)?shù)法

TheFibonacciSearchMethod基本思想對稱取點，利用上次已有的實驗點的函數(shù)值；如何選擇實驗點，計算n次函數(shù)值能得到多大的區(qū)間縮短率？換句話說，計算n次函數(shù)值能將多大的區(qū)間縮短到1。第三十五頁，共四十九頁，編輯于2023年，星期六

Fibonacci分?jǐn)?shù)法Fibonacci數(shù)列(FibonacciSequence)F0=1,F1=1,F2=2,F3=5,F4=8,……Fk=Fk-1+Fk-2實驗點的計算公式計算步驟算例第三十六頁，共四十九頁，編輯于2023年，星期六

Fibonacci分?jǐn)?shù)法特點：需要預(yù)先確定迭代次數(shù)n;在計算n次函數(shù)值情況下，該方法獲得最大的區(qū)間縮短率，精度最高；適用于不可微、不連續(xù)函數(shù)。第三十七頁，共四十九頁，編輯于2023年，星期六

作業(yè)P196,6.13,6.14第三十八頁，共四十九頁，編輯于2023年，星期六1.5多維無約束尋優(yōu)方法TheMulti-DimensionalSearchProcedure第三十九頁，共四十九頁，編輯于2023年，星期六

下降搜索算法下降算法的規(guī)則：給定一個初始點X0，在點Xk選擇一個方向(向量)Pk,并沿此方向選擇一點Xk+1=Xk+tkPk使得f(Xk+1)<f(Xk)。不同的尋優(yōu)方向選擇方法構(gòu)成不同的算法；有兩類方法：解析法——利用函數(shù)的梯度來構(gòu)造尋優(yōu)方向；直接法——利用函數(shù)值來構(gòu)造尋優(yōu)方向；第四十頁，共四十九頁，編輯于2023年，星期六

最速下降法（梯度法）

TheSteepestdescentmethod

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

X0P0P1X1X2P2P3X3X*X4第四十二頁，共四十九頁，編輯于2023年，星期六

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

變尺度法（VariableMetricMethod)（擬牛頓法Quasi-Newtonmethod）第四十三頁，共四十九頁，編輯于2023年，星期六

有約束優(yōu)化問題的算法解的最優(yōu)性條件Kuhn-Tucker條件求解算法直接法：可行方向法，梯度投影法等間接法：將有約束問題轉(zhuǎn)換成一系列的無約束問題來求解，如懲罰函數(shù)法，乘子法等第四十四頁，共四十九頁，編輯于2023年，星期六

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

第四十五頁，共四十九頁，編輯于2023年，星期六

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