數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性.ppt_第1頁(yè)
數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性.ppt_第2頁(yè)
數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性.ppt_第3頁(yè)
數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性.ppt_第4頁(yè)
數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性.ppt_第5頁(yè)
已閱讀5頁(yè),還剩112頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、1,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,組合優(yōu)化理論,Combinatorial Optimization Theory,2,第一章 組合優(yōu)化模型 與計(jì)算復(fù)雜性,1 組合優(yōu)化模型與算法,2 計(jì)算復(fù)雜性問(wèn)題,3 啟發(fā)式算法,3,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,模型(model )是所研究的系統(tǒng)、過(guò)程、事物或 概念的一種表達(dá)形式 .,1 組合優(yōu)化模型與算法,(一) 模型的概念,模型不是研究對(duì)象本身,而是對(duì)研究對(duì)象的一種 抽象,它反映現(xiàn)實(shí)中對(duì)象系統(tǒng)的主要特征,但它又高 于現(xiàn)實(shí),因而具有同類問(wèn)題的共性 .,由于研究目的的不同,對(duì)于同一個(gè)對(duì)象系統(tǒng), 可以建立完全不同的模型,分別反映該系統(tǒng)的不同 側(cè)面;出

2、于相同的研究目的,對(duì)于同一個(gè)對(duì)象系 統(tǒng),也可能建立不同的模型,反映不同的研究角 度、考察因素和價(jià)值取向 .,一、關(guān)于模型,4,1 組合優(yōu)化模型與算法,(二) 模型的本質(zhì),從系統(tǒng)概念上看,模型是系統(tǒng)中各種關(guān)系的表達(dá) 形式 . 因此,建立模型要從狀態(tài)和過(guò)程兩個(gè)方面去尋 找、把握和描述各系統(tǒng)要素之間的相互關(guān)系 .,狀態(tài):事物在某個(gè)時(shí)刻所處的狀況或表現(xiàn)形態(tài),過(guò)程:事物狀態(tài)的變化在時(shí)間上的持續(xù)和空間上的延伸,過(guò)程和狀態(tài)兩者緊密聯(lián)系、不可分割,狀態(tài)決 定和影響過(guò)程,過(guò)程又決定和影響新的狀態(tài) .,狀態(tài)和過(guò)程是相對(duì)的 .,5,從認(rèn)識(shí)論上看,模型是作為認(rèn)識(shí)與實(shí)踐活動(dòng)的中介 .,現(xiàn)實(shí)世界,認(rèn)識(shí)(信息),模 型,實(shí)

3、踐活動(dòng),概念化,用信息載體表達(dá),決策(行動(dòng)方案),產(chǎn)品和服務(wù),模型化過(guò)程示意圖,模型既是認(rèn)識(shí)的表達(dá),又是實(shí)踐活動(dòng)的先導(dǎo) .,模型參與認(rèn)識(shí)世界和改造世界的不斷的循環(huán)往復(fù) 過(guò)程,既是認(rèn)識(shí)不斷深化的體現(xiàn),又是實(shí)踐活動(dòng)不斷 拓展的體現(xiàn) .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,6,1 組合優(yōu)化模型與算法,從信息論上看,模型和認(rèn)識(shí)之間存在密切的反饋 關(guān)系 . 從已知信息可以通過(guò)模型加工產(chǎn)生出新的信 息,相關(guān)信息的積累可以從量變產(chǎn)生質(zhì)變,形成新的 概念,促使認(rèn)識(shí)深化 .,因此,模型的建立和完善不僅要注重對(duì)系統(tǒng)物質(zhì) 形態(tài)和能量形態(tài)的認(rèn)識(shí)、把握和描述,而且也依賴于 對(duì)系統(tǒng)相關(guān)信息不斷的采集、積累和加工,這就是用

4、模型研究問(wèn)題的現(xiàn)實(shí)活動(dòng) .,7,(三) 模型的分類,1、原樣模型,原樣模型是在工程開(kāi)發(fā)末期建立的一種具象實(shí) 體,是具有實(shí)物形態(tài)的模型 .,它與目的工程在結(jié)構(gòu)和過(guò)程方面基本相同 .,原樣模型經(jīng)過(guò)試驗(yàn)改進(jìn)和完善后便是所要開(kāi)發(fā) 的目的工程 .,新產(chǎn)品的樣機(jī)、新著作的原稿 ,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,8,1 組合優(yōu)化模型與算法,2、相似模型,相似模型是根據(jù)不同系統(tǒng)間的相似規(guī)律(包括幾 何相似、邏輯相似和過(guò)程相似等)而建立的用于研究 的模型 .,3、圖形模型,地球儀、船體放樣 模型、飛機(jī)風(fēng)洞實(shí)驗(yàn)?zāi)?擬模型等等,圖形模型可以表達(dá)非常豐富的內(nèi)容,主要有:, 圖畫(huà) 一種可以示形的圖形;, 草圖 一種可

5、以示意的圖形;, 框圖 一種可以表示系統(tǒng)的部分之間或部分 與整體之間聯(lián)系的圖形;,稱為不嚴(yán)格圖 (沒(méi)有嚴(yán)格的規(guī)范),系統(tǒng)分析和設(shè)計(jì)人員常常借助于這些圖形模型來(lái) 開(kāi)發(fā)、構(gòu)建一個(gè)新系統(tǒng)的想象力和創(chuàng)造力,逐步引申 出與之有關(guān)的問(wèn)題和需要進(jìn)一步探索的問(wèn)題,使所要 開(kāi)發(fā)的系統(tǒng)變得越來(lái)越清晰、越來(lái)越具體 .,9, 邏輯圖 一種可以反映因素或?qū)ο箝g邏輯關(guān)系 的圖形;,如:程序流程圖、控 制關(guān)系圖 etc., 工程圖 一種可以反映物體確定的結(jié)構(gòu)和順序 關(guān)系的圖形;,如:建筑工程圖、鐵路站場(chǎng)配置圖 etc., 圖論圖 包括圖論所定義的無(wú)向圖 G(V,E) 、 有向圖 G(V,A)、加權(quán)有(無(wú))向圖G(V,A(E

6、),w).,關(guān)系,稱為嚴(yán)格圖 (有嚴(yán)格確定的結(jié)構(gòu)形式和規(guī)范),4、數(shù)學(xué)模型,數(shù)學(xué)模型是指運(yùn)用數(shù)學(xué)符號(hào)和公式來(lái)表達(dá)、研究 對(duì)象系統(tǒng)的結(jié)構(gòu)或過(guò)程的模型 .,數(shù)學(xué)模型是用數(shù)學(xué)的語(yǔ)言、方法去近似地刻畫(huà)實(shí)際 , 是由數(shù)字、字母或其他數(shù)學(xué)符號(hào)組成的,描述現(xiàn)實(shí)對(duì) 象數(shù)量規(guī)律的數(shù)學(xué)公式、圖形或算法 .,是對(duì)現(xiàn)實(shí)對(duì)象本質(zhì)屬性的抽象而又簡(jiǎn)潔的刻畫(huà), 它或能解釋某些客觀現(xiàn)象,或能預(yù)測(cè)未來(lái)的發(fā)展規(guī) 律,或能為控制某一現(xiàn)象的發(fā)展提供某種意義下的最 優(yōu)策略或較好策略 .,Go back,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,10,二、 數(shù)學(xué)模型,Example 1,七橋問(wèn)題,18世紀(jì)的德國(guó)有個(gè)哥尼斯堡城,在流貫全城的普 雷爾

7、河兩岸和河中兩個(gè)島之間架設(shè)了七座橋,把河的 兩岸和兩島連接起來(lái),能否有這樣一種走法,它通過(guò) 每座橋一次且僅一次 .,該問(wèn)題由Euler在1736年解決,Solution :,1 組合優(yōu)化模型與算法,11,A,B,C,D,顯然,解決該問(wèn)題時(shí), 兩岸和島的大小、形狀以及 橋的長(zhǎng)短曲直都無(wú)關(guān),重要 的是什么?,每塊陸地間有幾座橋,對(duì)問(wèn)題進(jìn)行數(shù)學(xué)抽象:,把兩岸和兩島都看做頂點(diǎn),將連接這些頂點(diǎn)的橋 當(dāng)作邊,于是得到一無(wú)向圖 .,則七橋問(wèn)題就成為無(wú)向圖中是否存在通過(guò)每一邊 一次且僅一次的路(即一筆畫(huà))問(wèn)題 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,12,1 組合優(yōu)化模型與算法,A,B,C,D,Euler 在他

8、的論文中證明:,一個(gè)圖中存在一筆畫(huà)的 充要條件是同時(shí)滿足:,1、圖是連通的;,2、與圖中每一頂點(diǎn)(可能有兩點(diǎn)例外)相連的邊 (線度)必須是偶數(shù)條 .,這是關(guān)于圖論 的第一篇論文,見(jiàn)圖可知,與四個(gè)頂點(diǎn)相連的邊都是奇數(shù)條,因 而不可能存在通過(guò)每條邊一次且僅一次的畫(huà)法,即一 筆畫(huà)不存在 . 故七橋問(wèn)題不可能有解 .,問(wèn)題原型 七橋問(wèn)題,數(shù)學(xué)模型 一筆畫(huà)問(wèn)題,無(wú) 解 (一次過(guò)七座橋不可能),無(wú) 解 (一筆畫(huà)不可能),數(shù)學(xué)抽象,邏輯推理,翻譯回去,有無(wú)解?,這是利用數(shù)學(xué)模型分析和解決問(wèn)題的一個(gè)成功范例,13,(一) 數(shù)學(xué)模型的特點(diǎn),1、高度的抽象性,數(shù)學(xué)方法不僅要拋開(kāi)事物的次要屬性,突出事物 的本質(zhì)屬性

9、,而且要舍棄事物的物質(zhì)和能量方面的具 體內(nèi)容,只考慮其數(shù)量關(guān)系和空間形式,同時(shí)還要把 這些數(shù)量關(guān)系和空間形式作進(jìn)一步的抽象,加以形式 化和符號(hào)化,以便能夠進(jìn)行邏輯推理和數(shù)值運(yùn)算 .,這種高度的抽象性,實(shí)質(zhì)是對(duì)事物認(rèn)識(shí)上的高度 概括和深化,對(duì)同類問(wèn)題包含更多的經(jīng)驗(yàn)和理解 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,14,1 組合優(yōu)化模型與算法,2、高度的精確性,數(shù)學(xué)方法的高度精確性表現(xiàn)在三個(gè)方面:,一是表達(dá)各種因素、變量和它們之間的關(guān)系相當(dāng) 明確、清楚;二是邏輯推演和運(yùn)算規(guī)則十分嚴(yán)密;三 是結(jié)論非常確定 .,數(shù)學(xué)方法可以處理多變量、關(guān)系復(fù)雜的問(wèn)題,可 在有意義的范圍內(nèi)獲得令人滿意的計(jì)算精度 .,特別適

10、合于揭示事物的量的規(guī)定性,成為定量研 究的有力工具 .,15,3、應(yīng)用的普適性,數(shù)學(xué)方法的高度抽象和精確,使之比任何一種科 學(xué)方法的應(yīng)用范圍都更為廣泛 .,只存在尚未運(yùn)用數(shù)學(xué)方法的領(lǐng)域而不存在不能運(yùn) 用數(shù)學(xué)方法的領(lǐng)域 .,許多相同形式的數(shù)學(xué)模型可用于不同的實(shí)際問(wèn) 題,具有重要類比和借鑒意義 .數(shù)學(xué)方法的形式化和 公理化,使模型本身、計(jì)算過(guò)程和計(jì)算結(jié)果都便于交 流,數(shù)學(xué)模型易變動(dòng),便于修改和改變計(jì)算關(guān)系,分 析和求解問(wèn)題速度快,求解成本低 .,數(shù)學(xué)模型缺乏直觀性、形象性和實(shí)時(shí)感,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,16,1 組合優(yōu)化模型與算法,(二) 數(shù)學(xué)模型分類,數(shù)學(xué)模型分類的方法很多,如:,1

11、、按所研究問(wèn)題的性質(zhì)分類, 靜態(tài)模型與動(dòng)態(tài)模型, 確定型模型與隨機(jī)型模型, 連續(xù)模型與離散模型, 線性模型與非線性模型, 宏觀模型與微觀模型,17,2、按模型的解的特征分類,解析模型與數(shù)值模型,3、按模型所用的數(shù)學(xué)方法分類,初等模型、微分方程模型、差分方程模型、優(yōu) 化模型等,4、按模型研究的實(shí)際范疇分類,人口模型、生態(tài)系統(tǒng)模型 、交通流模型、經(jīng)濟(jì) 模型、 基因模型等,5、按對(duì)實(shí)際問(wèn)題了解的程度分類,白箱模型、灰箱模型、黑箱模型,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,18,1 組合優(yōu)化模型與算法,(三) 數(shù)學(xué)建模的基本步驟,數(shù)學(xué)模型因問(wèn)題不同而異,對(duì)同一問(wèn)題,從不同 角度、不同要求出發(fā),甚至問(wèn)題的解

12、表示結(jié)構(gòu)不同, 都可以建立不同的數(shù)學(xué)模型. 建立數(shù)學(xué)模型也沒(méi)有固 定的方法、標(biāo)準(zhǔn) . 不同的實(shí)際問(wèn)題,建模模式千差萬(wàn) 別.,在此介紹通常的幾個(gè)步驟:,數(shù)學(xué)建模問(wèn)題直接來(lái)源各領(lǐng)域?qū)嶋H,往往含糊不 清(目的、條件、類型 etc.). 首先,要對(duì)該問(wèn)題進(jìn) 行全面的、深入細(xì)微的調(diào)查和研究. 明確所解決問(wèn)題 的性質(zhì),著手收集數(shù)據(jù) ;,1、明確問(wèn)題,合理地、有目的地,注意精度,19,2、合理假設(shè),現(xiàn)實(shí)問(wèn)題錯(cuò)綜復(fù)雜,涉及面非常之廣. 一個(gè)數(shù)學(xué) 模型面面俱到、無(wú)所不包地反映一個(gè)現(xiàn)實(shí)是不可能 的,即使可能,也因其過(guò)于復(fù)雜而很難求解,也是沒(méi) 有必要的 . 所以,要作合理的假設(shè) .,1、簡(jiǎn)化問(wèn)題 2、限定適用范圍,

13、但也不能忽略實(shí)質(zhì)相關(guān)的因素,作假設(shè)的依據(jù)通常是出于對(duì)問(wèn)題內(nèi)在規(guī)律的認(rèn)識(shí), 或來(lái)自對(duì)數(shù)據(jù)或現(xiàn)象的分析,也可以是二者的綜合. 善于辨別問(wèn)題的主次,抓住主要因素,通過(guò)合理假設(shè), 使問(wèn)題簡(jiǎn)化以便進(jìn)行數(shù)學(xué)描述 .,假設(shè)是在模型的建立、求解和分析過(guò)程中完善 .,通常開(kāi)始讓問(wèn)題盡可能簡(jiǎn)化,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,20,1 組合優(yōu)化模型與算法,3、建立模型,建模時(shí),要分清問(wèn)題的類型恰當(dāng)使用數(shù)學(xué)工具; 抓住問(wèn)題的本質(zhì)簡(jiǎn)化變量之間的關(guān)系 .,用什么樣的方法建立數(shù)學(xué)模型,沒(méi)有絕對(duì)的標(biāo) 準(zhǔn);數(shù)學(xué)模型的形式可以是多種多樣,數(shù)學(xué)公式、表 格、圖形、算法 .,模型的優(yōu)劣在于是否采用了恰當(dāng)?shù)姆椒?,合理?描述了實(shí)際

14、問(wèn)題,而不在于是否用到了高深的數(shù)學(xué)工 具 .,數(shù)學(xué)建模是一個(gè)過(guò)程 .,21,4、模型求解,不同的模型要用到不同的數(shù)學(xué)工具求解 . 這就要 求從事實(shí)際工作者對(duì)相應(yīng)的數(shù)學(xué)分支知識(shí)有一定的了 解 .,可借助計(jì)算機(jī),特別是利用數(shù)學(xué)工具軟件 .,5、模型分析,對(duì)模型求出的解進(jìn)行數(shù)學(xué)上的分析,有助于對(duì)實(shí) 際問(wèn)題的解決 .,如:, 結(jié)果的誤差分析,誤差是否在允許的范圍內(nèi),分析誤差來(lái)源:,建模假設(shè)的誤差;,數(shù)據(jù)測(cè)量的誤差;,近似求解方法的誤差;,計(jì)算工具的舍入誤差 ., 結(jié)果的統(tǒng)計(jì)分析,結(jié)果是否符合特定的統(tǒng)計(jì)規(guī)律, 模型對(duì)數(shù)據(jù)的靈敏度分析,模型的結(jié)果是否會(huì)因數(shù)據(jù)的微小改變而發(fā)生大的變化, 對(duì)假設(shè)的魯棒性分析,

15、模型的結(jié)果是否對(duì)某一假設(shè)非常依賴, 不同模型間的對(duì)比分析,robustness,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,22,1 組合優(yōu)化模型與算法,6、模型檢驗(yàn),將求解結(jié)果和分析結(jié)果翻譯回到實(shí)際問(wèn)題之中, 與實(shí)際現(xiàn)象、實(shí)際數(shù)據(jù)進(jìn)行比較,檢驗(yàn)是否與實(shí)際吻 合 . 如果吻合較好,則模型及其結(jié)果可以應(yīng)用于實(shí)際 問(wèn)題;如果吻合不好,則需要對(duì)模型進(jìn)行修正 .,7、改進(jìn)模型,吻合不好,問(wèn)題常常出現(xiàn)在模型假設(shè)上 . 可能由 于假設(shè)了過(guò)于苛刻的條件,或者忽略了一些不該忽略 的因素. 所以, 要對(duì)實(shí)際問(wèn)題中的主次因素再次分析, 對(duì)模型進(jìn)行修改、補(bǔ)充、完善 . 需要多次反復(fù)才能達(dá) 到比較滿意的程度 。,23,8、模型

16、應(yīng)用,數(shù)學(xué)建模最終的目的是為了解決問(wèn)題 . 一方面可 以解釋以前的實(shí)踐成果;另一方面可以為現(xiàn)在的實(shí)際 問(wèn)題提供解決方案,甚至可以對(duì)一些不確定的現(xiàn)象或 規(guī)律作出預(yù)測(cè) .,現(xiàn)實(shí)問(wèn)題,簡(jiǎn)化、假設(shè),建立模型,求解模型,檢驗(yàn)分析模型,模型應(yīng)用,觀察、分析,收集數(shù)據(jù),確定主要因素,及相互關(guān)系,Go back,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,24,三、 組合優(yōu)化模型,Example 2,某商場(chǎng)根據(jù)客流量統(tǒng)計(jì)得出一周中每天所需要的 營(yíng)業(yè)員數(shù)如表:,營(yíng)業(yè)員配置問(wèn)題,如果規(guī)定每個(gè)營(yíng)業(yè)員每周連續(xù)工作 5 天,休息 2 天,求總?cè)藬?shù)最少的營(yíng)業(yè)員排班方案 .,Solution :,設(shè) xj 為從周 j 開(kāi)始連續(xù)工作

17、5 天的營(yíng)業(yè)員 人數(shù),j = 1,7 (其中 x7 為周日開(kāi)始連續(xù)工作 5 天的 營(yíng)業(yè)員數(shù)),則,可行解集是有限集,1 組合優(yōu)化模型與算法,25,Example 3 旅行商問(wèn)題,(Traveling Salesman Problem),TSP :,有一位旅行售貨員,欲到城市 v1,v2,,vn 進(jìn)行商品銷售,已知: 的距離為 wij.( , ).他從其中某個(gè)城市出發(fā),需訪問(wèn)每一個(gè) 城市一次而回到出發(fā)的城市.問(wèn)應(yīng)如何計(jì)劃他的旅行 路線,使他所走路線的總長(zhǎng)度最短?,TSP可分為:對(duì)稱(dij = dji) 和非對(duì)稱(dij dji)距離兩種,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,26,1 組合優(yōu)化模型

18、與算法,Hamilton 回路:,不含平行邊及自環(huán),這是1856年,Hamilton 首先提出的所謂環(huán)球 航行問(wèn)題而得名。它的存在性遠(yuǎn)比 Eular 回路的存 在性復(fù)雜得多。,最優(yōu) Hamilton 回路:,在賦權(quán)圖中,權(quán)和最小的 Hamilton 回路 .,過(guò)簡(jiǎn)單圖 G 的每一個(gè)頂點(diǎn)一次且僅一次的回路 .,27,最優(yōu)旅行商問(wèn)題與最優(yōu) Hamilton 回路一樣嗎?,如果不滿足三角不等式,則可通 過(guò)求最短路方法,構(gòu)造新圖,使之滿 足三角不等式 . 所以以下僅討論最優(yōu) 的 Hamilton 回路 .,2 5,2 3,Theorem 1 如果賦權(quán)圖滿足三角不等式 (歐氏距離),則它的最優(yōu)旅行商回路

19、 與最優(yōu) Hamilton 回路相同 (Hamilton 回路存在時(shí)).,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,28,1 組合優(yōu)化模型與算法,TSP 問(wèn)題的數(shù)學(xué)模型(非對(duì)稱的):,v6,v4,v5,v3,v2,v1,Note:條件(1),(2)表示每個(gè)城市經(jīng)過(guò)一 次,但不能保證它可行.,要求局部不構(gòu)成圈,條件(3)就是為 了約束這一點(diǎn) .,29,共同特點(diǎn):可行方案是有限的 組合優(yōu)化問(wèn)題,Definition 1 組合優(yōu)化問(wèn)題是一個(gè)極小化(或極大 化)的問(wèn)題,它是由以下三部分組成:,(1)實(shí)例集合 ;,(2)對(duì)每個(gè)實(shí)例 I,有一個(gè)有窮的可行解集合 S(I);,(3)目標(biāo)函數(shù) f ,它對(duì)于每個(gè)實(shí)例 I

20、 和每個(gè)可行解 S(I),賦以一個(gè)實(shí)數(shù) f (I, ). 則實(shí)例I的最優(yōu)解為 這樣一個(gè)可行解 * S(I) ,它使得對(duì)于所有S(I), 都有 (I, *) f (I, ) (f (I, *) f( I, )).,問(wèn)題:一類實(shí)際問(wèn)題的數(shù)學(xué)模型的總稱,如TSP、 LP etc ; 實(shí)例:(一個(gè)問(wèn)題中總包含了若干個(gè)參數(shù))對(duì)問(wèn)題 給定一組參數(shù)所得到的例子.,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,30,1 組合優(yōu)化模型與算法,組合優(yōu)化的數(shù)學(xué)模型:,Min f(x) s.t. g(x) 0 xD,其中x為決策變量,f(x)為目標(biāo)函數(shù),g(x)為約束函數(shù),D為決策變量的定義域,F=x|x D, g(x) 0可行

21、域(有限集),很多組合優(yōu)化問(wèn)題都可以給出整數(shù)線性規(guī)劃描 述,甚至在一些時(shí)候還不得不利用整數(shù)線性規(guī)劃的技 巧來(lái)解 . 當(dāng)然也可以用文字、網(wǎng)絡(luò)等來(lái)敘述 .,線性規(guī)劃是連續(xù)模型,但由于它的解的特殊結(jié) 構(gòu),也可以作為組合優(yōu)化問(wèn)題考慮 .,31,四、 關(guān)于算法,有兩種思想,像珠寶商放在天鵝絨上的寶石一樣 熠熠生輝,一個(gè)是微積分,另一個(gè)就是算法,微積分 以及在微積分基礎(chǔ)上建立起來(lái)的數(shù)學(xué)分析體系造就了 現(xiàn)代科學(xué),而算法則造就了現(xiàn)代世界 .,伯林斯基(D. Berlinski ),算法思想:指通過(guò)把數(shù)學(xué)問(wèn)題的求解分解為簡(jiǎn)單的、 刻板的、重復(fù)的機(jī)械動(dòng)作,達(dá)到以數(shù)目較多的、簡(jiǎn)單 的量的工作去實(shí)現(xiàn)較復(fù)雜的質(zhì)的目的

22、.,算法思想是數(shù)學(xué)發(fā)展的一個(gè)重要源泉,20 世紀(jì)中葉計(jì)算機(jī)的問(wèn)世是人類智力最偉大的成 就之一 . 算法是計(jì)算機(jī)的靈魂,隨著計(jì)算機(jī)融入現(xiàn)代 科學(xué)實(shí)踐和社會(huì)生活的各個(gè)方面,算法思想的意義與 作用日益為數(shù)學(xué)家所認(rèn)識(shí) . 是數(shù)學(xué)發(fā)展的機(jī)械化之路.,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,32,一個(gè)科學(xué)的計(jì)算過(guò)程,指一步步求解問(wèn)題的通 用程序,它是解決問(wèn)題的程序步驟的一個(gè)清晰 描述 .,算法是相對(duì)問(wèn)題而言的,不單單是針對(duì)問(wèn)題的 某個(gè)實(shí)例 .,算法:,Note:,假設(shè)你想把某個(gè)解決問(wèn)題的方法傳授給一臺(tái)沒(méi)有 任何智能的機(jī)器,以便由它來(lái)幫你完成解決這類問(wèn)題, 機(jī)器會(huì)要求你怎么做?,( 算法的能行性 ),你當(dāng)然不能只

23、告訴它一個(gè)大概或者模棱兩可、含 糊其辭,而應(yīng)該明確無(wú)誤地告訴它所有解決問(wèn)題的細(xì) 節(jié),而且這些細(xì)節(jié)應(yīng)詳細(xì)到機(jī)器可以執(zhí)行的程度(機(jī) 械性);你當(dāng)然也不可能無(wú)休止地進(jìn)行傳授,而只能 用到一些有限的符號(hào),告訴它一些有限的規(guī)則(有限 性) .,1 組合優(yōu)化模型與算法,33,如果算法從前一步到后一步的運(yùn)行是由 當(dāng)時(shí)狀態(tài)唯一確定的. 如:?jiǎn)渭冃?法,表上作業(yè)法 .,遺傳算法是隨機(jī)性算法 .,確定性算法:,數(shù)學(xué)上常常將算法分為數(shù)值算法和非數(shù)值算法 . 一般來(lái)說(shuō),數(shù)值算法用于科學(xué)計(jì)算,主要進(jìn)行代數(shù)運(yùn) 算;而非數(shù)值算法則用于數(shù)據(jù)處理,主要進(jìn)行比較和 邏輯運(yùn)算(也含代數(shù)運(yùn)算) .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,

24、34,對(duì)于一個(gè)極小化(極大化)優(yōu)化問(wèn)題, 如果給定任意一個(gè)實(shí)例I,算法A總能找到一個(gè)可 行解* S(I)。 使得 f(I, *) f(I, )(f(I, *) f(I, )),啟發(fā)式算法(近似算法,在4 中介紹),組合優(yōu)化總存在最優(yōu)算法,僅討論可計(jì)算問(wèn)題,最優(yōu)算法:,是否任何數(shù)學(xué)問(wèn)題都有算法求解嗎?,答案是否定的 (不可計(jì)算),停機(jī)問(wèn)題:給定一個(gè)帶輸入的計(jì)算機(jī)程序,它會(huì)停機(jī) 嗎?,英國(guó)數(shù)學(xué)家圖靈 (Turing) 證明了不存在一 個(gè)算法,它能對(duì)該問(wèn)題的一切實(shí)例給出正確答案 .,D.Hilbert 23個(gè)問(wèn)題之10 Diophantus 方程的 可解性 . (求出一個(gè)整系數(shù)方程的整數(shù)根),算法的

25、正確性不蘊(yùn)含算法的有效性,1 組合優(yōu)化模型與算法,35,五、 算法設(shè)計(jì)的基本方法,本節(jié)介紹算法設(shè)計(jì)的一些基本方法 . 在進(jìn)行復(fù)雜 的算法設(shè)計(jì)時(shí),常常利用這些基本方法(思想),有 必要熟練掌握 .,(一) 窮舉法,窮舉法:窮舉所有可能的解并進(jìn)行比較和選優(yōu)的方法 .,優(yōu)點(diǎn):獲得最優(yōu)解是確切無(wú)疑的(算法的正確性),對(duì)于運(yùn)算規(guī)模較小的、運(yùn)算時(shí)間允許的優(yōu)化問(wèn) 題,如無(wú)適合該問(wèn)題的優(yōu)化算法時(shí),可采用窮舉法 .,缺點(diǎn):需要大量的機(jī)時(shí)和內(nèi)存空間(算法的有效性),引言中對(duì)TSP問(wèn)題已有說(shuō) 明,復(fù)雜性為O(n-1)!),采用窮舉法的關(guān)鍵在于: 1、能否在理論上確定所求解問(wèn)題的全部可行解集; 2、對(duì)所求解問(wèn)題的全部

26、可行解集進(jìn)行比選是否可能. (計(jì)算時(shí)間復(fù)雜性),第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,36,(二) 登山法 (也稱貪心法),登山法:從對(duì)問(wèn)題的某一初始推測(cè)或初始解出發(fā),逐 步逼近給定的目標(biāo),并盡可能快地逼近更好的解;當(dāng) 進(jìn)行到某一步,不能再繼續(xù)逼近時(shí),算法便終止 .,得到的是近似解 或局部最優(yōu)解,方法簡(jiǎn)單、 適用面廣,登山法是一個(gè)多步?jīng)Q策過(guò)程,每一步的選擇都是 為了能構(gòu)成問(wèn)題的一個(gè)可行解,同時(shí)使目標(biāo)函數(shù)的值 增加最大或最小 .,選擇過(guò)程是以某些最優(yōu)化量度為依據(jù) .,最優(yōu)化量度可以是目標(biāo)函數(shù),也可以是別的量 度,它的選擇是登山法的關(guān)鍵 .,1 組合優(yōu)化模型與算法,37,TSP 的距離矩陣,Examp

27、le 2 用登山法求 TSP .,v5,v4,v3,v2,v1,4,1,4,3,2,3,5,7,2,1,Solution :,優(yōu)化準(zhǔn)則:最短距離.,從 v1 出發(fā),有4 個(gè)選擇, 按優(yōu)化準(zhǔn)則:選 v2 ;,得: v1 v2 v5 v3 v4 v1,總距離為:14,復(fù)雜性為 O(n2) .,記?。簺](méi)有免費(fèi)的午餐!,從選擇 p 個(gè)不同的 城市出發(fā),分別用登山法得到 p 個(gè)結(jié)果 . 比較得距離和最短 的路線 .,復(fù)雜性為 O(pn2) .,但求得的解更接近于最優(yōu)解,如從 v2 出發(fā),得:,v2 v1 v3 v4 v5 v2,總距離為:10,這是最優(yōu)解(運(yùn)氣好).,也可以從一個(gè)可行解出 發(fā),交換相鄰兩

28、個(gè)城市位置, 優(yōu)化準(zhǔn)則:總距離下降.,v1 v2 v5 v3 v4 v1,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,38,(三) 分枝與定界法,分枝與定界法的基本思想是對(duì)有約束條件的最優(yōu)化問(wèn) 題的所有可行解(其數(shù)目為有限集)空間適當(dāng)?shù)剡M(jìn)行 搜索 .,具體執(zhí)行時(shí),把可行解空間不斷分割為越來(lái)越小 的子集(稱為分枝),并確定每個(gè)分枝內(nèi)的解值的下 界或上界(稱為定界). 在每次分枝后,對(duì)凡是界超 出已知可行解值的子集被剪去,從而不斷縮小搜索范 圍.,這個(gè)過(guò)程一直進(jìn)行到找出最優(yōu)解為止,該可行解 的值不大于或不小于任何子集的界 .,優(yōu)點(diǎn):1、適用面廣 2、可檢查較少的解(運(yùn) 氣好)3、可獲得最優(yōu)解,缺點(diǎn):本質(zhì)是窮

29、 舉,復(fù)雜性大于窮舉法,給出一個(gè)重要思想: 設(shè)門檻 (稱為隱枚舉),1 組合優(yōu)化模型與算法,39,設(shè),如果 則稱問(wèn)題(2)是問(wèn)題(1)的松弛問(wèn)題.,Note :,1、松弛問(wèn)題未必比原問(wèn)題難解;,如:整數(shù)規(guī)劃與線性規(guī)劃;TSP 與指派問(wèn)題 etc.,如: A:尋找全國(guó)18 歲百米最快的運(yùn)動(dòng)員.,B:尋找全國(guó)所有百米最快的運(yùn)動(dòng)員.,顯然,B 問(wèn)題是 A 問(wèn)題的松弛問(wèn)題,且B 問(wèn)題更易解 .,2、如果松弛問(wèn)題易解,則先解松弛問(wèn)題是有益的 .,1)設(shè) x0 是松弛問(wèn)題的最優(yōu)解,且 則原問(wèn)題已解,2)即使 給出了原問(wèn)題最優(yōu)值的界 f(x0) .,x0,B,A,B,A,x0,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜

30、性,40,分枝與定界法為什么能少檢查一些解?,B,10s,B1,B2,10.2s,*,10s,B3,B4,10.3s,*,幾點(diǎn)注意:, 確定問(wèn)題(子問(wèn)題)的最優(yōu)值的界,通常是通過(guò)求解松弛問(wèn)題, 用松弛問(wèn)題的解作為界,也可 以用啟發(fā)式算法得到 .,Note : 松弛問(wèn)題選擇的原則,1、松弛問(wèn)題要與原問(wèn)題的 最優(yōu)值盡量接近;,2、松弛問(wèn)題要盡量容易解 .,這兩個(gè)原則不易統(tǒng)一,所以可選擇不同的松弛問(wèn)題,1 組合優(yōu)化模型與算法,41, 劃分方法的選擇,原則是希望分出來(lái)的子問(wèn)題容易被查清,可加快計(jì)算., 選哪個(gè)活問(wèn)題先檢查,1、先檢查最大上界(極大化問(wèn)題)的活問(wèn)題,優(yōu)點(diǎn):檢查子問(wèn)題較其他規(guī)則為少;,缺點(diǎn)

31、:計(jì)算機(jī)儲(chǔ)存量較大 .,2、先檢查最新產(chǎn)生的最大上界的活問(wèn)題,優(yōu)點(diǎn):計(jì)算機(jī)儲(chǔ)存量較少 ;,缺點(diǎn):需要更多的分支運(yùn)算 .,選擇的不同,提供了發(fā)揮的余地,分枝與定界法的重要在于它提出了一類新的思 路(隱枚舉法),使得許多原來(lái)不好解決的問(wèn)題有 了解決的可能性. (具有普適性),第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,42,(四) 分治法,分治法就是把原問(wèn)題分成若干個(gè)規(guī)模較小的子問(wèn)題, 這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同,對(duì)每個(gè)子 問(wèn)題分別求解,然后將各子問(wèn)題的解合并得到原問(wèn)題 的解 .,如果子問(wèn)題仍較復(fù)雜,可遞歸使用上述方法 .,Note:?jiǎn)栴}的類別在細(xì)分過(guò)程中不允許改變,改變的 只是問(wèn)題的尺度 .,分

32、治法的基本步驟:,分治法在每一層遞歸上都有三個(gè)步驟:,分解:將原問(wèn)題分解為若干個(gè)規(guī)模較小,相互獨(dú)立, 與原問(wèn)題形式相同的子問(wèn)題;,解決:若子問(wèn)題規(guī)模較小而容易被解決則直接解,否 則遞歸地解各個(gè)子問(wèn)題;,合并:將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解.,1 組合優(yōu)化模型與算法,43,整序問(wèn)題的快速算法是典型的分治策略運(yùn)用.,8 1 9 6 7 5 3 2,8,1,9,6,7,5,3,2,合并,合并,合并,合并,1 8,6 9,5 7,2 3,1 6 8 9,2 3 5 7,1 2 3 5 6 7 8 9,合并,合并,合并,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,44,分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征:

33、,1、該問(wèn)題的規(guī)??s小到一定的程度就可以容易地解決;,2、該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;,3、利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn) 題的解;,4、該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的,即 子問(wèn)題之間不包含公共的子子問(wèn)題 .,如何使用,因問(wèn)題而異.,分治法的應(yīng)用很廣,如鐵路運(yùn)輸技術(shù)計(jì)劃中的 空車調(diào)度計(jì)劃等.,1 組合優(yōu)化模型與算法,45,(五) 遞歸方法,遞歸就是自己調(diào)用自己的過(guò)程 . 這里的“自己”可以 是函數(shù)、過(guò)程、語(yǔ)言結(jié)構(gòu)和解題方法等 .,遞歸方法思路: 第一步驟(遞歸步驟):將規(guī)模較大的原問(wèn)題分 解為一個(gè)或多個(gè)規(guī)模更小、但具有類似于原問(wèn)題特性 的子問(wèn)題。即較大的問(wèn)題遞

34、歸地用較小的子問(wèn)題來(lái)描 述,解原問(wèn)題的方法同樣可用來(lái)解這些子問(wèn)題. 第二步驟:確定一個(gè)或多個(gè)無(wú)須分解、可直接求 解的最小子問(wèn)題(稱為遞歸的終止條件).,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,46,Example 4,斐波那契數(shù)定義為下列無(wú)窮整數(shù)的序列:,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,,第 n 個(gè)元素是緊接在它之前的兩個(gè)元素之和,用 FIB(n) 表示第 n 個(gè)斐波那契數(shù),則可用如下遞歸關(guān)系 式定義:,FIB(n) = FIB(n-1) + FIB(n-2) FIB(1) = 1 FIB(2) = 1,為了計(jì)算 FIB(n) ,要遞歸調(diào)用 FIB(n-1)

35、 、FIB(n-2) , 而為了計(jì)算 FIB(n-1) ,除了利用已調(diào)用的 FIB(n-2) 外,還要調(diào)用FIB(n-3),因此,為了計(jì)算FIB(n) 需作 n-1 次遞歸調(diào)用 .,遞歸調(diào)用次數(shù) 遞歸深度,分治與遞歸像一對(duì)孿生兄弟,經(jīng)常同時(shí)應(yīng) 用在算法設(shè)計(jì)之中,并由此產(chǎn)生許多高效算法.,1 組合優(yōu)化模型與算法,47,(六) 動(dòng)態(tài)規(guī)劃法,Example 5,100多年前,有位美國(guó)推銷員乘驛站馬車 向西旅行 ,從州A (state ,狀態(tài)) 到州E 如圖,需要4個(gè) 驛程(stage,階段)。問(wèn)題為求從 State A到 State E 走哪條途徑使他最安全?,原問(wèn)題為求從 A 到 E 走哪條途徑使

36、保險(xiǎn)單 (policy,策略)的總費(fèi)用達(dá)到最小?,6,4,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,48,6,4,Note :,作出各相繼驛程上最佳決策。不一定產(chǎn)生總 的最佳決策(即Greedy 算法未必取得最佳策略).,如: A 2 B1 4 C2 3 D2 4 E,費(fèi)用和為13,而 A 3 B3 1 C2,費(fèi)用更低廉,窮舉法:,即列出所有的可行路徑,逐個(gè)路徑進(jìn)行比 較,并從中選出最佳路徑.,共有路徑 18 條 .,1 組合優(yōu)化模型與算法,49,如果 s1s2sk sk+1 sn 是 s1 sn 的最短路, 則該路上任一點(diǎn)sksk+1sn 是sk sn 的最短路 .,結(jié)論:,設(shè) Sk 表示在第k個(gè)驛

37、程上出發(fā)州的集合(狀態(tài)集 合), S1 = A , S2 = B1,B2,B3 , S3 = C1, C2,C3 ,S4 = D1,D2 ,,uk(sk) = sk+1 表示在第k個(gè)驛程從 sk 出發(fā)所作的決 策 , 如:u2(B1) = C1 或 C2 或 C3 ( C1,C2,C3 表示第k 驛程從B1出發(fā)的允許決策集合) .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,50,6,4,fk(sk) 表示從第 k 個(gè)驛程的出發(fā)州 sk E 的最短 路的費(fèi)用和,f1(s1) 即為所求.,若已知 f2(B1)、f2(B2)、f2(B3),則,當(dāng)k = 4時(shí),,3,4,1 組合優(yōu)化模型與算法,51,6,4,

38、3,4,當(dāng)k = 3時(shí),,5,7,6,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,52,6,4,3,4,5,7,6,當(dāng) k = 2 時(shí),,8,8,11,1 組合優(yōu)化模型與算法,53,6,4,3,4,5,7,6,8,8,11,當(dāng) k = 1 時(shí),,11,u2( B3 ) = C2 u3( C2 ) = D2 u4( D2 ) = E 最安全道路為AB3C2D2E,最小費(fèi)用為11 .,Note 優(yōu)點(diǎn): 減少計(jì)算量,(共 18 次加法,11次比較); 豐富了計(jì)算結(jié)果 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,54,動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化的數(shù)量化方法.,動(dòng)態(tài)規(guī)劃的成功之處在于,它可以把一個(gè) n 維決 策

39、問(wèn)題變換為 n 個(gè)一維最優(yōu)化問(wèn)題 ;,另外,動(dòng)態(tài)規(guī)劃能夠得到全局最優(yōu)解 .,以空間換時(shí)間;,動(dòng)態(tài)規(guī)劃是求解某類問(wèn)題的一種方法,是一種算 法設(shè)計(jì)的策略,而不是一種特殊的算法(不像 LP 有 統(tǒng)一的數(shù)學(xué)模型和算法).,必須對(duì)具體問(wèn)題進(jìn)行具體 分析:適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿足最優(yōu)化原理和無(wú) 后效性;以豐富的想象力和靈活的技巧建立動(dòng)態(tài)規(guī)劃 模型及求解 .,動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于,對(duì)于重復(fù)出現(xiàn)的子問(wèn) 題,只在第一次遇到時(shí)加以求解,并把答案保存起 來(lái),讓以后再遇到時(shí)直接引用,不必重新求解.,最優(yōu)化原理(最優(yōu)子結(jié)構(gòu)性質(zhì)):一個(gè)最優(yōu)化策略具 有這樣的性質(zhì),不論過(guò)去狀態(tài)和決策如何,對(duì)前面的 決策所形成的狀態(tài)而言

40、,余下的諸決策必須構(gòu)成最優(yōu) 策略. 簡(jiǎn)言之, 一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的.,無(wú)后效性(馬爾科夫性)是指:如果給定某一階段的 狀態(tài),則在這一階段以后過(guò)程的發(fā)展,不受這階段以 前各階段狀態(tài)的影響,而只與當(dāng)前的狀態(tài)有關(guān). 換句 話說(shuō),過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響未 來(lái)的發(fā)展 . 每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié).,用到了遞歸,與貪 心法、分治法、分 枝與定界區(qū)別?,1 組合優(yōu)化模型與算法,55,動(dòng)態(tài)規(guī)劃問(wèn)題具有以下基本特征: 1、問(wèn)題具有多階段決策的特征; 2、每一階段都有相應(yīng)的“狀態(tài)”與之對(duì)應(yīng); 3、每一階段都面臨一個(gè)決策; 4、每一階段的最優(yōu)解問(wèn)題可以遞歸地歸結(jié)為下一階 段各個(gè)

41、可能狀態(tài)的最優(yōu)解問(wèn)題,各子問(wèn)題與原問(wèn) 題具有完全相同的結(jié)構(gòu) .,動(dòng)態(tài)規(guī)劃的基本概念:,1、階段(stage) 是對(duì)整個(gè)過(guò)程的自然劃分. 用 k = 1,2, n 表示階段序號(hào),把 k 稱為階段變量 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,56,2、狀態(tài) (state) 狀態(tài)表示每個(gè)階段開(kāi)始時(shí)所面臨的自然 狀況或客觀條件. 既是該階段某支路的始點(diǎn),又是前 一階段某支路的終點(diǎn).,描述狀態(tài)的變量稱為狀態(tài)變量,記作sk,它表示第 k 階段所處的狀態(tài). 狀態(tài)變量取值的全體,稱為允許 狀態(tài)集合,記作Sk . 顯然有 sk Sk,如前例 S1= A ,S2= B1,B2,B3 ,etc. 而 s2 可取B1,

42、B2,B3 .,3、決策 (decision) 當(dāng)某階段的狀態(tài)確定后,可以作 出各種不同的選擇,從而確定下一階段的狀態(tài),這種 選擇稱為決策.,1 組合優(yōu)化模型與算法,57,描述決策的變量稱為決策變量,用 uk(sk) 表示第 k 階段當(dāng)狀態(tài)處于 sk 時(shí)的決策變量.,決策變量允許取值的范圍稱為允許決策集合,常 用Dk(sk) 表示第 k 階段從狀態(tài) sk 出發(fā)的允許決策集 合, 顯然有 uk(sk) Dk(sk) .,在前例中,D1(A) = B1,B2,B3 , D2(B1) = C1,C2,C3 etc .,4、策略 (policy) 是一個(gè)按順序排列的決策組成的集合,由過(guò)程的第 k 階段

43、開(kāi)始到終止?fàn)顟B(tài)為止的過(guò)程, 稱 為問(wèn)題的后部子過(guò)程 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,58,由每階段的決策按順序排列組成的可行決策函數(shù) 序列 uk(sk) ,uk+1(sk+1) , ,un(sn) ,稱為 k 子過(guò)程 策略,簡(jiǎn)稱子策略.,記為 pk , n(sk)= uk(sk) , uk+1(sk+1) , , un(sn) .,當(dāng) k = 1 時(shí),此決策函數(shù)序列稱為全過(guò)程的一個(gè) 策略,簡(jiǎn)稱策略,記 p1,n(s1) .,可供選擇的策略有一定的范圍,稱為允許策略集 合,用 P1, n(s1) 表示 . 從 P1, n(s1) 中找出達(dá)到最優(yōu)效果 的策略稱為最優(yōu)策略,記 p1,n*= p

44、1,n*(s1)= u1*(s1) ,u2*(s2),,un*(sn) .,1 組合優(yōu)化模型與算法,59,5、狀態(tài)轉(zhuǎn)移方程 (equation of state transition) 反映 前后階段狀態(tài)之間的關(guān)系的方程 記為:sk+1=Tk(sk,uk) .,體現(xiàn)了無(wú)后效性,正是能將多階段化為單階段決策的理論依據(jù),(前例: sk+1 = uk(sk)),6、指標(biāo)函數(shù)和最優(yōu)值函數(shù) (objective function and optimal value function) 階段的指標(biāo)函數(shù)是對(duì)應(yīng)某一階 段狀態(tài)和從該狀態(tài)出發(fā)的一個(gè)決策的某種效益度量, 用vk(sk,uk) 表示 .,過(guò)程指標(biāo)函數(shù)

45、(又稱目標(biāo)函數(shù)) 是用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo),它是定 義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù),記作 Vk,n =Vk,n(sk , uk , sk+1 , uk+1 , , sn , un) ( k = 1,2,,n ),當(dāng) k = 1 時(shí),就是全過(guò)程的指標(biāo)函數(shù) . 指標(biāo)函數(shù)也是初始狀態(tài)和策略的函數(shù) 即 Vk,n = Vk,n(sk,pk,n(sk).,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,60,Note 指標(biāo)函數(shù)應(yīng)具有可分離性,即Vk,n可表示為:,Vk,n(sk , uk , sk+1 , uk+1 , , sn , un) =,且 對(duì)于Vk+1 , n 嚴(yán)格單調(diào).,常見(jiàn)的指標(biāo)函數(shù)

46、的形式有: 全過(guò)程和它的任一后部子過(guò)程的指標(biāo)函數(shù)等于各 階段指標(biāo)函數(shù)之和,即:,Vk,n(sk , uk , sk+1 , uk+1 , , sn , un) =,或,1 組合優(yōu)化模型與算法,61, 全過(guò)程和它的任一后部子過(guò)程的指標(biāo)函數(shù)等于各階 段指標(biāo)函數(shù)之積,即:,指標(biāo)函數(shù)的最優(yōu)值,稱為最優(yōu)值函數(shù),記 fk(sk),(opt 即 optimization, 具體問(wèn)題可取 min,max),或,f1(s1) 即為全過(guò)程的最優(yōu)策略.,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,62,Note 當(dāng)初始狀態(tài)給定時(shí),用逆序的方式比較好,當(dāng) 終止?fàn)顟B(tài)給定時(shí),用順序的方式比較好,通常初始 狀態(tài)給定的情況居多,所以用

47、逆序的方式比較多 .,對(duì)第一類指標(biāo)函數(shù)其基本方程為:,1 組合優(yōu)化模型與算法,63,Example 6,用動(dòng)態(tài)規(guī)劃法解 TSP,距離矩陣如右:,Solution :,不妨設(shè)從 v1 出發(fā)回 到 v1 .,用 f( vi; V) 表示從 vi 出 發(fā),經(jīng)頂點(diǎn)集合 V 中的點(diǎn)各一 次,回到 v1 點(diǎn)的最短路 .,則動(dòng)態(tài)規(guī)劃函數(shù)方程為:,用 f(v1; v2,v3,v4) 表示從 v1 出發(fā)經(jīng) v2,v3,v4 各一次 最后返回 v1 的最短路長(zhǎng)度 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,TSP 的距離矩陣,64,由動(dòng)態(tài)規(guī)劃函數(shù)方程有:,為了計(jì)算 ,,必須先計(jì)算,而,1 組合優(yōu)化模型與算法,65,計(jì)算

48、順序?yàn)椋?第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,TSP 的距離矩陣,66,TSP 的距離矩陣,最后計(jì)算:,通過(guò)下標(biāo),不難得最優(yōu)回路為: v1v3v4v2v1,用動(dòng)態(tài)規(guī)劃算法求 TSP , 其時(shí)間復(fù)雜性為 O(n 2n) .,1 組合優(yōu)化模型與算法,67,(七) 探索法,探索法是一種對(duì)給定的問(wèn)題能通過(guò)某種途徑(容易得 到、比求最優(yōu)解的算法速度快)進(jìn)行探索而找到一個(gè) 較好的解(不一定是最優(yōu)解,有時(shí)探索甚至失敗)的 算法 .,設(shè)計(jì)探索法的一種常用方法是列出精確解的所有 要求,并把這些要求分成兩類: 1、必須滿足的要求;2、允許折衷的要求 . 探索算法的設(shè)計(jì)目標(biāo)就是保證第一類要求得到滿 足,對(duì)第二類要求要

49、盡量滿足,但并不一定滿足 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,啟發(fā)式算法,68,(八) 倒推法,倒推法是從某個(gè)目標(biāo)或某個(gè)解出發(fā),倒推到這個(gè)問(wèn)題 的初始陳述 . 如果這個(gè)過(guò)程是可以逆轉(zhuǎn)的,則從問(wèn)題 的陳述可以推得問(wèn)題的解 .,倒推法不是從某個(gè)解推導(dǎo)出什么新的結(jié)論,而是 猜測(cè)能使結(jié)論成立的前提條件,然后再?gòu)倪@些前提條 件出發(fā),找出能導(dǎo)致它們成立的新的前提條件,如此 繼續(xù)尋找 .,有可能在進(jìn)行到某一步時(shí)新的前提條件會(huì) 與已知條件(即問(wèn)題的初始陳述)一致 . 這時(shí),由于 已知條件成立,所以在已知條件和解之間所有的前提 條件都成立,從而解必定成立 .,適用于倒推法的問(wèn)題應(yīng)滿足以下兩個(gè)條件: 1、問(wèn)題必

50、須有唯一解; 2、在問(wèn)題中出現(xiàn)的函數(shù)是單值的,或者說(shuō)對(duì)每一條 輸出信息都可以找到唯一的一條輸入信息(又稱 1 對(duì) 1 運(yùn)算).,1 組合優(yōu)化模型與算法,69,Example 7,水罐問(wèn)題,有兩個(gè)水罐,它們的容積分別為 7L 和 3L,除此 之外沒(méi)有別的容器 . 水的供應(yīng)是充分的 . 怎樣用這兩 個(gè)水罐量出 5L 水?,Solution :,這個(gè)問(wèn)題的解是在大罐里裝有 5L 水 .,從解往前倒推,有五種情況可能導(dǎo)致解的產(chǎn)生:, 大罐里有 2L 水,再?gòu)男」蘩锏谷?3L 水;, 大罐里裝滿水,小罐里有 1L 水,從大罐里倒出2L 水到小罐里,剩下 5L;, 大罐里有 3L 水,再?gòu)男」蘩锏谷?2L

51、 ;, 大罐里有 4L 水,再?gòu)男」蘩锏谷?1L ;, 大罐里有 6L 水,小罐里有 2L ,從大罐里往 小罐里倒入 1L 水,剩下 5L 水 .,在這五種情況中,第一和第二兩種情況的可能性 大,下面從第二種情況出發(fā)再往前推 .,先把大罐裝滿,再用小罐從大罐里量出兩次共 6L 水,使之剩下 1L 水,把它倒入小罐,然后把大罐 再裝滿 . 這就得到了上述第二種情況 . 這種情況發(fā)生 后,從大罐往小罐到2L 水,剩下 5L 水,問(wèn)題得到了 解決 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,70,(九) 回溯法,回溯法是一種滿足一定約束條件的窮舉式搜索法,它 的搜索方式與對(duì)樹(shù)的深度優(yōu)先搜索方式相似,但由于

52、 規(guī)定了問(wèn)題的解必須滿足一些約束條件,因此需要搜 索的空間大大減少 .,如果問(wèn)題的解能表示為一個(gè) n 元組 (x1, x2, , xn) 則可采用回溯法求解 .,回溯法求解的約束條件一般分為兩類:,1、顯約束,每個(gè) xi 的取值范圍;,2、隱約束,滿足判定函數(shù)的關(guān)于解空間上的多元式 .,1 組合優(yōu)化模型與算法,71,Example 8,設(shè)有一 44 的棋盤(pán)(即每行每列都有 4 個(gè)正方格的棋盤(pán)),用 4 個(gè)棋子布到格子上,要求滿 足一下兩個(gè)條件:,1、任意兩個(gè)棋子不在同一行和同一列上;,2、任意兩個(gè)棋子不在一對(duì)角線上 .,試問(wèn)有多少種的布局 ?,Solution :,如果采用窮舉式搜索,先不考慮

53、 1、2 兩 個(gè)條件,則布到每一行的棋子有 4 個(gè)選擇,故共有 44 = 256種方案 .,設(shè) xi 表示放在第 i 行上的棋子的列數(shù),,這是顯約束,顯然沒(méi)有必要!,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,72,隱約束有:,不同列,不在一對(duì)角線上,搜索過(guò)程如下:,這種一旦發(fā)現(xiàn)前面已是“此路不通”,立即回頭, 改換路徑,而不是一條道走到底的策略,就是回溯法 的基本思想 .,向前走,碰壁回頭,1 組合優(yōu)化模型與算法,73,(十) 模擬法,在實(shí)際科研和生產(chǎn)中有許多大系統(tǒng),要構(gòu)造大系 統(tǒng)的模型、對(duì)它們分析和求解都是相當(dāng)困難的 . 變量 之間的關(guān)系難以確定,隨機(jī)變量的分布不得而知,甚 至影響因素就找不全 .

54、利用計(jì)算機(jī)對(duì)大系統(tǒng)進(jìn)行模擬是研究大系統(tǒng)的一 種好方法 .,模擬法有許多優(yōu)點(diǎn): 1、它能按預(yù)定要求去研究系統(tǒng)的各個(gè)方面,借助計(jì)算 機(jī)的高速運(yùn)算和邏輯判斷能力,可以同時(shí)顧及系統(tǒng)各 個(gè)方面的結(jié)構(gòu),容易展現(xiàn)系統(tǒng)動(dòng)態(tài)變化的具體細(xì)節(jié) ;,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,直接解決問(wèn)題的方法,是一種建模方法.,74,2、模擬的方法比將系統(tǒng)置于實(shí)際環(huán)境直接進(jìn)行試驗(yàn) 的方法要節(jié)省很多時(shí)間和經(jīng)費(fèi); 3、模擬可用不同的時(shí)間比例尺進(jìn)行, 可放慢時(shí)間,在 微觀上認(rèn)真考察系統(tǒng)的性態(tài);也可加快時(shí)間,在宏觀 和大范圍上觀察系統(tǒng)的行為;還可以使時(shí)間暫停、返 回和重置,以便反復(fù)、詳盡地研究系統(tǒng)在任意時(shí)段的 各種反常的或重要的性態(tài)

55、及行為,這些都是在實(shí)際系 統(tǒng)中很難或根本不可能實(shí)現(xiàn)的 .,模擬是一項(xiàng)實(shí)驗(yàn)技術(shù),其實(shí)驗(yàn)結(jié)果取決于所采用 的模型和數(shù)據(jù) .,其他需要應(yīng)用模擬的情況: 1、有危險(xiǎn)性或代價(jià)過(guò)高的事情; 2、一旦實(shí)施,無(wú)法復(fù)原或產(chǎn)生嚴(yán)重后果的事情; 3、某種理論研究的結(jié)果需要驗(yàn)證 . etc .,以上介紹了十種基本的算法設(shè)計(jì)方法,在實(shí)際應(yīng) 用中,常常是幾種方法配合使用,以提高算法的效率 .,Go back,1 組合優(yōu)化模型與算法,75,在廣泛的意義下,執(zhí)行算法的效率是用執(zhí)行算法 所用的全部計(jì)算資源的多少來(lái)衡量(時(shí)間、空間),但通 常用時(shí)間作為衡量標(biāo)準(zhǔn),這就是計(jì)算(時(shí)間)復(fù)雜性問(wèn)題.,一、 如何計(jì)算時(shí)間,1 與實(shí)例的輸入

56、規(guī)模有關(guān),是輸入規(guī)模 的函數(shù)(輸入規(guī)模指的是:一個(gè)問(wèn)題的實(shí)例所有參數(shù) 的二進(jìn)制表示的長(zhǎng)度的總和。可簡(jiǎn)化為決策變量的個(gè) 數(shù)n,或者頂點(diǎn)的個(gè)數(shù)m .)f(n) , g(m) etc.,用初等運(yùn)算算術(shù)運(yùn)算、比較、轉(zhuǎn)移等指令的次 數(shù),來(lái)表示一個(gè)算法在假設(shè)的計(jì)算機(jī)上執(zhí)行時(shí)所需的 時(shí)間。,相關(guān)因素:,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,2 計(jì)算復(fù)雜性問(wèn)題,76,2 與實(shí)例的參數(shù)有關(guān) , 如LP 問(wèn)題: max z=cx s.t. Axb x0, c 0 , b 0,算法的時(shí)間復(fù)雜性是關(guān)于實(shí)例輸入長(zhǎng)度 的函數(shù),用來(lái)表示算法的時(shí)間需求. 對(duì)于每一個(gè)可能 的輸入長(zhǎng)度,它是該算法解此輸入長(zhǎng)度的最壞可能的 實(shí)例所需的

57、時(shí)間(基本運(yùn)算步驟).,相關(guān)因素:,Definition 1,2 計(jì)算復(fù)雜性問(wèn)題,77,研究計(jì)算復(fù)雜性問(wèn)題主要是針對(duì)n很大的情形,1 9n2 與 2n2 O(n2),2 f(n) = 12n4 - 8n3 + 5n2 + 2n - 80,f(n) = O(n4),當(dāng)n無(wú)限增大時(shí),,Ln n , n( 0) , an (a 1),趨向于無(wú)窮大的速度如何?,Note:,問(wèn):,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,78,復(fù)雜性分析的一個(gè)研究方向:對(duì)算法進(jìn)行評(píng)價(jià),給定n個(gè)整數(shù)x1,x2,xn, 要求將他們從小到大重新排列,取出x1,x2,xn中的最小者(需比較 n-1次)令其為b1(需n次賦值),從x1,

58、x2,xn中去 掉b1,在余下的n-1個(gè)數(shù)中選出最小者,令其為b2, 直到得到b1,b2,bn,易知其算法共做了n(n-1)/2次比 較,至多n(n+1)/2次賦值,計(jì)算復(fù)雜性為,O(n2).,Example 9 整序問(wèn)題:,比較交換法:,二、如何評(píng)價(jià)算法的好壞(從計(jì)算復(fù)雜性角度),2 計(jì)算復(fù)雜性問(wèn)題,79,先 將兩個(gè)單調(diào)不減的數(shù)列u1,u2um與v1,v2vm 合并為一個(gè)單調(diào)不減的數(shù)列w1,w2w2m方法為u1與v1 比較,若u1 v1,w1 :=v1 . 再對(duì)u1與v2進(jìn)行比較, 依次對(duì) w2,w3w2m賦值,計(jì)算量為O(m).,快速算法:,將 x1,x2,xn從小到大重新排列(設(shè):n=2p+1 如果n 不是2的冪次可補(bǔ)充 若干個(gè)很大的數(shù)字使之成 為2的冪次).,確定一個(gè)wj 需要一次比較一次賦值,共需要(2m-1)次比較,2m次賦值 .,第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性,80,將2p+1個(gè)數(shù)分成2p個(gè)單調(diào)不減的2元組,計(jì)算量為O(2p),O(2p)= 2p-1 O(2),計(jì)算量為O(2p),綜上,算法總工作量為: (p+1) *O(2p)=O(n logn),8 1 9 6 7 5 3 2,(8 1)(9 6)(7 5)(3 2),1 8 6 9 5 7 2 3,(1 8 6 9) (5 7 2

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論