管科大二上學期課件運籌學or intro

徐薇xuwei@南京大學工程管理學院運籌學《史記·高祖本紀》運籌學的萌芽齊王田忌上

中

下下

上

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

Research在美國稱為Operations

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

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

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

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

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

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

No.3,

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

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

Programming

&

Simplex

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

&

Sensitivity

Analysis運輸問題

(5課時)

Transportation

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

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