第7章动态规划.

第七章动态规划（DynamicProgramming）动态规划是研究多阶段决策问题的一种运筹学方法。第七章动态规划（DynamicProgramming）第一节动态规划的基本概念与方法第二节动态规划应用举例多阶段决策过程最优化:多阶段决策过程是指这样一类特殊的活动过程，它们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。第七章动态规划第一节动态规划的基本概念与方法第一节动态规划的基本概念与方法一、多阶段决策问题1.时间阶段的例子（机器负荷问题）某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。12345S1=1000x1x2x5x4x3s5v1v2v3v4v5s2s3s42.空间阶段的例子（最短路问题）如图为一线路网络。现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。AEB1B2B3C1C2C3D1D229531225156468101312111410阶段1阶段2阶段3阶段4•阶段(k)•状态•决策和策略•状态转移•指标函数将所要研究的问题，按时间或空间特征分成若干个互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量，k=1，…，n。二、基本概念第一节动态规划的基本概念与方法•阶段(k)•状态(sk,Sk)•决策•状态转移•指标函数各阶段开始时可能的情形或位置叫做状态，用状态变量sk表示。sk的取值集合称为状态集合，用Sk表示。某状态以后的过程和以前无关，只与当前状态有关，我们称这种特性为“无后效性”。按状态的取值是离散或连续，将动态规划问题分为离散型和连续型。第一节动态规划的基本概念与方法•阶段(k)•状态(sk,Sk)•决策(uk(sk))•状态转移•指标函数当个阶段的状态取定以后,就可以做出关于下一步的选择了,从而确定下一阶段的状态,这种决定称为决策。在实际问题中决策变量的取值往往限制在一定的范围内,我们称此范围为允许决策集,常用Dk(sk)表示第k阶段从状态sk出发的允许决策集。表示决策的变量叫做决策变量,常用uk(sk)或xk表示第k阶段当状态为sk时的决策变量。第一节动态规划的基本概念与方法•阶段(k)•状态(sk,Sk)•决策(uk(sk))•状态转移•指标函数动态规划中本阶段的状态是上一阶段的决策结果。如果给定了第k阶段的状态sk,本阶段的决策就为uk(sk),则第k+1段的状态sk+1也就完全确定了,它们的关系可表示为：sk+1=Tk(sk,uk)。由于它表示了由k到k+1段的状态转移规律,所以称为状态转移方程。第一节动态规划的基本概念与方法•阶段(k)•状态(sk,Sk)•决策(uk(sk))•状态转移•指标函数指标函数：用于衡量所选定策略优劣的数量指标。阶段指标函数：指第k阶段从状态sk出发，采取决策uk时的数量指标，用vk(sk,uk)表示。后部子过程的指标函数值：指第k阶段，状态为sk采用pk，n时，后部子过程的数量指标函数值，用Vk，n(sk，pk，n)表示。最优指标函数值：它表示从第k段状态sk采用最优策略pk,n到过程终止时的最优数量指标值,记fk=fk（sk）=optvkn。*第一节动态规划的基本概念与方法策略：各段决策确定后,整个问题的决策序列就构成了一个决策,用P1,n{u1(s1),u2(s2),…,un(sn)}表示问题：动态规划的最优解和最优值各是什么？——最优解：最优策略P1n，最优值：最优指标f1。第一节动态规划的基本概念与方法1）阶段2）阶段变量3）状态4）状态变量5）状态集合6）决策7）决策变量8）允许决策集9）策略10）允许策略集11）最优策略12）状态转移方程13）指标函数14）最优值函数基本概念复习及其表示1)Sk?2)uk(sk)?3)Dk(sk)?4)pk,n=?5)P1,n?6)Sk+1=Tk(sk,uk)?7)fk(sk)?8)xk(sk)?说出下列符号的含义三.基本原理与基本方程（1）基本原理。有和允许状态（对任何是最优策略定理：1111111,)1),,(kkpnnfvoptfsnkkxxPk略。子过程来说必为最优策至点的为起对于以），子策略（则对任何是最优策略，最优性原理）：若推论（nksPnkkPBellmankknn11以最短路为例说明（2）基本方程根据最优性原理，可建立从后向前逆推求解的递推公式——基本方程：,1,0,11nkffvoptfnkkxkk动态规划求解的一般步骤：-确定过程的分段，构造状态变量；-设置决策变量，写出状态转移；-列出阶段指标和指标函数；-写出基本方程，由此逐段递推求解。四、求解方法1.离散型（用表格方式求解）例1用动态规划方法求解前面的最短路问题。AEB1B2B3C1C2C3D1D229531225156468101312111410AEB1B2B3C1C2C3D1D229531225156468101312111410解：设阶段k=1，2，3，4依次表示4个阶段选路的过程；状态sk表示k阶段初可能处的位置；决策xk表示k阶段初可能选择的路；阶段指标vk表示k阶段与所选择的路段相应的路长；指标函数vk4=表示k至4阶段的总路长；v,14,0,51kffvMinfkkk递推公式：AEB1B2B3C1C2C3D1D2295312251564681013121114104kSkxkvkvkn=vk+fk+1fkP21DDEE02052525EDED21321DD21DD21DDC1C2C3935610829532556210588712C1D1EC2D2EC3D2EkSkxkvkvkn=vk+fk+1fkPAEB1B2B3C1C2C3D1D2295312251564681013121114102B1B2B321CC141271481220B1C1D1ECCC41061247108614B2C1D1ECCC111213121171281319B3C2D2EkSkxkvkvkn=vk+fk+1fkPAEB1B2B3C1C2C3D1D2295312251564681013121114101A321BBB15219152021419AB2C1D1EP*14=AB2C1D1Ef1=19（最短路）（最短距）2.连续型（用公式递推求解）例2用动态规划方法求解前面的机器负荷问题。某种机器可以在高、低两种负荷下进行生产。高负荷年产量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。解：设阶段k=1，…，5表示第k年安排机器的过程；状态sk表示第k年初的完好机器台数；决策xk表示第k年投入高负荷的机器台数；则投入低负荷的台数为sk-xk；状态转移sk+1=0.7xk+0.9(sk-xk)；阶段指标vk=8xk+5(sk-xk)表示第k年的产量；指标函数vkn=表示第k至5年的总产量；5v,15,0,61kffvMaxf递推公式：5505550650553)5(85555555sxMaxxsxMaxfvMaxfk，当投入高负荷。年初将全部完好机器都即第5,8,sfsx44044444054440540412.21.4))0.9(8(0.7538)5(8444444444sxMaxxsxsxMaxsxsxMaxfvMaxfk，当投入高负荷。年初将全部完好机器都即第4,13.6,4444sfsx33033330430317.240.28)0.213.6(0.9533333333sxMaxxssxMaxfvMaxfk，当投入高负荷。年初将全部完好机器都即第3,17.52,3333sfsx22022220320220.)0.252(0.917532222222x.sMaxxs.sxMaxfvMaxfk508，当投入低负荷。年初将全部完好机器都即第20,20.8,222sfx11011110210123.7)0.2(0.92053111111x.sMaxxs.sxMaxfvMaxfk161281，当投入低负荷。年初将全部完好机器都即第1,23.720,111sfx5年的最大总产量为23.72×1000=23720。[例3].某公司有资金10万元，若投资项目i（I=1,2,3）的投资额为时,其效益分别为:问应如何分配投资数额才能使总收益最大?可列出它的静态模型:ix23332221112)(,9)(,4)(xxgxxgxxg[分析]:这是一个表面与时间没有任何关系的问题,但要用动态规划的方法去解则必须把它划分为“时段”.本题可划分为3个时段,每段只决定对一个投资项目的投资额.这样把问题分解为3阶段决策问题.)3,2,1(010294max3212321ixxxxxxxzi解:kkkkkkkksuusssuussxusssxu112211211111010:,:初始状态为状态变量为设决策变量为233*323033441102,2max,30321,max33ssxxsfksfksfxgsfsxkkkksxkkkk时，函数取极大值为显然当）（时）（，，）（）（）（递推方程为：当k=2时,222202320332022)(29max29max)(9max)(222222xsxsxsfxsfsxsxsx这是一个函数求极值问题,利用微分方法可求得该函数有极小值.是极小值点。而4922sx的情况。讨论真实情况并不如此，要）时求得的（）（注：这只是在，），解得：（）（，令求）（，）（即：取得，，而极大值只能在22222222222222220290920]0[ssffssffsssfsfs0X2s2要讨论的具体情况:2s.),()0(,290),()0(,292*22222*22222做出到此第二阶段的决策已此时时当此时时当sxsffsxsffs.,,29010,29:,,9)(:959max994max94max,9)()(4max)(,101122*222*2221101110011110021100221221011*1*111111故舍之此结论与前矛盾而即相当于时当注时时当xxxxxsxxsssxssxssfsxsxsxsxssfsfxsfk22.100291001004010,1020010,0]100[124max1024max20*3*22*112*11111112111100121110112222*2111到第三个项目最优方案为全部资金投再由状态方程顺推：）（时当）（时当的端点，，比较。微分求解又是一个求极值问题，）（）（）（）（此时）（，另取xxsxssxfxfxsxxsxfxsxsfssfxxsx第二节动态规划应用举例本节将通过动态规划的三种应用类型——资源分配问题、复合系统可靠性问题、设备更新问题，进一步介绍动态规划的特点和处理方法。一、资源分配问题1.问题的一般提法设有某种资源，总数量为a，用于生产n种产品；若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应