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

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

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

3、neeringIndustrial and system engineeringOperations ResearchInformation system & operation managementManagement science 運籌學會與雜志中國運籌學學會(ORSC)The Operations Research Society of China 網(wǎng)站:雜志:,美國運籌與管理學會(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)實中的優(yōu)化問題物流網(wǎng)絡的設計優(yōu)化；供應鏈中的多級存儲系統(tǒng)的運行優(yōu)化；港口集裝箱調(diào)度的優(yōu)化；制造系

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

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

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

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

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

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

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

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

13、機環(huán)境下的決策分析方法。應用背景：產(chǎn)品開發(fā)決策問題、風險投資決策問題等等 博弈論（Game Theory) 博弈論博弈論研究的問題是：當一個主體，如一個人或一個企業(yè)的選擇，受到其他人、其他企業(yè)選擇的影響，而且反過來又影響到其他人、其他企業(yè)選擇時的決策問題和均衡問題。博棄論又稱為“對策論”.博弈論可以解釋一些經(jīng)濟和社會現(xiàn)象，比如家電的價格戰(zhàn)、民航業(yè)的價格戰(zhàn)、國家之間的軍備競賽、“劣幣逐良幣”等等現(xiàn)象,解決競爭環(huán)境下的決策問題。 排隊論銀行、醫(yī)院、機場跑道、港口碼頭、理發(fā)店、通信設備、交通路口等等的排隊現(xiàn)象；排隊論是運籌學的又一個分支，又叫做隨機服務系統(tǒng)理論。它的研究目的是要回答如何改進服務機構(gòu)、

14、或組織被服務的對象，使得某種指標達到最優(yōu)的問題。比如一個港口應該有多少個碼頭，一個工廠應該有多少維修人員等 。 庫存論存儲物品的現(xiàn)象是為了解決供應（生產(chǎn)）與需求（消費）之間的不協(xié)調(diào)的一種措施；由此帶來一些需要決策的問題：庫存量、進貨量（如報童問題）、補貨的時間等等決策量。庫存問題也一直是供應鏈管理研究中的熱點問題。非線性規(guī)劃Nonlinear Programming 1.1 相關(guān)的數(shù)學知識一、一般數(shù)學描述可行域特別當R=En, 稱為無約束優(yōu)化問題 1.1 相關(guān)的數(shù)學知識二、解的定義全局最優(yōu)解、嚴格全局最優(yōu)解；局部最優(yōu)解（極值點、極小點）三、多元函數(shù)的偏導偏導數(shù)：指函數(shù)沿某個坐標軸方向的變化率；

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

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

17、終止條件 下降搜索算法下降算法的規(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)方向；1.4 多維無約束尋優(yōu)算法簡介The Multi-Dimensional Search Procedure 最速下降法（梯度法）The Steepest descent method The Gradient Method基本思想：以負梯度方向作為尋優(yōu)方向算法步驟：(舉例說明)特點：迭代過程簡單，存儲量少，計

18、算量??；即使是正定二次函數(shù)也不能有限步收斂；相鄰兩次尋優(yōu)方向是垂直的;尋優(yōu)路線呈鋸齒狀（Zig-Zag)，在極小點附近收斂緩慢; 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ù)學家華羅庚他是中國解析數(shù)論、典型群、矩陣幾何學、自守函數(shù)論與多復變函數(shù)論等很多方面研究的創(chuàng)始人與開拓者。 優(yōu)選法是快速尋找最佳方案的科學方法。具體的優(yōu)選法有很多，如黃金分割法、分數(shù)法、對分法等。黃金分割法也稱0.618法。 如在煉鋼時需加入某種元素來增加鋼材強度，若將試驗點取在這一元素用量區(qū)間的0.618處，獲得理想用量的試驗次數(shù)將大大減少。 實驗證明，對一個因素的優(yōu)化問題，用優(yōu)選法做16次試驗，就可達到“對分法”做2000余次試驗的效果。 一、“成功-失敗”法基本思想“成功”則大步向前，“失敗”則小步后退框圖特點簡

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

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

22、成功-失敗”法搜索到一個包含極小點的區(qū)間。 Fibonacci分數(shù)法The Fibonacci Search Method問題：如何選擇實驗點，計算n次函數(shù)值能得到多大的區(qū)間縮短率？換句話說，計算n次函數(shù)值能將多大的區(qū)間縮短到1。答案：若對稱取點，利用上次已有的實驗點的函數(shù)值，計算n次函數(shù)值可獲得1/Fn區(qū)間縮短率。 Fibonacci分數(shù)法Fibonacci 數(shù)列 (Fibonacci Sequence) F0=1, F1=1, F2=2, F3=3, F4=5, Fk=Fk-1+Fk-2實驗點的計算公式計算步驟算例 Fibonacci 分數(shù)法特點：需要預先確定迭代次數(shù)n;在計算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ù)學規(guī)劃階段目標和約束是解析函數(shù)； 1970s2000s：智能優(yōu)化階段目標和約束可以放寬為含有判斷邏輯的計算機程序； 2000s未來：基于仿真優(yōu)化階段用大量仿真的統(tǒng)計數(shù)據(jù)來進行性能評價。 最優(yōu)化技術(shù)的基本步驟 搜索：在定義域內(nèi)尋找最優(yōu)解；評估：按照問題的目標對解的質(zhì)量進行評價；選擇 ：對獲得的解進行比較，判斷，選擇。 對于迭代算法還要判斷終止條件。 數(shù)學規(guī)劃方法數(shù)學規(guī)劃-線性規(guī)劃，非線性規(guī)劃，動態(tài)規(guī)劃，數(shù)學規(guī)劃

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

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

26、tion)軟計算(Soft Computation)自然計算(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)化算法的計算量分析：GA的評估次數(shù)：遺傳代數(shù)種群大小TS的評估次數(shù)：迭代次數(shù)領(lǐng)域大小SA的評估次數(shù)：降溫次數(shù)內(nèi)循環(huán)次數(shù)隱含假設是：目標函數(shù)的計算（解的評估）很容易，所以根本不注意節(jié)省計算次數(shù)。重復計算不可避免。