管科大二上學(xué)期課件運(yùn)籌學(xué)or intro

徐薇xuwei@南京大學(xué)工程管理學(xué)院運(yùn)籌學(xué)《史記·高祖本紀(jì)》運(yùn)籌學(xué)的萌芽齊王田忌上

中

下下

上

中最終凈勝一局，贏得1000金。在我國先秦時期的諸子著作中，就存在著許多樸素的運(yùn)籌學(xué)思想。田忌賽馬齊王要與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對局三次，每次勝負(fù)1000金。田忌在好友著名的軍事謀略家孫臏的指導(dǎo)下，采用以下安排：運(yùn)籌學(xué)的萌芽成功原因由于孫臏運(yùn)籌有方，田忌終于以弱勝強(qiáng)。這不僅顯示出我國古樸運(yùn)籌學(xué)的某些思想精華以及實(shí)踐成就，還蘊(yùn)含著現(xiàn)代運(yùn)籌學(xué)的重要分支之一——對策論（博弈論）的某些思想萌芽。運(yùn)籌學(xué)的萌芽丁謂主持的皇宮修復(fù)工程北宋年間，丁謂負(fù)責(zé)修復(fù)火毀的開封皇宮。他的施工方案是：先將工程皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。使用挖出的土就地制磚，令與汴水相連形成的河道承擔(dān)繁重的運(yùn)輸任務(wù)；修復(fù)工程完成后，實(shí)施大溝排水，并將原廢墟物回填，修復(fù)成原來的大街。丁謂將取材、生產(chǎn)、運(yùn)輸及廢墟物的處理用“一溝三用”巧妙地解決了。運(yùn)籌學(xué)緒論什么是運(yùn)籌學(xué)運(yùn)籌學(xué)的起源與發(fā)展運(yùn)籌學(xué)解決問題的方法步驟運(yùn)籌學(xué)的主要研究分支本課程的主要學(xué)習(xí)內(nèi)容什么是運(yùn)籌學(xué)？作為一門學(xué)科誕生于20世紀(jì)30年代末期運(yùn)籌學(xué)一詞在英國稱為Operational

Research在美國稱為Operations

Research縮寫為O.R.什么是運(yùn)籌學(xué)？大英百科全書——運(yùn)籌學(xué)是一門應(yīng)用于管理有組織系統(tǒng)的科學(xué)，它為掌管這類系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具。中國大百科全書——用數(shù)學(xué)方法研究經(jīng)濟(jì)、民政和

國防等部門在內(nèi)外環(huán)境的約束條件下合理分配人力、物力、財(cái)力等資源，使實(shí)際系統(tǒng)有效運(yùn)行的技術(shù)科

學(xué)，它可以用來預(yù)測發(fā)展趨勢，制定行動規(guī)劃或優(yōu)

選可行方案。……管理系統(tǒng)的人為了獲得關(guān)于系統(tǒng)運(yùn)行的最優(yōu)解而必須使用的一種科學(xué)方法。什么是運(yùn)籌學(xué)？運(yùn)籌學(xué)的研究對象是各種系統(tǒng)；運(yùn)籌學(xué)的研究目的是實(shí)現(xiàn)系統(tǒng)的最優(yōu)化，求得合理利用各種資源的最優(yōu)方案；運(yùn)籌學(xué)的研究方法是運(yùn)用數(shù)學(xué)語言來描述實(shí)際系統(tǒng)，通過建立數(shù)學(xué)模型和優(yōu)化技術(shù)求得系統(tǒng)運(yùn)營的最優(yōu)解；運(yùn)籌學(xué)的研究動機(jī)是為決策者提供科學(xué)決策的依據(jù)。運(yùn)籌學(xué)的起源與發(fā)展起源于二次大戰(zhàn)的一門新興學(xué)科與作戰(zhàn)問題相關(guān)如雷達(dá)的設(shè)置、運(yùn)輸船隊(duì)的護(hù)航、反潛作戰(zhàn)中深水炸彈的深度、飛行員的編組、軍事物資的存儲等鮑德西(Bawdsey)雷達(dá)站的研究(1935年)1935年，英國科學(xué)家R.Watson-Wart發(fā)明了雷達(dá)。丘吉爾命令在英國東海岸的Bawdsey建立了一個秘密雷達(dá)站。當(dāng)時，德國已擁有一支強(qiáng)大的空軍，起飛17分鐘即到達(dá)英國本土。在如此短的時間內(nèi)，如何預(yù)警和攔截成為一大難題。1939年由曼徹斯特大學(xué)物理學(xué)家、英國戰(zhàn)斗機(jī)司令部顧問、戰(zhàn)后獲得諾貝爾獎的P.M.S.Blackett為首，組織了一個小組，代號“Blackett馬戲團(tuán)”。這個小組包括3名心理學(xué)家、2名數(shù)學(xué)家、2名應(yīng)用數(shù)學(xué)家、1名天文物理學(xué)家、1名普通物理學(xué)家等。運(yùn)籌學(xué)的起源與發(fā)展–研究的問題是：設(shè)計(jì)將雷達(dá)信息傳送到指揮系統(tǒng)和武器系統(tǒng)的最佳方式；雷達(dá)與武器的最佳配置；對探測、信息傳遞、作戰(zhàn)指揮、戰(zhàn)斗機(jī)與武器的協(xié)調(diào)，作了系統(tǒng)研究，獲得成功。Blackett馬戲團(tuán)在秘密報(bào)告中使用了“Operational

Research”，即運(yùn)籌學(xué)。大西洋反潛戰(zhàn)(1942年)1941-1942年，德國潛艇嚴(yán)密封鎖了英吉利海峽，企圖切斷英國的“生命線”。海軍幾次反封鎖，均不成功。應(yīng)英國要求，美國派麻省理工學(xué)院的物理學(xué)家P.W.Morse擔(dān)任計(jì)劃與監(jiān)督。Morse經(jīng)過多方實(shí)地考察和分析計(jì)算，最后提出了兩條重要建議：將反潛攻擊由反潛潛艇投擲水雷，改為飛機(jī)投擲深水炸彈。起爆深度由100米左右改為25米左右。即當(dāng)潛艇剛下潛時攻擊效果最佳。(提高效率4-7倍)運(yùn)送物資的船隊(duì)及護(hù)航艦隊(duì)編隊(duì)，由小規(guī)模多批次，改為加大規(guī)模、減少批次，這樣損失率將減少。(25%下降到10%)運(yùn)籌學(xué)的起源與發(fā)展戰(zhàn)后在經(jīng)濟(jì)、管理和機(jī)關(guān)學(xué)校及科研單位繼續(xù)研究1948年英國首先成立運(yùn)籌學(xué)俱樂部1948年美國麻省理工學(xué)院設(shè)立運(yùn)籌學(xué)課程1950年第一本運(yùn)籌學(xué)雜志《運(yùn)籌學(xué)季刊》在英國創(chuàng)刊1951年，Morse

和Kimball出版《運(yùn)籌學(xué)方法》1952年美國成立運(yùn)籌學(xué)會，會刊OR創(chuàng)刊1953年美國成立管理科學(xué)學(xué)會，會刊MS創(chuàng)刊1959年國際運(yùn)籌學(xué)聯(lián)合會(IFORS)成立我國于1982年加入IFORS，并于1999年8月組織承辦了第15屆大會1995年國際運(yùn)籌學(xué)與管理科學(xué)學(xué)會(INFORMS)成立，是由美國運(yùn)籌學(xué)會和美國管理科學(xué)學(xué)會合并而成我國運(yùn)籌學(xué)的發(fā)展現(xiàn)代運(yùn)籌學(xué)被引入中國是在20世紀(jì)50年代后期:1956年——第一個運(yùn)籌學(xué)小組在錢學(xué)森、許國志先生的推動下，在中國科學(xué)院力學(xué)研究所成立1959年——第二個運(yùn)籌學(xué)部門在中國科學(xué)院數(shù)學(xué)研究所成立，1960年與力學(xué)所小組合并成為數(shù)學(xué)研究所的一個研究室1963年——數(shù)學(xué)研究所的運(yùn)籌學(xué)研究室為中國科技大學(xué)應(yīng)用數(shù)學(xué)系的第一屆學(xué)生開設(shè)了較為系統(tǒng)的運(yùn)籌學(xué)專業(yè)課1965年——華羅庚教授親自率領(lǐng)小分隊(duì)到農(nóng)村、工廠講解基本的“優(yōu)選法”和“統(tǒng)籌法”1980年——中國運(yùn)籌學(xué)會(ORSC)成立，華羅庚教授任第一屆理事長，1992年從中國數(shù)學(xué)會獨(dú)立出來，成為一級學(xué)會我國運(yùn)籌學(xué)的發(fā)展更詳細(xì)的介紹請參閱：《中國運(yùn)籌學(xué)發(fā)展研究報(bào)告》——運(yùn)籌學(xué)學(xué)報(bào)，Vol.16,

No.3,

2012.運(yùn)籌學(xué)解決問題的方法步驟明確問題建立模型設(shè)計(jì)算法整理數(shù)據(jù)求解模型評價結(jié)果明確問題建立模型設(shè)計(jì)算法整理數(shù)據(jù)求解模型評價結(jié)果滿意？Yes簡化？NoNo運(yùn)籌學(xué)的主要研究分支線性規(guī)劃：模型簡單，是運(yùn)籌學(xué)中應(yīng)用最為廣泛的一個分支。非線性規(guī)劃：在各類工程的優(yōu)化設(shè)計(jì)中應(yīng)用廣泛。動態(tài)規(guī)劃：研究多階段決策過程最優(yōu)化的運(yùn)籌學(xué)分支。圖論與網(wǎng)絡(luò)分析：利用圖來表示研究對象及其聯(lián)系，并用圖論方法來研究網(wǎng)絡(luò)結(jié)構(gòu)和流量的優(yōu)化分析。決策論：研究決策過程中關(guān)于方案目標(biāo)的選取和度量、效用值計(jì)算、選取最優(yōu)方案和策略等的科學(xué)理論。對策論（博弈論）：用于研究具有對抗局勢的模型。存貯論（庫存論）：研究最優(yōu)存貯策略的理論和方法。排隊(duì)論：研究排隊(duì)系統(tǒng)的理論和方法（隨機(jī)服務(wù)系統(tǒng)理論）。哥尼斯堡七橋問題運(yùn)籌學(xué)的應(yīng)用有人曾對世界上500家著名的企業(yè)集團(tuán)或跨國公司進(jìn)行過調(diào)查，發(fā)現(xiàn)其中95%使用過線性規(guī)劃75%使用過運(yùn)輸模型90%使用過網(wǎng)絡(luò)計(jì)劃技術(shù)90%使用過存儲模型43%使用過動態(tài)規(guī)劃國際著名運(yùn)籌學(xué)刊物……Management

Science

Operations

Research

MathematicalProgrammingMathematics

of

Operations

Research

Mathematical

Method

of

Operations

ResearchEuropean

Journal

of

Operations

ResearchOperations

Research

LetterINFORMS期刊(The

Institute

for

OperationsResearch

and

the

Management

Sciences)參考書籍△RonaldL.Rardin，《運(yùn)籌學(xué):優(yōu)化模型與算法》，電子工業(yè)出版社?！鱂rederickS.Hillier,GeraldJ.Lieberman，《運(yùn)籌學(xué)導(dǎo)論（第8版）》，清華大學(xué)出版社?！鱓ayne

L. Winston，《運(yùn)籌學(xué)(數(shù)學(xué)規(guī)劃第3版影印版)》，清華大學(xué)出版社?！魅~向，《實(shí)用運(yùn)籌學(xué)——運(yùn)用Excel建模和求解》，中國人民大學(xué)出版社?！麝愂砍桑秾?shí)用管理運(yùn)籌學(xué)——基于Excel》，清華大學(xué)出版社。課程安排線性規(guī)劃及單純形法(9課時)Linear

Programming

&

Simplex

Method對偶理論與靈敏度分析(6課時) Duality

&

Sensitivity

Analysis運(yùn)輸問題

(5課時)

Transportation

Models目標(biāo)規(guī)劃(3課時)Goal

Programming整數(shù)規(guī)劃