運籌學01-緒論-11

1、運籌學運籌學 華東理工大學商學院 管理科學與工程系 夏海洋 第第1講講 緒論緒論 1.1 運籌學的定義 1.2 運籌學研究的系統(tǒng)過程 1.3 運籌學的產(chǎn)生與發(fā)展 1.4 運籌學的主要分支 1.1 1.1 運籌學的定義運籌學的定義 o 運籌學一詞的由來 nOperations Research (美) nOperational Research (英國) n作業(yè)研究(臺灣)，運用學運籌學(1957年) n作戰(zhàn)研究：operation(軍事行動，作戰(zhàn)), research(研究) n二戰(zhàn)期間，英美等國為了解決作戰(zhàn)中遇到的錯綜復雜的 戰(zhàn)略、戰(zhàn)術問題而成立了由科學家、工程師等組成的關 于作戰(zhàn)的科學研究

2、小組。1938年，波德塞科學小組的負 責人A.P. Rowe把他們從事的工作稱為“operational research”(作戰(zhàn)研究)，他被認為這一詞匯的創(chuàng)始人。 School of Business ECUST o 運籌學的定義 n運籌學研究的兩位先驅(qū)莫斯(P. M. Morse)和金博爾(G.E. Kimball)的定義是：“運籌學是在實行管理的領域，運用運籌學是在實行管理的領域，運用 數(shù)學方法，對需要進行管理的問題統(tǒng)籌規(guī)劃，作出決策數(shù)學方法，對需要進行管理的問題統(tǒng)籌規(guī)劃，作出決策 的一門應用科學。的一門應用科學?！?n辭海中對運籌學作的解釋是：20世紀世紀40年代開始形年代開始形 成的

3、一門學科，主要研究經(jīng)濟活動和軍事活動中能用數(shù)成的一門學科，主要研究經(jīng)濟活動和軍事活動中能用數(shù) 量來表達的有關運用、籌劃與管理方面的問題。它根據(jù)量來表達的有關運用、籌劃與管理方面的問題。它根據(jù) 問題的要求，通過數(shù)學分析的運算，作出綜合性的合理問題的要求，通過數(shù)學分析的運算，作出綜合性的合理 安排，以達到較經(jīng)濟、較有效地使用人力、物力。安排，以達到較經(jīng)濟、較有效地使用人力、物力。 n另一較有代表性的定義是，運籌學是一門應用科學，它運籌學是一門應用科學，它 廣泛應用現(xiàn)有的科學技術知識和數(shù)學方法，解決實際提廣泛應用現(xiàn)有的科學技術知識和數(shù)學方法，解決實際提 出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)

4、。出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)。 o 關于運籌學定義的總結(jié)：關于運籌學定義的總結(jié)： n運籌學是一門應用科學，它是面向?qū)嵺`的，它的研究對運籌學是一門應用科學，它是面向?qū)嵺`的，它的研究對 象是實踐中的決策問題，并且要將研究結(jié)果應用于實象是實踐中的決策問題，并且要將研究結(jié)果應用于實 踐；踐；(運籌學的實踐性運籌學的實踐性) n運籌學研究是基于數(shù)量化的方法和技術，同時對這些數(shù)運籌學研究是基于數(shù)量化的方法和技術，同時對這些數(shù) 量化方法和技術的研究也構(gòu)成了運籌學的重要組成；量化方法和技術的研究也構(gòu)成了運籌學的重要組成；(數(shù)數(shù) 學分支，最優(yōu)化技術學分支，最優(yōu)化技術) n運籌學研究的目標是對

5、現(xiàn)實決策問題進行求解或評估，運籌學研究的目標是對現(xiàn)實決策問題進行求解或評估， 以達到優(yōu)化決策的目的。以達到優(yōu)化決策的目的。(方法論方法論vs決策科學決策科學) School of Business ECUST 現(xiàn)實中的決策問題現(xiàn)實中的決策問題 數(shù)量化的方法與技術 解決解決 運籌學(OR) School of Business ECUST 1.2 1.2 運籌學研究的系統(tǒng)過程運籌學研究的系統(tǒng)過程 定義現(xiàn)實中的問題 建立數(shù)學模型 對模型進行求解 對解進行驗證， 必要時修正模型 結(jié)果的實施 School of Business ECUST 示例示例1.1 1.1 下料問題下料問題 o 某工廠要做某工

6、廠要做100套三角鋼架，每套用長為套三角鋼架，每套用長為2.9m、2.1m和和 1.5m的圓鋼各一根。已知原料每根長的圓鋼各一根。已知原料每根長7.4m，問應如何，問應如何 下料，可使所用原料最省。下料，可使所用原料最省。 o （1）分析問題）分析問題 n最簡單的做法是：最簡單的做法是： n還有沒有其他裁剪方案？還有沒有其他裁剪方案？ 1.52.12.9 7.4 0.9 School of Business ECUST n經(jīng)過分析，我們可以制定下列經(jīng)過分析，我們可以制定下列5種方案可供裁剪：種方案可供裁剪： n問題轉(zhuǎn)換為：各種截法分別為多少根，使得在完成問題轉(zhuǎn)換為：各種截法分別為多少根，使得在

7、完成100套鋼架套鋼架 任務的條件下，使所用總的原料根數(shù)最少？任務的條件下，使所用總的原料根數(shù)最少？ 方案方案 長度長度 截法截法 x1 截法截法 x2 截法截法 x3 截法截法 x4 截法截法 x5 2.912010 2.100221 1.531203 合計合計7.47.37.27.16.6 料頭料頭00.10.20.30.8 School of Business ECUST o （2）建立模型）建立模型 設按設按，截法下料的原材料根數(shù)分別為截法下料的原材料根數(shù)分別為x1， x2，x3，x4，x5，可列出下面的數(shù)學模型。，可列出下面的數(shù)學模型。 目標函數(shù)：目標函數(shù)： min z= x1+x2

8、+x3+x4+x5 約束條件：約束條件： x1+ 2x2 +x4 100 2x3 + 2x4+ x5 100 3x1 + x2+ 2x3 +3x5 100 x1，x2，x3，x4，x5 0 x1=30，x2=10，x3=0，x4=50，x5=0 數(shù)學模型 解 求求 解解 School of Business ECUST o 在建立數(shù)學模型的過程中，需要明確： n決策變量是什么？求解的對象 n決策的目標是什么？ 目標函數(shù) n有哪些限制條件？ 約束條件 例1.2 城市更新模型( Taha, 運籌學導論第8版) o A市面臨著嚴重的財政收入不足問題，為了尋求一種長 期解決方案，市政府決定征用一塊內(nèi)城

9、的住宅區(qū)域，進 行一項現(xiàn)代化的房地產(chǎn)開發(fā)項目，以增加稅收來源。 o 改造工程分為兩個階段：(一)拆除不符合標準的住宅， 為新的開發(fā)提供土地；(二) 建設新的建筑。下面是情況 概要： n(1) 最多可拆除300套不符合標準的舊住宅，每套住宅占 地0.25英畝，拆除一套征地住宅的成本是2000美元。 n(2) 新建設的單、雙、三和四戶型住宅的占地面積分別為 0.18、0.28、0.4和0.5英畝。街道、開闊地和公共設施占 可利用面積總量的15%。 n(3) 在新的開發(fā)項目中，三戶型和四戶型的住宅單元數(shù)的 總和至少占住宅單元總量的25%；單戶型住宅單元數(shù)至 少應占總單元數(shù)的20%，雙戶型住宅單元數(shù)至

10、少占總單 元數(shù)的10%。 n(4) 對于單、雙、三和四戶型住宅，每個單元的征稅額分 別為1000美元、1900美元、2700美元和3400美元。 n(5) 對于單、雙、三和四戶型住宅，每個單元的建筑成本 分別為50000美元、70000美元、130000美元和160000美 元。通過當?shù)劂y行籌措資金總計最高達到1500萬美元。 o 問：各種戶型的住宅單元分別應建多少套，可使稅收總 額達到最大？ 數(shù)學模型的建立數(shù)學模型的建立 o 除了確定建造每種類型住宅單元的數(shù)量外，我們還需要 確定有多少套舊房屋必須拆除，為新的開發(fā)項目提供場 地。因此，問題的變量可定義如下： nx1-建造單戶型住宅的單元數(shù) n

11、x2-建造雙戶型住宅的單 nx3-建造三戶型住宅的單元數(shù) nx4-建造四戶型住宅的單元數(shù) nx5-拆除舊住宅的單元數(shù) o 目標函數(shù)是從新建的四類住宅中獲得的稅收最大，即 o 問題的第一個約束是土地可用量： n用于新建住宅的面積 = 總單元數(shù)量的20% n雙戶型住宅數(shù)量 = 總單元數(shù)量的10% n三戶型和四戶型住宅數(shù)量之和 = 總單元數(shù)量的25% n這些約束可表示為 11234 21234 341234 0. 2 0. 1 0. 25 xxxxx xxxxx xxxxxx o 還剩下一個約束就是要保證拆除和建設的總費用在允許 的預算內(nèi) n以1000美元表示費用的單位，可表示為 12345 507

12、0130160215000 xxxxx 12.34 12345 5 11234 21234 341234 12345 m ax1000190027003400 0. 180. 280. 40. 50. 25115% 300 0. 2 .0. 1 0. 25 5070130160215000 0,1,2,. . . ,5 j zxxxx xxxxx x xxxxx st xxxxx xxxxxx xxxxx xj 1.3 1.3 運籌學的產(chǎn)生與發(fā)展運籌學的產(chǎn)生與發(fā)展 o 我國古代樸素的運籌學思想 n戰(zhàn)國時期，李冰父子修建的都江堰水利工程 n北宋時期的丁渭修皇宮 n春秋時期的田忌賽馬 o 運籌學產(chǎn)

13、生的淵源 n蘭徹斯特方程：1914年英國工程師蘭徹斯特(F.W. Lanchester)在英國工程雜志上發(fā)表了一篇論文, 文中 建立的描述作戰(zhàn)雙方兵力變化過程的數(shù)學方程被稱為蘭 徹斯特方程，對集中兵力這一重要的軍事原則作出了科 學的論證。這是最早將數(shù)學定量分析方法應用于軍事作 戰(zhàn)研究的文獻之一，是運籌學產(chǎn)生的重要淵源。 n丹麥工程師A.K. Erlang在二十世紀初發(fā)展的排隊論 n數(shù)理經(jīng)濟學派的研究: o 運籌學的產(chǎn)生 n二戰(zhàn)期間，英、美等國組建的作戰(zhàn)研究(operational research)小組進行的關于戰(zhàn)略、戰(zhàn)術的研究工作。 nBawdsey雷達站的研究工作 負責人A.P. Rowe

14、提出立即進行整個防空作戰(zhàn)系統(tǒng)運行的研 究。所研究的具體問題有：設計將雷達信息傳送給指揮系 統(tǒng)及武器系統(tǒng)的最佳方式；雷達與防空武器的最佳配置； 由于對探測、信息傳遞、作戰(zhàn)指揮、戰(zhàn)斗機與防空火力協(xié) 調(diào)等獲得成功，大大提高了英國本土的防空能力，不久以 后在對抗德國對英倫三島的狂轟濫炸中發(fā)揮了極大的作用 。 Bawdsey也被稱為運籌學的發(fā)源地。 n大西洋反潛戰(zhàn)(1942年) 1942年，應英國要求美國派麻省理工學院的Morse教授率領 一個小組去協(xié)助進行反潛戰(zhàn)的作戰(zhàn)研究工作 。Morse小組 經(jīng)過多方實地考察，最后提出了兩條重要建議: (1) 將反潛攻擊由反潛潛艇投擲水雷，改為飛機投擲深水炸彈。 起

15、爆深度由100米左右改為25米左右。即當潛艇剛下潛時攻擊效 果最佳。(提高效率4-7倍) (2) 運送物資的船隊及護航艦隊編隊，由小規(guī)模多批次，改為加大 規(guī)模、減少批次，這樣，損失率將減少。（25%下降到10%） 丘吉爾采納了MORSE的建議，最終成功地打破封鎖，并重創(chuàng)了德 國潛艇。MORSE同時獲得英國和美國的最高勛章。 o 運籌學的發(fā)展 n二戰(zhàn)之后，二戰(zhàn)期間成立的運籌學小組成員把在戰(zhàn)爭中積累的 豐富經(jīng)驗與理論方法轉(zhuǎn)向了民用問題，運籌學開始進入工業(yè)部 門和管理領域。運籌學作為一門學科逐步發(fā)展起來： 1947年，Dantzig提出線性規(guī)劃的單純形法 19501956年間，線性規(guī)劃對偶理論誕生 1951年 ，Knhn-Tuker定理奠定了非線性規(guī)