管理运筹学讲义：动态规划

1、管理运筹学,2,第八章 动态规划,动态规划Dynamic Programming 研究多阶段决策的最优化问题的方法。 多阶段决策问题含有一个描述过程时序或空间演变的阶段变量，将复杂问题划分成若干阶段，根据“最优性原理”，逐段解决而最终实现全局最优。 经济、管理、工业生产、工程技术等领域，许多问题可归结为多阶段决策问题。 一些用线性规划、非线性规划处理有困难的问题，往往可以用动态规划方便地求解。 动态规划是美国运筹学家贝尔曼(R.Bellman)等人1959年提出的,3,第一节 多阶段决策问题,多阶段决策： 经济管理决策中，有些管理决策问题可以按时序或空间演变划分成多个阶段 ，呈现出明显的阶段性

2、； 于是可把这类决策问题分解成几个相互联系的阶段，每个阶段即为一个子问题； 原有问题的求解就化为逐个求解几个简单的阶段子问题； 每个阶段的决策一旦确定，整个决策过程也随之确定，此类问题称为多阶段决策问题。 例如： 企业生产物流：可分为物料供应、生产制造、分销零售等阶段。 最短路问题：可以按空间顺序划分阶段,一、 问题的提出,4,第一节 多阶段决策问题,从生产厂Q到某公司T选择那条路线,使总运费最低(路程最短),最短路问题,Q,T,A1,A2,A3,B1,B2,B3,C1,C1,2,4,3,7,4,6,4,2,4,4,2,5,1,4,6,3,3,3,3,4,生 产 商,某 公 司,出 口 港,进

3、 口 港,城 市,阶段1,阶段2,阶段3,阶段4,5,第一节 多阶段决策问题,这是一个多阶段决策问题，它可分为四个阶段： 第一阶段：从Q(制造厂)到A(出口港)； 第二阶段：从A(出口港)到B(进口港)； 第三阶段：从B(进口港)到C(城市)； 第四阶段：从C(城市)到T(某公司)。 每个阶段选取的路线不同，对应从Q到T就有一系列不同的运输路线: 从始点Q到终点T共有3321=18条不同路线 现在的问题是如何选择一条费用最小的路线,6,第一节 多阶段决策问题,最短路径：Q A3 B1 C1T,二、动态规划的标号法,0,3,T,4,T,4,C1,7,C2,6,C1,11,B1 ,B2,8,B1,

4、8,B1,11,A3,7,第一节 多阶段决策问题,最短路的基本特征 从始点Q到终点T 的最短路径：Q A3 B1 C1T，则 从中点A3 到终点T 的最短路径必为： A3 B1 C1T， 从中点B1 到终点T 的最短路径必为：B1 C1T，。 推广：从始点Q到终点T 的最短路径： Q S1 S2 Sk Sk+1 SnT，则 从中点Sk 到终点T 的最短路径必为： Sk Sk+1 SnT,三、 多阶段决策的基本特征,8,第二节 动态规划原理,阶段(stage) 处理多阶段决策，需将全过程划为若干阶段，每个阶段进行一次抉择。 各阶段按一定顺序联接在一起组成统一的整体。 用k表示阶段变量。 阶段编号

5、 顺序编号 逆序编号,一、动态规划的基本概念,9,第二节 动态规划原理,状态(state) 状态表示过程发展中某阶段的起始状况。 过程的发展可以通过各阶段状态的演变来描述。 状态可用一个变量来描述，称为状态变量，用Sk表示。 选取的状态变量必须满足无后效性。 某阶段的状态给定后，则过程未来发展不受该阶段以前各阶段状态的影响。 第 k 阶段可能有若干状态，用Sk 表示阶段k的状态集合， sk(i)表示第k阶段的第 i 个状态,10,第二节 动态规划原理,决策(decision) 从上一阶段某状态演变到下一阶段某状态要作一次选择，称为决策。 用变量xk(sk)表示第k阶段状态为sk时的决策，称为决

6、策变量，简记xk 决策变量的取值被限制在某一范围内，此范围称为允许决策集合Xk(sk,11,第二节 动态规划原理,策略(policy) 多阶段决策过程中，每一阶段均有一个决策，依序组合成一个全过程的决策序列，称为全过程策略。 p1,n(s1)=x1(s1),x2(s2) , xn(sn) ，简记p1,n =x1, x2, xn 从过程的某个阶段开始到最终阶段结束称为后部子过程。从第k阶段开始的后部子策略称为第k子过程策略。 pk,n(sk)=xk(sk), xk+1(sk+1) , xn(sn) ，简记pk,n =xk, xk+1, xn 每一阶段有若干状态,每个状态又有若干个不同的决策,即有

7、许多策略可供选择。全体策略构成允许策略集合Pk,n(sk)。 能使预期目标达到最优效果的策略称为最优策略P*k,n ， 构成最优策略的各决策称为相应阶段的最优决策x*k,12,第二节 动态规划原理,状态转移方程 下一阶段状态sk+1 是本阶段状态变量sk 和决策变量xk的函数， 即 sk+1 =T(sk, xk(sk) =T(sk, xk) 从状态sk出发到下一阶段状态sk+1的转移规律称为状态转移方程,13,第二节 动态规划原理,指标函数 用来衡量每一阶段决策效果的优劣的数量指标，称为阶段指标函数vk ，阶段指标是状态变量和相应决策变量的函数，即vk = vk(sk , xk )。 最短问题

8、是运费或路程。对阶段的不同状态，采取不同的决策，运费不同。 指标函数也可以是利润、成本、产量等。 从第k阶段的状态sk出发到最后阶段结束，各阶段绩效综合起来反映这个后部子过程的绩效，称为过程指标函数，记为Vk,n。 Vk,n的大小取决于从第k阶段到最后阶段所采取的子策略。即 Vk,n = Vk,n (sk , xk , sk+1 , xk+1 , sn) 根据实际问题的性质，指标函数Vk,n 可以是各个阶段指标的和或积。 从状态sk出发，选取最优策略所得的指标函数值称为最优指标函数值。 fk(sk)=optVk,n =optvk(sk , xk ) + fk+1(sk+1) opt表示最优化，

9、取最大max或最小min,14,第二节 动态规划原理,逆序算法：逆着阶段顺序的方向，由后向前推算。 把寻求最优策略看作连续递推过程，从最终阶段开始，逆着实际过程的进展方向逐段求解； 在每一阶段求解过程中都是其后部子过程最优策略的基础上，再考虑本阶段的指标函数，求出本阶段的最优策略； 直到第一阶段为止。 最优性原理：美国运筹学家贝尔曼提出 无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。 将决策问题划分为若干个阶段，全过程的优化问题就分解为子过程的优化问题，由后向前逐步倒推，最优化的子过程逐渐成为全过程最优。 作为全过程的最优策略P*1,n的组成部分的任一子

10、策略P*k,n(Sk)，一定是从状态Sk 出发直至终点的最优策略,二、动态规划方法的基本思路,15,第二节 动态规划原理,基本递推方程 据最优性原理，阶段k的阶段指标vk(sk ,xk )加上(或乘以)从下一阶段k+1开始到过程结束采取最优策略取得的最优指标函数值fk+1(sk+1) ，再从中选出最优，便是阶段k从状态sk出发到全过程结束的最优指标函数值,16,第二节 动态规划原理,阶段1,阶段2,阶段k,阶段k+1,阶段n,状态S1,决 策 x1,状态S2,v1,决 策 x2,状态S3,v2,决 策 xk,状态Sk+1,vk,决 策 xk+1,vk+1,决 策 xn,vn,寻求最优解的方向,

11、17,第二节 动态规划原理,建模步骤（小结） 对问题进行阶段划分，确定阶段变量k 确定状态变量sk 确定决策变量xk 、允许决策集合Xk (sk ) 写出状态转移方程sk+1 =Tk (sk,xk) 写出指标函数的基本递推方程 明确边界条件 动态规划模型分类,三、动态规划模型,18,第三节 应用举例,资源分配问题： 把有限的资源(如资金、材料、设备、人力等)分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。 资源可以有一种或若干种， 只有一种资源可供分配的问题称之为一维资源分配问题。 一维资源分配问题,一、资源分配问题,如何分配设备，可使获利最大,各分厂 在不同 设备台 数下所 获利

12、润,19,第三节 应用举例,动态规划的数学模型 将三个分厂看作是三个阶段，即阶段变量 k=1,2,3; 状态变量sk 表示第k 阶段初可分配的设备台数,0 sk 6; 决策变量xk 表示第k 阶段分配给分厂k 的设备台数， 允许决策集合Xk (sk)= xk 0 xk sk; 状态转移方程为 sk+1 = sk - xk ; 阶段指标vk(sk, xk) 表示第k 阶段从sk台设备中分配给k 分厂xk 台设备的阶段效益; 最优指数函数fk(sk)表示第k阶段从sk 开始到最后阶段采用最优分配策略取得的最大的效益值; 递推方程函数式,20,第三节 应用举例,逆序求解 K=3,第III分厂在不同设

13、 备台数下所获利润,21,第三节 应用举例,k=2,第II分厂在不同设 备台数下所获利润,第III分厂在设备台数为s3下所获得的最大利润,22,第三节 应用举例,k=1,第I分厂在不同设 备台数下所获利润,第II分厂在设备台数为s2下所获得的最大利润,6,18,1,2,顺序递推，得出结论,第I 分厂1套或2套 第II 分厂2套或1套 第III 分厂3套,23,第三节 应用举例,企业一年中的产品生产往往是分期分批生产的。 组织每批产品的生产，都要花费一些生产准备费和存贮费用。 若某一时期增大生产批量则可减少生产批次，从而降低生产成本。 与此同时，批量大了，必然增加库存而使存贮费用增加。 在企业产

14、品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题,二、生产与存储问题,24,第三节 应用举例,例， 某工厂与用户签订了4个月的交货合同如表所示,该厂生产能力为每月5万件，该厂仓库的存货能力为4万件。 已知生产费用为c=1千元/万件，在进行生产的月份，工厂要支出固定费用b=2千元，每月仓库保管费用h=0.2千元/万件/月。 假定开始时及4月底交货后无存货，试问应在每月各生产多少件产品，才能满足交货任务，又使总费用最小,25,第三节 应用举例,动态规划的数学模型 每个月为一个阶段，即阶段变量 k=1,2,3,4分别表示这

15、四个月; 状态变量sk 表示第k 月初的产品库存量，0 sk 4; 决策变量xk 表示第k月的生产量 ， 允许决策集合Xk (sk)= xk 0 xk 5; 状态转移方程为 sk+1 = sk + xk dk ; 阶段指标vk(sk, xk) 表示第k 月的费用 ：本月若不安排生产，则仅需支出保管费；本月若安排生产，则需支出生产费用和固定费，同时还需交付保管费。 当xk =0时， vk(sk, xk)=h sk =0.2sk 当xk 0时， vk(sk, xk)=b+cxk+hsk =2+xk +0.2sk 最优指数函数fk(sk)表示第k阶段从sk 开始到最后阶段采用最优生产策略实现的最低生

16、产费用,26,第三节 应用举例,逆序求解 K=4,d4=2， 4月末无库存则s5=0， 状态转移方程 s5= s4+ x4 d4 ，则 s4= d4 x4 = 2 x4 x40,则s4 = 2 x4 = 0,1,2 s40,则x4 = 2 s4 = 0,1,2,27,第三节 应用举例,k=3,d3=3， 0s4 2， 状态转移方程 s4= s3+ x3 d3 ，则 0 s3+ x3 d3 2，即 3 s3+ x4 5 0s34， 则s3 = 0,1,2,3,4 生产能力限制 0 x3 5，则x3 = 0,1,2,3,4,5,4月在库存量为s4下的最低生产成本,28,第三节 应用举例,k=2,d

17、2=2， 0s3 4， 状态转移方程 s3= s2+ x2 d2 ，则 0 s2+ x2 d2 4，即 2 s2+ x2 6 s1=0， 则s2 = s1+ x1 d1 = x1 3； x1 5，则s2 2 生产能力限制 0 x2 5，则x2 = 0,1,2,3,4,5,3月在库存量为s3下的最低生产成本,29,第三节 应用举例,k=1,2月在库存量为s2下的最低生产成本,0,14.8,5,顺序递推，得出结论,第1月生产5万件 s2 = s1+ x1 d1 =0+5-3=2，第2月不生产 s3 = s2+ x2 d2 =2+0-2=0，第3月生产5万件 s4 = s3+ x3 d3 =0+5-

18、3=2，第4月不生产,d1=3， s1=0，状态转移方程则s2 = s1+ x1 d1 = x1 3； s20，则 x1 3， 生产能力限制 x1 5，则3 x1 5 ，x1 = 3,4,5,30,第三节 应用举例,有一种设备可以在高低两种不同的负荷下运行，在高负荷下生产时，产品的年产量Q1与投入生产的设备台数x1的关系为： Q1 =9x1 ，年完好率(折损后)a=0.75；在低负荷下生产时，年产量Q2与投入生产的设备台数x2的关系为: Q2 =6 x2 ，年完好率为b=0.96，若开始时拥有完好机器台数为100台，要求制定一个4年计划，在每年初时应决定如何重新分配设备在高低不同的负荷下生产，使得4年内产品的总产量达到最高,三、机器负荷问题,31,第三节 应用举例,动态规划的数学模型 每年为一个阶段，即阶段变量 k=1,2,3,4; 状态变量sk 表示第k年初所拥有的完好机器台数，s1 =100; 决策变量xk 表示第k年投入高负荷生产的机器数 ， 允许决策集合Xk (sk)= xk 0 xk sk; 状态转移方程为 sk+1 =a xk +b(sk xk ) =0.75 xk +0.96(sk xk ) =0.