運(yùn)籌學(xué)導(dǎo)論第八緒論

演示文稿運(yùn)籌學(xué)導(dǎo)論第八版緒論當(dāng)前1頁，總共41頁。運(yùn)籌學(xué)導(dǎo)論第八版緒論ppt課件當(dāng)前2頁，總共41頁。3當(dāng)前3頁，總共41頁。4當(dāng)前4頁，總共41頁。51942年，BarnesWallis巴恩斯·沃利森就設(shè)計出了專門用來炸毀混凝土拱形水壩的專用炸彈，起名為“跳躍炸彈”。這種炸彈在水壩上游釋放，投放前先在炸彈架上賦予它500轉(zhuǎn)/分的自轉(zhuǎn)速度，炸彈投下后會像小孩玩石頭“打水漂”一樣，在水面上多次跳躍前進(jìn)，可以越過水壩前敷設(shè)的防彈網(wǎng)。在接觸水壩時，炸彈利用自身的旋轉(zhuǎn)，向水壩水線下深入，在水線下炸出大洞。拱形水壩一旦在支撐點上被炸毀，強(qiáng)大的水壓將使水壩立即潰決。當(dāng)前5頁，總共41頁。6中文：運(yùn)籌（夫運(yùn)籌帷幄之中，決勝于千里之外）——《史記?高祖本紀(jì)》英文：

OperationalResearch（英國）OperationsResearch（美國）

（直譯為“作戰(zhàn)研究”或“作業(yè)研究”、“運(yùn)作研究”）當(dāng)前6頁，總共41頁。7丁謂的皇宮修復(fù)工程運(yùn)籌學(xué)的起源北宋年間，丁謂負(fù)責(zé)修復(fù)焚毀的開封皇宮，他的施工方案是：Step1.先將工程皇宮前的一條大街挖成一條大溝，將大溝與汴水相通。Step2.使用挖出的土就地制磚，令與汴水相連形成的河道承擔(dān)繁重的運(yùn)輸任務(wù)；Step3.修復(fù)工程完成后，實施大溝排水，并將原廢墟物回填，修復(fù)成原來的大街。丁謂將取材、生產(chǎn)、運(yùn)輸及廢墟物的處理用“一溝三用”巧妙地解決了。當(dāng)前7頁，總共41頁。8田忌賽馬齊王與大臣田忌賽馬，雙方各出上、中、下馬各一匹，對局三次，每次勝負(fù)1000金。著名的軍事謀略家孫臏如何指導(dǎo)田忌的？齊王： 上 中 下

田忌： 下 上 中

最終凈勝一局，贏得1000金。當(dāng)前8頁，總共41頁。9北宋科學(xué)家、軍事家沈括,在率兵抗擊西夏征途中利用各兵種背負(fù)糧食的基本數(shù)據(jù)，盤算后勤兵與戰(zhàn)士在不同的行軍天數(shù)中的差異比例關(guān)系；盤算了用種種牲口運(yùn)糧與人力運(yùn)糧之間的利弊，做出了從敵國就地征糧，保障前線提供的決策。優(yōu)化后勤職員比例，增強(qiáng)了前線戰(zhàn)斗力。這種軍事運(yùn)籌是運(yùn)籌思想的典范，也是現(xiàn)代軍事運(yùn)籌的核心問題。沈括調(diào)整軍隊構(gòu)成當(dāng)前9頁，總共41頁。10運(yùn)籌學(xué)真正的發(fā)展起源于二次大戰(zhàn)的一門新興交叉學(xué)科與作戰(zhàn)問題相關(guān)雷達(dá)設(shè)置、運(yùn)輸船隊護(hù)航、反潛戰(zhàn)中深水炸彈起爆深度、飛行員編組、軍事物資存儲等戰(zhàn)后在經(jīng)濟(jì)、管理和機(jī)關(guān)學(xué)校及科研單位繼續(xù)研究1948年英國首先成立運(yùn)籌學(xué)會1952年，Morse和Kimball出版《運(yùn)籌學(xué)方法》1952年美國成立運(yùn)籌學(xué)會1959年成立國際運(yùn)籌學(xué)聯(lián)合會(IFORS)我國于1982年加入IFORS，并于1999年8月組織了第15屆大會當(dāng)前10頁，總共41頁。11PhilipM.Morse運(yùn)籌學(xué)發(fā)展的主要推動者WassilyW.Leontief投入產(chǎn)出法Dantzig,1914-2005單純形法VonNeumann,MonteCarlo方法JohnForbesNashJr博弈論當(dāng)前11頁，總共41頁。12運(yùn)籌學(xué)的內(nèi)容豐富，分支眾多。根據(jù)解決問題的主要特征可分兩大類：確定型和概率型。其中確定型包含：線性規(guī)劃，整數(shù)規(guī)劃，動態(tài)規(guī)劃，非線性規(guī)劃，多目標(biāo)決策及確定性存貯等；概率型中包含：回歸分析，決策論，對策論，排隊論，馬爾可夫鏈，圖論與網(wǎng)絡(luò)，概率存貯及搜索技術(shù)等。本課將闡述運(yùn)籌學(xué)中最基本的部分——規(guī)劃論（即線性規(guī)劃，對偶理論與靈敏度分析、整數(shù)規(guī)劃，網(wǎng)絡(luò)規(guī)劃）、排隊論運(yùn)籌學(xué)分支及模型類型當(dāng)前12頁，總共41頁。13運(yùn)籌學(xué)的研究問題與對象資源最佳利用問題方法：線性規(guī)劃、整數(shù)規(guī)劃、網(wǎng)絡(luò)圖、動態(tài)規(guī)劃、目標(biāo)規(guī)劃等競爭現(xiàn)象如戰(zhàn)爭、投資、商品競爭方法：對策論（博弈論）擁擠現(xiàn)象如公共汽車排隊、打電話、買東西、飛機(jī)著陸、船舶進(jìn)港等方法：排隊論當(dāng)前13頁，總共41頁。14運(yùn)籌學(xué)的關(guān)鍵在于模型的建立和使用；應(yīng)用運(yùn)籌學(xué)處理問題時，要從系統(tǒng)觀點來分析問題；提出需要解決的問題和希望達(dá)到的目標(biāo)；理清問題所處的環(huán)境和約束條件，包括：時間、地點、資金、原材料、設(shè)備、人力、能源、動力、信息、技術(shù)等；問題中的主要因素、各種環(huán)境和約束條件之間的邏輯關(guān)系運(yùn)籌學(xué)應(yīng)用前提當(dāng)前14頁，總共41頁。15運(yùn)籌學(xué)的發(fā)展趨勢運(yùn)籌學(xué)的危機(jī)脫離實際應(yīng)用，陷入數(shù)學(xué)陷阱IT對運(yùn)籌學(xué)的影響MIS,MRP-II,CIMS,ERPORDept.-->Dept.OfOR&IS運(yùn)籌學(xué)與行為科學(xué)結(jié)合群決策和談判、對策理論、多層規(guī)劃、合理性分析服務(wù)行業(yè)中的應(yīng)用金融服務(wù)業(yè)、信息、電信服務(wù)業(yè)、醫(yī)院管理當(dāng)前15頁，總共41頁。16研究深水炸彈起爆深度問題。當(dāng)飛機(jī)發(fā)現(xiàn)潛艇后，飛機(jī)何時投擲炸彈及炸彈的引爆引度是多少？運(yùn)籌學(xué)工作者對大量統(tǒng)計數(shù)字進(jìn)行認(rèn)真分析后，提出如下決策：僅當(dāng)潛艇浮出水面或剛下沉?xí)r，方投擲深水炸彈。炸彈的起爆深度為離水面25英尺（這是當(dāng)時深水炸彈所容許的最淺起爆點）。空軍采用上述決策后，所擊沉潛艇增加5倍。運(yùn)籌學(xué)的研究意義當(dāng)前16頁，總共41頁。17紐約消防車輛調(diào)度。都市求救電話是一個復(fù)雜的分布在不同地點的多個服務(wù)臺的排隊系統(tǒng)，涉及資源的空間配置、警車巡邏線路最優(yōu)設(shè)計、警力配備、電話調(diào)度；部署在紐約、圣迭戈、薩克拉門托、達(dá)拉斯、波特蘭、加拉加斯和鹿特丹。提高生產(chǎn)率10%~15%，特別是極大的降低了響應(yīng)時間。運(yùn)籌學(xué)的研究意義當(dāng)前17頁，總共41頁。18假設(shè)有70艘油輪向70個港口運(yùn)貨，已知每艘油輪駛向每個港口的費(fèi)用，油輪公司需制訂出最優(yōu)運(yùn)輸方案。采用全枚舉法（窮舉法）需計算方案數(shù)為70!(大于10100

）；IBM公司生產(chǎn)的大計算機(jī)1秒種大約可算出1012（即1000億）個方案。若要算出全部方案，則需調(diào)用占有空間為1050個地球一樣大的計算機(jī)計算幾百億年以上。而在這種大機(jī)器上用線性規(guī)劃的單純形法計算只需幾秒鐘（這是整數(shù)規(guī)劃問題）。運(yùn)籌學(xué)的研究意義運(yùn)籌學(xué)是研究從眾多方案（甚至無限多方案）中選擇最優(yōu)方案的技術(shù)，那么在當(dāng)代計算機(jī)技術(shù)迅速發(fā)展的今天，這種優(yōu)化技術(shù)是否會喪失其重要性？當(dāng)前18頁，總共41頁。19運(yùn)籌學(xué)的研究意義新型計算機(jī)的出現(xiàn)，不能代替運(yùn)籌學(xué)優(yōu)化需求。運(yùn)籌學(xué)與計算機(jī)科學(xué)及其它科學(xué)結(jié)合應(yīng)用，可以將人解放出來，產(chǎn)生更好的實施效果。

當(dāng)前19頁，總共41頁。20運(yùn)籌學(xué)在工程和商業(yè)管理的應(yīng)用:生產(chǎn)計劃：生產(chǎn)作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等；庫存管理：多種物資庫存量的管理，庫存方式、庫存量等；運(yùn)輸問題：確定最小成本的運(yùn)輸線路、物資的調(diào)撥、運(yùn)輸

工具的調(diào)度以及建廠地址的選擇等；人事管理：對人員的需求和使用的預(yù)測，確定人員編制、人員合理分配，建立人才評價體系等；市場營銷：廣告預(yù)算、媒介選擇、定價、產(chǎn)品開發(fā)與銷售計劃制定等；財務(wù)會計：預(yù)測、貸款、成本分析、定價、證券管理、

現(xiàn)金管理等；當(dāng)前20頁，總共41頁。21公司實施手段每年節(jié)支聯(lián)合航空滿足乘客需求前提下，以最低成本進(jìn)行訂票及安排機(jī)場工作班次600萬Citgo石油優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送及營銷7000萬荷馬特發(fā)展優(yōu)化商業(yè)區(qū)和辦公樓銷售程序4000萬AT&T優(yōu)化商業(yè)用戶的電話銷售中心選址4.06億標(biāo)準(zhǔn)品牌制定最優(yōu)再訂購點和訂購量，確保安全庫存380萬施樂通過戰(zhàn)略調(diào)整，縮短維修機(jī)器的反應(yīng)時間和改進(jìn)維修人員的生產(chǎn)率提高生產(chǎn)率50%寶潔重新設(shè)計北美生產(chǎn)和分銷系統(tǒng)以降低成本并加快了市場進(jìn)入速度2億法國鐵路制定最優(yōu)鐵路時刻表并調(diào)整鐵路日運(yùn)營量1500萬Delta航空進(jìn)行上千個國內(nèi)航線的飛機(jī)優(yōu)化配置來最大化利潤1億IBM重組全球供應(yīng)鏈，保持最小庫存同時滿足客戶需求7.5億當(dāng)前21頁，總共41頁。22本課程課程背景、教材、參考書

先修課：高等數(shù)學(xué)，概率與統(tǒng)計、線性代數(shù)1.教材：HamdyA.Taha,運(yùn)籌學(xué)導(dǎo)論（第8版），郵電出版社，20072．參考書：希利爾，利伯曼，運(yùn)籌學(xué)導(dǎo)論（第9版）,清華大學(xué)出版社,2010運(yùn)籌與管理（運(yùn)籌學(xué)50周年紀(jì)念特刊），2004傅家良，運(yùn)籌學(xué)方法與模型，復(fù)旦大學(xué)出版社，2006胡運(yùn)權(quán)，運(yùn)籌學(xué)教程，清華大學(xué)出版社出版，2007．當(dāng)前22頁，總共41頁。23國際著名運(yùn)籌學(xué)刊物：InterfacesManagementScienceOperationsResearchEuropeanJournalofOperationsResearchTransportationScienceMathematicsofOperationsResearchOperationsResearchLettersMathematicalProgramming當(dāng)前23頁，總共41頁。24本課程特點及要求目的：不僅掌握優(yōu)化理論方法的專業(yè)知識，更重要的是提高分析問題和解決問題的能力。方法：強(qiáng)調(diào)思路、觀點及弄清物理概念，掌握一定的理論推導(dǎo)能力，但不搞純數(shù)學(xué)公式。避免2種傾向：只羅列方法，不講本質(zhì)；或只追求數(shù)學(xué)推導(dǎo)，掩蓋物理概念。當(dāng)前24頁，總共41頁。25本課程授課方式與考核

本課程授課方式：對話式教學(xué)

作業(yè)：計算機(jī)編程或者軟件操作

考核：課程設(shè)計(匯報24%+報告36%)+期末考試成績（40%）當(dāng)前25頁，總共41頁。26緒論線性規(guī)劃建模單純形法與敏感性分析對偶與后最優(yōu)分析運(yùn)輸模型網(wǎng)絡(luò)模型整數(shù)線性規(guī)劃排隊論本課程授課內(nèi)容當(dāng)前26頁，總共41頁。27第1章什么是運(yùn)籌學(xué)當(dāng)前27頁，總共41頁。28設(shè)想你需要完成一項工作任務(wù)，需要5周完成，期間需要往返于Fayetteville（FYV）與Denver（DEN）之間，每個星期一你都要乘飛機(jī)從Fayetteville出發(fā)，星期三返回，普通的往返機(jī)票是400美元，但是如果購買跨周末的往返機(jī)票，可以享受20%的折扣，如果是單程的機(jī)票則為往返票的75%，那么如何購買這5周的機(jī)票？有哪些可能的決策方案？決策受到哪些限制條件？評價這些方案的標(biāo)準(zhǔn)是什么？1.1運(yùn)籌學(xué)模型當(dāng)前28頁，總共41頁。29購買5張普通的FYV-DEN-FYV往返機(jī)票，每周一出發(fā)，周三返回；購買1張F(tuán)YV-DEN單程機(jī)票，4張跨周末的DEN-FYV-DEN往返機(jī)票，再買1張DEN-FYV單程；先購買1張第一周星期一出發(fā)，最后一周星期三返程的FYV-DEN-FYV往返機(jī)票，再買4張跨周末的DEN-FYV-DEN往返機(jī)票。該方案使得所有機(jī)票都至少跨越一個周末。所有方案的約束條件：必須周一從FYV出發(fā)，在本周的星期三返回。有哪些可能的決策方案？當(dāng)前29頁，總共41頁。30評價所提出的各種方案好壞標(biāo)準(zhǔn)是購買這些機(jī)票的總費(fèi)用，花費(fèi)最少的方案最佳。方案1的費(fèi)用=5×400=$2000方案2的費(fèi)用=0.75×400+4×(400×0.8)+0.75×400=$1880方案3的費(fèi)用=5×(400×0.8)=$1600所以，應(yīng)該選擇方案三上例表明，運(yùn)籌學(xué)模型的3個主要構(gòu)成：備選方案目標(biāo)評判標(biāo)準(zhǔn)約束條件3個備選方案花費(fèi)最少周一去周三回當(dāng)前30頁，總共41頁。31

考慮長度為L的電線圍成一個矩形，要使得該矩形面積最大，長度和寬度如何選??？

令w=矩形的長；h=矩形的寬.則限制條件可以敘述為

(1)矩形長+矩形寬=電線長度一半；(2)長寬不能為負(fù)值以數(shù)學(xué)形式表示為

(1)2(w+h)=L；(2)w≥0,h≥0

問題的目標(biāo)（評判的標(biāo)準(zhǔn)），即矩形面積最大，令z為矩形的面積，模型變?yōu)镸axz=wh

St.2(w+h)=L；w,h≥0w=h=L/4對于可能的方案數(shù)是無限的情形，必須需要最優(yōu)化模型！當(dāng)前31頁，總共41頁。32

從上面的例子，可以歸納出一般的運(yùn)籌學(xué)模型具有以下通用的格式：max或min

目標(biāo)函數(shù)St.(Subjectto)約束條件一個模型的解若滿足所有約束條件，則解是可行的(feasible)；如果既是可行的，又取得了目標(biāo)的最佳（最大或最?。┲?，則解是最優(yōu)的(optimal).在購票的例子中3個方案是可行的，第三方案是最優(yōu)的。構(gòu)造矩形的例子中，可行方案要滿足w+h=L/2，w和h非負(fù)，則有無窮多的可行解。當(dāng)前32頁，總共41頁。33雖然運(yùn)籌學(xué)的模型是在一組約束條件下，使得某一具體的目標(biāo)評判標(biāo)準(zhǔn)達(dá)到最優(yōu)，但是它所得出的解的質(zhì)量取決于模型對實際問題刻畫的完全性。以購機(jī)票問題為例，假如我們不能找到所有的方案的話，那么所得到的解只相對于所選模型是最優(yōu)的。例如方案3沒有在模型中，則“最優(yōu)”解就要用1880美元，這是一個次最優(yōu)（suboptimal）解。因此，一個模型的“最優(yōu)”解只是對這個模型是最好的，當(dāng)模型完全的表達(dá)了實際問題時，他的解對實際才是最優(yōu)的。當(dāng)前33頁，總共41頁。341.2運(yùn)籌學(xué)模型的求解在OR中，沒有一種萬能的技術(shù)能求解出實踐中所有的數(shù)學(xué)模型；在OR中，常用的技術(shù)有：線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、網(wǎng)絡(luò)規(guī)劃、非線性規(guī)劃等，除此之外還有很多運(yùn)籌學(xué)方法。運(yùn)籌學(xué)的問題解通常不是某種解析式形式的，需要反復(fù)迭代，逐步向最優(yōu)解靠近，每步迭代的計算規(guī)則是一致的，這需要計算機(jī)來計算。對于非常復(fù)雜的數(shù)學(xué)模型，可能必須放棄最優(yōu)解，可能利用某些啟發(fā)式算法或經(jīng)驗方法，找到較好的解（非最優(yōu)的）。當(dāng)前34頁，總共41頁。351.3排隊模型和模擬模型排隊模型和模擬模型用于研究等待隊列，他們不屬于最優(yōu)化技術(shù)，而是用來度量等待隊列的性能，例如隊長、等待時間、設(shè)施利用率等；排隊論基于各種概率分布采用概率論隨機(jī)模型分析隊列，而模擬可以分析任何排隊情形，是觀察實際系統(tǒng)最好的方法；建立模擬模型的過程非常費(fèi)時費(fèi)力，計算過程非常耗時。當(dāng)前35頁，總共41頁。361.4建模的藝術(shù)運(yùn)籌學(xué)的建模過程實際上是對現(xiàn)實問題的抽象和近似。我們應(yīng)該把研究的重點聚焦在控制實際系統(tǒng)行為的主要變量上，從現(xiàn)實世界中抽象出假定的實際系統(tǒng)?，F(xiàn)實世界假設(shè)現(xiàn)實世界模型當(dāng)前36頁，總共41頁。37Tyko制造公司生產(chǎn)各種塑料容器制品，當(dāng)生產(chǎn)訂單到達(dá)生產(chǎn)部門的時候，必要的原材料要從公司庫存或采購。完成生產(chǎn)后，銷售部門負(fù)責(zé)向客戶分銷產(chǎn)品。問題：生產(chǎn)批量應(yīng)該是多少？如何用模型來表達(dá)？許多變量都可以直接表示生產(chǎn)水平，下面是各部門的變量：生產(chǎn)部門：機(jī)器數(shù)、工人工作時間、半成品庫存、質(zhì)量控制標(biāo)準(zhǔn)表示的生產(chǎn)能力；原材料部門：原材料庫存量、采購供貨安排、庫存限量銷售部門：銷售預(yù)測、分銷網(wǎng)能力、廣告促銷能力、競爭水平。這些變量均影響生產(chǎn)量，建立上述所有因素的模型極為困難當(dāng)前37頁，總共41頁。38第一個抽象水平需要定義出假定實際系統(tǒng)的邊界。通過分析，可以用下面兩個主要變量來近似描述實際系統(tǒng)：

生產(chǎn)率

(2)消費(fèi)率計算生產(chǎn)率要用到生產(chǎn)能力、質(zhì)量控制標(biāo)準(zhǔn)、現(xiàn)有原材料等變量；消費(fèi)率則可以從與銷售部門有關(guān)的變量計算。本質(zhì)上，從現(xiàn)實世界到假定現(xiàn)實世界的簡化，是通過多個現(xiàn)實世界變量“簡化”成為單一的假定現(xiàn)實世界變量來實現(xiàn)的。利用生產(chǎn)率和消費(fèi)率，就可以建立起庫存剩余和不足的度量