第1章運籌學概述1.1

運籌學的起源1.2運籌學的定義1.3運籌學的模型1.4運籌學的優化范式1.5運籌學應用的過程

1.1

運籌學的起源

運籌學起源于軍事問題的研究。第二次世界大戰初期,英國人為了將最新的雷達技術整合進英國空軍戰術,開始了相關研究,并稱之為OperationalResearch。最初,OperationalResearch的主要工作就是收集經驗數據并進行基礎的統計分析,也有一些工作應用了較為復雜的數學方法,如搜索理論。

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

軍官籌劃作戰策略和作戰行動而進行的研究,目標是通過量化分析技術最有效地利用有限的軍事資源。第二次世界大戰之后,OperationalResearch變成一種專業,并且更加關注和聚焦于復雜的數學方法。

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

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

1938年,Bawdsey研究站又增加部署了四部雷達,并進行了第二次實驗。

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

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

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

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

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

第二次世界大戰剛結束時,許多科學家認識到他們用于解決軍事問題的原則同樣適用于民用部門,于是運籌學在民用領域迅速發展起來,同時運籌學在軍事領域的發展也在持

續。

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

1.2運籌學的定義

1951年,莫爾斯和金博爾出版的《運籌學方法》一書中將運籌學定義為:運籌學是在實行管理的領域,運用數學方法,對需要進行管理的問題統籌規劃,做出決策的一門應用科學。美國運籌學會給出的定義為:運籌學關注的是,在需要考慮稀缺資源分配的條件下,研究最優設計的決策問題,研究人機系統的運用問題。

英國運籌學會給出的定義為:運籌學應用科學的方法解決工業、商業、政府和國防等領域大系統的指導與管理方面的問題,指導和管理的對象包括人員、機器、材料、資金等。

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

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

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

圖1-1-OODA環模型

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

1.3運籌學的模型

1.3.1-線性規劃模型數學規劃模型包含決策變量、目標函數、約束條件等三類必要元素。決策變量是決策要素的變量化定義;利用決策變量表達問題目標的函數就是目標函數;利用決策變量表達問題約束的等式或者不等式就是約束條件。

1.3.2網絡模型

網絡模型包含點和邊兩類必要元素。點代表問題中的對象,邊代表問題中對象之間的關系。以網絡模型為基礎,可以研究很多網路優化問題,如最小支撐樹問題、最短路問題、最大流問題、最小費用流問題等。1956年福特和福克遜提出了網絡最大流問題的標號法,建立了網絡流理論。

1.3.3動態規劃模型

動態規劃是一種算法設計技術,也是一種解決優化問題的模型及算法構造方法。它以遞歸的方式將一個復雜的問題分解成一系列簡單的子問題,并通過子問題序列化的求解得

到問題的最優方案。動態規劃模型包含狀態、狀態轉移等兩類基本要素,可以看作是一種具有階段性的特殊的網絡模型。

1.3.4生滅過程模型

生滅過程模型的基本要素包括狀態和狀態轉移,狀態代表排隊系統中的顧客的數量,狀態轉移代表排隊系統中顧客數量的變化,也就是系統狀態的變化。生滅過程模型以計算

系統處于各個狀態的概率為中介,結合排隊系統的Little公式,可以得到排隊系統的平均隊長、期望等待時間等各項參數,進而為排隊系統的優化提供支持。

1.3.5神經網絡模型

神經網絡模型是一種基于網絡模型的計算模型,計算的數據從輸入層開始往后流動,主要通過模擬生物的神經網絡進行模式識別,相當于OODA環中的“判斷”。

。傳統上,優化決策的步驟可分為問題定義、建立模型、設計算法、求解并檢驗驗證等環節,人工參與是全程和深入的,對人的建模求解能力和技術要求高。基于人工智能的優化決策技術,讓機器可以在有監督或者無監督的情況下學習,無須人類的參與,甚至無須人類經驗的加入,就能做出優化的決策。

1.3.6啟發式模型

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

從而開啟了進化計算的時代。

1.3.7仿真模型

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

仿真模型非常強大,并且它有一個非常可取的特性:將其用于非常復雜的系統建模時,不需要做太多的簡化假設,也不需要犧牲過多細節。然而,使用仿真模型時必須非常小心,避免誤用仿真。首先,在使用模型之前,必須對其進行適當的驗證。驗證對于任何模型來說都是必要的,對于仿真尤為重要。其次,分析人員必須熟悉如何正確使用仿真模型,包括復制、運行時間等。再次,為了有意義地分析仿真輸出,分析人員必須熟悉各種統計技術。最后,在計算機上構建復雜的仿真模型是一項具有挑戰性和相對耗時的任務,分析人員必須具有耐心。這里強調這些問題的原因是,現代仿真模型種類繁多,其真正的價值在于它能夠洞察非常復雜的問題。

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

1.4運籌學的優化范式

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

圖1-2運籌學的五大優化范式

1.4.1-樸素優化范式

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

1.4.2機械優化范式

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

1.4.3仿真優化范式

仿真優化范式是基于計算機仿真技術和平臺的優化方法,可充分利用仿真對復雜系統的強大描述和承載能力,為優化提供動態、復雜結構的數據輸入能力,并能夠對隨機性提供天然支持。

1.4.4智能優化范式

智能優化范式通過智能算法借鑒了智能體的進化優化過程,比較容易理解,能夠解決的問題也是廣譜的,但是針對具體的問題需要更多的專業知識,才能對算法的編碼、解的進化、參數的調整等技術細節進行良好的控制和優化。

1.4.5數據驅動優化范式

數據驅動優化范式是優化決策與大數據技術相結合的產物,它將數據作為驅動優化決策的直接動力,解決了傳統優化決策領域理論和實踐脫節的問題。傳統的優化決策方法都

是先對真實系統進行選擇性的抽象,建立實際上失真的模型,然后對模型進行優化,將對模型進行優化的結果作為對真實系統優化決策的替代物。然而數據驅動優化范式的模型本

身始終與真實系統保持聯系,真實系統的數據源源不斷地輸入模型中,使模型的失真度達到最小,從而保證了優化決策的準確度。

1.5運籌學應用的過程

運籌學不僅僅是數學工具的集合。運籌學也不僅僅是模型方法的集合,而更應該是一個完整的、系統的過程。運籌學研究的最終目的是對所分析的問題實施解決方案,因此保持問題驅動的焦點是至關重要的。運籌學實踐者經常要面對的是對系統化解決方案的需求,要面對的是對問題全系統全壽命的考驗。現實中的太多病態定義、非標準化結構的問題,往往需要運籌學實踐者自己提煉和解決。

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

圖1-3運籌學的應用過程

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

其中,系數a和b如表1-1所示。

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

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

1.5.1-定位

“定位”的主要目標是組成一個小組,并確保其所有成員對有關問題有一個清楚的了解。通常,團隊由一個領導者和來自不同職能領域或部門的成員組成。

1.5.2問題定義

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

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

第二個是對影響目標的因素的規范。

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

1.5.3數據收集

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

1.5.4模型構建

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

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

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

如果我們的目標是使六個防線上的持續時間之和達到最大,則目標函數可以表示為以下形式: