运筹学04动态规划1精选课件

1、第四章 动态规划Dynamic Programming多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例本章内容重点 动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家贝尔曼（Bellman）等人在20世纪50年代提出。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理 、 工程技术等方面的许多实际问题。 动态规划是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。动态规划的基本原理多阶段决策过程最优化 多阶段决策

2、过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。例 生产与存储问题 某工厂每月需供应市场一定数量的产品。供应需求所剩余产品应存入仓库，一般地说，某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个每月的生产计划，在满足需求条件下，使一年的生产与存储费用之和最小。例 投资决策问题 某公司现有资金Q亿元，在今后5年内考虑给A、B、C、D四个项目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些项目每年的投资额，使到第五年末拥有资金的本利总额最大。例

3、 设备更新问题 企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用。多阶段决策过程特点:状态 s1阶段1g1决策d1状态 s2决策d2阶段2g2状态 s3.状态 sk决策dk阶段kgk状态 sk+1.状态 sn决策dn阶段ngn状态 sn+1多阶段决策问题(Multi-Stage decision process)AEDCB252755610.53例1（不定阶段最短路线问题） 如图是一个五座城市的及其相连道路的交通图，线上的数字是对应的路长。问：应如何选择行驶路线，才能使从A、B、C、D各城市到E城市的行驶路程最短？从图中可以看出，任

4、意两座城市之间都有道路相通。我们把从一座城市直达另一座城市作为一个阶段。例从A城市到E城市的阶段数，少则一个（例从A城市直达E城市），多则无限（例从A城市通过其他B、C、D三城市循环到E城市）。为避免循环，加上约束条件：每个城市至多经过一次。 于是从A城市到达E城市的阶段数有下列四种情形：1.从A城市直达E城市，一个阶段。2.从A城市通过其他B、C、D三城市之一到E城市，二个阶段。3.从A城市通过其他B、C、D三城市之二到E城市，三个阶段。4.从A城市通过其他B、C、D三城市各一次到E城市，四个阶段。A 3 B1 4 C1 3 D14 5 3 2B2 2 C2 3 D2 E11 2 3 4C3

5、 4 D3 5 E2 2 F例2（一定阶段最短路问题） W先生每天驾车去公司上班。如图，W先生的住所位于A，公司位于F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是要确定一条最省时的上班路线。动态规划的基本概念阶段；状态；决策和策略；状态转移；指标函数。1 阶段（Stage） 将所给问题的过程，按时间或空间特征分解成若干个相互联系的阶段，以便按次序去求每阶段的解。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量。2 状态（State） 各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状

6、态变量的取值集合称为状态集合，用Sk表示。状态集合可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定。按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1。但为了清楚起见，通常定义阶段的状态即指其初始状态。动态规划中的状态具有如下性质： 当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响。即：过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。3 决策和策略（Decision and Policy）

7、 当各段的状态确定以后，就可以做出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量用xk(Sk)表示，允许决策集合用Dk(Sk)表示。 各个阶段决策确定后，整个问题的决策序列就构成一个策略，用p1,n(x1,x2,xn)表示。对每个实际问题，可供选择的策略有一定的范围，称为允许策略集合，用P表示。使整个问题达到最优效果的策略就是最优策略。4 状态转移方程 动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第k段的状态Sk ，本阶段决策为xk(Sk) ，则第k+1段的状态Sk+1由公式： Sk+1=Tk（ Sk， xk）确定，称为状态转移方程。5 指标函数 用于衡

8、量所选定策略优劣的数量指标称为指标函数v(Sk,xk(Sk)。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。k子过程指标函数Vk,n最优指标函数fk(Sk)动态规划的基本思想： 从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点E最短路线，最后求出A点到E点的最短路线。AB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB

9、C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1

10、D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F41544445333332222AB C DEFAB1B2C1C2C3D1D2D3E1E2F415444453

11、33332222AB C DEF动态规划的函数方程（DP） 建立DP函数方程是指确定过程的阶段及阶段数，规定状态变量和决策变量的取法，给出各阶段的状态集合，允许决策集合，状态转移方程和指标函数等。在上面的计算过程中，利用了第k阶段与第k+1阶段的关系：fk(Sk)= Min r(Sk,dk(Sk)+fk+1(Sk+1) dk(Sk) k=1,2,3,4,5f6(S6)=0 这种递推关系称为动态规划的函数基本方程。贝尔曼(Ballman)最优化原理 作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。这就是说，不管引导到这

12、个现时状态的头一个状态和决策是什么，所有的未来决策应是最优的。动态规划数学模型由最优指标函数递推表达式、边界条件及状态转移方程构成。动态规划的优点：可把一个N维优化问题化成N个一维优化问题求解。DP方程中附加某些约束条件，可使求解更加容易。求得最优解以后，可得所有子问题的最优解。动态规划的缺点：“一个”问题，“一个”模型，“一个”求解方法。且求解技巧要求比较高，没有统一处理方法。状态变量维数不能太高，一般要求小于6。“维数灾难”离散型动态规划连续型动态规划确定型动态规划随机型动态规划动态规划的分类：离散型动态规划应用举例1、开店问题2、一维背包问题3、生产与存储问题4、资源平行分配问题5、非线

13、性分配问题动态规划应用举例例6 一家著名的快餐店计划在某城市建立5个分店，这个城市分成三个区，分别用1，2，3表示。由于每个区的地理位置、交通状况及居民的构成等诸多因素的差异，将对各分店的经营状况产生直接的影响。经营者通过市场调查及咨询后，建立了下表。该表表明了各个区建立不同数目的分店时的利润估计，确定各区建店数目使总利润最大。解：阶段：每个区，共三个阶段。状态：Sk为第k阶段开始时，可供分配的店数。决策：dk为分配给区k的店数。状态转移方程：Sk+1=Sk-dk效益：rk(dk)为分配给区k,dk个店时的利润。fk(Sk)为当第k阶段初始状态为Sk时，从第k阶段到最后阶段所得最大利润。fk(

14、Sk)=Max rk(dk) + fk+1(Sk+1) dk (Sk) k=1，2，3f4(S4)= 0k=3 时， 计算如下：k=2 时， 计算如下：S3=S2-d2k=1 时， 计算如下：最优解：d*1 =3， d*2 =2，d*3 =0即：在区1建3个分店，在区2建2个分店，而不在区3建立分店。最大总利润=22。d1*=3,s2=s1- d1*=5-3=2, d2*=2s3=s2- d2*=2-2=0, d3*=0建立动态规划模型的要点： 分析题意，识别问题的多阶段性，按时间或空间的先后顺序适当地划分满足递推关系的若干阶段，对非时序的静态问题要人为地赋予“时段”的概念。建立动态规划模型的

15、要点： 正确地选择状态变量，使其具备两个必要特征：（1）可知性：即过去演变过程的各阶段状态变量的取值，能直接或间接地确定。（2）能够确切地描述过程的演变且满足无后效性。建立动态规划模型的要点： 根据状态变量与决策变量的含义，正确写出状态转移方程或转移规则。根据题意明确指标函数，最优指标函数以及一段效益即阶段指标的含义。并正确列出最优指标函数的递推关系及边界条件（即 DP基本方程）。生产和存储问题假设某厂生产的某种产品，以后四个月的订单如下表所示，合同规定在月底前交货，生产每批产品的固定成本为3千元，每批生产的产品的数量不限。每件产品的可变成本为1千元，每批产品的最大生产能力为5件。产品每件每月

16、的存储费用为0.5千元。设1月初有库存1件，4月底不再留下产品。试在满足需要的前提下，如何组织生产才能使总的成本费用最低。月份1234订货量3324n=4，状态变量sk（k=1,2,3,4）为每月初的库存，则 s1 =1, s5 =0,决策变量xk，每月生产的产量状态转移方程sk+1 = sk+ xk -bk阶段损益函数d(sk,xk)为各阶段产品的总成本（库存成本+生产成本）模型K=4S4的取值范围s4本阶段费用s5f5(s5)d(s4,x4)+f5(s5)f4(s4)x4生产费用存储费d(s4,x4)043+4070077133+30.56.5006.56.5223+21.06006631

17、3+11.55.5005.55.5400220022最大：S5 = S4+ x4 b4 S4= 5*3+1-(3+3+2)K=3S3的取值范围s3本阶段费用s4f4(s4)d(s3,x3)+f3(s3)f3(s3)x3生产费用存储费d(s3,x3)023+20507121233+30616.512.543+407261353+50835.513.5最大：6 S4= 5*2+1-(3+3)s3本阶段费用s4f4(s4)d(s3,x3)+f4(s4)f3(s3)x3生产费用存储费d(s3,x3)113+10.54.50711.510.523+20.55.516.51233+30.56.52612.

18、543+40.57.535.51353+50.58.54210.5s3本阶段费用s4f4(s4)d(s3,x3)+f4(s4)f3(s3)x3生产费用存储费d(s3,x3)2001.01.0078813+1516.511.523+26261233+3735.512.543+484210s3本阶段费用s4f4(s4)d(s3,x3)+f4(s4)f3(s3)x3生产费用存储费d(s3,x3)3001.51.516.58813+11.55.52611.523+21.56.535.51233+31.57.5429.540022268813+12635.511.523+2274295002.52.53

19、5.58813+12.56.5428.5s2本阶段费用s3f3(s3)d(s2,x2)+f3(s3)f2(s2)x2生产费用存储费d(s2,x2)033+306012181643+407110.517.553+5082816123+20.55.501217.515.533+30.56.5110.51743+40.57.52815.553+50.58.53816.5213+115012171523+216110.516.533+317281543+418381653+5194817s2本阶段费用s3f3(s3)d(s2,x2)+f3(s3)f2(s2)x2生产费用存储费d(s2,x2)3001.

20、51.501213.513.513+11.55.5110.51623+21.56.52814.533+31.57.53815.543+41.58.54816.553+51.59.55817.5s1本阶段费用s2f2(s2)d(s1,x1)+f2(s2)f1(s1)x1生产费用存储费d(s1,x1)123+20.55.501621.521.533+30.56.5115.52243+40.57.521522.553+50.58.5313.522最优解为x1*=2,x2*=5,x3*=0,x4*=4,f1(s1)=21.5存在特别的规律：根据再生点性质，简化求解C(j,i)fi资源平行分配问题假设有

21、某种原材料数量为a，这种材料可以用来生产n种产品，已知生产每种产品所获的收益与所使用的原材料的数量关系为Vi=gi(xi)，其中xi表示用于生产第i种产品的原材料的数量。目标：总收益最大满足的条件背包问题一维“背包”问题例8：有一辆最大货运量为10吨的卡车，用于装载三种货物，每种货物的单位重量及相应单位价值如下，应如何装载可使总价值最大？解：设第i种货物装载的件数为xi(i=1,2,3) 则问题可表示为： max Z=4x1+5x2+6x3 3x1+4x2+5x3 10 xi0且为整数(i=1,2,3)阶段k：第k次装载第k种物品（k=1,2,n）状态变量Sk：假设Sk为第k阶段到第3阶段背包

22、中装入物品的重量，决策变量dk：第k次装载第k种物品的件数决策允许集合：Dk(sk)=dk|0 xksk/wk，xk为整数状态转移方程：Sk+1=Skwkxk阶段指标：rk=ckxkK=3时 x36x3012f3(s3)x3000010002000300040005066160661706618066190661100612122s35x2 +f3(s2-4x2)012f2(s2)x200001000200030004055156560665607656086560961111110121110120 x2s2K=2时 x14x1+f2(s1-3x1)0123f1(s1)x1000010002

23、00030441454505646066488276488286108101911108121231012101312132s1可推得全部策略为：x1*=2，x2*=1， x3*=0，最大价值为13。二维“背包”问题例9：有一辆最大货运量为12吨，最大容量10立方米的某种类型卡车，用于装载两种货物A、B，每种货物的单件重量分别3吨、4吨，体积为1立方米、5立方米，价值为2、3，求合理装载的最大效益？解：设A、B货物装载的件数为 xi(i=1,2) 则问题可表示为： max Z=2x1+3x2 3x1+4x2 12 x1+5x2 10 xi 0整数 (i=1,2)阶段k：第k次装载第k种物品（k

24、=1,2,n）状态变量Sk：假设Sk为第k阶段到第3阶段背包中装入物品的重量和体积，决策变量dk：第k次装载第k种物品的件数决策允许集合：Dk(sk)=dk|0 xksk,1/wk，0 xksk,2/ak, xk为整数状态转移方程：Sk+1,1=Sk,1wkxk， Sk+1,2=Sk,2akxk阶段指标：rk=ckxk资金分配问题某建筑公司拟建造甲乙丙三类住宅出售，甲类住宅每栋耗费100万元，售价200万元，乙类住宅每栋耗资60万元，售价110万元，丙类住宅每栋耗资30万元，售价70万元。由于某种限制，建造每类住宅不得超过3栋。该公司拥有建房资金350万元，问应当如何安排资金可使该公司的住房收

25、益最大。max Z=100 x1+50 x2+40 x3 100 x1+60 x2+30 x3 350 x1 3， x2 3， x3 3， xi0且为整数 (i=1,2,3)阶段:将甲乙丙三种住宅的建造计划视为3个阶段，第一阶段建造甲，第二阶段建造乙，第三阶段建造丙状态变量：sk表示阶段k公司所拥有的资金的数量决策变量： xk表示阶段k公司建造的数量状态转移方程：s2=s1-100 x1， s3=s2-60 x2，s1=350允许决策的集合D3(s3)=0,1,2,min3,s3/30 D2(s2)=0,1,2,min3,s2/60, D1(s1)=0,1,2,min3,s1/100最大收益f

26、k(sk)表示当第k阶段拥有的资金为sk时从第k到第3阶段获得的最大收益 x340 x3f3(s3)x3s4=s3-30 x301230-200000-2030-500404010-2060-80040808020-2090-3500408012012030-260s3K=3D3(s3)=0,1,2,min3,s3/30 x250 x2 + f3(s3)f2(s2)x2s3=s2-60 x201230-200000-2030-500+4040030-5060-800+805080060-8090-1100+12050+40120090-110120-1400+12050+80100+01301

27、60-80150-1700+12050+120100+40170190-110180-2000+12050+120100+80150180260-80210-2300+12050+120100+120150+40220290-110240-2600+12050+120100+120150+80230360-80270-3500+12050+120100+120150+120270390-110s2K=2D2(s2)=0,1,2,min3,s2/60=0.1.2.3,K=1D1(s1)=0,1,2,min3,350/100= 0,1,2,3 x1100 x1+f2(s2)f1(s1)x1s2=s

28、1-100 x101233500+270100+230200+170300+403702150s1总获利370万元90设 备 更 新 问 题在企业中，经常遇到设备陈旧或部分损坏需要更新的问题。从经济上分析，一种设备应该使用多少年后进行更新最合算。这就是要研究的问题。 一台设备的价格为P，运行寿命为m年，每年的维修费用是设备役龄t的函数，记为C(t)；旧设备出售的价格也是设备役龄t的函数，记为S(t)。新设备的役龄为0。现要用该种设备进行为期n年的生产，在n年末，役龄为t的设备残值为R(t)。在n年的生产过程开始时，有一台役龄为T的设备；以后每年都会面临“继续使用”或“更新”的决策。设备更新问题

29、设具体数据如下：设备更新问题对于 k = 6： f6(t6) =-R(t6)f6(1) = -25,f6(2) = -17,f6(3) = -8,f6(4) = 0,f6(5) = 0,f6(6) = 0,f6(7) = 0对于 k = 5：对于 k = 4：对于 k = 3：对于 k = 2：对于 k = 1： 两个最优策略 设备更新问题由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。110旅行售货员问题Traveling Salesman Problem 设有n个城镇，城镇i到城镇j的距离为dij，现求从城镇1出发，经各城镇一次且仅一次，最后返回城镇1的最短路线。旅行售货员问题/货郎担问题AEDCB252755610.53阶段设S表示从城镇1出发，目前到达某个城镇前经过的城镇（不包括城镇1和目前到达的城镇）。 第k阶段为经过城镇的个数为k个，即S中元素个数为k个。 k = 0, 1, , n-1。状态变量第k阶段状态变量(i, S)：从城镇1出发，经