數(shù)學(xué)建模動(dòng)態(tài)規(guī)劃PPT課件

1、動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化的一種方法。該方法是由美國(guó)數(shù)學(xué)家貝爾曼（R. E. Bellman)等人在20世紀(jì)50年代初提出的。他們針對(duì)多階段決策問(wèn)題的特點(diǎn)，提出了解決這類問(wèn)題的“最優(yōu)化原理”，并成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多問(wèn)題，從而建立了運(yùn)籌學(xué)的一個(gè)新的分支，即動(dòng)態(tài)規(guī)劃。Bellman在1957年出版了Dynamic Programming一書，是動(dòng)態(tài)規(guī)劃領(lǐng)域中的第一本著作。第1頁(yè)/共69頁(yè) 動(dòng)態(tài)規(guī)劃問(wèn)題及實(shí)動(dòng)態(tài)規(guī)劃問(wèn)題及實(shí)例例動(dòng)態(tài)規(guī)劃是解決多階段決策問(wèn)題的一種方法，是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)計(jì)劃和庫(kù)存問(wèn)題、投資問(wèn)題、裝載問(wèn)

2、題、排序問(wèn)題及生產(chǎn)過(guò)程的最優(yōu)控制等。動(dòng)態(tài)規(guī)劃模型的分類：以“時(shí)間”角度可分成：離散型和連續(xù)型。從信息確定與否可分成：確定型和隨機(jī)型。從目標(biāo)函數(shù)的個(gè)數(shù)可分成：?jiǎn)文繕?biāo)型和多目標(biāo)型。第2頁(yè)/共69頁(yè)一、多階段決策過(guò)程 多階段決策過(guò)程是指這樣一類特殊的活動(dòng)過(guò)程，他們可以按時(shí)間順序分解成若干相互聯(lián)系的階段，在每個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列，所以多階段決策過(guò)程也稱為序貫決策過(guò)程。這種問(wèn)題就稱為多階段決策問(wèn)題。 二、多階段決策問(wèn)題的特點(diǎn) 過(guò)程可分為若干個(gè)相互聯(lián)系的階段；每一階段都對(duì)應(yīng)著一組可供選擇的決策；每一決策的選定即依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。第3頁(yè)/共69頁(yè)三、具體

3、實(shí)例 1、最短路線問(wèn)題給定一個(gè)線路網(wǎng)絡(luò)，要從A向F鋪設(shè)一條輸油管道，各點(diǎn)間連線上的數(shù)字表示距離，問(wèn)應(yīng)選擇什么路線，可使總距離最短？第4頁(yè)/共69頁(yè)2、生產(chǎn)與存儲(chǔ)問(wèn)題：某工廠每月需供應(yīng)市場(chǎng)一定數(shù)量的產(chǎn)品。供應(yīng)需求所剩余產(chǎn)品應(yīng)存入倉(cāng)庫(kù)，一般地說(shuō)，某月適當(dāng)增加產(chǎn)量可降低生產(chǎn)成本，但超產(chǎn)部分存入倉(cāng)庫(kù)會(huì)增加庫(kù)存費(fèi)用，要確定一個(gè)每月的生產(chǎn)計(jì)劃，在滿足需求條件下，使一年的生產(chǎn)與存儲(chǔ)費(fèi)用之和最小。第5頁(yè)/共69頁(yè) 動(dòng)態(tài)規(guī)劃的基本概念與原理動(dòng)態(tài)規(guī)劃的基本概念與原理動(dòng)態(tài)規(guī)劃的基本概念階段；狀態(tài)；決策和策略；狀態(tài)轉(zhuǎn)移方程；指標(biāo)函數(shù)。第6頁(yè)/共69頁(yè)一、基本概念階段：是指問(wèn)題需要做出決策的步數(shù)。階段總數(shù)常記為n，相應(yīng)

4、的是n個(gè)階段的決策問(wèn)題。階段的序號(hào)常記為k，稱為階段變量，k=1,2, ,n. k即可以是順序編號(hào)也可以是逆序編號(hào)，常用順序編號(hào)。狀態(tài)：各階段開始時(shí)的客觀條件，第k階段的狀態(tài)常用狀態(tài)變量 表示，狀態(tài)變量取值的集合成為狀態(tài)集合，用表示。kskS例如，案例1中，.,2121BBSAS第7頁(yè)/共69頁(yè)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1階段第2階段第3階段第4階段第5階段狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5狀態(tài)6第8頁(yè)/共69頁(yè)決策：是指從某階段的某個(gè)狀態(tài)出發(fā)，在若干個(gè)不同方案中做出的選擇。表示決策的變量，稱為決策變量，用 表示。 表示第k階

5、段當(dāng)狀態(tài)處于sk時(shí)的決策變量。)(kksu例如： 表示走到C階段,當(dāng)處于C2 路口時(shí)，下一步奔D1.123)(DCu 時(shí)的允許決策集合記為 ，例如：)(kksD,)(32112CCCBD決策變量允許的取值范圍稱為允許決策集合，第k階段狀態(tài)為 )(kksuks第9頁(yè)/共69頁(yè)狀態(tài)轉(zhuǎn)移方程：是從上一階段的某一狀態(tài)值轉(zhuǎn)變?yōu)橄乱浑A段某一狀態(tài)值的轉(zhuǎn)移規(guī)律，用 ),(1kkkkusTs表示。策略：一個(gè)按順序排列的決策組成的集合。由每段的決策按順序排列組成的決策函數(shù)序列 稱為k子過(guò)程策略。簡(jiǎn)稱子策略，記為 。即當(dāng)k=1時(shí)，此決策函數(shù)序列成為全過(guò)程的一個(gè)策略，簡(jiǎn)稱策略，記為：在實(shí)際問(wèn)題中，可供選擇的策略有一定

6、的范圍，此范圍稱為允許策略集合，用P表示。第10頁(yè)/共69頁(yè)指標(biāo)函數(shù)：階段指標(biāo)函數(shù)和過(guò)程指標(biāo)函數(shù)。階段指標(biāo)函數(shù)是指第k階段從狀態(tài) 出發(fā)，采取決策 時(shí)的效益，用ksku),(kkkusv表示。而過(guò)程指標(biāo)函數(shù)是從第k階段的某狀態(tài)出發(fā)，采取子策略效益之和：最優(yōu)指標(biāo)函數(shù)：表示從第k階段狀態(tài)為 時(shí)采用最佳策略ks到過(guò)程終止時(shí)的最佳效益。記為時(shí)所得到的階段第11頁(yè)/共69頁(yè)其中 opt 可根據(jù)具體情況取max 或min?；痉匠蹋捍藶橹鸲芜f推求和的依據(jù)，一般為：式中opt 可根據(jù)題意取 max 或 min.例如，案例1的基本方程為：0)(1 , 2 , 3 , 4 , 5)(),(min)(6611sfk

7、sfusdsfkkkkkukkk第12頁(yè)/共69頁(yè)最優(yōu)性原理：最優(yōu)策略的子策略必為最優(yōu)。不管過(guò)去的狀態(tài)和決策如何，從眼下直到最后的諸決策必構(gòu)成最優(yōu)子策略。動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：可把一個(gè)N維優(yōu)化問(wèn)題化成N個(gè)一維優(yōu)化問(wèn)題求解。求得最優(yōu)解以后，可得所有子問(wèn)題的最優(yōu)解。動(dòng)態(tài)規(guī)劃的缺點(diǎn)：“一個(gè)”問(wèn)題，“一個(gè)”模型，“一個(gè)”求解方法。且求解技巧要求比較高，沒(méi)有統(tǒng)一處理方法。狀態(tài)變量維數(shù)不能太高，一般要求小于6。第13頁(yè)/共69頁(yè)動(dòng)態(tài)規(guī)劃應(yīng)用舉例例1 最短路線問(wèn)題基本思想：如果起點(diǎn)A經(jīng)過(guò)B1,C1,D1,E1而到終點(diǎn)F，則由C1出發(fā)經(jīng)D1,E1到F點(diǎn)這條子路線，是從C1到F的最短路線。所以，尋找最短路線，應(yīng)該從最

8、后一段開始找，然后往前遞推。第14頁(yè)/共69頁(yè)狀態(tài)變量 ：各路線的位置決策變量 ：第k階段當(dāng)狀態(tài)處于 時(shí)，決定下一個(gè)狀態(tài)的位置狀態(tài)轉(zhuǎn)移方程 ：上一階段到下一階段的轉(zhuǎn)移規(guī)則指標(biāo)函數(shù) ：從狀態(tài)出發(fā)，采取決策時(shí)的路程距離最優(yōu)指標(biāo)函數(shù) ：第k階段狀態(tài)為時(shí)且采用最佳走線策略，使從k位置及以后的路線最短。ksks)(kksu)(kksu第15頁(yè)/共69頁(yè)逆序遞推方程：0)(1 , 2 , 3 , 4 , 5)(),(min)(6611sfksfusdsfkkkkkukkk（1）k=5 時(shí)，狀態(tài),215EES它們到F 點(diǎn)的距離即為最短路。, 4)(15Ef; 3)(25Ef,)(1*5FEu.)(2*5FE

9、uAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第16頁(yè)/共69頁(yè)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4 時(shí)，狀態(tài),3214DDDS它們到F 點(diǎn)需經(jīng)過(guò)中途點(diǎn)E，需一一分析從E 到 F的最短路：先說(shuō)從D1到F 的最短路有兩種選擇：經(jīng)過(guò) E1, E2, 比較最短。.)(2*5FEu,)(1*5FEu第17頁(yè)/共69頁(yè)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252141511414EfEDdEf

10、EDdDf. 735 , 43min這說(shuō)明由 D1 到F 的最短距離為7，其路徑為.11FED相應(yīng)的決策為：.)(11*4EDu.)(2*5FEu,)(1*5FEu第18頁(yè)/共69頁(yè))(),(),(),(min)(252241512424EfEDdEfEDdDf. 532 , 46min這說(shuō)明由 D2 到F 的最短距離為5，其路徑為.22FED相應(yīng)的決策為：.)(22*4EDuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu第19頁(yè)/共69頁(yè)AB1B2C1C2C3C4D1D2D3E1E2F4

11、52368775845348435623143)(),(),(),(min)(252341513434EfEDdEfEDdDf. 533, 41min即 D3 到F 的最短距離為5，其路徑為.13FED相應(yīng)的決策為：.)(13*4EDu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu第20頁(yè)/共69頁(yè)（3）k=3 時(shí)，狀態(tài),43214CCCCS )(),(),(),(min)(242131411313DfDCdDfDCdCf.1258, 75min這說(shuō)明由 C1 到F 的最短距離為12，相應(yīng)的決策為.)(11*3DCuAB1B2C1C2C3C4D1D2D3E1E2F

12、452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu5)(24Df7)(14Df5)(34Df第21頁(yè)/共69頁(yè)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(242231412323DfDCdDfDCdCf.1055 , 74min即由 C2 到F 的最短距離為10，相應(yīng)的決策為.)(22*3DCu)(),(),(),(min)(343332423333DfDCdDfDCdCf. 854 , 53min.)(2*5FEu,

13、)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu7)(14Df5)(24Df5)(34Df第22頁(yè)/共69頁(yè)即由 C3 到F 的最短距離為8，相應(yīng)的決策為.)(23*3DCu)(),(),(),(min)(343432424343DfDCdDfDCdCf. 954 , 58min即由 C4 到F 的最短距離為9，相應(yīng)的決策為.)(34*3DCuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3

14、DCu.)(22*3DCu5)(24Df5)(34Df第23頁(yè)/共69頁(yè)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2時(shí)，狀態(tài),212BBS)(),(),(),(),(),(min)(33312232121311212CfCBdCfCBdCfCBdBf.1386 ,103 ,122min這說(shuō)明由 B1 到F 的最短距離為13，相應(yīng)的決策為.)(21*2CBu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu1

15、2)(13Cf10)(23Cf8)(33Cf第24頁(yè)/共69頁(yè))(),(),(),(),(),(min)(43422333222322222CfCBdCfCBdCfCBdBf.1597 , 87 ,108min即由 B2到F 的最短距離為15，相應(yīng)的決策為.)(32*2CBuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(21*2CBu9)(43Cf10)(23Cf8

16、)(33Cf第25頁(yè)/共69頁(yè)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1 時(shí)，只有一個(gè)狀態(tài)點(diǎn)A, 則)(),(),(),(min)(222112111BfBAdBfBAdAf.17155 ,134min即由 A到F 的最短距離為17，相應(yīng)的決策為.)(1*1BAu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)(21*2CBu13)(12Bf15)(22Bf第26頁(yè)/共69頁(yè),)

17、(21*2CBu,)(22*3DCu,)(22*4EDu.)(2*5FEu所以最優(yōu)路線為：FEDCBA2221AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)(21*2CBu再按計(jì)算順序反推可得最優(yōu)決策序列：,)(1*1BAu第27頁(yè)/共69頁(yè)順序遞推方程：初始條件0)(5 , 4 , 3 , 2 , 1)(),(min)(10111sfksfusd

18、sfkkkkkukkkAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1階段2階段3階段4階段5階段行走方向第28頁(yè)/共69頁(yè)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1 時(shí))(),()()(10111121sfABdBfsf注意到：0)()(010Afsf所以ABu)(1*1)(),()()(10212121sfABdBfsf, 4)(11Bf, 5)(21BfABu)(2*1第29頁(yè)/共69頁(yè)K=2 時(shí)642)(),()()(111121232BfBCdCfsf11*2)(BCu

19、AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*1)(),(),(),(min)()(21222111222232BfBCdBfBCdCfsf758 , 43min12*2)(BCu)(),(),(),(min)()(21232111323232BfBCdBfBCdCfsf第30頁(yè)/共69頁(yè)13*2)(BCu,1257)(),()()(212424232BfBCdCfsf24*2)(BCuK=3 時(shí))(),(),(),(min)()(22212121131343CfCDdCfCDdDfsf1174 , 65minAB

20、1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*1,1057 , 46min11*2)(BCu12*2)(BCu6)(12Cf7)(22Cf第31頁(yè)/共69頁(yè)AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*112*2)(BCu11*2)(BCu13*2)(BCu24*2)(BCu,)(11*3CDu21*3)(CDu或類似地，可算出：12)(23Df22*3)(CDu14)(33Df33*3)(CDu6)(12Cf7)(22Cf12)(42Cf

21、10)(32Cf第32頁(yè)/共69頁(yè)14)(14Ef11*4)(DEu14)(24Ef22*4)(DEu17)(5Ff2*5)(EFu最優(yōu)策略：2*5)(EFu22*4)(DEuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*111*2)(BCu12*2)(BCu13*2)(BCu24*2)(BCu,)(11*3CDu或21*3)(CDu22*3)(CDu33*3)(CDu12)(23Df14)(33Df11)(13Df第33頁(yè)/共69頁(yè)22*3)(CDu12*2)(BCuABu)(1*1最短路徑：FEDCBA2221

22、最短路長(zhǎng)：17)(5Ff注：順序解法與逆序解法無(wú)本質(zhì)區(qū)別，一般來(lái)說(shuō)，當(dāng)初始狀態(tài)給定時(shí)用逆序解法，當(dāng)終止?fàn)顟B(tài)給定時(shí)用順序解法。若問(wèn)題給定了一個(gè)初始狀態(tài)與一個(gè)終止?fàn)顟B(tài)，則兩種方法均可使用。第34頁(yè)/共69頁(yè)例2 資源分配問(wèn)題（離散型） 例：設(shè)有6萬(wàn)元資金用于4個(gè)工廠的擴(kuò)建，已知每個(gè)工廠的利潤(rùn)增長(zhǎng)額同投資額的大小有關(guān)，見下表。問(wèn)應(yīng)如何確定對(duì)這四個(gè)工廠的投資額，使總利潤(rùn)增長(zhǎng)額最大？ 投資額 (j)工廠(i)0 100 200 300 400 500 600 10 20 42 60 75 85 90 20 25 45 57 65 70 73 30 18 39 61 78 90 95 40 28 47 6

23、5 74 80 85 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）第35頁(yè)/共69頁(yè)解：把對(duì)四個(gè)工廠的投資依次看成4個(gè)階段的決策過(guò)程， 確定對(duì)第k個(gè)工廠的投資額看成第k個(gè)階段的決策，k=1,2,3,4。圖示如下：狀態(tài)變量 ：可用于第k, k+1,n個(gè)工廠的投資額。ks決策變量 ：第 k 階段對(duì)第 k 個(gè)工廠的投資額。kx允許決策集 ：kD,100, 0kksD3s4s112xss工廠1工廠2工廠3工廠46001s投資x1投資x2投資x3投資x4狀態(tài)2s223xss334xss5s狀態(tài)狀態(tài))(44xg)(33xg)(11xg)(22xg第36頁(yè)/共69頁(yè)狀態(tài)轉(zhuǎn)移方程：,1kkkxss. 4 , 3 ,

24、 2 , 1k其中6001s階段指標(biāo)函數(shù) ：第 k 階段投資 元時(shí)所產(chǎn)生的利潤(rùn)。（見上表）)(kkxgkx最優(yōu)指標(biāo)函數(shù) ：第 k 階段狀態(tài)為 且采取最佳投資策略，從第 k 個(gè)工廠以及以后的最大總利潤(rùn)。)(kksfks 逆序法基本遞推方程： 0)(1 , 2 , 3 , 4)()(max)(55110sfksfxgsfkkkksxkkkk第37頁(yè)/共69頁(yè)工廠1工廠2工廠3工廠46001s投資x1投資x2投資x3投資x4狀態(tài)2s112xss223xss334xss3s4s5s狀態(tài)狀態(tài))(44xg)(33xg)(11xg)(22xg 投資額 (j)工廠(i)0 100 200 300 400 50

25、0 600 40 28 47 65 74 80 85 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）解：（1）k=4時(shí)考慮：若到最后一個(gè)，第4個(gè)工廠投資時(shí)，還有資金 ，若投資于第4個(gè)工廠的資金為 ，則最大利潤(rùn)為4s4x第38頁(yè)/共69頁(yè)工廠1工廠2工廠3工廠46001s投資x1投資x2投資x3投資x4狀態(tài)2s112xss223xss334xss3s4s5s狀態(tài)狀態(tài))(44xg)(33xg)(11xg)(22xg 投資額 (j)工廠(i)0 100 200 300 400 500 600 40 28 47 65 74 80 85 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）)()(max)(554404444

26、sfxgsfsx（注意到此時(shí) =0） )(55sf)(max44044xgsx 第39頁(yè)/共69頁(yè)自然問(wèn)：現(xiàn)在還有多少錢？即 =？ 4s =0，100，200，300，400，500，600都有可能。 4s下面分情況討論：工廠1工廠2工廠3工廠46001s投資x1投資x2投資x3投資x4狀態(tài)2s112xss223xss334xss3s4s5s狀態(tài)狀態(tài))(44xg)(33xg)(11xg)(22xg 投資額 (j)工廠(i)0 100 200 300 400 500 600 40 28 47 65 74 80 85 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）第40頁(yè)/共69頁(yè)04s時(shí)，)(max)(

27、4404444xgsfsx )(max44004xgx )(max4404xgx . 00max1004s時(shí)，)(max)(4404444xgsfsx )(max4410004xgx )(max44100, 04xgx .2828, 0max其他種情況類似討論，我們把所有的結(jié)果匯總成一個(gè)表2。04x1004x 投資額 (j)工廠(i)0 100 200 300 400 500 600 40 28 47 65 74 80 85 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）第41頁(yè)/共69頁(yè)4x4s)(44xg)(44sf4x0 100 200 300 400 500 600 0 100 200 300

28、 400 500 60000 280 28 470 28 47 65 0 28 47 65 74 0 28 47 65 74 800 28 47 65 74 80 8502847657480850100200300400500600 表2 k=4 時(shí)決策表 投資額 (j)工廠(i)0 100 200 300 400 500 600 10 20 42 60 75 85 90 20 25 45 57 65 70 73 30 18 39 61 78 90 95 40 28 47 65 74 80 85 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）第42頁(yè)/共69頁(yè)（2）k=3時(shí) 到第三個(gè)工廠投資時(shí)，可利用

29、的資金還有 ， 3s若向第三個(gè)工廠投資 （萬(wàn)元），則自此即以后最大利潤(rùn)為：3x)()(max)(443303333sfxgsfsx)()(max33433033xsfxgsx 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）,1kkkxss 投資額 (j)工廠(i)0 100 200 300 400 500 600 30 18 39 61 78 90 95同樣問(wèn)： =？，即現(xiàn)在還有多少錢？它是允許決策集上界。3s600,500,400,300,200,100, 033 Ss同理第43頁(yè)/共69頁(yè)3003s僅舉一例：)300()(max)300(3433300033xfxgfx)300()(max3433

30、300,200,100, 03xfxgx)300300()300(),200300()200(),100300()100(),0300()0(max43434343fgfgfgfg)0()300(),100()200(),200()100(),300()0(max43434343fgfgfgfg 投資額 (j)工廠(i)0 100 200 300 400 500 600 30 18 39 61 78 90 95 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）第44頁(yè)/共69頁(yè)4x4s)(44xg)(44sf4x0 100 200 300 400 500 600 0 100 200 300 400 50

31、0 60000 280 28 470 28 47 65 0 28 47 65 74 0 28 47 65 74 800 28 47 65 74 80 8502847657480850100200300400500600 表2 k=4 時(shí)決策表)0()300(),100()200(),200()100(),300()0(max)300(434343433fgfgfgfgf67061,2839,4718,650max2003x 投資額 (j)工廠(i)0 100 200 300 400 500 600 30 18 39 61 78 90 95 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）第45頁(yè)/共69

32、頁(yè)所有情況討論結(jié)果匯總成下表： 3x3s)()(33433xsfxg)(33sf3x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 18+00+47 18+28 39+0 0+65 18+47 39+28 61+0 0+74 18+65 39+47 61+28 78+0 0+80 18+74 39+65 61+74 78+28 90+00+85 18+80 39+74 61+65 78+47 90+28 95+0 028476789108126000200300300300 表3 k=3 時(shí)決策表第46頁(yè)/共69頁(yè))600(

33、)(max)600(2322600022xfxgfx)600()(max2322600,500,400,300,200,100, 02xfxgx)600600()600()500600()500(),400600()400(),300600()300(),200600()200(),100600()100(),0600()0(max32323232323232fgfgfgfgfgfgfg（3）k=2 時(shí) )()(max)(2232202222xsfxgsfsx600,500,400,300,200,100, 022 Ss僅舉一例：6002s第47頁(yè)/共69頁(yè) 投資額 (j)工廠(i)0 100

34、 200 300 400 500 600 20 25 45 57 65 70 73 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）)0()600()100()500(),200()400(),300()300(),400()200(),500()100(),600()0(max)600(323232323232322fgfgfgfgfgfgfgf)0(73),100(70),200(65),300(57),400(45),500(25),600(0max3333333fffffff第48頁(yè)/共69頁(yè))0(73),100(70),200(65),300(57),400(45),500(25),600(0

35、max)600(33333332ffffffff3x3s)()(33433xsfxg)(33sf3x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 18+00+47 18+28 39+0 0+65 18+47 39+28 61+0 0+74 18+65 39+47 61+28 78+0 0+80 18+74 39+65 61+74 78+28 90+00+85 18+80 39+74 61+65 78+47 90+28 95+0 028476789108126000200300300300 表3 k=3 時(shí)決策表.13489

36、45073,2870,4765,6757,8945,10825,1260max2002x第49頁(yè)/共69頁(yè)關(guān)于 的其它取值情況及相應(yīng)的最優(yōu)決策列于下表2s2x2s)()(22322xsfxg)(22sf2x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 25+00+47 25+28 45+0 0+67 25+47 45+28 57+0 0+89 25+67 45+47 57+28 65+0 0+108 25+89 45+67 57+47 65+28 70+00+126 25+108 45+89 57+67 65+47 70+

37、28 73+0 02853739211413400100200100或或200100200 表4 k=2 時(shí)決策表第50頁(yè)/共69頁(yè)（4）k=1 時(shí) ，此時(shí),6001s)()(max)600()(11211011111xsfxgfsfsx)600()(max121160001xfxgx)600()(max1211600,500,400,300,200,100, 01xfxgx)600600()600()500600()500(),400600()400(),300600()300(),200600()200(),100600()100(),0600()0(max21212121212121fg

38、fgfgfgfgfgfg第51頁(yè)/共69頁(yè) 投資額 (j)工廠(i)0 100 200 300 400 500 600 10 20 42 60 75 85 90 表1 利潤(rùn)增長(zhǎng)額 )(jixg（百元）)600600(90)500600(85),400600(75),300600(60),200600(42),100600(20),0600(0max2222222fffffff)600600()600()500600()500(),400600()400(),300600()300(),200600()200(),100600()100(),0600()0(max)600(21212121212

39、1211fgfgfgfgfgfgfgf第52頁(yè)/共69頁(yè)2x2s)()(22322xsfxg)(22sf2x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 25+00+47 25+28 45+0 0+67 25+47 45+28 57+0 0+89 25+67 45+47 57+28 65+0 0+108 25+89 45+67 57+47 65+28 70+00+126 25+108 45+89 57+67 65+47 70+28 73+0 02853739211413400100200100或或200100200 表4

40、k=2 時(shí)決策表)600600(90),500600(85),400600(75),300600(60),200600(42),100600(20),0600(0max)600(22222221ffffffff.13490,113,128,133,134,134,134max090,2885,5375,7360,9242,11420,1340max第53頁(yè)/共69頁(yè)匯一表格：1x1s)()(11211xsfxg)(11sf1x0 100 200 300 400 500 600 600134 134 134 133 138 113 90 1340或或100或或200 表5 k=1 時(shí)決策表此時(shí)對(duì)

41、應(yīng)最大值134 的有三個(gè)值： 200,100, 01x所對(duì)應(yīng)的最優(yōu)策略分別為： 01x時(shí)，由狀態(tài)轉(zhuǎn)移方程112xss知：6000600112xss所對(duì)應(yīng)的?2x第54頁(yè)/共69頁(yè)2x2s)()(22322xsfxg)(22sf2x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 25+00+47 25+28 45+0 0+67 25+47 45+28 57+0 0+89 25+67 45+47 57+28 65+0 0+108 25+89 45+67 57+47 65+28 70+00+126 25+108 45+89 57+

42、67 65+47 70+28 73+0 02853739211413400100200100或或200100200 表4 k=2 時(shí)決策表 對(duì)應(yīng)的 2002x 再由狀態(tài)轉(zhuǎn)移方程400200600223xss 對(duì)應(yīng)的 ?3x第55頁(yè)/共69頁(yè)3x3s)()(33433xsfxg)(33sf3x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 18+00+47 18+28 39+0 0+65 18+47 39+28 61+0 0+74 18+65 39+47 61+28 78+0 0+80 18+74 39+65 61+74 78

43、+28 90+00+85 18+80 39+74 61+65 78+47 90+28 95+0 028476789108126000200300300300 表3 k=3 時(shí)決策表 所對(duì)應(yīng)的 3003x 再由狀態(tài)轉(zhuǎn)移方程100300400334xss 對(duì)應(yīng)的 ?4x第56頁(yè)/共69頁(yè)4x4s)(44xg)(44sf4x0 100 200 300 400 500 600 0 100 200 300 400 500 60000 280 28 470 28 47 65 0 28 47 65 74 0 28 47 65 74 800 28 47 65 74 80 8502847657480850100

44、200300400500600 表2 k=4 時(shí)決策表 對(duì)應(yīng)的 1004x從而得一最優(yōu)策略, 01x,2002x,3003x1004x第57頁(yè)/共69頁(yè)同理還有另外三個(gè)最優(yōu)策略:,2001x,1002x,2003x1004x,1001x,1002x,3003x1004x,2001x,2002x, 03x2004x所有解總利潤(rùn)最大增長(zhǎng)額為134)(11sf（百元）加上剛才一組,2002x,3003x1004x, 01x第58頁(yè)/共69頁(yè)資源分配問(wèn)題（連續(xù)型）：設(shè)備負(fù)荷分配問(wèn)題。例3:某公司有500輛運(yùn)輸卡車，在超負(fù)荷運(yùn)輸（即每天滿載行駛500km以上）情況下，年利潤(rùn)為25萬(wàn)元/輛，這時(shí)卡車的年損

45、壞率為0.3；在低負(fù)荷下運(yùn)輸（即每天行駛300km以下）情況下，年利潤(rùn)為16萬(wàn)元/輛。年損壞率為0.1。現(xiàn)要制定一個(gè)5年計(jì)劃，問(wèn)每年年初應(yīng)如何分配完好車輛，在兩種不同的負(fù)荷下運(yùn)輸?shù)目ㄜ嚁?shù)量，使在5年內(nèi)的總利潤(rùn)最大？解：這是一個(gè)以時(shí)間為特征的多階段決策問(wèn)題。第59頁(yè)/共69頁(yè)2s第1年第2年第3年第4年5001s投 x1輛 超負(fù)荷車狀態(tài)1122 . 09 . 0 xss2232 . 09 . 0 xss3342 . 09 . 0 xss3s4s5s狀態(tài)狀態(tài))(44xg)(33xg)(11xg)(22xg投 x2輛 超負(fù)荷車投 x3輛 超負(fù)荷車投 x4輛 超負(fù)荷車第5年投 x4輛 超負(fù)荷車)(55

46、xg狀態(tài)狀態(tài)6s4452 . 09 . 0 xss階段：將5年運(yùn)輸計(jì)劃看成5個(gè)階段的決策問(wèn)題。k=1,2,3,4,5狀態(tài)變量 ：第k階段初完好卡車數(shù)量 ，其中ks.5001s決策變量 ：表示第k 階段分配給超負(fù)荷運(yùn)輸?shù)目ㄜ嚁?shù)量。kx 顯然，分配給低負(fù)荷的卡車數(shù)為 kkxs )(1 . 01 ()3 . 01 (1kkkkxsxskkxs2 . 09 . 0第60頁(yè)/共69頁(yè)注：這里視 ， 為連續(xù)變量。若 =0.6表示有一輛卡車在第k年度有60的時(shí)間處于完好狀態(tài)。 =0.7表示有一輛卡車在第k年度有70時(shí)間在超負(fù)荷運(yùn)輸?shù)鹊取?kskxkskx狀態(tài)轉(zhuǎn)移方程： )(1 . 01 ()3 . 01 (1kkkkxsxskkxs2 . 09 . 05 , 4 , 3