運籌學(xué) OperationsResearch Chapter1運籌學(xué)概論 一運籌學(xué)簡史 1 運籌學(xué) 的釋義OperationalResearch 英 OperationsResearch 美 直譯為 運作研究 或 運用研究 簡稱OR 中文名稱 運用學(xué) 運籌學(xué)夫運籌帷幄之中 決勝于千里之外 吾不如子房 劉邦 史記 高祖本記 2 我國古代運籌思想的運用 田忌賽馬 一運籌學(xué)簡史 晉國公重建皇城 晉國公重建皇城的施工方案 體現(xiàn)了運籌學(xué)的樸素思想 要使重建工 程的各個工序 在時間 空間上彼此協(xié)調(diào) 環(huán)環(huán)相扣 就需要運用行列式的相關(guān)知識 進行精確計算 一運籌學(xué)簡史 約1000年前 開封一場大火 北宋皇城毀于一旦 宋真宗命晉國公丁渭 主持重建皇城 丁渭先在皇宮前的大道上挖土燒磚備料 待把大道挖成深溝后 引城外汴水使之與汴水連通成為 臨時運河 用船把其他建筑材料直接運入工地 等到皇宮修復(fù)后 將碎磚石填入河道 修復(fù)原來皇宮前的大道 挖街取土 就地?zé)u 渠成引水 運送建材 宮殿完工 渣土回填 恢復(fù)街道 這就巧妙地解決了取土之難 運輸之難 清場之難 可謂 一石三鳥 沈括運糧 沈括 1031 1095年 北宋時期大科學(xué)家 軍事家 在率兵抗擊西夏侵擾的征途中 曾經(jīng)從行軍中各類人員可以背負糧食的基本數(shù)據(jù)出發(fā) 分析計算了后勤人員與作戰(zhàn)士兵在不同行軍天數(shù)中的不同比例關(guān)系 同時也分析計算了用各種牲畜運糧與人力運糧之間的利弊 最后做出了從敵國就地征糧 保障前方供應(yīng)的重要決策 從而減少了后勤人員的比例 增強了前方作戰(zhàn)的兵力 假設(shè)一個民夫可以背六斗米 士兵自帶五天的干糧 如果一個民夫供應(yīng)一個士兵 單程只能進軍十八天 六斗米 每人每天吃二升 二人吃十八天 如果兩個民夫供應(yīng)一個士兵 單程可進軍二十六天 兩個民夫背一石二斗米 三個人每天要吃六升 八天以后 其中一個民夫背的米已經(jīng)吃光 給他六天的口糧讓他先返回 以后的十八天 二人每天吃四升米 如果三個民夫供應(yīng)一個士兵 單程可進軍三十一天 如果要計回程的話 只可進軍十六天 而三個民夫供應(yīng)一個士兵 已經(jīng)到極限了 如果要出動十萬軍隊 輜重占去三分之一兵源 還要用三十萬民夫運糧 再要擴大規(guī)模很困難了 如果用牲畜運輸 駱駝可以馱三石 馬或騾可以馱一石五斗 驢子可以馱一石 與人工相比 雖然能馱的多 花費也少 但如果不能及時放牧或喂食 牲口就會瘦弱而死 一頭牲口死了 只能連它馱的糧食也一同丟棄 所以與人工相比 實際上是利害相當(dāng) 利弊分析后的結(jié)論是 從敵國就地征糧 這種軍事后勤問題的分析計算是具有現(xiàn)代意義的運籌思想的范例 一運籌學(xué)簡史 3 運籌學(xué)的發(fā)展歷程 1 萌芽時期1914年 英工程師Lanchester用微分方程研究作戰(zhàn)雙方的兵力使用 提出了軍事運籌學(xué)中的Lanchester戰(zhàn)斗方程 1909年丹麥工程師愛爾朗在哥本哈根電話公司研究電話交換機的效率開始提出了排隊論的一些著名公式 1920年Harris提出了庫存論的EOQ公式 1930年列溫遜運用運籌學(xué)思想分析商業(yè)廣告和顧客心理 一運籌學(xué)簡史 一運籌學(xué)簡史 2 產(chǎn)生 運籌學(xué)作為一門系統(tǒng)的科學(xué) 產(chǎn)生的背景為第二次世界大戰(zhàn) 主要用于解決如何在與德軍的對抗中最大限度地殺傷敵人 減少損失 運作研究 OperationalResearch 小組 解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題 例如 如何合理運用雷達有效地對付德軍德空襲 對商船如何進行編隊護航 使船隊遭受德國潛艇攻擊時損失最少 在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度 才能增加對德國潛艇的殺傷力等 1938年7月 波得塞 Bawdsey 雷達站的負責(zé)人羅伊 A P Rowe 提出立即進行整個防空作戰(zhàn)系統(tǒng)運行的研究 并用 OperationalResearch 一詞作為這方面研究的描述 這就是O R 名詞的起源 1940年9月英國成立了由物理學(xué)家布萊克特 P M S Blackett 領(lǐng)導(dǎo)的第一個運籌學(xué)小組 后來發(fā)展到每一個英軍指揮部都成立運籌學(xué)小組 1942年美國和加拿大也都相繼成立運籌學(xué)小組 這些小組在確定擴建艦隊規(guī)模 開展反潛艇戰(zhàn)偵察和組織有效對敵轟炸等方面作了大量研究 為取得反法西斯戰(zhàn)爭的勝利及運籌學(xué)有關(guān)分支的建立作出了貢獻 一運籌學(xué)簡史 典型戰(zhàn)例 不列顛之戰(zhàn)1941年 希特勒為了實施在英倫三島登陸的計劃 命令德國空軍輪番對英國進行狂轟濫炸 當(dāng)時英國皇家空軍以一比七的數(shù)量劣勢迎戰(zhàn) 為此需要盡可能地保持飛機處于飛行狀態(tài) 于是 空軍司令部規(guī)定保持70 的飛機在天上巡邏 但是 英軍很快發(fā)現(xiàn)要保持這么高的飛行比例有困難 因為飛機的被擊落的 有需要維修的 飛行員也有傷亡 這一決策的后果是在空中飛行的飛機數(shù)量越來越少 不列顛之戰(zhàn)究竟保持多大比例的飛機在巡邏才能持久作戰(zhàn)呢 OR小組的專家紛紛研究這個問題 這個問題最后被生物學(xué)家康頓解決了 他根據(jù)計算生物平均壽命的方法 運用飛機飛行時間 維修時間 空戰(zhàn)特點和飛機被落擊傷狀況等數(shù)據(jù) 得出的結(jié)論是 只要保持35 的飛機在飛行狀態(tài) 就能使全部飛機的飛行戰(zhàn)斗時間最多 這一研究成果為取得不列顛之戰(zhàn)的勝利作出了貢獻 典型戰(zhàn)例 盟軍封鎖直布羅陀海峽 獵潛戰(zhàn)例 1944年初 為幫助美國海軍在連接大西洋和地中海的直布羅陀海峽封鎖過往的德軍潛艇 美軍OR小組的約翰 佩芝姆博士提出了一種 屏障巡邏 飛行戰(zhàn)術(shù) 典型戰(zhàn)例 盟軍封鎖直布羅陀海峽 獵潛戰(zhàn)例 在深水航道的最窄處劃出一個4英里長 1英里寬的長方形 兩架飛機保持在長方形兩邊線的對稱位置上 同時以115英里 小時的速度繞長方形飛行 這樣 在長 方形上的每一點 每隔3分鐘就有一架飛機巡邏通過 潛艇通過這個區(qū)域時 巡邏的飛機至少有兩次機會去發(fā)現(xiàn)它 就這樣 在2月24日到3月16日短短三個星期內(nèi) 一個巡邏機中隊擊沉擊傷德軍潛艇3艘 自己無一傷亡 典型戰(zhàn)例 3 發(fā)展英美以蘭德公司 Rand 為首的部門著重研究戰(zhàn)略性問題 未來的武器系統(tǒng)的設(shè)計和其可能合理運用的方法 為美國空軍評價各種轟炸機系統(tǒng) 討論未來戰(zhàn)爭的策略 研究蘇聯(lián)政治局的行動原則和將來的行動預(yù)測 除了在軍事應(yīng)用研究以外 相繼在工業(yè) 農(nóng)業(yè) 經(jīng)濟和社會問題等各領(lǐng)域的應(yīng)用 4 成熟期建立運籌學(xué)會 英 1948 美 1952 法 1956 日本和印度 1957 中 1980 一運籌學(xué)簡史 1 運籌學(xué)的定義MorseandKimball 為決策機構(gòu)在對其控制下業(yè)務(wù)活動進行決策時 提供以數(shù)量化為基礎(chǔ)的科學(xué)方法 運籌學(xué)是一門應(yīng)用科學(xué) 它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法 解決實際中提出的專門問題 為決策者選擇最優(yōu)決策提供定量依據(jù) 英國運籌學(xué)會 運籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員 工商企業(yè)政法和國防方面解決發(fā)生的各種問題 其方法是發(fā)展一個科學(xué)的系統(tǒng)模式 并運用這種模式預(yù)測 比較公眾決策及產(chǎn)生的后果以幫助決策者科學(xué)地決定工作方針和政策 美國運籌協(xié)會 運籌學(xué)是在要求分配有限資源的條件下 科學(xué)地決定如何最好地設(shè)計和運營人機系統(tǒng) 二運籌學(xué)的性質(zhì)和特點 引入數(shù)學(xué)方法解決實際問題 定性與定量方法結(jié)合系統(tǒng)與整體性 從全局考察問題應(yīng)用性 源于實踐 為了實踐 服務(wù)于實踐交叉學(xué)科 涉及經(jīng)濟 管理 數(shù)學(xué) 工程和系統(tǒng)等多學(xué)科開放性 不斷產(chǎn)生新的問題和學(xué)科分支多分支 問題的復(fù)雜和多樣性 2 運籌學(xué)的特點 二運籌學(xué)的性質(zhì)和特點 線性規(guī)劃 數(shù)學(xué)規(guī)劃 非線性規(guī)劃 整數(shù)規(guī)劃 動態(tài)規(guī)劃 運籌學(xué) 多目標(biāo)規(guī)劃 雙層規(guī)劃 組合優(yōu)化 最優(yōu)計數(shù)問題 圖論與網(wǎng)絡(luò)優(yōu)化 排序問題 統(tǒng)籌圖 隨機優(yōu)化 對策論 排隊論 庫存論 決策論 可靠性分析 三運籌學(xué)的內(nèi)容 系統(tǒng)仿真 1 排隊論 研究關(guān)于公用服務(wù)系統(tǒng)的排隊和擁擠現(xiàn)象的隨機特性和規(guī)律的理論 使服務(wù)機構(gòu)對被服務(wù)對象得到某指標(biāo)最優(yōu) 于1909年丹麥工程師愛爾朗研究電話交換機的效率開始的 如一個港口應(yīng)該有多少個碼頭 銀行應(yīng)該開設(shè)多少個服務(wù)窗口等 三運籌學(xué)的內(nèi)容 1 囚徒困境問題 兩個小偷甲和乙聯(lián)手作案 因私入民宅被警方抓住但未獲證據(jù) 警方將兩人分別置于兩間房間分開審訊 政策是若一人招供但另一人未招 則招者立即被釋放 未招者判入獄10年 若二人都招 則兩人各判刑8年 若兩人都不招 則未獲證據(jù)但因私入民宅各拘留1年 盡管甲不知道乙是否招供 但他認為自己選 招 最好 因而甲會選擇 招 乙也同樣會選擇 招 結(jié)果各判8年 但若兩人都不招 結(jié)果是每人只被判1年 但在 人是理性的 即人人都會在約束條件下最大化自身的利益 的基本假設(shè)下 這種結(jié)果是不會出現(xiàn)的 甲和乙是參與博弈的人 稱為 局中人 上表中每一個小方格內(nèi)的數(shù)字被稱為局中人的支付 其中左邊的數(shù)字代表甲的支付 右邊的是乙的支付 表上中的雙變量矩陣稱為博弈支付矩陣 局中人所選擇的策略構(gòu)成的組合 招 招 被稱為博弈均衡 這個組合中前后兩個策略分別表示甲和乙所選擇的策略 納什均衡 非合作博弈均衡 對于一個博弈問題 如果在每一個局勢中 全體局中人的得失相加都是零 則稱此博弈為零和博弈 非合作博弈 否則稱為非零和博弈 合作博弈 在二人零和博弈中 雙方局中人尋求的最優(yōu)解是一種納什均衡 達到這種均衡時 只要其他局中人不改變自己的策略 則任何一方單獨改變策略 只能帶來收益或效用的減少 納什均衡 首先對亞當(dāng) 斯密的 看不見的手 的原理提出挑戰(zhàn) 按照斯密的理論 在市場經(jīng)濟中 每一個人都從利己的目的出發(fā) 而最終全社會達到利他的效果 但是我們可以從 納什均衡 中引出 看不見的手 原理的一個悖論 從利己目的出發(fā) 結(jié)果損人不利己 既不利己也不利他 3 庫存論 又稱存儲論 研究合理經(jīng)濟地進行物資儲備的控制策略的理論 4 決策論 研究決策者如何有效進行決策的理論與方法 根據(jù)信息和評價標(biāo)準(zhǔn)用數(shù)量方法尋找或選取最優(yōu)決策方案的科學(xué) 運籌數(shù)學(xué) 系統(tǒng)工程 管理與運籌學(xué) 問題與方法 方法與應(yīng)用 核心算法與工具 基礎(chǔ)理論 應(yīng)用理論 應(yīng)用技術(shù) 運籌學(xué) 運籌學(xué)的學(xué)科地位 1 市場營銷 廣告預(yù)算 媒介選擇 定價 產(chǎn)品開發(fā)與銷售計劃制定等 2 生產(chǎn)計劃 生產(chǎn)作業(yè)的計劃 日程表的編排 合理下料 配料問題 物料管理等 3 庫存管理 多種物資庫存量的管理 庫存方式 庫存量等 4 運輸問題 確定最小成本的運輸線路 物資的調(diào)撥 運輸工具的調(diào)度以及建廠地址的選擇等 5 財務(wù)和會計 預(yù)測 貸款 成本分析 定價 證券管理 現(xiàn)金管理等 四運籌學(xué)的應(yīng)用 6 人事管理 對人員的需求和使用的預(yù)測 確定人員編制 人員合理分配 建立人才評價體系等 7 財務(wù)和會計 預(yù)測 貸款 成本分析 定價 證券管理 現(xiàn)金管理等 8 設(shè)備維修 更新和可靠性 項目選擇 評價 9 工程優(yōu)化設(shè)計與管理 10 城市管理 緊急服務(wù)系統(tǒng)設(shè)計和應(yīng)用 供水和污水處理系統(tǒng)的規(guī)劃等 四運籌學(xué)的應(yīng)用 由國際運籌與管理科學(xué)協(xié)會 INFORMS 主持評獎的負有盛名的弗蘭茨 埃德曼 FranyEdelman 獎 就是為獎勵優(yōu)秀的運籌學(xué)在管理中的應(yīng)用的成就設(shè)立的 該獎每年舉行一次 在對大量富有競爭力的入圍者進行艱苦的評審后 一般有六位優(yōu)勝者獲獎 關(guān)于這些獲獎項目的文章都在第二年發(fā)表在著名刊物Interface的第一期上 下面列表就是發(fā)表在Interface期刊的一些獲獎項目 四運籌學(xué)的應(yīng)用 2008年度大獎 荷蘭鐵路 項目 荷蘭火車新時刻表問題 1970年80億人千米到2006年154億人千米解決方法 構(gòu)建改進的循環(huán)的時刻表 每一個小時可重復(fù) 這是一個組合優(yōu)化問題 設(shè)計4個程序效果 公眾意見從負面批評道正面肯定 每年增加了4000萬歐元的利潤 運籌學(xué)方法使用情況 美1983 運籌學(xué)方法在中國使用情況 隨機抽樣 軟運籌學(xué) 發(fā)源于英國 軟系統(tǒng)方法論問題結(jié)構(gòu)法戰(zhàn)略假設(shè)表面化與檢驗戰(zhàn)略選擇超對策亞對策生存系統(tǒng)模型對話式計劃 五運籌學(xué)的展望 運籌學(xué)應(yīng)用 運籌科學(xué) 運籌數(shù)學(xué) 軟計算 與優(yōu)化有關(guān) 遺傳算法模擬退火算法神經(jīng)網(wǎng)絡(luò)模糊邏輯進化計算禁忌算法蟻群優(yōu)化 教材 運籌學(xué) 教學(xué)內(nèi)容 韓伯棠 管理運籌學(xué) 高等教育出版社 北京 2000年胡運權(quán)等 運籌學(xué)教程 清華出版社 北京 1998年劉家壯 王建方 網(wǎng)絡(luò)最優(yōu)化 華中工學(xué)院出版社 武漢 1987年管梅谷 鄭漢鼎 線性規(guī)劃 山東科學(xué)技術(shù)出版社 濟南 1983年 參考資料 本課程授課方式與考核 講授為主 結(jié)合習(xí)題作業(yè) Theend thankyou