戰(zhàn)爭中的運籌學(xué)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、割并攻擊后部12艘。小縱列：8艘，在中心部分附近攻擊其先頭部分的3-4艘。,23,蘭徹斯特（F.W.Lanchester）作戰(zhàn)分析 蘭徹斯特方程：設(shè)兩軍對抗中一方有x 個戰(zhàn)斗單位（戰(zhàn)艦、戰(zhàn)車、戰(zhàn)機、步兵單位等），另外一方有y個戰(zhàn)斗單位?；炯僭O(shè)：每一方戰(zhàn)斗單位的損失率與對方戰(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定律可以對“納爾森（Nelson）秘訣”進行分析：整體戰(zhàn)斗實力。設(shè)雙方單個戰(zhàn)斗單位的戰(zhàn)斗力相同，則有：英國艦隊：402=1600聯(lián)合艦隊：462=2116此時聯(lián)合艦隊占優(yōu)勢，設(shè)想聯(lián)合艦隊全殲英國艦隊后，聯(lián)合艦隊還有5161/2=23艘。,26,將聯(lián)合艦隊攔腰切斷，23+23=46，是將聯(lián)合艦隊實力減

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

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

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

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

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

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

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

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

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

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