1、动态规划生产和存储问题 动态规划（生产和存储问题） 一、动态规划法的发展及其研究内容 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.BELLMAN等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解 创立了解决这类过程优化问题的新方法动态规划。1957年出版的他的名著Dynamic Proggramming，这是该领域的第一本著作。 动态规划问世以来，在经济管理生产调度工程技术和最优控制等方面得到了广泛的应用。例如最短路线库存管理资源分配设备更新组合排序装载等问题，采用动态规划法求解比用其
2、他方法更为简便。 二、动态规划法基本概念 一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素： 1 阶段 阶段（stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。 表示。.n.k=1.2阶段变量一般用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)的演变的结果。 根据演变过程的具体情况，状态变量可以是离散的或是连续的。为了计算方便有时将连续变量离散化，为了分析的方便有时又将离散的变量视为连续的。 2 决策 当一个阶段的状态确定后，可以做出各种选择从而演变到下一
4、阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）描述决策的变量称为决策变量（decision virable）。of set （合集策决许允为称围范的值取许允量变 阶段处于k。用表示第admissble decisions） 的函数，用x(k)的决策变量，它是x(k)阶段。决策变量简称合示表x(k)的允许决策集决策 。 4.策略。由初始状态决策组成的系列称为策略（policy） . x1开始的全过程的策略记作 . 开始到终止状态的后部子k由第阶段的状态x(k) , 过程的策略 ,n-;k=2,1. 称为允许策略集合可供选择的策略有一定的范围
5、， , 用,polices（set of admissble ） 等表示。 5.状态转移方程一旦某阶段的状态和决策为已知，在确定性过程中，state 下阶段的状态偏完全可以确定。（用状态转移方程 transfer equations）表示这种演变规律，写作： 阶段指标函数6. 时，当执行了决策x(k)，对于k阶段的状态阶段的局部利k除带来系统状态的转移之外，还产生第stage 益，它是总效益的一部分，称为阶段指标函数（ . ，记作effective fuction） 7.过程指标函数用来衡量策略或者是子策略执行效果的数量指标称为，它定义在所过程指标函数（process effective fu
6、ction） 后部子过程上，常用用表示，即有k ,n. k=1,2, 时，就是全过程指标函数。当k=1 也就被和子策略那么给定，如果状态x(k) 的函数，记为：确定了，所以是x(k)和 常见的过程指标函数是连和 形式或连积形式： 8.最优指标函数 的最优值称为过程指标函数f(x(k).，记为）fuctioneffective (optimum 最优指标函数它表示，采取了最优子策略 之后，后部子过程所获 得的总效益，表示为： 中式可以根据具体问意为最优化，optimizationopt是的缩写，min 或题去max 三动态规划法的最优性原理和基本函数方程“作为整个在动态规划中起核心作用的是最优性
7、原理：过程的最优策略具有这样的性质，无论过去的状态和决策如何，相对于前面决策所形成的状态而言，余下的决策系列必 须构成最优子策略。”动态规划解法的关键在于给出一种递推关系，一般把 这种关系称为基本函数方程， 注意到无后效性，最优指标函数为 以后不x(n+1)是整个决策过程的终止状态，当k=n时，由于 再做出决策，因此， 这样就得到了可以用来递推的基本函数方程： f(x(n+1)=0. 类似的，可以得到乘法形式的基本函数方程： f(x(n+1)=1. 四、建立动态规划模型的基本步骤 阶段；1. 2. 状态变量及可能状态集合； 3. 决策变量及允许决策集合； 状态转移方程；4. 阶段指数函数；5.
8、 基本函数方程；6. 个步骤，按上述顺序逐步建立动态规划模型基本上是上面6 16确定的内容。 五、动态规划法的递推方向及求解形式 1.递推解法 基本方程： f(x(n+1)=0 状态转移方程为 开始由后向前递推基本方计算步骤是，利用终端条件从k=nf(x(1)程，求得各阶段的最优决策和最优函数，最后算出 时就得到了最优决策系列 程态转移方再按照状 定始确从k=1开 ，最优线轨迹,n，k=1,2,为 为最优策略。 顺推解法2. 使用顺推解法时，一些概念的含义须做相应调整。最优值函状态变量x(k)表示第k阶段末系统的形态状况，阶段总效益的最优值，状f(x(k)数表示从第一阶段到第k 态转移方程为
9、基本函数方程为 1 或f(x(0)=03. 求解形式 求解动态规划问题，一般有两种形式：解析形式和表格形式，解析形式是利用函数的解析表达式，在每个阶段用经典求极值的方法得到最优解。表格形式是指各阶段的计算过程均在表格中进行，这种形式便于分析和比较，操作过程直观且简练，适用于没有解析表达式的离散型问题。 4.动态规划的适用条件 适用动态规划的问题通常应满足如下3点： 1最优化原理(最优子结构性质)。如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构性质，即满足最优化原理。由于对于有些问题的某些递归式来讲并不一定能保证最优化原则，因此在求解问题时有必要对它进行验证。若不能保持最
10、优原则，则不可以应用动态规划法求解。在得到最优解的递归式之后，需要执行回溯以构造最优解。 2无后效性。应用动态规划法的一个重要条件就是将各阶段按照一定的次序排好，阶段i的状态只能由阶段i+1的状态来确定，与其他状态没有关系，尤其是于未发生的状态没有关系。换言之，每个状态都是“过去历史的一个完整总结”。这就是无后效性。 3子问题的重叠性。子问题的重叠性是指在利用递归算法自顶向下对问题进行求解时，每次产生的问题并不总是新问题，有些子问题可能会被重复计算多次。动态规划法正是利用子问题的这种重叠性质，对每一个问题只计算一次，然后将其计算结果保持起来，当再次需要计算已经计算过的子问题时，只要简单的查看一
11、下以往的计算结果，从而获得较高的解题效率。 子问题的的重叠性并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就无优势可言了。 5.解决问题的步骤 利用动态规划法求解问题的算法通常包含如下几个步骤。 1分析。对原始的问题进行分析，找到问题的最优解的结构特征。 2分解。将所给问题按时间或空间特征分解成相互关联的阶段，并确定出计算局部最优解的递推关系，这是利用动态规划法解决问题的关键和难点所在。需要注意的是，分解后的各个阶段一定是有序的或者是可以排序的，即无后向性。否则问题就无法用动态规划求解。 阶段之间相互联系方式是通过状态和状态转移体现的。每个阶段通常包含若干个状
12、态，可以描述问题发展到这个阶段时所处在的一种客观情况。每个阶段的状态都由以前阶段的状态以某种方式“变化”来的，这样的“变化”称为状态转移。 状态转移是导出状态的途径，也是联系各阶段的方式。3解决。对于每个阶段通过自底向上的方法求得局部最优解。由于这一步骤通常是通过递推实现的，因此，需要递推终止条件或边界条件。 4合并。将各个阶段求出的解合并为原问题的解，即构造一个最优解。 动态规划的主要难点在于理论的设计，特别是递推关系的建立，一旦设计完成，实现部分就会非常简单。整个求解过程就可以使用一个最优决策表的二维数组来描述，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某阶
13、段某个状态下的最优值，如最短路径，最长公共子序列，最大价值等。填表的过程就是根据递推关系从1行1列开始，以行或者列优先的顺序，依次填写表格。最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。 总之，动态规划算法的关键在于解决冗余，是一个以空间换时间的技术，所以它的空间复杂度要大于其他的算法。 六、动态规划问题在问题中的具体实现 例如： 动态规划规划在生产存储中的运用 生产 存储问题是生产活动中经常遇到的问题。大批量生产可以降低成本，但当产量大于销量时就会造成产品积压而增加库存费用；单纯按市场要求安排生产也会因为开工不足或加班加点造成生产成本增加。因此合理利用存贮资源调节产量，满足要
14、求是十分有意义的。生产与存贮问题是一个生产部门如何在已知生产成本，存贮费用和各阶段市场要求的条件下，决定各个生产阶段的产量，使得计划期内的费用之和最小。 现设有一个生产部门，生产计划周期为n个阶段，已知最初库存量为x1，阶段需求量为dk，单位产品的消耗费用是lk，单位产品的阶段库存费用为hk，仓库容量为mk，阶段 问如何安排，生产固定成本为生产能力为bk 现阶段的产量，使计划期内的费用综合为最小？xk该问题本身就是一个多阶段决策问题，设状态变量为已知，计x1为k阶段初的库存量，由于计划期初的库存量）n+1x（为简单起见，划期末的库存量通常也是给定的，假定：是束条件约变于=0，是状态量xk的 的
15、产量，它满足的约束条件是：uk决策变量选为阶段k ，它满足无后效性状态转移方程为 的要求。阶段效用由两阶段组成，一部分为生产费用，另一部分 为存贮费用，即： 动态规划基本方程为： 七、设计题目： 某机床厂根据合同，在一至四月份为客户生产某种机床。工厂每月的0.2存储费用为每台每月10台，机床可以库存，生产能力为万元，每月需要的数量及每台机床的生产成本如下表。试确定每月的生产量，要求既能满足每月的需求，又能使生产成 本和存储费用之和达到最小。 表 需求量及生产成本 4 3 1 月份 2 6 12 7 需求（台）6 7.6 8 生产成本（万元/台）7 7.2 1.构造动态规划模型1k 阶段变量k=
16、1,2,3,4 把每个月作为一个阶段， 2 状态变量 选择每个阶段的库存量为状态变量，可满足无后效性，由已知条件可知：x1=x5=0，单位为台 3 决策变量 设每个阶段的生产量为决策变量由已知条件得0， 10台，4状态转移方程 阶段的市k-（是第=状态转移方程为：+ 场需求量） 5 阶段指标 第k阶段的指标费用： i=1,2,3,4. ）,（=0.2+y(i)（0） （+0 ）=0.2=0）或（ , ，y2=7.2，y3=8y4=7.6，单位为万元，其中y1=7 建立基本方程2. 状态出发到过程终k是从第阶段的设最优值函数 结的最小费用，按动态规划方法的逆序解基本方程又： ）k=4,3,2,1
17、（ )+,(F5(x5)=0 逆序逆推计算 3.1时k=4 的取值范围。按照问题的各种约束条件，确定状态变量x4的全按穷举法的思路，在量化的精度内，确定状态变量x4 x5=x4+u4-d4 部可能取值。状态转移方程x4+u4=6 所以有又x5=0，d4=6 月的需3又因为每个月的最大生产能力为10台。第1，2， 3，4，4台16求量为，7，12台，故x4=0，2，2 的取值范围x4的的确定取值，分别求出决策变量u4对u4=6;x4=3,u4=3 ，当x4=0x4=1, u4=5; x4=4, u4=2 x4=2, u4=4; x4=5, u4=1 是一一对应的，即对于每个确定的状态，x4与u4
18、由此可知 只有一种决策，故这唯一决策的结果是最优的。 利用第四阶段的基本方程进行计算：F4(x4)=minv4(x4,u4)+f5(x5) =minv4(x4,u4) =v4(x4,u4) 1 ）计算结果列表（=0.2x4+7.6u4 (u40)或=0.2x4 u4=0 时表1 k=4 + 45.6 6 0 0 0 45.6 38.2 38.2 5 0 1 0 30.8 0 0 4 30.8 2 23.4 23.4 0 3 0 3 16 0 16 0 2 4 8.6 0 8.6 0 1 5 2k=3时 每月的最大生产能力为，d1=7.因为d3=12，d4=6，x1=x5=07 x310台，故2
19、u3=10 ，当x3=29 ，x3=3，u3=108 ，x3=4，u3=10，97 ，u3=10，9，8，x3=56 97，8，x3=6，u3=10，5 67，u3=10x3=7，9，8，的六个可能取值，的一个取值，对应决策变量u3状态变量x3取值相应的指标函数值，再挑选其要求分别计算出各个u3f3(0). 中的最小值为这个状态的最优指标函数值， 下面利用第三阶段的基本方程进行计算。 】F3（x3）=min【v3(x3,u3)+f4(x4)v3(x3,u3)=0.2x3 其中v3(x3,u3)=0.2x3+8u3 (u30)或(u3=0) 2 x4=x3+u3-12 计算结果位于表状态转移方程
20、 2 k=32表时表 + 126 10 45.6 0 2 80.4 118.8 1 3 10 38.2 80.6 118.2 45.6 72.6 0 9 4 10 2 80.8 30.8 111.6 111 1 38.2 72.8 9 110.4 64.8 0 45.6 8 104.4 81 3 5 10 9 2 103.8 73 8 103.2 65 1 7 102.6 57 0 6 97.2 81.2 4 10 9 73.2 96.6 3 8 96 2 65.2 7 95.4 1 57.2 6 0 94.8 49.2 7 90 5 10 81.4 9 4 89.4 73.4 8 88.8
21、65.4 3 7 57.4 2 88.2 6 1 87.6 49.4 5 87 0 41.4 23.4 30.8 38.2 45.6 16 23.4 30.8 38.2 45.6 8.6 16 23.4 30.8 38.2 45.6 3k=2时 确定x2的取值范围 因为x1=0，0u110，且d1=6，且x32 x2=0,1,2,3,4. 即4 x20因此 u2的可能取值对于x2的每个确定值，分别求出9 u2=10，X2=0时，8 ，X2=1时，u2=1097 ，X2=2时，u2=10，9，86 ，u2=109，8，7，X2=3时，5 8，6，7，X2=4时，u2=10，9，f2(x2)=mi
22、nv2(x2,u2)+f3(x3) 基本方程v2(x2,u2)=0.2x2 或v2(x2,u2)=0.2x2+7.2u2 (u20)其中 ）（u2=0x3=x2+u2-3 状态方程 注：对上面的u2取值解释。7. 8，u2本来 x2=0时，可取值为10，9，必x3但由于每个月的最大生产能力为10台且d3=12，所以9. 须大于2台，因此u2取值只能为10，台，2必须大于x3取其他可能值，也应考虑到x3同理对于3. 计算结果如下表3 k=2 表 + 0 10 3 72 118.2 190.2 9 2 64.8 126 190.8 10 1 4 72.2 110.4 182.6 9 3 65 11
23、8.2 183.2 183.6 57.8 126 8 2 175 72.4 2 10 5 102.6 175.6 65.2 9 4 110.4 176.2 3 58 8 176.8 2 7 50.8 167.4 3 10 6 72.6 168 5 65.4 9 168.6 58.2 4 8 169.2 7 51 169.8 43.8 6 159.8 72.8 10 4 160.4 65.6 9 8 58.4 51.2 7 6 5 118.2 126 94.8 102.6 110.4 118.2 126 87 94.8 102.6 110.4 118.2 126 3 2 7 6 5 4 3 2
24、161 161.6 162.2 162.8 44 36.8 4k=1时 确定x1的取值范围 X1=0 确定u1的取值范围 10 u16。故x1=0，d1=6因为6 ，所以u1=10，9，87f1(x1)=minv1(x1,u1)+f2(x2) 基本方程 ）v1(x1,u1)=x1+7u1 （u10）或v1(x1,u1)=x1 （u1=0其中x2=x1+u1-6 状态转移方程： 计算结果列于下表4中：4 k=1 表 + 0 10 4 70 159.8 229.8 9 0 3 63 167.4 230.4 8 0 2 56 175 231 7 0 1 49 182.6 231.6 6 0 0 42
25、 190.2 232.2 5求全过程最优指标函数与最优化策略 由k=1.可以求出其全过程最优指标函数f1(x1)；由k=1至k=4各表，可以依次求出第1，2，3，4各阶段的最优策略，进而得到最优策略。由表1可知。在年初无库存的情况下，四个月的最小费用f1(0)为229.8万元。且第一阶段的最优决策u1=10台，第一阶段末即第二阶段初的最优库存x2=4台。 根据x2=4台查表3可知，第二阶段的最优决策u2=10台，因此库存x3=7台。 台，因u3=5得，第三阶段的最优决策2台，查表x3=7根据此x4=0台，查表1得u4=6台。这样到最后一个月恰好无库存，即x5=0。 综上所述，该生产与存储问题的最优化安排是： 第1个月生产10台，费用为70万元； 第2个月生产10台，费用为72.8万元； 第3个月生产5台，费用为41.4万元； 第4个月生产6台，费用为45.6万元。 一至四月的生产与存储费用最小为229.8万元。
