運(yùn)籌學(xué)01-緒論-11

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

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

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

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

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

6、廠要做100套三角鋼架，每套用長為套三角鋼架，每套用長為2.9m、2.1m和和 1.5m的圓鋼各一根。已知原料每根長的圓鋼各一根。已知原料每根長7.4m，問應(yīng)如何，問應(yīng)如何 下料，可使所用原料最省。下料，可使所用原料最省。 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套鋼架套鋼架 任務(wù)的條件下，使所用總的原料根數(shù)最少？任務(wù)的條件下，使所用總的原料根數(shù)最少？ 方案方案 長度長度 截法截法 x1 截法截法 x2 截法截法 x3 截法截法 x4 截法截法 x5 2.912010 2.100221 1.531203 合計(jì)合計(jì)7.47.37.27.16.6 料頭料頭00.10.20.30.8 School of Business ECUST o （2）建立模型）建立模型 設(shè)按設(shè)按，截法下料的原材料根數(shù)分別為截法下料的原材料根數(shù)分別為x1， x2，x3，x4，x5，可列出下面的數(shù)學(xué)模型。，可列出下面的數(shù)學(xué)模型。 目標(biāo)函數(shù)：目標(biāo)函數(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ù)學(xué)模型 解 求求 解解 School of Business ECUST o 在建立數(shù)學(xué)模型的過程中，需要明確： n決策變量是什么？求解的對(duì)象 n決策的目標(biāo)是什么？ 目標(biāo)函數(shù) n有哪些限制條件？ 約束條件 例1.2 城市更新模型( Taha, 運(yùn)籌學(xué)導(dǎo)論第8版) o A市面臨著嚴(yán)重的財(cái)政收入不足問題，為了尋求一種長 期解決方案，市政府決定征用一塊內(nèi)城

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

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

11、x2-建造雙戶型住宅的單 nx3-建造三戶型住宅的單元數(shù) nx4-建造四戶型住宅的單元數(shù) nx5-拆除舊住宅的單元數(shù) o 目標(biāo)函數(shù)是從新建的四類住宅中獲得的稅收最大，即 o 問題的第一個(gè)約束是土地可用量： 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 還剩下一個(gè)約束就是要保證拆除和建設(shè)的總費(fèi)用在允許 的預(yù)算內(nèi) n以1000美元表示費(fèi)用的單位，可表示為 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 運(yùn)籌學(xué)的產(chǎn)生與發(fā)展運(yùn)籌學(xué)的產(chǎn)生與發(fā)展 o 我國古代樸素的運(yùn)籌學(xué)思想 n戰(zhàn)國時(shí)期，李冰父子修建的都江堰水利工程 n北宋時(shí)期的丁渭修皇宮 n春秋時(shí)期的田忌賽馬 o 運(yùn)籌學(xué)產(chǎn)

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

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

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