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

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

2、月，Bawdsey雷達(dá)站的負(fù)責(zé)人A.P.Rowe（羅伊）提出立即進(jìn)行整個(gè)防空作戰(zhàn)系統(tǒng)運(yùn)行的研究，1939年，以英國的物理學(xué)家，時(shí)任英國戰(zhàn)斗機(jī)司令部科學(xué)顧問的Blackett為首，聯(lián)合心理學(xué)家、數(shù)學(xué)家、應(yīng)用數(shù)學(xué)家、天文物理學(xué)家、海軍陸軍軍官組成了一個(gè)代號“Blackett馬戲團(tuán)”的研究小組，專門就改進(jìn)防空系統(tǒng)進(jìn)行研究。在他們的報(bào)告中使用了“Operational Research”一詞，這便是我們所說的運(yùn)籌學(xué)。國內(nèi)：國內(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é)不是對每一個(gè)決策行為孤立的進(jìn)行評價(jià)，而是把它同系統(tǒng)內(nèi)所有其他重要的相互作用結(jié)合起來作出評價(jià)，把相互影響的各方面作為一個(gè)統(tǒng)一體，從總體利益出發(fā)，尋找一個(gè)優(yōu)化方案。運(yùn)籌學(xué)的性質(zhì)與特點(diǎn)多學(xué)科的配合：一個(gè)企業(yè)的有效管理涉及到很多方面，運(yùn)籌學(xué)的研究要吸收不同領(lǐng)域、不同學(xué)科的知識和技術(shù)。模型方法的應(yīng)用：1。分析與表述問題：2。建立模型：3。對問題求解：4。對模型和由模型導(dǎo)出的解進(jìn)行實(shí)驗(yàn)5。建立起對解的有效控制6。方案的實(shí)施線性規(guī)劃數(shù)學(xué)規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動態(tài)規(guī)劃學(xué)科內(nèi)容多目標(biāo)規(guī)劃組合優(yōu)化最優(yōu)計(jì)數(shù)問題網(wǎng)絡(luò)優(yōu)化排序問題統(tǒng)籌圖隨機(jī)優(yōu)化對策論排隊(duì)論庫存論決策分析可靠性分析運(yùn)籌學(xué)的主要內(nèi)容成熟的學(xué)科

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

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

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

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