川大《運(yùn)籌學(xué)》課件-序論0

1、運(yùn) 籌 帷 幄 之 中決 勝 千 里 之 外運(yùn) 籌 學(xué) 課 件緒 論Introduction運(yùn)籌學(xué)的概況最優(yōu)化模型教學(xué)計(jì)劃與方法 緒 論運(yùn)籌學(xué)的由來(lái)與發(fā)展運(yùn)籌學(xué)的性質(zhì)與特點(diǎn) 運(yùn)籌學(xué)的主要內(nèi)容運(yùn)籌學(xué)的發(fā)展趨勢(shì)運(yùn)籌學(xué)的學(xué)科地位運(yùn) 籌 學(xué) 概 況名稱(chēng)的由來(lái) Operation Research 運(yùn)籌帷幄 “史記” 運(yùn)作研究發(fā)展歷程 運(yùn)籌學(xué)的由來(lái)與發(fā)展二戰(zhàn)以前萌芽二戰(zhàn)期間產(chǎn)生五六十年代發(fā)展七八十年代成熟一、運(yùn)籌學(xué)的起源（國(guó)內(nèi)、國(guó)外）：國(guó)外：1938年，英國(guó)為解決空襲的早期預(yù)警，做好反侵略戰(zhàn)爭(zhēng)準(zhǔn)備，大量使用雷達(dá)，隨著雷達(dá)的使用，出現(xiàn)了來(lái)自不同雷達(dá)站的信息及雷達(dá)站同整個(gè)防空作戰(zhàn)系統(tǒng)的協(xié)調(diào)問(wèn)題。1938年7

2、月，Bawdsey雷達(dá)站的負(fù)責(zé)人A.P.Rowe（羅伊）提出立即進(jìn)行整個(gè)防空作戰(zhàn)系統(tǒng)運(yùn)行的研究，1939年，以英國(guó)的物理學(xué)家，時(shí)任英國(guó)戰(zhàn)斗機(jī)司令部科學(xué)顧問(wèn)的Blackett為首，聯(lián)合心理學(xué)家、數(shù)學(xué)家、應(yīng)用數(shù)學(xué)家、天文物理學(xué)家、海軍陸軍軍官組成了一個(gè)代號(hào)“Blackett馬戲團(tuán)”的研究小組，專(zhuān)門(mén)就改進(jìn)防空系統(tǒng)進(jìn)行研究。在他們的報(bào)告中使用了“Operational Research”一詞，這便是我們所說(shuō)的運(yùn)籌學(xué)。國(guó)內(nèi)：國(guó)內(nèi)最早的運(yùn)籌學(xué)思想源于齊王與田忌賽馬。 系統(tǒng)的整體優(yōu)化、 多學(xué)科的配合、 模型方法的應(yīng)用系統(tǒng)的整體優(yōu)化：所謂系統(tǒng)即是由相互關(guān)聯(lián)、相互制約、相互作用的一些部分組成的具有某種功能的有機(jī)

3、整體。而運(yùn)籌學(xué)不是對(duì)每一個(gè)決策行為孤立的進(jìn)行評(píng)價(jià)，而是把它同系統(tǒng)內(nèi)所有其他重要的相互作用結(jié)合起來(lái)作出評(píng)價(jià)，把相互影響的各方面作為一個(gè)統(tǒng)一體，從總體利益出發(fā)，尋找一個(gè)優(yōu)化方案。運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)多學(xué)科的配合：一個(gè)企業(yè)的有效管理涉及到很多方面，運(yùn)籌學(xué)的研究要吸收不同領(lǐng)域、不同學(xué)科的知識(shí)和技術(shù)。模型方法的應(yīng)用：1。分析與表述問(wèn)題：2。建立模型：3。對(duì)問(wèn)題求解：4。對(duì)模型和由模型導(dǎo)出的解進(jìn)行實(shí)驗(yàn)5。建立起對(duì)解的有效控制6。方案的實(shí)施線(xiàn)性規(guī)劃數(shù)學(xué)規(guī)劃非線(xiàn)性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃學(xué)科內(nèi)容多目標(biāo)規(guī)劃組合優(yōu)化最優(yōu)計(jì)數(shù)問(wèn)題網(wǎng)絡(luò)優(yōu)化排序問(wèn)題統(tǒng)籌圖隨機(jī)優(yōu)化對(duì)策論排隊(duì)論庫(kù)存論決策分析可靠性分析運(yùn)籌學(xué)的主要內(nèi)容成熟的學(xué)科

4、分支向縱深發(fā)展新的研究領(lǐng)域產(chǎn)生與新的技術(shù)結(jié)合與其他學(xué)科的結(jié)合加強(qiáng)傳統(tǒng)優(yōu)化觀(guān)念不斷變化運(yùn)籌學(xué)的發(fā)展趨勢(shì)模型要素 變量可控因素 目標(biāo)優(yōu)化的動(dòng)力和依據(jù) 約束內(nèi)部條件和外部約束研究?jī)?nèi)容 建模概念最優(yōu)性條件算法靈敏度分析最優(yōu)化模型 實(shí)例某工廠(chǎng)用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如表所示，試制訂總利潤(rùn)最大的生產(chǎn)計(jì)劃單位產(chǎn)品所需原料數(shù)量（公斤）產(chǎn)品Q(chēng)1產(chǎn)品Q(chēng)2產(chǎn)品Q(chēng)3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000單位產(chǎn)品的利潤(rùn)（千元）3541. 生 產(chǎn) 計(jì) 劃 問(wèn) 題問(wèn) 題 分 析模 型軟 件 計(jì) 算 結(jié) 果某食品公司經(jīng)銷(xiāo)的主要產(chǎn)品之一是糖果。它下面設(shè)有三個(gè)加工廠(chǎng)，每天

5、的生產(chǎn)量分別為:A17噸， A24噸，A39噸。擬把這些糖果運(yùn)往四個(gè)門(mén)市銷(xiāo)售，各門(mén)市的每日銷(xiāo)量為B13噸， B26噸，B35噸，B46噸。運(yùn)價(jià)表如下，問(wèn)：如何運(yùn)送使總運(yùn)費(fèi)最??？2. 運(yùn) 輸 問(wèn) 題B1B2B3B4 A1311310 A21928 A374105表1：?jiǎn)挝贿\(yùn)價(jià)表門(mén)市加工廠(chǎng)方案B1B2B3B4產(chǎn)量A1527A2314A3639銷(xiāo) 量3656最優(yōu)方案3. 整數(shù)規(guī)劃 問(wèn) 題證券投資：把一定的資金投入到合適的有價(jià)證券上以規(guī)避風(fēng)險(xiǎn)并獲得最大的利潤(rùn)。項(xiàng)目投資：財(cái)團(tuán)或銀行把資金投入到若干項(xiàng)目中以獲得中長(zhǎng)期的收益最大。4. 組合投資 問(wèn) 題某財(cái)團(tuán)有 萬(wàn)元的資金，經(jīng)出其考察選中 個(gè)投資項(xiàng)目，每個(gè)項(xiàng)

6、目只能投資一次。其中第 個(gè)項(xiàng)目需投資金額為 萬(wàn)元，預(yù)計(jì)5年后獲利 （ ）萬(wàn)元，問(wèn)應(yīng)如何選擇項(xiàng)目使得5年后總收益最大？模 型5. 目標(biāo)規(guī)劃 問(wèn) 題例 某電視機(jī)廠(chǎng)裝配黑白和彩色兩種電視機(jī)，每裝配一臺(tái)電視機(jī)需占用裝配線(xiàn)1小時(shí)，裝配線(xiàn)每周計(jì)劃開(kāi)動(dòng)40小時(shí)。預(yù)計(jì)市場(chǎng)每周彩色電視機(jī)的銷(xiāo)量是24臺(tái)，每臺(tái)可獲利80元；黑白電視機(jī)的銷(xiāo)量是30臺(tái)，每臺(tái)可獲利40元。該廠(chǎng)確定的目標(biāo)為：第一優(yōu)先級(jí)：充分利用裝配線(xiàn)每周計(jì)劃開(kāi)動(dòng)40小時(shí)；第二優(yōu)先級(jí)：允許裝配線(xiàn)加班；但加班時(shí)間每周盡量不超過(guò)10小時(shí)；第三優(yōu)先級(jí)：裝配電視機(jī)的數(shù)量盡量滿(mǎn)足市場(chǎng)需要。因彩色電視機(jī)的利潤(rùn)高，取其權(quán)系數(shù)為2。試建立這問(wèn)題的目標(biāo)規(guī)劃模型，并求解黑白和

7、彩色電視機(jī)的產(chǎn)量。 (d)0102030405060102030405060(a)(b)(c)(24, 26)滿(mǎn)足P1, P2的可行域滿(mǎn)足P1, P2, P3(c)的可行域目標(biāo)規(guī)劃的最優(yōu)解d1+d2+d4+例1：18世紀(jì)，在東普魯士哥尼斯堡有座橋，如下圖，一個(gè)散步者能否走遍七座橋，每座橋只走過(guò)一次，最后回到出發(fā)點(diǎn)？ 6. 圖論 問(wèn) 題定義：（Euler開(kāi)（閉）跡、Euler跡、可一筆畫(huà)）解：1。模擬圖：以頂點(diǎn)表陸地，以邊表橋，得4個(gè)頂點(diǎn)的模擬圖。2。問(wèn)題等價(jià)于：能否有一條閉跡包含模擬圖的所有邊，即：模擬圖含有Euler閉跡嗎？3。求解：假設(shè)圖G含Euler閉跡。因?yàn)殚]跡是連通的，所以圖G也連通。又因?yàn)槊總€(gè)頂點(diǎn)既能到達(dá)也能離開(kāi)，所以圖G的每個(gè)頂點(diǎn)度都是偶數(shù)。即：圖G含Euler閉跡的必要條件：連通且沒(méi)有奇度頂點(diǎn)。所以，“七橋問(wèn)題”是不可能的。若有一條開(kāi)（閉）跡含圖G的所有頂點(diǎn)和邊，則稱(chēng)其為Euler開(kāi)（閉）跡， Euler開(kāi)（閉）跡統(tǒng)稱(chēng)Euler跡。可一筆畫(huà)：從起點(diǎn)到終點(diǎn)一筆畫(huà)完。華羅庚的例子：有客來(lái)訪(fǎng)，要請(qǐng)他飲茶，于是要做幾件事：洗茶杯、洗杯蓋、燒開(kāi)水、泡茶到端茶。7. 關(guān)鍵路線(xiàn)法 問(wèn) 題客來(lái)沏茶本問(wèn)題的幾道“工序”有次序, 洗杯蓋 端茶 燒水 泡茶 洗杯 虛 251020.5教學(xué)計(jì)劃 數(shù)學(xué)規(guī)劃部分：線(xiàn)性規(guī)劃，對(duì)偶問(wèn)題，整數(shù)規(guī)劃，目標(biāo)規(guī)劃，動(dòng)