運籌學(xué)課件 動態(tài)規(guī)劃

運籌帷幄之中決勝千里之外運籌學(xué)課件動態(tài)規(guī)劃DynamicProgramming綜述

動態(tài)規(guī)劃所研究的對象是多階段決策問題。所謂多階段決策問題是指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。每個階段的決策確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的效益的總和達(dá)到最優(yōu)。動態(tài)規(guī)劃的基本概念與模型最優(yōu)化原理動態(tài)規(guī)劃的數(shù)學(xué)模型第二節(jié)離散確定性動態(tài)規(guī)劃模型的求解預(yù)期損失巡邏隊數(shù)A1B2C3D4218382434314352231410312125x4s4P4(x4)f4(s4)x4*23423434233431313434312525453431252546343125254x3s3P3(x3)+f4（s3－x3）f3(s3)x3*234424+34582524+3122+34552624+2522+3121+34492724+2522+2521+31473824+2522+2521+25464x2s2P2(x3)+f3（s2－x2）f2(s2)x2*234838+4935+5531+58872938+4735+4931+558431038+4635+4731+49804s1=12x1s1P1(x1)+f2（s1－x1）f1(s1)x1*2341218+8014+8410+87974x1s2P1(x1)f1(s2)x1*23421818231814143418141010451814101046181410104x2s3P2(x2)+f1（s3－x2）f2(s3)x2*234438+18562538+1435+18522638+1035+1431+18482738+1035+1031+14453,4838+1035+1031+10414x3s4P3(x3)+f2（s4－x3）f3(s4)x3*234824+4822+5221+56722924+4522+4621+526921024+4122+4521+48652s5=12x4s5P4(x4)+f3（s5－x4）f4(s5)x4*2341234+6531+6925+72974動態(tài)規(guī)劃應(yīng)用資源分配問題最短路徑問題旅行售貨員問題生產(chǎn)經(jīng)營問題排序求對三個項目的最優(yōu)投資分配，使總投資效益最大。

資源分配問題

有資金4萬元，投資A、B、C三個項目，每個項目的投資效益與投入該項目的資金有關(guān)。三個項目A、B、C的投資效益（萬噸）和投入資金（萬元）關(guān)系見下表：階段k：每投資一個項目作為一個階段；狀態(tài)變量xk：投資第k個項目前的資金數(shù)；決策變量dk：第k個項目的投資；決策允許集合：0≤dk≤xk狀態(tài)轉(zhuǎn)移方程：xk+1=xk-dk階段指標(biāo)：vk(xk

,dk)見表中所示；遞推方程：fk(xk)=max{vk(xk

,dk)+fk+1(xk+1)}終端條件：f4(x4)=0k=4，f4(x4)=0

k=3，0≤d3≤x3，x4=x3-d3

k=2，0≤d2≤x2，x3=x2-d2k=1，0≤d1≤x1，x2=x1-d12511214106104131112396581052C1C3D1AB1B3B2D2EC2最短路徑問題求從A到E的最短路徑2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f