第8章动态规划

动态规划8.1多阶段决策问题与动态规划

8.2动态规划的基本概念

8.3动态规划的步骤

8.4动态规划的应用

1求解静态规划问题

2资源分配问题

3不确定性采购问题

4排序问题

动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。8.1多阶段决策问题与动态规划安全过河问题古代有3位商人各自带了一个仆人外出来到了一个渡口,渡口只有一条小船每次只能乘2人,仆人私下约定只要岸上的仆人人数超过商人人数,就可杀人越货.但是过河的决策由商人制定.问商人如何安全的渡过河去?一、多阶段决策问题1.时间阶段的例子（机器负荷问题）

某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。12345S1=1000x1x2x5x4x3s5v1v2v3v4v5s2s3s48.1多阶段决策问题与动态规划2.空间阶段的例子（最短路问题）

如图为一线路网络。现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。AEB1B2B3C1C2C3D1D229531225156468101312111410阶段1阶段2阶段3阶段4动态规划解决问题的基本特征1.动态规划一般解决最值（最优，最大，最小，最长……）问题；2.动态规划解决的问题一般是离散的，可以分解（划分阶段）的；3.动态规划解决的问题必须包含最优子结构，即可以由（n－1）的最优推导出n的最优动态规划模型的分类：以“时间”角度可分成：

离散型和连续型。从信息确定与否可分成：

确定型和随机型。从目标函数的个数可分成：

单目标型和多目标型。1.基本概念阶段（Stage）——分步求解的过程，用阶段变量k表示，k=1，，n状态（State）——每阶段初可能的情形或位置，用状态变量Sk表示。

按状态的取值是离散或连续，将动态规划问题分为离散型和连续型。决策（

Decision）——每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选择，用决策变量xk表示。状态转移——由Sk转变为Sk+1的规律，记Sk+1=T(Sk，xk)。策略（

Policy）——由各阶段决策组成的序列，记P1n={x1，…，xn}，

称Pkn={xk，…，xn}为阶段k至n的后部子策略。

8.2

基本概念与方程当前状态以前状态决策显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。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

）=optvkn。问题：动态规划的最优解和最优值各是什么？——最优解：最优策略P1n

，

最优值：最优指标f1。多阶段决策过程

d1d2dNs1s2s3

sNsN+112N

V1V2VN

N阶段决策系统示意图2.基本原理与基本方程（1）基本原理以最短路为例说明（2）基本方程根据最优性原理，可建立从后向前逆推求解的递推公式——基本方程：通常动态规划问题的最优值函数满足递推关系式.。

边界条件

动态规划求解的一般步骤：

-确定过程的分段，构造状态变量；

-设置决策变量，写出状态转移；

-列出阶段指标和指标函数；

-写出基本方程，由此逐段递推求解。KSkSk+1XkVk8.3动态规划的求解方法例1

用动态规划方法求解前面的最短路问题。AEB1B2B3C1C2C3D1D2295312251564681013121114101.离散型求解方法

标号法求解在每个节点上标出从该节点到终点的最短距离AEB1B2B3C1C2C3D1D229531225156468101312111410始端终端0528712201419191234逆序解法AEB1B2B3C1C2C3D1D229531225156468101312111410请在每个节点上标出从该节点到始点的最短距离顺序解法解：设阶段k=1，2，3，4依次表示4个阶段选路的过程；

状态sk表示k阶段初可能处的位置；决策xk表示k阶段初可能选择的路；阶段指标vk表示k阶段与所选择的路段相应的路长；指标函数vk4=表示k至4阶段的总路长；

用表格方式求解逆推AEB1B2B3C1C2C3D1D2295312251564681013121114104kSkxkvkvkn=vk+fk+1

fk3C1C2C38712C1D1EC2D2EC3D2EkSkxkvkvkn=vk+fk+1

fkAEB1B2B3C1C2C3D1D2295312251564681013121114102B1B2B320B1C1D1E14B2C1D1E19B3C2D2EkSkxkvkvkn=vk+fk+1

fkAEB1B2B3C1C2C3D1D2295312251564681013121114101A19AB2C1D1EP*14=AB2C1D1Ef1=19（最短路）（最短距）2.连续型（用公式递推求解）例2

用动态规划方法求解前面的机器负荷问题。某种机器可以在高、低两种负荷下进行生产。高负荷年产量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器1000台，需制定一个5年计划，以决定每年安排多少台机器投入高、低负荷生产，使5年的总产量最大。12345S1=1000x1x2x5x4x3s5v1v2v3v4v5s2s3s4阶段指标vk=8xk+5(sk-xk)表示第k年的产量；指标函数vkn=表示第k至5年的总产量；解：设阶段k=1，…，5表示第k年安排机器的过程；状态sk表示第k年初的完好机器台数；决策xk表示第k年投入高负荷的机器台数；则投入低负荷的台数为sk-xk

；状态转移sk+1=0.7xk+0.9(sk-xk)；f5(S5

)是关于x5的单调增函数x5*=S5

f5

(S5

)=8S55年的最大总产量为23.72×1000=23720。逆推解法的特点:12345S1x1x2x5x4x3s5v1v2v3v4v5s2s3s4始端已知终端边界值取0或11.已知初始状态s12.最优值函数fk(sk)表示第k阶段的初始状态为sk,从k阶段到n阶段的最优值.该问题的最优值f1(s1)3.边界条件是fn+1=0或者14.递推关系是fk(sk)=opt(vk+fk+1)8.4

动态规划应用举例

本节将通过动态规划的四种应用类型——静态规划问题的动态规划求解、资源分配问题、复合系统可靠性问题、设备更新问题，进一步介绍动态规划的特点和处理方法。123S1x1x2x3v1v2v3s2s3s4三阶段决策问题状态变量Sk:s1,s2,s3,s4决策变量为xi:x1,x2,x3例子:一、静态规划问题的动态规划求解123S1x1x2x3v1v2v3s2s3s44假定s1=4,用逆推法可分析每个阶段的状态转移:第3阶段:s3=x3第2阶段:s2=x2+s3第1阶段:s1=x1+s2递推方程:每个阶段上决策变量的取值范围?123S1x1x2x3v1v2v3s2s3s4k123sk431x*k121fk441123S1x1x2x3v1v2v3s2s3s44假定s4=4,用顺推法可分析每个阶段的状态转移:第1阶段:s2=x1第2阶段:s3=x2+s2第3阶段:s4=x3+s3递推方程:每个阶段上决策变量的取值范围?已知终止状态sn+1怎么求解动态规划?k123sk-+1134x*k121fk144二、资源分配问题1.问题的一般提法

设有某种资源，总数量为a，用于生产n种产品；若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，可使总收益最大？2.数学规划模型模型的特点——变量分离。3.用动态规划方法求解阶段k状态sk决策xk=1,…,n表示把资源分配给第k种产品的过程；表示在给第k种产品分配之前还剩有的资源量；表示分配给第k种产品的资源量；状态转移sk+1=sk-xk；阶段指标vk指标函数vkn

12S1=ax1x2g1(x1)g2(x2)

nxnsngn(xn)s2s3...例3某公司拟将某种高效设备5台分配给所属甲、乙、丙3厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总效益最大？效益厂设备台数甲乙丙000013542710639111141211125131112解：阶段k状态sk决策xk=1,2,3依次表示把设备分配给甲、乙、丙厂的过程；表示在第k阶段初还剩有的可分台数；表示第k阶段分配的设备台数；状态转移sk+1=sk-xk；阶段指标vk指标函数vk3

问题：本问题是属于离散型还是属于连续型？怎样解？——离散型，用表格的方式求解。效益厂设备台数甲乙丙000013542710639111141211125131112kSkxkvkvk+fk+1

fk30123450123450461112120+04+06+011+012+012+0046111212012345kSkxkvkvk+fk+1

fk0123452000+000-0

000+4155+051-0

000+6155+421010+0102-0

000+11155+621010+431111+0142-1

000+12155+1121010+631111+441111+0161-32-2

000+12155+1221010+1131111+641111+451111+0212-3kSkxkvkvk+fk+1

fk15012345037912130+213+167+149+1012+513+0210-2-32-2-1最优策略：P*13为0-2-3或2-2-1，即分给甲厂0台、分给乙厂2台、分给丙厂3台，或分给甲厂2台、分给乙厂2台、分给丙厂1台。最优值：f1=21。可见，最优解可以是不唯一的，但最优值是唯一的。资源分配问题的应用很广泛，例如：

1.某学生正在备考4门功课，还剩7天时间，每门功课至少复习1天。若他已估计出各门功课的复习天数与能提高的分数之间的关系，问他应怎样安排复习时间可使总的分数提高最多？

2.背包问题：旅行者携带的背包中能装的物品重量为a，现他要从n种物品中挑选若干数量装入背包，问他应如何挑选可使所带的物品总价值最大？其中,ci(xi)表示携带数量为xi的价值函数;Wi表示第i种物品的单件重量1n2s1x1x2xnSn+1s2v1=c1(x1)vn=cn(xn)v2=c2(x2)sn三、复合系统工作可靠性问题1.问题的一般提法

设某工作系统由n个部件串接而成，为提高系统的可靠性，在每个部件上装有备用件。已知部件i上装有xi个备用件时，其正常工作的概率为pi(xi)；每个部件i的备用件重量为wi，系统要求总重量不超过W。问应如何安排备用件可使系统可靠性最高？串接:122.数学规划模型模型的特点——变量分离。3.用动态规划方法求解12S1=Wx1x2p1(x1)p2(x2)

nxnsnpn(xn)s2s3...阶段k状态sk决策xk=1,…,n表示安排第k个部件备用件的过程；表示在给第k个部件安排之前还剩有的容许重量；表示第k个部件上安排的备用件数量；状态转移sk+1=sk-wkxk；阶段指标vk指标函数vkn

可靠性问题的应用很广泛，例如：

1.某重要的科研攻关项目正在由3个课题组以3种不同的方式进行，各组已估计出失败的概率。为减少失败的概率，选派了2名高级专家去充实科研力量。若可估计出各组增加专家后的失败概率，问应如何分派专家可使总的失败概率最小？

2.已知x1+x2+…+xn=c，求z=x1x2…xn的最大值。四、设备更新问题例4

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

=rk[tk

]-uk[tk]-ck(tk)(1-xk)(1-xk)xk四、其他——随机型问题举例例5

某瓷厂接受订制一个瓷瓶的任务。瓷瓶用电炉烧制。据技术分析估计，每个瓷瓶出炉后的合格率为0.5，各瓶合格与否相互独立