动态规划(生产和存储问题)

1、动态规划（生产和存储问题）一、动态规划法的发展及其研究内容 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家 R.E.BELLMAN等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原 理，把多阶段问题转化为一系列的单阶段问题，逐个求解 创立了解决这类过程优化问题的新方法动态规划。 1957 年出版的他的名著 Dynamic Proggramming ，这是该领域 的第一本著作。动态规划问世以来，在经济管理生产调度工程技术和最优控制等方面得到了广泛的应用。例如最短路线库存 管理资源分配设备更新组合排序装载等问题，采 用动态规划法求解比用其他方法更为

2、简便。二、动态规划法基本概念一个多阶段决策过程最优化问题的动态规划模型通常包 括以下几个要素：1 阶段阶段（ stage ）是对整个过程的自然划分。通常根据时间顺 序或是空间特征来划分阶段，对于与时间，空间无关的“静 态”优化问题，可以根据其自然特征，人为的赋予“时段” 概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用 k=1.2.n.表示。1. 状态状态 (state) 是我们所研究的问题(也叫系统)在过 个阶段的初始状态或客观条件。 它应能描述过程的特征并 且具有无后效性， 即当某阶段的状态给定时， 这个阶段以 后的过程的演变与该阶段以前各阶段的状态无关。 通常还 要求状

3、态是可以直接或者是间接可以观测的。 描述状态的 变量称为状态变量( State Virable )用 s 表示，状态变 量的取值集合称为状态集合， 用 S 表示。变量允许取值的 范围称为允许状态集合 (set of admissble states). 用 x(k) 表示第 k 阶段的状态变量， 它可以是一个数或者是一 个向量。用 X(k) 表示第 k 阶段的允许状态集合。n 个阶段的决策过程有 n+1 个状态变量， x(n+1) 是 x(n) 的演变的结果。根据演变过程的具体情况， 状态变量可以是离散的或 是连续的。 为了计算方便有时将连续变量离散化， 为了分 析的方便有时又将离散的变量视为

4、连续的。2 决策 当一个阶段的状态确定后， 可以做出各种选择从而演变 到下一阶段的某个状态，这种选择手段称为决策 (decision )，在最优控制问题中也称为控制 ( control ) 描述决策的变量称为决策变量( decision virable )。 变 量 允 许 取 值 的 范 围 称 为 允 许 决 策 集 合 ( set of admissble decisions )。用(*()表示第 k 阶段处于 阶段x(k)的决策变量，它是x(k)的函数，用 仏(丫(約) 表示x(k)的允许决策集合决策变量简称决策。 亦讹)e亿(期)。4. 策略决策组成的系列称为策略(policy )。

5、由初始状态 x1开始的全过程的策略记作尸ln(X(l).人心)-M(t(1)S(x(2),A ,”(*().由第k阶段的状态x(k)开始到终止状态的后部子 过程的策略耳w),=；k=2,n-1.可供选择的策略有一定的范围，称为允许策略集合(set of admissble polices ),用 &),4f) 等表示。5. 状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知， 下阶段的状态偏完全可以确定。用状态转移方程(state transfer equations )表示这种演变规律，写作：十1)二 7 (x(叫(心) k=l26. 阶段指标函数对于k阶段的状态x（k），当执行了决策

6、时， 除带来系统状态的转移之外，还产生第k阶段的局部利 益，它是总效益的一部分，称为阶段指标函数（ stage effective fuction），记作几（兀）.7. 过程指标函数用来衡量策略或者是子策略执行效果的数量指标称为过程指标函数（process effective fuction ），它定义在所有k后部子过程上，常用用 人表示，即Vk =（巩&）我 +1）仏 + 1）、人，巩必叫（兀0）k=1,2，,n.当k=1时，就是全过程指标函数。如果状态x（k）和子策略耳”（巩斤）给定，那么几也就被确定了，所以久是x（k）和心（巩斤）的函数，记为：几=汗（如片陀）常见的过程指标函数是连和形式

7、或连积形式：Vk =乞匚（曲）已（4）川二12八11=EkW）（E）* = 】2A ,帆7=A*8. 最优指标函数过程指标函数*W n 的最优值称为最优指标函数(optimum effective fuction ),记为 f(x(k).米取了 最优子策略5 m：之后，后部子过程所获得的总效益，表示为:.m = optvk(x(Q Ph(x伙)/ = 1.2.A JLopt是optimization的缩写，意为最优化，可以根据具体问题去max或min三动态规划法的最优性原理和基本函数方程在动态规划中起核心作用的是最优性原理：“作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如 何，相

8、对于前面决策所形成的状态而言，余下的决策系列必 须构成最优子策略。”动态规划解法的关键在于给出一种递推关系，一般把这种关系称为基本函数方程，耳（x（你巴Q） = （讹）心（讹） + +】（刑+1）/卜“（x（約） 注意到无后效性，最优指标函数为/（貫）=僻；（讹人丘仕）-optr, (x(k 叫(讹)+ F；+l gk +1), gk + 1)=約“ (*)+ opt VMx(k i 1)出讹 + I)“JtUHJ-卿WQr心Qr依)+/(巩斤+1)当k=n时，由于x(n+1)是整个决策过程的终止状态，以后不再做出决策，因此，州(巩+1)(这样就得到了可以用来递推的基本函数方程：= op/rk

9、(x(k)jfkSAky)-f(x(k +1), k丄f(x(n+1)=0.类似的，可以得到乘法形式的基本函数方程：= optrk (x(Ar),) f (x(k +1), k =f(x(n+1)=1.四、建立动态规划模型的基本步骤1. 阶段；2. 状态变量及可能状态集合；3. 决策变量及允许决策集合；4. 状态转移方程；5. 阶段指数函数；6. 基本函数方程；建立动态规划模型基本上是上面6个步骤，按上述顺序逐步确定16的内容。五、动态规划法的递推方向及求解形式1.递推解法基本方程：f(x(n+1)=0状态转移方程为r(A +1) = 7(x(A),t-r() * k h、h 1,A 丄计算步

10、骤是，利用终端条件从 k=n开始由后向前递推基本方 程，求得各阶段的最优决策和最优函数，最后算出f(x(1)时就得到了最优决策系列你(6工匚X* 12人”:再按照状态转移方程* *側+ 12住(灯冲(购)从k=i开始确定g序列讥),k=1,2,n为最优轨迹线， x(k), k -1,2,A 为最优策略2顺推解法使用顺推解法时，一些概念的含义须做相应调整。状态变量x(k)表示第k阶段末系统的形态状况，最优值函 数f(x(k)表示从第一阶段到第k阶段总效益的最优值，状态转移方程为x(k -1) =(x(A) * k = 12 A基本函数方程为- opt rk (x(kuk(x(A) + fxk -

11、 I), k = 1,2.A mf(x(0)=0 或 13. 求解形式 求解动态规划问题， 一般有两种形式： 解析形式和表格形式， 解析形式是利用函数的解析表达式，在每个阶段用经典求极 值的方法得到最优解。表格形式是指各阶段的计算过程均在 表格中进行，这种形式便于分析和比较，操作过程直观且简 练，适用于没有解析表达式的离散型问题。4. 动态规划的适用条件 适用动态规划的问题通常应满足如下 3 点：CD最优化原理（最优子结构性质）。如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构性质， 即满足最优化原理。由于对于有些问题的某些递归式来讲并 不一定能保证最优化原则，因此在求解

12、问题时有必要对它进 行验证。若不能保持最优原则，则不可以应用动态规划法求 解。在得到最优解的递归式之后，需要执行回溯以构造最优 解。C2 无后效性。应用动态规划法的一个重要条件就是将各阶段 按照一定的次序排好，阶段 i 的状态只能由阶段 i+1 的状态 来确定，与其他状态没有关系，尤其是于未发生的状态没有 关系。 换言之， 每个状态都是 “过去历史的一个完整总结” 。 这就是无后效性。C3 子问题的重叠性。子问题的重叠性是指在利用递归算法自 顶向下对问题进行求解时，每次产生的问题并不总是新问题，有些子问题可能会被重复计算多次。动态规划法正是利用子问题的这种重叠性质，对每一个问题只计算一次，然后

13、将其 计算结果保持起来，当再次需要计算已经计算过的子问题时， 只要简单的查看一下以往的计算结果，从而获得较高的解题 效率。子问题的的重叠性并不是动态规划适用的必要条件，但是如 果该性质无法满足，动态规划算法同其他算法相比就无优势 可言了。5. 解决问题的步骤 利用动态规划法求解问题的算法通常包含如下几个步骤。 分析。对原始的问题进行分析，找到问题的最优解的结构 特征。 分解。将所给问题按时间或空间特征分解成相互关联的阶段，并确定出计算局部最优解的递推关系，这是利用动态规 划法解决问题的关键和难点所在。需要注意的是，分解后的 各个阶段一定是有序的或者是可以排序的，即无后向性。否 则问题就无法用动

14、态规划求解。阶段之间相互联系方式是通过状态和状态转移体现的。每个 阶段通常包含若干个状态，可以描述问题发展到这个阶段时 所处在的一种客观情况。每个阶段的状态都由以前阶段的状 态以某种方式 “变化” 来的， 这样的“变化”称为状态转移 状态转移是导出状态的途径，也是联系各阶段的方式。 解决。对于每个阶段通过自底向上的方法求得局部最优解。由于这一步骤通常是通过递推实现的，因此，需要递推终止 条件或边界条件。合并。将各个阶段求出的解合并为原问题的解，即构造一 个最优解。动态规划的主要难点在于理论的设计，特别是递推关系的建 立，一旦设计完成，实现部分就会非常简单。整个求解过程 就可以使用一个最优决策表

15、的二维数组来描述，其中行表示 决策的阶段，列表示问题状态，表格需要填写的数据一般对 应此问题的在某阶段某个状态下的最优值，如最短路径，最 长公共子序列，最大价值等。填表的过程就是根据递推关系 从 1 行 1 列开始，以行或者列优先的顺序，依次填写表格。 最后根据整个表格的数据通过简单的取舍或者运算求得问 题的最优解。总之，动态规划算法的关键在于解决冗余，是一个以空 间换时间的技术，所以它的空间复杂度要大于其他的算法。六、动态规划问题在问题中的具体实现 例如：动态规划规划在生产存储中的运用生产 存储问题是生产活动中经常遇到的问题。大批量生 产可以降低成本，但当产量大于销量时就会造成产品积压而 增

16、加库存费用；单纯按市场要求安排生产也会因为开工不足或加班加点造成生产成本增加。因此合理利用存贮资源调节 产量，满足要求是十分有意义的。生产与存贮问题是一个生 产部门如何在已知生产成本，存贮费用和各阶段市场要求的 条件下，决定各个生产阶段的产量，使得计划期内的费用之 和最小。现设有一个生产部门，生产计划周期为n个阶段，已知最初库存量为x1，阶段需求量为 dk，单位产品的消耗费用是Ik，单位产品的阶段库存费用为hk，仓库容量为 mk阶段生产能力为bk，生产固定成本为产量=o 产量0问如何安排现阶段的产量，使计划期内的费用综合为最小？该问题本身就是一个多阶段决策问题，设状态变量为xk为k阶段初的库存

17、量，由于计划期初的库存量x1已知，计划期末的库存量通常也是给定的，为简单起见，假定x(n+1)=0 ，于是状态变量 xk 的约束条件是：0 M+ 屮 + 十乩 M = 1 总决策变量uk选为阶段k的产量，它满足的约束条件是：0无 中黑min( 心十况屮一十山一,叮* 冲十必显=1 -*n状态转移方程为 丫宀/，它满足无后效性 的要求。阶段效用由两阶段组成，一部分为生产费用，另一部分为存贮费用，即:0 -h （ 嗾 H 0 nR =为匚（九鼻如）i -=i动态规划基本方程为：兔1乩）+卉门（丁屮）叫0AtjCk） = mint-j la +曲 + 野一必）+ jt+i （x*4i ）0七、设计题

18、目：某机床厂根据合同，在一至四月份为客户生产某种机床。工厂每月的生产能力为10台，机床可以库存，存储费用为每台每月0.2万元，每月需要的数量及每台机床的生产成本如下表。试确定每月的生产量，要求既能满足每月的需求，又能使生产成本和存储费用之和达到最小。表需求量及生产成本月份1234需求（台）67126生产成本（万元/台）77.287.61.构造动态规划模型 阶段变量k把每个月作为一个阶段，k=1,2,3,4 状态变量耳选择每个阶段的库存量为状态变量,可满足无后效性，由已知条件可知：x仁x5=0，单位为台 决策变量设每个阶段的生产量为决策变量，由已知条件得0） i=1,2,3,4.或厂（可，叫）=

19、0.2+0（叫=0）其中 y1=7, y2=7.2 , y3=8, y4=7.6，单位为万元2. 建立基本方程设最优值函数是从第k阶段的亞 状态出发到过程终结的最小费用，按动态规划方法的逆序解基本方程又： 屁八即山（叫，巧+九心小（k=4,3,2,1 ）F5（x5）=03. 逆序逆推计算 k=4 时按照问题的各种约束条件，确定状态变量x4的取值范围。按穷举法的思路，在量化的精度内，确定状态变量x4的全部可能取值。状态转移方程x5=x4+u4-d4又 x5=0 , d4=6 所以有 x4+u4=6又因为每个月的最大生产能力为10台。第1, 2, 3月的需求量为 6, 7, 12 台，故 x4=0

20、, 1, 2, 3, 4, 4 台对x4的的确定取值，分别求出决策变量u4的取值范围当 x4=0, u4=6;x4=3,u4=3x4=1, u4=5;x4=4, u4=2x4=2, u4=4;x4=5, u4=1由此可知x4与u4是一一对应的，即对于每个确定的状态， 只有一种决策，故这唯一决策的结果是最优的。利用第四阶段的基本方程进行计算：F4(x4)=minv4(x4,u4)+f5(x5)=minv4(x4,u4)=v4(x4,u4)=0.2x4+7.6u4 (u40) 或=0.2x4( u4=0)计算结果列表 1表1k=4 时8工*+ ir +九卜】(丁时1)06045.6045.6150

21、38.2038.224030.8030.833023.4023.4420160165108.608.6k=3时因为d3=12, d4=6, x仁x5=0 , d仁7.每月的最大生产能力为10台，故2三x3三7当 x3=2 , u3=10x3=3，u3=10， 9x3=4，u3=10， 9， 8x3=5，u3=10， 9，8， 7x3=6，u3=10， 9，8， 7，6x3=7，u3=10， 9， 8， 7， 6， 5状态变量x3的一个取值，对应决策变量u3的六个可能取值， 要求分别计算出各个u3取值相应的指标函数值，再挑选其中的最小值为这个状态的最优指标函数值，f3(0).下面利用第三阶段的基

22、本方程进行计算。F3( x3)=min【v3(x3,u3)+f4(x4)】其中 v3(x3,u3)=0.2x3+8u3(u30)或 v3(x3,u3)=0.2x3 (u3=0)状态转移方程x4=x3+u3-12 计算结果位于表2表2表2 k=3 时叫i兀JI扎+i (工卄ir; +几心中210080.445.6126310180.638.2118.89072.645.6118.2410280.830.8111.69172.838.21118064.845.6110.451038123.4104.4927330.8103.8816538.2103.2705745.6102.6610481.216

23、97.29373.223.496.68265.230.8967157.238.295.46049.245.694.8710581.48.6909473.41689.48365.423.488.87257.430.888.26149.438.287.65041.445.687 k=2 时确定x2的取值范围因为x仁0 , 0三u1 10,且d仁6,且x3三2因此 0 三 x2 三 4 即 x2=0,1,2,3,4.对于x2的每个确定值，分别求出u2的可能取值X2=0 时，u2=10， 9X2=1 时，u2=10， 9， 8X2=2 时，u2=10， 9， 8， 7X2=3 时，u2=10， 9，

24、8， 7， 6X2=4 时，u2=10， 9， 8， 7， 6， 5基本方程f2(x2)=minv2(x2,u2)+f3(x3)其中 v2(x2,u2)=0.2x2+7.2u2 (u20) 或 v2(x2,u2)=0.2x2(u2=0)状态方程x3=x2+u2-3注：对上面的u2取值解释。本来x2=0时，u2可取值为10，9，8，7.但由于每个月的最大生产能力为10台且d3=12，所以x3必须大于2台，因此u2取值只能为10，9.同理对于x3取其他可能值，也应考虑到x3必须大于2台，计算结果如下表3.表 3 k=2%工屮忖+t+i (+-1)010372118.2190.29264.8126190.8110472.2110.4182.69365118.2183.28257.8126183.6210572.4102.61759465.2110.4175.68358118.2176.27250.8126176.8310672.694.8167.49565.4102.61688458