運(yùn)籌學(xué)緒論課件

運(yùn)籌學(xué)授課：趙秀霞2014.3田忌賽馬上等馬中等馬下等馬上等馬中等馬下等馬齊王田忌上等馬中等馬下等馬上等馬中等馬下等馬齊王田忌田忌賽馬丁渭修復(fù)皇宮皇宮遺址各種建筑用材料宮前大街護(hù)城河護(hù)城河灌水成渠灌水成渠挖土成磚丁渭修復(fù)皇宮皇宮宮前大街護(hù)城河護(hù)城河引水入河引水入河廢磚修街《大英百科全書(shū)》釋義 “運(yùn)籌學(xué)是一門(mén)應(yīng)用于管理有組織系統(tǒng)的科學(xué)”，“運(yùn)籌學(xué)為掌管這類(lèi)系統(tǒng)的人提供決策目標(biāo)和數(shù)量分析的工具”《中國(guó)大百科全書(shū)》釋義“用數(shù)學(xué)方法研究經(jīng)濟(jì)、民政和國(guó)防等部門(mén)在內(nèi)外環(huán)境的約束條件下合理分配人力、物力、財(cái)力等資源，使實(shí)際系統(tǒng)有效運(yùn)行的技術(shù)科學(xué)．它可以用來(lái)預(yù)測(cè)發(fā)展趨勢(shì)．制定行動(dòng)規(guī)劃或優(yōu)選可行方案”《辭海》釋義“主要研究經(jīng)濟(jì)活動(dòng)與軍事活動(dòng)中能用數(shù)量來(lái)表達(dá)有關(guān)運(yùn)用、籌劃與管理方面的問(wèn)題．它根據(jù)問(wèn)題的要求，通過(guò)數(shù)學(xué)的分析與運(yùn)算，作出綜合性的合理安排．以達(dá)到較經(jīng)濟(jì)較有效地使用人力物力?！薄吨袊?guó)企業(yè)管理百科全書(shū)》釋義“應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。”運(yùn)籌學(xué)的來(lái)源正式使用－－在二戰(zhàn)期間解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題：如何合理運(yùn)用雷達(dá)有效地對(duì)付德國(guó)空襲；對(duì)商船隊(duì)如何進(jìn)行編隊(duì)護(hù)航；反潛深水炸彈在各種情況下如何調(diào)整其爆炸深度。運(yùn)籌學(xué)的來(lái)源名稱(chēng)－－英國(guó)稱(chēng)為Operationalresearch，美國(guó)稱(chēng)為operationsresearch(縮寫(xiě)為O．R．)我國(guó)從1957年開(kāi)始譯作運(yùn)籌學(xué)運(yùn)籌學(xué)的發(fā)展一、從l945年到50年代初，被稱(chēng)為創(chuàng)建時(shí)期。第一本運(yùn)籌學(xué)雜志《運(yùn)籌學(xué)季刊》(O．R．Quarterly)1950年于英國(guó)創(chuàng)刊，第一個(gè)運(yùn)籌學(xué)會(huì)英國(guó)運(yùn)籌學(xué)會(huì)于1948年成立。運(yùn)籌學(xué)的發(fā)展二、50年代初期到50年代末期，被認(rèn)為是運(yùn)籌學(xué)的成長(zhǎng)時(shí)期。最早建立運(yùn)籌學(xué)會(huì)的國(guó)家是英國(guó)（1948），接著是美國(guó)（1952），法國(guó)（1956），日本和印度（1957）。我國(guó)的運(yùn)籌學(xué)會(huì)建立在1980年。最初是50年代中期由錢(qián)學(xué)森，許國(guó)志等教授引入我國(guó)。三、自60年代以來(lái)，認(rèn)為是運(yùn)籌學(xué)迅速發(fā)展和開(kāi)始普及的時(shí)期。運(yùn)籌學(xué)的應(yīng)用一、市場(chǎng)營(yíng)銷(xiāo)二、生產(chǎn)計(jì)劃三、庫(kù)存管理四、運(yùn)輸問(wèn)題五、財(cái)政和會(huì)計(jì)運(yùn)籌學(xué)的應(yīng)用六、人事管理七、設(shè)備維修、更新、項(xiàng)目選擇、評(píng)價(jià)和可靠性分析八、工程的優(yōu)化設(shè)計(jì)九、計(jì)算機(jī)和信息系統(tǒng)十、城市管理運(yùn)籌學(xué)的發(fā)展方向一、運(yùn)籌學(xué)應(yīng)用二、運(yùn)籌科學(xué)三、運(yùn)籌數(shù)學(xué)運(yùn)籌學(xué)研究的基本特征系統(tǒng)的整體觀念－－運(yùn)籌學(xué)研究中不是對(duì)各子系統(tǒng)的決策行為孤立評(píng)價(jià)，而把有關(guān)子系統(tǒng)相互關(guān)聯(lián)的決策結(jié)合起來(lái)考慮，把相互影響和制約的各個(gè)方面作為一個(gè)統(tǒng)一體．從系統(tǒng)整體利益出發(fā)，尋找了個(gè)優(yōu)化協(xié)調(diào)的方案。運(yùn)籌學(xué)研究的基本特征多學(xué)科的綜合－－運(yùn)籌學(xué)研究中吸收來(lái)自不同領(lǐng)域、具有不同經(jīng)驗(yàn)和技能的專(zhuān)家。模型方法的應(yīng)用－－運(yùn)籌學(xué)研究的系統(tǒng)不能搬到實(shí)驗(yàn)室來(lái)，而是建立這個(gè)問(wèn)題的數(shù)學(xué)和模擬的模型。制定決策是運(yùn)籌學(xué)應(yīng)用的核心建立模型則是運(yùn)籌學(xué)方法的精髓運(yùn)籌學(xué)研究的基本方法一、分析和表述問(wèn)題1、確定決策目標(biāo)，明確主要決策什么；2、要辨認(rèn)哪些是決策的關(guān)鍵影響因素，在選取這些關(guān)鍵因素時(shí)存在哪些資源和環(huán)境的限制；3、列出表述問(wèn)題的各種基本要素，并確定優(yōu)化和改進(jìn)方案的目標(biāo)是什么。運(yùn)籌學(xué)研究的基本方法二、建立模型三、求解模型和優(yōu)化方案四、對(duì)模型和由模型導(dǎo)出的解進(jìn)行檢驗(yàn)五、建立起對(duì)解的有效控制

確定最優(yōu)解保持穩(wěn)定時(shí)的參數(shù)變化范圍。

六、方案的實(shí)施

運(yùn)籌學(xué)的模型模型——是研究者對(duì)客觀現(xiàn)實(shí)經(jīng)過(guò)思維抽象后用文字、圖表、符號(hào)、關(guān)系式以及實(shí)體模樣描述所認(rèn)識(shí)到的客觀對(duì)象。運(yùn)籌學(xué)的模型模型有三種基本形式：形象模型模擬模型符號(hào)或數(shù)學(xué)模型構(gòu)模的方法和思路直接分析法應(yīng)用已有模型：運(yùn)籌學(xué)中的線(xiàn)性規(guī)劃模型、投入產(chǎn)出模型、排隊(duì)模型、決策和對(duì)策模型等。類(lèi)比法不同系統(tǒng)之間的類(lèi)同現(xiàn)象，類(lèi)比構(gòu)模。如物理學(xué)中的機(jī)械系統(tǒng)、氣體動(dòng)力學(xué)系統(tǒng)、水力學(xué)系統(tǒng)、熱力學(xué)系統(tǒng)及電路系統(tǒng)之間就有不少彼此類(lèi)同的現(xiàn)象。構(gòu)模的方法和思路數(shù)據(jù)分析法

依據(jù)大量數(shù)據(jù)用統(tǒng)計(jì)分析法建模。試驗(yàn)分析法

通過(guò)局部試驗(yàn)數(shù)據(jù)加上分析來(lái)構(gòu)造模型。想定（構(gòu)想）法

在已有的知識(shí)、經(jīng)驗(yàn)和某些的基礎(chǔ)上，對(duì)于將來(lái)可能發(fā)生的情況給出邏輯上合理的設(shè)想和描述，然后用已有的方法構(gòu)造模型，并不斷修正完善，直至比較滿(mǎn)意為止。運(yùn)籌學(xué)主要分支簡(jiǎn)介一、線(xiàn)性規(guī)劃(Linearprogramming)二、非線(xiàn)性規(guī)劃(nonlinearprogramming)三、動(dòng)態(tài)規(guī)劃(dynamicprogramming)四、圖與網(wǎng)絡(luò)分析(graphtheoryandnetworkanalysis)五、存貯論(inventorytheory)六、排隊(duì)論(queueingtheory,orwaitingline)七、對(duì)策論(gametheory)八、決策論(decisiontheory)運(yùn)籌學(xué)主要分支簡(jiǎn)介一、線(xiàn)性規(guī)劃(Linearprogramming)

用數(shù)學(xué)語(yǔ)言表達(dá)統(tǒng)籌問(wèn)題，先根據(jù)問(wèn)題要達(dá)到的目標(biāo)選取適當(dāng)?shù)淖兞?，?wèn)題的目標(biāo)通過(guò)用變量的函數(shù)形式來(lái)表示（稱(chēng)為目標(biāo)函數(shù)），對(duì)問(wèn)題的限制條件用有關(guān)變量的等式或不等式表達(dá)（稱(chēng)為約束條件）。當(dāng)變量連續(xù)取值，且目標(biāo)函數(shù)和約束條件均為線(xiàn)性時(shí)，稱(chēng)這類(lèi)模型為線(xiàn)性規(guī)劃的模型。

用線(xiàn)性規(guī)劃求解的典型問(wèn)題由運(yùn)輸問(wèn)題、生產(chǎn)計(jì)劃問(wèn)題、下料問(wèn)題、混合配料問(wèn)題等。線(xiàn)性規(guī)劃問(wèn)題某醫(yī)院護(hù)士值班班次、每班工作時(shí)間及各班所需護(hù)士數(shù)如表1—19所示。每班護(hù)士值班開(kāi)始時(shí)向病房報(bào)到，并連續(xù)工作8小時(shí)。試決定該醫(yī)院最少需多少名護(hù)士，以滿(mǎn)足輪班需要？運(yùn)籌學(xué)主要分支簡(jiǎn)介二、非線(xiàn)性規(guī)劃(nonlinearprogramming)

如果現(xiàn)行規(guī)劃建模中的目標(biāo)函數(shù)或者是約束條件不全是線(xiàn)性的，對(duì)這類(lèi)模型的研究構(gòu)成非線(xiàn)性規(guī)劃的分枝。由于大多數(shù)工程物理量的表達(dá)式是非線(xiàn)性的，因此非線(xiàn)性規(guī)劃在各類(lèi)工程的優(yōu)化設(shè)計(jì)中得到較多應(yīng)用。它是優(yōu)化設(shè)計(jì)的有力工具。非線(xiàn)性規(guī)劃問(wèn)題某工地有4個(gè)工點(diǎn)，各工點(diǎn)的位置及對(duì)混凝土的需求量列入下表，現(xiàn)需建一中心混凝土攪拌站，以供給各工點(diǎn)所需要的混凝土，要求混凝土的總運(yùn)輸量（運(yùn)量×運(yùn)距）最小，試決定攪拌站的位置？工點(diǎn)的位置（x1，y1）（x2，y2）（x3，y3）（x4，y4）混凝土需要量Q1Q2Q3Q4運(yùn)籌學(xué)主要分支簡(jiǎn)介三、動(dòng)態(tài)規(guī)劃(dynamicprogramming)

動(dòng)態(tài)規(guī)劃研究多階段決策過(guò)程最優(yōu)化。有些經(jīng)營(yíng)管理活動(dòng)由一系列相互關(guān)聯(lián)的階段組成，在每個(gè)階段一次進(jìn)行決策，而且上一階段的輸出狀態(tài)就是下一階段的輸入狀態(tài)，各階段決策之間互相管理，因此構(gòu)成一個(gè)多階段的決策過(guò)程。

動(dòng)態(tài)規(guī)劃研究多階段決策過(guò)程的總體優(yōu)化，即從系統(tǒng)總體出發(fā)，要求各階段決策所構(gòu)成的決策序列使目標(biāo)函數(shù)值達(dá)到最優(yōu)。動(dòng)態(tài)規(guī)劃問(wèn)題某公司打算在3個(gè)不同地區(qū)設(shè)置4個(gè)銷(xiāo)售點(diǎn)，根據(jù)市場(chǎng)預(yù)測(cè)部門(mén)估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷(xiāo)售站，每月可得利潤(rùn)如表7—21所示，試問(wèn)應(yīng)如何在各地區(qū)設(shè)置銷(xiāo)售站，可使每月總利潤(rùn)最大？運(yùn)籌學(xué)主要分支簡(jiǎn)介四、圖與網(wǎng)絡(luò)分析(graphtheoryandnetworkanalysis)

運(yùn)籌學(xué)中把一些研究對(duì)象用節(jié)點(diǎn)表示，對(duì)象之間的聯(lián)系用連線(xiàn)表示，用點(diǎn)、線(xiàn)的集合構(gòu)成圖。根據(jù)研究的具體網(wǎng)絡(luò)對(duì)象，賦予圖中各邊某個(gè)具體的參數(shù)，如時(shí)間、流量、費(fèi)用、距離等，規(guī)定圖中各節(jié)點(diǎn)代表具體網(wǎng)絡(luò)中任何一種流動(dòng)的起點(diǎn)、中轉(zhuǎn)點(diǎn)或終點(diǎn)，然后利用圖論方法來(lái)研究各類(lèi)網(wǎng)絡(luò)結(jié)構(gòu)和流量的優(yōu)化分析。

工序間的合理銜接搭配問(wèn)題，設(shè)計(jì)中遇到研究各種管道、線(xiàn)路的通過(guò)能力，以及倉(cāng)庫(kù)、附屬設(shè)施的布局等問(wèn)題。圖與圖絡(luò)分析求解如圖8—55所示的中國(guó)郵路問(wèn)題，A點(diǎn)是郵局。運(yùn)籌學(xué)主要分支簡(jiǎn)介五、存貯論(inventorytheory)

存貯策略研究在不同需求、供貨及到達(dá)方式等情況下，確定在什么時(shí)間點(diǎn)訂貨，以及一次提出多大的批量，使用于訂購(gòu)、儲(chǔ)存和可能發(fā)生短缺的費(fèi)用的總和為最少。

存貯論對(duì)某種電子元件每月需求量為4000件，每件成本為150元，每年的存貯費(fèi)為成本的10％，每次訂購(gòu)費(fèi)為500元。求：(1)不允許缺貨條件下的最優(yōu)存貯策略；(2)允許缺貨(缺貨費(fèi)為每件每年100元)條件下的最優(yōu)存貯策略。運(yùn)籌學(xué)主要分支簡(jiǎn)介六、排隊(duì)論(queueingtheory,orwaitingline)

排隊(duì)輪研究顧客不同輸入、各類(lèi)服務(wù)時(shí)間的分布、不同服務(wù)員數(shù)及不同排隊(duì)規(guī)則情況下，排隊(duì)系統(tǒng)的工作性能和狀態(tài)，設(shè)計(jì)新的排隊(duì)系統(tǒng)及改進(jìn)現(xiàn)有系統(tǒng)的性能提供數(shù)量依據(jù)。

排隊(duì)論某店僅有一個(gè)修理工人，顧客到達(dá)過(guò)程為Poisson流，平均每小時(shí)3人，修理時(shí)間服從負(fù)指數(shù)分布，平均需10分鐘。求：(1)店內(nèi)空閑的概率；(2)有4個(gè)顧客的概率；(3)至少有1個(gè)顧客的概率；(4)店內(nèi)顧客的平均數(shù)；(5)等待服務(wù)的顧客的平均數(shù)(6)平均等待修理時(shí)間；對(duì)策論七、對(duì)策論

(gametheory)對(duì)策論用于研究具有對(duì)抗局勢(shì)的模型。在這類(lèi)模型中，參與對(duì)抗的各方成為局中人，每個(gè)局中人均有一組策略可供選擇，當(dāng)各局中人分別采取不同策略時(shí)，對(duì)應(yīng)一個(gè)收益或需要支付的函數(shù)。對(duì)策論為局中人在高度不確定和充滿(mǎn)競(jìng)爭(zhēng)的環(huán)境中提供一套完整的、定量化和程序化的選擇策略的理論和方法。

對(duì)策論已應(yīng)用于商品、消費(fèi)者、生產(chǎn)者之間的供求平衡分析，利益集團(tuán)的協(xié)商和談判，以及軍事上各種作戰(zhàn)模型的研究等。對(duì)策論“二指莫拉問(wèn)題”，甲、乙二人游戲，每人出一個(gè)或兩個(gè)手指，同時(shí)又把猜測(cè)對(duì)方所出的指數(shù)叫出來(lái)。如果只有一個(gè)人猜測(cè)正確，則他的贏得分?jǐn)?shù)為二人所出指數(shù)之和、否則重新開(kāi)始。試寫(xiě)出該對(duì)策中各局中人的策略集及甲的贏得矩陣，并說(shuō)明是否存在某一種策略比其它策略更有利。決策論八、決策論(decisiontheory)決策是指為最優(yōu)的達(dá)到目標(biāo)，依據(jù)一定準(zhǔn)則，對(duì)若干備選方案進(jìn)行選擇。決策論是對(duì)整個(gè)決策過(guò)程中涉及方案目標(biāo)選取、度量、概率值確定、效用值計(jì)算，一直到最優(yōu)方案和策略選取的有關(guān)科學(xué)理論。決策論根據(jù)以往的資料，一家面包店每天所需面包數(shù)(當(dāng)天市場(chǎng)需求量)可能是下列當(dāng)中的某一個(gè)，100，150，200，250，300，但其概率分布不知道。如果一個(gè)面包當(dāng)天沒(méi)有賣(mài)掉，則可在當(dāng)天結(jié)束時(shí)每個(gè)0.15元處理掉。新鮮面包每個(gè)售價(jià)為0.49元，成本為0.25元，假設(shè)進(jìn)貨量限制在需求量中的某一個(gè)，要求：(1)做出面包進(jìn)貨問(wèn)題的決策矩陣；(2)分別用處理不確定性決策