《运筹学》课件 第8章 动态规划

第8章动态规划8.1动态规划的基本概念8.2动态规划的最优性原理8.3动态规划问题的建模与求解8.4动态规划应用举例第8章内容提要8.1动态规划的基本概念动态决策问题在生产和经营活动中，经常遇到这样的问题，它们包含若干个相互联系的阶段，在每个阶段都要做出决策，从而使整个过程达到最优。因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线。这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程，就称为多阶段决策过程，也称序贯决策过程。12……状态n决策状态决策状态状态状态决策多阶段决策问题：整个决策过程可按照时间或空间顺序分解成若干相互联系的阶段，每一阶段都需要作出决策，全部过程的决策是一个决策序列。目标是要达到整个过程的最优，而不是单个阶段的最优。动态规划的基本概念AB1B2B3FC1C2C3D1D2D3E1E135495435171584642544269721ABCDEF12345阶段（k）：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。阶段的划分，一般是根据时间和空间的自然特征来划分。上例中k=1,2,3,4,5，其中第一个阶段的起点为A，终点为B1、B2或B3。状态（Sk）：简单来讲，状态是指某阶段的出发位置，即阶段的起点。描述过程状态的变量称为状态变量，常用Sk表示第k阶段的状态变量。上例中，第三阶段有三个状态，则状态变量可取三个值，即S3={C1,C2,C3}。点集合={C1,C2,C3}称为第三阶段的可达状态集合。决策（uk(Sk)）：决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量，常用uk(sk)表示第k阶段当状态处于sk时的决策变量。如：u1(s1)={u1(A)}={B1,B2,B3} 在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。如：D2(B2)={C1,C2,C3}策略：全过程各个阶段的决策uk按顺序排列组成的有序总体，记为：P1,n(s1)={u1(s1),u2(s2)…,un(sn)}子策略：由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程，也称为k子过程。与之相对应的决策序列Pk,n(sk)={uk(sk),uk+1(sk+1)…,un(sn)}

称为k子过程策略，简称子策略。状态转移方程：确定过程由一个状态到另一个状态的演变过程。如果给定第k阶段的起始状态sk与决策变量uk(sk)，则第k+1阶段的状态变量sk+1的值也就确定了。这种关系可用公式：sk+1=Tk(sk,uk)

上式描述了由k到k+1阶段的状态转移规律，称为状态转移方程。Tk称为状态转移函数。指标函数：是评价动态规划决策结果优劣的数量指标，它是定义在全过程和所有后部子过程上确定的数量函数，一般以Vk,n表示。指标函数可以是时间、效率、利润、成本或产量等。Vk,n=Vk,n(sk,uk,sk+1,…,sn+1)一般而言，指标函数满足如下递推关系：

Vk,n(sk,uk,sk+1,…,sn+1)=ψk[sk,uk,Vk+1,n(sk+1,…,sn+1)]最优指标函数：记为fk(sk)，表示从第k阶段的状态sk开始，到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值，即：其中，opt表示最优的意思，可以是max或min。V是函数关系，可以表示加法关系，也可以表示乘法关系或其它。在最短路线问题中，指标函数Vk,n就表示在第k阶段由点sk至终点F的距离，用dk(sk,uk)=vk(sk,uk)表示第k阶段由点sk到点sk+1=uk(sk)的距离。例如，

d4(D3,E2)=5，表示在第4阶段，由点D3到点E2的距离为5。fk(sk)表示从第k阶段点sk到终点F的最短距离。如

f4(D2)就表示从第4阶段中的点D2到点F的最短距离指各个阶段的数量指标，记为dk(sk,uk)，如d2(B3,C2)＝1，表示距离。策略指标函数：指策略的数量指标值，记为：

z=d1(s1,u1)+…+d5(s5,u5)最优策略：指策略指标函数达到最优的策略。

Minz=d1(s1,u1)+…+d5(s5,u5)8.2动态规划的最优性原理最优化原理贝尔曼最优化原理：作为整个过程的最优策略，无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必构成最优策略。即：一个最优策略的子策略总是最优的。MAB例如，若M是从A到B最优路线上的任一点，则从M到B的路线也是最优路线。整个问题将最后一阶段问题最优化将最后两阶段问题最优化整个问题最优化指标函数递推方程贝尔曼最优化原理可以导出指标函数递推方程：

f*n(Sn)为从第n个阶段到终点的最短距离，f*n+1(Sn+1)为从第n+1个阶段到终点的最短距离，dn(Sn,Xn)为第n个阶段的距离，f*5(S5)为递推的起点，通常为已知的。求解过程由最后一个阶段的优化开始，按逆向顺序逐步向前一阶段扩展，并将后一阶段的优化结果带到扩展后的阶段中去，以此逐步向前推进，直至得到全过程的优化结果。AB1B2E495648768935623143ABCDE1234例1：最短线路问题B3C1C2C3D1D2解：(1)k=4，起始状态集合为：s4={D1,D2}

当s4=D1时，从D1到E的路线只有一条，其距离d(D1,E)=4，所以f4(D1)=4;

当s4=D2时，从D2到E的路线只有一条，其距离d(D2,E)=3，所以f4(D2)=3;(2)k=3，起始状态集合为：s3={C1,C2,C3}

当s3=C1时，从C1到E的路线有两条，C1→D1→E或C1→D2→E。我们要在这两条路线中选择一条最短路线，即：其最短路线是C1→D1→E

，相应的决策变量是u3(C1)=D1

当s3=C2时，从C2到E的路线也有两条，C2→D1→E或C2→D2→E。

其最短路线是C2→D2→E

，相应的决策变量是u3(C2)=D2

当s3=C3时，从C3到E的路线也有两条，C3→D1→E或C3→D2→E。

其最短路线是C3→D1→E

，相应的决策变量是u3(C3)=D1(3)k=2，起始状态集合为：s2={B1,B2,B3}

当s2=B1时，从B1出发的线路有两条B1C1和B1C2

。可以计算得：其最短路线是B1→C2→D2→E

，相应的决策变量是u2(B1)=C2

当s2=B2时，从B2出发的线路有三条B2C1、B2C2和B2C3

。可以计算得：其最短路线是B2→C3→D1→E

，相应的决策变量是u2(B2)=C3

当s2=B3时，从B3出发的线路有两条B3C2和B3C3

。可以计算得：最短路线是B3→C2→D2→E

，相应的决策变量是u2(B3)=C2(4)k=1，起始状态集合为：s1={A}。从A出发的线路有三条AB1、AB2和AB3

。可以计算得：其最短路线是A→B1→C2→D2→E

，相应的决策变量是u1(A)=B1因此，最优策略序列是：

u1(A)=B1,u2(B1)=C2,u3(C2)=D2,u4(D2)=E31动态规划的基本思想：关键在于正确地写出基本的递推关系式和恰当的边界条件（基本方程）；在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法；在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线。8.3动态规划问题的建模与求解AB1B2E495648768935623143ABCDE1234动态规划的标号法B3C1C2C3D1D2437559111313动态规划的表格计算——从最后一个阶段开始：n=4时，这一步数据为已知，是递推的起点：u4s4d(u4)f4(s4)u4*ED144ED233E动态规划的表格计算n=3时：第3阶段到终点分两步走：第3阶段到终点的距离等于第3阶段的距离加上第4阶段到终点的最短距离，其计算如下：u3s3d(u3)+f4f3(s3)u3*D1D2C13+4=75+3=87D1C26+4=102+3=55D2C31+4=53+3=65D1n=2时：第2阶段到终点分两步走：第2阶段到终点的距离等于第2阶段的距离加上第3阶段到终点的最短距离，其计算如下：u2s2d(u2)+f3f2(s2)u2*C1C2C3B16+7=134+5=9-9C2B28+7=157+5=126+5=1111C3B3-8+5=139+5=1413C2n=1时：第1阶段到终点分两步走：第1阶段到终点的距离等于第1阶段的距离加上第2阶段到终点的最短距离，其计算如下：因此，可以得到从A到E的最短路线（即最优策略）为：A→B1→C2→D2→EA到E的最短距离为：f1(s1)＝13u1s1d(u1)+f2f1(s1)u1*B1B2B3A4+9=139+11=205+13=1813B1动态规划的逆推解法与顺推解法逆推解法：即由最后一段到第一段逐步求出各点到终点的最短路线，最后求出A点到E点的最短路线。运用逆序递推方法的好处是可以始终盯住目标，不致脱离最终目标。顺推解法：其寻优方向与过程的行进方向相同，求解时是从第一段开始计算，逐段向后推进，计算后一阶段时要用到前一段求优的结果，最后一段的计算结果就是全过程的最优结果。动态规划的优点减少计算量；丰富计算结果。40动态规划模型的建立所研究的问题必须能够分成几个相互联系的阶段，且在每个阶段都具有需要进行决策的问题；在每一阶段都必须有若干个与该阶段相关的状态，识别每一阶段的状态是建立动态规划模型的关键内容。状态的选取要注意以下几个要点：在所研究问题的各阶段，都能直接或间接确定状态变量的数值；状态的后无效性：即以第k阶段的状态sk为出发点的后部子过程的最优策略应与sk状态之前的过程无关。具有明确的指标函数Vk,n，且阶段指标值dk(sk,uk)可以计算。动态规划的求解步骤将问题合理分成阶段。设阶段总数为n，边界条件fn(sn)，然后从最后一个阶段n的优化开始，逐步向前一阶段推进，直至第一阶段为止。在每一阶段都进行如下的步骤：列出本阶段所有可能的状态变量sk对每一个状态sk列出可能的决策变量uk(sk)对每一对sk,uk(sk),计算本阶段的指标值dk(sk,uk)利用状态转移方程sk+1=T(sk,uk)，对每对sk,uk(sk)求出sk+1的值；计算每一对sk,uk(sk)的指标值dk(sk,uk)+fk+1(sk+1)将上一步中各指标值进行比较，取最优者（极大或极小）为从本阶段sk状态开始的后部子过程的最优指标fk(sk)，相应的决策即是本阶段以sk为起始状态的最优决策uk*(sk)在第一阶段的最优决策确定之后，第一阶段的最优初始s1*即可确定，然后根据状态转移方程确定下一阶段的最优状态。这样，最优策略所经过的各阶段最优状态即可逐次得到，从而确定了最优策略的状态变化路线。8.4动态规划应用实例定价问题资源分配问题背包问题例2某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元、8元这四个价格中选取其中之一，每年年初允许变动价格，但幅度不能超过1元。该公司预计该产品畅销只有五年，五年后将被淘汰。另据销售情况的预测，在价格不同的情况下，各年的预计利润额如下表。现在问公司将如何为产品定价，以实现五年内的利润最大化？1.定价问题预计利润额单价(元)第1年第2年第3年第4年第5年5678101214161213141515161615202018142524181410121520251213162024141416181816151514145元6元7元8元动态规划的表格计算——从最后一个阶段开始：n=5时，这一步数据为已知，是递推的起点：u5s5d5f5(s5)u5*E1E2E3E4E12525E1E22424E2E31818E3E41414E4n=4时：第4阶段到终点分两步走：第4阶段的利润等于第4阶段的利润加上第5阶段的最大利润，其计算如下：u4s4d4+f5f4(s4)u4*E1E2E3E4D120+2520+2445E1D220+2520+2420+1845E1D318+2418+1818+1442E2D414+1814+1432E3n=3时：第3阶段到终点分两步走：第3阶段的利润等于第3阶段的利润加上第4阶段以后的最大利润，其计算如下：u3s3d3+f4f3(s3)u3*D1D2D3D4C115+4515+4560D1,D2C216+4516+4516+4261D1,D2C316+4516+4216+3261D2C415+4215+3257D3n=2时：第2阶段到终点分两步走：第2阶段的利润等于第2阶段的利润加上第3阶段以后的最大利润，其计算如下：u2s2d2+f3f2(s2)u2*C1C2C3C4B112+6012+6173C2B213+6013+6113+6174C2,C3B314+6114+6114+5775C2,C3B415+6115+5776C3n=1时：第1阶段到终点分两步走：第1阶段的利润等于第1阶段的利润加上第2阶段以后的最大利润，其计算如下：u1s1d1+f2f1(s1)u1*B1B2B3B4A110+7310+7484B2A212+7312+7412+7587B3A314+7414+7514+7690B4A416+7516+7692B4可知，为获得最大利润，各年的定价策略为：A4→B4→C3→D2→E1，即：第一年：8元；第二年：8元；第三年：7元；第四年：6元；第五年：5元2.资源分配问题某种资源总量为a，用于生产n种产品。设分配数量xi用于生产第i种产品，第i种产品的收益为gi(xi)。问如何分配才使总收益最大？模型为：Maxz=g1(x1)+…+gn(xn)S.t.x1+x2+…+xn=a,xj≥0这是静态决策问题，可将其化为动态模型来求解。例3某有色金属公司拟拔出50万元对所属三家冶炼厂进行技术改造。若以10万元为最小分割单位，各厂收益与投资的关系如下表所示。问对三个工厂如何分配这50万元，才能使总收益达到最大？投资额(单位：十万元)技术改造后收益工厂1工厂2工厂301234504.57.09.010.512.002.04.57.511.015.005.07.08.010.013.0思路：首先对工厂1进行分配，余下的对工厂2进行分配，最后余下的分配给工厂3。建立如下动态规划数学模型：工厂1工厂2工厂3阶段k(工厂)：1,2,3状态sk(可供分配的资金量)：s1={5};s2=s1-u1,s3=s2-u2决策uk(已分配的资金量)：0≤u1≤s1,0≤u2≤s2,0≤u3≤s3状态转移方程：sk+1=sk-uk指标函数(收益)：

d1(u1)={0,4.5,7,9,10.5,12}

d2(u2)={0,2,4.5,7.5,11,15}

d3(u3)={0,5,7,8,10,13}指标递推方程：

fk(sk)=max[dk(uk)+fk+1(sk+1)]，k=1,2 f3(s3)=max[d3(u3)]利用表格进行计算，从最后一个阶段开始

k=3,u3=s3u3s3d3f3(s3)u3*0123450000155127723883410104513135k=2时，0≤u2≤s2，s3=s2-u2u2s2d2+f3f2(s2)u2*01234500+0=00010+5=52+0=25020+7=72+5=74.5+0=4.570,130+8=82+7=94.5+5=9.57.5+0=7.59.5240+10=102+8=104.5+7=11.57.5+5=12.511+0=1112.5350+13=132+10=124.5+8=12.57.5+7=14.511+5=1615+0=15164k=1时，0≤u1≤s1，s2=s1-u1u1s1d1+f2f1(s1)u1*01234550+16=164.5+12.5=177+9.5=16.59+7=1610.5+5=15.512+0=12171

可见，当s1=5，此时u1*=1，s2=s1-u1*=4,u2*=3;s3=s2-u2*=1,u3*=1最优策略为：P={u1*,u2*,u3*}={1,3,1}即给工厂1分配10万元，工厂2分配30万元，工厂3分配10万元，可使总收益达到最大为17万元。背包问题假设一个徒步旅行者，有n种物品供他选择后装入背包中。设这n种物品编号为1,2,…,j,…,n，并已知一件第j种物品的重量为wj千克，这一件物品对他的使用价值为cj。又知这位旅行者本身所能承受的总重量不能超过W千克。问该旅行者如何选择这n种物品的件数，以对他来说使用价值最大？3.背包问题一般的数学模型：背包问题的动态规划模型求解：用状态变量sk表示背包中可装进第k种至第n种物品的总重量(即从k阶段开始，还可以装入的总重量)；用决策变量xk表示背包中装进第k种物品的件数，则背包中装进第k种至第n种物品后的总重量为

sk=∑wkxk

,sk+1=sk-wkxk。用fk(sk)表示背包装入第k种至第n种商品所得的最大使用价值。则根据最优化原理，有如下递推方程：65例4解背包问题

max z=8x1+5x