運(yùn)籌學(xué)基礎(chǔ) 課件全套 （宋志華） 第1-9章 運(yùn)籌學(xué)概述-旅行商問題

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

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

1.1

運(yùn)籌學(xué)的起源

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

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

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

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

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

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

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

1940年5月14日,德國(guó)軍隊(duì)在法國(guó)快速推進(jìn),法國(guó)此時(shí)的兵力消耗速度為每?jī)商烊齻€(gè)中隊(duì)。法國(guó)請(qǐng)求英國(guó)再增加10個(gè)中隊(duì)力量的支援(每個(gè)中隊(duì)12架飛機(jī),總共120架飛機(jī)),而英國(guó)首相很可能因?yàn)槁?lián)盟關(guān)系而向法國(guó)增援。

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

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

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

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

續(xù)。

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

1.2運(yùn)籌學(xué)的定義

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

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

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

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

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

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

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

1.3運(yùn)籌學(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ò)模型包含點(diǎn)和邊兩類必要元素。點(diǎn)代表問題中的對(duì)象,邊代表問題中對(duì)象之間的關(guān)系。以網(wǎng)絡(luò)模型為基礎(chǔ),可以研究很多網(wǎng)路優(yōu)化問題,如最小支撐樹問題、最短路問題、最大流問題、最小費(fèi)用流問題等。1956年福特和福克遜提出了網(wǎng)絡(luò)最大流問題的標(biāo)號(hào)法,建立了網(wǎng)絡(luò)流理論。

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

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

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

1.3.4生滅過程模型

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

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

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

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

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

1.3.6啟發(fā)式模型

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

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

1.3.7仿真模型

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

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

值得指出的一點(diǎn)是,仿真只是利用計(jì)算機(jī)的仿真模型進(jìn)行了大量時(shí)間軸上的計(jì)算,它不能提供最佳策略的指示。從某種意義上說,這是一個(gè)反復(fù)實(shí)驗(yàn)的過程,因?yàn)槲覀冇酶鞣N似乎有意義的策略進(jìn)行實(shí)驗(yàn),并查看仿真模型提供的客觀結(jié)果,以評(píng)估每種策略的優(yōu)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.5.1-定位

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

1.5.2問題定義

“問題定義”需要對(duì)問題的范圍和期望的結(jié)果有一個(gè)明確定義。這一階段不應(yīng)與前一階段相混淆,因?yàn)樗蛹泻兔嫦蚰繕?biāo)。

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

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

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

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

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

1.5.4模型構(gòu)建

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

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

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

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

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

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

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

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

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

1.5.5模型求解

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

1.5.6驗(yàn)證與分析

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

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

1.5.7實(shí)施與監(jiān)控

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

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

2.1生成測(cè)試范例

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

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

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

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

2.2

枚舉法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2-7拼圖問題步驟4

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

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

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

例2-6(拼圖問題)同樣,對(duì)于一個(gè)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的下級(jí)節(jié)點(diǎn)有2個(gè)。圖2-102×2拼圖問題的步驟1

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

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

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

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

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

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

2.5貪婪算法

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

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

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

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

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

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

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

2.6啟發(fā)式算法

所謂啟發(fā)式算法,指的是受物理生物運(yùn)行進(jìn)化規(guī)律(如模擬退火算法、煙花算法、遺傳算法)、生物智能(如蟻群算法、蜂群算法、狼群算法等)、人類解決問題的“經(jīng)驗(yàn)”“知識(shí)”的啟發(fā)(如旅行商問題的最近鄰算法和插入算法等、運(yùn)輸問題的最小元素法和伏格爾法等),通過模仿尋優(yōu)規(guī)則、模式而得出來的算法。啟發(fā)式算法一般能比較快速地找到滿意解,對(duì)于很多復(fù)雜問題雖然不能保證給出最優(yōu)解,但是起碼能給出不錯(cuò)的解。其缺點(diǎn)是不能保證得到最優(yōu)解,甚至對(duì)解的質(zhì)量通常也很難做出判斷。

例2-9對(duì)于如圖2-16所示的迷宮問題,請(qǐng)使用扶墻算法找到一條從入口到出口的路。所謂扶墻算法,就是從入口處開始,假設(shè)人在行進(jìn)的過程中,始終要左手(或者右手)扶著墻不能離開。扶墻算法就借鑒了人類的知識(shí)和經(jīng)驗(yàn):“順藤摸瓜”。

圖2-16迷宮問題

例2-10對(duì)于如圖2-16所示的迷宮問題,請(qǐng)使用隨機(jī)老鼠算法求解從入口到出口的路。所謂隨機(jī)老鼠算法,就是從入口處開始往前走,每當(dāng)走到分岔口的時(shí)候,就隨機(jī)決定往哪個(gè)方向走。隨機(jī)老鼠算法模仿了自然界中的老鼠的行為,最終也能找到出口,但是一般花費(fèi)的時(shí)間相對(duì)較長(zhǎng)。

2.7拓展應(yīng)用:玻璃球硬度測(cè)試實(shí)驗(yàn)設(shè)計(jì)問題

有一棟100層高的大樓,給你兩個(gè)完全相同的玻璃球。假設(shè)從某一層開始往上,丟下玻璃球會(huì)摔碎,現(xiàn)在要測(cè)試這個(gè)臨界層數(shù),作為玻璃球硬度的度量。那么怎么利用手中的兩個(gè)球,用最少的測(cè)試次數(shù),測(cè)試玻璃球的硬度呢?假如只有一個(gè)球,那么很顯然,只有一個(gè)辦法:從第一層開始投,如果沒碎再試第二層、第三層等,也就是只能使用枚舉法進(jìn)行實(shí)驗(yàn)。其實(shí)驗(yàn)次數(shù)的分布與玻璃球?qū)嶋H硬度之間的關(guān)系如圖2-17所示。

圖2-17枚舉法實(shí)驗(yàn)次數(shù)與實(shí)際硬度之間的關(guān)系

現(xiàn)在有兩個(gè)球,當(dāng)然也可以使用枚舉法,但是實(shí)驗(yàn)次數(shù)沒有降低。我們使用生成測(cè)試范例的辦法明顯可以找到一個(gè)實(shí)驗(yàn)次數(shù)更少的方案:第一個(gè)球在50層往下扔,如果碎了,說明玻璃球的硬度小于50,無須再測(cè)試50以上的樓層,如果玻璃球沒碎,則只需要測(cè)試50以上的樓層,通過這樣簡(jiǎn)單的二分法可以降低有可能的實(shí)驗(yàn)次數(shù)。其最壞情況下實(shí)驗(yàn)次數(shù)的分布與玻璃球?qū)嶋H硬度之間的關(guān)系如圖2-18所示。

圖2-18二分法的實(shí)驗(yàn)次數(shù)與實(shí)際硬度之間的關(guān)系

為了使最壞情況下的實(shí)驗(yàn)次數(shù)最小化,目標(biāo)函數(shù)設(shè)為

其中,xi為實(shí)際硬度為i的情況下的實(shí)驗(yàn)次數(shù)。

轉(zhuǎn)化成數(shù)學(xué)模型,最壞情況下,A球最后實(shí)驗(yàn)的樓層數(shù)要大于等于100才可以,也就是有如下不等式約束:

即

解出結(jié)果等于14

A球?qū)嶒?yàn)的樓層序列為14,27,39,50,60,69,77,84,90,95,99。不同實(shí)驗(yàn)策略下,實(shí)驗(yàn)期望次數(shù)與實(shí)際硬度之間的關(guān)系如圖2-19所示。圖2-19不同實(shí)驗(yàn)策略下,實(shí)驗(yàn)期望次數(shù)與實(shí)際硬度之間的關(guān)系第3章線性規(guī)劃3.1約束目標(biāo)標(biāo)準(zhǔn)型3.2從無窮到有限之基解3.3

單純形法3.4對(duì)偶問題3.5運(yùn)輸問題3.6典型案例

3.1約束目標(biāo)標(biāo)準(zhǔn)型

3.1.1線性規(guī)劃的一般形式

定義3-1線性規(guī)劃(LinearProgramming,LP)是一種凸規(guī)劃問題,它的目標(biāo)函數(shù)為最大化(或者最小化)決策變量的線性多項(xiàng)式,約束條件為決策變量的線性不等式(或者等式),其一般形式為

若記

則其一般形式可以表示為

3.1.2線性規(guī)劃的標(biāo)準(zhǔn)形式

定義3-2線性規(guī)劃的標(biāo)準(zhǔn)形式為

則標(biāo)準(zhǔn)形式可以記為

定理3-1線性規(guī)劃的一般形式可以轉(zhuǎn)換為等價(jià)的標(biāo)準(zhǔn)形式。

對(duì)于目標(biāo)函數(shù),可以通過將系數(shù)向量取負(fù),將最大化和最小化目標(biāo)函數(shù)進(jìn)行互化。對(duì)于約束條件來講,不等式可以通過增加輔助決策變量的方法進(jìn)行轉(zhuǎn)換,遵循以下轉(zhuǎn)換規(guī)則:

(1)對(duì)于小于不等式,在左側(cè)加上一個(gè)輔助決策變量。

(2)對(duì)于大于不等式,在左側(cè)減去一個(gè)輔助決策變量。

例3-1對(duì)于如下線性規(guī)劃模型的一般形式,將其轉(zhuǎn)換為標(biāo)準(zhǔn)形式。

先通過將系數(shù)向量取負(fù),將目標(biāo)函數(shù)轉(zhuǎn)換為最小化,然后增加一個(gè)輔助決策變量將約束條件不等式轉(zhuǎn)換為等式,得到如下標(biāo)準(zhǔn)形式

3.1.3-整數(shù)線性規(guī)劃

定義3-3-如果線性規(guī)劃的所有決策變量都必須是整數(shù),那么這個(gè)問題稱為整數(shù)規(guī)劃問題。

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

設(shè)裝入背包的三種物品的數(shù)量分別為x1,x2,x3,則可以建立一般形式的線性規(guī)劃模型

其中目標(biāo)函數(shù)代表最大化裝入背包中物品的價(jià)值,第一個(gè)約束條件代表裝入背包中的物品總重量不能超過背包的最大載重4,第二個(gè)約束條件代表裝入背包中物品的數(shù)量不能為負(fù),第三個(gè)約束條件代表裝入背包中物品的數(shù)量為整數(shù)

定義3-4如果線性規(guī)劃的所有決策變量只能取0或者1,則稱之為0-1整數(shù)規(guī)劃。

3.2從無窮到有限之基解

3.2.1可行解

定義3-5可行解是滿足約束條件的解。所有可行解的集合稱作可行域。

首先,線性規(guī)劃標(biāo)準(zhǔn)形式約束條件的主體是一個(gè)線性方程組,另外加一個(gè)非負(fù)條件。

若先不考慮非負(fù)條件,這個(gè)線性方程組可變?yōu)?/p>

與線性規(guī)劃問題的可行域有如圖3-1所示對(duì)應(yīng)關(guān)系。

圖3-1線性規(guī)劃可行域與線性方程組解集之間的對(duì)應(yīng)關(guān)系

定理3-2線性規(guī)劃標(biāo)準(zhǔn)形式的可行域等于其約束條件組成的線性方程組的非負(fù)解集。

根據(jù)線性方程組解的理論,線性方程組的解有以下幾種情況:

(1)無解,R(A)<R(A,b)。

(2)唯一最優(yōu)解,R(A)=R

(A,b)=n。

3)無窮多最優(yōu)解,R(A)=R(A,b)<n。其中,A=[aij

];b=[bi

];i=1,…,m;j=1,…,n;R(·)代表矩陣的秩。

因此,根據(jù)定理3-2,可以有以下結(jié)論:

(1)若線性規(guī)劃標(biāo)準(zhǔn)形式約束條件構(gòu)成的線性方程組無解,則線性規(guī)劃問題無解。

(2)若此線性方程組有唯一非負(fù)解,則這個(gè)解是線性規(guī)劃問題可行解也是最優(yōu)解;若此線性方程組有唯一解,但是負(fù)數(shù),則線性規(guī)劃問題無解。

(3)若此線性方程組有無窮多非負(fù)解,則線性規(guī)劃問題有可能有無窮多可行解,這種情況是線性規(guī)劃研究的重點(diǎn)。

3.2.2基解

在這種情況下,根據(jù)生成測(cè)試范例的樸素優(yōu)化思想,我們可以往可解的方向碰碰運(yùn)氣。如果令任意n-m個(gè)變量取特定值(如取0),把它們看作常量,移動(dòng)到等式的右邊,得

這樣方程組就可解了。

定義3-6如果將n-m個(gè)變量取值為0,對(duì)線性規(guī)劃標(biāo)準(zhǔn)形式約束條件構(gòu)成的線性方程組求解,若能得到唯一解,則稱此解為線性規(guī)劃問題的基解,如果基解滿足非負(fù)條件,則稱為基可行解,取值為0的n-m個(gè)決策變量稱為非基變量,等式左邊的m個(gè)決策變量稱為基變量,基變量對(duì)應(yīng)的系數(shù)矩陣的列稱為基向量,基向量組成的矩陣稱為線性規(guī)劃問題的基。

例如,對(duì)于線性方程組(3-1),若有唯一解,則其所對(duì)應(yīng)的線性規(guī)劃問題的基為

其中,Pi為基向量,與基向量Pi相應(yīng)的變量xi為基變量,否則稱為非基變量。

3.2.3-基解三定理

定理3-3-若線性規(guī)劃問題存在可行域,則一定是凸集。

定理3-4若線性規(guī)劃問題的可行域有界,則一定可在此凸集的頂點(diǎn)上達(dá)到最優(yōu)。

定理3-5線性規(guī)劃的可行域的頂點(diǎn)與基可行解一一對(duì)應(yīng)

(2)若X不是基可行解,則X一定不是可行域的頂點(diǎn)。

3.2.4基解的枚舉

這樣,由于最優(yōu)解一定是基解,基解的數(shù)量是有限的,因此可以使用枚舉法求解線性規(guī)劃標(biāo)準(zhǔn)形式,步驟為:

步驟1:在n個(gè)決策變量中,選擇m個(gè)決策變量作為基變量,其他變量取0,求線性規(guī)劃標(biāo)準(zhǔn)形式隱含的線性規(guī)劃方程組,若得到唯一解,則此唯一解就是基解,若非負(fù),則是基可行解。

步驟2:循環(huán)執(zhí)行步驟1直到找出所有的基可行解,對(duì)比其目標(biāo)函數(shù),使目標(biāo)函數(shù)達(dá)到最優(yōu)的即為最優(yōu)解。

例3-4對(duì)如下的線性規(guī)劃一般形式的模型:

(1)將其可行域在二維坐標(biāo)系中表示出來。

(2)將一般形式轉(zhuǎn)換為標(biāo)準(zhǔn)形式,并計(jì)算其所有的基解。

(3)對(duì)比基解與可行域在二維坐標(biāo)系中的頂點(diǎn)的關(guān)系。

因?yàn)槊總€(gè)約束條件不等式都代表二維平面上的一個(gè)半平面,因此,這些半平面的交集構(gòu)成線性規(guī)劃問題的可行域,利用軟件QMforWindows畫出來的可行域如圖3-2所示。圖3-2圖解法實(shí)例

將其轉(zhuǎn)換為標(biāo)準(zhǔn)形式為

利用基解的求解方法可得,基解、基可行解及其對(duì)應(yīng)的目標(biāo)函數(shù)值如表3-1所示。

3.2.5基解的啟發(fā)尋優(yōu)

采用啟發(fā)式算法尋找最優(yōu)解的基本流程如圖3-3所示。圖3-3-基解的啟發(fā)尋優(yōu)過程框架

3.3-單純形法

3.3.1起點(diǎn)單純形法可以選擇任意基可行解作為搜索的起點(diǎn)。為了方便,可以直接在系數(shù)矩陣中找出或者通過初等變換得到一個(gè)單位子矩陣,其所對(duì)應(yīng)的變量作為初始可行基變量。

3.3.2鄰域中的改進(jìn)解

1.換入基的確定

根據(jù)約束條件,非基變量可以使用基變量來表示。因此,在約束條件中,將非基變量移動(dòng)到等式右邊,求得基變量的表達(dá)形式為

換入基操作:利用非基變量表示目標(biāo)函數(shù),非基變量xj的系數(shù)σj作為檢驗(yàn)數(shù),即

檢驗(yàn)數(shù)σj為正的非基變量進(jìn)基．

2.換出基的確定

換出基操作:確定了換入基變量之后,利用

確定換出基變量xl。

3.3.3-終止

當(dāng)所有的檢驗(yàn)數(shù)σj均小于等于0的時(shí)候,非基變量無法進(jìn)基,目標(biāo)函數(shù)無法得到進(jìn)一步的改進(jìn),算法終止。

3.3.4算例

例3-5對(duì)于如下的線性規(guī)劃標(biāo)準(zhǔn)形式:

系數(shù)矩陣為

步驟2:通過換入基和換出基操作,得到一個(gè)改進(jìn)的基可行解。所有與基x3,x4相鄰的基如表3-3所示。

將以上計(jì)算過程的數(shù)據(jù)整理到單純形表中,如表3-4所示。

將換入基變量x2和換出基變量x4進(jìn)行調(diào)換,得到表3-5。

步驟3:通過換入基和換出基操作,得到下一個(gè)改進(jìn)的基可行解。所有與基x3,x2相鄰的基如表3-6所示。

根據(jù)約束條件中基變量與非基變量之間的關(guān)系,使用非基變量表示目標(biāo)函數(shù)得

從換基的效果來講,選擇x1進(jìn)基可以使目標(biāo)函數(shù)值增加,x4進(jìn)基可以使目標(biāo)函數(shù)值降低。因此選擇x1進(jìn)基,當(dāng)前待換入基變量為x1。

將換入基變量x1和換出基變量x3進(jìn)行調(diào)換,得到表3-8。

步驟4:通過換入基和換出基操作,得到下一個(gè)改進(jìn)的基可行解。所有與基x1,x2相鄰的基如表3-9所示。

根據(jù)約束條件中基變量與非基變量之間的關(guān)系,使用非基變量表示目標(biāo)函數(shù)得

從換基的效果來講,選擇x3或者x4進(jìn)基均使目標(biāo)函數(shù)值降低,因此算法停止。

對(duì)表3-9進(jìn)行初等變換,令基變量對(duì)應(yīng)的系數(shù)列向量為單位向量,并重新計(jì)算檢驗(yàn)數(shù)

從而得到表3-10。

此時(shí)的基可行解為最優(yōu)解:

3.4對(duì)偶問題

3.4.1機(jī)會(huì)成本與影子價(jià)格定義3-7機(jī)會(huì)成本是當(dāng)投資者、個(gè)人或企業(yè)決策時(shí)選擇某種方案而不是另一種方案時(shí),錯(cuò)過或放棄的收益。

例3-6假設(shè)你的公司使用A和B兩種原料生產(chǎn)C、D兩種油漆,表3-11提供了基本數(shù)據(jù)。

請(qǐng)問怎么確定最好的C、D油漆產(chǎn)品混合,使你的日總利潤(rùn)最大?

假設(shè)生產(chǎn)C、D油漆的數(shù)量分別為x1和x2,則上述問題可以建立以下線性規(guī)劃模型

利用單純形法可以很容易求得問題的最優(yōu)解為x1=3,x2=1.5,z=21。

但是僅就獲取利潤(rùn)來講,如果另外一個(gè)經(jīng)理時(shí)刻關(guān)注著原材料的市場(chǎng)價(jià)格y1和y2,當(dāng)市場(chǎng)價(jià)格達(dá)到某個(gè)水平時(shí),他可以選擇不生產(chǎn),而直接賣掉原材料,卻可以獲得更大的利潤(rùn),這個(gè)多獲得的利潤(rùn)就是用原材料進(jìn)行生產(chǎn)而不是直接賣掉的機(jī)會(huì)成本。例如,原材料1和原材料2的價(jià)格滿足以下約束:

則自己生產(chǎn)的利潤(rùn)是要小于直接把原材料賣掉所獲得的利潤(rùn)的,辛辛苦苦生產(chǎn)的還不如將原材料直接賣掉的企業(yè)掙得多,如圖3-4所示。

圖3-4影子價(jià)格

影子價(jià)格使用如下模型求得

而這個(gè)模型,由于和原線性規(guī)劃模型有著十分漂亮和規(guī)整的關(guān)系,稱為原線性規(guī)劃問題的對(duì)偶問題。

3.4.2對(duì)偶問題的模型

一般地,對(duì)于如下線性規(guī)劃模型

其對(duì)偶問題模型為

更為一般地,任意形式的線性規(guī)劃都可以通過以下變換規(guī)則得到其對(duì)應(yīng)的對(duì)偶問題。

(1)原問題的約束條件和對(duì)偶問題的決策變量一一對(duì)應(yīng),原問題約束條件的右端常數(shù)作為對(duì)偶問題的目標(biāo)函數(shù)系數(shù);

(2)原問題的決策變量和對(duì)偶問題的約束條件一一對(duì)應(yīng),原問題的目標(biāo)函數(shù)系數(shù)作為對(duì)偶問題約束條件的右端常數(shù)項(xiàng),原問題的系數(shù)矩陣轉(zhuǎn)置后等于對(duì)偶問題的系數(shù)矩陣;

(3)原問題為最大化(最小化),則對(duì)偶問題為最小化(最大化);

(4)約束與變量之間對(duì)應(yīng)的不等式方向的變換規(guī)則如表3-12所示。

3.5運(yùn)輸問題

3.5.1真假運(yùn)輸問題1.真運(yùn)輸問題本章所述的運(yùn)輸問題,是最簡(jiǎn)單的運(yùn)輸問題,運(yùn)輸?shù)呢浳锸菃我粺o差別的,不同的產(chǎn)地產(chǎn)量不同,不同的銷地需求量不同,不同產(chǎn)地和銷地之間的運(yùn)輸費(fèi)用也不同,在這樣的情況下,確定不同產(chǎn)地到不同銷地之間的供應(yīng)量,使運(yùn)輸費(fèi)用最小。

例3-7三個(gè)煉油廠的日煉油能力分別為600萬升、500萬升和800萬升,所供應(yīng)三個(gè)分銷區(qū)域的日需求量分別為400萬升、800萬升和700萬升。汽油通過輸油管線被運(yùn)送到分銷區(qū)域。管線每公里運(yùn)送1萬升的運(yùn)費(fèi)為100元。表3-13給出了煉油廠到分銷區(qū)域的里程表。其中煉油廠1與分銷區(qū)域3-不相連。

例3-8為確保飛行安全,飛機(jī)發(fā)動(dòng)機(jī)需定時(shí)更換進(jìn)行大修。現(xiàn)有三個(gè)航修廠和四個(gè)機(jī)場(chǎng)。三個(gè)航修廠A1、A2、A3-的月修復(fù)量分別為7臺(tái)、4臺(tái)、9臺(tái);四個(gè)機(jī)場(chǎng)B1、B2、B3、B4的月需求量為3臺(tái)、6臺(tái)、5臺(tái)、6臺(tái)。各航修廠到各機(jī)場(chǎng)的單位運(yùn)價(jià)(萬元)如表3-14所示。問應(yīng)如何調(diào)運(yùn)發(fā)動(dòng)機(jī)完成運(yùn)輸任務(wù)而使運(yùn)費(fèi)最省。

2.假運(yùn)輸問題

有一些問題雖然表面上看著不是運(yùn)輸問題,但是可以建立運(yùn)輸問題的類比模型,因此,我們稱之為假運(yùn)輸問題。

例3-9一種小型發(fā)動(dòng)機(jī)未來五個(gè)月的需求量分別為200臺(tái)、150臺(tái)、300臺(tái)、250臺(tái)、480臺(tái)。生產(chǎn)商對(duì)這五個(gè)月的生產(chǎn)能力估計(jì)為180臺(tái)、230臺(tái)、430臺(tái)、300臺(tái)、300臺(tái)。不允許延期交貨,但在必要的情況下生產(chǎn)商可安排加班滿足當(dāng)前需求。每個(gè)月的加班生產(chǎn)能力是正常生產(chǎn)能力的一半。五個(gè)月的單位生產(chǎn)費(fèi)用分別為100元、96元、116元、102元、106元。加班生產(chǎn)的費(fèi)用比正常生產(chǎn)的費(fèi)用高50%。如果當(dāng)月生產(chǎn)的發(fā)動(dòng)機(jī)在以后月使用,則每臺(tái)發(fā)動(dòng)機(jī)每個(gè)月的額外儲(chǔ)存費(fèi)用為4萬元。為問題建立一個(gè)運(yùn)輸模型并確定每個(gè)月正常生產(chǎn)和加班生產(chǎn)發(fā)動(dòng)機(jī)的數(shù)量。

3.5.2運(yùn)輸問題模型

1.線性規(guī)劃模型

設(shè)xij和cij為產(chǎn)地i到銷地j的物品運(yùn)輸量和單位運(yùn)價(jià),si為產(chǎn)地i的產(chǎn)量,dj為銷地j的需求量,則運(yùn)輸問題的線性規(guī)劃模型如下:

其系數(shù)矩陣具有如下形式:

2.表模型

運(yùn)輸表模型,就是在運(yùn)輸費(fèi)用表的基礎(chǔ)上,拓展而成的一個(gè)表,其基本框架如表3-15所示。

因此,例3-7就可以建立如表3-16所示的運(yùn)輸表模型．

例3-8的運(yùn)輸表模型如表3-17所示。

對(duì)于例3-9來講,要建立運(yùn)輸表模型,就要確定產(chǎn)地、銷地、單位運(yùn)價(jià)以及供應(yīng)量和需求量等表中的基本要素。產(chǎn)地和銷地分別有五個(gè),代表五個(gè)月份,i月到j(luò)月的單位運(yùn)價(jià)就是i月生產(chǎn)一個(gè)發(fā)動(dòng)機(jī)j月用的總的費(fèi)用,這個(gè)總的費(fèi)用要包含正常生產(chǎn)費(fèi)用、加班費(fèi)用、儲(chǔ)存費(fèi)用等因素。其中,空白區(qū)域?qū)?yīng)的產(chǎn)地和銷地?zé)o法到達(dá),所建立的運(yùn)輸表模型如表3-18所示。

3.圖模型

所謂圖模型,就是將產(chǎn)地和銷地用圖上的點(diǎn)來表示,點(diǎn)上有數(shù)字代表供應(yīng)量或者需求量,使產(chǎn)地和銷地之間的邊來表示運(yùn)輸關(guān)系,邊上的權(quán)重表示單位運(yùn)價(jià)。

例3-7的運(yùn)輸圖模型如圖3-5所示,其中從s點(diǎn)到煉油廠的邊上的容量為煉油廠的產(chǎn)量,單位運(yùn)價(jià)為0;從分銷區(qū)域到t的邊上的容量為分銷區(qū)域的需求量,單位運(yùn)價(jià)為0;從煉油廠到分銷區(qū)域的其他邊上的容量沒有限制,單位運(yùn)價(jià)為兩者之間的單位運(yùn)價(jià)。

圖3-5例3-7的運(yùn)輸問題圖模型

例3-8的運(yùn)輸圖模型如圖3-6所示。其中從s點(diǎn)到航修廠的邊上的容量為月修復(fù)量,單位運(yùn)價(jià)為0;從機(jī)場(chǎng)到t的邊上的容量為機(jī)場(chǎng)的需求量,單位運(yùn)價(jià)為0;從航修廠到機(jī)場(chǎng)的其他邊上的容量沒有限制,單位運(yùn)價(jià)為兩者之間的單位運(yùn)價(jià)。

圖3-6例3-8的運(yùn)輸問題圖模型

例3-9的運(yùn)輸圖模型如圖3-7所示。其中從s點(diǎn)到煉油廠的邊上的容量為煉油廠的產(chǎn)量,單位運(yùn)價(jià)為0;從分銷區(qū)域到t的邊上的容量為分銷區(qū)域的需求量,單位運(yùn)價(jià)為0;從煉油廠到分銷區(qū)域的其他邊上的容量沒有限制,單位運(yùn)價(jià)為兩者之間的單位運(yùn)價(jià)。

圖3-7例3-9的運(yùn)輸問題圖模型

3.5.3-運(yùn)輸問題算法

1.貪婪啟發(fā)式算法

1)最小元素法

最小元素法中的元素,指的就是運(yùn)價(jià),也就是為產(chǎn)地和銷地之間的貨物制訂匹配運(yùn)輸關(guān)系時(shí),優(yōu)先選擇可運(yùn)輸?shù)娜肿钚∵\(yùn)價(jià)。最小元素法屬于貪婪啟發(fā)式算法,不能保證得到最優(yōu)解,但是可以得到一般意義下的較優(yōu)解。

例如,表3-16的表模型中,運(yùn)用最小元素法的計(jì)算運(yùn)輸方案過程如下:

(1)在運(yùn)價(jià)表中選擇最小元素,并最大化地滿足其對(duì)應(yīng)的產(chǎn)銷地的剩余產(chǎn)銷量,從而得到表3-19。

(2)在運(yùn)價(jià)表中選擇供需均大于0的最小元素,并最大化地滿足其對(duì)應(yīng)的產(chǎn)銷地的剩余產(chǎn)銷量,從而得到表3-20。

(3)在運(yùn)價(jià)表中選擇供需均大于0的最小元素,并最大化地滿足其對(duì)應(yīng)的產(chǎn)銷地的剩余產(chǎn)銷量,從而得到表3-21。

(4)再一步迭代計(jì)算得到表3-22。

(5)繼續(xù)迭代計(jì)算得到表3-23。

(6)所有的供應(yīng)量和均為0,算法結(jié)束,得到最后結(jié)果如表3-24所示,其中括號(hào)中的數(shù)量為對(duì)應(yīng)產(chǎn)地和銷地之間的運(yùn)量方案。

2)伏格爾法

最小元素法是貪婪算法,特點(diǎn)是只顧眼前。伏格爾法的考慮往前更進(jìn)了一步,如果一個(gè)物品不能按照最小的費(fèi)用運(yùn)輸,而是按照次小的費(fèi)用運(yùn)輸,這就有一個(gè)差額,不妨令gsi代表產(chǎn)地i的差額,gjd代表銷地j的差額。將這個(gè)差額作為一種啟發(fā)信息,對(duì)于差額大的產(chǎn)地或者銷地,優(yōu)先安排最小元素,這樣有可能會(huì)降低貪婪的成本。

步驟4:若產(chǎn)銷地均無余量可形成運(yùn)輸指派,也即

則算法結(jié)束,否則轉(zhuǎn)步驟2。

2.最優(yōu)性條件

定理3-6對(duì)于貪婪啟發(fā)式算法得到的除最后一個(gè)0+之外的m+n-1個(gè)變量為基變量(包括取值為正以及0+的所有變量),這樣給出的解是運(yùn)輸問題的基解。

證明:首先,算法每使一個(gè)產(chǎn)地的產(chǎn)量或者銷地的需求歸0,就會(huì)增加一個(gè)變量,因此,使所有的產(chǎn)量及銷量歸0,總共增加的變量的個(gè)數(shù)為m+n,而算法最后一步加上的變量的值為0+,除去這個(gè)變量之外的m+n-1個(gè)變量構(gòu)成基變量。

在使用貪婪啟發(fā)式算法確定第一個(gè)變量xi1j1,它對(duì)應(yīng)的系數(shù)列向量為

其中,ei1是第i1個(gè)元素為1的單位列向量。

例3-10檢驗(yàn)例3-7的結(jié)果(見表3-25)是不是最優(yōu)解。

因?yàn)榛兞康臋z驗(yàn)數(shù)為0,所以有

可見,非基變量的檢驗(yàn)數(shù)有非負(fù)的,即

3.5.4從不平衡到平衡

例3-11在例3-7的基礎(chǔ)上,假設(shè)煉油廠3的日生產(chǎn)能力增大為1000萬升,那么必然有銷地得不到完全滿足,在這種情況下,建立相應(yīng)的運(yùn)輸模型,使三個(gè)煉油廠的煉油最大化地運(yùn)輸,并且總的運(yùn)費(fèi)最小。

可以建立一個(gè)虛擬的銷地,其銷量為200萬升,并設(shè)煉油廠到此虛擬銷地的運(yùn)價(jià)取較大的數(shù),例如1000000,可建立運(yùn)輸問題的表模型如表3-27所示。

3.6典型案例

3.6.1投資方案的規(guī)劃1.問題描述良好的投資規(guī)劃,對(duì)國(guó)民生產(chǎn)產(chǎn)生直接推動(dòng)作用,對(duì)國(guó)民收入有著正相關(guān)的積極影響。在投資方案的規(guī)劃過程中既要考慮實(shí)現(xiàn)投資方案的可行性,又要考慮投資方案的盈利率。這里考慮一個(gè)經(jīng)過抽象和定義過的案例。

2.問題分析

單從收益率來講,計(jì)劃B具有明顯的優(yōu)勢(shì),因此,根據(jù)啟發(fā)式規(guī)則,我們要將盡量多的錢投入B計(jì)劃中。投資周期為三年,B計(jì)劃以兩年為周期,因此在三年的周期中,計(jì)劃B只能投資一次,若第一年全部投到B計(jì)劃中,則在第二年末收回本金和收益共計(jì)300萬元之后,還剩下一年,只能投資于A計(jì)劃,到第三年末總共收益321萬元。

為了讓B計(jì)劃能有更多的資金,獲取更高的收益,我們可以讓100萬元第一年先投資于A計(jì)劃,第二年得到總計(jì)107萬元之后,再將其全部投入B計(jì)劃中,這樣第三年末得到的總收入是321萬元。

3.建立模型

設(shè)決策變量如表3-28所示。

表3-28決策變量及其含義

整理得如下線性規(guī)劃模型:

4.求解

應(yīng)用Matlab的線性規(guī)劃求解函數(shù)linprog,求解的代碼及得到的最優(yōu)解如下所示:

5.單純形表求解

利用單純形法進(jìn)行計(jì)算,首先要將線性規(guī)劃轉(zhuǎn)化成標(biāo)準(zhǔn)形式如下:

(1)列出初始單純形表如表3-29所示。

(2)選定檢驗(yàn)數(shù)σj最大的非基變量之一作為進(jìn)基變量,這里可選擇x1B進(jìn)基,在其所在的列,按照換出基確定的規(guī)則,可選擇y1或者y2作為出基變量,這里不妨選y1作為出基變量,從而得到表3-30。

(3)通過初等變換,將x1B所在的列變?yōu)閱挝幌蛄?更新檢驗(yàn)數(shù)基右端常數(shù)項(xiàng),從而得到表3-31。

(4)同樣地,選定檢驗(yàn)數(shù)σj最大的非基變量x2B進(jìn)基,在其所在的列,按照換出基確定的規(guī)則,選擇y2作為出基變量,從而得到表3-32。

(5)通過初等變換,將x2B所在的列變?yōu)閱挝幌蛄?更新檢驗(yàn)數(shù)基右端常數(shù)項(xiàng),從而得到表3-33。

(6)選定檢驗(yàn)數(shù)σj最大的非基變量x1A進(jìn)基,在其所在的列,按照換出基確定的規(guī)則,選擇x1B

作為出基變量,從而得到表3-34。

(7)通過初等變換,將x1A所在的列變?yōu)閱挝幌蛄?更新檢驗(yàn)數(shù)基右端常數(shù)項(xiàng),從而得到表3-35。

(8)選定檢驗(yàn)數(shù)σj最大的非基變量x3A進(jìn)基,在其所在的列,按照換出基確定的規(guī)則,選擇y3作為出基變量,從而得到表3-36。

6.討論

模型不考慮盈利率波動(dòng),以及資金的時(shí)間價(jià)值等在實(shí)際的投資中會(huì)考慮的一些重要因素。

軟件計(jì)算和使用單純形表手工計(jì)算得出來的分配方案并不相同,但是最優(yōu)目標(biāo)函數(shù)值是一樣的,這說明模型的最優(yōu)解不唯一。

3.6.2防御兵力的部署

1.問題描述

藍(lán)軍試圖入侵由紅軍防御的領(lǐng)地。紅軍有三條防線和200個(gè)正規(guī)戰(zhàn)斗單位,并且還能抽調(diào)出200個(gè)預(yù)備單位。藍(lán)軍計(jì)劃進(jìn)攻兩條前線(南線和北線);紅軍設(shè)置三條東西防線

(Ⅰ、Ⅱ、Ⅲ),防線Ⅰ和防線Ⅱ各自要至少阻止藍(lán)軍進(jìn)攻4天以上,并盡可能延長(zhǎng)總的戰(zhàn)斗持續(xù)時(shí)間。藍(lán)軍的前進(jìn)時(shí)間由下列經(jīng)驗(yàn)公式估計(jì)得到:

戰(zhàn)斗持續(xù)天數(shù)的經(jīng)驗(yàn)公式的系數(shù)如表3-37所示。

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

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

2.問題分析

定義八個(gè)決策變量xij(i=1,2;j=1,2,3),分別表示各個(gè)防線上的正規(guī)兵力部署數(shù)量,yij表示部署在防線Ⅱ上的預(yù)備兵力的數(shù)量。那么我們就可以依據(jù)經(jīng)驗(yàn)公式計(jì)算各個(gè)防線上的戰(zhàn)斗持續(xù)時(shí)間。

案例要求盡可能延長(zhǎng)總的戰(zhàn)斗持續(xù)時(shí)間,這只是戰(zhàn)術(shù)要求的具體量化抽象,在不同的戰(zhàn)術(shù)場(chǎng)景中,對(duì)總的戰(zhàn)斗持續(xù)時(shí)間也有不同的具體計(jì)算方式。

以下的目標(biāo)函數(shù)適合類似“拖延戰(zhàn)”的戰(zhàn)術(shù)場(chǎng)景,也就是作戰(zhàn)的目的是拖住敵方的兵力,使其無法騰出手來攻擊其他目標(biāo)。

3.建立模型

兵力的分配要受到以下約束:

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

4.求解

采用目標(biāo)函數(shù)一的時(shí)候,數(shù)學(xué)模型是線性規(guī)劃模型,可以使用Matlab求解。

5.討論

線性規(guī)劃的模型和算法都很標(biāo)準(zhǔn)化、程序化,可以快速方便地求解很多復(fù)雜和大型的問題。但是,我們?nèi)匀恍枰谛睦锢斡?這并不能替代優(yōu)化決策系統(tǒng)過程中的其他環(huán)節(jié)。

3.6.3-火車站售票的規(guī)劃

1.問題描述

從城市A到城市B開通了一條新的客運(yùn)鐵路,總共有N個(gè)站點(diǎn),各站點(diǎn)依次編號(hào),A市站點(diǎn)編號(hào)1,B市站點(diǎn)編號(hào)N。這列火車的最大載客量是n人。為提高客運(yùn)能力,增加收益,在對(duì)歷史數(shù)據(jù)進(jìn)行了統(tǒng)計(jì)分析以及對(duì)未來一段時(shí)間進(jìn)行了預(yù)測(cè)的基礎(chǔ)上,得出了不同站點(diǎn)之間客運(yùn)需求的數(shù)量。如果因客運(yùn)量限制而不能接受所有訂單,則會(huì)拒絕部分訂單。現(xiàn)在要根據(jù)這些數(shù)據(jù),確定鐵路售票的規(guī)劃,使可能的總收益最大化,一個(gè)已接受訂單的收益是訂單中乘客人數(shù)和火車票價(jià)格的乘積?？偸找媸撬幸呀邮苡唵蔚氖找嬷?。

例如,假設(shè)從城市A到城市B的站點(diǎn)數(shù)目為N=6,火車最大載客量n=2000,不同站點(diǎn)之間的客運(yùn)需求已知數(shù)據(jù)如表3-39所示。

2.問題分析與建模

3.求解

3.6.4武器目標(biāo)分配問題

1.問題描述

在時(shí)刻t,某單位有3個(gè)武器系統(tǒng),每個(gè)武器系統(tǒng)均有2個(gè)目標(biāo)通道,要射擊6批目標(biāo),武器系統(tǒng)對(duì)目標(biāo)的射擊有利度數(shù)據(jù)如表3-41所示,要進(jìn)行目標(biāo)分配,使總的射擊有利度達(dá)到最大,請(qǐng)建立數(shù)學(xué)模型。

2.問題分析與建模

為了簡(jiǎn)化起見,將上述模型進(jìn)行轉(zhuǎn)化,每個(gè)通道視為一個(gè)單獨(dú)的武器,建立武器目標(biāo)分配問題的射擊有利度矩陣如表3-42所示。第4章網(wǎng)絡(luò)最優(yōu)化4.1最小支撐樹問題4.2最短路問題4.3最大流問題4.4

最小費(fèi)用流問題4.5二分匹配問題

4.1最小支撐樹問題

定義4-3連通圖G=(V,E)的最小支撐樹T(G)就是圖的權(quán)重之和最小的支撐樹。

其中,cij是邊(i,j)的權(quán)重。

例4-1某公司中標(biāo)為“一帶一路”上某國(guó)家的六個(gè)居民點(diǎn)提供寬帶建設(shè)服務(wù),圖4-1給出了鋪設(shè)通信線路的可能情況及相應(yīng)距離。請(qǐng)確定最經(jīng)濟(jì)的通信線路鋪設(shè)方案,使六個(gè)居民點(diǎn)可以連接起來。

圖4-1寬帶網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)問題的輸入

記六個(gè)居民點(diǎn)及相應(yīng)的可能連接方式組成的圖為G=(V,E),設(shè)xij為決策變量,xij=1代表點(diǎn)i與點(diǎn)j之間鋪設(shè)的通信線路,否則不鋪設(shè)。此問題可以表示為以下線性規(guī)劃模型

本問題可以使用線性規(guī)劃求解,但是對(duì)于點(diǎn)的數(shù)量較多的問題,使用線性規(guī)劃求解的話就不可行了。例如,對(duì)于有60個(gè)點(diǎn)的圖,要用線性規(guī)劃模型求解最小支撐樹,需要的約束條件數(shù)量比地球上的原子數(shù)量還多。

支撐樹使用了最少數(shù)量的邊連通了圖的所有點(diǎn),從數(shù)量方面是網(wǎng)絡(luò)連通優(yōu)化設(shè)計(jì)問題的最優(yōu)方案,而最小支撐樹是邊的總長(zhǎng)度之和最小的支撐樹,因此,從數(shù)量和質(zhì)量方面都是最優(yōu)的網(wǎng)絡(luò)連通設(shè)計(jì)方案。

4.1.2兩個(gè)屬性

1.Cut屬性

在最小支撐樹的線性規(guī)劃模型中,式(4-2)代表連通性約束,不等式左側(cè)的表達(dá)式表示圖的截集中至少有一條邊要保留。

定義4-4-圖G=(V,E)中,對(duì)于?S?V,所有的一端在S中、一端不在S中的邊構(gòu)成的集合稱為圖的截集。

例4-2圖4-1的截集數(shù)量為6!/2,其中兩個(gè)如圖4-2所示。圖4-2圖的截集示例

最小支撐樹的Cut屬性:連通圖G任意截集的最小邊必屬于最小支撐樹。

2.Cycle屬性

最小支撐樹的另外一個(gè)屬性是無圈的,因此,任意圈上肯定有一條邊不屬于最小支撐樹,依據(jù)“貪婪法”的啟發(fā)式規(guī)則,我們猜測(cè)圈上的最大邊不屬于最小支撐樹。

最小支撐樹的Cycle屬性:圖中圈上若只有單一最大邊,則此最大邊一定不屬于最小支撐樹;若有多條最大邊,則去掉任意一條最大邊,不影響得到最小支撐樹。總之,去掉圈上一條最大邊,仍然可以得到最小支撐樹。

算法的步驟如下:

例4-3利用Prim算法求解圖4-1的最小支撐樹。

步驟1:首先令S={6},則Cut(S)={(6,3),(6,4)},E(T)=?,得到最小邊為emin=(6,4),如圖4-3所示。

步驟2:(6,4)是最小支撐樹上的邊,令E(T)=E(T)∪emin={(6,4)},S=S∪V(emin)={6,4},則

Cut(S)={(6,3),(4,1),(4,2),(4,3),(4,5)}

得到最小邊emin=(4,2),如圖4-4所示。

圖4-3例4-3求解步驟1的結(jié)果

圖4-4-例4-3求解步驟2的結(jié)果

步驟3:(4,2)是最小支撐樹上的邊,令E(T)=E(T)∪emin={(6,4),(4,2)},S=S∪V(emin)={6,4,2},則

Cut(S)={(6,3),(4,1),(4,3),(4,5),(2,1),(2,3),(2,5)}

得到最小邊emin=(1,2),如圖4-5所示。

圖4-5例4-3求解步驟3的結(jié)果

步驟4:(1,2)是最小支撐樹上的邊,令E(T)=E(T)∪emin={(6,4),(4,2),(1,2)},S=S∪V(emin)={6,4,2,1},則

Cut(S)={(6,3),(4,3),(4,5),(2,3),(2,5),(1,3),(1,5)}

得到最小邊有三條,emin=(2,3)、(2,5)、(4,3),如圖4-6所示。

圖4-6例4-3求解步驟4的結(jié)果

步驟5:可以任選一條最小邊加入E(T),如(2,3)。令E(T)=E(T)∪emin

={(6,4),(4,2),(1,2),(2,3)},S=S∪V(emin

)={6,4,2,1,3},則

Cut(S)={(4,5),(2,5),(1,5)}

得到最小邊emin

=(2,5),如圖4-7所示。

圖4-7例4-3求解步驟5的結(jié)果

步驟6:(2,5)是最小支撐樹上的邊。令E(T)=E(T)∪emin

={(6,4),(4,2),(1,2),(2,3),(2,5)},S=S∪V(emin

)={6,4,2,1,3,5},算法結(jié)束,如圖4-8所示。圖4-8例4-3求解步驟6的結(jié)果

2.Kruskal算法

從構(gòu)造的角度考慮,在選擇一部分邊時(shí),只要避免將圈上的最大邊選上就可以了。

Kruskal從構(gòu)造的角度提出了尋找最小支撐樹的方法。

Kruskal法將所有的邊從圖中取出來,從小到大依次考慮重新加回到圖中,如果不產(chǎn)生圈則留下,否則拋棄掉,這也是一種“貪婪算法”。

例4-4-利用Kruskal算法求解圖4-1的最小支撐樹。

步驟1:令E(T)=?,當(dāng)前圖中的最小邊為

如圖4-9所示。圖4-9例4-4求解步驟1的結(jié)果

步驟2:(1,2)選作最小支撐樹上的邊,令E(T)=E(T)∪emin={(1,2)},E=E-{(1,2)},剩下圖中的最小邊為圖4-10例4-4求解步驟2的結(jié)果

步驟3:(6,4)選作最小支撐樹上的邊,令E(T)=E(T)∪emin

={(1,2),(6,4)},E=E-{(6,4)},剩下圖中的最小邊為

如圖4-11所示。圖4-11例4-4求解步驟3的結(jié)果

步驟4:(2,4)選作最小支撐樹上的邊,令E(T)=E(T)∪emin

={(1,2),(6,4),(2,4)},E=E-{(2,4)},剩下圖中的最小邊有三條,emin

=(2,3)、(2,5)、(4,3),如圖4-12所示。圖4-12例4-4求解步驟4的結(jié)果

步驟5:可以任選一條最小邊加入E(T),如(2,3)。令E(T)=E(T)∪emin={(1,2),(6,4),(2,4),(2,3)},E=E-{(2,3)},剩下圖中的最小邊有兩條,emin=(2,5)、(4,3),如圖4-13所示。圖4-13例4-4求解步驟5的結(jié)果

步驟6:可以任選一條最小邊加入E(T),如(2,5)。令E(T)=E(T)∪emin

={(1,2),(6,4),(2,4),(2,3),(2,5)},E=E-{(2,5)},剩下圖中的最小邊為emin

=(4,3),如圖4-14所示。圖4-14-例4-4求解步驟6的結(jié)果

步驟7:此時(shí),E(T)中已經(jīng)有5條邊滿足支撐樹點(diǎn)數(shù)和邊數(shù)的關(guān)系,算法停止?？梢钥吹?此時(shí),若再加入任意邊,都會(huì)產(chǎn)生圈。

算法的步驟可以總結(jié)為口訣:“一邊一邊地連,先連最小邊,不能產(chǎn)生圈”。

3.破圈法

破圈法是指利用Cycle屬性,逐步去掉圈上的最大邊,最終得到最小支撐樹。其步驟總結(jié)為口訣:“一圈一圈地破,破掉圈上最大邊”。

對(duì)于連通圖G=(V,E),破圈法的步驟總結(jié)如下:

4.1.4-拓展應(yīng)用:k－聚類分析

聚類就是一種尋找數(shù)據(jù)之間一種內(nèi)在結(jié)構(gòu)的技術(shù)。聚類把全體數(shù)據(jù)實(shí)例組織成不同的組,處于相同分組中的數(shù)據(jù)實(shí)例彼此相近,處于不同分組中的實(shí)例彼此相遠(yuǎn)。對(duì)一個(gè)集合

V={v1,v2,…,vn}中的對(duì)象,在已知對(duì)象之間差異性度量的情況下,將其分為由類似的對(duì)象組成的多個(gè)類Vi的過程,稱為聚類分析,其中

使用最小支撐樹進(jìn)行k－聚類分析的步驟如下:

步驟1:將聚類的對(duì)象集合V看作圖G=(V,E)的點(diǎn)集,將對(duì)象之間的差異性dij作為點(diǎn)之間邊(i,j)∈E的權(quán)重。

步驟2:求解G的最小支撐樹T=(V,E')。

步驟3:去掉T上的k-1條最大邊,得到k個(gè)相互不連通的連通子圖Gi=(Vi,Ei

')i=1,…,k,則Vi是第i類的點(diǎn)集合。

例4-5某電子企業(yè)需要在10臺(tái)機(jī)器上生產(chǎn)15種電子零件。企業(yè)準(zhǔn)備將機(jī)器分成若干組,使零件在不同機(jī)器上生產(chǎn)的“差異”最小。零件i在機(jī)器j上生產(chǎn)的“差異”定義為

其中,nij表示機(jī)器i和機(jī)器j上都可以生產(chǎn)的零件數(shù)量;mij表示只能在機(jī)器i和機(jī)器j其中之一生產(chǎn)的零件數(shù)量。根據(jù)表4-1給出的數(shù)據(jù),求將機(jī)器分成兩組和三組的解。

步驟1:將不同機(jī)器生產(chǎn)的零件按照表4-1所示的對(duì)應(yīng)關(guān)系輸入Matlab的cell結(jié)構(gòu)變量中,可以得到:

步驟2:按照差異的定義,計(jì)算dij:

步驟3:將d作為鄰接矩陣,求解圖的最小支撐樹:

結(jié)果如圖4-15所示。

圖4-15機(jī)器差異性最小支撐樹

步驟4:若要將機(jī)器分成2組,則去掉最小支撐樹上的一條最大邊就可以達(dá)到目的(見圖4-16(a)),若要將機(jī)器分成3組,再去掉一條最大邊即可(見圖4-16(b)),以此類推。圖4-16利用最小支撐樹對(duì)圖上的點(diǎn)進(jìn)行2－聚類和3－聚類

4.1.5拓展應(yīng)用:戰(zhàn)備通信節(jié)點(diǎn)的建設(shè)問題

1.問題描述

構(gòu)建將N個(gè)城市作為節(jié)點(diǎn)的有線通信網(wǎng)絡(luò),在每個(gè)城市內(nèi)設(shè)置一架專用網(wǎng)絡(luò)連接設(shè)備,請(qǐng)?jiān)O(shè)計(jì)通信網(wǎng)絡(luò)的最經(jīng)濟(jì)連接方案。同時(shí),為了增加抗毀性,可以在N個(gè)城市之外的地方構(gòu)建一定數(shù)量的戰(zhàn)備節(jié)點(diǎn),戰(zhàn)備節(jié)點(diǎn)平時(shí)不工作,當(dāng)出現(xiàn)應(yīng)急突發(fā)情況、通信網(wǎng)絡(luò)中斷時(shí),可以啟用戰(zhàn)備節(jié)點(diǎn),迅速地恢復(fù)通信網(wǎng)絡(luò)的連通性,請(qǐng)?jiān)O(shè)計(jì)戰(zhàn)備節(jié)點(diǎn)的建設(shè)方案。設(shè)計(jì)時(shí)應(yīng)充分考慮經(jīng)濟(jì)性和抗毀性。經(jīng)濟(jì)性是指要考慮節(jié)省網(wǎng)絡(luò)連接的總費(fèi)用,而抗毀性是指要提高網(wǎng)絡(luò)在節(jié)點(diǎn)故障的情況下仍然保持連通的能力。

現(xiàn)已知138個(gè)城市(見圖4-17)建設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)的選址的經(jīng)緯度坐標(biāo),請(qǐng)為通信網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)提供優(yōu)化方法。圖4-17需要建立通信網(wǎng)絡(luò)連接的138個(gè)節(jié)點(diǎn)分布

2.問題分析

若只考慮經(jīng)濟(jì)性指標(biāo),這是一個(gè)網(wǎng)絡(luò)最優(yōu)化決策中的最小支撐樹問題(參見4.1節(jié)),輸入是點(diǎn)以及點(diǎn)之間的連接費(fèi)用。給定的N個(gè)城市作為網(wǎng)絡(luò)上的點(diǎn),點(diǎn)之間的通信連接費(fèi)用可以用點(diǎn)之間的通信連接長(zhǎng)度來代替。

3.最經(jīng)濟(jì)的連通方案

根據(jù)已知通信網(wǎng)絡(luò)節(jié)點(diǎn)的選址經(jīng)緯度坐標(biāo),可以計(jì)算相互之間的距離,這是一種簡(jiǎn)要的代替節(jié)點(diǎn)之間通信連接建設(shè)費(fèi)用的方法。然后利用網(wǎng)絡(luò)最優(yōu)化中的最小支撐樹求解算

法,求解通信線路總長(zhǎng)度最短的建設(shè)方案。假設(shè)將N個(gè)城市的經(jīng)緯度坐標(biāo)(度)存儲(chǔ)到N×2維變量Cord中,其第一列存儲(chǔ)的是點(diǎn)的緯度信息,第二列存儲(chǔ)的是經(jīng)度信息,共有N行,每行對(duì)應(yīng)一個(gè)城市選址點(diǎn),可得到:

求得的以距離度量的最經(jīng)濟(jì)的通信線路建設(shè)方案如圖4-18所示。

圖4-18以距離度量的最經(jīng)濟(jì)的通信線路建設(shè)方案

4.最經(jīng)濟(jì)的恢復(fù)方案

預(yù)備建設(shè)戰(zhàn)備節(jié)點(diǎn)的集合為Nb,使通信節(jié)點(diǎn)Nd?V被破壞的情景下,網(wǎng)絡(luò)G'=(V-Nd

,E-E(Nd

)),可以對(duì)網(wǎng)絡(luò)進(jìn)行連通性分析

例如,去掉第53、56和105個(gè)城市之后,網(wǎng)絡(luò)分成相互不連通的4個(gè)部分,如圖4-19所示。Matlab代碼如下:

圖4-19破壞掉3個(gè)節(jié)點(diǎn)后,通信網(wǎng)絡(luò)分成4個(gè)獨(dú)立的部分

4.2最短路問題4.2.1線性規(guī)劃模型在網(wǎng)絡(luò)G=(V,E)中,邊(i,j)∈E的權(quán)值(長(zhǎng)度、時(shí)間、費(fèi)用等的抽象)為cij,尋找從起點(diǎn)s∈V到終點(diǎn)t∈V的最短路P,就稱為最短路問題。目標(biāo)函數(shù)是位于最短路上的邊的總長(zhǎng)度最短,即其中,xij∈{0,1}是決策變量,xij=1代表邊(i,j

)是最短路上的邊,否則不是。

約束條件是,對(duì)于起點(diǎn)s來講

對(duì)于終點(diǎn)t來講

對(duì)于網(wǎng)絡(luò)中的其他