ch7動(dòng)態(tài)規(guī)劃實(shí)例教學(xué)

1、動(dòng)態(tài)規(guī)劃v動(dòng)態(tài)規(guī)劃問題實(shí)例v動(dòng)態(tài)規(guī)劃的基本概念與原理v動(dòng)態(tài)規(guī)劃應(yīng)用舉例引 言動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種方法。動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種方法。該方法是由美國數(shù)學(xué)家貝爾曼（該方法是由美國數(shù)學(xué)家貝爾曼（R. E. Bellman)等人等人在在20世紀(jì)世紀(jì)50年代初提出的。并成功地解決了生產(chǎn)管年代初提出的。并成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多問題，從而建立了運(yùn)籌理、工程技術(shù)等方面的許多問題，從而建立了運(yùn)籌學(xué)的一個(gè)新的分支，即動(dòng)態(tài)規(guī)劃。學(xué)的一個(gè)新的分支，即動(dòng)態(tài)規(guī)劃。Bellman在在1957年出版了年出版了Dynamic Programming一書，是動(dòng)態(tài)一書，是動(dòng)態(tài)

2、規(guī)劃領(lǐng)域中的第一本著作。規(guī)劃領(lǐng)域中的第一本著作。1 動(dòng)態(tài)規(guī)劃問題實(shí)例例例1 給定一個(gè)線路網(wǎng)絡(luò)，給定一個(gè)線路網(wǎng)絡(luò)，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要從要從A向向F鋪設(shè)一條輸油管道，鋪設(shè)一條輸油管道，各點(diǎn)間連線上的數(shù)字表示距離，問應(yīng)選擇什么路線，可使總各點(diǎn)間連線上的數(shù)字表示距離，問應(yīng)選擇什么路線，可使總距離最短？距離最短？動(dòng)態(tài)規(guī)劃是解決動(dòng)態(tài)規(guī)劃是解決多階段決策問題多階段決策問題的一種方法。所謂多階段的一種方法。所謂多階段決策問題是指這樣的決策問題：其過程可分為若干個(gè)相互聯(lián)決策問題是指這樣的決策問題：其過程可分為若干個(gè)相互聯(lián)系的階段，每

3、一階段都對(duì)應(yīng)著一組可供選擇的決策，每一決系的階段，每一階段都對(duì)應(yīng)著一組可供選擇的決策，每一決策的選定即依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。策的選定即依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。當(dāng)每一階段的決策選定以后，就構(gòu)成一個(gè)決策序列，稱為一個(gè)當(dāng)每一階段的決策選定以后，就構(gòu)成一個(gè)決策序列，稱為一個(gè)ABCDE狀態(tài)A狀態(tài)B狀態(tài)C狀態(tài)D狀態(tài)E狀態(tài)F決策A決策D決策E決策B決策C策略策略，它對(duì)應(yīng)著一個(gè)確定的效果。它對(duì)應(yīng)著一個(gè)確定的效果。多階段決策問題就是尋找使多階段決策問題就是尋找使此效果最好的策略。此效果最好的策略。2 動(dòng)態(tài)規(guī)劃的基本概念與原理一?；靖拍钜??；靖拍铍A段階段：是指問題需要

4、做出決策的步數(shù)。階段總數(shù)常記為：是指問題需要做出決策的步數(shù)。階段總數(shù)常記為n，相相應(yīng)的是應(yīng)的是n個(gè)階段的決策問題。階段的序號(hào)常記為個(gè)階段的決策問題。階段的序號(hào)常記為k，稱為，稱為階段階段變量變量，k=1,2, ,n. k即可以是順序編號(hào)也可以是逆序編號(hào)，即可以是順序編號(hào)也可以是逆序編號(hào)，常用順序編號(hào)。常用順序編號(hào)。狀態(tài)狀態(tài)：各階段開始時(shí)的客觀條件，第：各階段開始時(shí)的客觀條件，第k階段的狀態(tài)常用階段的狀態(tài)常用狀態(tài)狀態(tài)變量變量 表示，狀態(tài)變量取值的集合成為狀態(tài)集合，用表示，狀態(tài)變量取值的集合成為狀態(tài)集合，用表示。表示。kskS例如，例例如，例1中，中，.,2121BBSASAB1B2C1C2C3C

5、4D1D2D3E1E2F452368775845348435623143第第1階階段段第第2階階段段第第3階階段段第第4階階段段第第5階階段段狀狀態(tài)態(tài)1狀狀態(tài)態(tài)2狀狀態(tài)態(tài)3狀狀態(tài)態(tài)4狀狀態(tài)態(tài)5狀狀態(tài)態(tài)6決策決策：是指從某階段的某個(gè)狀態(tài)出發(fā)，在若干個(gè)不同方案中：是指從某階段的某個(gè)狀態(tài)出發(fā)，在若干個(gè)不同方案中做出的選擇。表示決策的變量，稱為做出的選擇。表示決策的變量，稱為決策變量決策變量，用，用 表示表示)(kksu例如：例如： 表示走到表示走到C階段階段,當(dāng)處于當(dāng)處于C2 路口時(shí)，下一路口時(shí)，下一步奔步奔D1.123)(DCu 時(shí)的允許決策集合記為時(shí)的允許決策集合記為 ，例如：，例如：ks)(k

6、ksD,)(32112CCCBD狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：是從上一階段的某一狀態(tài)值轉(zhuǎn)變?yōu)橄乱浑A段：是從上一階段的某一狀態(tài)值轉(zhuǎn)變?yōu)橄乱浑A段某一狀態(tài)值的轉(zhuǎn)移規(guī)律，用某一狀態(tài)值的轉(zhuǎn)移規(guī)律，用 ),(1kkkkusTs表示。表示。決策變量允許的取值范圍稱為決策變量允許的取值范圍稱為允許決策集合允許決策集合，第，第k階段狀態(tài)為階段狀態(tài)為 指標(biāo)函數(shù)指標(biāo)函數(shù)：分：分階段指標(biāo)函數(shù)階段指標(biāo)函數(shù)和和過程指標(biāo)函數(shù)過程指標(biāo)函數(shù)。階段指標(biāo)函數(shù)。階段指標(biāo)函數(shù)是指第是指第k階段從狀態(tài)階段從狀態(tài) 出發(fā)，采取決策出發(fā)，采取決策 時(shí)的效益，用時(shí)的效益，用ksku),(kkkusv表示。而過程指標(biāo)函數(shù)從第表示。而過程指標(biāo)函數(shù)從第k

7、階段的某狀態(tài)出發(fā)，階段的某狀態(tài)出發(fā)，采取子策略采取子策略,1nkkknuuup時(shí)所得到的階段效益之和：時(shí)所得到的階段效益之和：nkjjjjknkknusvpsV),(),(最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù)：表示從第：表示從第k階段狀態(tài)為階段狀態(tài)為 時(shí)采用最佳策略時(shí)采用最佳策略ks*knp到過程終止時(shí)的最佳效益。記為到過程終止時(shí)的最佳效益。記為),(),()()(*knkknsDpknkknkkpsVoptpsVsfkknkn其中其中 opt 可根據(jù)具體情況取可根據(jù)具體情況取max 或或min?；痉匠袒痉匠蹋捍藶橹鸲芜f推求和的依據(jù)，一般為：此為逐段遞推求和的依據(jù)，一般為：0)(1 , 1,)(),(

8、)(1111)(nnkkkkksDukksfnnksfusvoptsfkkk式中式中opt 可根據(jù)題意取可根據(jù)題意取 max 或或 min.例如，例例如，例1的基本方程為：的基本方程為：0)(1 , 2 , 3 , 4 , 5)(),(min)(6611sfksfusdsfkkkkkukkk最優(yōu)性原理最優(yōu)性原理：最優(yōu)策略的子策略必為最優(yōu)。不管過去的狀態(tài)：最優(yōu)策略的子策略必為最優(yōu)。不管過去的狀態(tài)和決策如何，從眼下直到最后的諸決策必構(gòu)成最優(yōu)子策略。和決策如何，從眼下直到最后的諸決策必構(gòu)成最優(yōu)子策略。動(dòng)態(tài)規(guī)劃應(yīng)用舉例動(dòng)態(tài)規(guī)劃應(yīng)用舉例例例1 最短路線問題最短路線問題AB1B2C1C2C3C4D1D2D

9、3E1E2F452368775845348435623143逆序遞推方程：逆序遞推方程：0)(1 , 2 , 3 , 4 , 5)(),(min)(6611sfksfusdsfkkkkkukkk（1）k=5 時(shí)，狀態(tài)時(shí)，狀態(tài),215EES它們到它們到F 點(diǎn)的距離即為點(diǎn)的距離即為最短路。最短路。, 4)(15Ef; 3)(25Ef,)(1*5FEu.)(2*5FEuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4 時(shí)，狀態(tài)時(shí)，狀態(tài),3214D

10、DDS它們到它們到F 點(diǎn)需經(jīng)過中途點(diǎn)需經(jīng)過中途點(diǎn)點(diǎn)E，需一一分析從，需一一分析從E 到到 F的最短路：先說從的最短路：先說從D1到到F 的最短路的最短路有兩種選擇：經(jīng)過有兩種選擇：經(jīng)過 E1, E2, 比較最短。比較最短。.)(2*5FEu,)(1*5FEuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252141511414EfEDdEfEDdDf. 735 , 43min這說明由這說明由 D1 到到F 的最短距離為的最短距離為7，其路徑為，其路徑為.11FED相應(yīng)的決策為：相應(yīng)的決策為：.)(11*4EDu.

11、)(2*5FEu,)(1*5FEu)(),(),(),(min)(252241512424EfEDdEfEDdDf. 532 , 46min這說明由這說明由 D2 到到F 的最短距離為的最短距離為5，其路徑為，其路徑為.22FED相應(yīng)的決策為：相應(yīng)的決策為：.)(22*4EDuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252341513434EfEDdEfED

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

13、2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu5)(24Df7)(14DfAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(242231412323DfDCdDfDCdCf.1055 , 74min即由即由 C2 到到F 的最短距離為的最短距離為10，相應(yīng)的決策為，相應(yīng)的決策為.)(22*3DCu)(),(),(),(min)(343332423333DfDCdDfDCdCf. 854 , 53min.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4ED

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

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

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

17、9)(43Cf10)(23Cf8)(33CfAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1 時(shí)，只有一個(gè)狀態(tài)點(diǎn)時(shí)，只有一個(gè)狀態(tài)點(diǎn)A, 則則)(),(),(),(min)(222112111BfBAdBfBAdAf.17155 ,134min即由即由 A到到F 的最短距離為的最短距離為17，相應(yīng)的決策為，相應(yīng)的決策為.)(1*1BAu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)(2

18、1*2CBu13)(12Bf15)(22Bf,)(21*2CBu,)(22*3DCu,)(22*4EDu.)(2*5FEu所以最優(yōu)路線為：所以最優(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)決策序列：再按計(jì)算順序反推可得最優(yōu)決策序列：,)(1*1BAu順序遞推方程：順序遞推方程：

19、初始條件0)(5 , 4 , 3 , 2 , 1)(),(min)(10111sfksfusdsfkkkkkukkkAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例例1：1階段階段2階段階段3階段階段4階段階段5階段階段行走方向行走方向AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1 時(shí)時(shí))(),()()(10111121sfABdBfsf注意到：注意到：0)()(010Afsf所以所以ABu)(1*1)(),()()(10212121sfABdBfsf, 4)(11Bf, 5)(21BfA

20、Bu)(2*1K=2 時(shí)時(shí)642)(),()()(111121232BfBCdCfsf11*2)(BCuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*1)(),(),(),(min)()(21222111222232BfBCdBfBCdCfsf758 , 43min12*2)(BCu)(),(),(),(min)()(21232111323232BfBCdBfBCdCfsf13*2)(BCu,1257)(),()()(212424232BfBCdCfsf24*2)(BCuK=3 時(shí)時(shí))(),(),(),(min)(

21、)(22212121131343CfCDdCfCDdDfsf1174 , 65minAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*1,1057 , 46min11*2)(BCu12*2)(BCu6)(12Cf7)(22CfAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*112*2)(BCu11*2)(BCu13*2)(BCu24*2)(BCu,)(11*3CDu21*3)(CDu或或類似地，可算出：類似地，可算出：12)(23Df22*3

22、)(CDu14)(33Df33*3)(CDu6)(12Cf7)(22Cf12)(42Cf10)(32Cf14)(14Ef11*4)(DEu14)(24Ef22*4)(DEu17)(5Ff2*5)(EFu最優(yōu)策略：最優(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)(13Df22*3)(CDu

23、12*2)(BCuABu)(1*1最短路徑：最短路徑：FEDCBA2221最短路長：最短路長：17)(5Ff注注：順序解法與逆序解法無本質(zhì)區(qū)別，一般來說，當(dāng)初始狀：順序解法與逆序解法無本質(zhì)區(qū)別，一般來說，當(dāng)初始狀態(tài)給定時(shí)用逆序解法，當(dāng)終止?fàn)顟B(tài)給定時(shí)用順序解法。若問態(tài)給定時(shí)用逆序解法，當(dāng)終止?fàn)顟B(tài)給定時(shí)用順序解法。若問題給定了一個(gè)初始狀態(tài)與一個(gè)終止?fàn)顟B(tài)，則兩種方法均可使題給定了一個(gè)初始狀態(tài)與一個(gè)終止?fàn)顟B(tài)，則兩種方法均可使用。用。資源分配問題（連續(xù)型）：設(shè)備負(fù)荷分配問題。資源分配問題（連續(xù)型）：設(shè)備負(fù)荷分配問題。例例 某公司有某公司有500輛運(yùn)輸卡車，在超負(fù)荷運(yùn)輸（即每天輛運(yùn)輸卡車，在超負(fù)荷運(yùn)輸（即

24、每天滿載行駛滿載行駛500km以上）情況下，年利潤為以上）情況下，年利潤為25萬元萬元/輛，輛，這時(shí)卡車的年損壞率為這時(shí)卡車的年損壞率為0.3；在低負(fù)荷下運(yùn)輸（即每；在低負(fù)荷下運(yùn)輸（即每天行駛天行駛300km以下）情況下，年利潤為以下）情況下，年利潤為16萬元萬元/輛。輛。年損壞率為年損壞率為0.1?，F(xiàn)要制定一個(gè)。現(xiàn)要制定一個(gè)5年計(jì)劃，問每年年初年計(jì)劃，問每年年初應(yīng)如何分配完好車輛，在兩種不同的負(fù)荷下運(yùn)輸?shù)目☉?yīng)如何分配完好車輛，在兩種不同的負(fù)荷下運(yùn)輸?shù)目ㄜ嚁?shù)量，使在車數(shù)量，使在5年內(nèi)的總利潤最大？年內(nèi)的總利潤最大？解：這是一個(gè)以時(shí)間為特征的多階段決策問題。解：這是一個(gè)以時(shí)間為特征的多階段決策問

25、題。第第1年年第第2年年第第3年年第第4年年5001s投投 x1輛 超輛 超負(fù)荷車負(fù)荷車狀態(tài)狀態(tài)2s1122 . 09 . 0 xss2232 . 09 . 0 xss3342 . 09 . 0 xss3s4s5s狀態(tài)狀態(tài)狀態(tài)狀態(tài))(44xg)(33xg)(11xg)(22xg投投 x2輛 超輛 超負(fù)荷車負(fù)荷車投投 x3輛 超輛 超負(fù)荷車負(fù)荷車投投 x4輛 超輛 超負(fù)荷車負(fù)荷車第第5年年投投 x4輛 超輛 超負(fù)荷車負(fù)荷車)(55xg狀態(tài)狀態(tài)狀態(tài)狀態(tài)6s4452 . 09 . 0 xss階段：將階段：將5年運(yùn)輸計(jì)劃看成年運(yùn)輸計(jì)劃看成5個(gè)階段的決策問題。個(gè)階段的決策問題。k=1,2,3,4,5狀態(tài)

26、變量狀態(tài)變量 ：第：第k階段初完好卡車數(shù)量階段初完好卡車數(shù)量 ，其中，其中ks.5001s決策變量決策變量 ：表示第：表示第k 階段分配給超負(fù)荷運(yùn)輸?shù)目ㄜ嚁?shù)量。階段分配給超負(fù)荷運(yùn)輸?shù)目ㄜ嚁?shù)量。kx 顯然，分配給低負(fù)荷的卡車數(shù)為顯然，分配給低負(fù)荷的卡車數(shù)為 kkxs )(1 . 01 ()3 . 01 (1kkkkxsxskkxs2 . 09 . 0注：這里視注：這里視 ， 為連續(xù)變量。若為連續(xù)變量。若 =0.6表示有一輛卡表示有一輛卡車在第車在第k年度有年度有60的時(shí)間處于完好狀態(tài)。的時(shí)間處于完好狀態(tài)。 =0.7表示有表示有一輛卡車在第一輛卡車在第k年度有年度有70時(shí)間在超負(fù)荷運(yùn)輸?shù)鹊?。時(shí)間在

27、超負(fù)荷運(yùn)輸?shù)鹊取?kskxkskx狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： )(1 . 01 ()3 . 01 (1kkkkxsxskkxs2 . 09 . 05 , 4 , 3 , 2 , 1k 階段指標(biāo)函數(shù)階段指標(biāo)函數(shù) ：表示第：表示第 k 年度利潤。年度利潤。)(kkxg5 , 4 , 3 , 2 , 1k)(1625)(kkkkkxsxxgkkxs9165 , 4 , 3 , 2 , 1k最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) ：第：第 k 年度初完好車輛數(shù)為年度初完好車輛數(shù)為 時(shí)，采時(shí)，采用最優(yōu)策略到第用最優(yōu)策略到第 5 年末所產(chǎn)生的最大利潤。年末所產(chǎn)生的最大利潤。 )(kksfks逆序遞推式為：逆序遞推式為

28、： 0)(1 , 2 , 3 , 4 , 5)()(max)(66110sfksfxgsfkkkksxkkkk1） k=5時(shí)時(shí))()(max)(665505555sfxgsfsx（注意到此時(shí)（注意到此時(shí) =0） )(66sf)(max55055xgsx 916max55055xssx916max)(5505555xssfsx5f5x5s516so55525916sss5*5sx 此時(shí)此時(shí)2） k=4 時(shí)時(shí))()(max)(554404444sfxgsfsx25916max544044sxssx)2 . 09 . 0(25916max4444044xsxssx45 .38max44044xssx

29、同理，只有當(dāng)同理，只有當(dāng)44sx 時(shí)，函數(shù)時(shí)，函數(shù)4445 .38xs 才能達(dá)到極大值。故有才能達(dá)到極大值。故有4*4sx 4445 .42)(ssf3） k=3 時(shí)時(shí))()(max)(443303333sfxgsfsx5 .42916max433033sxssx)2 . 09 . 0(5 .42916max3333033xsxssx5 . 025.54max33033xssx不難得到不難得到3*3sx 33375.54)(ssf4） k=2 時(shí)時(shí))()(max)(332202222sfxgsfsx)2 . 09 . 0(75.54916max2222022xsxssx95. 1275.65m

30、ax22022xssx2f2x247.33s2275.65so可見，只有當(dāng)可見，只有當(dāng)02x時(shí)，函數(shù)時(shí)，函數(shù)2295. 1275.65xs 才能達(dá)到才能達(dá)到極大值。故有極大值。故有, 0*2x222275.65)(ssf33375.54)(ssf5） k=1 時(shí)時(shí))()(max)500()(2211011111sfxgfsfsx275.65916max21150001sxsx)2 . 09 . 0(275.65916max111150001xsxsx055. 47475.74max1150001xsx同理，只有當(dāng)同理，只有當(dāng)時(shí)，函數(shù)時(shí)，函數(shù), 0*1x75.373735007475.74747

31、5.74)(111ssf01x11055. 47475.74xs 才能達(dá)到才能達(dá)到極大值。故有極大值。故有（萬元）（萬元）所對(duì)應(yīng)的最優(yōu)策略分別為：所對(duì)應(yīng)的最優(yōu)策略分別為： 01x時(shí)，由狀態(tài)轉(zhuǎn)移方程時(shí)，由狀態(tài)轉(zhuǎn)移方程kkkxss2 . 09 . 014505009 . 02 . 09 . 0112xss由由, 0*2x且且4054509 . 02 . 09 . 0223xss再由再由3*3sx 且且5 .2834052 . 04059 . 02 . 09 . 0334xss4*4sx 45.1985 .2832 . 05 .2839 . 02 . 09 . 0445xss5*5sx 15.138

32、45.1982 . 045.1989 . 02 . 09 . 0556xss第一年初：第一年初：500輛車全部用于低負(fù)荷運(yùn)輸。輛車全部用于低負(fù)荷運(yùn)輸。第二年初：還有第二年初：還有450輛完好的車，也全部用于低負(fù)荷運(yùn)輸。輛完好的車，也全部用于低負(fù)荷運(yùn)輸。第三年初：還有第三年初：還有405輛完好的車，全部用于超負(fù)荷運(yùn)輸。輛完好的車，全部用于超負(fù)荷運(yùn)輸。第四年初：還有第四年初：還有238.5輛完好的車，全部用于超負(fù)荷運(yùn)輸。輛完好的車，全部用于超負(fù)荷運(yùn)輸。第五年初：還有第五年初：還有198.45輛完好的車，全部用于超負(fù)荷運(yùn)輸。輛完好的車，全部用于超負(fù)荷運(yùn)輸。到第五年末，即第六年初，還剩余到第五年末，即

33、第六年初，還剩余138.15輛完好的車。輛完好的車。實(shí)現(xiàn)最大利潤實(shí)現(xiàn)最大利潤74. 3)(11sf（億元）（億元）背背 包包 問問 題題 一般的提法為：一旅行者攜帶背包去登山。已知他所能承受一般的提法為：一旅行者攜帶背包去登山。已知他所能承受 的背包重量的極限為的背包重量的極限為a (千克千克)，現(xiàn)有，現(xiàn)有n種物品可供他選擇裝入種物品可供他選擇裝入背包。第背包。第i種物品的單位重量為種物品的單位重量為 (千克千克)，其價(jià)值（可以是，其價(jià)值（可以是表表明本物品對(duì)登山者的重要性指標(biāo)）是攜帶數(shù)量明本物品對(duì)登山者的重要性指標(biāo)）是攜帶數(shù)量 的函數(shù)的函數(shù) （i=1，2，n）.問旅行者應(yīng)如何選擇攜帶物品的件

34、問旅行者應(yīng)如何選擇攜帶物品的件數(shù)，以使總價(jià)值最大？數(shù)，以使總價(jià)值最大？ia)(iixgix此模型解決的是運(yùn)輸工具包括衛(wèi)星的最優(yōu)裝載問題。此模型解決的是運(yùn)輸工具包括衛(wèi)星的最優(yōu)裝載問題。其數(shù)學(xué)模型為：其數(shù)學(xué)模型為：設(shè)設(shè) 為第為第 i 種物品裝入的件數(shù)，則背包問題可歸結(jié)為如下種物品裝入的件數(shù)，則背包問題可歸結(jié)為如下 ix形式的整數(shù)規(guī)劃模型：形式的整數(shù)規(guī)劃模型：niiixgz1)(max), 2 , 101nixaxainiii（整數(shù)下面從一個(gè)例子來分析動(dòng)態(tài)規(guī)劃建模。下面從一個(gè)例子來分析動(dòng)態(tài)規(guī)劃建模。例例 有一輛最大貨運(yùn)量為有一輛最大貨運(yùn)量為10 t 的卡車，用以裝載的卡車，用以裝載3種種貨物，每種貨

35、物的單位重量及相應(yīng)單位價(jià)值如表貨物，每種貨物的單位重量及相應(yīng)單位價(jià)值如表 所示。所示。應(yīng)如何裝載可使總價(jià)值最大？應(yīng)如何裝載可使總價(jià)值最大？貨物編號(hào)貨物編號(hào)i 1 2 3單位重量（單位重量（t） 3 4 5單位價(jià)值單位價(jià)值 ci 4 5 6設(shè)第設(shè)第 種貨物裝載的件數(shù)為種貨物裝載的件數(shù)為 ix),3 , 2 , 1( ii則問題可表為：則問題可表為：321654maxxxxz)3 , 2 , 1(, 010543321ixxxxi整數(shù)階段階段k: 將可裝入物品按將可裝入物品按1，2，3的順序排序，每段裝入一的順序排序，每段裝入一種物品，共劃分種物品，共劃分3個(gè)階段，即個(gè)階段，即k=1,2,3.狀態(tài)

36、變量狀態(tài)變量 ：在第：在第k段開始時(shí)，背包中允許裝入前段開始時(shí)，背包中允許裝入前k種種物品的總重量。物品的總重量。1ks決策變量決策變量 ：裝入第：裝入第k種物品的件數(shù)。種物品的件數(shù)。kx狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：kkkkxass1最優(yōu)指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù) ：在背包中允許裝入物品的總重量不：在背包中允許裝入物品的總重量不超超過過 kg，采取最優(yōu)策略只裝前，采取最優(yōu)策略只裝前k種物品時(shí)的最大使用價(jià)值種物品時(shí)的最大使用價(jià)值)(1kksf1ks貨物貨物1貨物貨物2貨物貨物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13x由此

37、可得動(dòng)態(tài)規(guī)劃的順序遞推方程為：由此可得動(dòng)態(tài)規(guī)劃的順序遞推方程為：0)(3 , 2 , 1)()(max)(1011011sfkxasfxgsfkkkkkksxakkkkk貨物貨物1貨物貨物2貨物貨物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13xK=1 時(shí)時(shí))()(max)(10113021121sfxgsfxsx為整數(shù)4max130121xxsx為整數(shù)貨物貨物1貨物貨物2貨物貨物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13xK=1 時(shí)時(shí))(

38、)(max)(10113021121sfxgsfxsx為整數(shù)4max130121xxsx為整數(shù)注意到：注意到：10, 1 , 02s例如：例如：72s時(shí)，時(shí)，4max)7(1730111xfxx為整數(shù)4max12, 1 , 01xx 88 , 4 , 0max2*1x其它計(jì)算結(jié)果見表其它計(jì)算結(jié)果見表7-5：1x2s14x)(21sf1x0 1 2 3 0 1 2 3 4 5 6 7 8 9 104 40 04 40 0 4 40 0 4 40 0 4 41 1 4 40 40 41 41 42 24 40 40 41 41 42 42 43 3000481202400123表 7- 5貨物1貨

39、物2貨物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13xK=2 時(shí))()(max)(21224032232sfxgsfxsx為整數(shù))4(5max231240232xsfxxsx為整數(shù)其中10, 1 , 03s例如：103s時(shí)，)410(5max)10()(212104023222xfxfsfxx為整數(shù))410(5max2122, 1 , 02xfxx)0(10),6(5),10(0max111fff)0(10),6(5),10(0max111fff13010, 85 ,120max1*2x1x2s14x)(21sf1x

40、0 1 2 3 0 1 2 3 4 5 6 7 8 9 104 40 04 40 0 4 40 0 4 40 0 4 41 1 4 40 40 41 41 42 24 40 40 41 41 42 42 43 3000481202400123表 7- 5其它計(jì)算結(jié)果見表7-6：2x3s)4(52312xsfx)(32sf2x 0 1 2 0 1 2 3 4 5 6 7 8 9 105 50 00 0 5 50 04 4 5 51 10 0 5 50 012 512 51 18 58 52 20 0 0513011表 7- 6貨物1貨物2貨物3104s3435xss2324xss1213xss1

41、114)(xxg2225)(xxg3336)(xxg24x35x13xK=3 時(shí))()(max)10()(323350343343sfxgfsfxsx為整數(shù))510(6max323105033xfxxx為整數(shù))510(6max3232, 1 , 03xfxx)0(12),5(6),10(0max222fff2x3s)4(52312xsfx)(32sf2x 0 1 2 0 1 2 3 4 5 6 7 8 9 105 50 00 0 5 50 04 4 5 51 10 0 5 50 012 512 51 18 58 52 20 0 0513011表 7- 6)0(12),5(6),10(0max2

42、22fff13012, 56 ,130max0*3x從0*3x再由狀態(tài)轉(zhuǎn)移方程100105*343xss2x3s)4(52312xsfx)(32sf2x 0 1 2 0 1 2 3 4 5 6 7 8 9 105 50 00 0 5 50 04 4 5 51 10 0 5 50 012 512 51 18 58 52 20 0 0513011表 7- 61*2x貨物1貨物2貨物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13x再由狀態(tài)轉(zhuǎn)移方程64104*232xss1x2s14x)(21sf1x0 1 2 3 0 1 2

43、 3 4 5 6 7 8 9 104 40 04 40 0 4 40 0 4 40 0 4 41 1 4 40 40 41 41 42 24 40 40 41 41 42 42 43 3000481202400123表 7- 52*1x最大裝載價(jià)值為 .13)10(3f總結(jié)：今后解背包問題應(yīng)先從k=3入手：k=3時(shí) )()(max)10()(323350343343sfxgfsfxsx為整數(shù))510(6max323105033xfxxx為整數(shù))510(6max3232, 1 , 03xfxx)0(12),5(6),10(0max222fff下面應(yīng)有重點(diǎn)地從k=2中求解三個(gè)最優(yōu)函數(shù)值： )10(

44、2f)5(2f)0(2fK=2 時(shí))()(max)(21224032232sfxgsfxsx為整數(shù))4(5max231240232xsfxxsx為整數(shù))410(5max)10()(212104023222xfxfsfxx為整數(shù))410(5max2122, 1 , 02xfxx)2(10),6(5),10(0max111fff)45(5max)5()(21254023222xfxfsfxx為整數(shù))45(5max2121 , 02xfxx)1 (5),5(0max11ff)40(5max)0()(21204023222xfxfsfxx為整數(shù))0(0max)40(5max121202fxfxx所以從

45、第一階段應(yīng)有重點(diǎn)地求以下四個(gè)數(shù)：所以從第一階段應(yīng)有重點(diǎn)地求以下四個(gè)數(shù)： )0(1f) 1 (1f)6(1f)10(1f)()(max)(10113021121sfxgsfxsx為整數(shù)K=1 時(shí)時(shí)4max130121xxsx為整數(shù)4max)0(1030111xfxx為整數(shù)04max101xx4max) 1 (1130111xfxx為整數(shù)04max101xx0*1x0*1x)2(1f)5(1f4max)6(1630111xfxx為整數(shù)88 , 4 , 0max4max12, 1 , 01xx2*1x4max)10(11030111xfxx為整數(shù)1212, 8 , 4 , 0max4max13 ,

46、2, 1 , 01xx3*1x由此逐一逆推代回上式：由此逐一逆推代回上式：4max)5(1530111xfxx為整數(shù)44 , 0max4max11 , 01xx1*1x4max)2(1230111xfxx為整數(shù)04max101xx0*1x)0(2f, 0)0(0max)40(5max121202fxfxx, 0)0(1f0*2x)1 (5),5(0max)5(112fff505 , 40max1*2x, 0) 1 (1f0*1x4max)6(1630111xfxx為整數(shù)88 , 4 , 0max4max12, 1 , 01xx2*1x4max)10(11030111xfxx為整數(shù)1212, 8

47、 , 4 , 0max4max13 , 2, 1 , 01xx3*1x4max)5(1530111xfxx為整數(shù)44 , 0max4max11 , 01xx1*1x4max)2(1230111xfxx為整數(shù)04max101xx0*1x由此逐一逆推代回上式：由此逐一逆推代回上式：4max)6(1630111xfxx為整數(shù)88 , 4 , 0max4max12, 1 , 01xx2*1x4max)10(11030111xfxx為整數(shù)1212, 8 , 4 , 0max4max13 , 2, 1 , 01xx3*1x4max)5(1530111xfxx為整數(shù)44 , 0max4max11 , 01x

48、x1*1x4max)2(1230111xfxx為整數(shù)04max101xx0*1x由此逐一逆推代回上式：由此逐一逆推代回上式：)2(10),6(5),10(0max)10(1112ffff13010, 85 ,120max1*2x)0(12),5(6),10(0max)10(2223ffff13012, 56 ,130max0*3x最后最后最優(yōu)策略：最優(yōu)策略：0*3x再由狀態(tài)轉(zhuǎn)移方程再由狀態(tài)轉(zhuǎn)移方程100105*343xss1*2x再由狀態(tài)轉(zhuǎn)移方程再由狀態(tài)轉(zhuǎn)移方程64104*232xss2*1x最大裝載價(jià)值為最大裝載價(jià)值為 .13)10(3f用動(dòng)態(tài)規(guī)劃方法求解：用動(dòng)態(tài)規(guī)劃方法求解：)3 , 2

49、, 1(010342321ixxxxi2321294maxxxxF解：我們用背包問題順序解的思路：解：我們用背包問題順序解的思路：人為的劃分三個(gè)階段：人為的劃分三個(gè)階段：k=1,2,3階段指標(biāo)函數(shù)及其他分配情況如下圖：階段指標(biāo)函數(shù)及其他分配情況如下圖：1231114)(xxg2229)(xxg23332)(xxg33x24x12x1212xss2324xss3433xss104s1231114)(xxg2229)(xxg23332)(xxg33x24x12x1212xss2324xss3433xss104s動(dòng)態(tài)規(guī)劃的順序遞推方程為：動(dòng)態(tài)規(guī)劃的順序遞推方程為：0)(3 , 2 , 1)()(ma

50、x)(1011011sfkxasfxgsfkkkkkksxakkkkk)()(max)10()(32335034343sfxgfsfsx)310(2max322310303xfxx)310(2max3223310, 1 , 03xfxx)1 (18),4(8),7(2),10(0max2222ffff)()(max)(2122403232sfxgsfsx)4()(max231224032xsfxgsx)10(2f)410(9max212410, 1 , 02xfxx1231114)(xxg2229)(xxg23332)(xxg33x24x12x1212xss2324xss3433xss104s

51、)10(2f)410(9max212410, 1 , 02xfxx)410(9max2122, 1 , 02xfxx)2(18),6(9),10(0max111fff)7(2f)47(9max2127402xfxx)47(9max2121 , 02xfxx)3(9),7(0max11ff)4(2f)44(9max2124402xfxx)44(9max2121 , 02xfxx)0(9),4(0max11ff) 1 (2f)41 (9max2121402xfxx)41 (9max21202xfxx) 1 (1f1231114)(xxg2229)(xxg23332)(xxg33x24x12x121

52、2xss2324xss3433xss104s)()(max)(1011202121sfxgsfsx4max12021xsx )0(1f4max10201xx , 04max101xx01x) 1 (1f, 04max101xx4max10201xx 01x)2(1f4max12201xx 4max11 , 01xx , 44, 0max11x)3(1f4max13201xx 4max11 , 01xx , 44, 0max11x)4(1f4max14201xx 4max12, 1 , 01xx , 88, 4, 0max21x)6(1f4max16201xx 4max13 , 2, 1 , 0

53、1xx ,1212, 8, 4, 0max31x)7(1f4max17201xx 4max13 , 2, 1 , 01xx ,1212, 8, 4, 0max31x, 0)0(1f, 0)1 (1f, 4)2(1f, 4)3(1f, 8)4(1f,12)6(1f.20)10(1f)1 (2f, 0) 1 (1 f)4(2f)0(9),4(0max11ff, 909, 80max)10(1f4max110201xx 4max15 , 4, 2, 1 , 01xx ,1212, 8, 4, 0max,2020,16,12, 8, 4, 0max51x,12)7(1f)41 (9max21202xf

54、xx02x)44(9max2121 , 02xfxx12x)7(2f)3(9),7(0max11ff)47(9max2121 , 02xfxx)10(2f)2(18),6(9),10(0max111fff, 0)0(1f, 0)1 (1f, 4)2(1f, 4)3(1f, 8)4(1f,12)6(1f.20)10(1f,12)7(1f)7(2f)3(9),7(0max11ff)47(9max2121 , 02xfxx,1349,120max12x)410(9max2122, 1 , 02xfxx,22418,129,200max22x)310(2max)10()(32233 , 2, 1 ,

55、03433xfxfsfx)1 (18),4(8),7(2),10(0max2222ffff,22018, 98,132,220max03x,100103343xss02x12x12x22x,22)10()(232 fsf, 9)4()(232 fsf,13)7()(232 fsf, 0) 1 ()(232 fsf22x, 4)2()(121 fsf11x, 28104232xss,100103343xss22x11x最優(yōu)決策為最優(yōu)決策為, 11x, 22x03x所對(duì)應(yīng)的最優(yōu)解為所對(duì)應(yīng)的最優(yōu)解為.22)10()(343 fsf例（二維背包）例（二維背包） 有一輛最大貨運(yùn)量為有一輛最大貨運(yùn)量為13

56、t、最大容量為、最大容量為10件的卡車，用以裝載件的卡車，用以裝載3種貨物，每種貨物的單位重量及相種貨物，每種貨物的單位重量及相應(yīng)單位價(jià)值如下表所示。應(yīng)如何裝載可使總價(jià)值最大？應(yīng)單位價(jià)值如下表所示。應(yīng)如何裝載可使總價(jià)值最大？貨物編號(hào)貨物編號(hào)i i 1 1 2 2 3 3單位重量（單位重量（t t） 1 1 3 3 6 6單位價(jià)值單位價(jià)值 c ci i 4 4 5 5 8 8解：設(shè)裝載第解：設(shè)裝載第i種貨物的件數(shù)為種貨物的件數(shù)為 （i=1,2,3），則問題可表述為），則問題可表述為136310.321321xxxxxxts321854maxxxxzNxixii3 , 2 , 1, 0ix1231

57、114)(xxg2225)(xxg3338)(xxg36x23x1x121xss232xss343xss104s關(guān)于件數(shù)的約束關(guān)于件數(shù)的約束:kkkxss1關(guān)于重量的約束關(guān)于重量的約束:kkkkxauu13, 2, 1k3, 2, 1k134u3436xsu2323xuu121xuu基本方程式：基本方程式：0),(3 , 2 , 1),()(max),(110111001111usfkxauxsfxgusfkkkkkkkkuxasxkkkkkkkk11a32a63a1231114)(xxg2225)(xxg3338)(xxg36x23x1x121xss232xss343xss104s134u3

58、436xsu2323xuu121xuu0),(3 , 2 , 1),()(max),(110111 ,min01111usfkxauxsfxgusfkkkkkkkkausxkkkkkkk11a32a63a問題就是求：問題就是求：)613,10()(max)13,10(),(332331360100344333xxfxgfusfxx1231114)(xxg2225)(xxg3338)(xxg36x23x1x121xss232xss343xss104s134u3436xuu2323xuu121xuu)613,10()(max33233613 ,10min, 1 , 03xxfxgx)613,10(

59、8max33232, 1 , 03xxfxx11a32a63a)613,10(8max33232, 1 , 03xxfxx)1 , 8(16),7 , 9(8),13,10(0max222fff),()(max),(221223003323232usfxgusfuxsx)3,()(max23231223 ,min, 1 , 0332xuxsfxgusx)313,10(5max)13,10(2212313 ,10min, 1 , 022xxfxfx)313,10(5max22124, 1 , 02xxfxx)1 , 6(20),4 , 7(15),7 , 8(10),10, 9(5),13,10

60、(max11111fffff)37 ,9(5max)7 , 9(221237 , 9min, 1 , 022xxfxfx)37 ,9(5max22122, 1 , 02xxfxx)1 , 7(10),4 , 8(5),7 , 9(max111fff)31 ,8(5max) 1 , 8(221231 , 8min, 1 , 022xxfxfx)31 ,8(5max221202xxfxx)1 , 8(0max1f),()(max),(11011,min0221221usfxgusfusx4max1,min0221xusx 1231114)(xxg2225)(xxg3338)(xxg36x23x1x