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

1、運(yùn)籌學(xué)概述運(yùn)籌學(xué)的研究對(duì)象是各種系統(tǒng)；運(yùn)籌學(xué)的研究目的是實(shí)現(xiàn)系統(tǒng)的最優(yōu)化，求得合理利用各種資源的最優(yōu)方案；運(yùn)籌學(xué)的研究方法是運(yùn)用數(shù)學(xué)語言來描述實(shí)際系統(tǒng)，通過建立數(shù)學(xué)模型和優(yōu)化技術(shù)求得系統(tǒng)運(yùn)營的最優(yōu)解；運(yùn)籌學(xué)的研究動(dòng)機(jī)是為決策者提供科學(xué)決策的依據(jù)。 運(yùn)籌學(xué)概述有人曾對(duì)世界上500家著名的企業(yè)集團(tuán)或跨國公司進(jìn)行過調(diào)查，發(fā)現(xiàn)其中95%曾使用過線性規(guī)劃，75%使用過運(yùn)輸模型，90%使用過網(wǎng)絡(luò)計(jì)劃技術(shù)，90%使用過存儲(chǔ)模型，43%使用過動(dòng)態(tài)規(guī)劃。 運(yùn)籌學(xué)的學(xué)科背景從狹義到廣義的管理科學(xué) 狹義的管理科學(xué)指： 用科學(xué)的方法，特別是定量（運(yùn)籌學(xué)）分析的方法來解決管理問題； 廣義的管理科學(xué)指：有關(guān)管理的學(xué)科或?qū)W

2、科體系管理科學(xué)與工程學(xué)科簡(jiǎn)介管理科學(xué)與工程是綜合運(yùn)用系統(tǒng)科學(xué)、管理科學(xué)、數(shù)學(xué)、經(jīng)濟(jì)和行為科學(xué)及工程方法，結(jié)合信息技術(shù)研究解決社會(huì)、經(jīng)濟(jì)、工程等方面的管理問題的一門交叉學(xué)科。1996年設(shè)立，是管理門類的一級(jí)學(xué)科，與工商管理同,1998年開始授予博士學(xué)位點(diǎn)。當(dāng)時(shí)設(shè)四個(gè)二級(jí)學(xué)科：工業(yè)工程、工程管理、金融工程、管理科學(xué)1998年第一批授予管理科學(xué)與工程學(xué)科博士點(diǎn)的學(xué)校，大多是從原有的“系統(tǒng)工程”學(xué)科轉(zhuǎn)變而來。 管理科學(xué)與工程學(xué)科簡(jiǎn)介管理科學(xué)與工程學(xué)科背景下的本科專業(yè)一般有：工業(yè)工程工程管理管理科學(xué)信息管理與信息工程物流管理（近年增加） 管理科學(xué)與工程學(xué)科簡(jiǎn)介國外相近的系科Industrial engi

3、neeringIndustrial and system engineeringOperations ResearchInformation system & operation managementManagement science 運(yùn)籌學(xué)會(huì)與雜志中國運(yùn)籌學(xué)學(xué)會(huì)(ORSC)The Operations Research Society of China 網(wǎng)站:雜志:,美國運(yùn)籌與管理學(xué)會(huì)(IFORMS)Institute for Operations Research and the Management Sciences英文網(wǎng)址：http:/ 中文網(wǎng)站：http:/ 雜志 Decision

4、 AnalysisInformation Systems ResearchINFORMS Journal on ComputingInterfacesManagement ScienceManufacturing & Service Operations ManagementMarketing ScienceMathematics of Operations ResearchOperations ResearchOrganization ScienceTransportation Science 現(xiàn)實(shí)中的優(yōu)化問題物流網(wǎng)絡(luò)的設(shè)計(jì)優(yōu)化；供應(yīng)鏈中的多級(jí)存儲(chǔ)系統(tǒng)的運(yùn)行優(yōu)化；港口集裝箱調(diào)度的優(yōu)化；制造系

5、統(tǒng)的生產(chǎn)計(jì)劃與調(diào)度優(yōu)化；金融投資領(lǐng)域;復(fù)雜工程系統(tǒng)設(shè)計(jì)的優(yōu)化；復(fù)雜過程控制系統(tǒng)的參數(shù)優(yōu)化；社會(huì)經(jīng)濟(jì)系統(tǒng)的優(yōu)化；。 物流網(wǎng)絡(luò)的設(shè)計(jì)優(yōu)化隨著我國物流業(yè)的快速發(fā)展，不同類型的物流系統(tǒng)的設(shè)計(jì)，物流園區(qū)的設(shè)計(jì)有很大的實(shí)際需求。這些系統(tǒng)設(shè)計(jì)中有很多優(yōu)化問題，比如：多個(gè)倉庫位置的選定，倉庫容量的確定，運(yùn)輸方式和運(yùn)輸工具的選擇，車輛路徑的規(guī)劃，。 供應(yīng)鏈中的多級(jí)存儲(chǔ)系統(tǒng)的運(yùn)行優(yōu)化供應(yīng)鏈的運(yùn)行中也有很多優(yōu)化的問題分銷網(wǎng)絡(luò)中的多級(jí)庫存系統(tǒng)的庫存補(bǔ)充計(jì)劃安全庫存的分級(jí)配置優(yōu)化考慮缺貨或事故情況的處理順應(yīng)價(jià)格波動(dòng)的存儲(chǔ)計(jì)劃車輛運(yùn)輸計(jì)劃和路徑優(yōu)化。 港口集裝箱調(diào)度的優(yōu)化現(xiàn)代化港口和鐵路集裝箱中心站的集裝箱運(yùn)輸中有很多的

6、優(yōu)化問題。比如：船舶的泊次計(jì)劃集裝箱的裝/卸載計(jì)劃堆場(chǎng)的空間計(jì)劃車輛的作業(yè)計(jì)劃貨場(chǎng)的堆放計(jì)劃碼頭起重機(jī)的調(diào)度計(jì)劃,等等 制造系統(tǒng)的生產(chǎn)計(jì)劃與調(diào)度優(yōu)化制造系統(tǒng)的生產(chǎn)計(jì)劃與調(diào)度經(jīng)典的數(shù)學(xué)規(guī)劃方法有很多的成功案例。但是，這類系統(tǒng)當(dāng)考慮到細(xì)節(jié)時(shí)，比如求解車間作業(yè)調(diào)度問題（JSP）時(shí)，一旦考慮托盤的調(diào)度，裝設(shè)時(shí)間和運(yùn)輸時(shí)間，等等，問題將遠(yuǎn)比一般的經(jīng)典JSP更為復(fù)雜。 金融投資問題投資組合問題(portfolio)已知某三支股票的價(jià)格近十年每年的增長情況,以及500種股票指數(shù)變化情況, 假設(shè)你現(xiàn)在有一筆資金要進(jìn)行投資, 并期望年利率至少達(dá)到15%, 那么你應(yīng)該如何投資?。 定量分析的過程定性分析定量分析的

7、前奏應(yīng)當(dāng)是一個(gè)充分的定性分析表達(dá)問題列出表達(dá)問題的基本要素：決策變量、不可控量、限制條件等；建立模型列出表達(dá)這些要素之間關(guān)系的數(shù)學(xué)方程式求解模型與分析運(yùn)用算法求解所構(gòu)建的模型得到最佳方案或滿意方案對(duì)輸入數(shù)據(jù)和模型結(jié)構(gòu)作靈敏度分析執(zhí)行決定或修改模型在實(shí)際應(yīng)用過程中不斷完善模型 建立模型的重要性建立模型是運(yùn)籌學(xué)方法的精髓建立模型有助于我們把決策問題所遇到的復(fù)雜性和可能的不確定性，轉(zhuǎn)變?yōu)檫m于綜合分析的邏輯結(jié)構(gòu)；模型是一種媒介，借以認(rèn)識(shí)現(xiàn)實(shí)世界。模型是現(xiàn)實(shí)的近似表達(dá)，要能抓住決策問題的關(guān)鍵，在真實(shí)性和可用性之間取得適當(dāng)?shù)钠胶狻?油庫和加油站地理分布油品配送路線中國石油上海銷售公司油品配送決策系統(tǒng)18一

8、次配送二次配送油品供應(yīng)鏈原油供應(yīng)商煉油廠油庫工業(yè)客戶/潤滑油廠社會(huì)客戶加油站工業(yè)客戶分油庫 中國石油上海銷售公司上海地區(qū)嘉興地區(qū)蘇州地區(qū)湖州地區(qū)17個(gè)油庫，300個(gè)加油站，1000多個(gè)固定大客戶，分4個(gè)銷售區(qū)域2003年銷售汽油和柴油 200 萬噸，物流成本近 1 億元人民幣 中國石油迫切需要解決的決策問題油品配送決策支持系統(tǒng)戰(zhàn)略決策戰(zhàn)術(shù)決策銷售區(qū)域劃分油品供應(yīng)分配新建油庫選址新建油庫規(guī)模 日配送調(diào)度 多艙位油車調(diào)度 跨區(qū)域集中調(diào)度 緊急調(diào)度供應(yīng)鏈問題 油品配送決策系統(tǒng)結(jié)構(gòu)與特點(diǎn)先進(jìn)的信息和控制技術(shù)Web、液位儀、GIS大規(guī)模、復(fù)雜的OR問題巨大數(shù)量的數(shù)據(jù)處理實(shí)時(shí)決策和人機(jī)交互系統(tǒng)要求與特點(diǎn)油

9、品配送決策系統(tǒng)日配送調(diào)度計(jì)劃油品供應(yīng)分配油庫選址物流信息系統(tǒng)GIS系統(tǒng)Internet加 油 站油庫車隊(duì)液 位 儀 油庫1車站1油庫2加油站加油站加油站加油站車站2加油站加油站加油站加油站1#車輛的配送路線2#車輛的配送路線油品配送路線示意圖 配送調(diào)度模型(超大型混合整數(shù)規(guī)劃)定義網(wǎng)絡(luò) 配送調(diào)度模型定義網(wǎng)絡(luò)30 萬條可行路線 配送調(diào)度模型決策變量 配送調(diào)度模型目標(biāo)函數(shù)運(yùn)輸成本未達(dá)最佳配送量的懲罰未達(dá)最佳運(yùn)載量的懲罰 配送調(diào)度模型每車至多行駛一條可行路線車輛對(duì)路線的限制車輛對(duì)配送油品種數(shù)的限制車輛裝載油品限制約束條件 配送調(diào)度模型(超大型混合整數(shù)規(guī)劃)約束條件需求約束供需平衡供應(yīng)約束車輛裝載限制

10、 配送調(diào)度的人機(jī)交互界面路線鎖定/解鎖按鈕解的序列表示區(qū)備注區(qū)點(diǎn)重新定位按鈕待重新定位點(diǎn)列表解的矢圖表示區(qū) 油庫列表 油庫出油臨時(shí)限制縮放功能 系統(tǒng)效果該系統(tǒng)完全改變了公司傳統(tǒng)的調(diào)度管理方式，顯著提高了配送調(diào)度的響應(yīng)速度、決策的正確性和科學(xué)性，適應(yīng)公司的扁平化管理的目標(biāo)。承運(yùn)商配送決策系統(tǒng)提貨單/發(fā)貨憑證加 油 站油 庫液 位 儀業(yè) 務(wù) 接口 管 理主管公司管理系統(tǒng)提貨單Internet設(shè) 備 接 口 管 理發(fā) 貨 憑 證 系統(tǒng)效果通過使用該系統(tǒng)，中國石油上海銷售公司的物流在產(chǎn)品資源分布、產(chǎn)品庫存、運(yùn)輸成本、運(yùn)輸車輛、運(yùn)輸和管理人工等五個(gè)方面得到了改善，節(jié)省成本。根據(jù)該公司財(cái)務(wù)部估計(jì)，該系統(tǒng)可

11、使該公司全年的物流成本下降 1000 余萬元人民幣，節(jié)省物流成本10% 以上。 各種散裝品的配送調(diào)度油品配送決策系統(tǒng)各種業(yè)態(tài)的實(shí)時(shí)配送調(diào)度第三方物流、郵政、快遞的配送調(diào)度配送決策系統(tǒng)應(yīng)用推廣大型連鎖超市的配送調(diào)度家電、乳品等專業(yè)銷售的配送調(diào)度 可視化集成式油品銷售物流決策系統(tǒng) 運(yùn)籌學(xué)的分支數(shù)學(xué)規(guī)劃線性規(guī)劃 非線性規(guī)劃整數(shù)規(guī)劃 動(dòng)態(tài)規(guī)劃圖與網(wǎng)絡(luò)流 網(wǎng)絡(luò)計(jì)劃庫存論排隊(duì)論對(duì)策論決策論。 優(yōu)化問題的分類確定性、靜態(tài)優(yōu)化問題數(shù)學(xué)規(guī)劃（單目標(biāo)、多目標(biāo)）圖與網(wǎng)絡(luò)流決策論（多目標(biāo)）確定性、動(dòng)態(tài)優(yōu)化問題動(dòng)態(tài)規(guī)劃（離散）最優(yōu)控制（離散、連續(xù)）隨機(jī)性優(yōu)化問題隨機(jī)規(guī)劃存儲(chǔ)論排隊(duì)論決策論（單目標(biāo)）多人競(jìng)爭(zhēng)性決策問題博弈

12、論（對(duì)策論） 本課程的主要內(nèi)容非線性規(guī)劃（一維無約束極值問題）決策論博弈論排隊(duì)論庫存論本課程成績(jī)構(gòu)成平時(shí)30%+期末考試70%平時(shí)成績(jī) = 到課率+作業(yè)+論文或測(cè)驗(yàn)期末考試:閉卷筆試 非線性規(guī)劃問題一般數(shù)學(xué)描述 目標(biāo)函數(shù)或約束函數(shù)中至少有一個(gè)是非線性的應(yīng)用背景有著最廣泛的應(yīng)用，應(yīng)該說所有現(xiàn)實(shí)問題都是非線性的，線性模型都是經(jīng)過簡(jiǎn)化而來的。機(jī)械、電子等行業(yè)的器件最優(yōu)設(shè)計(jì)問題，如飛行器的結(jié)構(gòu)優(yōu)化設(shè)計(jì)等；管理科學(xué)中的應(yīng)用問題更是不勝枚舉；系統(tǒng)控制問題。 決策論（decision theory)著名經(jīng)濟(jì)學(xué)家西蒙有一句名言：“管理就是決策”。“決策”一詞本身是一個(gè)廣義的概念，本課程介紹的是針對(duì)在不確定或隨

13、機(jī)環(huán)境下的決策分析方法。應(yīng)用背景：產(chǎn)品開發(fā)決策問題、風(fēng)險(xiǎn)投資決策問題等等 博弈論（Game Theory) 博弈論博弈論研究的問題是：當(dāng)一個(gè)主體，如一個(gè)人或一個(gè)企業(yè)的選擇，受到其他人、其他企業(yè)選擇的影響，而且反過來又影響到其他人、其他企業(yè)選擇時(shí)的決策問題和均衡問題。博棄論又稱為“對(duì)策論”.博弈論可以解釋一些經(jīng)濟(jì)和社會(huì)現(xiàn)象，比如家電的價(jià)格戰(zhàn)、民航業(yè)的價(jià)格戰(zhàn)、國家之間的軍備競(jìng)賽、“劣幣逐良幣”等等現(xiàn)象,解決競(jìng)爭(zhēng)環(huán)境下的決策問題。 排隊(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)、

14、或組織被服務(wù)的對(duì)象，使得某種指標(biāo)達(dá)到最優(yōu)的問題。比如一個(gè)港口應(yīng)該有多少個(gè)碼頭，一個(gè)工廠應(yīng)該有多少維修人員等 。 庫存論存儲(chǔ)物品的現(xiàn)象是為了解決供應(yīng)（生產(chǎn)）與需求（消費(fèi)）之間的不協(xié)調(diào)的一種措施；由此帶來一些需要決策的問題：庫存量、進(jìn)貨量（如報(bào)童問題）、補(bǔ)貨的時(shí)間等等決策量。庫存問題也一直是供應(yīng)鏈管理研究中的熱點(diǎn)問題。非線性規(guī)劃Nonlinear Programming 1.1 相關(guān)的數(shù)學(xué)知識(shí)一、一般數(shù)學(xué)描述可行域特別當(dāng)R=En, 稱為無約束優(yōu)化問題 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)軸方向的變化率；

15、梯度：由各個(gè)坐標(biāo)軸方向組成的向量；方向?qū)?shù)：指函數(shù)沿某個(gè)給定方向的變化率；常用的求梯度公式 1.1 相關(guān)的數(shù)學(xué)知識(shí)四、Hessian 矩陣（二階導(dǎo)數(shù)矩陣）幾個(gè)常用的公式五、正定矩陣定義正定二次函數(shù)六、多元函數(shù)的Taylor展開 1.1 相關(guān)的數(shù)學(xué)知識(shí)七、凸函數(shù)、凸規(guī)劃凸集(convex set)：凸函數(shù)(convex )、凹函數(shù)(concave)：定義幾何意義性質(zhì)判別條件特別：線性函數(shù)既是凸函數(shù)也是凹函數(shù)凸規(guī)劃(convex programming) 1.2 解的最優(yōu)性條件一階必要條件在極值點(diǎn)的梯度=0二階充分條件二階導(dǎo)數(shù)矩陣為正定矩陣 1.3下降搜索算法目標(biāo)函數(shù)的等值線（二維，等高線）對(duì)二次

16、函數(shù)，等值線是一族同心的橢圓；對(duì)于非二次函數(shù)，在極小點(diǎn)附近，等值線近似一族同心橢圓；具有不同值的等值線不相交；等值線稠密處目標(biāo)函數(shù)變化快，稀疏處變化慢；等值線上一點(diǎn)的梯度與該點(diǎn)的的等值線切線方向相互垂直。 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)。 X0P0P1X1X2P2P3X3X*X4 1.3下降搜索算法算法步驟中的關(guān)鍵要素：給定初始點(diǎn)；確定尋優(yōu)方向；確定一個(gè)步長；判別是否滿足

17、終止條件 下降搜索算法下降算法的規(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ù)的梯度來構(gòu)造尋優(yōu)方向；直接法利用函數(shù)值來構(gòu)造尋優(yōu)方向；1.4 多維無約束尋優(yōu)算法簡(jiǎn)介The Multi-Dimensional Search Procedure 最速下降法（梯度法）The Steepest descent method The Gradient Method基本思想：以負(fù)梯度方向作為尋優(yōu)方向算法步驟：(舉例說明)特點(diǎn)：迭代過程簡(jiǎn)單，存儲(chǔ)量少，計(jì)

18、算量?。患词故钦ǘ魏瘮?shù)也不能有限步收斂；相鄰兩次尋優(yōu)方向是垂直的;尋優(yōu)路線呈鋸齒狀（Zig-Zag)，在極小點(diǎn)附近收斂緩慢; X0P0P1X1X2P2P3X3X*X4 其他解析算法共軛梯度法(Conjugate gradient method) 牛頓法（Newtons method) 變尺度法 （Variable Metric Method) （擬牛頓法Quasi-Newton method） 有約束優(yōu)化問題的算法解的最優(yōu)性條件Kuhn-Tucker 條件求解算法直接法：可行方向法，梯度投影法等間接法：將有約束問題轉(zhuǎn)換成一系列的無約束問題來求解，如懲罰函數(shù)法，乘子法等1.5 一維尋優(yōu)方法T

19、he One-Dimensional Search Procedure優(yōu)選法數(shù)學(xué)家華羅庚他是中國解析數(shù)論、典型群、矩陣幾何學(xué)、自守函數(shù)論與多復(fù)變函數(shù)論等很多方面研究的創(chuàng)始人與開拓者。 優(yōu)選法是快速尋找最佳方案的科學(xué)方法。具體的優(yōu)選法有很多，如黃金分割法、分?jǐn)?shù)法、對(duì)分法等。黃金分割法也稱0.618法。 如在煉鋼時(shí)需加入某種元素來增加鋼材強(qiáng)度，若將試驗(yàn)點(diǎn)取在這一元素用量區(qū)間的0.618處，獲得理想用量的試驗(yàn)次數(shù)將大大減少。 實(shí)驗(yàn)證明，對(duì)一個(gè)因素的優(yōu)化問題，用優(yōu)選法做16次試驗(yàn)，就可達(dá)到“對(duì)分法”做2000余次試驗(yàn)的效果。 一、“成功-失敗”法基本思想“成功”則大步向前，“失敗”則小步后退框圖特點(diǎn)簡(jiǎn)

20、單易行，對(duì)初始點(diǎn)選擇無嚴(yán)格限制；適用于不可微的函數(shù)；在極小點(diǎn)附近收斂慢；可用此方法來確定一個(gè)搜索區(qū)間。 二、牛頓法（切線法）基本思想：適合二階連續(xù)可微的函數(shù)，求導(dǎo)數(shù)為0的方程根。迭代公式算法步驟特點(diǎn)適用于二階可微函數(shù)；最快的收斂速度，二階收斂速度；初始點(diǎn)要求接近極小點(diǎn)；可與“成功-失敗”法聯(lián)合使用。 序貫實(shí)驗(yàn)法單峰函數(shù)（Unimodal Function,下單峰、單谷) 定義（在極小點(diǎn)左邊單調(diào)下降，右邊單調(diào)上升）性質(zhì)( Unimodality，單峰性)基本思想：通過選擇實(shí)驗(yàn)點(diǎn)，計(jì)算其函數(shù)值，比較實(shí)驗(yàn)點(diǎn)的函數(shù)值大小，縮小包含極值點(diǎn)的區(qū)間 二分搜索法The Dichotomy Method wit

21、hout Derivatives基本思想對(duì)稱取點(diǎn)，等比例縮小區(qū)間特點(diǎn)：簡(jiǎn)單對(duì)稱取點(diǎn)，不論取哪個(gè)區(qū)間，其長度相等；每次要計(jì)算兩次函數(shù)值 黃金分割法（0.618法)The Golden Section Search Method基本思想：對(duì)稱取點(diǎn)，等比例的縮小區(qū)間，除第一次外，每次只需計(jì)算一次函數(shù)值，可使區(qū)間縮小。b0a0t11t12b1a1f(t11)f(t12)t22t21 黃金分割法（0.618法)The Golden Section Search Method實(shí)驗(yàn)點(diǎn)的計(jì)算公式算法步驟特點(diǎn)：具有相同的區(qū)間縮短率0.618；精度不如Fobonacci分?jǐn)?shù)法；適用于不可微、不連續(xù)函數(shù)，可以先用“

22、成功-失敗”法搜索到一個(gè)包含極小點(diǎn)的區(qū)間。 Fibonacci分?jǐn)?shù)法The Fibonacci Search Method問題：如何選擇實(shí)驗(yàn)點(diǎn)，計(jì)算n次函數(shù)值能得到多大的區(qū)間縮短率？換句話說，計(jì)算n次函數(shù)值能將多大的區(qū)間縮短到1。答案：若對(duì)稱取點(diǎn)，利用上次已有的實(shí)驗(yàn)點(diǎn)的函數(shù)值，計(jì)算n次函數(shù)值可獲得1/Fn區(qū)間縮短率。 Fibonacci分?jǐn)?shù)法Fibonacci 數(shù)列 (Fibonacci Sequence) F0=1, F1=1, F2=2, F3=3, F4=5, Fk=Fk-1+Fk-2實(shí)驗(yàn)點(diǎn)的計(jì)算公式計(jì)算步驟算例 Fibonacci 分?jǐn)?shù)法特點(diǎn)：需要預(yù)先確定迭代次數(shù)n;在計(jì)算n次函數(shù)值情

23、況下，該方法獲得最大的區(qū)間縮短率，精度最高；適用于不可微、不連續(xù)函數(shù)。 作業(yè)P196, 6.12, 6.13, 6.141.6 最優(yōu)化技術(shù)的新發(fā)展 最優(yōu)化技術(shù)的發(fā)展1940s1970s：數(shù)學(xué)規(guī)劃階段目標(biāo)和約束是解析函數(shù)； 1970s2000s：智能優(yōu)化階段目標(biāo)和約束可以放寬為含有判斷邏輯的計(jì)算機(jī)程序； 2000s未來：基于仿真優(yōu)化階段用大量仿真的統(tǒng)計(jì)數(shù)據(jù)來進(jìn)行性能評(píng)價(jià)。 最優(yōu)化技術(shù)的基本步驟 搜索：在定義域內(nèi)尋找最優(yōu)解；評(píng)估：按照問題的目標(biāo)對(duì)解的質(zhì)量進(jìn)行評(píng)價(jià)；選擇 ：對(duì)獲得的解進(jìn)行比較，判斷，選擇。 對(duì)于迭代算法還要判斷終止條件。 數(shù)學(xué)規(guī)劃方法數(shù)學(xué)規(guī)劃-線性規(guī)劃，非線性規(guī)劃，動(dòng)態(tài)規(guī)劃，數(shù)學(xué)規(guī)劃

24、的基本步驟三步曲選一個(gè)初始解；LP:大M，二階段法NLP:任意點(diǎn)或一個(gè)內(nèi)點(diǎn) 數(shù)學(xué)規(guī)劃方法（2）停止判據(jù)停止規(guī)則最優(yōu)性檢驗(yàn)；LP:檢驗(yàn)數(shù)當(dāng)0時(shí)有可能減小NLP: 數(shù)學(xué)規(guī)劃方法（3）向改進(jìn)方向移動(dòng)改進(jìn)解LP:轉(zhuǎn)軸變換(進(jìn)基、退基)NLP:向負(fù)梯度方向移動(dòng)(共軛梯度方向、牛頓方向) 數(shù)學(xué)規(guī)劃方法（4）停機(jī)選擇一個(gè)初始解 停止準(zhǔn)則向改進(jìn)方向移動(dòng)啟動(dòng)YN評(píng)估解問題：解的評(píng)估呢？評(píng)估解 數(shù)學(xué)規(guī)劃方法（5）數(shù)學(xué)規(guī)劃方法的局限性對(duì)問題中目標(biāo)函數(shù)、約束函數(shù)有很高的要求有顯式表達(dá)，線性、連續(xù)、可微，且高階可微;只從一個(gè)初始點(diǎn)出發(fā)，難以進(jìn)行并行、網(wǎng)絡(luò)計(jì)算，難以提高計(jì)算效率；最優(yōu)性達(dá)到的條件太苛刻問題的目標(biāo)函數(shù)為凸函

25、數(shù)，可行域?yàn)橥辜辉诜请p凸條件下，沒有跳出局部最優(yōu)解的能力。 實(shí)際優(yōu)化問題往往不滿足雙凸條件 智能優(yōu)化方法智能優(yōu)化方法的產(chǎn)生對(duì)問題的描述要寬松(目標(biāo)和約束函數(shù)) 可以用一段程序來描述(程序中帶判斷、循環(huán))，函數(shù)可以非連續(xù)、非凸、非可微、非顯式；并不苛求最優(yōu)解通常滿意解、理想解就可以了；計(jì)算快速、高效,可隨時(shí)終止(根據(jù)時(shí)間定解的質(zhì)量)。 智能優(yōu)化方法（2）智能優(yōu)化方法的好多名字：高級(jí)啟發(fā)式(Advanced Heuristics)智能優(yōu)化(Intelligent Optimization)計(jì)算智能(Intelligent Computation)進(jìn)化計(jì)算(Evolutionary computa

26、tion)軟計(jì)算(Soft Computation)自然計(jì)算(Natural Computation) 智能優(yōu)化方法（3）智能優(yōu)化的主流算法：1975年Holland提出遺傳算法(Genetic Algorithm)-GA1977年Glover提出禁忌搜索算法(Tabu Search)-TS1982年Kirkpatrick提出模擬退火算法(Simulated Annealing)-SA1995年Dorigo提出蟻群算法(Ant Colony Optimization)-ACO1995年Kennedy & Eherhart提出粒子群優(yōu)化 (Particle Swarm Optimization)-PSO 智能優(yōu)化方法（6）智能優(yōu)化算法的計(jì)算量分析：GA的評(píng)估次數(shù)：遺傳代數(shù)種群大小TS的評(píng)估次數(shù)：迭代次數(shù)領(lǐng)域大小SA的評(píng)估次數(shù)：降溫次數(shù)內(nèi)循環(huán)次數(shù)隱含假設(shè)是：目標(biāo)函數(shù)的計(jì)算（解的評(píng)估）很容易，所以根本不注意節(jié)省計(jì)算次數(shù)。重復(fù)計(jì)算不可避免。