1、第一节 动态规划的基本概念与方法一、多阶段决策问题1.时间阶段的例子（机器负荷问题）某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。123 4 5S1=1000 x1x2x5x4x3s5v1v2v3v4v5s2s3s42.空间阶段的例子（最短路问题）如图为一线路网络。现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。AEB1B2B3C1C2C3D1D229531225156468101312111410阶段1 阶段2 阶段3 阶段4二、基本概念与方程 1.基本概
2、念阶段分步求解的过程，用阶段变量k表示，k=1，n状态每阶段初可能的情形或位置，用状态变量Sk表示。按状态的取值是离散或连续，将动态规划问题分为 离散型和连续型。决策每阶段状态确定后的抉择，即从该状态演变到下阶 段某状态的选择，用决策变量xk表示。状态转移由Sk转变为Sk+1的规律，记Sk+1=T(Sk，xk)。策略由各阶段决策组成的序列，记P1n=x1，xn，称Pkn=xk，xn为阶段k至n的后部子策略。阶段指标每阶段选定决策xk后所产生的效益，记 vk=vk(Sk，xk)。指标函数各阶段的总效益，记相应于Pkn的指标函数 为vkn=vkn(Sk，Pkn)。其中最优的称最优 指标函数，记 f
3、k=fk（Sk）=opt vkn。问题：动态规划的最优解和最优值各是什么？最优解：最优策略P1n，最优值：最优指标f1。2.基本原理与基本方程（1）基本原理。有和允许状态（对任何是最优策略定理：1111111,)1),(略。子过程来说必为最优策至点的为起对于以），子策略（则对任何是最优策略，最优性原理）：若推论（nksPnkkPBellmankknn11以最短路为例说明（2）基本方程 根据最优性原理，可建立从后向前逆推求解的递推公式基本方程：,1,0,11nkffvoptfnkkxkk 动态规划求解的一般步骤：-确定过程的分段，构造状态变量；-设置决策变量，写出状态转移；-列出阶段指标和指标函
4、数；-写出基本方程，由此逐段递推求解。三、求解方法1.离散型（用表格方式求解）例1 用动态规划方法求解前面的最短路问题。AEB1B2B3C1C2C3D1D229531225156468101312111410AEB1B2B3C1C2C3D1D229531225156468101312111410解：设阶段k=1，2，3，4依次表示4个阶段选路的过程；状态sk表示k阶段初可能处的位置；决策xk表示k阶段初可能选择的路；阶段指标vk表示k阶段与所选择的路段相应的路长；指标函数 vk4=表示k至4阶段的总路长；4kiiv ,14,0,51kffvMinfkkk递推公式：AEB1B2B3C1C2C3D
5、1D2295312251564681013121114104k Sk xk vk vkn=vk+fk+1 fkknP21DDEE02052525EDED21321DD21DD21DDC1C2C3935610829532556210588712C1D1EC2D2EC3D2Ek Sk xk vk vkn=vk+fk+1 fkknPAEB1B2B3C1C2C3D1D2295312251564681013121114102B1B2B321CC141271481220B1C1D1EP21CCC41061247108614B2C1D1EP21CCC111213121171281319B3C2D2Ek Sk
6、 xk vk vkn=vk+fk+1 fkknPAEB1B2B3C1C2C3D1D2295312251564681013121114101A321BBB15219152021419AB2C1D1EP*14=AB2C1D1Ef1=19（最短路）（最短距）2.连续型（用公式递推求解）例2 用动态规划方法求解前面的机器负荷问题。某种机器可以在高、低两种负荷下进行生产。高负荷年产量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。解：设阶段k=1，5表示第k年安排机器的过程；状态sk表示第k年
7、初的完好机器台数；决策xk表示第k年投入高负荷的机器台数；则投入低负荷的台数为sk-xk；状态转移sk+1=0.7xk+0.9(sk-xk)；阶段指标vk=8xk+5(sk-xk)表示第k年的产量；指标函数vkn=表示第k至5年的总产量；5kiiv ,15,0,61kffvMaxfkkk递推公式：5505550650553 )5(85 555555sxMaxxsxMaxfvMaxfksxsxsx，当投入高负荷。年初将全部完好机器都即第5,8,5555sfsx44044444054440540412.21.4 )0.9(8(0.753 8)5(84 44444444sxMaxxsxsxMaxsx
8、sxMaxfvMaxfksxsxsxsx，当投入高负荷。年初将全部完好机器都即第4,13.6,4444sfsx33033330430317.240.28 )0.213.6(0.9533 333333sxMaxxssxMaxfvMaxfksxsxsx，当投入高负荷。年初将全部完好机器都即第3,17.52,3333sfsx22022220320220.)0.252(0.917532 222222x.sMaxxs.sxMaxfvMaxfksxsxsx508，当投入低负荷。年初将全部完好机器都即第20,20.8,222sfx11011110210123.7 )0.2(0.92053 111111x.sMaxxs.sxMaxfvMaxfksxsxsx161281，当投入低负荷。年初将全部完好机器都即第1,23.720,111sfx5年的最大总产量为23.721000=23720。
