動態(tài)規(guī)劃資源分配問題ppt課件

1、動態(tài)規(guī)劃資源分配問題 小組成員：黃秀梅 羅燕雯 楊俊 李彩霞 林琳 （女） 吳晶瑩 鄧桂蘭 羅碧輝資源分配問題：只有一種資源有待于分配到若干個活動，其目標是如何最有效地在各個活動中分配這種資源。在建立任何效益分配問題的DP(Dynamic Programming )模型時，階段對應(yīng)于活動，每個階段的決策對應(yīng)于分配到該活動的資源數(shù)量；任何狀態(tài)的當(dāng)前狀態(tài)總是等于留待當(dāng)前階段和以后階段分配的資源數(shù)量，即總資源量減去前面各階段已分配的資源量。 標題：一名大學(xué)生還有7天就要進入有四門考試科目的期末考試。他想盡可能有效地分配這7天復(fù)習(xí)時間，每門學(xué)科至少需要1天復(fù)習(xí)時間。他喜歡每天只復(fù)習(xí)一門課，所以他可能分

2、配給每門功課的時間是1，2，3或4天，由于最近學(xué)習(xí)了運籌學(xué)他希望用DP方法安排時間以使能從這四門課中得到最高的總學(xué)分，他估計每門課的時間分配可能產(chǎn)生的學(xué)分如下表。用DP方法求解這個問題。 課程 學(xué)分復(fù)習(xí)天數(shù)1 2 3 4 1 2 3 4 3 5 24 5 6 45 6 8 78 7 8 8數(shù)）前面階段未分配完的天是仍待分配的天數(shù)（即狀態(tài)變量：sk的天數(shù)；科目）是分配到階段（考試（k1，2，3，4決策變量：x，4?？荚嚳颇侩A段：k1，2，3個階段。成動態(tài)規(guī)劃模型中的四這四門考試科目可以看定的次序，因此，即使這里沒有固少天給每門考試科目。即應(yīng)分配多4個相應(yīng)關(guān)聯(lián)的決策，解：這個問題要求作出kk0sf

3、1,2,3k )()(max)(1 .,3 , 2 , 1 ),(max)(maxxPxsf1xxx x 7xxx x.)()()()(maxxxxxixx5*5*1,.,2, 1*i4*41kkkkk43214321443322114321i）（將遞推關(guān)系寫出即是且為整數(shù)大于等于（）（），（目標可改寫成且為整數(shù)，使，是挑選的效果量，我們的目標天給考試科目）表示分配（令kkkkksxkkkikikkkkkkkkiiiixsfxPsfxsxsxxsfsfxPtsxPxPxPxPPkk當(dāng)k=4時;f4(s4) = max p4(x4) 1 xk sk 1 sk 4s41 2 3 4x411 21

4、2 31 2 3 4p4(x4)22 42 4 72 4 7 8f4(s4)2 4 7 8X4*1 2 3 4 當(dāng)k=3時; f3(s3) = max p3(x3)+ f4(s4) 1 x3 s3 2 sk 5 計算結(jié)果:S32 3 4 5X311 21 2 31 2 3 4p3(x3)55 65 6 85 6 8 8F3+ p379 812 10 1013 13 12 10f3(s3)791213X3*1111或2 當(dāng)k=1時; f1(s1) = max p1(x1)+ f2(s2) 1 x1 s1 s1=7 計算結(jié)果:S1 7X1 1 2 3 4P1(x1) 4 4 5 8F2+ p121 19 17 18f1(s1)21X1*1 當(dāng)k=2時; f2(s2) = max p2(x2)+ f3(s3) 1 x2 s2 3 s2 6 計算結(jié)果:S23456X211 21 2 31 2 3 4p2(x2)33 53 5 6 3 5 6 7F3+ p21012 1215 14 1316 17 15 14f2(s2)10121517X2*11或211天?？颇繌?fù)習(xí)天；第四天；第三科目復(fù)習(xí)天；第二