1、三、動態規劃的應用舉例(一)定價問題例27考慮為某新產品定價，該產品的單價從每件5元、6元、7元、8元這四個價 格中選取其中之一，每年年初允許變動價格，但幅度不能超過1元。該公司預計該產品 暢銷只有五年，五年后將被淘汰，另據銷售情況的預測，在價格不同的情況下個年的預 計利潤如表3-32。表3-32預計利潤額(單位：萬元)單價第一年第二年第三年第四年第五年5元10121520256元121316202471615151414解：1.畫出多階段決策圖，如圖3-10。圖中圓圈內的數字表示各年不同定價下的利潤。出一H15圖 3-102.確定參數根據題意，可劃分為五個階段，每階

2、段之末進行價格策略。k階段的狀態變量sk取為本年制定的價格，狀態的可能集合為：S廣(5,6,7,8)。據每年年初允許價格變動的幅度不能超過1元，故決策變量與上一階段的價格有關，當上階段的價格為，.時，則u (s ) = (s -1, s , s )，且(s ) E Sk kk k k+1k k k 狀態轉移方程sk+i = uk (sk)最優指標函數的遞推公式f (s ) = maxd (s ,u ) + f (s )k kk k kk+1 k+1uk式中，fk(七)從第k階段開始到最后階段為止的最大總收益，dk第k階段的收益值，在本例中dk僅與sk有關。3.進行各階段的計算設人(S6)=0,

3、人(7)=18,人(8)二14。這時，當 k =5 時，S5=5,6,7,8,所以人(5)二25,人(6)二24,當 k =4 時，S4=5,6,7,8,f (s ) = max d (s , u ) + f (s )4444455f (5) = ma叩55)頊5(5) = ma2。+ 孔=45 4d 4(56) + f (6)J20 + 24J所以u (5)=5；4d4(65) f (6) = max d (66) + f (6)所以u4(6)=5；d 4(76)+ 以6)f =max =max 、20+18,18 + 24、 =max 8 +14,=42=45所以u (7)=6；4f (8

4、) = maxjd4(87) + f5| = ma/4 + % 32 4 d 4(88) + f (8) J14 + 14j所以u4 (8)=7。當 k =3 時，S3=5,6,7,8，這時|15 + 45f (5) = max，= 603115+45|七=5或者6；|16 + 45 f (6) = max16 + 45316 + 42 = 61七=5或者6；|16 + 45 f (7) = max16 + 42316 + 32 = 61u3(7)=6；f(8)= max：5 ： 42 = 57，u3 (8)=7。315 + 32J3當 k =2 時，S2=5,6,7,8，這時，12 + 60

5、件)=m叫 12 + 61 73，七=6；|13 + 6。f (6) = max 13 + 61，= 74 ,n6)=6 或者 7；213+612|14 + 61|fJ7) = maxj14 + 61，= 75 ,u2(7)=6 或者 7；14 + 5715 + 61f2(8) = maX檢 + 57 = 76，七(8)=7。當 k =1 時，S1=5,6,7,8,這時10 + 73f1=m叫10 + 74，= 84，ui(5)=6；|12+73|f (6) = max12 + 74，= 87，u (6)二7；|12 + 75|14+74|f =max 14 + 75，= 90，u (7)二8

6、；1 1、14 + 7616 + 75f1(8) = max16 + 76，= 92，氣二8。所以，最優策略是，第一年定價8元，第二年定價8元，第三年定價7元，第四年 定價6元，第五年定價5元，總利潤是92萬元。本例也可以利用圖上標號法，圖3-10圓圈上方的數字就是在各階段各狀態下的最優 收益值。雙實線表示最優定價策略路線。（二）資源分配問題例28某公司準備將五臺加工中心分配給所屬的甲、乙、丙、丁四個工廠。各工廠 獲得該設備后，可以取得的利潤估算如表3-33所示。試問，應如何分配這些設備，使公 司的總利潤最大？表3-33預計利潤（單位：萬元）設備數甲乙丙丁0000016354277106310

7、91111412121112515131112解：1.按動態規劃要求確定以下參數： 將分配問題按工廠甲、乙、丙、丁順序分為四個階段。各階段的狀態參數s取為在各階段可能分配設備的總臺數或者說，七是分配給 第k個工廠以后（含第k個工廠）的各工廠的設備總數。U是分配給辨個工廠的設備臺數。狀態轉移方程s =s -u (s )k+1k k k最優指標函數fk（S）是從第k階段開始到最后階段為止的最大利潤指標函數 遞推關系式:k ) + f+1(Sk Juk f4(Sk) = 02.下面進行分階段的計算當k =4時，S（0,1,2,3,4,5） , S4取不同值時，九（S4）的計算如表12-3所示。表 3

8、-34Sud (s , u )Eu*(s )000001144122662331111344121245512125當陣3時，是將s 3 MV,5）臺設備分配給丙和丁兩個工廠。這時，對于每個S 3值都有一個最優分配方案，使這兩個工廠的總利潤為最大。即f (s ) = maxd (S , u ) + f (S )3333344u3=maxd (s ,u ) + f (s -u )333433u3當S3取不同值時，九(S3)的計算如表3-35。當k =2,S2=(0,1,2,3,4,5)；當S2取不同值時，九(S2)的計算如表3-36。當k =1時，Si=5,/i（Si）的計算如表3-37。表 3

9、-35Sud (s , u )333f4(S3 u3)d 3+ f4u*(s )f3( s 3)0000000105441500662154921001021000111132510614214311011001212151116142106162163114154110110012121512175210e2117221411415511011表 3-36sud (s , u )f3( s2 u2 )d2 + f3u*( s )f2()0000000100550513030010100102135827070014140141310133275123909001616131417142710

10、172173951441201200212101316192714212215391019412517513013表 3-37sud (s , u )f2(5 - 1)d1 +f2u*(s )fi(S i)002121161723123271421531010204125175150153.從第一個階段開始尋找最優決策序列，其步驟如下： 由u*(5) = 1,可知應分配給甲工廠1臺設備，剩下4臺設備待以后分配。 由*(4) = 1或2,可知分配給乙工廠有兩個最優方案，1臺或2臺。當分配給乙 2工廠1臺時，剩余3臺待以后分配；當分配給乙工廠2臺時，將剩余2臺設備待分配。 由*(3) 二 2，可知應分