運(yùn)籌學(xué)第07章PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 運(yùn)籌學(xué)第運(yùn)籌學(xué)第07章章 2 第1頁/共164頁 3 A A B B B C C D D D E E F 1 2 3 1 2 1 2 3 1 2 5 2 1 6 4 3 7 3 3 3 2 5 4 2 7 10 8 9 7 11 9 12 13 第2頁/共164頁 4 6 6 生產(chǎn)量，使既能滿足各月的定單生產(chǎn)量，使既能滿足各月的定單 需求，同時(shí)生產(chǎn)成本最低。需求，同時(shí)生產(chǎn)成本最低。 月份月份(k)(k) 成本與需求成本與需求 123456 生產(chǎn)成本生產(chǎn)成本(ck)(ck) （萬元千件）（萬元千件） 2.12.82.32.72.02.5 需求量需求量(rk)(rk)（千（千 件）件）

2、356350326744 第3頁/共164頁 多階段決策過程特點(diǎn)多階段決策過程特點(diǎn): : 狀態(tài)狀態(tài) x1 1 階段階段1 1 T1 決策決策u1 狀態(tài)狀態(tài) x2 決策決策u2 階段階段2 2 T2 狀態(tài)狀態(tài) x3 . 狀態(tài)狀態(tài) xk 決策決策uk 階段階段k k Tk 狀態(tài)狀態(tài) xk+1 1. . 狀狀 態(tài)態(tài) xn 決策決策un 階段階段n n Tn 狀狀 態(tài)態(tài) xn+1 第4頁/共164頁 第5頁/共164頁 7 第6頁/共164頁 付出更新費(fèi)。因此就需要綜合付出更新費(fèi)。因此就需要綜合 權(quán)衡決定設(shè)備的使用年限，使權(quán)衡決定設(shè)備的使用年限，使 總的經(jīng)濟(jì)效益最好?？偟慕?jīng)濟(jì)效益最好。 第7頁/共16

3、4頁 9 第8頁/共164頁 第9頁/共164頁 第10頁/共164頁 12 第11頁/共164頁 第12頁/共164頁 14 第13頁/共164頁 15 第14頁/共164頁 返回 第15頁/共164頁 18用窮舉法求最優(yōu)路線的計(jì)算用窮舉法求最優(yōu)路線的計(jì)算 工作量將會(huì)十分龐大，而且其中工作量將會(huì)十分龐大，而且其中 包含著許多重復(fù)計(jì)算包含著許多重復(fù)計(jì)算 第16頁/共164頁 18 第17頁/共164頁 19 第18頁/共164頁 1.4 1.4 動(dòng)態(tài)規(guī)劃方法導(dǎo)引動(dòng)態(tài)規(guī)劃方法導(dǎo)引 圖1 運(yùn)輸網(wǎng)絡(luò)動(dòng)態(tài)規(guī)劃方法求解圖示 跳過過程跳過過程 第19頁/共164頁 21 第20頁/共164頁 22 各點(diǎn)到

4、終點(diǎn)的最優(yōu)路線，每點(diǎn)上各點(diǎn)到終點(diǎn)的最優(yōu)路線，每點(diǎn)上 方括號(hào)內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)方括號(hào)內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn) 的最短路距離。的最短路距離。 第21頁/共164頁 23 第22頁/共164頁 24 第23頁/共164頁 第24頁/共164頁 第25頁/共164頁 27 第26頁/共164頁 28 第27頁/共164頁 29 第28頁/共164頁 30 第29頁/共164頁 31 第30頁/共164頁 32 第31頁/共164頁 33 第32頁/共164頁 34 第33頁/共164頁 35 第34頁/共164頁 36 第35頁/共164頁 37 )( kkkkk susTs, 1 第36頁/共16

5、4頁 38 第37頁/共164頁 39 第38頁/共164頁 40 )s(p,s(R kkkk 第39頁/共164頁 第40頁/共164頁 42 )u ,s(g)u ,s(g)u ,s(g )u ,s ,u ,s ,u ,s(RR nnnkkkkkk nnkkkkn ,kn ,k 111 11 第41頁/共164頁 43 n ki iiik )u,s(gR 第42頁/共164頁 44 n ki iiik )u,s(gR 第43頁/共164頁 45 )s(p,s(R kkkk n,2 , 1k )s(p,s(Ropt)s(f kkkk )s(Pp kk kKk 第44頁/共164頁 46 )s(

6、u,),s(u),s(u nn1k1kkk n, 2 , 1k )s(u,),s(u),s(u)s(p nn1k1kkkkk n,2 , 1k,u,u,up n1kkk 第45頁/共164頁 47 )ss(f)s(foptf 11111 Ss 0 11 第46頁/共164頁 48 u ,u),s(u)ss(p n211111 )n,2 ,1k(uk 第47頁/共164頁 n,2 ,1k Uu Ss )u,s(Ts . t . s )u,s,u,s,u,s(RRopt kk kk kkk1k nn2211 uu n1 第48頁/共164頁 u,u,u n21 s ,s ,s ,s 1nn21 第

7、49頁/共164頁 51 第50頁/共164頁 )(),(,),(),()( 221111nnkk sususususp )(,),(),()( 11nnkkkkkk susususp 第51頁/共164頁 53 第52頁/共164頁 )s (p ,s (Ropt)s (f kkkk )s(Pp kk kKk ),( n ki iii usgopt 1 ,2 , 1n,nk ),s(f)s(u,s(gopt)s(f )s(f 1k1kkkkk Uu kk 1n1n kk 第53頁/共164頁 )s (p,s (Ropt)s (f kkkk )s(Pp kk kKk n ki iii )u,s(

8、gopt 1 ,2 , 1n,nk )s(f)s(u,s(gopt)s(f )s(f 1k1kkkkk Uu kk 1n1n kk 第54頁/共164頁 56 1 , 2 , 1n, nk )s(f)s(u,s(gmin)s(f 0)s(f 1k1kkkkk )s(Uu kk 1n1n kkk （邊界條件）（邊界條件） 階段指標(biāo)階段指標(biāo) 第55頁/共164頁 第56頁/共164頁 58 第57頁/共164頁 59 第58頁/共164頁 第59頁/共164頁 61 第60頁/共164頁 62 第61頁/共164頁 63 第62頁/共164頁 1 ,2 ,1n,nk ),s(f)s(u,s(gop

9、t)s(f )s(f 1k1kkkkk Uu kk 1n1n kk 1 ,2 ,1n,nk )s(f)s(u,s(gopt)s(f )s(f 1k1kkkkk Uu kk 1n1n kk 或或 第63頁/共164頁 65 第64頁/共164頁 66 第65頁/共164頁 第66頁/共164頁 68 返回返回 第67頁/共164頁 第68頁/共164頁 70 第69頁/共164頁 71 第70頁/共164頁 72 第71頁/共164頁 73 第72頁/共164頁 74 第73頁/共164頁 0 5 8 11 14 17 19 18 21 第74頁/共164頁 第75頁/共164頁 ECBAS 1

10、11 ECBAS 113 ECBAS 123 第76頁/共164頁 78 第77頁/共164頁 79 BA CB D B C D E C 2 1 2 3 1 2 3 1 2 5 1 12 14 10 6 10 4 13 12 11 3 9 6 5 8 10 5 2 階段階段 1 階段階段 2 階段階段 3 階段階段 4 階段階段 5 例：求最短路徑問題例：求最短路徑問題 第78頁/共164頁 80 第79頁/共164頁 81 1 , 2 , 3 , 4k )x(f)d ,x(vmin)x(f 1k1kkkk )x(Dd kk kkk 第80頁/共164頁 x4 D4(x4) x5 v4(x4,

11、d4) v4(x4,d4)+f5(x5) f4(x4) 最優(yōu)決策最優(yōu)決策 d4* D1 D1E E 5 5+0=5* 5 D1E D2 D2E E 2 2+0=2* 2 D2E )x(f)d ,x(vmin)x(f 55444 )x(Dd 44 444 第81頁/共164頁 從從 f4(x4)到到 f3(x3)的遞推過程用表格表示如下：的遞推過程用表格表示如下： x3 D3(x3) x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) 最優(yōu)決策最優(yōu)決策 d3* C1 C1D1 C1D2 D1 D2 3 9 3+5=8* 9+2=11 8 C1D1 C2 C2D1 C2D2

12、D1 D2 6 5 6+5=11 5+2=7* 7 C2D2 C3 C3D1 C3D2 D1 D2 8 10 8+5=13 10+2=12* 12 C3D2 )(),(min)( 44333 )( 33 333 xfdxvxf xDd 第82頁/共164頁 84 )x(f)d ,x(vmin)x(f 33222 )x(Dd 22 222 第83頁/共164頁 x2 D2(x2) x3 v2(x2,d2) v2(x2,d2)+f3(x3) f2(x2) 最優(yōu)決策最優(yōu)決策 d2* B1 B1C1 B1C2 B1C3 C1 C2 C3 12 14 10 12+8=20* 14+7=21 10+12=

13、22 20 B1C1 B2 B2C1 B2C2 B2C3 C1 C2 C3 6 10 4 6+8=14* 10+7=17 4+12=16 14 B2C1 B3 B3C1 B3C2 B3C3 C1 C2 C3 13 12 11 13+8=21 12+7=19* 11+12=23 19 B3C2 第84頁/共164頁 )(),(min)( 22111 )( 11 111 xfdxvxf xDd 從從 f2(x2)到到 f1(x1)的遞推過程用表格的遞推過程用表格 表示如下：表示如下： x1 D1(x1) x2 v1(x1,d1) v1(x1,d1)+f2(x2) f1(x1) 最優(yōu)決策最優(yōu)決策 d

14、1* A A B1 A B2 AB3 B1 B2 B3 2 5 1 2+20=22 5+14=19* 1+19=20 19 A B 2 第85頁/共164頁 87 第86頁/共164頁 求最優(yōu)投資分配使總投資效益最大。求最優(yōu)投資分配使總投資效益最大。 第87頁/共164頁 第88頁/共164頁 90 第89頁/共164頁 91 第90頁/共164頁 92 第91頁/共164頁 第92頁/共164頁 第93頁/共164頁 第94頁/共164頁 第95頁/共164頁 97 第96頁/共164頁 第97頁/共164頁 第98頁/共164頁 第99頁/共164頁 第100頁/共164頁 102 第10

15、1頁/共164頁 第102頁/共164頁 第103頁/共164頁 第104頁/共164頁 106 tn i i )t(n i i k )kk(p pp k 0 1 121 21 1 0 1 討論（續(xù)）討論（續(xù)） 第105頁/共164頁 107 第106頁/共164頁 第107頁/共164頁 第108頁/共164頁 第109頁/共164頁 d30max )x(fdcmax)x(f 3 w/xd0 4433 w/xd0 33 333 333 列出列出 f3(x3)的數(shù)值表的數(shù)值表 第110頁/共164頁 112 第111頁/共164頁 113 )d3x(fd80max )x(fdcmax)x(f

16、2232 3/xd0 3322 w/xd0 22 22 222 對(duì)于對(duì)于 k=2 第112頁/共164頁 第113頁/共164頁 )d2x(fd65max )x(fdcmax)x(f 1121 2/xd0 2211 w/xd0 11 11 111 第114頁/共164頁 列出列出 f1(x1)的數(shù)值的數(shù)值 x1 D1(x1) x2 65d1+f2(x2) f1(x1) d1* 0 0 0 0+f2(0)=0+0=0* 0 0 1 0 1 0+f2(1)=0+30=30* 30 0 2 0 1 2 0 0+f2(2)=0+60=60 65+f2(0)=65+0=65* 65 1 3 0 1 3

17、1 0+f2(3)=0+90=90 65+f2(1)=65+30=95* 95 1 4 0 1 2 4 2 0 0+f2(4)=0+120=120 65+f2(2)=65+60=125 130+f2(0)=130+0=130* 130 2 5 0 1 2 5 3 1 0+f2(5)=0+150=150 65+f2(3)=65+90=155 130+f2(1)=130+30=160* 160 2 第115頁/共164頁 第116頁/共164頁 333 3 w/xd0 4433 w/xd0 33 xdx30 d30max )x(fdcmax)x(f 333 333 第117頁/共164頁 0dx3

18、0 )d3x(30d80max )d3x(fd80max )x(fdcmax)x(f 22 222 3/xd0 2232 3/xd0 3322 w/xd0 22 22 22 222 第118頁/共164頁 2 2 x d160 )d2x(30d65max )d2x(fd65max )x(fdcmax)x(f 1 1 111 2/xd0 1121 2/xd0 2211 w/xd0 11 11 11 111 第119頁/共164頁 121 第120頁/共164頁 月份月份(k) 1 2 3 4 5 6 7 生產(chǎn)成本生產(chǎn)成本(ck) 11 18 13 17 20 10 15 需求量需求量(rk) 0

19、 8 5 3 2 7 4 為了調(diào)節(jié)生產(chǎn)和需求，工廠設(shè)有一個(gè)為了調(diào)節(jié)生產(chǎn)和需求，工廠設(shè)有一個(gè) 產(chǎn)品倉庫，庫容量產(chǎn)品倉庫，庫容量H H =9=9。已知期初庫存量。已知期初庫存量 為為2 2，要求期末（七月底）庫存量為，要求期末（七月底）庫存量為0 0。每。每 個(gè)月生產(chǎn)的產(chǎn)品在月末入庫，月初根據(jù)當(dāng)個(gè)月生產(chǎn)的產(chǎn)品在月末入庫，月初根據(jù)當(dāng) 月需求發(fā)貨。求七個(gè)月的生產(chǎn)量，能滿足月需求發(fā)貨。求七個(gè)月的生產(chǎn)量，能滿足 各月的需求，并使生產(chǎn)成本最低。各月的需求，并使生產(chǎn)成本最低。 第121頁/共164頁 第122頁/共164頁 124 第123頁/共164頁 125 第124頁/共164頁 f6(x6) = mi

20、n c6d6+f7(x7) d6=11-x6 =10d6=10(11- x6)=110-10 x6 第125頁/共164頁 第126頁/共164頁 128 因?yàn)橐驗(yàn)?x5 H = 9，因此因此 d5*= 9-x5 第127頁/共164頁 20(x4-3+d4) = min -3d4-20 x4+280 第128頁/共164頁 第129頁/共164頁 第130頁/共164頁 第131頁/共164頁 133 d2* = 13-x2 第132頁/共164頁 第133頁/共164頁 k 1 2 3 4 5 6 7 ck 11 18 13 17 20 10 15 rk 0 8 5 3 2 7 4 xk

21、2 9 5 9 9 7 4 dk 7 13-x2=4 14-x3=9 12-x4=3 9-x5=0 11-x6=4 0 第134頁/共164頁 136 第135頁/共164頁 第136頁/共164頁 繼續(xù)使用繼續(xù)使用 更新更新 )Keep(K )place(ReR dk Kd1x Rd1 x kk k 1k 第137頁/共164頁 139 階段指標(biāo)：階段指標(biāo)： Kd)t(C Rd)t(S)0(CP Kd)x(C Rd)x(S)0(CP v k k kk kk k 第138頁/共164頁 遞推方程：遞推方程： 終端條件：終端條件：fn(t) = - R ( t ) Kd)1t (f)t (C R

22、d)1(f)t (S)0(CP min Kd)x(f)x(C Rd)x(f)x(S)0(CP min)x(f k1k k1k k1k1kk k1k1kk kk 第139頁/共164頁 141 T 0 1 2 3 4 5 6 7 C(t) 10 13 20 40 70 100 100 - S(t) - 32 21 11 5 0 0 0 R(t) - 25 17 8 0 0 0 0 且且 n = 5，T = 2，P = 50 由上表開始，終端條件為：由上表開始，終端條件為： f6(1) = -25，f6(2) = -17，f6(3) = -8 f6(4) = f6(5) = f6(7) = 0 不

23、可能為不可能為6年年 第140頁/共164頁 Kd Rd )t (f)t (C )(f)t (S)(CP min)t (f 5 5 6 6 5 1 10 Kd fC fSCP f * 5 6 6 5 ,4 4 3 min )17(13 )25(321050 min )2()1( )1()1()0( min)1( 第141頁/共164頁 12 12 14 min )8(20 )25(211050 min )3()2( )1()2()0( min)2( 6 6 5 fC fSCP f d5*= K 24 40 24 min 040 )25(111050 min )4()3( )1()3()0( m

24、in)3( 6 6 5 fC fSCP fd5*= R 第142頁/共164頁 35 100 35 min 0100 )25(01050 min )7()6( ) 1 ()6()0( min)6( 6 6 5 fC fSCP f 30 70 30 min 070 )25(51050 min )5()4( )1()4()0( min)4( 6 6 5 fC fSCP fd5*= R d5*= R 第143頁/共164頁 Kd Rd tftC ftSCP tf 4 4 5 5 4 ) 1()( ) 1 ()()0( min)( 24 25 24 min 1213 )4(321050 min )2(

25、) 1 ( ) 1 () 1 ()0( min) 1 ( 5 5 4 fC fSCP fd4*= R 第144頁/共164頁 35 44 35 min 2420 )4(211050 min )3()2( )1()2()0( min)2( 5 5 4 fC fSCP f 45 70 45 min 3040 )4(111050 min )4()3( )1()3()0( min)3( 5 5 4 fC fSCP f d4*= R d4*= R 第145頁/共164頁 56 135 56 min 35100 )4(01050 min )6()5( )1()5()0( min)5( 5 5 4 fC fSCP f d4*= R 第146頁/共164頁 Kd Rd tftC ftSCP tf 3 3 4 4 3 )1()( )1()()0( min)( 48 48 52 min 3513 24321050 min )2()1( )1()1()0( min)1( 4 4 3 fC fSCP fd3*= K 第147頁/共164頁 63 65 6