數(shù)學(xué)建模 - 第一章 組合優(yōu)化模型與計(jì)算復(fù)雜性課件

第一章組合優(yōu)化模型與計(jì)算復(fù)雜性組合優(yōu)化理論

CombinatorialOptimizationTheory1數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性第一章組合優(yōu)化模型

與計(jì)算復(fù)雜性§1組合優(yōu)化模型與算法§2計(jì)算復(fù)雜性問(wèn)題§3啟發(fā)式算法2數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性第一章組合優(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è)面；出于相同的研究目的，對(duì)于同一個(gè)對(duì)象系統(tǒng)，也可能建立不同的模型，反映不同的研究角度、考察因素和價(jià)值取向.一、關(guān)于模型3數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§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ì)的.4數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性

從認(rèn)識(shí)論上看，模型是作為認(rèn)識(shí)與實(shí)踐活動(dòng)的中介.現(xiàn)實(shí)世界認(rèn)識(shí)（信息）

模型實(shí)踐活動(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ù)雜性5數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§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)信息不斷的采集、積累和加工，這就是用模型研究問(wèn)題的現(xiàn)實(shí)活動(dòng).6數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（三）模型的分類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ù)雜性7數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§1組合優(yōu)化模型與算法2、相似模型

相似模型是根據(jù)不同系統(tǒng)間的相似規(guī)律（包括幾何相似、邏輯相似和過(guò)程相似等）而建立的用于研究的模型.3、圖形模型

地球儀、船體放樣模型、飛機(jī)風(fēng)洞實(shí)驗(yàn)?zāi)M模型等等圖形模型可以表達(dá)非常豐富的內(nèi)容，主要有：①圖畫

——一種可以示形的圖形；②草圖

——一種可以示意的圖形；③框圖

——一種可以表示系統(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)越具體.8數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性④邏輯圖

——一種可以反映因素或?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)，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ǔ)言、方法去近似地刻畫實(shí)際,是由數(shù)字、字母或其他數(shù)學(xué)符號(hào)組成的，描述現(xiàn)實(shí)對(duì)象數(shù)量規(guī)律的數(shù)學(xué)公式、圖形或算法.

是對(duì)現(xiàn)實(shí)對(duì)象本質(zhì)屬性的抽象而又簡(jiǎn)潔的刻畫，它或能解釋某些客觀現(xiàn)象，或能預(yù)測(cè)未來(lái)的發(fā)展規(guī)律，或能為控制某一現(xiàn)象的發(fā)展提供某種意義下的最優(yōu)策略或較好策略.Goback第一章組合優(yōu)化模型與計(jì)算復(fù)雜性9數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性二、數(shù)學(xué)模型Example1七橋問(wèn)題18世紀(jì)的德國(guó)有個(gè)哥尼斯堡城，在流貫全城的普雷爾河兩岸和河中兩個(gè)島之間架設(shè)了七座橋，把河的兩岸和兩島連接起來(lái)，能否有這樣一種走法，它通過(guò)每座橋一次且僅一次.該問(wèn)題由Euler在1736年解決Solution:§1組合優(yōu)化模型與算法10數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性ABCD

顯然，解決該問(wèn)題時(shí)，兩岸和島的大小、形狀以及橋的長(zhǎng)短曲直都無(wú)關(guān)，重要的是什么？每塊陸地間有幾座橋?qū)?wèn)題進(jìn)行數(shù)學(xué)抽象：

把兩岸和兩島都看做頂點(diǎn)，將連接這些頂點(diǎn)的橋當(dāng)作邊，于是得到一無(wú)向圖.

則七橋問(wèn)題就成為無(wú)向圖中是否存在通過(guò)每一邊一次且僅一次的路（即一筆畫）問(wèn)題.第一章組合優(yōu)化模型與計(jì)算復(fù)雜性11數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§1組合優(yōu)化模型與算法ABCDEuler

在他的論文中證明：

一個(gè)圖中存在一筆畫的充要條件是同時(shí)滿足：1、圖是連通的；2、與圖中每一頂點(diǎn)（可能有兩點(diǎn)例外）相連的邊（線度）必須是偶數(shù)條.這是關(guān)于圖論的第一篇論文

見(jiàn)圖可知，與四個(gè)頂點(diǎn)相連的邊都是奇數(shù)條，因而不可能存在通過(guò)每條邊一次且僅一次的畫法，即一筆畫不存在.故七橋問(wèn)題不可能有解

.問(wèn)題原型七橋問(wèn)題數(shù)學(xué)模型一筆畫問(wèn)題無(wú)解(一次過(guò)七座橋不可能)無(wú)解(一筆畫不可能)數(shù)學(xué)抽象邏輯推理翻譯回去有無(wú)解？這是利用數(shù)學(xué)模型分析和解決問(wèn)題的一個(gè)成功范例12數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（一）數(shù)學(xué)模型的特點(diǎn)1、高度的抽象性

數(shù)學(xué)方法不僅要拋開(kāi)事物的次要屬性，突出事物的本質(zhì)屬性，而且要舍棄事物的物質(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ù)雜性13數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§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ì)算精度.

特別適合于揭示事物的量的規(guī)定性，成為定量研究的有力工具.14數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性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ù)雜性15數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§1組合優(yōu)化模型與算法（二）數(shù)學(xué)模型分類數(shù)學(xué)模型分類的方法很多，如：1、按所研究問(wèn)題的性質(zhì)分類⑴靜態(tài)模型與動(dòng)態(tài)模型⑵確定型模型與隨機(jī)型模型⑶連續(xù)模型與離散模型⑷線性模型與非線性模型⑸宏觀模型與微觀模型16數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性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ù)雜性17數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§1組合優(yōu)化模型與算法（三）數(shù)學(xué)建模的基本步驟

數(shù)學(xué)模型因問(wèn)題不同而異，對(duì)同一問(wèn)題，從不同角度、不同要求出發(fā)，甚至問(wèn)題的解表示結(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)題合理地、有目的地注意精度18數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性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、限定適用范圍但也不能忽略實(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ù)雜性19數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§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í)際問(wèn)題，而不在于是否用到了高深的數(shù)學(xué)工具.數(shù)學(xué)建模是一個(gè)過(guò)程.20數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性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è)的魯棒性分析模型的結(jié)果是否對(duì)某一假設(shè)非常依賴⑤不同模型間的對(duì)比分析robustness第一章組合優(yōu)化模型與計(jì)算復(fù)雜性21數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§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á)到比較滿意的程度。22數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性8、模型應(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)系Goback第一章組合優(yōu)化模型與計(jì)算復(fù)雜性23數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性三、組合優(yōu)化模型Example2

某商場(chǎng)根據(jù)客流量統(tǒng)計(jì)得出一周中每天所需要的營(yíng)業(yè)員數(shù)如表：營(yíng)業(yè)員配置問(wèn)題時(shí)間周一周二周三周四周五周六周日所需營(yíng)業(yè)員數(shù)677278768510698

如果規(guī)定每個(gè)營(yíng)業(yè)員每周連續(xù)工作5天，休息2天，求總?cè)藬?shù)最少的營(yíng)業(yè)員排班方案.Solution:

設(shè)xj

為從周j開(kāi)始連續(xù)工作5天的營(yíng)業(yè)員人數(shù)，j=1,…,7(其中

x7

為周日開(kāi)始連續(xù)工作5天的營(yíng)業(yè)員數(shù))，則可行解集是有限集§1組合優(yōu)化模型與算法24數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性Example3

旅行商問(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ù)雜性25數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§1組合優(yōu)化模型與算法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)一次且僅一次的回路.26數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性最優(yōu)旅行商問(wèn)題與最優(yōu)Hamilton回路一樣嗎？

如果不滿足三角不等式，則可通過(guò)求最短路方法，構(gòu)造新圖，使之滿足三角不等式.所以以下僅討論最優(yōu)的

Hamilton

回路.2523Theorem1

如果賦權(quán)圖滿足三角不等式（歐氏距離），則它的最優(yōu)旅行商回路與最優(yōu)Hamilton

回路相同（Hamilton回路存在時(shí)）.第一章組合優(yōu)化模型與計(jì)算復(fù)雜性27數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§1組合優(yōu)化模型與算法TSP

問(wèn)題的數(shù)學(xué)模型（非對(duì)稱的）：v6v4v5v3v2v1Note：條件(1)，(2)表示每個(gè)城市經(jīng)過(guò)一次，但不能保證它可行.

要求局部不構(gòu)成圈，條件(3)就是為了約束這一點(diǎn).28數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性共同特點(diǎn)：可行方案是有限的

——組合優(yōu)化問(wèn)題

Definition1

組合優(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和每個(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、

LPetc；實(shí)例：（一個(gè)問(wèn)題中總包含了若干個(gè)參數(shù)）對(duì)問(wèn)題給定一組參數(shù)所得到的例子.第一章組合優(yōu)化模型與計(jì)算復(fù)雜性29數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性§1組合優(yōu)化模型與算法組合優(yōu)化的數(shù)學(xué)模型：

Minf(x)s.t.g(x)

≥0x∈D其中x為決策變量

f(x)為目標(biāo)函數(shù)g(x)為約束函數(shù)D為決策變量的定義域F={x|x∈D,g(x)≥0}——可行域(有限集)

很多組合優(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)題考慮.30數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性四、關(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ì)的目的.算法思想是數(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ù)雜性31數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性

一個(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)然不能只告訴它一個(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)化模型與算法32數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性如果算法從前一步到后一步的運(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ù)雜性33數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性

對(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.Hilbert23個(gè)問(wèn)題之10——Diophantus方程的可解性.（求出一個(gè)整系數(shù)方程的整數(shù)根）算法的正確性不蘊(yùn)含算法的有效性§1組合優(yōu)化模型與算法34數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性五、算法設(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)題的全部可行解集進(jìn)行比選是否可能.

（計(jì)算時(shí)間復(fù)雜性）第一章組合優(yōu)化模型與計(jì)算復(fù)雜性35數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（二）登山法（也稱貪心法）登山法：從對(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)化模型與算法36數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性TSP的距離矩陣Example

2

用登山法求TSP.v5v4v3v2olution:優(yōu)化準(zhǔn)則：最短距離.

從v1

出發(fā)，有4個(gè)選擇，按優(yōu)化準(zhǔn)則：選v2;……得：v1v2

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ā)，得：

v2v1

v3

v4

v5

v2總距離為：10這是最優(yōu)解（運(yùn)氣好）.

也可以從一個(gè)可行解出發(fā)，交換相鄰兩個(gè)城市位置,優(yōu)化準(zhǔn)則：總距離下降.

v1v2

v5

v3

v4

v1第一章組合優(yōu)化模型與計(jì)算復(fù)雜性37數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（三）分枝與定界法分枝與定界法的基本思想是對(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ì)是窮舉，復(fù)雜性大于窮舉法給出一個(gè)重要思想:設(shè)門檻(稱為隱枚舉)§1組合優(yōu)化模型與算法38數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性設(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).x0BABAx0第一章組合優(yōu)化模型與計(jì)算復(fù)雜性39數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性分枝與定界法為什么能少檢查一些解？B10sB1B210.2s*10sB3B410.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)化模型與算法40數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性△劃分方法的選擇原則是希望分出來(lái)的子問(wèn)題容易被查清，可加快計(jì)算.△選哪個(gè)活問(wèn)題先檢查1、先檢查最大上界（極大化問(wèn)題）的活問(wèn)題優(yōu)點(diǎn)：檢查子問(wèn)題較其他規(guī)則為少；缺點(diǎn)：計(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ù)雜性41數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（四）分治法分治法就是把原問(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)題的尺度.分治法的基本步驟：分治法在每一層遞歸上都有三個(gè)步驟：分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題；合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解.§1組合優(yōu)化模型與算法42數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性

整序問(wèn)題的快速算法是典型的分治策略運(yùn)用.8196753281967532合并合并合并合并186957231689235712356789合并合并合并第一章組合優(yōu)化模型與計(jì)算復(fù)雜性43數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：1、該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決;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)化模型與算法44數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（五）遞歸方法遞歸就是自己調(diào)用自己的過(guò)程.這里的“自己”可以是函數(shù)、過(guò)程、語(yǔ)言結(jié)構(gòu)和解題方法等

.遞歸方法思路:

第一步驟（遞歸步驟）：將規(guī)模較大的原問(wèn)題分解為一個(gè)或多個(gè)規(guī)模更小、但具有類似于原問(wèn)題特性的子問(wèn)題。即較大的問(wèn)題遞歸地用較小的子問(wèn)題來(lái)描述，解原問(wèn)題的方法同樣可用來(lái)解這些子問(wèn)題.

第二步驟：確定一個(gè)或多個(gè)無(wú)須分解、可直接求解的最小子問(wèn)題（稱為遞歸的終止條件）.第一章組合優(yōu)化模型與計(jì)算復(fù)雜性45數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性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)=1FIB(2)=1

為了計(jì)算FIB(n)，要遞歸調(diào)用FIB(n-1)、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)化模型與算法46數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（六）動(dòng)態(tài)規(guī)劃法Example

5100多年前，有位美國(guó)推銷員乘驛站馬車向西旅行，從州A(state,狀態(tài))到州E如圖，需要4個(gè)驛程（stage，階段）。問(wèn)題為求從StateA到StateE走哪條途徑使他最安全？

原問(wèn)題為求從A到E走哪條途徑使保險(xiǎn)單（policy，策略）的總費(fèi)用達(dá)到最小？26AB2B1B3C1C2C3D1D2E243743241543333464第一章組合優(yōu)化模型與計(jì)算復(fù)雜性47數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性26AB2B1B3C1C2C3D1D2E243743241543333464Note:

作出各相繼驛程上最佳決策。不一定產(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)化模型與算法48數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性

如果s1

s2

…

sk

sk+1

…sn是

s1

sn的最短路，則該路上任一點(diǎn)sk

sk+1

…sn

是sk

sn的最短路.結(jié)論：

設(shè)Sk

表示在第k個(gè)驛程上出發(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ù)雜性49數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性26AB2B1B3C1C2C3D1D2E243743241543333464fk(sk)表示從第k個(gè)驛程的出發(fā)州sk

E的最短路的費(fèi)用和，f1(s1)即為所求.若已知f2(B1)、f2(B2)、f2(B3)，則當(dāng)k=4時(shí)，34§1組合優(yōu)化模型與算法50數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性26AB2B1B3C1C2C3D1D2E24374324154333346434當(dāng)k=3時(shí)，

576第一章組合優(yōu)化模型與計(jì)算復(fù)雜性51數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性26AB2B1B3C1C2C3D1D2E24374324154333346434576當(dāng)k=2時(shí)，8811§1組合優(yōu)化模型與算法52數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性26AB2B1B3C1C2C3D1D2E243743241543333464345768811當(dāng)k=1時(shí)，11u2(B3)=C2

u3(C2)=D2

u4(D2)=E最安全道路為A→B3→C2→D2→E，最小費(fèi)用為11.Note

優(yōu)點(diǎn)：①減少計(jì)算量，（共18次加法，11次比較）；②豐富了計(jì)算結(jié)果.第一章組合優(yōu)化模型與計(jì)算復(fù)雜性53數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化的數(shù)量化方法.

動(dòng)態(tài)規(guī)劃的成功之處在于，它可以把一個(gè)n

維決策問(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)而言，余下的諸決策必須構(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)化模型與算法54數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性動(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è)可能狀態(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ù)雜性55數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性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.顯然有skSk如前例S1={A}，S2={B1，B2，B3}，etc.

而s2可取B1，B2，B3.3、決策

(decision)當(dāng)某階段的狀態(tài)確定后，可以作出各種不同的選擇，從而確定下一階段的狀態(tài)，這種選擇稱為決策.§1組合優(yōu)化模型與算法56數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性描述決策的變量稱為決策變量，用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階段開(kāi)始到終止?fàn)顟B(tài)為止的過(guò)程,稱為問(wèn)題的后部子過(guò)程.第一章組合優(yōu)化模型與計(jì)算復(fù)雜性57數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性由每階段的決策按順序排列組成的可行決策函數(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*=p1,n*(s1)={u1*(s1)，u2*(s2),…，un*(sn)}.§1組合優(yōu)化模型與算法58數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性5、狀態(tài)轉(zhuǎn)移方程

(equationofstatetransition)反映前后階段狀態(tài)之間的關(guān)系的方程

記為：sk+1=Tk(sk，uk).體現(xiàn)了無(wú)后效性，正是能將多階段化為單階段決策的理論依據(jù)（前例：sk+1=uk(sk)）6、指標(biāo)函數(shù)和最優(yōu)值函數(shù)(objectivefunctionandoptimalvaluefunction)階段的指標(biāo)函數(shù)是對(duì)應(yīng)某一階段狀態(tài)和從該狀態(tài)出發(fā)的一個(gè)決策的某種效益度量，用vk(sk，uk)表示.過(guò)程指標(biāo)函數(shù)（又稱目標(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ù)雜性59數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性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ù)的形式有：①全過(guò)程和它的任一后部子過(guò)程的指標(biāo)函數(shù)等于各階段指標(biāo)函數(shù)之和，即：

Vk,n(sk,uk,sk+1,uk+1,…,sn,un)=

或§1組合優(yōu)化模型與算法60數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性②全過(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ù)雜性61數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性Note

當(dāng)初始狀態(tài)給定時(shí)，用逆序的方式比較好，當(dāng)終止?fàn)顟B(tài)給定時(shí)，用順序的方式比較好，通常初始狀態(tài)給定的情況居多，所以用逆序的方式比較多.對(duì)第一類指標(biāo)函數(shù)其基本方程為：§1組合優(yōu)化模型與算法62數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性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的距離矩陣63數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性由動(dòng)態(tài)規(guī)劃函數(shù)方程有：為了計(jì)算，必須先計(jì)算而§1組合優(yōu)化模型與算法64數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性計(jì)算順序?yàn)椋旱谝徽陆M合優(yōu)化模型與計(jì)算復(fù)雜性TSP的距離矩陣65數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性TSP的距離矩陣最后計(jì)算：通過(guò)下標(biāo)，不難得最優(yōu)回路為:v1→v3→v4→v2→v1

用動(dòng)態(tài)規(guī)劃算法求TSP,其時(shí)間復(fù)雜性為O(n2n).§1組合優(yōu)化模型與算法66數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（七）探索法探索法是一種對(duì)給定的問(wèn)題能通過(guò)某種途徑（容易得到、比求最優(yōu)解的算法速度快）進(jìn)行探索而找到一個(gè)較好的解（不一定是最優(yōu)解，有時(shí)探索甚至失?。┑乃惴?

設(shè)計(jì)探索法的一種常用方法是列出精確解的所有要求，并把這些要求分成兩類：1、必須滿足的要求；2、允許折衷的要求.

探索算法的設(shè)計(jì)目標(biāo)就是保證第一類要求得到滿足，對(duì)第二類要求要盡量滿足，但并不一定滿足.第一章組合優(yōu)化模型與計(jì)算復(fù)雜性啟發(fā)式算法

67數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（八）倒推法倒推法是從某個(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)題必須有唯一解；2、在問(wèn)題中出現(xiàn)的函數(shù)是單值的，或者說(shuō)對(duì)每一條輸出信息都可以找到唯一的一條輸入信息（又稱1對(duì)1運(yùn)算）.§1組合優(yōu)化模型與算法68數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性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)男」蘩锏谷?L

水；②大罐里裝滿水，小罐里有1L

水，從大罐里倒出2L

水到小罐里，剩下5L；③大罐里有3L水，再?gòu)男」蘩锏谷?L

；④大罐里有4L

水，再?gòu)男」蘩锏谷?L

；⑤大罐里有6L

水，小罐里有2L，從大罐里往小罐里倒入1L水，剩下5L

水.

在這五種情況中，第一和第二兩種情況的可能性大，下面從第二種情況出發(fā)再往前推.

先把大罐裝滿，再用小罐從大罐里量出兩次共6L

水，使之剩下1L

水，把它倒入小罐，然后把大罐再裝滿.這就得到了上述第二種情況.這種情況發(fā)生后，從大罐往小罐到2L

水，剩下5L

水，問(wèn)題得到了解決.第一章組合優(yōu)化模型與計(jì)算復(fù)雜性69數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（九）回溯法回溯法是一種滿足一定約束條件的窮舉式搜索法，它的搜索方式與對(duì)樹(shù)的深度優(yōu)先搜索方式相似，但由于規(guī)定了問(wèn)題的解必須滿足一些約束條件，因此需要搜索的空間大大減少.

如果問(wèn)題的解能表示為一個(gè)n

元組(x1,x2,…,xn)

則可采用回溯法求解.回溯法求解的約束條件一般分為兩類：1、顯約束，每個(gè)xi

的取值范圍；2、隱約束，滿足判定函數(shù)的關(guān)于解空間上的多元式.§1組合優(yōu)化模型與算法70數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性Example

8

設(shè)有一4×4的棋盤（即每行每列都有4個(gè)正方格的棋盤），用4個(gè)棋子布到格子上，要求滿足一下兩個(gè)條件：1、任意兩個(gè)棋子不在同一行和同一列上；2、任意兩個(gè)棋子不在一對(duì)角線上.試問(wèn)有多少種的布局？Solution:

如果采用窮舉式搜索，先不考慮1、2兩個(gè)條件，則布到每一行的棋子有4個(gè)選擇，故共有

44=256種方案.設(shè)xi

表示放在第i行上的棋子的列數(shù)，這是顯約束

顯然沒(méi)有必要！第一章組合優(yōu)化模型與計(jì)算復(fù)雜性71數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性隱約束有：不同列不在一對(duì)角線上搜索過(guò)程如下：××××××××××××××××

這種一旦發(fā)現(xiàn)前面已是“此路不通”，立即回頭，改換路徑，而不是一條道走到底的策略，就是回溯法的基本思想.向前走，碰壁回頭§1組合優(yōu)化模型與算法72數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性（十）模擬法

在實(shí)際科研和生產(chǎn)中有許多大系統(tǒng)，要構(gòu)造大系統(tǒng)的模型、對(duì)它們分析和求解都是相當(dāng)困難的.變量之間的關(guān)系難以確定，隨機(jī)變量的分布不得而知，甚至影響因素就找不全.

利用計(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)題的方法，是一種建模方法.73數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性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)及行為，這些都是在實(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)用中，常常是幾種方法配合使用，以提高算法的效率.Goback§1組合優(yōu)化模型與算法74數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性

在廣泛的意義下，執(zhí)行算法的效率是用執(zhí)行算法所用的全部計(jì)算資源的多少來(lái)衡量(時(shí)間、空間),但通常用時(shí)間作為衡量標(biāo)準(zhǔn)，這就是計(jì)算(時(shí)間)復(fù)雜性問(wèn)題.一、如何計(jì)算時(shí)間

1°與實(shí)例的輸入規(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)題75數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性

2°與實(shí)例的參數(shù)有關(guān)，如LP

問(wèn)題：

maxz=c’xs.t.Ax≤bx≥0,c≤0,b≥0

算法的時(shí)間復(fù)雜性是關(guān)于實(shí)例輸入長(zhǎng)度的函數(shù)，用來(lái)表示算法的時(shí)間需求.對(duì)于每一個(gè)可能的輸入長(zhǎng)度，它是該算法解此輸入長(zhǎng)度的最壞可能的實(shí)例所需的時(shí)間（基本運(yùn)算步驟）.相關(guān)因素:Definition1§2計(jì)算復(fù)雜性問(wèn)題76數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性研究計(jì)算復(fù)雜性問(wèn)題主要是針對(duì)n很大的情形1°9n2與2n2——O(n2)

2°f(n)=12n4-8n3+5n2+2n-80f(n)=O(n4)

當(dāng)n無(wú)限增大時(shí)，Lnn,nα(α>0),an

（a>1）趨向于無(wú)窮大的速度如何？Note：?jiǎn)枺汉瘮?shù)規(guī)模n

的近似值101001000n101001000nlogn336649966n31031061092n10241.27×10301.05×10301n!101584×102567第一章組合優(yōu)化模型與計(jì)算復(fù)雜性77數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性復(fù)雜性分析的一個(gè)研究方向：對(duì)算法進(jìn)行評(píng)價(jià)

給定n個(gè)整數(shù)x1，x2，……xn，要求將他們從小到大重新排列

取出x1，x2，…xn中的最小者（需比較n-1次）令其為b1（需n次賦值），從x1，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)題78數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性

先將兩個(gè)單調(diào)不減的數(shù)列{u1，u2…um}與{v1，v2…vm}合并為一個(gè)單調(diào)不減的數(shù)列{w1，w2…w2m}方法為u1與v1比較,若u1≥

v1，w1:=v1.再對(duì)u1與v2進(jìn)行比較，依次對(duì)w2，w3…w2m賦值，計(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ù)雜性79數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性將2p+1個(gè)數(shù)分成2p個(gè)單調(diào)不減的2元組,計(jì)算量為O(2p)O(2p)=2p-1O(2)計(jì)算量為O（2p）綜上，算法總工作量為：(p+1)*O(2p)=O(nlogn)81967532(81)(96)(75)(32)18695723(1869)(5723)1689235712356789將2元組兩兩合并成2p-1個(gè)單調(diào)不減的4元組，計(jì)算量為O(2p)依次類推，最后將兩個(gè)2p元組合并成為一個(gè)單調(diào)不減的2p+1元組2p+1=n§2計(jì)算復(fù)雜性問(wèn)題80數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性設(shè)機(jī)器速度100萬(wàn)次/秒快速算法O(nlogn)……需20秒設(shè)機(jī)器速度為M次/秒

問(wèn)題D

算法A……計(jì)算復(fù)雜性

n2算法B……計(jì)算復(fù)雜性2n給定1秒的機(jī)器時(shí)間

算法A………可解規(guī)模算法B………可解規(guī)模n=100萬(wàn)比較交換法O(n2)……需5.8天M=n2第一章組合優(yōu)化模型與計(jì)算復(fù)雜性81數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性設(shè)機(jī)器速度100萬(wàn)次/秒給定1秒的機(jī)器時(shí)間

算法A…………可解規(guī)模n=算法B…………可解規(guī)模n=給定1秒的機(jī)器時(shí)間

算法A…………可解規(guī)模n=1000算法B…………可解規(guī)模n=20設(shè)機(jī)器速度提高100倍為1億次/秒給定1秒的機(jī)器時(shí)間算法A……可解規(guī)模n=1000×10算法B……可解規(guī)模

n=20+log2100Log2100<7提供好的算法比提高機(jī)器效率更重要§2計(jì)算復(fù)雜性問(wèn)題82數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性Definition2

設(shè)A是解某一問(wèn)題D的算法，對(duì)D

的任一規(guī)模為n

的實(shí)例，可在n的多項(xiàng)式時(shí)間內(nèi)求解（即計(jì)算復(fù)雜性為O（nα））,則稱算法A

為一個(gè)解問(wèn)題D

的多項(xiàng)式時(shí)間算法.（簡(jiǎn)稱多項(xiàng)式算法）

不能這樣限制時(shí)間復(fù)雜性函數(shù)的算法稱為指數(shù)時(shí)間算法.

若存在一個(gè)常數(shù)

C，使得對(duì)所有n≥1,都有︱f(n)︱≤C︱g(n)︱,則稱函數(shù)f(n)是O(g(n)).多項(xiàng)式時(shí)間算法:指數(shù)時(shí)間算法:O(nlogn)、O(n2.8)、O(n2)O(n!)、O(3n)第一章組合優(yōu)化模型與計(jì)算復(fù)雜性83數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性多項(xiàng)式時(shí)間算法好算法有效算法指數(shù)時(shí)間算法壞算法惡劣算法Note:A

算法的計(jì)算復(fù)雜性為O(n80)，A

是好算法嗎？與O(2n)比較問(wèn)題D是否有多項(xiàng)式時(shí)間算法是問(wèn)題的固有性質(zhì).Goback偽多項(xiàng)式時(shí)間算法：它的時(shí)間復(fù)雜性不超過(guò)關(guān)于實(shí)例輸入長(zhǎng)度和實(shí)例中最大數(shù)的某個(gè)二元多項(xiàng)式.如：O(mn2).§2計(jì)算復(fù)雜性問(wèn)題84數(shù)學(xué)建模-第一章組合優(yōu)化模型與計(jì)算復(fù)雜性三、P類、NP類、NP—完全問(wèn)題復(fù)雜性分析的另一個(gè)研究方向：對(duì)組合優(yōu)化問(wèn)題歸類

對(duì)組合優(yōu)化問(wèn)題π，如果存在一個(gè)求解該問(wèn)題的多項(xiàng)式時(shí)間算法，則稱π是多項(xiàng)式時(shí)間可解問(wèn)題.所有多項(xiàng)式時(shí)間可解問(wèn)題構(gòu)成的集合，稱為

P類問(wèn)題記為P.π∈PP類問(wèn)題:（Polynomial）第一章組合優(yōu)化模型與計(jì)算復(fù)雜性85數(shù)學(xué)建模-第一章組合優(yōu)化