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

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

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

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

4、段的狀態(tài)，這種決定（或選擇）叫決策。如選擇D2，記u3（C2）= D2說，當(dāng)處于C2狀態(tài)時，下一步的決策為D2。其中表示第k階段當(dāng)狀態(tài)處于時的決策變量。一般地，用表示第k階段從狀態(tài)出發(fā)的允許決策集合。如=D1 ，D2顯然，。 （4）策略與最優(yōu)策略：每一階段產(chǎn)生一個決策，5個階段的決策就構(gòu)成一個決策序列： ，稱為一策略。所謂策略是指按一定的順序排列的決策組成的集合，也稱決策序列。這里的最短路徑成為最優(yōu)策略。動態(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)于動態(tài)的目標(biāo)函數(shù)，最后一個階段的目標(biāo)函數(shù)就是總的目標(biāo)函數(shù)。它分階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)。階段指標(biāo)函數(shù)是指第k階段，從狀態(tài)出發(fā)，采用決策時的效益，用表示。最優(yōu)指標(biāo)函數(shù)是指從第k階段狀態(tài)采用最優(yōu)策略到過程終止時的最佳效益值，用表示。例如：d（C2, D1）是指由C2出發(fā)，下一階段的決策是D1的兩點間的距離。即d（C2, D1）=4。表示從B1到F的最短距離。整個問題即為=？1 逆序遞推法：倒退著從F向A走，每倒退一步，思想上問自己：“從現(xiàn)在出發(fā)，退向何處？到F的距離最短？”我們分5步來解決問題：（1） k=5時下求=？此時狀態(tài)集S5=E1，E2，故分情況討論，先說=

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

7、時， S1=A=min = min =17, = B1.再按計算順序的反推可得最優(yōu)策略：= B1. = C2. = D2. = E2. = F.從而得最優(yōu)路徑：AB1 C2 D2E2 F最短距離為 =17。由上面的過程可以看出，在求解的各個階段利用了第k段和第k+1段的如下關(guān)系：這種遞推關(guān)系稱為動態(tài)規(guī)劃的基本方程。（7.3b）式稱為邊界條件。2 逆向標(biāo)號法每退到一站，看終點F，找最短路徑及最短路徑的距離，標(biā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此時的（？）？=最優(yōu)指標(biāo)函數(shù)值f.得最優(yōu)路徑： AB1 C2 D2E2 F總距離為 17.3 順序遞推法：此法類似于逆序遞推法。從起點A向終點F倒退。（1） k=1時，=0，此為初始條件。退向允許決策集S1=B1, B2 此時退向B1時看起點A，最短距離為=4，此時路徑（或最優(yōu)決策）是唯一的：=A；記，同理，（2） k=2時，直接用遞推式：（3） k=3時。類似的， 同理， ， 最后 逆推最優(yōu)策略：AB1 C2 D2E2 F。 與前相同。全部計算情況如圖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)系式： 此與逆序法無本質(zhì)的區(qū)別。一般來說，當(dāng)初始狀態(tài)給定時，用逆序解法，當(dāng)終止?fàn)顟B(tài)給定時，用順序解法。若既給定了初始狀態(tài)又給定了終止?fàn)顟B(tài)，則兩種方法均可使用。如習(xí)題7.2/P237，終點有三個，用逆序解法較好。7.2/P237 一艘貨輪在A港裝貨后駛往F港，中途須靠港加油、淡水三次，從A港到F港全部可能的航行路線及兩港之間距離如圖7-7，F(xiàn)港有三個碼頭 ，實秋最合理的?？康拇a頭及航線，使總路程最短。3040203050253040605030406030204550C1F2F2F1D2D1

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

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

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

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

15、00，得所有可能取值為0，100，200，300，此為第三階段允許決策集。在=0，100，200，300中選取最優(yōu)的，使最大，即=max,=max0+65,18+47,39+28,61+0=67, 此67對應(yīng)的是=200時所得，即=200；（3）k=2時 此時，的所有可能取值0，100，200，300，400，500，600，每個定一個值，在的范圍內(nèi)變動，由，求出=？=？=？下面舉一個例子來說明。=max,=0+126，25+108，45+89，57+67，65+47，70+28，73+0=max126，133，134，124，112，98，73=134。對應(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時，此時=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此時對應(yīng)最大值134的有三個值：=0，100，200。所對應(yīng)的最優(yōu)策略分別為：=0，由= -=600-0=600 對應(yīng)的 =200， 再由=-=600-200=400對應(yīng)的=300 再由=-=400-300=100對應(yīng)的=100從而得一最優(yōu)策略=0，=200，=300，=100同理還有另外三個最優(yōu)策略=20

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

19、負荷車投x1輛超負荷車狀態(tài)s3狀態(tài)s2第1年第2年第3年s1=1000s2=0.9 s1-0.2x1S3= s2-x2投x5輛超負車投x4輛超負車狀態(tài)s4S5s4=0.9 s3-0.2x3s5=0.9s4-0.2x4第五年第四年階段：將5年運輸計劃看成5個階段的決策問題。k=1,2,3,4,5狀態(tài)變量：第k階段初完好卡車數(shù)量。=1000，=500。決策變量：表示第k階段用于分配給超負荷運輸?shù)目ㄜ嚁?shù)量。 顯然，分配給低負荷的卡車數(shù)為-。注：這里視，為連續(xù)變量。若=0.6表示還有一輛卡車在第k年度有60的時間處于完好狀態(tài)。=0.7表示有一輛卡車在第k年度有70的時間超負荷運輸?shù)鹊?。狀態(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年度利潤。 =25+16（-） =16+9 k=1,2,3,4,5 最優(yōu)指標(biāo)函數(shù)：第k年度初完好車輛數(shù)為時，采用最優(yōu)策略到第5年末所產(chǎn)生的最大利潤。 遞推式為： 下用逆序遞推法求解：1） k=5時 （注意到此時=0）16 = O =16+9=25 =2) k=4時 = = = =38.5+4=42.4。此時，=3） k=3時 = = = =54.25+0.5 =54.75 此時，=4） k=2時 = = =65.275 此時=05） k=1時 = = = =74.7475 =74.7475&#

21、215;1000 =74747.5（萬元） 此時=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輛車全部用于低負荷運輸。第二年初：還有900輛完好的車，也全部用于低負荷運輸。第三年初：還有810輛完好的

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

23、產(chǎn)的產(chǎn)品總產(chǎn)量最高。第1年第2年第3年第四年投x1輛超負荷車投x2輛超負荷車投x3輛超負車投x4輛超負車s1=1000狀態(tài)s2s2=0.9 s1-0.2x1S3= s2-x2狀態(tài)s4狀態(tài)s3S5第五年投x5輛超負車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時=0.9-0.2=500可得 =4.5-2500=3（4.5-2500）+5=18.5-75002） k=4時 = = = =21.65-7500 此時=03） k=3時 = = =24.48-7500 此

24、時=04） k=2時 = = =27.0365-7500 此時=05） k=1時 = = =29.33285-7500 =29.33285×1000-7500 =21832.85 此時=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輛車全部用于低負荷運輸。第二年初：還有900輛完好的車，也全部用于低負荷運輸。第三年初：還有810輛完好的車，全部用于低負荷運輸。第四年初：還有729輛完好的車，全部用于低負荷運輸。第五年初：還有656.1輛完好的車，其中452臺用于高負荷運輸，204臺在低負荷下運輸。到第五年末，即第六年初，還剩余500輛完好的車。所創(chuàng)最大利潤=21833萬元第四講 資源分配問題（一維連續(xù)）例5 某公司有資金10萬元

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

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

28、0故此函數(shù)在（0，10）內(nèi)只有一個極小值點。極大值點只能在端點處取的。 考慮：=0時， =9=90=10時， =2=200 所以有 =10此時，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 解：因為這里的010，k=1，2，3.可在區(qū)間0，10內(nèi)選有限個點，比如分割成0，2，4，6，8，10。將來決策變量、狀態(tài)變量均取值集合0，2，4，6，8，10中的點。盡管這樣做可能出現(xiàn)丟失最優(yōu)解，但作為近似解求解簡單。此時的動態(tài)規(guī)劃基本方程： 當(dāng)k

29、=3時， =式中的，均取值于0，2，4，6，8，10，計算結(jié)果見下表02468100832721282000246810當(dāng)k=2時，=，計算結(jié)果見下表+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時，計算結(jié)果見下表0 2 4 6 8 10 100+200 8+128 16+72 24+36 32+18 40+0 2000計算結(jié)果表

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

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

32、534 =-3=-4=-5=10 貨物3貨物1貨物1=5=6=4由于取整數(shù)，故，0，1，2，10，下用順序法求解。K=1時 =計算結(jié)果見下表：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時 =具體的計算結(jié)果見下表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時：= = max 0, 6, 12 = max013,65,120=13 此時，=0下逆推得最優(yōu)解： =0，=-5=10-0=10 =1 =-4=10-4=6 =2最大裝載價值為 =13。故今后解背包問題應(yīng)先從k=3入手：k=3時：= = max 0, 6, 12下有重點地從k=2中求解三個最優(yōu)函數(shù)值：，。K=2時 = = = max0, 5, 10= = = max0, 5=下從第一階段有重點地求四個函數(shù)：，K=1時 =0， 此時 =0=0 此時 =0= = = max0，4= 4, 此時 =1= = = maxo,4,8,12=12, 此時 =3由此逆推回去：=0， 此時 =0，=0 = max0, 5= max04, 50=5，此時 =0，=1= max0, 5, 10 = max012, 58, 100=13, 此時 =1, =2最后： = max 0, 6, 12 = max013, 65, 120=13, 對應(yīng)最大值13，=0，且，故對應(yīng)=2, =1最大運輸價值=13。7.9/P-239 用動態(tài)規(guī)