運(yùn)籌學(xué)建模PPT培訓(xùn)資料

1、1,運(yùn)籌學(xué)建模,1.線性規(guī)劃 2.對偶規(guī)劃和影子價(jià)格 3.運(yùn)輸問題 4.整數(shù)規(guī)劃 5.動態(tài)規(guī)劃,2,運(yùn)籌學(xué)簡介,1.引言： 運(yùn)籌學(xué)（Operations Research）主要研究系統(tǒng)最優(yōu)化。在我國公元前6世紀(jì)孫子兵法中處處體現(xiàn)了軍事運(yùn)籌的思想，賈思勰的齊民要術(shù)一書是一部體現(xiàn)運(yùn)籌思想、合理規(guī)劃農(nóng)事的寶貴文獻(xiàn),3,歐美，在20世紀(jì)前葉，1914年提出了軍事運(yùn)籌學(xué)中的蘭徹斯特（Lanchester）戰(zhàn)斗方程；1917年排隊(duì)論的先驅(qū)者丹麥工程師愛爾朗（Erlang）在哥本哈根電話公司研究電話通信系統(tǒng)時(shí)，提出了排隊(duì)論的一些著名公式；20世紀(jì)20年代初提出了存貯論的最優(yōu)批量公式；20世紀(jì)30年代，在商業(yè)

2、方面列溫遜已經(jīng)運(yùn)用運(yùn)籌思想來分析商業(yè)廣告和顧客心里等；20世紀(jì)30年代末，美英對付德國，20世紀(jì)50年代中期，我國著名的科學(xué)家錢學(xué)森、許國志等將運(yùn)籌學(xué)從西方引入中國,4,運(yùn)籌學(xué)在管理方面的應(yīng)用,生產(chǎn)運(yùn)作，物資庫存管理，物資運(yùn)輸，組織人事管理，市場營銷，財(cái)務(wù)管理和會計(jì)，計(jì)算機(jī)應(yīng)用和信息系統(tǒng)開發(fā)，城市管理等,5,運(yùn)籌學(xué)的來源和組成,運(yùn)籌學(xué)的三個(gè)來源：軍事、管理和經(jīng)濟(jì)。 運(yùn)籌學(xué)的三個(gè)組成部分：運(yùn)用分析理論、競爭理論和隨機(jī)服務(wù)理論（排隊(duì)論,6,運(yùn)籌學(xué)分支,線性規(guī)劃是由美國運(yùn)籌學(xué)工作者G.B.Dantzig在1947年發(fā)表的結(jié)果，提出單純形法。列昂杰夫在1932年提出了投入產(chǎn)出模型；馮諾伊曼（Von N

3、eumman）和O.Moogenstern合著（1944年）的對策論與經(jīng)濟(jì)行為是對策論的奠基作，同時(shí)該書已隱約地提出了對策論與線性規(guī)劃對偶理論地緊密聯(lián)系,7,運(yùn)籌學(xué)分支,運(yùn)籌學(xué)一般包含：線性規(guī)劃，非線性規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃，動態(tài)規(guī)劃，隨機(jī)規(guī)劃，模糊規(guī)劃； 圖論與網(wǎng)絡(luò)，排隊(duì)論，存貯論，對策論，搜索論，維修更新理論，排序與運(yùn)籌方法等,8,運(yùn)籌學(xué)定義,1）為決策機(jī)構(gòu)在對其控制下的業(yè)務(wù)活動進(jìn)行決策時(shí)，提供以數(shù)量化為基礎(chǔ)的科學(xué)方法（P.M.Morse 和G.E.Kimball給出的）。 （2）運(yùn)籌學(xué)是一門應(yīng)用科學(xué)，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)知識和數(shù)學(xué)方法，解決實(shí)際中提出的專門問題，為決策者選擇最優(yōu)決策

4、提供定量依據(jù)。 （3）運(yùn)籌學(xué)是給出問題壞的答案的藝術(shù)，否則的話問題的結(jié)果會更壞,9,運(yùn)籌學(xué)的原則,為了有效地應(yīng)用運(yùn)籌學(xué)，必須遵循下列六條原則： （1）合伙原則 （2）催化原則 （3）互相滲透原則 （4）獨(dú)立原則 （5）寬容原則 （6）平衡原則,10,線性規(guī)劃例,引例：某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品，每種產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的機(jī)時(shí)數(shù)如下表,11,線性規(guī)劃例,問：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤,解：設(shè)xj為第j種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù) j1，2 ，則由題意知，問題可轉(zhuǎn)化為,12,線性規(guī)劃例,注：Max為Maxim

5、ize求f的最大值，s.t.為Subject to約束，限制，滿足于,13,線性規(guī)劃例,求解方法一：圖解法,14,線性規(guī)劃例,求解方法二：單純形法,15,線性規(guī)劃例,第一次迭代,1）取x3，x4，x5為基變量，x1，x2為非基變量 ，基本可行解為（0，0，65，40，75），f0,16,線性規(guī)劃例,2）選擇進(jìn)基變量：目標(biāo)函數(shù)中非基變量的系數(shù)全為負(fù)時(shí)，則剛才的基本可行解即為最優(yōu)解。若有正的，選擇系數(shù)大的非基變量為進(jìn)基變量，本例為x2 （3）出基變量為當(dāng)進(jìn)基變量增大時(shí)，首先下降為零的基變量，本例為x5,17,線性規(guī)劃例,第二次迭代,1）取x2，x3，x4為基變量，x1，x5為非基變量 ，可行解為（

6、0，25，15，15，0），f62500,18,線性規(guī)劃例,2）選擇進(jìn)基變量：方法同第一次迭代，本例為x1 （3）出基變量：方法同第一次迭代，本例為x3,19,線性規(guī)劃例,第三次迭代,1）取x1，x2，x4為基變量，x3，x5為非基變量 ，可行解為（5，25，0，5，0），f70000,20,線性規(guī)劃例,2）選擇進(jìn)基變量：已無 ，因此該可行解即為最優(yōu)解，結(jié)束,21,線性規(guī)劃一般模型,目標(biāo)函數(shù)： 約束條件,稱xj為決策變量，cj為價(jià)值系數(shù)和費(fèi)用系數(shù)，aij為約束系數(shù)或技術(shù)系數(shù)，bi為資源系數(shù),22,線性規(guī)劃一般模型,其它形式,23,線性規(guī)劃中的一些名詞和術(shù)語,線性規(guī)劃模型三要素： 決策變量 約束

7、條件 目標(biāo)函數(shù),24,線性規(guī)劃中的一些名詞和術(shù)語,可行解滿速線性規(guī)劃全部約束條件的解 可行域全體可行解的集合 最優(yōu)解使得目標(biāo)函數(shù)實(shí)現(xiàn)最小值（或最大值）的可行解 最優(yōu)值最優(yōu)解的目標(biāo)函數(shù)值,25,線性規(guī)劃模型標(biāo)準(zhǔn)型,LP,26,求線性規(guī)劃方法單純形法,G.B.Danting在1947年提出了求解線性規(guī)劃問題的方法單純形法(simplex method)，其原理是：如果（LP）的可行域K不是空集，我們從K的某一頂點(diǎn)X0出發(fā)，判別它是否為最優(yōu)解？若不是，沿著邊界找它鄰近的另一個(gè)頂點(diǎn)，它應(yīng)比原來的頂點(diǎn)優(yōu)，看它是否為最優(yōu)解？若不是，再沿著邊界找它鄰近的頂點(diǎn)。通過逐次迭代，直至找出最優(yōu)解,27,求線性規(guī)劃方

8、法軟件,LINDO軟件包首先由Linus Schrage開發(fā)，現(xiàn)在，美國的LINDO系統(tǒng)公司（LINDO System Inc.）擁有版權(quán)，是一種專門求解數(shù)學(xué)規(guī)劃（優(yōu)化問題）的軟件包。它能求解線性規(guī)劃、（0，1）規(guī)劃、整數(shù)規(guī)劃、二次規(guī)劃等優(yōu)化問題，并能同時(shí)給出靈敏度分析、影子價(jià)格以及最優(yōu)解的松弛分析，非常方便實(shí)用,28,與線性規(guī)劃有關(guān)的名字,改進(jìn)單純形法 人工變量法（大M法和兩節(jié)段法） 對偶問題，對偶理論，對偶單純形法 影子價(jià)格 靈敏度分析,29,線性規(guī)劃有關(guān)的問題,1.生產(chǎn)計(jì)劃問題 ：m種資源B1, B2, , Bm，生產(chǎn)n種產(chǎn)品A1, A2, An，單位產(chǎn)品所需資源數(shù)aij，所得利潤cj，

9、可供應(yīng)的資源總量bi，問應(yīng)如何組織生產(chǎn)才能使利潤最大？ 2.合理下料問題 ：一維下料，二維下料，三維下料,30,線性規(guī)劃有關(guān)的問題,3.合理配料問題 ：m種原料B1, B2, , Bm混合調(diào)制n種產(chǎn)品A1, A2, An，產(chǎn)品的規(guī)格要求、單位價(jià)格，原料供應(yīng)量，原料的價(jià)格要求如下，問應(yīng)如何組織生產(chǎn)才能使利潤最大,31,線性規(guī)劃有關(guān)的問題,4.運(yùn)輸問題 ：m個(gè)物資產(chǎn)地B1, B2, , Bm，n個(gè)物資銷地A1, A2, An，si為產(chǎn)地Bi產(chǎn)量，dj為銷地Aj的銷量，cij表示把物資從產(chǎn)地Bi運(yùn)到銷地Aj的單位運(yùn)價(jià)，xij表示把物資從產(chǎn)地Bi運(yùn)到銷地Aj的運(yùn)輸量，問應(yīng)如何運(yùn)輸才能使運(yùn)費(fèi)最小,32,

10、對偶問題,引例：某工廠計(jì)劃在下一生產(chǎn)周期生產(chǎn)3種產(chǎn)品A1, A2, A3，這些產(chǎn)品都要在甲、乙、丙、丁4種設(shè)備上加工，根據(jù)設(shè)備性能和以往的生產(chǎn)情況知道單位產(chǎn)品的加工工時(shí)、各種設(shè)備的最大加工工時(shí)限制，以及每種產(chǎn)品的單位利潤，如下表。問如何安排生產(chǎn)計(jì)劃，才能使工廠得到最大利潤,33,對偶問題,34,對偶問題,解：設(shè)xj為產(chǎn)品Aj的生產(chǎn)件數(shù) j1,2,3，則由題意知，問題可轉(zhuǎn)化為如下的線性規(guī)劃問題,35,對偶問題,現(xiàn)在從另一個(gè)角度來討論問題：假設(shè)工廠考慮不安排生產(chǎn)，而準(zhǔn)備將所有設(shè)備出租，收取租費(fèi)。于是需要為每種設(shè)備的臺時(shí)進(jìn)行估價(jià)。設(shè)y1, y2, y3, y4分別表示甲、乙、丙、丁4種設(shè)備的臺時(shí)估價(jià)

11、，下面分析約束條件和目標(biāo)函數(shù),36,對偶問題,由上面的表可知，生產(chǎn)一件產(chǎn)品A1需要各設(shè)備臺時(shí)分別為2h，4h，3h，2h，如果將2h，4h，3h，2h不用于生產(chǎn)產(chǎn)品A1，而是用于出租，租費(fèi)應(yīng)滿足（為了不蝕本，租費(fèi)不能少于利潤，否則還不如自己生產(chǎn)產(chǎn)品合算呢?。?2 y1+4y2+3 y3+2 y48，依次可分析得線性規(guī)劃模型如下,37,對偶問題,說明：企業(yè)為了能夠得到租用設(shè)備的用戶，使出租設(shè)備的計(jì)劃成交，在價(jià)格滿足約束條件下，應(yīng)將設(shè)備價(jià)格定得盡可能低,38,對偶規(guī)劃,設(shè) 為對偶問題（D）的最優(yōu)解，則稱 為原有問題（P）第i個(gè)約束對應(yīng)的影子價(jià)格（Shadow Price,39,對偶規(guī)劃影子價(jià)格,影

12、子價(jià)格的經(jīng)濟(jì)含義：（1）影子價(jià)格是對現(xiàn)有資源實(shí)現(xiàn)最大效益的一種估價(jià)。根據(jù)上例，企業(yè)可以根據(jù)現(xiàn)有資源的影子價(jià)格，對資源的使用有兩種考慮：第一，是否將設(shè)備用于出租，若租費(fèi)高于某設(shè)備的影子價(jià)格，可考慮出租該設(shè)備，否則不宜出租；第二，是否將投資用于購買設(shè)備，以擴(kuò)大生產(chǎn)能力，若市價(jià)低于某設(shè)備的影子價(jià)格，可考慮買進(jìn)該設(shè)備，否則不宜買進(jìn),40,對偶規(guī)劃影子價(jià)格,2）影子價(jià)格表明資源增加對總效益產(chǎn)生的影響。易見有 從而，如果 增加一個(gè)單位，目標(biāo)函數(shù)值的增量將是 ，據(jù)此，由影子價(jià)格的大小可以知道哪種資源的增加可以給企業(yè)帶來較大的收益,41,對偶規(guī)劃影子價(jià)格應(yīng)用例,某外貿(mào)公司準(zhǔn)備購進(jìn)兩種產(chǎn)品A1, A2。購進(jìn)產(chǎn)品

13、A1每件需要10元，占用5m3的空間，待每件A1賣出后，可獲純利潤3元；購進(jìn)產(chǎn)品A2每件需要15元，占用3m3的空間，待每件A2賣出后，可獲純利潤4元。公司現(xiàn)有資金1400元，有430 m3的倉庫空間存放產(chǎn)品，如何安排可以獲得最大利潤,42,對偶規(guī)劃影子價(jià)格應(yīng)用例,現(xiàn)在公司有另外一筆資金585元，準(zhǔn)備用于投資，到底是購買產(chǎn)品呢？還是增加倉庫容量？（假設(shè)增加1m3的倉庫空間需要0.8元,43,靈敏度分析,最優(yōu)解是在參數(shù)cj、bi、aij都固定不變的條件下取得的。但是，在實(shí)際問題中，對一個(gè)具體的企業(yè)來說，參數(shù)cj、bi、aij不是固定不變的，或者說得到的這些參數(shù)有一定的誤差。 如產(chǎn)品的市場價(jià)格可能

14、有所變動；國家分配的原材料可能有所增減；動力供應(yīng)情況可能隨季審而變化f添置新設(shè)備而使生產(chǎn)臺時(shí)增加；由于產(chǎn)品設(shè)計(jì)結(jié)構(gòu)有所改進(jìn)，使單位產(chǎn)品的原材料消耗定額有所增減,44,靈敏度分析,現(xiàn)實(shí)諸因素的種種變化都會引起已建立的數(shù)學(xué)模型的參數(shù)變化?；蛘?，當(dāng)運(yùn)用線性規(guī)劃編制完生產(chǎn)計(jì)劃并即將付諸應(yīng)用時(shí)，又發(fā)生了新的情況，某些原來未加限制的資源現(xiàn)在有了限制，從而出現(xiàn)一個(gè)新的追加約束條件?；蛘?，企業(yè)準(zhǔn)備增加新產(chǎn)品，使工廠的生產(chǎn)計(jì)劃發(fā)生整個(gè)變化,45,靈敏度分析,從而，我們面臨這樣的問題：上述種種情況的發(fā)生，將對已求得的最優(yōu)解產(chǎn)生什么影響?或者說，我們?nèi)绾卧谠械淖顑?yōu)單純形表的基礎(chǔ)上用最少的計(jì)算量，去獲得修改后的線性

15、規(guī)劃問題的最優(yōu)解?這就是我們要討論的靈敏度分析（Sensitivity Analysis）問題,46,靈敏度分析,一般分下面5個(gè)問題來進(jìn)行靈敏度分析： 1變量xj的目標(biāo)函數(shù)系數(shù)cj在何范圍內(nèi)變動，問題(LP)的最優(yōu)基(最優(yōu)解)不變?如果超出這個(gè)范圍，如何求最優(yōu)解? 2第s種資源bs在何范圍內(nèi)變動，最優(yōu)基不變?如果bs超出這個(gè)范圍，如何求最優(yōu)解? 3變量xj在矩陣A中的系數(shù)列向量發(fā)生變化，如何求新問題的最優(yōu)解? 4追加新的約束條件，如何求新的線性規(guī)劃的最優(yōu)解? 5增加新的變量xj，如何求新問題的最優(yōu)解,47,特殊規(guī)劃運(yùn)輸問題,一般模型：m個(gè)物資產(chǎn)地（發(fā)點(diǎn)）A1, A2, Am，n個(gè)物資銷地（收點(diǎn)

16、）B1, B2, , Bn，ai為發(fā)點(diǎn)Ai的物資供應(yīng)量（發(fā)量），bj為收點(diǎn)Bj對物資的需求量（收量），cij表示把物資從Ai運(yùn)到Bj的單位運(yùn)價(jià)，xij表示把物資從Ai運(yùn)到Bj的運(yùn)輸量，問應(yīng)如何運(yùn)輸才能使運(yùn)費(fèi)最??？（假定收發(fā)平衡,48,特殊規(guī)劃運(yùn)輸問題,Ai,運(yùn)輸收發(fā)平衡單位運(yùn)價(jià)表（簡稱運(yùn)輸表格,49,特殊規(guī)劃運(yùn)輸問題,稱之為運(yùn)輸問題的標(biāo)準(zhǔn)模型，此為產(chǎn)銷平衡模型，產(chǎn)銷不平衡時(shí)，增加虛擬的收點(diǎn)和發(fā)點(diǎn)（松弛變量）即可達(dá)到產(chǎn)銷平衡,50,特殊規(guī)劃運(yùn)輸問題,求解方法：線性規(guī)劃的解法也適用運(yùn)輸問題，但是針對運(yùn)輸問題的特殊性有其特殊解法表上作業(yè)法（詳見有關(guān)書籍）。 一些名詞：閉回路，孤立點(diǎn)，尋找初始基本可行解方法（西北角法，最小元素法），計(jì)算檢驗(yàn)數(shù)方法（位勢法,一般模型有：平衡運(yùn)輸問題，不平衡運(yùn)輸問題，有界發(fā)量運(yùn)輸問題，運(yùn)量有界的運(yùn)輸問題，轉(zhuǎn)運(yùn)問題，多品種物資運(yùn)輸問題，空車調(diào)