1、管管 理理 运运 筹筹 学学1第七章第七章 动态规划动态规划1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理3动态规划的应用动态规划的应用(1)4动态规划的应用动态规划的应用(2)管管 理理 运运 筹筹 学学21 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例例例1 最短路径问题最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC4123123123221647248386756110643751管管 理理 运运 筹筹 学学3一、基本概念：1、阶段k：表示决策顺序的离散
2、的量，阶段可以按时间或空间划分。2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程 sk+1=Tk(sk,xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。2 2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理管管 理理 运运 筹筹
3、 学学4 6、阶段指标函数vk(sk,xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。过程指标函数Vk,n(sk,xk,xk+1,xn)：从状态sk出发，选择决策xk,xk+1,xn所产生的过程指标。动态规划要求过程指标具有可分离性，即 Vk,n(sk,xk,xk+1,xn)=vk(sk,xk)+Vk+1(sk+1,xk+1,xn)称指标具有可加性，或 Vk,n(sk,xk,xk+1,xn)=vk(sk,xk)Vk+1(sk+1,xk+1,xn)称指标具有可乘性。二、基本方程：最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即 ),()(,)
4、(nkknksDxkkPsVsfoptkkk2 2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理管管 理理 运运 筹筹 学学5 对于可加性指标函数，上式可以写为 上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为 以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。nksfxsvsfkkkkksDxkkoptkkk,2,1)(),()(11)(nksfxsvsfkkkkksDxkkoptkkk,2,1)(),()(
5、11)(2 2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理管管 理理 运运 筹筹 学学6三、最优化原理三、最优化原理 作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。2 2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理管管 理理 运运 筹筹 学学7一、资源分配问题一、资源分配问题 例2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润
6、为最大？表10-5 盈利 工厂设备台数 甲 厂 乙 厂 丙 厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 123 3 动态规划的应用动态规划的应用(1)(1)管管 理理 运运 筹筹 学学8二、背包问题二、背包问题 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i=1,2,n），背包中物品的总价值为z，则 Max z=c1x1+c2x2+cn
7、xn s.t.w1x1+w2x2+wnxnW x1,x2,xn0 且为整数。3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学9 下面用动态规划逆序解法求解它。设阶段变量k：第k次装载第k种物品（k=1,2,n）状态变量sk：第k次装载时背包还可以装载的重量；决策变量uk=xk：第k次装载第k种物品的件数；决策允许集合：Dk(sk)=xk|0 xksk/wk，xk为整数；状态转移方程：sk+1=sk wkxk；阶段指标：vk=ckxk；最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使用价值；递推方程：fk(sk)=max ckxk+fk+1(sk+1)=max
8、 ckxk+fk+1(sk wkxk)；xDk(sk)终端条件：fn+1(sn+1)=0。3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学10例3.某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这10个工作日中获利最大？咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润1234432213472811203 3 动态规划的应用动态规划的应用(1)管管
9、 理理 运运 筹筹 学学11 实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这N种物品中第i种物品的重量为，价值为，第i种物品的总数量的，我们可以设表示携带第i种物品的数量，则其数学模型为：S.T.且为整数。我们不妨用此模型去求解例3，也一定得出同样的结果。iwicinix,max1Niiixcf0),2,1(1iiiNiiixNinxWxw3 3动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学12三、生产与存贮问题 例4.某公司为主要电力公司生产大型变压器，由于电力采取预订方式购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的
10、一年前四个月制定一项生产计划，这四个月的需求如表1所示。生产成本随着生产数量而变化。调试费为4，除了调度费用外，每月生产的头两台各花费为2，后两台花费为1。最大生产能力每月为4台，生产成本如表2所示。表13 3动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学13 表表2每台变压器在仓库中由这个月存到下个月的储存费为1，仓库的最大储存能力为3台，另外，知道在1月1日时仓库里存有一台变压器，要求在4月30日仓库的库存量为零。试问该公司应如何制定生产计划，使得四个月的生产成本和储存总费用最少？3 3动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学143 3动态规划的应用动
11、态规划的应用(1)四、系统可靠性问题 例例5.某科研项目组由三个小组用不同的手段顺序研究，它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？高级科学家小组12300.400.600.8010.200.400.5020.150.200.30管管 理理 运运 筹筹 学学154 4动态规划的应用动态规划的应用(2)(2)一、一、连续连续确定性动态规划确定性动态规划 对于状态变量和决策变量只取连续值，过程的演变方式为确
12、定性时，这种动态规划问题就称为连续确定性动态规划问题。管管 理理 运运 筹筹 学学164 4动态规划的应用动态规划的应用(2)(2)机器负荷分配问题机器负荷分配问题 例例1 一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。管管 理理
13、运运 筹筹 学学174 4动态规划的应用动态规划的应用(2)(2)*解 建立动态规划模型：分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然sk-xk为分配给低负荷状态下生产的机器数目。状态转移方程为 sk+1=0.7xk+0.9(sk-xk)阶段指标 rk(sk,xk)=8xk+5(sk-xk)最优指标函数 ，其中k=1,2,3,4,5。f6(s6)=0。)()58max)(11kkkkkkksfxsxsf（kksx 0管管 理理 运运 筹筹 学学18
14、4 4动态规划的应用动态规划的应用(2)(2)*第5阶段：因为f5(s5)是x5的线性单调增函数，故有x5*=s5，于是有f5(s5)=8s5。第4阶段：)(2.126.13max)(9.07.0 8)(58max8)(58max)()(58max)(44404444440544405544404444444444xsxxsxxsxsxsxsfxsxsfsxsxsxsx 管管 理理 运运 筹筹 学学194 4动态规划的应用动态规划的应用(2)(2)*同样的，f4(s4)是x4的线性单调增函数，有x4*=s4，f4(s4)=13.6s4。对前几个阶段依次类推，可得 f3(s3)=17.5s3，f
15、2(s2)=20.75s2，f1(s1)=23.72s1。因为期初共有完好机器1000台，故s1=1000。有f1(s1)=23.72s123720，即5年最大的产量为23720台。得最优解为 ，。这意味着前两年应把年初完好机器完全投入低负荷生产，后三年应把年初完好机器完全投入高负荷生产。0*1x0*2x3*3sx 4*4sx 5*5sx 管管 理理 运运 筹筹 学学204 4动态规划的应用动态规划的应用(2)(2)*下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知s1=1000,根据状态转移方程，有:9009.0)(9.07.01*11*12sxsxs8
16、109.0)(9.07.02*22*23sxsxs5677.0)(9.07.03*33*34sxsxs3977.0)(9.07.04*44*45sxsxs管管 理理 运运 筹筹 学学214 4动态规划的应用动态规划的应用(2)(2)上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？下面来分析：根据终点条件有 可得500)(9.07.05556xsxs
17、25005.455sx管管 理理 运运 筹筹 学学224 4动态规划的应用动态规划的应用(2)(2)*显然，由于固定了终点的状态，x5的取值受到了约束。因此有 类似的，容易解得 ，f4(s4)=21.7s4-7500。75005.18)25005.4(5)25005.4(8max)(555555sssssf75007.07.21max75005.18)(58max)()(58max)(4405444055444044444444xssxsxsfxsxsfsxsxsx0*4x管管 理理 运运 筹筹 学学234 4动态规划的应用动态规划的应用(2)(2)*依次类推，得 f3(s3)=24.5s3-
18、7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用顺序方法递推计算各年的状态，有 s1=1000，0*1*2*3xxx9009.0)(9.07.01*11*12sxsxs8109.0)(9.07.02*22*23sxsxs7297.0)(9.07.03*33*34sxsxs6567.0)(9.07.04*44*45sxsxs管管 理理 运运 筹筹 学学244 4动态规划的应用动态规划的应用(2)(2)可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，也只能全部投入高负荷。相应的最优指标为 f1(s
19、1)=29.4s1-750021900。可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。管管 理理 运运 筹筹 学学25二、离散随机性动态规划二、离散随机性动态规划 随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图：4 4动态规划的应用动态规划的应用(2)(2)sk状态 xk决策概率k阶段的收益p1p2pN.k+1阶段的状态sk+1c1c2cN 1 2N管管 理理 运运 筹筹 学学264 4动态规划的应用动态规划的应用(2)(2
20、)图中N表示第k+1阶段可能的状态数，p1、p2、pN为给定状态sk和决策xk的前提下，可能达到下一个状态的概率。ci为从k阶段状态sk转移到k+1 阶段状态为i时的指标函数值。在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。管管 理理 运运 筹筹 学学27离散随机性动态规划离散随机性动态规划 例例2 2 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概率为0.4，每次试制一批的装配费为200元，每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制，每次生产多少件，才能使得期望费用最小？管管 理理 运运 筹筹 学学28离散随机性动态规划离散随机性动态规划随机采购问题随机采购问题例例3 某公司打算在5周内采购一批原料，未来5周内的原料的价格有三种，这些价格的出现概率可以估计，如下表。该部分由于生产需要，必须在5周内采购这批原料。如果第一周价格很高，可以等到第2周；同样的，第2周如果仍对价格不满意，可以等到第3周；类似地，未来几周都可能选择购买或者等待，但必须保证第5周时采购了该原料。试问该选择哪种采购方案，才能使得采购费用最小？价格 概率 450 0.25 470 0.35 500 0.40
