戰(zhàn)爭(zhēng)中的運(yùn)籌學(xué)

1、1,,運(yùn)籌學(xué)(Operation Research) MBA學(xué)位課程,衷心希望本課程能讓大家受益,,2,教師介紹 姓 名： 劉滿鳳 職 稱： 教授 博士 單 位： 江西財(cái)經(jīng)大學(xué)科研處 副處長(zhǎng) 電 話： 3823072（O） 3816926（H)，13627086942 E-mail: liumanfeng@sina.com.cn,3,課程內(nèi)容簡(jiǎn)介與學(xué)習(xí)要求,,課程內(nèi)容簡(jiǎn)介,運(yùn)籌學(xué)是一門應(yīng)

2、用性學(xué)科，它主要是應(yīng)用定性分析和定量分析相結(jié)合的方法，通過(guò)建立實(shí)際問(wèn)題的數(shù)學(xué)模型，應(yīng)用合適的優(yōu)化算法對(duì)模型進(jìn)行求解，從而解決實(shí)際問(wèn)題。,其主要內(nèi)容有：線性規(guī)劃、運(yùn)輸模型、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃、圖與網(wǎng)絡(luò)分析、排隊(duì)論、存貯論、對(duì)策論、決策論、等。,學(xué)習(xí)要求,本課程將通過(guò)重點(diǎn)講授原理方法、上機(jī)解題、個(gè)人研究與小組討論相結(jié)合的案例分析等環(huán)節(jié)，培養(yǎng)學(xué)員全局優(yōu)化的思想，使學(xué)員掌握若干類常用的運(yùn)籌學(xué)模型，并能用其解決經(jīng)濟(jì)管理中的復(fù)雜問(wèn)題。 因此要

3、求學(xué)員：對(duì)布置的思考、案例討論題進(jìn)行認(rèn)真準(zhǔn)備，按進(jìn)度完成平時(shí)作業(yè)和上機(jī)練習(xí)，按要求完成大作業(yè)書(shū)面報(bào)告。,參考資料,（1）劉滿鳳、付波、聶高飛編著《運(yùn)籌學(xué)模型與方法教程例題分析與題解》，清華大學(xué)出版社，2001年。（2）《運(yùn)籌學(xué)》教材編寫組編《運(yùn)籌學(xué)》（修訂版），清華大學(xué)出版社，1996年。（3）Dimitris Bertsimas, Robert M.Freund,《數(shù)據(jù)、模型與決策》,中信出版社，2004。（4）弗雷德里克.S.

4、希利爾,馬克.S.希利爾,《數(shù)據(jù)、模型與決策》，中國(guó)財(cái)政經(jīng)濟(jì)出版社。2004（5）胡運(yùn)權(quán)主編《運(yùn)籌學(xué)》（修訂版），清華大學(xué)出版社，2002年（6）Frederick S. Hillier《Introduction to Operations Research》，機(jī)械工業(yè)出版社，1999,4,本課程內(nèi)容安派：,第一部分 線性規(guī)劃及其應(yīng)用,,第三部分 動(dòng)態(tài)規(guī)劃,1、動(dòng)態(tài)規(guī)劃的基本概念和最優(yōu)化原理2、動(dòng)態(tài)規(guī)劃模型的建立和求解方法

5、3、建模訓(xùn)練與求解,,第四部分 對(duì)策論模型,第五部分 決策論,1、兩人有限零和對(duì)策模型及其解法2、兩人有限非零和對(duì)策,1、圖與網(wǎng)絡(luò)的基本概念2、最短路問(wèn)題3、最大流問(wèn)題4、最小費(fèi)用最大流問(wèn)題5、關(guān)鍵路線（CPM）與計(jì)劃評(píng)審法（PERT）,第二部分 整數(shù)規(guī)劃及其應(yīng)用,1、整數(shù)規(guī)劃的數(shù)學(xué)模型及其特點(diǎn)2、分枝定界法3、0-1規(guī)劃的解法4、指派問(wèn)題的解法,1、問(wèn)題的數(shù)學(xué)模型與求解2、單純形法與計(jì)算機(jī)求解3、對(duì)偶

6、理論與靈敏度分析4、運(yùn)輸問(wèn)題及其解法,第六部分 圖與網(wǎng)絡(luò)分析,1、決策問(wèn)題的基本概念2、決策問(wèn)題的基本方法3、信息分析,5,第一章 緒 論,1.1 運(yùn)籌學(xué)的定義1.2 運(yùn)籌學(xué)的工作步驟 1.3 運(yùn)籌學(xué)的模型 1.4 運(yùn)籌學(xué)的發(fā)展簡(jiǎn)史,6,1.1 運(yùn) 籌 學(xué) 定 義（Operations Research OR） 由于運(yùn)籌學(xué)研究的廣泛性和復(fù)雜性，人們至今沒(méi)有形成一個(gè)統(tǒng)一的定義。以下

7、給出二種有代表性定義： 運(yùn)籌學(xué)是依據(jù)給定目標(biāo)和條件從眾多方案中選擇最優(yōu)方案的最優(yōu)化技術(shù)。 運(yùn)籌學(xué)是一門尋求在給定資源條件下，如何設(shè)計(jì)和運(yùn)行一個(gè)系統(tǒng)的科學(xué)決策的方法,7,1.2 運(yùn)籌學(xué)的工作步驟,運(yùn)籌學(xué)在解決大量實(shí)際問(wèn)題的過(guò)程中形成了自己的工作步驟：1.提出和形成問(wèn)題：即要弄清問(wèn)題的目標(biāo)，可能的約束，問(wèn)題的可控變量以及有關(guān)參數(shù)，搜集有關(guān)資料。2.建立模型：即把問(wèn)題中可控變量、參數(shù)和目標(biāo)與約束之間的關(guān)系用一定的模型表示出來(lái)。

8、3.求解：用各種手段(主要是數(shù)學(xué)方法，也可用其它方法)將模型求解。解可以是最優(yōu)解、次優(yōu)解、滿意解。復(fù)雜模型的求解需用計(jì)算機(jī),解的精度要求由決策者提出。,8,4.解的檢驗(yàn)：首先檢驗(yàn)求解步驟和程序有無(wú)錯(cuò)誤，然后檢查解是否反映現(xiàn)實(shí)問(wèn)題。5.解的控制：通過(guò)控制解的變化過(guò)程決定對(duì)解是否要作一定的修改。6.解的實(shí)施：是指將解用到實(shí)際中去，必須考慮到實(shí)際的問(wèn)題，如向?qū)嶋H部門講清楚解的用法，在實(shí)施中可能產(chǎn)生的問(wèn)題等。 以上過(guò)程應(yīng)反復(fù)進(jìn)

9、行。,9,真實(shí)系統(tǒng),系統(tǒng)分析問(wèn)題描述,模型建立與修改,模型求解與檢驗(yàn),結(jié)果分析與實(shí)施,數(shù)據(jù)準(zhǔn)備,,,,,,,,,,,,運(yùn)籌學(xué)工作的步驟,10,1.3 運(yùn)籌學(xué)模型 運(yùn)籌學(xué)研究的模型主要是抽象模型——數(shù)學(xué)模型。數(shù)學(xué)模型的基本特點(diǎn)是用一些數(shù)學(xué)關(guān)系（數(shù)學(xué)方程、邏輯關(guān)系等）來(lái)描述被研究對(duì)象的實(shí)際關(guān)系（技術(shù)關(guān)系、物理定律、外部環(huán)境等）。,11,運(yùn)籌學(xué)模型的一個(gè)顯著特點(diǎn)是它們大部分為最優(yōu)化模型。一般來(lái)說(shuō)，運(yùn)籌學(xué)模型都有一個(gè)目標(biāo)函數(shù)和

10、一系列的約束條件，模型的目標(biāo)是在滿足約束條件的前提下使目標(biāo)函數(shù)最大化或最小化。,12,1.4 運(yùn)籌學(xué)的發(fā)展簡(jiǎn)史 1、樸素的運(yùn)籌思想：都江堰水利工程戰(zhàn)國(guó)時(shí)期（大約公元前250年）川西太守李冰父子主持修建。其目標(biāo)是：利用岷江上游的水資源灌溉川西平原。追求的效益有防洪與航運(yùn)。其總體構(gòu)思是系統(tǒng)思想的杰出運(yùn)用。,13,都江堰由三大工程及120多項(xiàng)配套工程組成：1.“魚(yú)嘴”岷江分水工程：將岷江水有控制地引入內(nèi)江。2.“飛沙堰”分洪

11、排沙工程：將泥沙排入外江。3.“寶瓶口”引水工程：除沙后的江水引入水網(wǎng)干道。,14,它們巧妙結(jié)合，完整而嚴(yán)密，相得益彰。兩千多年來(lái)，這項(xiàng)工程一直發(fā)揮著巨大的效益，是我國(guó)最成功的水利工程。,都江堰水利工程,15,丁謂的皇宮修復(fù)工程 北宋年間，丁謂負(fù)責(zé)修復(fù)火毀的開(kāi)封皇宮。他的施工方案是：先將皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。使用挖出的土就地制磚，令與汴水相連形成的河道承擔(dān)繁重的運(yùn)輸任務(wù)；修復(fù)工程完成后，實(shí)施大溝

12、排水，并將原廢墟物回填，修復(fù)成原來(lái)的大街。丁謂將取材、運(yùn)輸及清廢用“一溝三用”巧妙地解決了，體現(xiàn)了系統(tǒng)規(guī)劃的思想。,16,田忌賽馬齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對(duì)局三次，每次勝負(fù)1000金。田忌在好友、著名的軍事謀略家孫臏的指導(dǎo)下，以以下安排：齊王上中下田忌下上中最終凈勝一局，贏得1000金。,,,,,17,2、早期的軍事運(yùn)籌學(xué)特拉法加爾（Trafalgar）海戰(zhàn)和納爾森（Nelson）秘訣

13、 19世紀(jì)中葉，法國(guó)拿破倫統(tǒng)帥大軍要與英國(guó)爭(zhēng)奪海上霸主地位，而實(shí)施這一戰(zhàn)略的最主要的關(guān)鍵是消滅英國(guó)的艦隊(duì)。英國(guó)海軍統(tǒng)帥、海軍中將納爾森親自制定了周密的戰(zhàn)術(shù)方案。,18,1805年10月21日，這場(chǎng)海上大戰(zhàn)爆發(fā)了。英國(guó)是納爾森親自統(tǒng)帥的地中海艦隊(duì)，由27艘戰(zhàn)艦組成；另外一方是由費(fèi)倫紐夫（Villenuve）率領(lǐng)的法國(guó)——西班牙聯(lián)合艦隊(duì)，共有33艘戰(zhàn)艦。Trafalgar大海戰(zhàn)的概況是：費(fèi)倫紐夫（Villenuve）率領(lǐng)的法國(guó)——

14、西班牙聯(lián)合艦隊(duì)采用常規(guī)的一字橫列，以利炮火充分展開(kāi)，而納爾森的戰(zhàn)術(shù)使費(fèi)倫紐夫大出意外。,19,英國(guó)的艦隊(duì)分成兩個(gè)縱列：前衛(wèi)上風(fēng)縱列由12艘戰(zhàn)艦組成，由納爾森親自指揮，攔腰將法國(guó)——西班牙聯(lián)合艦隊(duì)切為兩段；后衛(wèi)下風(fēng)縱列由英國(guó)海軍中將科林伍德(Collingwood)指揮，由15艘戰(zhàn)艦組成。在一場(chǎng)海戰(zhàn)后，法國(guó)——西班牙聯(lián)合艦隊(duì)以慘敗告終：聯(lián)合艦隊(duì)司令費(fèi)倫紐夫連同12艘戰(zhàn)艦被俘，8艘沉沒(méi)，僅13艘逃走，人員傷亡7000人。而英國(guó)戰(zhàn)艦沒(méi)有沉沒(méi)，

15、人員傷亡1663人，但是，作為統(tǒng)帥的納爾森陣亡。,20,秘密備忘錄中的納爾森（Nelson）秘訣：預(yù)期參加戰(zhàn)斗的英國(guó)艦隊(duì)：40艘。法國(guó)—西班牙聯(lián)合艦隊(duì)：46艘。預(yù)計(jì)聯(lián)合艦隊(duì)?wèi)?zhàn)斗隊(duì)形一字橫列。英國(guó)艦隊(duì)的戰(zhàn)斗隊(duì)形與任務(wù)：分成兩個(gè)主縱列及一個(gè)小縱列。,21,22,主縱列1：16艘，由納爾森親自指揮，攔腰將法國(guó)——西班牙聯(lián)合艦隊(duì)切為兩段，并攻擊聯(lián)合艦隊(duì)的中間部分。主縱列2：16艘，由英國(guó)海軍中將科林伍德指揮，從聯(lián)合艦隊(duì)后半部再切斷，分

16、割并攻擊后部12艘。小縱列：8艘，在中心部分附近攻擊其先頭部分的3-4艘。,23,蘭徹斯特（F.W.Lanchester）作戰(zhàn)分析 蘭徹斯特方程：設(shè)兩軍對(duì)抗中一方有x 個(gè)戰(zhàn)斗單位（戰(zhàn)艦、戰(zhàn)車、戰(zhàn)機(jī)、步兵單位等），另外一方有y個(gè)戰(zhàn)斗單位?；炯僭O(shè)：每一方戰(zhàn)斗單位的損失率與對(duì)方戰(zhàn)斗單位的數(shù)量成正比。,24,于是，雙方戰(zhàn)斗損失的微分方程為：dy/dt= - ax, dx/dt= - by.其中， a&g

17、t;0與b>0 表示雙方的平均戰(zhàn)斗力。因此可以得到： ax2=by2上式稱為蘭徹斯特N2定律。,25,用蘭徹斯特N2定律可以對(duì)“納爾森（Nelson）秘訣”進(jìn)行分析：整體戰(zhàn)斗實(shí)力。設(shè)雙方單個(gè)戰(zhàn)斗單位的戰(zhàn)斗力相同，則有：英國(guó)艦隊(duì)：402=1600聯(lián)合艦隊(duì)：462=2116此時(shí)聯(lián)合艦隊(duì)占優(yōu)勢(shì)，設(shè)想聯(lián)合艦隊(duì)全殲英國(guó)艦隊(duì)后，聯(lián)合艦隊(duì)還有5161/2=23艘。,26,將聯(lián)合艦隊(duì)攔腰切斷，23+23=46，是將聯(lián)合艦隊(duì)實(shí)力減

18、弱的最小分割法。此時(shí)，聯(lián)合艦隊(duì)的實(shí)力為：232+232=1058而英國(guó)艦隊(duì)的實(shí)力為：（16+16）2+82=1088，已略占有優(yōu)勢(shì)。,27,在英國(guó)艦隊(duì)兩個(gè)主縱列共32艘，攻擊聯(lián)合艦隊(duì)的后一半23艘，此時(shí)，英國(guó)艦隊(duì)實(shí)力：（16+16）2=322=1064聯(lián)合艦隊(duì)的實(shí)力為： 232 =529,28,英國(guó)艦隊(duì)已占有優(yōu)勢(shì)。在全殲聯(lián)合艦隊(duì)后部后，英國(guó)艦隊(duì)兩個(gè)主縱列還可以保留：（1064-529）

19、1/2 =5161/2=23艘，再與小縱列中艦隊(duì)聯(lián)合對(duì)聯(lián)合艦隊(duì)前部作戰(zhàn)還占有優(yōu)勢(shì)。即在最壞情況下，“納爾森（Nelson）秘訣”也可以使英國(guó)艦隊(duì)獲得勝利。,29,鮑德西（Bawdsey）雷達(dá)站的研究（1935年） 1935年，英國(guó)科學(xué)家R.Watson-Wart發(fā)明了雷達(dá)。丘吉爾命令在英國(guó)東海岸的Bawdsey建立了一個(gè)秘密雷達(dá)站。當(dāng)時(shí)，德國(guó)已擁有一支強(qiáng)大的空軍，起飛17分鐘即到達(dá)英國(guó)本土。在如此短的時(shí)間內(nèi)，如何預(yù)警和攔截成為

20、一大難題。,30,1939年由曼徹斯特大學(xué)物理學(xué)家、英國(guó)戰(zhàn)斗機(jī)司令部顧問(wèn)、戰(zhàn)后獲得諾貝爾獎(jiǎng)金的P.M.S.Blackett為首，組織了一個(gè)小組，代號(hào)“Blackett馬戲團(tuán)”。這個(gè)小組包括三名心理學(xué)家、一名理論數(shù)學(xué)家、兩名應(yīng)用數(shù)學(xué)家、一名天文物理學(xué)家、一名普通物理學(xué)家、一名海軍軍官、一名陸軍軍官、一名測(cè)量員。,31,研究的問(wèn)題是：設(shè)計(jì)將雷達(dá)信息傳送到指揮系統(tǒng)和武器系統(tǒng)的最佳方式；雷達(dá)與武器的最佳配置；對(duì)探測(cè)、信息傳遞、作戰(zhàn)指揮、戰(zhàn)斗機(jī)與

21、武器的協(xié)調(diào)，作了系統(tǒng)的研究，并獲得成功?！癇lackett馬戲團(tuán)”在秘密報(bào)告中使用了“Operational Research”，即“運(yùn)籌學(xué)”。,32,大西洋反潛戰(zhàn)（1942年） 1942年，美國(guó)大西洋艦隊(duì)反潛戰(zhàn)官員W.D.BAKER艦長(zhǎng)請(qǐng)求成立反潛戰(zhàn)運(yùn)籌組，麻省理工學(xué)院的物理學(xué)家P.W.MORSE被請(qǐng)來(lái)?yè)?dān)任計(jì)劃與監(jiān)督。,33,MORSE 出色的工作之一，是協(xié)助英國(guó)打破了德國(guó)對(duì)英吉利海峽的封鎖。1941-1942年，德國(guó)潛艇

22、嚴(yán)密封鎖了英吉利海峽，企圖切斷英國(guó)的“生命線”。海軍幾次反封鎖，均不成功。,34,應(yīng)英國(guó)要求，美國(guó)派MORSE率領(lǐng)一個(gè)小組去協(xié)助。MORSE經(jīng)過(guò)多方實(shí)地考察，最后提出了兩條重要建議：將反潛攻擊由反潛潛艇投擲水雷，改為飛機(jī)投擲深水炸彈。起爆深度由100米左右改為25米左右。即當(dāng)潛艇剛下潛時(shí)攻擊效果最佳。(提高效率4-7倍),35,運(yùn)送物資的船隊(duì)及護(hù)航艦隊(duì)編隊(duì)，由小規(guī)模多批次，改為加大規(guī)模、減少批次，這樣，損失率將減少。（25%下降到10

23、%） 丘吉爾采納了MORSE的建議，最終成功地打破封鎖，并重創(chuàng)了德國(guó)潛艇。MORSE同時(shí)獲得英國(guó)和美國(guó)的最高勛章。,36,戰(zhàn)略核武器殺傷力模型 美國(guó)和蘇聯(lián)從六十年代起就展開(kāi)了激烈的核武器競(jìng)爭(zhēng)。六十年代初期，蘇聯(lián)主張武器往大型化方向發(fā)展，其理由是武器的威力越大，殺傷力越強(qiáng)。但美國(guó)有人認(rèn)為：雖然武器的威力越大，殺傷力越強(qiáng)，但武器殺傷力不全取決威力，還與準(zhǔn)確度有關(guān)，如果武,37,器的威力大而準(zhǔn)確度低，

24、其殺傷力未必就大。反之，雖然威力小但準(zhǔn)確度高，殺傷力也可能大。殺傷力K不僅與威力Y有關(guān)，而且與精度C有關(guān)。經(jīng)過(guò)大量的模擬試驗(yàn)，將有關(guān)數(shù)據(jù)經(jīng)過(guò)處理和分析，利用蒙特卡洛擬合而得K、Y、C的函數(shù)關(guān)系： K=Y2/3/C2,38,由這個(gè)模型，容易得當(dāng)Y*=8Y時(shí)，K*=4K，即威力提高8倍，殺傷力僅提高4倍。當(dāng)C*=C/8時(shí)，K*=64K，即精度提高8倍，殺傷力可以提高64倍。這說(shuō)明提高精度合理，因

25、而美國(guó)走提高武器精度的道路。,39,海灣戰(zhàn)爭(zhēng)中的作戰(zhàn)模擬（1990年8月）《The Commanders》一書(shū)描述了美國(guó)最高當(dāng)局如何策劃入侵巴拿馬和如何策劃海灣戰(zhàn)爭(zhēng)，書(shū)中透露美國(guó)國(guó)防部長(zhǎng)切尼在海灣戰(zhàn)爭(zhēng)準(zhǔn)備階段曾因拿不準(zhǔn)美國(guó)在這場(chǎng)戰(zhàn)爭(zhēng)付出多大代價(jià)和費(fèi)用而困擾。,40,在海灣戰(zhàn)爭(zhēng)爆發(fā)前，美國(guó)采用CEM“作戰(zhàn)方案評(píng)價(jià)模型”和相關(guān)的支持模型制訂戰(zhàn)爭(zhēng)計(jì)劃。CEM由美國(guó)研究分析公司（RAC）與陸軍概念分析局在1980年合作開(kāi)發(fā)，應(yīng)用于北大西洋公

26、約組織與華沙條約集團(tuán)之間的戰(zhàn)區(qū)級(jí)戰(zhàn)役仿真。CEM的特征：全自主運(yùn)行，確定型，裝甲旅級(jí)戰(zhàn)斗分辨率。,41,過(guò)程由戰(zhàn)區(qū)司令官?zèng)Q策控制，新一輪仿真準(zhǔn)備時(shí)間為數(shù)月，在CRAYII巨型計(jì)算機(jī)上運(yùn)行一次仿真時(shí)間不超過(guò)2小時(shí)。1990年8月，美國(guó)陸軍概念分析局用CEM為“沙漠盾牌”行動(dòng)提供分析支持，包括戰(zhàn)略步驟，部隊(duì)、人力、彈藥需求，以及評(píng)估防空與戰(zhàn)區(qū)導(dǎo)彈防御和聯(lián)軍的潛力。,42,從1990年8 月中旬到地面戰(zhàn)爭(zhēng)結(jié)束，CEM共運(yùn)行了500個(gè)回合。美

27、軍投入“沙漠盾牌”和“沙漠風(fēng)暴”行動(dòng)應(yīng)用另一計(jì)算機(jī)仿真模型為C3I SIM 模型，它為美軍空中行動(dòng)提供頭24小時(shí)的損耗分析。,43,1991年12月9日-11日，在美國(guó)海軍分析中心支持了美國(guó)軍事運(yùn)籌學(xué)會(huì)“分析海灣戰(zhàn)爭(zhēng)教訓(xùn)的研討會(huì)”。美國(guó)軍事運(yùn)籌學(xué)會(huì)主席 Vernon M.Bettencourt.JR指出：海灣戰(zhàn)爭(zhēng)的遺產(chǎn)，將繼續(xù)對(duì)國(guó)防系統(tǒng)分析和美國(guó)軍事運(yùn)籌學(xué)會(huì)的活動(dòng)產(chǎn)生影響。,44,國(guó)防系統(tǒng)分析模型如何表達(dá)直接影響戰(zhàn)斗力的電子戰(zhàn)、戰(zhàn)場(chǎng)探