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

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

2、給每門功課的時(shí)間是1，2，3或4天，由于最近學(xué)習(xí)了運(yùn)籌學(xué)他希望用DP方法安排時(shí)間以使能從這四門課中得到最高的總學(xué)分，他估計(jì)每門課的時(shí)間分配能夠產(chǎn)生的學(xué)分如下表。用DP方法求解這個(gè)問題。 課程 學(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個(gè)階段。成動(dòng)態(tài)規(guī)劃模型中的四這四門考試科目可以看定的次序，因此，即使這里沒有固少天給每門考試科目。即應(yīng)分配多4個(gè)相應(yīng)關(guān)聯(lián)的決策，解：這個(gè)問題要求作出kk0sf1

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

4、 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時(shí); f3(s3) = max p3(x3)+ f4(s4) 1 x3 s3 2 sk 5 計(jì)算結(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時(shí); f1(s1) = max p1(x1)+ f2(s2) 1 x1 s1 s1=7 計(jì)算結(jié)果:S1 7X1 1 2 3 4P1(x1) 4 4 5 8F2+ p121 19 17 18f1(s1)21X1*1 當(dāng)k=2時(shí); f2(s2) = max p2(x2)+ f3(s3) 1 x2 s2 3 s2 6 計(jì)算結(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í)天；第二