運籌學(xué)基礎(chǔ) 課件 宋志華 第1、2章 運籌學(xué)概述、樸素優(yōu)化范式

第1章運籌學(xué)概述1.1

運籌學(xué)的起源1.2運籌學(xué)的定義1.3運籌學(xué)的模型1.4運籌學(xué)的優(yōu)化范式1.5運籌學(xué)應(yīng)用的過程

1.1

運籌學(xué)的起源

運籌學(xué)起源于軍事問題的研究。第二次世界大戰(zhàn)初期,英國人為了將最新的雷達(dá)技術(shù)整合進(jìn)英國空軍戰(zhàn)術(shù),開始了相關(guān)研究,并稱之為OperationalResearch。最初,OperationalResearch的主要工作就是收集經(jīng)驗數(shù)據(jù)并進(jìn)行基礎(chǔ)的統(tǒng)計分析,也有一些工作應(yīng)用了較為復(fù)雜的數(shù)學(xué)方法,如搜索理論。

1941年,OperationalResearch這個詞被泛指所有為了輔助

軍官籌劃作戰(zhàn)策略和作戰(zhàn)行動而進(jìn)行的研究,目標(biāo)是通過量化分析技術(shù)最有效地利用有限的軍事資源。第二次世界大戰(zhàn)之后,OperationalResearch變成一種專業(yè),并且更加關(guān)注和聚焦于復(fù)雜的數(shù)學(xué)方法。

早在1936年,英國空軍在東海岸(位于Felixstowe,Suffolk附近)建立了Bawdsey研究站,在這里對空軍和陸軍的雷達(dá)開展實驗活動。

1937年,Bawdsey研究站的第一部實驗雷達(dá)部署完畢。

1938年,Bawdsey研究站又增加部署了四部雷達(dá),并進(jìn)行了第二次實驗。

1939年,Bawdsey研究站進(jìn)行了第三次實驗,有33000人、1300架飛機、110套高射機槍、700套探照燈和100個阻塞氣球參與了實驗過程。第三次實驗的結(jié)果表明,作戰(zhàn)應(yīng)用研究團(tuán)隊的有效工作使防空預(yù)警和控制系統(tǒng)在作戰(zhàn)效能方面有巨大提升。

1940年5月14日,德國軍隊在法國快速推進(jìn),法國此時的兵力消耗速度為每兩天三個中隊。法國請求英國再增加10個中隊力量的支援(每個中隊12架飛機,總共120架飛機),而英國首相很可能因為聯(lián)盟關(guān)系而向法國增援。

1941年,OperationalResearchSection(ORS)在英國海岸司令部成立,并進(jìn)行了許多著名的運籌學(xué)工作。當(dāng)時海岸司令部的主要工作是利用飛機發(fā)現(xiàn)并攻擊德國的U型潛艇(當(dāng)時U型潛艇經(jīng)常浮出水面,因為只有浮出水面才能給電池充電、排出潛艇上的煙、給氣罐充氣,并且在水面上U型潛艇航行得更快,也可以降低被聲吶發(fā)現(xiàn)的概率)。

從1942年開始,Blackett帶領(lǐng)的運籌學(xué)團(tuán)隊為海軍海岸司令部作戰(zhàn)研究處提供了許多有益的分析。在研究深水炸彈的觸發(fā)深度問題時,Blackett團(tuán)隊的研究指出,如果將空投深水炸彈的觸發(fā)深度從100英尺改為25英尺,那么殺傷率就會上升。

運籌學(xué)在它起源于英國的幾年后就傳到了美國。

第二次世界大戰(zhàn)剛結(jié)束時,許多科學(xué)家認(rèn)識到他們用于解決軍事問題的原則同樣適用于民用部門,于是運籌學(xué)在民用領(lǐng)域迅速發(fā)展起來,同時運籌學(xué)在軍事領(lǐng)域的發(fā)展也在持

續(xù)。

直至今天,美國空軍的軍事運籌組織還存在并發(fā)揮作用。

1.2運籌學(xué)的定義

1951年,莫爾斯和金博爾出版的《運籌學(xué)方法》一書中將運籌學(xué)定義為:運籌學(xué)是在實行管理的領(lǐng)域,運用數(shù)學(xué)方法,對需要進(jìn)行管理的問題統(tǒng)籌規(guī)劃,做出決策的一門應(yīng)用科學(xué)。美國運籌學(xué)會給出的定義為:運籌學(xué)關(guān)注的是,在需要考慮稀缺資源分配的條件下,研究最優(yōu)設(shè)計的決策問題,研究人機系統(tǒng)的運用問題。

英國運籌學(xué)會給出的定義為:運籌學(xué)應(yīng)用科學(xué)的方法解決工業(yè)、商業(yè)、政府和國防等領(lǐng)域大系統(tǒng)的指導(dǎo)與管理方面的問題,指導(dǎo)和管理的對象包括人員、機器、材料、資金等。

在顧基昌等人提出的物理事理人理方法論(簡稱WSR方法論)中,運籌學(xué)被歸屬為研究事理的科學(xué)。在WSR方法論中,“物理”指涉及物質(zhì)運動的機理,既包括狹義的物理,也包括化學(xué)、生物、地理、天文等,通常要用自然科學(xué)知識回答“物”是什么。

“事理”指做事的道理,主要解決如何去安排所有的設(shè)備、材料、人員等,通常要回答“怎樣去做”的問題,也就是需要決策。“人理”指做人的道理,通常要用人文和社會科學(xué)的知識回答“應(yīng)當(dāng)怎樣做”的問題。人理的作用可以反映在世界觀、文化、信仰、宗教和情感等方面,特別表現(xiàn)在人們處理一些“事”和“物”中的利益觀和價值觀上。

與軍事相關(guān)的運籌學(xué)稱作軍事運籌學(xué)。張最良給出的軍事運籌學(xué)的定義是:應(yīng)用數(shù)學(xué)和計算機等科學(xué)技術(shù)方法研究各類軍事活動,為決策優(yōu)化提供理論和方法的一門軍事學(xué)科。OODA環(huán)模型是描述軍事活動的常用模型,它將交戰(zhàn)雙方的交戰(zhàn)過程描述為由觀察、判斷、決策、行動四個基本活動構(gòu)成的環(huán),如圖1-1所示。

圖1-1-OODA環(huán)模型

維基百科上給出了運籌學(xué)最為簡潔的定義:運籌學(xué)(OperationsResearch,OR)研究怎樣使用高級的分析技術(shù)做更好的決策。所謂的“高級分析技術(shù)”是一個相對的概念,是相對問題本身來講的,取決于是否更適合實際問題以及能否做出更好的決策,并不是復(fù)雜程度的代名詞。因此,分析技術(shù)本身沒有普適性,一切要視實際問題而定。

1.3運籌學(xué)的模型

1.3.1-線性規(guī)劃模型數(shù)學(xué)規(guī)劃模型包含決策變量、目標(biāo)函數(shù)、約束條件等三類必要元素。決策變量是決策要素的變量化定義;利用決策變量表達(dá)問題目標(biāo)的函數(shù)就是目標(biāo)函數(shù);利用決策變量表達(dá)問題約束的等式或者不等式就是約束條件。

1.3.2網(wǎng)絡(luò)模型

網(wǎng)絡(luò)模型包含點和邊兩類必要元素。點代表問題中的對象,邊代表問題中對象之間的關(guān)系。以網(wǎng)絡(luò)模型為基礎(chǔ),可以研究很多網(wǎng)路優(yōu)化問題,如最小支撐樹問題、最短路問題、最大流問題、最小費用流問題等。1956年福特和?？诉d提出了網(wǎng)絡(luò)最大流問題的標(biāo)號法,建立了網(wǎng)絡(luò)流理論。

1.3.3動態(tài)規(guī)劃模型

動態(tài)規(guī)劃是一種算法設(shè)計技術(shù),也是一種解決優(yōu)化問題的模型及算法構(gòu)造方法。它以遞歸的方式將一個復(fù)雜的問題分解成一系列簡單的子問題,并通過子問題序列化的求解得

到問題的最優(yōu)方案。動態(tài)規(guī)劃模型包含狀態(tài)、狀態(tài)轉(zhuǎn)移等兩類基本要素,可以看作是一種具有階段性的特殊的網(wǎng)絡(luò)模型。

1.3.4生滅過程模型

生滅過程模型的基本要素包括狀態(tài)和狀態(tài)轉(zhuǎn)移,狀態(tài)代表排隊系統(tǒng)中的顧客的數(shù)量,狀態(tài)轉(zhuǎn)移代表排隊系統(tǒng)中顧客數(shù)量的變化,也就是系統(tǒng)狀態(tài)的變化。生滅過程模型以計算

系統(tǒng)處于各個狀態(tài)的概率為中介,結(jié)合排隊系統(tǒng)的Little公式,可以得到排隊系統(tǒng)的平均隊長、期望等待時間等各項參數(shù),進(jìn)而為排隊系統(tǒng)的優(yōu)化提供支持。

1.3.5神經(jīng)網(wǎng)絡(luò)模型

神經(jīng)網(wǎng)絡(luò)模型是一種基于網(wǎng)絡(luò)模型的計算模型,計算的數(shù)據(jù)從輸入層開始往后流動,主要通過模擬生物的神經(jīng)網(wǎng)絡(luò)進(jìn)行模式識別,相當(dāng)于OODA環(huán)中的“判斷”。

。傳統(tǒng)上,優(yōu)化決策的步驟可分為問題定義、建立模型、設(shè)計算法、求解并檢驗驗證等環(huán)節(jié),人工參與是全程和深入的,對人的建模求解能力和技術(shù)要求高。基于人工智能的優(yōu)化決策技術(shù),讓機器可以在有監(jiān)督或者無監(jiān)督的情況下學(xué)習(xí),無須人類的參與,甚至無須人類經(jīng)驗的加入,就能做出優(yōu)化的決策。

1.3.6啟發(fā)式模型

啟發(fā)式模型將問題的求解方案編碼為生物基因、粒子、鳥類等對象,并模擬這些對象的進(jìn)化優(yōu)化過程進(jìn)行進(jìn)化。1975年,Holland教授借鑒生物界的進(jìn)化規(guī)律提出了遺傳算法,

從而開啟了進(jìn)化計算的時代。

1.3.7仿真模型

基于解析分析的方法和基于仿真的方法,是兩種不同的研究客觀世界的方法?；诮馕龇治龅姆椒軌蜓杆僮プ】陀^問題的主要矛盾和關(guān)鍵的變量關(guān)系,因此適合解決條件比較理想化、變量個數(shù)和關(guān)系不是太過復(fù)雜的問題。而運籌學(xué)要面對大量復(fù)雜的現(xiàn)實問題,借助基于仿真的方法,是必由之路。仿真本質(zhì)上是計算,是對客觀問題數(shù)量關(guān)系在時間軸上演進(jìn)的模擬,它可以將不確定性、結(jié)構(gòu)復(fù)雜、計算量巨大等困難交給計算機,使人員的精力集中到仿真模型的建立和仿真數(shù)據(jù)的分析上。

仿真模型非常強大,并且它有一個非?？扇〉奶匦?將其用于非常復(fù)雜的系統(tǒng)建模時,不需要做太多的簡化假設(shè),也不需要犧牲過多細(xì)節(jié)。然而,使用仿真模型時必須非常小心,避免誤用仿真。首先,在使用模型之前,必須對其進(jìn)行適當(dāng)?shù)尿炞C。驗證對于任何模型來說都是必要的,對于仿真尤為重要。其次,分析人員必須熟悉如何正確使用仿真模型,包括復(fù)制、運行時間等。再次,為了有意義地分析仿真輸出,分析人員必須熟悉各種統(tǒng)計技術(shù)。最后,在計算機上構(gòu)建復(fù)雜的仿真模型是一項具有挑戰(zhàn)性和相對耗時的任務(wù),分析人員必須具有耐心。這里強調(diào)這些問題的原因是,現(xiàn)代仿真模型種類繁多,其真正的價值在于它能夠洞察非常復(fù)雜的問題。

值得指出的一點是,仿真只是利用計算機的仿真模型進(jìn)行了大量時間軸上的計算,它不能提供最佳策略的指示。從某種意義上說,這是一個反復(fù)實驗的過程,因為我們用各種似乎有意義的策略進(jìn)行實驗,并查看仿真模型提供的客觀結(jié)果,以評估每種策略的優(yōu)點。

1.4運籌學(xué)的優(yōu)化范式

自運籌學(xué)誕生以來,運籌學(xué)所利用的模型和分析技術(shù)眾多。在面對一個新問題或者尚未很好解決的問題時,需要選擇相應(yīng)的模型和分析技術(shù)。通過對運籌學(xué)解決問題方法的聚類分析,可以得到運籌學(xué)的五大優(yōu)化范式,即樸素優(yōu)化范式、機械優(yōu)化范式、仿真優(yōu)化范式、智能優(yōu)化范式和數(shù)據(jù)驅(qū)動優(yōu)化范式(見圖1-2)。

圖1-2運籌學(xué)的五大優(yōu)化范式

1.4.1-樸素優(yōu)化范式

樸素優(yōu)化范式是源于智能體直覺本能的規(guī)則式優(yōu)化范式,是出現(xiàn)較早的一種優(yōu)化決策范式,目前,對許多問題仍然具有生命力,同時,也會作為其他優(yōu)化決策范式的子算法或者啟發(fā)思路。貪婪算法、窮舉法、深度優(yōu)先搜索、廣度優(yōu)先搜索、生成測試范例等都可劃分到此類。這類方法不需要復(fù)雜的數(shù)學(xué)推導(dǎo),基本是一種規(guī)則式的算法,可以單獨使用,也可以作為一種規(guī)則融入其他更復(fù)雜的算法中去。這些樸素優(yōu)化的思想,為運籌學(xué)的許多高級算法持續(xù)提供支撐。

1.4.2機械優(yōu)化范式

機械優(yōu)化范式是可以程序化和結(jié)果重現(xiàn)的一些算法,比樸素優(yōu)化范式更加需要智慧和直覺之上的智能。例如,單純形法、內(nèi)點法、表上作業(yè)法、動態(tài)規(guī)劃、匈牙利算法、標(biāo)號法、層次分析法、非線性規(guī)劃中的梯度法等均屬于此類。

1.4.3仿真優(yōu)化范式

仿真優(yōu)化范式是基于計算機仿真技術(shù)和平臺的優(yōu)化方法,可充分利用仿真對復(fù)雜系統(tǒng)的強大描述和承載能力,為優(yōu)化提供動態(tài)、復(fù)雜結(jié)構(gòu)的數(shù)據(jù)輸入能力,并能夠?qū)﹄S機性提供天然支持。

1.4.4智能優(yōu)化范式

智能優(yōu)化范式通過智能算法借鑒了智能體的進(jìn)化優(yōu)化過程,比較容易理解,能夠解決的問題也是廣譜的,但是針對具體的問題需要更多的專業(yè)知識,才能對算法的編碼、解的進(jìn)化、參數(shù)的調(diào)整等技術(shù)細(xì)節(jié)進(jìn)行良好的控制和優(yōu)化。

1.4.5數(shù)據(jù)驅(qū)動優(yōu)化范式

數(shù)據(jù)驅(qū)動優(yōu)化范式是優(yōu)化決策與大數(shù)據(jù)技術(shù)相結(jié)合的產(chǎn)物,它將數(shù)據(jù)作為驅(qū)動優(yōu)化決策的直接動力,解決了傳統(tǒng)優(yōu)化決策領(lǐng)域理論和實踐脫節(jié)的問題。傳統(tǒng)的優(yōu)化決策方法都

是先對真實系統(tǒng)進(jìn)行選擇性的抽象,建立實際上失真的模型,然后對模型進(jìn)行優(yōu)化,將對模型進(jìn)行優(yōu)化的結(jié)果作為對真實系統(tǒng)優(yōu)化決策的替代物。然而數(shù)據(jù)驅(qū)動優(yōu)化范式的模型本

身始終與真實系統(tǒng)保持聯(lián)系,真實系統(tǒng)的數(shù)據(jù)源源不斷地輸入模型中,使模型的失真度達(dá)到最小,從而保證了優(yōu)化決策的準(zhǔn)確度。

1.5運籌學(xué)應(yīng)用的過程

運籌學(xué)不僅僅是數(shù)學(xué)工具的集合。運籌學(xué)也不僅僅是模型方法的集合,而更應(yīng)該是一個完整的、系統(tǒng)的過程。運籌學(xué)研究的最終目的是對所分析的問題實施解決方案,因此保持問題驅(qū)動的焦點是至關(guān)重要的。運籌學(xué)實踐者經(jīng)常要面對的是對系統(tǒng)化解決方案的需求,要面對的是對問題全系統(tǒng)全壽命的考驗?，F(xiàn)實中的太多病態(tài)定義、非標(biāo)準(zhǔn)化結(jié)構(gòu)的問題,往往需要運籌學(xué)實踐者自己提煉和解決。

如圖1-3所示,運籌學(xué)的應(yīng)用過程包括以下七個步驟:定位、問題定義、數(shù)據(jù)收集、模型構(gòu)建、模型求解、驗證與分析、實施與監(jiān)控。將這些步驟結(jié)合在一起構(gòu)成了一種持續(xù)反饋的機制。

圖1-3運籌學(xué)的應(yīng)用過程

例1-1-考慮一個高度簡化的軍事作戰(zhàn)計劃問題。藍(lán)軍試圖入侵由紅軍防御的領(lǐng)地。紅軍有三條防線和200個正規(guī)戰(zhàn)斗單位,并且還能抽調(diào)出200個預(yù)備單位。藍(lán)軍計劃進(jìn)攻兩條前線(南線和北線);紅軍設(shè)置三條東西防線(Ⅰ、Ⅱ、Ⅲ),防線Ⅰ和防線Ⅱ各自要至少阻止藍(lán)軍進(jìn)攻4天以上,并盡可能延長總的戰(zhàn)斗持續(xù)時間。藍(lán)軍的前進(jìn)時間由下列經(jīng)驗公式估計得到:

其中,系數(shù)a和b如表1-1所示。

紅軍的預(yù)備單位能夠且只能用在防線Ⅱ上。藍(lán)軍分配到三條防線的單位數(shù)由表1-2給出。

紅軍應(yīng)如何在北線/南線和三條防線上部署他的軍隊?

1.5.1-定位

“定位”的主要目標(biāo)是組成一個小組,并確保其所有成員對有關(guān)問題有一個清楚的了解。通常,團(tuán)隊由一個領(lǐng)導(dǎo)者和來自不同職能領(lǐng)域或部門的成員組成。

1.5.2問題定義

“問題定義”需要對問題的范圍和期望的結(jié)果有一個明確定義。這一階段不應(yīng)與前一階段相混淆,因為它更加集中和面向目標(biāo)。

對問題的清晰定義包含三個主要部分。第一個是明確目標(biāo)的陳述。雖然完整的系統(tǒng)級解決方案會更受青睞,但當(dāng)系統(tǒng)非常大或復(fù)雜時,這通常是不現(xiàn)實的,在許多情況下,必須將重點放在系統(tǒng)中可以有效隔離和分析的部分。

第二個是對影響目標(biāo)的因素的規(guī)范。

第三個也是最后一個組成部分是對行動過程的約束的規(guī)范,即為決策者可能采取的具體行動設(shè)定界限。

1.5.3數(shù)據(jù)收集

“數(shù)據(jù)收集”的目的是將第二階段定義的問題轉(zhuǎn)化為模型進(jìn)行客觀分析。數(shù)據(jù)通常有兩個來源———觀察和預(yù)測。一些數(shù)據(jù)可以通過“觀察”得到,即通過觀察系統(tǒng)的運行實際收集數(shù)據(jù)。

1.5.4模型構(gòu)建

模型是對現(xiàn)實世界的選擇性抽象,建模是捕獲系統(tǒng)或流程的選定特征。分析一個簡化的模型通常比分析原始系統(tǒng)要容易得多,并且只要模型合理、準(zhǔn)確,由得出的結(jié)論就可以有效地推回原始系統(tǒng)。

給出的模型的正式定義中,關(guān)鍵字是“選擇性”。有了清晰的問題定義,就可以更好地確定系統(tǒng)的關(guān)鍵方面。這些方面必須由模型來表示。最終的目的是得到一個模型,該模型捕獲了系統(tǒng)的所有關(guān)鍵元素,同時又足夠簡單,可以進(jìn)行分析。

例如,在建立例1-1的數(shù)學(xué)規(guī)劃模型時,首先要定義決策變量xij和yij(i=1,2;j=1,2,3),xij表示各個防線上的正規(guī)兵力部署數(shù)量,yij表示部署在防線Ⅱ上的預(yù)備兵力數(shù)量。下面我們就可以依據(jù)經(jīng)驗公式計算各個防線上的戰(zhàn)斗持續(xù)時間,即

如果我們的目標(biāo)是使六個防線上的持續(xù)時間之和達(dá)到最大,則目標(biāo)函數(shù)可以表示為以下形式:

同時,兵力的分配要受到以下約束。

正規(guī)戰(zhàn)斗單位總數(shù)為200個,因此有

預(yù)備戰(zhàn)斗單位有200個,能夠且只能用在防線Ⅱ上,故有

防線Ⅰ和防線Ⅱ各自要至少阻止紅軍進(jìn)攻4天以上,故有

這個模型中顯然沒有考慮藍(lán)軍在突破一個防線之后,剩余的兵力是否會加入另外一個尚未突破防線的戰(zhàn)斗中。

1.5.5模型求解

在應(yīng)用特定的技術(shù)時,如果資源可用性和時間都不是問題,人們當(dāng)然會尋找最佳解決方案。然而,在許多情況下,及時性是至關(guān)重要的,通常更重要的是快速獲得令人滿意的解決方案,而不是花費大量的精力來確定最佳的解決方案,特別是在這樣做的邊際收益很小的情況下。

1.5.6驗證與分析

獲得解決方案之后,需要先驗證解決方案本身是否有意義。通常情況下產(chǎn)生問題的原因是模型不準(zhǔn)確或漏掉了影響因素,有時需要對模型進(jìn)行求解來發(fā)現(xiàn)其中的不準(zhǔn)確性。在

這個階段可能出現(xiàn)的一個典型錯誤是,模型忽略了一些重要的約束,然后分析人員必須返回修改模型并重新求解它。這個循環(huán)會一直持續(xù)下去,直到確定結(jié)果是合理的。

1.5.7實施與監(jiān)控

實施與監(jiān)控是一個將決策轉(zhuǎn)化為行動并不斷評估和反饋的過程。實施與監(jiān)控均需要團(tuán)隊來完成。實施團(tuán)隊通常包括原運籌團(tuán)隊的一些成員,負(fù)責(zé)制訂作業(yè)流程或手冊,并制訂實施計劃的時間表。監(jiān)控團(tuán)隊一般要包括操作人員。從運籌的角度來看,監(jiān)控團(tuán)隊的人員應(yīng)認(rèn)識到,只有在操作環(huán)境不變、研究假設(shè)保持有效的情況下,實施的結(jié)果才是有效的。因此,當(dāng)制訂計劃的基礎(chǔ)發(fā)生根本變化時,人們必須重新考慮自己的戰(zhàn)略。第2章樸素優(yōu)化范式2.1生成測試范例2.2

枚舉法2.3深度優(yōu)先搜索2.4廣度優(yōu)先搜索2.5貪婪算法2.6啟發(fā)式算法2.7拓展應(yīng)用:玻璃球硬度測試實驗設(shè)計問題

2.1生成測試范例

在最直觀的決策模式中,我們會構(gòu)造一個解決方案并檢測是否滿足約束條件,如果不滿足約束條件,就再構(gòu)造一個解決方案,直到找到一個滿足約束條件的解決方案為止,這樣的為問題找到解決方案的決策思路稱為生成測試范例。這適合于尋找可行解的問題,可行解之間無優(yōu)劣之分。

例2-2(八皇后問題)在國際象棋8×8的棋盤上,要擺放8個皇后,但是要保證沒有任意兩個皇后可以相互攻擊,也即要求沒有任意兩個皇后處在相同的行、列或?qū)蔷€上。如圖2-1所示,如果深色方格代表為皇后選擇的位置,則圖2-1(a)所示的為一個可行的方案,而圖2-1(b)所示的是不可行的方案,因為不符合任意兩個皇后都不能處在同一對角線上的約束。

圖2-1八皇后問題的生成測試范例

對于八皇后問題來講,基本的解決范式就是生成測試范例,也就是生成一個解決方案,判斷是否可行,如果可行,算法結(jié)束,否則再生成另外一個解決方案。不同的解決方案之間并無優(yōu)劣之分,問題的目標(biāo)只是要找到一個滿足條件的解決方案。

2.2

枚舉法

枚舉法就是檢測決策對應(yīng)的每一種可能的解決方案,并比較它們的優(yōu)劣,從中選擇出最好的方案。枚舉法的好處是能夠確切無誤地找到問題的最優(yōu)解,并且實現(xiàn)起來簡單易行,但是顯然不適合連續(xù)變量優(yōu)化問題以及可能解決方案數(shù)量過于龐大的問題。

例2-3(人民幣組合問題)假設(shè)我們有8種不同面值的人民幣{1,5,10,50,100,200,500,1000},單位為分,用這些面值的人民幣組合構(gòu)成一個給定的數(shù)值n。例如,n=3000,問總共有多少種可能的組合方式?

如果假設(shè)8種人民幣的數(shù)量分別為xi(i=1,…,8),則可以確定各個變量的取值范圍如表2-1所示。

使用枚舉的方法需要搜索的狀態(tài)空間中包含的解的數(shù)量為各個維度狀態(tài)數(shù)量的乘積,也即4.5991e+14,這樣的狀態(tài)空間規(guī)模使用一般的計算機尚可在忍受的時間范圍內(nèi)完成。

例如,在處理器為Intel(R)Core(TM)i77500UCPU@2.70GHz,內(nèi)存為8GB的聯(lián)想筆記本電腦上,使用Matlab計算n=30000的人民幣組合問題,花費時間為2285.5秒,代碼如下:

然而對于很多實際問題的搜索狀態(tài)空間,枚舉法多數(shù)是不可忍受的。當(dāng)然,枚舉法在很多情況下計算時間的不可忍受也是可被利用的,否則,密碼可被暴力破解,網(wǎng)上銀行和保密通信就有麻煩了。

例2-4(n皇后問題)針對例2-2的八皇后問題,將其一般化后就是n皇后問題,在一個n×n的棋盤上擺放n個皇后保證相互沒有攻擊可能。請問n皇后問題有多少種可行的方案?

對于n皇后問題,需要檢查的組合數(shù)量為n!。對于八皇后問題,可以使用枚舉的辦法統(tǒng)計可行方案的數(shù)量。但是對于數(shù)量越大的n皇后問題,枚舉法就越不可行,因為需要枚舉的方案的數(shù)量呈指數(shù)級增長。例如,n=20,需要檢查的組合數(shù)量為20!=2.433×1018,使用枚舉法來檢查已經(jīng)不現(xiàn)實了。

2.3深度優(yōu)先搜索

深度優(yōu)先搜索(Deep-FirstSearch,DFS)是一種基于圖數(shù)據(jù)結(jié)構(gòu)的枚舉法?？梢赃@樣理解,圖中的節(jié)點都有一定的層次關(guān)系,所有的從同一個點a出發(fā)通過弧能夠直接一步到達(dá)的點bi∈B是同級的,這是廣度上的衡量,而a稱為bi的上級,bi稱作a的下級,如圖2-2所示。所謂深度優(yōu)先,就是當(dāng)前點往下走的時候,優(yōu)先選擇第一個未走過的下級節(jié)點,不優(yōu)先到達(dá)一個未走過的同級節(jié)點。

圖2-2-節(jié)點的層次結(jié)構(gòu)及深度和廣度衡量

例2-5(拼圖問題)對于一個2×2拼圖問題來講,給定初始排列和目標(biāo)排列如圖23所示,要想從初始排列達(dá)到目標(biāo)排列,請問要進(jìn)行怎樣的操作才可以達(dá)到目的?

為了描述問題更加方便,將拼圖的一個排列稱為拼圖的一個狀態(tài),對拼圖的操作抽象為四種操作:空格上移、空格下移、空格右移、空格左移。

圖2-3拼圖問題的初始排列和目標(biāo)排列

步驟1:初始狀態(tài)為s0,按照順序通過操作集中的某種操作后,狀態(tài)轉(zhuǎn)移關(guān)系如圖2-4所示,因此狀態(tài)s0的下級節(jié)點有2個。圖2-4拼圖問題步驟1

步驟2:按照深度優(yōu)先搜索的規(guī)則,當(dāng)前狀態(tài)點s0往下走的時候,優(yōu)先選擇第一個未走過的下級節(jié)點s11,也就是如

圖2-5所示的狀態(tài)轉(zhuǎn)移關(guān)系。圖2-5拼圖問題步驟2

步驟3:當(dāng)前狀態(tài)s11與目標(biāo)狀態(tài)不同,則按照操作集判

斷下一個階段狀態(tài),如圖2-6所示。圖2-6拼圖問題步驟3

步驟4:按照深度優(yōu)先搜索的規(guī)則,當(dāng)前狀態(tài)點s11往下走的時候,優(yōu)先選擇第一個未走過的下級節(jié)點s21,也就是如圖2-7所示的狀態(tài)轉(zhuǎn)移關(guān)系。

圖2-7拼圖問題步驟4

以此類推,直到算法停止,搜索過程如圖2-8所示。

圖2-8深度優(yōu)先搜索用于拼圖問題的搜索序列

2.4廣度優(yōu)先搜索

例2-6(拼圖問題)同樣,對于一個2×2拼圖問題來講,給定初始狀態(tài)和目標(biāo)狀態(tài)如圖2-9所示,要想從初始狀態(tài)達(dá)到目標(biāo)狀態(tài),也可以使用廣度優(yōu)先搜索的辦法尋找解決方案。

圖2-92×2拼圖問題的初始狀態(tài)和目標(biāo)狀態(tài)

步驟1:初始狀態(tài)為s0,按照順序通過操作集中的某種操作后,狀態(tài)轉(zhuǎn)移關(guān)系如圖2-10所示,因此狀態(tài)s0的下級節(jié)點有2個。圖2-102×2拼圖問題的步驟1

步驟2:初始狀態(tài)點s0的下級狀態(tài)節(jié)點包括s11和s12,按照廣度優(yōu)先搜索的規(guī)則,優(yōu)先搜索同級的狀態(tài)節(jié)點,也就是如圖2-11所示的狀態(tài)轉(zhuǎn)移關(guān)系。圖2-112×2拼圖問題的步驟2

步驟3:從狀態(tài)s11開始,按照操作集判斷下一個階段狀態(tài),如圖2-12所示,因此當(dāng)前狀態(tài)s11的下級節(jié)點只有s21。圖2-12-2×2拼圖問題的步驟3

步驟4:從狀態(tài)s12開始,按照操作集判斷下一個階段狀態(tài),如圖2-13所示,因此當(dāng)前狀態(tài)的下級節(jié)點只有s22。圖2-132×2拼圖問題的步驟4

步驟5:按照廣度優(yōu)先搜索的規(guī)則,搜索的狀態(tài)轉(zhuǎn)移如圖2-14所示(從上往下、從左至右的生成順序)。圖2-142×2拼圖問題的步驟5

步驟6:以此類推,直到搜索到的某個狀態(tài)和目標(biāo)狀態(tài)相同,算法停止,搜索過程如圖2-15所示。

圖2-15廣度優(yōu)先搜索用于2×2拼圖還原的搜索序列

2.5貪婪算法

貪婪算法是指,在對問題求解的每個子階段或者步驟中,總是做出在當(dāng)前看來是最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,所做出的是在某種意義上的局部最優(yōu)解。

例2-7有三種物品A、B、C,單位物品的重量分別為1、2、3,單位物品的價值分別為3、2、1,背包的最大載重為4,請問可裝入背包的物品的最大價值是多少?

例2-8有三種物品A、B、C,單位物品的重量分別為1、2、3,單位物品的價值分別為15、33、50,背包的最大載重為4,請問可裝入背包的物品的最大價值是多少?

按照貪婪算法的思想,要想裝入物品的總價值最高,那么單位價值應(yīng)該也比較高,因此,計算三種物品的單位價值分別為

因此,貪婪算法不一定能保證得到最優(yōu)解。關(guān)于背包問題,可以建立線性規(guī)劃模型求解,也可以利用動態(tài)規(guī)劃求解(參見5.4節(jié))。

貪婪算法看起來有點只顧眼前不顧長遠(yuǎn),甚至有人形容其為“飲鴆止渴”。但是在許多情況下,貪婪算法簡單直接并且好用,很多問題使用貪婪算法可以得到令人滿意的解。如果再進(jìn)一步優(yōu)化,往往要花費較大的建設(shè)成本和付出艱辛的努力,并且個體的努力還依賴于整體信息化計算環(huán)境的支持。因此,在現(xiàn)實中,貪婪算法非常好用,在許多粗放式管理與

運用中,運籌學(xué)的很多優(yōu)良的算法被束之高閣。

2.6啟發(fā)式算法

所謂啟發(fā)式算法,指的是受物理生物運行進(jìn)化規(guī)律(如模擬退火算法、煙花算法、遺傳算法)、生物智能(如蟻群算法、蜂群算法、狼