理學(xué)第八章動(dòng)態(tài)規(guī)劃PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 理學(xué)第八章動(dòng)態(tài)規(guī)劃理學(xué)第八章動(dòng)態(tài)規(guī)劃 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 原問(wèn)題為求從原問(wèn)題為求從A A到到E E走哪條途徑使保險(xiǎn)單（走哪條途徑使保險(xiǎn)單（policypolicy，策略，策略）的總費(fèi)用達(dá)到最??？）的總費(fèi)用達(dá)到最??？ 6 4 第1頁(yè)/共84頁(yè) 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 4 6 1 1 8 7 4 0 第2頁(yè)/共84頁(yè) 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2

2、4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 6 4 第3頁(yè)/共84頁(yè) EDuDf)(,3)( 1414 EDuDf)(,4)( 2424 113 24 14 13 5 )(4 )(2 min)(DCu Df Df Cf ）（， 223 24 14 23 7 )(3 )(6 min)(DCu Df Df Cf ）（， 133 24 14 33 6 )(3 )(3 min)(DCu Df Df Cf ）（， )(3 )(4 )(2 min)( 32 22 12 1 Bf Bf Bf Af 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4

3、1 5 4 3 3 3 3 4 4 6 3 4 0 5 7 6 第4頁(yè)/共84頁(yè) 212 33 23 13 12 11 66 74 57 min )(6 )(4 )(7 minCBu Cf Cf Cf Bf ）（，）（ 122 33 23 13 22 8 )(4 )(2 )(3 min)(CBu Cf Cf Cf Bf ）（， 232 33 23 13 32 8 )(5 )(1 )(4 min)(CBu Cf Cf Cf Bf ）（， 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 6 4 0 3 4 5 7 6 1

4、 1 8 8 第5頁(yè)/共84頁(yè) 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 6 4 0 3 4 5 7 6 1 1 8 8 31 32 22 12 1 11 83 84 112 min )(3 )(4 )(2 minBAu Bf Bf Bf Af ）（，）（ 1 1 u u2 2（B B3 3）=C=C2 2 u u3 3（C C2 2）=D=D2 2 u u4 4（D D2 2）=E=E 最安全道路為最安全道路為ABAB3 3CC2 2DD2 2EE，最小費(fèi)用為，最小費(fèi)用為1111。 第6頁(yè)/共84頁(yè) 第7頁(yè)/

5、共84頁(yè) 第8頁(yè)/共84頁(yè) 狀態(tài)狀態(tài) sn 狀態(tài)狀態(tài) sn+1 決策決策un 效果效果 vn n 第9頁(yè)/共84頁(yè) 第10頁(yè)/共84頁(yè) 第11頁(yè)/共84頁(yè) 第12頁(yè)/共84頁(yè) nknkkk usVus, 1,1 n kj jjj usv),( ),(),( 11, 1,nnkknkkkknk ususVusvV 常用的指標(biāo)函數(shù)常用的指標(biāo)函數(shù)： 1 1 全過(guò)程和它的任一后部子過(guò)程的指標(biāo)函數(shù)等于各階段指標(biāo)函數(shù)之和 全過(guò)程和它的任一后部子過(guò)程的指標(biāo)函數(shù)等于各階段指標(biāo)函數(shù)之和 N Noteote 指標(biāo)函數(shù)應(yīng)具有指標(biāo)函數(shù)應(yīng)具有可分離性可分離性，即，即V Vk,n k,n可表示為： 可表示為： V Vk,

6、n k,n（ （s sk k，u uk k，s sk+1 k+1， ，u uk+1 k+1， ，s sn n，u un n）= = V Vk,n k,n（ （s sk k，u uk k，s sk+1 k+1， ，u uk+1 k+1， ，s sn n，u un n）= = 或或 且且對(duì)于對(duì)于Vk+1，n單調(diào)性單調(diào)性,滿(mǎn)足遞推關(guān)系滿(mǎn)足遞推關(guān)系 第13頁(yè)/共84頁(yè) ),()( , ).( nnkknk uu kk ususVoptsf nk ),()( , )( , nkknk sPp kk psVoptsf knknk n kj nkkkkjjjnk VusvusvV ,1, ),(),( 第1

7、4頁(yè)/共84頁(yè) ),(),(*),( , )( 1, 111, 1 )( , 11, 1 ,11, 11, 1 nkknk sPp Kk sPp nn psVoptpsVoptpsV knknkkk 第15頁(yè)/共84頁(yè) )(),()( 11 )( kkkkk sDu kk sfusvoptsf k k k 第16頁(yè)/共84頁(yè) （邊界條件）0)( )()(,()( 55 1 )( min sf sufsusvsf kkkkkk sDu kk kkk 第17頁(yè)/共84頁(yè) ),( 0)( )(),()( 1 11 11 )( kkkk nn kkkk sDu kk usTs sf sfusvopts

8、f kkk ),( 1)( )(),()( 1 11 11 )( kkkk nn kkkk sDu kk usTs sf sfusvoptsf kkk 第18頁(yè)/共84頁(yè) 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 6 4 0 2 4 3 7 4 8 9 7 11 第19頁(yè)/共84頁(yè) ),( 0)( ,2, 1)(),()( 1 10 11 )( 1 1 kkkk kkkkk sDu kk usTs sf nksfusvoptsf kkk 第20頁(yè)/共84頁(yè) ),( 0)( )(),()( 1 11 11 )(

9、kkkk nn kkkk sDu kk usTs sf sfusvoptsf kkk )(,),( 11 sfsf nn 第21頁(yè)/共84頁(yè) )( 11 sf ),(),()( , 11, 1 )( * , 11, 11 * 1 1, 1, 1 nn sPp nn psVoptpsVsf nn 第22頁(yè)/共84頁(yè) ),( 0)( )(),()( 1 11 11 )( kkkk nn kkkk sDu kk usTs sf sfusvoptsf kkk ),( 1)( )(),()( 1 11 11 )( kkkk nn kkkk sDu kk usTs sf sfusvoptsf kkk 第2

10、3頁(yè)/共84頁(yè) 第24頁(yè)/共84頁(yè) 解解: 2年劃分年劃分2個(gè)階段，個(gè)階段， 表示表示K個(gè)階段高負(fù)荷生產(chǎn)的設(shè)備臺(tái)數(shù)個(gè)階段高負(fù)荷生產(chǎn)的設(shè)備臺(tái)數(shù), 表示第表示第K個(gè)階段完好的設(shè)備臺(tái)數(shù)個(gè)階段完好的設(shè)備臺(tái)數(shù) 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程: -3分分 時(shí)，時(shí)， 時(shí)，時(shí)， 為最優(yōu)解和最優(yōu)值為最優(yōu)解和最優(yōu)值-10分分 xxg8)( yyh6)( k u k s ),(9 . 04 . 0 1kkkk usus 0)(,)()(68)( 3311 0 max sfsfususf kkkkk su kk kk 2k ）取 22222 0 222 0 22 ( ,8)62()(68)( maxmax 2222 sus

11、suususf susu 1k ）令0( ,2 .1322 .138)(68)( 1111 u0 2111 u0 11maxmax 1111 usussususf ss 0 1 u13200)1000(,900 12 fzu 111112 5 .09 .0)(9 .04 .0ususus 第25頁(yè)/共84頁(yè) nju buauaua st ugugugz j nn nn , 2 , 10 )()()(max 2211 2211 用動(dòng)態(tài)規(guī)劃求解上述靜態(tài)模型有一個(gè)統(tǒng)一的方法： 如同線(xiàn)性規(guī)劃問(wèn)題中可以將約束條件看成資源限制一樣，這里也可以這樣理解，將現(xiàn)有數(shù)量為 個(gè)單位的某種資源用來(lái)生產(chǎn) 種產(chǎn)品，問(wèn)如何

12、分配使總利潤(rùn)最大。 設(shè)工廠(chǎng)的決策者分 階段來(lái)考慮這個(gè)問(wèn)題，如果是逆序遞推法，決策者首先考慮的是第 種產(chǎn)品生產(chǎn)幾件，消耗資源多少，然后考慮第 種和第 種產(chǎn)品各生產(chǎn)多少，消耗資源多少；依次向前遞推，在第 階段時(shí)考慮第 種，直到第 種產(chǎn)品各生產(chǎn)多少，消耗資源多少。 bn n 1n n k kn n 第26頁(yè)/共84頁(yè) （1）把問(wèn)題劃分為n個(gè)階段，取 為第k階段的決策變量，或者理解為 第k種產(chǎn)品生產(chǎn)的件數(shù)，第k階段的效益為 ， K子過(guò)程的指標(biāo)函數(shù)為各階段效益之和。 k u ), 2 , 1(),(nkug kk ), 2 , 1()( , nkugV n kj jjnk （2）如何選擇狀態(tài)變量 k s

13、？ ) 1 , 1,( 1 nnkuass kkkk 令 表示可供第 種產(chǎn)品直到第 種產(chǎn)品消耗的資源數(shù)。 顯然 ， 而且 無(wú)后效性，第 階段（產(chǎn)品）消耗的資源數(shù)為 狀態(tài)轉(zhuǎn)移方程為： k s k n 0 k s k sk kku a 第27頁(yè)/共84頁(yè) k u 0 k s 0 k u kkk asu/0 kkkkkk asuusD/0|)( bSbssS kkk 1 ,0| )( kk sf （3）決策變量 的取值范圍： 由 ， 得 于是決策集合： 允許狀態(tài)集合： （4）最優(yōu)值函數(shù) 表示從第k階段到第n階段指標(biāo)函數(shù)的最優(yōu)值 逆序遞推方程： 0)( ) 1 , 1,()()(max)( 11 11

14、 )( nn kkkk sDx kk sf nnksfxgsf kkk 第28頁(yè)/共84頁(yè) nju buauaua st ugugugz j nn nn , 2 , 10 )()()(max 2211 2211 （1）把問(wèn)題劃分為n個(gè)階段，取 為第k階段的決策變量，第k種產(chǎn)品生 產(chǎn)的件數(shù)，第k階段的效益為 ， 指標(biāo)函數(shù)為各階段效益之積。 k u ), 2 , 1(),(nkug kk ), 2 , 1()( , nkugV jj n kj nk 第29頁(yè)/共84頁(yè) （2）如何選擇狀態(tài)變量 k s？ 令 表示可供第 種產(chǎn)品直到第 種產(chǎn)品消耗的資源數(shù)。 顯然 ， 而且 無(wú)后效性，第 階段（產(chǎn)品）消

15、耗的資源數(shù)為 狀態(tài)轉(zhuǎn)移方程為： k s k n 0 k s k sk kku a ) 1 , 1,( 1 nnkuass kkkk 第30頁(yè)/共84頁(yè) k u 0 k s 0 k u kkk asu/0 kkkkkk asuusD/0|)( bSbssS kkk 1 ,0| )( kk sf （3）決策變量 的取值范圍： 由 ， 得 于是決策集合： 允許狀態(tài)集合： （4）最優(yōu)值函數(shù) 表示從第k階段到第n階段指標(biāo)函數(shù)的最優(yōu)值 逆序遞推方程： 1)( ) 1 , 1,()()(max)( 11 11 )( nn kkkk sDx kk sf nnksfxgsf kkk 第31頁(yè)/共84頁(yè) 3 ,

16、2 , 10 10543 654max 321 321 ju uuu st uuuz j kkkk uass 1 10 1 s kkk asu/0 0)( ) 1 , 2 , 3()()(max)( 44 11 )( sf ksfugsf kkkk sDu kk kkk 06max)()(max)( 3 5/0 4433 )( 33 33333 usfugsf susDu 5/ 33 su 5/6)( 333 ssf 取 ， 狀態(tài)轉(zhuǎn)移方程： 223 4uss 第32頁(yè)/共84頁(yè) 當(dāng)k=2時(shí) )4/( 4/5)5/620/1 (5/65/max 5/65max)()(max)( 22 2222

17、4/0 32 4/0 3322 )( 22 22 22222 su sssu susfugsf su susDu 取 狀態(tài)轉(zhuǎn)移方程 ： 當(dāng)k=1時(shí) 112 3uss ) 3/( 3/44/ )3(54max 4/54max)()(max)( 11 1111 3/0 21 3/0 2211 )( 11 11 11111 su susu susfugsf su susDu 取 10 1 s 3/403/1043/4)( 111 ssf 由 得 3/10 1 u 03/103103 112 uss 04/ 22 su 00404 223 uss 05/ 33 su 3/40)0 , 0 , 3/10

18、( * zu T 第33頁(yè)/共84頁(yè) 3 , 2 , 10 6 max 321 3 32 2 1 ju uuu st uuuz j kkk uss 1 6 1 s60 kk su 1)( ) 1 , 2 , 3()()(max)( 44 11 )( sf ksfugsf kkkk sDu kk kkk 3 3 0 4433 )( 33 33333 max)()(max)(usfugsf susDu 33 su 3 333 )(ssf 取 ， 狀態(tài)轉(zhuǎn)移方程： 223 uss 第34頁(yè)/共84頁(yè) 當(dāng)k=2時(shí) )4/( 256/27)(max max)()(max)( 22 4 2 3 222 0

19、3 32 0 3322 )( 22 22 22222 su susu susfugsf su susDu 取 狀態(tài)轉(zhuǎn)移方程 ： 當(dāng)k=1時(shí) 112 uss ) 3/(, 2716 1 )( 256 27 max)()(max)( 11 6 1 4 11 2 1 0 2211 )( 11 11111 sus ususfugsf susDu 取 6 1 s 108)( 11 sf 由 得 23/ 11 su 426 112 uss 14/ 22 su 314 223 uss 3 33 su 108)3 , 1 , 2( * zu T 第35頁(yè)/共84頁(yè) 月份k0123456 需求量dk 08532

20、74 單位工時(shí)ak 111813172010 5 , 4 , 3 , 2 , 1 , 00 294723582 102017131811min 543210 543210 ju uuuuuu st uuuuuuz j 第36頁(yè)/共84頁(yè) 0)( )(min)( 77 1 )( sf dusfuasf kkkkkk sDu kk kKK ) 4( 0 , 1 , 2 , 3 , 4 , 5 , 6 66 ds k )11(10min)( 555 11 55 55 suasf su 第37頁(yè)/共84頁(yè) )( 44 sf )( 444 min sDu )( 444544 dusfua )( 444m

21、in sDu )( 444 min sDu )( 33 sf )( 333 min sDu )( 333433 dusfua )( 333 min sDu 第38頁(yè)/共84頁(yè) )( 333mins Du )( 22 sf )( 222mins Du )( 222322 dusfua )( 222 min sDu 329174 22 su 第39頁(yè)/共84頁(yè) )( 11 sf)( 111211 dusfua )( 111mins Du 377135 11 su )( 00 sf )( 000mins Du )( 000100 dusfua )( 000mins Du 442187 00 su )

22、( 111mins Du 第40頁(yè)/共84頁(yè) k 0 1 2 3 4 5 6 sk2959974 uk7493040 dk0853274 第41頁(yè)/共84頁(yè) 1 u 2 u 0,8 2117 2415310max 2121 2 22 2 11 2 222 2 111 uuuust uuuu uuuuuuz k u k s kkk uss 1 第42頁(yè)/共84頁(yè) kkkkk suusD0|)( 8,80| 1 ssss kkk 0)( ) 1 , 2()()(max)( 33 11 )( sf ksfugsf kkkk sDu kk kkk 允許決策集合為允許決策集合為 允許狀態(tài)集合為允許狀態(tài)集

23、合為 基本方程基本方程 k=2時(shí)時(shí) ) 4 11 (8 4 11 8 121 )( 4 11 0211 211max)()(max)( 22 2222 2 22 2 22 0 3322 )( 22 22222 us sususs uusfugsf susDu 取 取 當(dāng)k=1時(shí) 88 4 11 , 8 121 7 4 11 80,32840)8(2)8(11)7( max )8()7(max )()7(max)()(max)( 1 2 11 1 2 11 2 11 2 11 80 12 2 11 80 112 2 11 0 2211 )( 11 1 1 11111 uuu uuuuuuu uf

24、uu usfuusfugsf u u susDu 第43頁(yè)/共84頁(yè) 4 21 0 8 121 7 8 4 21 32840 )( 1 2 11 1 2 11 1 uuu uuu u ）（最大值為 ）（最大值為 ， 2 7 4 21 )( 4 21 027 8 4 21 628 )( 1 11 11 1 u uu uu u 2 7 1 u 4/112/92/78 112 uss 4/11 2 u 375.27| ) 8 121 7()8( 2 7 2 111 1 u uuf 取取時(shí)，時(shí)， 所以所以 第44頁(yè)/共84頁(yè) 0 1 ij x 否則 套設(shè)備個(gè)分廠(chǎng)分配得第ji 3 1 6 1 max i

25、j ijij xcZ 6 0 1 j ij x 3 1 6 1 64 ij ij jx 第45頁(yè)/共84頁(yè) 第46頁(yè)/共84頁(yè) 444 11 0 )( 1 , 2 , 3)(max)( ssf ksfusf kkk su kk kk %)101)(max)()(max)( 333 0 4433 0 33 3333 ususfsusf susu 0)%)101)( 3 333 u usu %102 3 3 s u 333 %)102()(ssf %)101)(%)(102()( 2233 ussf 444444 )()(suufsf 第47頁(yè)/共84頁(yè) %)101)(%)(102(max)(ma

26、x)( 222 0 332 0 22 2222 ususfusf susu 2 2 2 %)101(%)101(1 s u 2 2 22 %)101(%)101(1)(ssf %)101)( 112 uss %)101)(400( 12 us %)101)(400(%)101 (%)101 (1 )( 1 2 22 usf 第48頁(yè)/共84頁(yè) %)101)(400(%)101 (%)101 (1max)400()( 1 2 1 4000 111 1 uufsf u 0%)101)(400(%)101 (%)101 (1 1 1 2 1 n uu 2 .86%)101 (%)101 (%)101

27、 (1 400 132 1 u 1.43)400( 1 f 第49頁(yè)/共84頁(yè) 第50頁(yè)/共84頁(yè) 第51頁(yè)/共84頁(yè) kkk uss 1 0|)( kkkkk suusD 0)( 1 , 2, 2, 1,)()(max)( 11 1 0 nn kkkkk su kk sf nnnkusfugsf kk 第52頁(yè)/共84頁(yè) 套 數(shù) 利 潤(rùn) 分 廠(chǎng) 0 1 2 3 4 5 6 1 0 3 5 6 7 6 5 2 0 4 6 7 8 9 10 3 0 2 5 9 8 8 7 第53頁(yè)/共84頁(yè) 0|)( kkkkk suusD kkk uss 1 0)( 1 , 2 , 3)()(max)( 44

28、 11 0 sf ksfugsf kkkk su kk kk 第54頁(yè)/共84頁(yè) f g3（3）+f4（s4=s3-u3） f3（s3） u3* u3 s3 0 1 2 3 4 5 6 0 0 0 0 1 0 221 2 0 2 5 52 3 0 2 5 993 4 0 2 5 9 8 93 5 0 2 5 9 8 893 60 2 5 9 8 8 79 3 K=3 第55頁(yè)/共84頁(yè) f g2（u2）+ f3（s3=s2-u2） F2（s2） u2* s3 u2 S2 0123456 0 0+0 000 1 0+2=24+0=4 410 2 0+5=54+2=66+0=6 61，21，0 3

29、 0+9=94+5=96+2=87+0=7 90，13，2 4 0+9=94+9=136+5=117+2=98+0=8 1313 5 0+9=94+9=136+9=157+5=128+2=109+0=9 1523 6 0+9=94+9=136+9=157+9=168+5=139+2=1110+0=10 1633 K=2 第56頁(yè)/共84頁(yè) f g1（u1）+ f2（s2=s1-u1） f1（s1 ） u1* s2 u1 s1 0 1 2 3 4 56 40+13 =13 3+9 =12 5+6 =11 6+4 =10 7+0 =7 1304 50+15 =15 3+13 =16 5+9 =14

30、 6+6 =12 7+4 =11 6+0 =6 1614 60+16 =16 3+15 =18 5+13 =18 6+9 =15 7+6 =13 6+4 =10 5+0 =5 181,25，4 從上表看出最優(yōu)值和最優(yōu)解為： F1（4）=13 ， u1=0，u2=1，u3=3 F1（5）=16，u1=1，u2=1，u3=3 F1（6）=18，u1=1，u2=2，u3=3或 u1=2，u2=1，u3=3 第57頁(yè)/共84頁(yè) 0)( 3 , 2 , 1)()(max)( 10 1 )( 1 1 sf ksfugsf kkkk sDu kk kkk 第58頁(yè)/共84頁(yè) K=2 g1（u1）+ f0（s

31、1） f1（s2） u1* s2 u10123456 00+000 13+0=331 25+0=552 36+0=663 47+0=774 56+0=665 65+0=556 表1-5 第59頁(yè)/共84頁(yè) K=2 g2（u2）+ f1（s2） f2（s3） u1* s3 u20123456 00+000 10+3=34+0=441 20+5=54+3=76+0=671 30+6=64+5=96+3=97+0=791,2 40+7=74+6=106+5=1 1 7+3=1 0 8+0=8112 50+7=74+7=116+6=1 2 7+5=1 2 8+3=1 1 9+0 =9 122,3 60

32、+7=74+7=116+7=1 3 7+6=1 3 8+5=1 3 9+3 =12 10+0= 10 132,3, 4 表 1-6 第60頁(yè)/共84頁(yè) K=3 g3（u3）+ f2（s3） f3 （ s4 ） u 3* u3 s4 0123456 40+11=112+9=135+7=129+4=1 3 8+0=8133 50+12=1 2 2+11=1 3 5+9=149+7=1 6 8+4=128+0=8163 60+13=1 3 2+12=1 4 5+11=16 9+9=1 8 8+7=158+4=1210+0=1 0 183 s s4 4=6=6時(shí)，即購(gòu)時(shí)，即購(gòu)6 6套設(shè)備，套設(shè)備，f

33、f3 3(6) =18(6) =18為最大值為最大值, ,反向追蹤反向追蹤 可知最優(yōu)策略為可知最優(yōu)策略為p p1 1， ，3 3（ （s s3 3=6=6）=1=1，2 2，33或或22，1 1，33。 第61頁(yè)/共84頁(yè) N j jju vZ 1 max N j jj Wuw 1 第62頁(yè)/共84頁(yè) 0)( )(max)( 11 11 /0 NN jjjj wsu jj sf sfuvsf jjj 第63頁(yè)/共84頁(yè) )(30max)( 443 /0 33 333 sfusf wsu jwjvj 1265 2380 3130 第64頁(yè)/共84頁(yè) u3 3 30 u3 f3（3）u3* 012

34、345 00 00 1030 301 203060 602 30306090 903 40306090120 1204 503060901201501505 第65頁(yè)/共84頁(yè) )3(80max)( 2232 /0 22 222 usfusf wsu u2 2 80 u2+f3（2-3 u2） f2（2） u2* 3 01 00+0=0 000 10+30=30 3001 20+60=60 6002 30+90=9080+0=809003 40+120=12080+30=11012004 50+150=15080+60=14015005 第66頁(yè)/共84頁(yè) )2(65max)( 1121 20

35、 11 1 usfusf u u1 1 65u1+f2（1-2u1） f1（1） u1 * 012 50+150 =150 65+90 =155 130+30 =160 1602 j123 wj511 uj*201 第67頁(yè)/共84頁(yè) 第68頁(yè)/共84頁(yè) 部位 巡邏隊(duì)數(shù) 預(yù)期損失 ABCD 218382434 314352231 410312125 第69頁(yè)/共84頁(yè) )()(min)( 11 )( kkkk sDu kk sfugsf kkk 第70頁(yè)/共84頁(yè) )()(min)( 5544 )( 44 444 sfugsf sDu )(min)( 44 )( 44 444 ugsf sDu

36、 第71頁(yè)/共84頁(yè) u4 s4 g4（u4） f4（s4） u4 * s5 234 2343420 334313130 43431252540 53431252540 63431252540 第72頁(yè)/共84頁(yè) )()(min)( 4433 )( 33 333 sfugsf sDu u3 s3 g3（u3）+ f4（s3- u3） f3（s3） u3 * s4 234 424+34=585822 524+31=5522+34=565523 624+25=4922+31=5321+34=554924 724+25=4922+25=4721+31=524734 824+25=4922+25=47

37、21+25=464644 第73頁(yè)/共84頁(yè) )()(min)( 3322 )( 22 222 sfugsf SDu u2 s2 g 2（u2）+ f3（s2- u2） f2（s2） u2 * s3 234 838+49=8735+55=9031+58=898726 938+47=8535+49=8431+55=868436 1038+46=8435+47=8231+49=808046 第74頁(yè)/共84頁(yè) )()(min)12()( 2211 )12( 111 11 sfugfsf Du u1 s1 g1（u1）+ f2（s1- u1） f1（s1） u1* s2 234 1218+80=9814+84=9810+87=979748 第75頁(yè)/共84頁(yè) 銷(xiāo)售點(diǎn) 地區(qū) 012345 1067111521 20912172329 301014192023 第76頁(yè)/共84頁(yè) k x k s kkkkk sxxss 0, 1 0)(,)()()( 4411 0 max sfsfxgsf kkkk sx kk kk 3k f 3