运筹学 operations research 第二章动态规划 解:设阶段k1,2,3,4依次表示4个阶段选路的 过程; 状态S表示k阶段初可能处的位置; 决策x表示k阶段初可能选择的路; 阶段指标V表示k阶段与所选择的路段相应的路长; 指标函数vk4=∑v,表示k至4阶段的总 路长 k 递推公式:fk=Mm{k+f} f5=0,k=4,…,1
http://www.tju.edu.cn 第二章 动态规划 解：设阶段k=1，2，3，4依次表示4个阶段选路的 过程； 状态sk表示k阶段初可能处的位置； 决策xk表示k阶段初可能选择的路； 阶段指标vk表示k阶段与所选择的路段相应的路长； 指标函数 表示k至4阶段的总 路长； 4 k i 4 i k v v = = ∑ { 1} 5 0, 4, ,1 k kk f Min v f f k = + + = = " 递推公式：
运筹学 operations research 第二章动态规划 k Sk xk VK Vki =V+k+I k P D E 5+0 DE D E 2+0 2 DE 3+5 8 CD,E 9+2 3 6+5 5+2 7 CD, 8+5 10+2 DE
http://www.tju.edu.cn 第二章 动态规划 4 k Sk xk v k vkn=v k+fk+1 fk ∗ P kn 2 1 D D E E 02 05 + + 2 5 2 5 ED D E 2 1 3 2 1 D D 2 1 D D 2 1 D D C 1 C 2 C 3 9 3 5 6 10 8 29 53 + + 25 56 + + 210 58 + + 8 7 1 2 C1 D 1 E C2D 2E C3 D 2E
运筹学 operations research 第二章动态规划 k k +k+1P C.12 2+8 B1C,14 14+7 20 B,CID,E 6+8 2 B C.10 10+7 14 B2CIDE C.4 4+12 13 13+8 B 12+7 19 B3C2D2E 11+12
http://www.tju.edu.cn 第二章 动态规划 k Sk xk vk vkn=vk+fk+1 fk ∗ P kn 2 B1 B2 B3 2 1 C C 14 12 714 812 + + 20 B1C1D1E 3 2 1 C C C 4 10 6 124 710 86 + + + 14 B2C1D1E 3 2 1 C C C 11 12 13 1211 712 813 + + + 19 B3C2D2E