高級(jí)運(yùn)籌學(xué)非線性規(guī)劃

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

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

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

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

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

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

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

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

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

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

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

博弈論（GameTheory)

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

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

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

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

運(yùn)籌學(xué)會(huì)與雜志中國(guó)運(yùn)籌學(xué)學(xué)會(huì)(ORSC)TheOperationsResearchSocietyofChina網(wǎng)站:雜志:<運(yùn)籌學(xué)學(xué)報(bào)>,<運(yùn)籌與管理>美國(guó)運(yùn)籌與管理學(xué)會(huì)(IFORMS)InstituteforOperationsResearchandtheManagementSciences英文網(wǎng)址：

中文網(wǎng)站：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二分搜索法

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

黃金分割法（0.618法)

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

黃金分割法（0.618法)

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

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

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

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

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

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

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

最速下降法（梯度法）

TheSteepestdescentmethod

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

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

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

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

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

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

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

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