第七章動(dòng)態(tài)規(guī)劃

1、 第七章 動(dòng) 態(tài) 規(guī) 劃 第一講 概念及最短路問(wèn)題動(dòng)態(tài)規(guī)劃（Dynamic Programming）是20世紀(jì)50年代由美國(guó)數(shù)學(xué)家貝爾曼（Richard Bellman）及他的學(xué)生們一同建立和發(fā)展起來(lái)的一種解多階段決策問(wèn)題的優(yōu)化方法。所謂多階段決策問(wèn)題是指一類活動(dòng)過(guò)程。它可按時(shí)間或空間把問(wèn)題分為若干個(gè)相互聯(lián)系的階段。在每一階段都要作出選擇（決策），這個(gè)決策不僅僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)，從而決定整個(gè)過(guò)程的走向（從而稱為動(dòng)態(tài)規(guī)劃）。每當(dāng)一階段的決策一一確定之后，就得到一個(gè)決策序列，稱為策略。所謂多階段決策問(wèn)題就是求一個(gè)策略，使各個(gè)階段的效益總和達(dá)到最優(yōu)。先聲明：下面研究的解

2、決多階段的決策問(wèn)題的最優(yōu)化的稱之為動(dòng)態(tài)規(guī)劃的數(shù)學(xué)方法，僅僅是一種解決問(wèn)題的思路，而不是一種算法。這一點(diǎn)與線性規(guī)劃不同。線性規(guī)劃是一種算法。下面從一典型的例子去說(shuō)明動(dòng)態(tài)規(guī)劃的基本思想與原理：某地要從A向F地鋪設(shè)一條輸油管道，各點(diǎn)間連線上的數(shù)字表示距離。問(wèn)應(yīng)選擇什么路線，可是總距離最短？5C128D1 433B154E1C26456E2C4C3FA 3D2 3285 147 3B2D3 87 4 第一階段 第二階段 第三階段 第四階段 第五階段 圖7-1先引入幾個(gè)符號(hào)與概念：（1） 階段與階段變量：先把問(wèn)題從中間站B，C，D，E用空間位置分成5個(gè)階段，階段用階段變量k來(lái)描述，k=1,表示第一階段，

3、k=2表示第二階段，（2） 狀態(tài)與狀態(tài)變量：每一階段的左端點(diǎn)（初始條件）集合稱為本階段的狀態(tài)（即開(kāi)始的客觀條件，或稱階段初態(tài)）。如第三階段有四個(gè)狀態(tài)S3 =C1 ,C2，C3，C4, 第四階段有三個(gè)狀態(tài) S4=D1, D2 , D3, 描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量：用小寫s1 ,s2 ,s3 表示第一，第二，第三階段的狀態(tài)變量。當(dāng)處在狀態(tài)C2時(shí)，我們可記 s3= C2正像離散型R.V“X=2”代表一事件一樣。(3) 決策與決策變量：如當(dāng)處于C2狀態(tài)時(shí)，下一步怎么走？如何選擇路線？即如何決策。是走向D1，還是走向D2？當(dāng)過(guò)程處于某一階段的某一狀態(tài)時(shí)，可以作出不同的決策（或選擇），從而確定下一階

4、段的狀態(tài)，這種決定（或選擇）叫決策。如選擇D2，記u3（C2）= D2說(shuō)，當(dāng)處于C2狀態(tài)時(shí)，下一步的決策為D2。其中表示第k階段當(dāng)狀態(tài)處于時(shí)的決策變量。一般地，用表示第k階段從狀態(tài)出發(fā)的允許決策集合。如=D1 ，D2顯然，。 （4）策略與最優(yōu)策略：每一階段產(chǎn)生一個(gè)決策，5個(gè)階段的決策就構(gòu)成一個(gè)決策序列： ，稱為一策略。所謂策略是指按一定的順序排列的決策組成的集合，也稱決策序列。這里的最短路徑成為最優(yōu)策略。動(dòng)態(tài)規(guī)劃就是在允許策略集中選最優(yōu)策略。（5）狀態(tài)轉(zhuǎn)移方程：是描述由第k階段到第k+1階段狀態(tài)轉(zhuǎn)移規(guī)律的關(guān)系式。 =上例中狀態(tài)轉(zhuǎn)移方程為： = （6）指標(biāo)函數(shù)與最優(yōu)指標(biāo)函數(shù)：用于衡量所選定策略優(yōu)

5、劣的數(shù)量指標(biāo)稱為指標(biāo)函數(shù)。相當(dāng)于動(dòng)態(tài)的目標(biāo)函數(shù)，最后一個(gè)階段的目標(biāo)函數(shù)就是總的目標(biāo)函數(shù)。它分階段指標(biāo)函數(shù)和過(guò)程指標(biāo)函數(shù)。階段指標(biāo)函數(shù)是指第k階段，從狀態(tài)出發(fā)，采用決策時(shí)的效益，用表示。最優(yōu)指標(biāo)函數(shù)是指從第k階段狀態(tài)采用最優(yōu)策略到過(guò)程終止時(shí)的最佳效益值，用表示。例如：d（C2, D1）是指由C2出發(fā)，下一階段的決策是D1的兩點(diǎn)間的距離。即d（C2, D1）=4。表示從B1到F的最短距離。整個(gè)問(wèn)題即為=？1 逆序遞推法：倒退著從F向A走，每倒退一步，思想上問(wèn)自己：“從現(xiàn)在出發(fā)，退向何處？到F的距離最短？”我們分5步來(lái)解決問(wèn)題：（1） k=5時(shí)下求=？此時(shí)狀態(tài)集S5=E1，E2，故分情況討論，先說(shuō)=

6、？若最佳路徑從A出發(fā)通過(guò)E1的話，由 E1到終點(diǎn)F的最短距離為=5同理，=3。 （只有唯一的選擇）故最優(yōu)決策為：=F，=F（2） k=2時(shí) 下求 =？由于S4=D1, D2 , D3，下分四種情況進(jìn)行討論：=min = min =7, = E1.=min = min =5, = E2.=min = min =5, = E1.(3) k=3時(shí) S3 =C1 ,C2，C3，C4,=min = min =12, = D1.同理，=10， = D2. =8， = D2. =9， = D3.（4）k=4時(shí) S2=B1, B2=min = min =13, = C2.同理，=15， = C3.（5）k=1

7、時(shí)， S1=A=min = min =17, = B1.再按計(jì)算順序的反推可得最優(yōu)策略：= B1. = C2. = D2. = E2. = F.從而得最優(yōu)路徑：AB1 C2 D2E2 F最短距離為 =17。由上面的過(guò)程可以看出，在求解的各個(gè)階段利用了第k段和第k+1段的如下關(guān)系：這種遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的基本方程。（7.3b）式稱為邊界條件。2 逆向標(biāo)號(hào)法每退到一站，看終點(diǎn)F，找最短路徑及最短路徑的距離，標(biāo)號(hào)。畫路徑。（12）（7）C125（13）（10）8D1 3（4）B14C24E153（17）（5）（8）5646E2C4C3FA 23D2 （15）1（3）385 （5）47 （9）3B2

8、D3 87 4 圖 7-2此時(shí)的（？）？=最優(yōu)指標(biāo)函數(shù)值f.得最優(yōu)路徑： AB1 C2 D2E2 F總距離為 17.3 順序遞推法：此法類似于逆序遞推法。從起點(diǎn)A向終點(diǎn)F倒退。（1） k=1時(shí)，=0，此為初始條件。退向允許決策集S1=B1, B2 此時(shí)退向B1時(shí)看起點(diǎn)A，最短距離為=4，此時(shí)路徑（或最優(yōu)決策）是唯一的：=A；記，同理，（2） k=2時(shí)，直接用遞推式：（3） k=3時(shí)。類似的， 同理， ， 最后 逆推最優(yōu)策略：AB1 C2 D2E2 F。 與前相同。全部計(jì)算情況如圖7-3（11）C152（6）（4）（7）8D1 3（14）B1C2E14435（12）（10）（17）5646E2C

9、4C3FA 23D2 （14）（5）1385 （14）47 （12）3B2D3 87 4 圖 7-3遞推關(guān)系式： 此與逆序法無(wú)本質(zhì)的區(qū)別。一般來(lái)說(shuō)，當(dāng)初始狀態(tài)給定時(shí)，用逆序解法，當(dāng)終止?fàn)顟B(tài)給定時(shí)，用順序解法。若既給定了初始狀態(tài)又給定了終止?fàn)顟B(tài)，則兩種方法均可使用。如習(xí)題7.2/P237，終點(diǎn)有三個(gè)，用逆序解法較好。7.2/P237 一艘貨輪在A港裝貨后駛往F港，中途須靠港加油、淡水三次，從A港到F港全部可能的航行路線及兩港之間距離如圖7-7，F(xiàn)港有三個(gè)碼頭 ，實(shí)秋最合理的?？康拇a頭及航線，使總路程最短。3040203050253040605030406030204550C1F2F2F1D2D1

10、C3C2B1B2A F 圖7-7解：順序解法此法類似于逆序遞推法。從起點(diǎn)A向終點(diǎn)F倒退。（1） k=1時(shí)，=0，此為初始條件。退向允許決策集S1=B1, B2 ，此時(shí)退向B1時(shí)看起點(diǎn)A，最短距離為=50，此時(shí)路徑（或最優(yōu)決策）是唯一的：=A；記，同理，（2） k=2時(shí)，直接用遞推式：（3） k=3時(shí)。類似的。（4） k=4時(shí)由此看來(lái)，A到F距離最短的是120，故最優(yōu)路線為A B2 C3 D1F2 §7.2 資源分配問(wèn)題（離散型）例：設(shè)有6萬(wàn)元資金用于4個(gè)工廠的擴(kuò)建，已知每個(gè)工廠的利潤(rùn)增長(zhǎng)額同投資額的大小有關(guān)，見(jiàn)下表。問(wèn)應(yīng)如何確定對(duì)這四個(gè)工廠的投資額，使總利潤(rùn)增長(zhǎng)額最大？ 表內(nèi)數(shù)據(jù)是利

11、潤(rùn)額 投資額(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解：把對(duì)四個(gè)工廠的投資依次看成4個(gè)階段的決策過(guò)程，確定對(duì)第k個(gè)工廠的投資額看成第k個(gè)階段的決策，k=1,2,3,4。圖示如下：S5狀態(tài)s4狀態(tài)s3狀態(tài)s2s1=600投資x1(萬(wàn)元)投資x2(萬(wàn)元)投資x4(萬(wàn)元)投資x3(萬(wàn)元)S4= s3-x3S3= s2-x2s2= s1-x1工廠2工廠1工廠3工廠4狀態(tài)變量：可用于第k, k+1,n個(gè)工廠的投資

12、額。決策變量：第k階段對(duì)第k個(gè)工廠的投資額。允許決策集：=0，100，狀態(tài)轉(zhuǎn)移方程：=- k=1,2,3,4 其中=600。階段指標(biāo)函數(shù)：第i階段投資元時(shí)所產(chǎn)生的利潤(rùn)。（見(jiàn)上表）最優(yōu)指標(biāo)函數(shù)：第k階段狀態(tài)為且對(duì)第k個(gè)工廠投資為時(shí)，第k個(gè)工廠以及以后的總利潤(rùn)。 基本遞推方程： 初始條件已知：=600，逆序法求解。（1） k=4時(shí)，考慮：若到最后一個(gè)，第4個(gè)工廠投資時(shí)，還有資金，若投資于第4個(gè)工廠的資金為，則最大利潤(rùn)為 （注意到此時(shí)=0） = （1）自然問(wèn)：現(xiàn)在還有多少錢？即=？=0，100，200，300，400，500，600都有可能。下分情況討論： =0時(shí)，只能=0。從表上看（4，1）位置是

13、第4個(gè)工廠=0時(shí)的利潤(rùn)其值為=0，由=0的唯一性知=0。=100，此時(shí)=0或100。產(chǎn)生的利潤(rùn)=0或28。 =0，28=28，對(duì)應(yīng)的=100，即此種情況的最優(yōu)決策=100。其他種情況類似討論，我們把所有的結(jié)果匯總成一個(gè)表1。（2）k=3時(shí) 到第三個(gè)工廠投資時(shí)，可利用的資金還有，若向第三個(gè)工廠投資（萬(wàn)元），則自此即以后最大利潤(rùn)為： = 表10 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 850284765

14、7480850100200300400500600同樣問(wèn)：=？，即現(xiàn)在還有多少錢？分情況討論匯總成下表： +0 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我們舉一個(gè)例子來(lái)說(shuō)明。若=3

15、00，得所有可能取值為0，100，200，300，此為第三階段允許決策集。在=0，100，200，300中選取最優(yōu)的，使最大，即=max,=max0+65,18+47,39+28,61+0=67, 此67對(duì)應(yīng)的是=200時(shí)所得，即=200；（3）k=2時(shí) 此時(shí)，的所有可能取值0，100，200，300，400，500，600，每個(gè)定一個(gè)值，在的范圍內(nèi)變動(dòng)，由，求出=？=？=？下面舉一個(gè)例子來(lái)說(shuō)明。=max,=0+126，25+108，45+89，57+67，65+47，70+28，73+0=max126，133，134，124，112，98，73=134。對(duì)應(yīng)最大值的=200，所以=200。關(guān)

16、于的其他取值情況及相應(yīng)的最有決策列于下表+0 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（5） k=1時(shí)，此時(shí)=600。=max,=max0+134,20+114,

17、42+92,60+73,75+53,85+28，90+0=max134,134,134,133,128,113,90=134. 0 100 200 300 400 500 600 6000+134 20+114 42+92 60+73 75+53 85+28 90+01340或100或200此時(shí)對(duì)應(yīng)最大值134的有三個(gè)值：=0，100，200。所對(duì)應(yīng)的最優(yōu)策略分別為：=0，由= -=600-0=600 對(duì)應(yīng)的 =200， 再由=-=600-200=400對(duì)應(yīng)的=300 再由=-=400-300=100對(duì)應(yīng)的=100從而得一最優(yōu)策略=0，=200，=300，=100同理還有另外三個(gè)最優(yōu)策略=20

18、0，=100，=200，=100=100，=100，=300，=100=200，=200，=0，=200總的最大利潤(rùn)=134（萬(wàn)元）第三講：資源分配問(wèn)題（連續(xù)型）設(shè)備負(fù)荷分配問(wèn)題。例（何堅(jiān)勇/P-256）某公司有1000輛運(yùn)輸卡車，在超負(fù)荷運(yùn)輸（即每天滿載行駛500km以上）情況下，年利潤(rùn)為25萬(wàn)元/輛，這時(shí)卡車的年損壞率為0.3；在低負(fù)荷下運(yùn)輸（即每天行駛300km以下）情況下，年利潤(rùn)為16萬(wàn)元/輛。年損壞率為0.1?，F(xiàn)要制定一個(gè)5年計(jì)劃，問(wèn)每年年初應(yīng)如何分配完好車輛，在兩種不同的負(fù)荷下運(yùn)輸?shù)目ㄜ嚁?shù)量，使在5年內(nèi)的總利潤(rùn)最大？解：這是一個(gè)以時(shí)間為特征的多階段決策問(wèn)題。投x3輛超負(fù)車投x2輛超

19、負(fù)荷車投x1輛超負(fù)荷車狀態(tài)s3狀態(tài)s2第1年第2年第3年s1=1000s2=0.9 s1-0.2x1S3= s2-x2投x5輛超負(fù)車投x4輛超負(fù)車狀態(tài)s4S5s4=0.9 s3-0.2x3s5=0.9s4-0.2x4第五年第四年階段：將5年運(yùn)輸計(jì)劃看成5個(gè)階段的決策問(wèn)題。k=1,2,3,4,5狀態(tài)變量：第k階段初完好卡車數(shù)量。=1000，=500。決策變量：表示第k階段用于分配給超負(fù)荷運(yùn)輸?shù)目ㄜ嚁?shù)量。 顯然，分配給低負(fù)荷的卡車數(shù)為-。注：這里視，為連續(xù)變量。若=0.6表示還有一輛卡車在第k年度有60的時(shí)間處于完好狀態(tài)。=0.7表示有一輛卡車在第k年度有70的時(shí)間超負(fù)荷運(yùn)輸?shù)鹊取顟B(tài)轉(zhuǎn)移方程：

20、=（1-0.3）+（1-0.1）（-）=0.9-0.2 k=1,2,3,4,5 階段指標(biāo)函數(shù)：表示第k年度利潤(rùn)。 =25+16（-） =16+9 k=1,2,3,4,5 最優(yōu)指標(biāo)函數(shù)：第k年度初完好車輛數(shù)為時(shí)，采用最優(yōu)策略到第5年末所產(chǎn)生的最大利潤(rùn)。 遞推式為： 下用逆序遞推法求解：1） k=5時(shí) （注意到此時(shí)=0）16 = O =16+9=25 =2) k=4時(shí) = = = =38.5+4=42.4。此時(shí)，=3） k=3時(shí) = = = =54.25+0.5 =54.75 此時(shí)，=4） k=2時(shí) = = =65.275 此時(shí)=05） k=1時(shí) = = = =74.7475 =74.7475&#

21、215;1000 =74747.5（萬(wàn)元） 此時(shí)=0下用倒推法求出最優(yōu)策略。=0， =0.9-0.2=0.9×1000-0.2×0=900輛=0 =0.9-0.2=0.9×900-0.2×0=810輛=810 =0.9-0.2=0.9×810-0.2×810=567輛=567 =0.9-0.2=0.7×567=396.9輛=396.9 =0.9 -0.2=0.7×396.9=277.83輛答：第一年初：1000輛車全部用于低負(fù)荷運(yùn)輸。第二年初：還有900輛完好的車，也全部用于低負(fù)荷運(yùn)輸。第三年初：還有810輛完好的

22、車，全部用于超負(fù)荷運(yùn)輸。第四年初：還有567輛完好的車，全部用于超負(fù)荷運(yùn)輸。第五年初：還有396.9輛完好的車，全部用于超負(fù)荷運(yùn)輸。到第五年末，即第六年初，還剩余277.83輛完好的車。所創(chuàng)最大利潤(rùn)=74747.5萬(wàn)元某種機(jī)器可在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。設(shè)機(jī)器在高負(fù)荷下生產(chǎn)的產(chǎn)量為h=8u，其中u為投入生產(chǎn)的機(jī)器數(shù)量，年終機(jī)器的完好率為a=0.7；在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為=5v,其中v為投入生產(chǎn)的機(jī)器數(shù)量，年終機(jī)器的完好率為b=0.9。假定開(kāi)始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為=1000臺(tái)，試問(wèn)企業(yè)每年年初應(yīng)如何安排機(jī)器在高、低兩種負(fù)荷下的生產(chǎn)，使在第5年年末完好的機(jī)器數(shù)量=500臺(tái)，并且5年內(nèi)生

23、產(chǎn)的產(chǎn)品總產(chǎn)量最高。第1年第2年第3年第四年投x1輛超負(fù)荷車投x2輛超負(fù)荷車投x3輛超負(fù)車投x4輛超負(fù)車s1=1000狀態(tài)s2s2=0.9 s1-0.2x1S3= s2-x2狀態(tài)s4狀態(tài)s3S5第五年投x5輛超負(fù)車s5=0.9s4-0.2x4=500s4=0.9 s3-0.2x3解：階段指標(biāo)函數(shù)：第k年的產(chǎn)量 =8+5（-）=5+3 k=1,2,3,4,5 下用逆序遞推法求解：1） k=5時(shí)=0.9-0.2=500可得 =4.5-2500=3（4.5-2500）+5=18.5-75002） k=4時(shí) = = = =21.65-7500 此時(shí)=03） k=3時(shí) = = =24.48-7500 此

24、時(shí)=04） k=2時(shí) = = =27.0365-7500 此時(shí)=05） k=1時(shí) = = =29.33285-7500 =29.33285×1000-7500 =21832.85 此時(shí)=0最優(yōu)策略為：=0， =0.9-0.2 =0.9×100=900輛=0， =0.9-0.2=0.9×900-0.2×0=810輛=0， =0.9-0.2=0.9×810-0.2×0=729輛=0， =0.9-0.2=0.9×729=656.1輛=4.5-2500=4.5×0.94-2500=452.45 =0.9 -0.2=0.9&

25、#215;656.1-0.2×452.45=500輛其中=0.9=0.9×0.9=0.9×0.9×0.9×0.9=656.1答：第一年初：1000輛車全部用于低負(fù)荷運(yùn)輸。第二年初：還有900輛完好的車，也全部用于低負(fù)荷運(yùn)輸。第三年初：還有810輛完好的車，全部用于低負(fù)荷運(yùn)輸。第四年初：還有729輛完好的車，全部用于低負(fù)荷運(yùn)輸。第五年初：還有656.1輛完好的車，其中452臺(tái)用于高負(fù)荷運(yùn)輸，204臺(tái)在低負(fù)荷下運(yùn)輸。到第五年末，即第六年初，還剩余500輛完好的車。所創(chuàng)最大利潤(rùn)=21833萬(wàn)元第四講 資源分配問(wèn)題（一維連續(xù)）例5 某公司有資金10萬(wàn)元

26、，若投資于項(xiàng)目i (i=1,2,3)的投資額為時(shí)，其收益分別為。其中=4，=9，=2，問(wèn)應(yīng)如何分配資金額才能使總收益最大？解： = s.t (一) 逆序解=-=4=2=9=-項(xiàng)目1=10-項(xiàng)目1=10項(xiàng)目1 狀態(tài)轉(zhuǎn)移方程： k=1,2,3基本方程：對(duì)這種初始狀態(tài)=10（萬(wàn)元）已知的資金分配問(wèn)題，我們采用逆序法。K=3時(shí) =2； 此時(shí)，=K=2時(shí)O = =問(wèn) = 0，當(dāng)=？時(shí)，最大。且最大值=？ （0，）時(shí)。 =9+4（-）（-1）=0， =-9/4且 =4>0。 故在=-9/4處取得極小值。=2=9 依題意在0，上有極大值，故極大值只能在端點(diǎn)處取得，為此考察：=9 =2； =9現(xiàn)在問(wèn)：誰(shuí)

27、大誰(shuí)?。窟@是以為自變量的兩個(gè)函數(shù)的大小比較問(wèn)題。O 9/2 從右圖上可看出=最后看k=1時(shí)現(xiàn)在的問(wèn)題是=？2200=90O 9/2 10 = = = =200 此時(shí)，=0。逆追最優(yōu)解： =0， =10-=109/2 =0 =-=10 =10且最大利潤(rùn) =200（萬(wàn)元）=10（二） 順序解：=-=-=-=2=9=4項(xiàng)目2項(xiàng)目3項(xiàng)目1 狀態(tài)轉(zhuǎn)移方程： =- k=1,2,3最優(yōu)指標(biāo)函數(shù)：第k階段，當(dāng)投資額為時(shí)，從第1到第k階段所獲得的最大收益。 總的收益=？基本方程：k=1時(shí):=4 此時(shí)，=k=2時(shí)：=9，此時(shí)，=k=3時(shí)：=令= 0，10下求它的極大值： = 49 令其為0，得 =9/4 且= 4

28、0故此函數(shù)在（0，10）內(nèi)只有一個(gè)極小值點(diǎn)。極大值點(diǎn)只能在端點(diǎn)處取的。 考慮：=0時(shí)， =9=90=10時(shí)， =2=200 所以有 =10此時(shí)，200。再用狀態(tài)轉(zhuǎn)移方程逆推得最優(yōu)解：=10，=-=10-10=0，=0，=-=0-0=0，=0。此解與逆序相同。（三）連續(xù)變量的離散化解法：例6 用連續(xù)變量的離散化求解： Max z =4+9+2s.t 解：因?yàn)檫@里的010，k=1，2，3.可在區(qū)間0，10內(nèi)選有限個(gè)點(diǎn)，比如分割成0，2，4，6，8，10。將來(lái)決策變量、狀態(tài)變量均取值集合0，2，4，6，8，10中的點(diǎn)。盡管這樣做可能出現(xiàn)丟失最優(yōu)解，但作為近似解求解簡(jiǎn)單。此時(shí)的動(dòng)態(tài)規(guī)劃基本方程： 當(dāng)k

29、=3時(shí)， =式中的，均取值于0，2，4，6，8，10，計(jì)算結(jié)果見(jiàn)下表02468100832721282000246810當(dāng)k=2時(shí)，=，計(jì)算結(jié)果見(jiàn)下表+0 2 4 6 8 10 0 2 4 6 8 100+00+8 18+00+32 18+8 36+0 0+72 18+32 36+8 54+0 0+128 18+72 36+32 54+8 72+0 0+200 18+128 36+72 54+32 72+8 90+00183672128200024000k=1時(shí)，計(jì)算結(jié)果見(jiàn)下表0 2 4 6 8 10 100+200 8+128 16+72 24+36 32+18 40+0 2000計(jì)算結(jié)果表

30、明，最有決策為： =0，=0，=10。最大收益為=200。與上例完全相同。 第五講：背包問(wèn)題一般的提法為：以旅行者攜帶背包去登山。已知他所能承受的背包重量的極限為a (千克)，現(xiàn)有n種物品可供他選擇裝入背包。第i種物品的單位重量為(千克)其價(jià)值（可以是表明本物品對(duì)登山者的重要性指標(biāo)）是攜帶數(shù)量的函數(shù)（i=1，2，n）.問(wèn)旅行者應(yīng)如何選擇攜帶物品的件數(shù)，以使總價(jià)值最大？其數(shù)學(xué)模型為： max z = s. t (i=1,2,n.且為整數(shù))此模型解決的是運(yùn)輸工具包括衛(wèi)星的最優(yōu)裝載問(wèn)題。下面從一個(gè)例子來(lái)分析動(dòng)態(tài)規(guī)劃建模。例7 有一輛最大貨運(yùn)量為10t的卡車，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)

31、單位價(jià)值如表7-4所示。應(yīng)如何裝載可使總價(jià)值最大？貨物編號(hào)i 1 2 3單位重量（t） 3 4 5單位價(jià)值ci 4 5 6設(shè)第i種貨物的件數(shù)為（i=1,2,3），則問(wèn)題可表述為： max z = 456 (i=1,2,n.且為整數(shù))下用動(dòng)態(tài)規(guī)劃順序解法建模求解：階段k: 將可裝入物品按1，2，3的順序排序，每段裝入一種物品，共劃分3個(gè)階段，即k=1,2,3.狀態(tài)變量：在第k段開(kāi)始時(shí)，背包中允許裝入前k種物品的總重量。決策變量：裝入第k種物品的件數(shù)。狀態(tài)轉(zhuǎn)移方程： 最優(yōu)指標(biāo)函數(shù)：在背包中允許裝入物品的總重量不超過(guò)kg，采取最優(yōu)策略只裝前k種物品時(shí)的最大使用價(jià)值。由此可得動(dòng)態(tài)規(guī)劃的順序遞推方程為：

32、534 =-3=-4=-5=10 貨物3貨物1貨物1=5=6=4由于取整數(shù)，故，0，1，2，10，下用順序法求解。K=1時(shí) =計(jì)算結(jié)果見(jiàn)下表：0 1 2 3 3 4 7 8 9 4×04×0 4×0 4×0 4×1 4×0 4×1 4×24×0 4×1 4×2 4×3000481202400123K=2時(shí) =具體的計(jì)算結(jié)果見(jiàn)下表0 1 2 1 2 3 4 6 7 8 9 5×00 5×04 5×10 5×012 5×18 5&

33、#215;20 0513011k=3時(shí)：= = max 0, 6, 12 = max013,65,120=13 此時(shí)，=0下逆推得最優(yōu)解： =0，=-5=10-0=10 =1 =-4=10-4=6 =2最大裝載價(jià)值為 =13。故今后解背包問(wèn)題應(yīng)先從k=3入手：k=3時(shí)：= = max 0, 6, 12下有重點(diǎn)地從k=2中求解三個(gè)最優(yōu)函數(shù)值：，。K=2時(shí) = = = max0, 5, 10= = = max0, 5=下從第一階段有重點(diǎn)地求四個(gè)函數(shù)：，K=1時(shí) =0， 此時(shí) =0=0 此時(shí) =0= = = max0，4= 4, 此時(shí) =1= = = maxo,4,8,12=12, 此時(shí) =3由此逆推回去：=0， 此時(shí) =0，=0 = max0, 5= max04, 50=5，此時(shí) =0，=1= max0, 5, 10 = max012, 58, 100=13, 此時(shí) =1, =2最后： = max 0, 6, 12 = max013, 65, 120=13, 對(duì)應(yīng)最大值13，=0，且，故對(duì)應(yīng)=2, =1最大運(yùn)輸價(jià)值=13。7.9/P-239 用動(dòng)態(tài)規(guī)