動態(tài)規(guī)劃習題課ppt課件

1、動態(tài)規(guī)劃習題課動態(tài)規(guī)劃習題課1;資源分配資源分配問題問題例1某公司擬將500萬元的資本投入所屬的甲、乙、丙三個工廠，各工廠獲得投資后年利潤將有相應的增長，一定投資下的利潤增長額如下表所示，試確定最優(yōu)的投資分配方案，使公司年利潤增長額最大。 投資投資(百萬元) 1 2 3 4 5 甲甲 0.3 0.7 0.9 1.2 1.3 乙乙 0.5 1.0 1.1 1.1 1.1 丙丙 0.4 0.6 1.1 1.2 1.2 2;例例1的求解的求解按工廠分為三個階段： 甲 乙 丙 k ： 1 2 3 設Sk為第k個工廠至第3個工廠可利用的投資額，xk為第k個工廠獲得的投資額，則Sk+1=Sk - xk。因

2、而有最優(yōu)指標函數：fk(Sk)=maxrk(xk)+fk+1(Sk-xk) f4(S4)=0 3;例例1的求解的求解k =3：f3(S3)=maxr3(x3)+f4(S4)=maxr3(x3)S3 0 1 2 3 4 5 *x3 0 1 2 3 4 4, 5f3(S3) 0 0.4 0.6 1.1 1.2 1.2 k =2：f2(S2)=maxr2(x2)+f3(S2 - x2) 4;例例1的求解的求解 x2 r2(x2)+f3(S2-x2) S2 0 1 2 3 4 5 f2(S2) *x2 0 0+0 0 0 1 0+.4 .5+0 0.5 1 2 0+.6 .5+.4 1+0 1.0 2

3、 3 0+1.1 .5+.6 1+.4 1.4 2 4 0+1.2 .5+1.1 1+.6 1.1+.4 1.1=0 1.6 1,2 5 0+1.2 .5+1.2 1+1.1 1.1+.6 1.1+.4 1.1+0 2.1 2 5;例例1的求解的求解k =1：f1(S1)=maxr1(x1)+f2(S1-x1) x1 r1(x1)+f2(S1-x1)S1 0 1 2 3 4 5 f1(S1) *x1 5 0+2.1 .3+1.6 .7+1.4 .9+1.0 1.2+0.5 1.3+0 2.1 0, 2 然后按計算表格的順序反推算，可得如下兩個最優(yōu)分配方案：1. x1=0 S2=S1-x1=5-

4、0=5 x2=2S3=3x3=3 2. x1=2， x2=2， x3=1 6;存貯控制問題存貯控制問題例例2 某鞋店銷售一種雪地防潮鞋，以往的銷售經歷表明，此種鞋的銷售季節(jié)是從10月1日至3月31日。下一個銷售季節(jié)各月的需求量預測值為：月 份 10 11 12 1 2 3需求(雙) 40 20 30 40 30 20 該鞋店直接從生產商進貨，基礎進貨價為每雙4美元。進貨批量有10、20、30、40和50雙五種規(guī)模，對應不同的進貨批量享受一定的價格折扣，具體數值如下：批 量 10 20 30 40 50 折扣(%) 4 5 10 20 25 7;例例2的求解的求解 假設需求是按一定速度均勻發(fā)生的

5、，訂貨不需要時間，但訂貨只能在月初辦理，每次訂貨的費用為10美元。月存貯費用是按每月底鞋的存量計算的，每雙0.2美元。由于訂貨不需要時間，所以銷售季節(jié)以外的月份無存貨。試確定最佳的進貨方案，以使總的銷售費用最小。階段階段：k = 1, 2, 3, 4, 5, 6狀態(tài)狀態(tài)： Sk 代表第k月初鞋的存量決策變量決策變量：dk 代表第k月鞋的采購量狀態(tài)轉移律狀態(tài)轉移律： Sk+1=Sk + dk - Dk ，S1 = S7 = 0費用函數費用函數： rk (Sk, dk )= (dk)+ 0.2(Sk + dk - Dk)，其中 (dk)為訂貨費用，訂貨費用由兩部分構成，一部分是固定的采購費10美元

6、，另一部分是貨款， dk= 0時 (dk)= 0。最優(yōu)指標函數最優(yōu)指標函數： fk (Sk )=min (dk) + 0.2(Sk + dk - Dk)+ fk+1 (Sk+1)8;例例2的求解的求解K=6(三月): S6 0 10 20 *d6 20 10 0f6 (S6 )= (*d6 ) 86 48 0K=5(二月): d5 0 10 20 30 40 50 * d5 f5 (S5 )S5 0 204 188 164 50 164 10 172 168 142 40 142 20 134 136 122 30 122 30 86 98 90 0 86 40 50 52 0 50 50 4

7、 0 49;例例2的求解的求解K=4(一月): d4 0 10 20 30 40 50 * d4 f4 (S4 )S4 0 302 304 40 302 10 282 282 286 30, 40 282 20 250 262 264 252 20 250 30 212 230 244 230 218 10 212 40 164 192 212 210 196 170 0 164 50 144 174 178 176 152 0 144 60 126 140 144 132 0 12610;例例2的求解的求解K=3(十二月): d3 0 10 20 30 40 50 * d3 f3 (S3 )

8、S3 0 420 422 414 50 414 10 388 402 392 384 50 384 20 350 370 372 362 332 50 332 30 302 332 340 342 310 314 0 302 40 284 302 310 290 292 298 0 284 11;例例2的求解的求解K=2(十一月): d2 0 10 20 30 40 50 * d2 f2 (S2 )S2 0 500 504 474 468 50 468 10 462 472 454 446 452 40 446 K=1(十月): d1 0 10 20 30 40 50 * d1 f1 (S1

9、)S1 0 606 608 40 606 12;例例2的求解的求解利用狀態(tài)轉移律，按上述計算的逆順序推算，可得如下最優(yōu)策略：十月份40雙 十一月份50雙 十二月份0雙 一月份40雙 二月份50雙 三月份0雙最小的銷售費用為606美元。13; 有一個徒步旅行者，其可攜帶物品重量的限度為有一個徒步旅行者，其可攜帶物品重量的限度為a 公公斤，設有斤，設有n 種物品可供他選擇裝入包中。已知每種物品種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？的物品（各幾件），使所起作用（使

10、用價值）最大？物品物品 1 2 j n重量（公斤重量（公斤/ /件）件） a1 a2 aj an每件使用價值每件使用價值 c1 c2 cj cn 這就是背包問題。類似的還有工廠里的下料問題、這就是背包問題。類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內的物品裝載問題運輸中的貨物裝載問題、人造衛(wèi)星內的物品裝載問題等。等。例3 背包問題14;設設xj 為第為第j 種物品的裝件數（非負整數）則問題的數學種物品的裝件數（非負整數）則問題的數學模型如下：模型如下： ). 2 . 1(0max1njxaxaxcZjnijjjnjjj 且且為為整整數數用動態(tài)規(guī)劃方法求解，令用動態(tài)規(guī)劃方法求解，

11、令 fx(y) = 總重量不超過總重量不超過 y 公斤，包中只裝有前公斤，包中只裝有前k 種物品種物品時的最大使用價值。時的最大使用價值。 其中其中y 0， k 1,2, , n 。所以問題就是求所以問題就是求 fn(a) 15;其遞推關系式為：其遞推關系式為： nkxayfxcyfkkkkkayxkkk 2)(max)(10 其其中中當當 k=1 時，有：時，有：的的最最大大整整數數表表示示不不超超過過其其中中1111111 , )(ayayayxaycyf16;例題：求下面背包問題的最優(yōu)解例題：求下面背包問題的最優(yōu)解 且且為為整整數數0,55231258max321321321xxxxxx

12、xxxZ物品物品 1 2 3重量（公斤）重量（公斤） 3 2 5使用價值使用價值 8 5 12解：解：a5 ，問題是求，問題是求 f3(5) )55(12max)5(323503333xfxfxax 整整數數17; )1()0(223231032355032350333333333)0(12),5(0max)55(12max)55(12max)55(12max)5(xxxxxxaxffxfxxfxxfxf ，整整數數整整數數18; 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),3(5),5(0max)25(max)25(max)25(

13、5max)5(xxxxxxxaxfffxfxxfxxfxf，整數整數整數整數19; )0()0(0max)20(max)20(max)20(5max)0(1)0(121202122002120022222222ffxfxxfxxfxfxxxxxax 5 5 整數整數整數整數20;)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(1112222 xxffffxxx )( 21; )0, 0(0)

14、0()0(0max)0(211)0(122 xxfffx )0,1,1(13012,130max)0(12),5(0max)5(321)1()0(22333 xxxfffxx所以，最優(yōu)解為所以，最優(yōu)解為 X（1 . 1 . 0），），最優(yōu)值為最優(yōu)值為 Z = 13。22; 練習練習1：某廠生產三種產品，各種產品重量與利：某廠生產三種產品，各種產品重量與利潤的關系如表所示。現將此三種產品運往市場出售，潤的關系如表所示。現將此三種產品運往市場出售，運輸能力總重量不超過運輸能力總重量不超過 6 噸，問如何安排運輸，使噸，問如何安排運輸，使總利潤最大？總利潤最大？種類種類 1 2 3重量（噸重量（噸/

15、 /公斤）公斤） 2 3 4 單件利潤（元）單件利潤（元） 80 130 180最優(yōu)方案：最優(yōu)方案：X1 = =（0.2.00.2.0）X2 = =（1.0.11.0.1）Z=260=26023; 例例4 投資問題投資問題 現有資金現有資金5百萬元百萬元,可對三個項目進行投資可對三個項目進行投資,投資額均投資額均為整數為整數(單位為百萬元單位為百萬元),其中其中2號項目的投資不得超過號項目的投資不得超過3百萬元百萬元,1號和號和3號項目的投資均不得超過號項目的投資均不得超過4百萬元，百萬元，3號號項目至少要投資項目至少要投資1百萬元。每個項目投資百萬元。每個項目投資5年后年后,預計可預計可獲得

16、的收益見下表獲得的收益見下表,問如何投資可望獲得最大的收益。問如何投資可望獲得最大的收益。 0 1 2 3 4 1 0 3 6 10 122 0 5 10 12 - 3 0 4 8 11 15投資額投資額u收益收益wk項目項目k24; 解解 sk對對1,(k-1)項目投資后剩余的金額項目投資后剩余的金額(狀狀態(tài)變量態(tài)變量)uk對對k項目的投資額項目的投資額wk(sk,uk)對對k項目投資項目投資uk后的收益后的收益wk(uk) fk(sk)應用剩余資金應用剩余資金sk對對k,(k+1),n項項 目投資可獲得的最大收益目投資可獲得的最大收益狀態(tài)轉移方程為狀態(tài)轉移方程為sk+1=sk-uk 為了獲

17、得最大收益，必須將為了獲得最大收益，必須將5百萬元資金全部用于百萬元資金全部用于投資，可得下面的遞歸方程投資，可得下面的遞歸方程25; f4(s4)=0 fk(sk)=maxwk(sk,uk)+fk+1(sk+1) k=3,2,1當當k=3時時 uk=skf3(1)=4 f3(2)=8 f3(3)=11 f3(4) =15當當k=2時時, 有有(注意：注意：項目項目3至少投資至少投資1百萬元百萬元, 2號項目的投資不得超過號項目的投資不得超過3百萬元百萬元)s2 1 2 3 4 5D2(sk) 0 0,1 0,1,2 0,1,2,3 0,1,2,3f2(1)=w2(1,0)+f3(1)=426;f2(2)=maxw2(2,1)+f3(1)w2(2,0)+f3(2)=max5+40+8=9f2(3)=maxw2(3,2)+f3(1)w2(3,1)+f3(2)w2(3,0)+f3(3)=max10+45+80+11=14f2(4)=maxw2(4,3)+f3(1)w2(4,2)+f3(2)w2(4,1)+f3(3)w2(4,0)+f3(4)=max12+410+85+11 0+15=1827