第8章动态规划

1、动态规划动态规划 8.1 多阶段决策问题与动态规划 8.2 动态规划的基本概念 8.3 动态规划的步骤 8.4 动态规划的应用 1 求解静态规划问题 2 资源分配问题 3 不确定性采购问题 4 排序问题 动态规划所研究的对象是多阶段决策问题。动态规划所研究的对象是多阶段决策问题。 所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。益，而且决定下一阶段的初始状态。 每个阶段

2、的决策确定以后，就得到一个决策每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。略，使各阶段的效益的总和达到最优。8.1 多阶段决策问题与动态规划多阶段决策问题与动态规划安全过河问题安全过河问题古代有3位商人各自带了一个仆人外出来到了一个渡口, 渡口只有一条小船每次只能乘2人,仆人私下约定只要岸上的仆人人数超过商人人数,就可杀人越货.但是过河的决策由商人制定.问商人如何安全的渡过河去?一、多阶段决策问题1. 时间阶段的例子（机器负荷问题） 某厂有1000台机器，现需作一个五年计划，以决定每

3、年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。123 4 5S1=1000 x1x2x5x4x3s5v1v2v3v4v5s2s3s48.1 多阶段决策问题与动态规划多阶段决策问题与动态规划2. 空间阶段的例子（最短路问题） 如图为一线路网络。现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。AEB1B2B3C1C2C3D1D229531225156468101312111410阶段1 阶段2 阶段3 阶段4动态规划解决问题的基本特征1. 动态规划一般解决最值（最优，最大，最小，最长）问题；2. 动态规划解决的

4、问题一般是离散的，可以分解（划分阶段）的；3. 动态规划解决的问题必须包含最优子结构，即可以由（n1）的最优推导出n的最优1.基本概念阶段分步求解的过程，用阶段变量k表示，k=1，n状态每阶段初每阶段初可能的情形或位置，用状态变量Sk表示。 按状态的取值是离散或连续，将动态规划问题分为 离散型和连续型。决策 每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选择，用决策变量xk表示。状态转移由Sk转变为Sk+1的规律，记Sk+1=T(Sk， xk)。策略 由各阶段决策组成的序列，记P1n=x1， xn， 称Pkn=xk， xn为阶段k至n的后部子策略。 8.2 基本概念与方程基本概念与方程

5、显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。KSkSk+1XkVk过河:决策向量xk(I,J)初始状态s1是T(3,3)结束状态sn是 T(0,0)可达状态有哪些?(3,J) (2,2) (1,1) (0,J)0321123AJII 表示留在左岸的商人人数J 表示留在左岸的仆人人数阶段指标每阶段选定决策xk后所产生的效益，记 vk= vk(Sk， xk)。指标函数各阶段的总效益，记相应于Pkn的指标函数 为vkn= vkn(Sk， Pkn )。其中最优的称最优 指标函数，记 fk = fk（ Sk ）=opt vk

6、n。问题：动态规划的最优解和最优值各是什么？最优解：最优策略P1n ， 最优值：最优指标f1。多阶段决策过程多阶段决策过程 d1 d2 dNs1 s2 s3 sN sN+1 1 2 N V1 V2 VN N 阶段决策系统示意图2.基本原理与基本方程（1）基本原理。有和允许状态（对任何是最优策略定理：1111111, )1),(kkkpnnfvoptfsnkkxxP略。子过程来说必为最优策至点的为起对于以），子策略（则对任何是最优策略，最优性原理）：若推论（nksPnkkPBellmankknn11以最短路为例说明（2）基本方程,1, 0, 11nkffvoptfnkkxkk 根据最优性原理，可

7、建立从后向前逆推求解的递推公式基本方程：通常动态规划问题的最优值函数满足递推关系式.。 边界条件 动态规划求解的一般步骤： - 确定过程的分段，构造状态变量； - 设置决策变量，写出状态转移； - 列出阶段指标和指标函数； - 写出基本方程，由此逐段递推求解。KSkSk+1XkVk8.3 动态规划的求解方法动态规划的求解方法例1 用动态规划方法求解前面的最短路问题。AEB1B2B3C1C2C3D1D2295312251564681013121114101. 离散型离散型求解方法求解方法 标号法求解标号法求解在每个节点上标出从该节点到终点终点的最短距离AEB1B2B3C1C2C3D1D22953

8、1225156468101312111410始端终端0528712201419191234逆序解法AEB1B2B3C1C2C3D1D229531225156468101312111410请在每个节点上标出从该节点到始点始点的最短距离顺序解法解：设阶段k=1，2，3，4依次表示4个阶段选路的过程； 状态sk表示k阶段初可能处的位置；决策xk表示k阶段初可能选择的路；阶段指标vk表示k阶段与所选择的路段相应的路长；指标函数 vk4 = 表示k至4阶段的总路长；4kiiv ,14, 0, 51kffvMinfkkk递推公式： 用表格方式求解用表格方式求解逆推AEB1B2B3C1C2C3D1D2295

9、312251564681013121114104k Sk xk vk vkn=vk+fk+1 fkknP21DDEE02052525EDED21321DD21DD21DDC1C2C3935610829532556210588712C1D1EC2D2EC3D2Ek Sk xk vk vkn=vk+fk+1 fkknPAEB1B2B3C1C2C3D1D2295312251564681013121114102B1B2B321CC141271481220B1C1D1EP21CCC41061247108614B2C1D1EP21CCC111213121171281319B3C2D2Ek Sk xk vk

10、 vkn=vk+fk+1 fkknPAEB1B2B3C1C2C3D1D2295312251564681013121114101A321BBB15219152021419AB2C1D1EP*14=AB2C1D1Ef1 = 19（最短路）（最短距）2. 连续型（用公式递推求解）例2 用动态规划方法求解前面的机器负荷问题。 某种机器可以在高、低两种负荷下进行生产。高负荷年产量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。123 4 5S1=1000 x1x2x5x4x3s5v1v2v3v

11、4v5s2s3s4阶段指标vk=8xk+5(sk-xk)表示第k年的产量；指标函数vkn= 表示第k至5年的总产量；5kiiv ,15, 0, 61kffvMaxfkkk递推公式：解：设阶段k=1，5表示第k年安排机器的过程； 状态sk表示第k年初的完好机器台数； 决策xk表示第k年投入高负荷的机器台数；则投入低负荷的台数为sk-xk ； 状态转移sk+1=0.7xk+0.9(sk-xk)；5505550650553 )5(85 555555sxMaxxsxMaxfvMaxfksxsxsx，当投入高负荷。年初将全部完好机器都即第5,8,5555sfsx44044444054440540412.

12、21.4 )0.9(8(0.753 8)5(84 44444444sxMaxxsxsxMaxsxsxMaxfvMaxfksxsxsxsx，当投入高负荷。年初将全部完好机器都即第4,13.6,4444sfsxf5 (S5 )是关于x5的单调增函数 x5 *=S5 f5 (S5 )= 8S533033330430317.240.28 )0.213.6(0.9533 333333sxMaxxssxMaxfvMaxfksxsxsx，当投入高负荷。年初将全部完好机器都即第3,17.52,3333sfsx22022220320220. )0.252(0.917532 222222x.sMaxxs.sxMa

13、xfvMaxfksxsxsx508，当投入低负荷。年初将全部完好机器都即第20,20.8,222sfx11011110210123.7 )0.2(0.92053 111111x.sMaxxs.sxMaxfvMaxfksxsxsx161281，当投入低负荷。年初将全部完好机器都即第1,23.720,111sfx5年的最大总产量为23 .721000=23720。逆推解法的特点:123 4 5 S1x1x2x5x4x3s5v1v2v3v4v5s2s3s4始端已知终端边界值取0或11.已知初始状态s12.最优值函数fk(sk)表示第k阶段的初始状态为sk,从k阶段到n阶段的最优值. 该问题的最优值f

14、1(s1)3.边界条件是fn+1=0或者14.递推关系是 fk(sk)=opt(vk+fk+1)8.4 动态规划应用举例动态规划应用举例n 本节将通过动态规划的四种应用类型静态规划问题的动态规划求解、资源分配问题、复合系统可靠性问题、设备更新问题，进一步介绍动态规划的特点和处理方法。3,2,104max3213221ixxxxxxxZi123 S1x1x2x3v1v2v3s2s3s4三阶段决策问题状态变量Sk: s1,s2,s3,s4决策变量为xi:x1,x2,x31122233kvvxvxvx：阶段指标例子例子:一、静态规划问题的动态规划求解一、静态规划问题的动态规划求解123 S1x1x2

15、x3v1v2v3s2s3s44假定s1=4,用逆推法可分析每个阶段的状态转移:第3阶段: s3=x3第2阶段: s2=x2+s3第1阶段: s1=x1+s21,2,31)(max41kffvfkkkDk递推方程:每个阶段上决策变量的取值范围?11223300sxsxsx)(max)(max)(max)(, 2,)(max)(max)(, 3222203220320223*33343332222223333xsxsxfvsfksxsxfvsfksxsxsxsxsx的极值问题函数关于求令2222222h),(),(xxsxsxh有极大值时有极小值；反之，时，h,0h0,02222dxhddxhdd

16、xdh2*23222222322222222222232,274)(32, 0232),(0, 03222sxssfsxsdxhdsxxxsxdxdhsx为极大值点故舍去得)(274(max)274(max)(max)(, 131110321021011112211xsxsxfvsfksxsxsx141,641)(41, 021, 0)(98)(94)(9441, 0)(94)(2741*14111112141212112121112112112121111211131111111sxssfsxsdxhdsxdxhdxsxxsxsdxhdsxsxxsxxsdxdhsxsx为极大值点故舍去得12

17、3 S1x1x2x3v1v2v3s2s3s4k123sk431x*k121fk4414maxz123 S1x1x2x3v1v2v3s2s3s44假定s4=4,用顺推法可分析每个阶段的状态转移:第1阶段: s2=x1第2阶段: s3=x2+s2第3阶段: s4=x3+s33,2,1,1)(max)(011kffvsfkkDkkk递推方程:每个阶段上决策变量的取值范围?43322100sxsxsx已知终止状态sn+1怎么求解动态规划?3*233232202220120322*121012132,274)(max)(max)(max)(, 2,)(max)(max)(,xs

18、xsxsxfvsfksxsxfvsfksxsxsxsxsx4*3443343033302304341,641)(274(max)274(max)(max)(, 3434343sxsxsxsxfvsfksxsxsxk123sk-+1134x*k121fk144二、资源分配问题二、资源分配问题1. 问题的一般提法 设有某种资源，总数量为a，用于生产n种产品；若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，可使总收益最大？2. 数学规划模型ixi种产品的资源数量为设分配给第决策变量： niiixgMaxz1)( 目标函数：nixaxinii,1,0 1约束条件：模型的特点变量分

19、离。3.用动态规划方法求解阶段k状态sk决策xk=1,n表示把资源分配给第k种产品的过程；表示在给第k种产品分配之前还剩有的资源量；表示分配给第k种产品的资源量；状态转移sk+1= sk- xk ；阶段指标vk指标函数vkn ；nkiiikkxgxg)()(,1,0,11nkffvMaxfnkkxkk基本方程12S1=ax1x2g1(x1)g2(x2) nxnsngn(xn)s2s3.例例3 3 某公司拟将某种高效设备某公司拟将某种高效设备5 5台分配给所属甲、台分配给所属甲、乙、丙乙、丙3 3厂。各厂获此设备后可产生的效益如下厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总

20、效益最大？表。问应如何分配，可使所产生的总效益最大？效益厂设备台数甲 乙 丙0 0 0 01 3 5 42 7 10 63 9 11 114 12 11 125 13 11 12解：阶段k状态sk决策xk=1,2,3依次表示把设备分配给甲、乙、丙厂的过程；表示在第k阶段初还剩有的可分台数；表示第k阶段分配的设备台数；状态转移sk+1= sk- xk ；阶段指标vk指标函数vk3 ；阶段分配后产生的效益表示第3k)(iiixvk,1,0,1234kffvMaxfkkxkk基本方程问题：本问题是属于离散型还是属于连续型？怎样解？离散型，用表格的方式求解。效益厂设备台数甲 乙 丙0 0 0 01 3

21、 5 42 7 10 63 9 11 114 12 11 125 13 11 12k Sk xk vk vk+fk+1 fkknP3012345012345 0 4 6111212 0+0 4+0 6+011+012+012+0 0 4 6111212012345k Sk xk vk vk+fk+1 fkknP0123452 0 0 0+0 0 0-0 0 0 0+4 1 5 5+0 5 1-0 0 0 0+6 1 5 5+4 2 10 10+010 2-0 0 0 0+11 1 5 5+6 2 10 10+4 3 11 11+014 2-1 0 0 0+12 1 5 5+11 2 10 10

22、+6 3 11 11+4 4 11 11+016 1-3 2-2 0 0 0+12 1 5 5+12 2 10 10+11 3 11 11+6 4 11 11+4 5 11 11+021 2-3k Sk xk vk vk+fk+1 fkknP15012345 0 3 7 912130+21 3+167+149+1012+513+021 0-2-3 2-2-1最优策略：P*13 为0-2-3或2-2-1， 即分给甲厂0台、分给乙厂2台、分给丙厂3台， 或分给甲厂2台、分给乙厂2台、分给丙厂1台。最优值： f1=21。可见，最优解可以是不唯一的，但最优值是唯一的。资源分配问题的应用很广泛，例如：

23、1.某学生正在备考4门功课，还剩7天时间，每门功课至少复习1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，问他应怎样安排复习时间可使总的分数提高最多？ 2.背包问题：旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？11max( )01niniiiniiiixizc xw xaxi设决策变量 为第 种物品的装入件数，其数学模型为且为整数，其中,ci(xi)表示携带数量为xi的价值函数;Wi表示第i种物品的单件重量1n2s1x1x2xnSn+1s2v1=c1(x1)vn=cn(xn)v2=c2(x2)sn三、复合系

24、统工作可靠性问题三、复合系统工作可靠性问题1. 问题的一般提法 设某工作系统由n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。已知部件i上装有xi个备用件时，其正常工作的概率为pi(xi)；每个部件i的备用件重量为wi，系统要求总重量不超过W。问应如何安排备用件可使系统可靠性最高？串接:122. 数学规划模型个备用件个部件安排设给第决策变量：ixi )( 1iinixpMaxz目标函数：为非负整数约束条件：iniiixWxw1 模型的特点变量分离。3.用动态规划方法求解12S1=Wx1x2p1(x1)p2(x2) nxnsnpn(xn)s2s3.阶段k状态sk决策xk=1,n表示

25、安排第k个部件备用件的过程；表示在给第k个部件安排之前还剩有的容许重量；表示第k个部件上安排的备用件数量；状态转移sk+1= sk- wkxk ；阶段指标vk指标函数vkn ；的可靠性；部件安排备用件后产生表示第)(niikixpk,1,1n1nkffvMaxfkkxkk1基本方程可靠性问题的应用很广泛，例如： 1.某重要的科研攻关项目正在由3个课题组以3种不同的方式进行，各组已估计出失败的概率。为减少失败的概率，选派了2名高级专家去充实科研力量。若可估计出各组增加专家后的失败概率，问应如何分派专家可使总的失败概率最小？ 2.已知x1+x2+xn=c，求z=x1x2xn的最大值。四、设备更新问

26、题四、设备更新问题例4 某运输公司购进一批卡车投入运营，公司每年初需对卡车作出更新或继续使用的决定。假设第k年中，rk(tk)表示车龄为tk的车使用一年的收入，uk(tk)表示车龄为tk的车使用一年的维修费用，ck(tk)表示车龄为tk的车更新成新车的费用。现公司需制定一个10年计划，以决定如何安排使10年的总收入最大。12S1=？x1x2 10 x10s10v1v2v10s2问题：状态和决策怎样设置？ 决策是更新与否，可用0-1变量表示；状态可设为车龄。阶段k状态sk决策xk= 1,10表示第k年的决策过程；= tk表示第k年的车龄；年不更新，第年更新第kk0 1, 状态转移tk+1= tk

27、 +1(1-xk)阶段指标vk指标函数vkn = rktk - uktk - ck(tk)(1-xk)(1-xk)xk；10kiiv,110,0,111kffvMaxfkkxkk1 ,M基本方程四、其他随机型问题举例例5 某瓷厂接受订制一个瓷瓶的任务。瓷瓶用电炉烧制。据技术分析估计，每个瓷瓶出炉后的合格率为0.5，各瓶合格与否相互独立（即一炉如装有n个瓷瓶，那么出炉后都不合的概率为0.5n）。制造一个瓷瓶的原料费为100元，烧一炉的费用为300元。现因厂中条件限制最多只能烧3炉，每炉最多装4个瓷瓶。若3炉的瓷瓶无1个合格，则因不能履行合同而被罚款1600元。试用动态规划方法确定一种生产方案（即

28、每炉该装几个瓷瓶），使总的期望成本为最小。采采购购与与销销售售 某商店在未来的4个月里,准备用它的一个仓库来专门经销某种商品,仓库最大容量能贮存这种商品1000单位.假定该商店每月只能出卖仓库现有的货,当商店在某月购货时,下月初才能到货.预测该商品未来四个月的买卖价格如表7-12所示,假定商店在1月开始经销时,仓库贮有该商品500单位.试问若不计库存费用,该商店应如何制定1月至4月的订购与销售计划,使预期获利最大。1281317 10911151234销售单价购买单价月份 kkckpKSkSk+1XkVkYk)(100010000kkkkkkxsysxs题目给出的约束条件题目给出的约束条件n建立动态规划模型建立动态规划模型阶段k : 按月份划分为4个阶段，K1，2，3，4 ：第K月定购的货物数量ky状态转移方程：ks状态变量 : 第K月初时仓库中的存货量（含上月订货）决策变量 ：kx第K月卖出的货物数量)(kksf最优指标函数 ：第K月初存货量为 时，从第K月到4月末所获得最大利润。kskkkkxyss1则有逆序递推关系式(基本方程)为：1 , 2 , 3 , 4k )()()(100000max)( 55110sfsfycxpxsysxsfkkkkkkkkkkkkkn建立动态规划模型建立动态规划模型当 K4 时1517max)(44443