運籌學課件(武漢大學劉明霞).ppt

《運籌學課件(武漢大學劉明霞).ppt》由會員分享，可在線閱讀，更多相關(guān)《運籌學課件(武漢大學劉明霞).ppt（50頁珍藏版）》請在裝配圖網(wǎng)上搜索。

《運籌學》,武漢大學商學院 劉明霞,教材,Operation(al) Research（簡寫OR） 直譯為：作戰(zhàn)研究、運用研究 日本：運用學 中國：運籌學（意譯） 教材 《運籌學》，韓伯堂，高等教育出版社，2000年 參考書 《運籌學》，清華大學出版社 《管理運籌學》韓大衛(wèi)編，大連理工大學出版社 其它同類書,教學目的與方法,教學目的：介紹運籌學各分支體系的基本模型、求解方法；引導并鍛練MBA學員用運籌學知識定量分析與解決實際問題的能力。 教學方法 以各種實際問題為背景，引出各分支基本概念、基本模型和基本方法，側(cè)重各種方法及應用，回避繁復的數(shù)學理論推導。 運用軟件教學，并讓學生掌握這類軟件。 分組進行案例分析與討論,教學內(nèi)容,運籌學ABC 線性規(guī)劃問題 整數(shù)規(guī)劃 目標規(guī)劃 動態(tài)規(guī)劃 網(wǎng)絡規(guī)劃 排隊論 存貯論 對策論 決策論,,第一章 運籌學ABC,運籌學 的發(fā)展：三個來源 運籌學的性質(zhì)和特點 運籌學研究的問題與解決方法 運籌學的工作步驟,運籌學的發(fā)展：三個來源,軍 事 管 理 經(jīng) 濟,軍事：運籌學的主要發(fā)源地,古代軍事運籌學思想 中國古代的“孫子兵法”在質(zhì)的論斷中滲透著量的分析（1981年美國軍事運籌學會出版了一本書，書中第一句話就是說孫武子是世界上第一個軍事運籌學的實踐家），中國古代運籌學思想的例子還有：田忌賽馬、圍魏救趙、行軍運糧，等等。 國外歷史上的阿基米德、伽利略研究過作戰(zhàn)問題；第一次世界大戰(zhàn)時，英國的蘭徹斯特（Lanchester）提出了戰(zhàn)斗方程，指出了數(shù)量優(yōu)勢、火力和勝負的動態(tài)關(guān)系；美國的愛迪生為美國海軍咨詢委員會研究了潛艇攻擊和潛艇回避攻擊的問題。,,運籌學的正式產(chǎn)生：第二次世界大戰(zhàn) 鮑德西（Bawdsey）雷達站的研究 1939年，以Blackett為首的一個研究小組（代號“Blackett 馬戲團”），研究如何改進英國的空防系統(tǒng)，提高英國本土防空能力。 Blackett備忘錄 1941年12月， Blackett應盟國政府的要求，寫了五份題為“Scientists at the Operational Level”的簡短備忘錄，建議在各大指揮部建立運籌學小組，此建議被迅速采納。據(jù)不完全統(tǒng)計，二戰(zhàn)期間，僅在英、美和加拿大，參加運籌學工作的科學家超過700名。 大西洋反潛戰(zhàn)：研究如何打破德國對英吉利海峽的海上封鎖 英國戰(zhàn)斗機中隊援法的決策,管理,泰勒的時間動作研究、甘特的用于生產(chǎn)計劃與控制的“甘特圖”、吉爾布雷思夫婦的動作研究等 愛爾朗（Erlong）的排隊論公式 1909－1920年間，丹麥哥本哈根電話公司工程師愛爾朗陸續(xù)發(fā)表了關(guān)于電話通路數(shù)量等方面的分析與計算公式。尤其是1909年的論文“概率與電話通話理論”，開創(chuàng)了運籌學的重要分支－－排隊論。,經(jīng)濟（數(shù)理經(jīng)濟學）,Von Neumann 與對策論 1932年，Von Neumann提出一個廣義經(jīng)濟平衡模型；1939年，提出了一個屬于宏觀經(jīng)濟優(yōu)化的控制論模型；1944年，與Morgenstern共著的《對策論與經(jīng)濟行為》開創(chuàng)了對策論分支。 康托洛維奇與“生產(chǎn)組織與計劃中的數(shù)學方法” 30年代，蘇聯(lián)數(shù)理經(jīng)濟學家康托洛維奇從事生產(chǎn)組織與管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪稱運籌學的先驅(qū)著作－－《生產(chǎn)組織與計劃中的數(shù)學方法》，其思想和模型被歸入線性規(guī)劃范疇。,運籌學的性質(zhì)和特點,應用科學－“應用現(xiàn)有的科學技術(shù)知識和數(shù)學方法，解決實際中提出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)”。 運籌學的特點 定量化分析 多學科交叉，如綜合利用了心理學、經(jīng)濟學、物理、化學等方法 最優(yōu)決策,運籌學的研究對象,1）機器、工具、設(shè)備、人員等如何最佳利用問題 方法有：線性規(guī)劃、整數(shù)規(guī)劃、網(wǎng)絡圖、動態(tài)規(guī)劃、目標規(guī)劃等 2）競爭現(xiàn)象如戰(zhàn)爭、投資、商品競爭 方法是對策論 3）擁擠現(xiàn)象如公共汽車排隊、打電話、買東西、飛機著陸、船舶進港等 方法是排隊論,運籌學的工作步驟,1）提出和形成問題， 2）建立模型， 3）求解， 4）解的檢驗， 5）解的控制， 6）解的實施。,,第二章 線性規(guī)劃,線性規(guī)劃問題 線性規(guī)劃模型 線性規(guī)劃的求解------單純形方法,線性規(guī)劃問題,例1(廣告方式的選擇)中華家電公司推銷一種新型洗衣機,有關(guān)數(shù)據(jù)見下表.銷售部第一月的廣告預算為20000元,要求至少有8電視商業(yè)節(jié)目,15家報紙廣告/電視廣告費不得超過12000元,電臺廣播至少隔日有一次.現(xiàn)問該公司銷售部應當采用怎樣的廣告宣傳計劃,才能取得最好的效果?,表1-1,,,例2 長成家電公司準備將一種新型電視機在三家商場進行銷售，每一個商場的批發(fā)價和推銷費及產(chǎn)品的利潤如表所示。由于該電視機的性能良好，各商場都紛紛爭購，但公司每月的生產(chǎn)能力有限，只能生產(chǎn)1000臺，故公司規(guī)定：鐵路商場至少經(jīng)銷300臺，水上商場至少經(jīng)銷200臺，航空商場至少經(jīng)銷100臺，至多200臺。公司計劃在一個月內(nèi)的廣告預算費為8000元,推銷人員最高可用工時數(shù)為1500。同時，公司只根據(jù)經(jīng)銷數(shù)進行生產(chǎn)，試問公司下個月的市場對策？,表1-2,,,,,,求解--單純形法,將所給問題化為標準形 找出一個初始可行基,建立初始單純形表 檢查所有檢驗數(shù)(若全為非負,則已得到最優(yōu)解,計算停止.否則繼續(xù)下一步) 考察是否無解(若是,計算停止,否則繼續(xù)下一步) 確定入基變量,出基變量 對初始單純形表進行單純形變換,,,第三章 對偶問題和靈敏度分析,原問題,對偶問題,對偶性質(zhì),原問題與對偶問題互為對偶 原問題與對偶問題或都有最優(yōu)解(最優(yōu)值相同),兩最優(yōu)解之間存在一定的關(guān)系,或都 沒有最優(yōu)解 可知:研究對偶問題可以簡化計算(當原問題很復雜時,可先求解對偶問題,再根據(jù)一定的關(guān)系得出原問題的最優(yōu)解 提出了新的求解方法:對偶單純形法,對偶變量的經(jīng)濟解釋,對偶變量yi在經(jīng)濟上表示原問題第i種資源的邊際貢獻,即當?shù)趇種資源增加一個單位時,相應的目標值z的增量 對偶問題的最優(yōu)解yi*是原問題第i種資源的影子價格 應用:1.出租資源或設(shè)備時,租金價格的設(shè)定(至少高于該資源在企業(yè)內(nèi)的影子價格) 2.企業(yè)內(nèi)資源I的存量設(shè)定(當資源I的影子價格=市場價格時,可買進該資源;否則賣出) 3.調(diào)整資源的分配量以增加利潤,靈敏度分析,基本任務:確定參數(shù)的影響范圍,即保持某LP問題的最優(yōu)基不變的條件下該參數(shù)單獨變化的最大范圍 一個參數(shù)的影響范圍越小,最優(yōu)基對這一參數(shù)的變化就越敏感,最優(yōu)基對該參數(shù)而言就越不穩(wěn)定 另一個任務:當最優(yōu)解隨參數(shù)變化時如何簡便地求得新最優(yōu)解,第四章 運輸問題,,平衡運輸問題的模型,Min z= S.t.,平衡運輸問題的求解---表上作業(yè)法,找一個初始基可行解; 方法:最小元素法/Vogel近似法(VAM) 檢驗,若所有的檢驗數(shù)都小于零,最優(yōu)解已得,否則繼續(xù)下一步; 方法:位勢檢驗法 調(diào)整,得到一個新的基可行解,重復第二步. 方法:閉回路法,運輸問題的實例,東風電機公司接到上海一家商場(B1),青島一家商場(B2),西安一家商場(B3)各一份訂單,要求下月供應電機.B1的需求量為100臺,B2的需求量為80臺,而B3要求供應120臺.該公司在北京和武漢設(shè)有兩個倉庫(A1,A2),預計A1,A2下月的庫存量分別為200臺和150臺.已知每個倉庫到每家商場運送1 臺電機的費用如表所示.問該公司應如何調(diào)運電機,才能既滿足用戶的需要又使總的運費最少?,,第五章 指派問題,設(shè)有n 個人A1, A2, …An,要分派去做n件事B1, B2… Bn,要求每一件事都 必須有一個人去做,而且不同的事由不同的人去做.已知每個人Ai做每件事Bj的效率(如勞動工時或成本,或創(chuàng)造的價值等)為Cij,問應如何進行指派(哪個人做哪件事),才能使 工作效益最好(如工時最少,或成本最低,或創(chuàng)造的價值最大)? 指派問題既可以說是運輸問題的特殊情形,也可以說是整數(shù)規(guī)劃的特殊情形.,,指派問題的數(shù)學模型,Min z= S.t.,舉例,有4 個工人,要指派他們分別完成4 項工作,每人做各項工作所消耗的時間如下表:問如何指派使總的消耗時間最小?,第六章 目標規(guī)劃,多目標 的線性規(guī)劃問題(多目標 決策),而非單目標. 其模型是在線性模型的基礎(chǔ)上,利用正負偏差變量(d+,d-) 、優(yōu)先因子(pk,pkpk+1) 、權(quán)系數(shù),對同等級或不同等級的目標進行設(shè)置. 因其模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學模型結(jié)構(gòu)沒有本質(zhì)的區(qū)別,所以可用單純形法求解.,舉例,某商店有五位工作人員:經(jīng)理1人,主任1人,售貨員3人.有關(guān)情況見下表.設(shè)廣告費對銷售額的貢獻為其投入的15倍,各工作人員的收入相當于其完成銷售額的5.5%.問如何安排才能達到以下的目標:P1保證全體人員正常工作時間;P2 至少完成銷售額70000元;P3主任的月收入不少于1200元,售貨員A和B的月收入不少于600元和400元;P4 全體人員加班時間不超過規(guī)定; P5廣告費不超過3000元,力爭銷售額增加10000元,前者的重要性為后者的兩倍.,,第七章 整數(shù)規(guī)劃,最優(yōu)解不是分數(shù)或小數(shù),而是整數(shù)的情形. 整數(shù)規(guī)劃的一種特殊情形是0-1規(guī)劃,如指派問題. 整數(shù)規(guī)劃的解法有割平面法、分枝定界法。0-1規(guī)劃的解法有0-1隱枚舉法.,,整數(shù)規(guī)劃,純整數(shù)規(guī)劃,混合整數(shù)規(guī)劃,運用0-1規(guī)劃的實際問題,關(guān)于固定費用的問題 相互排斥的約束條件 投資場所的選定------相互排斥的計劃 例:某公司擬在市東、西、南三區(qū)建立門市部,擬議中有7個位置Ai（i=1,2, …7）可供選擇,規(guī)定:在東區(qū),由A1,A2,A3三個點中至多選兩個;在西區(qū),由A4,A5兩個點中至少選一個;在南區(qū),由A6,A7兩個點中至少選一個.如選用Ai點設(shè)備投資估計為bi元,每年可獲利潤估計為ci元,但投資總額不能超過B元,問如何選擇使年利潤最大?,建模,解:先引入0-1變量,令 于是:max z=,,Xi=,1,當Ai點被選用,0,當Ai點沒被選用,第八章 圖與網(wǎng)絡分析,著名哥尼斯堡七橋問題:歐拉(1736). 中國郵遞員問題：中國管梅谷（1962）,,C,D,,,,,,,,,,,,,,,,,A A C B D,B,,,,,,,,,,1,3,5,2,4,6,,網(wǎng)絡規(guī)劃問題 最小支撐樹問題 網(wǎng)絡最大流問題 最短路問題 最小費用流問題 將龐大復雜的工程系統(tǒng)和管理問題用圖描述,可以解決工程設(shè)計和管理決策的最優(yōu)化.問題.如,完成任務的時間最少,距離最短,費用最省等等.,第九章 網(wǎng)絡計劃(PERT技術(shù)),特別適用于生產(chǎn)技術(shù)復雜,工作項目繁多且聯(lián)系緊密的一些跨部門的工作計劃,如新產(chǎn)品開發(fā)、大型的工程項目.還可以應用在人力、物力、財力等資源的安排. 編制網(wǎng)絡計劃包括繪制網(wǎng)絡圖、計算時間參數(shù)、確定關(guān)鍵路線、網(wǎng)絡優(yōu)化等環(huán)節(jié).,第十章 動態(tài)規(guī)劃,解決多階段決策過程最優(yōu)化. 只是求解某類問題的一種方法,是考察問題的一種途徑,而不是一種特殊算法(如線性規(guī)劃是一種算法),因而沒有一個標準的數(shù)學表達式和明確定義的一組規(guī)則,必須對具體問題進行具體分析處理.,,動態(tài)規(guī)劃方法的基本思想,動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當?shù)倪吔鐥l件(即基本方程).所以,必須先將問題的過程分成幾個相互聯(lián)系的階段,恰當?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù),從而把一個大問題化成一族同類型的子問題,然后逐個求解.,動態(tài)規(guī)劃的應用------定價問題,例 :某廠要確定一種新產(chǎn)品在今后五年內(nèi)的價格,并已擬定只在5,6,7,8元這四種單價中進行選擇.據(jù)預測,今后五年不同價格下每年盈利(萬元)如下表所示,但是各相鄰年度價格不得超過1元.問今后五年內(nèi)每年定價各為多少,可預期五年總利潤最大?,上表,第十二章 決策論,決策過程 不確定型的決策 悲觀主義決策準則、樂觀主義決策準則、等可能性準則、最小機會損失準則、折衷主義準則 風險決策 最大期望值決策準則、最小機會損失決策準則,第十一章 對策論(博弈論),二人或多人競爭或?qū)够顒?基本概念:局中人、策略集、支付函數(shù) 矩陣對策記為:G=｛I,II;S1,S2;A｝或 G=｛ S1,S2;A｝,其中A為某局中人的支付矩陣. 矩陣對策的解法,