高等運籌學(xué)(第1章).ppt

1、1,高 等 運 籌 學(xué),2,課程內(nèi)容特點,基礎(chǔ)運籌學(xué)：單目標優(yōu)化，精確算法。 高等運籌學(xué)：多目標優(yōu)化，啟發(fā)式算法。,3,主要內(nèi)容,概論 現(xiàn)代運籌學(xué)的理念柔性 多目標規(guī)劃 經(jīng)典啟發(fā)式方法 模擬退火算法 禁忌搜索算法 遺傳算法,4,第1章 概論,1.1 運籌學(xué)概述 1.2 最優(yōu)化問題及其分類 1.3 計算復(fù)雜性概述 1.4 優(yōu)化算法及其分類 1.5 鄰域與局部搜索,5,1.1 運籌學(xué)概述,1.運籌學(xué)的產(chǎn)生和發(fā)展 二戰(zhàn)期間，英國海軍部召集了一個專家小組，稱為“Operational Research”小組，美國武裝部隊的規(guī)劃總部也建立了一個類似的專家小組，稱為“Operations Research

2、”小組，從事軍事運籌方面的研究。 戰(zhàn)后，運籌學(xué)的方法廣泛應(yīng)用于民用企業(yè)，以解決復(fù)雜的經(jīng)營管理問題，并促進運籌學(xué)發(fā)展成為一門獨立的學(xué)科。該學(xué)科的英文名稱就是Operational Research或Operations Research, 簡稱OR。,6,英國：1948年成立運籌學(xué)俱樂部，1950年創(chuàng)辦第一份運籌學(xué)刊物“Operational Research Quarterly”，該俱樂部于1953年改名為運籌學(xué)會，刊物也更名為“Journal of the Operational Research Society”。 美國：1952年成立運籌學(xué)會，并創(chuàng)刊“Operations Researc

3、h”。 中國：1956年在中科院成立我國第一個運籌學(xué)小組，1980年成立運籌學(xué)會，1982年成為國際運籌學(xué)聯(lián)合會會員國?，F(xiàn)創(chuàng)辦的主要刊物有“運籌學(xué)學(xué)報”和“運籌與管理”。 “運籌帷幄之中，決勝千里之外”與“運籌學(xué)” 。 OR的發(fā)展與計算機的發(fā)展分不開。如果沒有計算機，OR只不過是一種理論科學(xué)，不會成為應(yīng)用科學(xué)。,7,2. 運籌學(xué)的組成部分 運籌學(xué)研究的現(xiàn)象有三類：一是資源運用的問題，二是競爭現(xiàn)象，三是擁擠現(xiàn)象。 其內(nèi)容相應(yīng)地劃分為三個組成部分：運用分析理論，競爭理論，隨機服務(wù)理論。 運用分析理論：包括分配、選址、資源最佳利用、設(shè)備最佳運行等。常用的數(shù)學(xué)方法有線性規(guī)劃、非線性規(guī)劃、網(wǎng)絡(luò)規(guī)劃、動態(tài)

4、規(guī)劃、最優(yōu)控制等。 競爭理論：主要方法是對策論。 隨機服務(wù)理論：主要方法是排隊論。,8,3. 運籌學(xué)的性質(zhì) 核心：運用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑和方案，為決策者提供科學(xué)決策依據(jù)。 研究對象：人類對各種資源的運用及籌劃活動。 研究方法：定量化和模型化，尤其是運用各種數(shù)學(xué)模型和優(yōu)化技術(shù)。 研究目的：了解和發(fā)現(xiàn)這些運用及活動的基本規(guī)律，發(fā)揮有限資源的最大效益。 OR：The Science of Better. OR uses mathematics, but it is not a branch of mathematics.,9,4. 運籌學(xué)的特點 強調(diào)研究過程的完整性：問題的提出建立模型提

5、出解案付諸實施。 強調(diào)理論與實踐的結(jié)合。 5. 運籌學(xué)的應(yīng)用領(lǐng)域 其影響繼續(xù)擴大：國際運籌學(xué)聯(lián)合會已有48個成員國。 應(yīng)用領(lǐng)域不斷增加：如軍事運籌學(xué)、管理運籌學(xué)、交通運輸運籌學(xué)、工業(yè)運籌學(xué)、農(nóng)業(yè)運籌學(xué)、工程技術(shù)運籌學(xué)、計算運籌學(xué)等。 總之，凡是在某些有限的資源限制下尋求一個最優(yōu)的行動方案，運籌學(xué)就有可能用得上。,10,1.2 最優(yōu)化問題及其分類,最優(yōu)化指最小化或最大化，本課程以最小化為例。 最優(yōu)化問題可分為函數(shù)優(yōu)化問題和組合優(yōu)化問題兩大類。 1.函數(shù)優(yōu)化問題 優(yōu)化的對象是可在一定區(qū)間內(nèi)取值的連續(xù)變量。 2.組合優(yōu)化問題 優(yōu)化的對象是解空間中的離散狀態(tài)。 解決的是離散事件的最優(yōu)編排、分組、次序或

6、篩選等問題，是運籌學(xué)中一個經(jīng)典且重要的分支。涉及管理、交通運輸、通信網(wǎng)絡(luò)等諸多領(lǐng)域。,11,組合優(yōu)化問題可用數(shù)學(xué)模型描述為： min f (x) s.t. g (x) 0, xS, 其中，f (x)為目標函數(shù)，g (x)為約束函數(shù)，x為決策變量，S表示有限個點組成的集合。 一個組合優(yōu)化問題也可用三個參數(shù)（S, F, f）來描述： S：決策變量的定義域，即解空間； F = x | xS, g (x)0：可行解區(qū)域； f ：目標函數(shù)值，滿足f (x*) = min f (x)| xF 的可 行解x*稱為該問題的最優(yōu)解。 組合優(yōu)化的特點：可行解集合為有限點集。,12,幾個典型組合優(yōu)化問題： (1)

7、旅行商問題（traveling salesman problem, TSP） 一個商人欲到n個城市巡回推銷商品，已知城市i和j之間的距離為dij，如何確定一條巡回路線，使得商人從其中的某一城市出發(fā)，經(jīng)過其他城市一次且僅一次后回到原出發(fā)點，且所走的路程最短。 設(shè),13,則該問題的一種數(shù)學(xué)模型為： s.t. xij0,1, i,j =1,2,n, ij.,14,(2) 0-1背包問題（knapsack problem） 對于n個體積分別為ai (1,2,n)，價值分別為ci (1,2,n)的物品，如何將它們裝入總體積為b的背包中，使得所選物品的總價值最大？ 設(shè) 則該問題可用數(shù)學(xué)模型表示為： s.t

8、. xi0,1, i =1,2,n,15,(3) 裝箱問題（bin packing problem） 如何以個數(shù)最少的尺寸為1單位的箱子裝入n個尺寸不超過1單位的物品。 (4) 機器排序問題（machine scheduling problem） 。 有n個工件需要在機床A、B上加工，每個工件都必須經(jīng)過先A而后B的兩道工序。以Aj和Bj分別表示工件j（j=1, 2, , n）在A和B上的加工時間。問應(yīng)如何安排各工件加工的順序，才能使從機床A上加工第一個工件開始到在機床B上將最后一個工件加工完為止，所用的加工總時間最少？ 在組合優(yōu)化問題中，有些可以用整數(shù)規(guī)劃模型表示，有些則用文字敘述更易理解。

9、上述問題描述均非常簡單，但求其最優(yōu)解確很困難。,16,1.3 計算復(fù)雜性概述,1.算法及算法分析 算法:能被機械地執(zhí)行的動作（或規(guī)則）的有限集合，一個動作的一次執(zhí)行稱為一步。 算法特征：輸入、確定性、可執(zhí)行性、有限性、輸出。 算法分析：對算法性能的討論。 算法分析目的： 對同一問題的各種可實現(xiàn)的算法進行比較，對它們的性能作出定量的判斷。 確定算法是否存在什么性能上的限制，給算法設(shè)計提供理論上的指導(dǎo)。,17,算法復(fù)雜性：算法對時間和空間的需要量分別稱為算法的時間復(fù)雜性和空間復(fù)雜性。 算法執(zhí)行基本操作的次數(shù)定義為算法的時間復(fù)雜性，記為T(n)； 算法執(zhí)行期間占用的計算機存儲單元定義為算法的空間復(fù)雜

10、性，記為S(n)。 算法的復(fù)雜性的表示：一般表示為問題規(guī)模n（如TSP中的城市數(shù)）的函數(shù)。 當一個算法A對于規(guī)模為n的問題進行求解計算時，若所需的基本操作次數(shù)的上界（指在最壞情況下）為f (n)，則稱f (n)為算法A的時間復(fù)雜性函數(shù)。 在分析復(fù)雜性時，可用其函數(shù)主要項的階O(f (n)來表示。,18,若算法A的時間復(fù)雜性為T(n) = O(f (n)，且f (n)為n的多項式函數(shù)，如O(n)、O(n3)等，則稱算法A為多項式算法。 時間復(fù)雜性函數(shù)不屬于n的多項式函數(shù)的算法統(tǒng)稱為指數(shù)算法，如f(n)為2n、n!、nn等形式。 算法性能：多項式算法是有效算法；指數(shù)算法不是有效算法。另外，多項式算

11、法有較好的“閉”性。 問題的難易性：若一個問題找到了多項式算法，就可以認為這個問題基本解決了。若一個問題不存在多項式算法，則稱這個問題是難解的。 有少數(shù)復(fù)雜度為指數(shù)函數(shù)的算法，在實踐中卻被證明是有效的算法，如求解線性規(guī)劃問題的單純形法就是一個突出的例子。,19,2. P, NP, NP完全和NP難 P類和NP類問題 若問題有求解它的多項式算法，則屬于P類問題。 若問題仍沒有找到求其最優(yōu)解的多項式算法，則稱這類問題為非多項式確定問題，即NP類問題。 NP完全問題 NP完全（NP-complete, NP-C）問題是NP類問題中難度最大的一類問題。 為證明一個問題是NP完全的，須證明：該問題是NP

12、的；所有其他NP問題可多項式歸約（變換）到該問題。 現(xiàn)已證明的NP完全問題已上千個，但沒有找到任一問題的多項式算法。 性質(zhì)：任一NP完全問題都不能用任何已知的多項式算法求解；若任一NP完全問題有多項式算法，則一切NP完全問題都有多項式算法。,20,NP難問題 有些問題，不能驗證它屬于NP類，但可以證明所有NP問題都可以多項式歸約為該問題，則這類問題稱為NP難問題（NP-hard）。 一個問題是NP難問題不要求該問題屬于NP類，但至少和NP完全問題有同等的難度。 P NP NP完全 NP難 圖1.1 四類問題的關(guān)系圖,21,1.4 優(yōu)化算法及其分類,優(yōu)化算法：是基于某種思想和機制建立起來的、能求

13、出滿足要求的問題的解的一種搜索途徑或規(guī)則。 按求解精度分類： 精確算法（exact algorithm）：可求出問題最優(yōu)解的算法，且一般要求問題能用數(shù)學(xué)模型表示，但對大規(guī)模問題計算量大，應(yīng)用范圍常常受到限制。 啟發(fā)式算法（heuristic algorithm）：基于直觀或經(jīng)驗構(gòu)造的算法，且一般不要求將問題表述為某種標準數(shù)學(xué)模型。在可接受的計算量內(nèi)求出問題的可行解，但不能保證解的最優(yōu)性。,22,按優(yōu)化機制與行為分類： 經(jīng)典算法：包括線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)規(guī)劃和分枝定界等運籌學(xué)中的傳統(tǒng)算法。 構(gòu)造算法：用構(gòu)造的方法快速建立問題的一個可行解。如運輸問題中的最小元素法。 鄰域搜索算法：從任一初始解

14、出發(fā)，對其鄰域的不斷搜索和當前解的替換來逐步實現(xiàn)優(yōu)化。根據(jù)搜索行為，又可將其分為局部搜索法和指導(dǎo)性搜索法。 基于系統(tǒng)動態(tài)演化的方法：將優(yōu)化過程轉(zhuǎn)化為系統(tǒng)動態(tài)的演化過程，以系統(tǒng)動態(tài)的演化來實現(xiàn)優(yōu)化。 混合型算法：上述各算法從結(jié)構(gòu)或操作上相混合而產(chǎn)生的各類算法。 按其它角度分類：如確定性算法和隨機性算法；局部優(yōu)化算法和全局優(yōu)化算法等。,23,1.5 鄰域與局部搜索,1.鄰域 定義: 在距離空間中：是指以一點為中心的一個球體。 在組合優(yōu)化中：設(shè)某問題所有解構(gòu)成的解空間為S。對于每個解xiS，有一個在某種意義上是“鄰近”xi的解的集合，稱集合N(xi)為xi的鄰域（neighbourhood），每個x

15、jN(xi)稱為xi的一個鄰域解或鄰居（neighbour）。此外，通常約定xjN(xi) =xiN(xj)。 2.鄰域結(jié)構(gòu)（neighbourhood structure，也稱鄰域函數(shù)或解產(chǎn)生函數(shù)）,24,其作用是指導(dǎo)如何由一個解來產(chǎn)生一個新的解。 設(shè)計往往依賴于問題的特性和解的表達方式。 函數(shù)優(yōu)化與組合優(yōu)化中的鄰域結(jié)構(gòu)的具體方式存在明顯差異： 函數(shù)優(yōu)化中：利用距離的概念通過附加擾動來構(gòu)造鄰域結(jié)構(gòu)是最常用的方法，如x= x+，其中x為新解，x為舊解，為尺度參數(shù)，為滿足某種概率分布的隨機數(shù)或梯度信息等。 組合優(yōu)化中：因傳統(tǒng)的距離概念不再適用，但鄰域結(jié)構(gòu)的基本思想仍舊是通過對一個解進行適當變換后

16、產(chǎn)生另一個解。,25,如TSP的解可用置換排列來表示，如排列（1, 2, 3, 4）可表示為有4個城市的TSP的一個解。那么，k個點的交換就可認為是一種鄰域結(jié)構(gòu)，即 Nk = jN(i) | j可由i經(jīng)一次k交換得到 如上述排列的2點交換對應(yīng)的鄰域結(jié)構(gòu)將產(chǎn)生新解（2, 1, 3, 4）、（3, 2, 1, 4）等。 3.局部最優(yōu)和全局最優(yōu) 定義：令（S, F, f）為一個優(yōu)化問題，其中S為所有解構(gòu)成的解空間，F(xiàn)為S上的可行域，f 為目標函數(shù)，設(shè) 為解x*的鄰域，若 xN(xi)F，滿足f(x*)()f(x)，則稱x*為f 在F上的局部最?。ㄗ畲螅┙猓c）；若 xF，滿足f(x*)()f(x)，

17、則稱x*為f 在F上的全局最?。ㄗ畲螅┙猓c）。,26,以一維變量x為例，假設(shè)可行域為區(qū)間1,10中的整數(shù)點，目標函數(shù)值如圖1.2所示，如果采用如下鄰域定義： N(x) = yZ+|y-x|1， 則x=9為全局最小點；x=5為局部最小點；而x=4既不是局部最大點也不是局部最小點。 f(x) + + + + + + + + + + O 1 2 3 4 5 6 7 8 9 10 x 圖1.2 局部最優(yōu)解示意圖,27,4.局部搜索算法（local search） 是一種傳統(tǒng)的優(yōu)化算法，是基于貪婪思想利用鄰域結(jié)構(gòu)進行搜索的。又兩種實現(xiàn)方式： 上（下）山法：一旦搜索到一個更好的解，就立即接受其作為新的當

18、前解； 最陡下降法：只接受當前解整個鄰域中的最好解作為下一當前解。 以下山法為例介紹求目標函數(shù)值最小的局部搜索算法：從一個初始解x0F出發(fā)，利用鄰域結(jié)構(gòu)持續(xù)地在當前解x i的鄰域中搜索比它更好的解，若能夠找到這樣的解，就用這個解取代x i，成為新的當前解，再對當前解重復(fù)上述過程；否則搜索過程終止，并以當前解作為算法的最終解。,28,用偽Pascal語言描述的局部搜索算法： Procedure Local_Search; Begin 任選一初始解x0； x i := x0 （置初始解為當前解） repeat 從鄰域N(x i)中隨機選一個x j； if f(x j) f(x i) then x i := x j； until 對鄰域N(x i)中的所有x j均有f(x j) f(x i) End. 以圖1.2為例，若以x=4為起點用局部搜索算法搜索最小值點，則搜索到x=5這個局部最優(yōu)（最?。c時就會停止。,29,局部搜索算法具有以下優(yōu)點： 通用性，易實現(xiàn)。 靈活性。 局部搜索算法有以下不足： 搜索性能和最終解的質(zhì)量依賴