动态规划的应用.docx

动态规划的应用 【摘 要】本文的主要内容是求解决策过程最优化的数学方法动态规划。动态规划问世以来，在经济管理、生产调度、工程技术和最优限制等方面得到了广泛的应用，用动态规划方法比用其它方法求解更为便利。本文主要探讨动态规划的资源安排问题和设备更新问题，所谓安排问题，就是如何将肯定数量的资源安排给各运用者从而让目标函数达到最优，设备更新问题则是多用于工业和交通运输行业中，企业常常会遇到设备陈旧或部分损坏须要更新的问题，因此须要分析一种设备应当用多少年后进行更新最为恰当，从而使某一时间内的总收入达到最大。 【关键词】动态规划；资源安排；设备更新 1 动态规划的基本概念 多阶段决策过程，是指一类特别的过程，它们可以按时间依次分解成若干个相互联系的阶段，称为“时段”，在每个时段都要做决策，全部过程的决策是一个决策序列。多阶段决策问题也称为序贯决策问题。 多阶段决策问题的目标是要达到整个活动过程的总体最优。在每个阶段进行决策时不应仅考虑本阶段最优，尤其应考虑对最终目标的影响，从而做出对全局来说最优的决策。动态规划是符合这种要求的一种决策方法。 动态规划起先只是应用于多阶段决策性问题，后来慢慢被发展为解决离散最优化问题的有效手段，进一步应用于一些连续性问题上。然而，动态规划更像是一种思想而非算法，它没有固定的数学模型，没有固定的实现方法，其正确性也缺乏严格的理论证明。因此，始终以来动态规划的数学理论模型是一个探讨的热点。一个多阶段决策过程最优化问题的动态规划模型通常包含以下基本要素：阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数，在建立动态规划数学模型时，主要是确定这些动态规划的基本要素。 2 动态规划算法的基本步骤 2.1 划分阶段 应将实际问题恰当地分割成n个子问题。通常是依据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。 2.2 选择状态 正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满意无后效性.动态规划中的状态与一般限制系统中和通常所说的状态的概念是有所不同的。 2.3 确定决策并写出状态转移方程 之所以把这两步放在一起，是因为决策和状态转移有着自然的联系，状态转移就是依据上一阶段的状态和决策来导出本阶段的状态。所以，假如我们确定了决策，状态转移方程也就写出来了。但事实上，我们经常是反过来做，依据相邻两段的各状态之间的关系来确定决策。 2.4 写出规划方程 动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简洁的。 3 动态规划应用问题 3.1 资源安排问题 例：某物流公司每天要给3家公司运输6车货物，假如各公司获得这些货物之后获得的盈利如表1所示，则这车货物如何安排给各工厂才能使盈利最大。 解：将问题按公司分为3个阶段，甲、乙、丙三个公司分别编号为1、2、3 设sk表示为安排给第k个公司至第n个公司的货物车数 xk表示为安排给第k个公司的货物数量 则sk+1=sk-xk为安排给第k+1个公司至第n个公司的货物车数 pk表示为xk车货物安排到第k个公司所得的盈利值 fk表示为sk车货物安排给第k个公司至第n个公司时所得到的最大盈利值 依据逆推关系式 fk=maxpk+fk+1，k=3，2，1 0xksk f4=0 所以从最终一个阶段起先向前逆推计算 第三阶段： 设将s3车货物全部安排给公司丙时，最大盈利值为 f3=maxp3 其中x3=s3=0，1，2，3，4，5，6 因为此时只有一个公司，有多少车货物就全部安排给公司丙，故它的盈利值就是该段的最大盈利值，其数值计算如表2所示。 其次阶段： k=2时，设把s2车货物安排给公司乙和丙时，对每个s2值有一种最优安排方案，使最大盈利值为 f2=maxp2+f3 其中s2=0，1，2，3，4，5，6 因为乙公司x2车，其盈利为p2，余下的s2-x2车就给丙公司，则它的盈利最大值为f3。现在选择x2的值，使p2+f3取最大值，其数值计算如表3所示。 第一阶段： k=1时，设把s1车货物安排给甲、乙、丙三个公司时，最大盈利值为 f1=maxp1+f2 其中x1=0，1，2，3，4，5，6 因为给甲公司x1车，其盈利为p1，剩下的6-x1车就分给乙和丙两个公司，则它的盈利最大值为f2，现选择x1值，使p1+f2取最大值，它就是所求的总盈利最大值，其数值计算如表4所示。 依据计算表格的依次反推算，可知最优安排方案为： x1*=1，由于s2=s1-x1*=6-1=5，查其次个表可知x2*=5，s3=s2-x2*=5-5=0 即得甲公司安排1车，乙公司安排5车，丙公司不安排，总盈利为17。 3.2 设备更新问题 现以一台机器设备为例，在运用过程中，每年都面临接着运用或更新的决策，要求在n年内的每年年初作出决策，是接着运用旧设备还是更换一台新的，使n年内总效益最大。 n为设备安排运用年数。 Ik为第k年机器役龄为t年的一台机器运行所得的收入。 Ok为第k年机器役龄为t年的一台机器运行时所需运行的费用。 Ck为第k年机器役龄为t年的一台机器更新时所需的净费用。 a为折扣因子，表示一年以后的收入是上一年的a单位。 T为在第一年起先正在运用的机器的役龄。 最优指标函数gk：表示第k年初，运用一台已用了t年的设备，到第n年末的最大收益。 xk表示给出gk时，在第k年起先时的决策 建立动态规划模型如下： 阶段k表示安排运用该设备的年限数。 决策变量xk：是第k年初更新，还是保留运用旧设备，分别用R ，K表示。 状态转移方程为： gk=maxR：Ik-Ok-Ck+agk+1K： Ik-Ok+agk+1 gn+1=0 例：假设n=5，a=1，T=1，某台新设备的年收入及运行费用、更新费用如表5，试确定五年内的更新策略，使总效益达到最大。 解：因第k年起先机龄为t年的机器，其制造年序应为k-t年，因此，I5为第五年新产品的收入，即I5=43，I3为第一年的产品其机龄为2年的收入，即I3=30，C5是第五年机龄为1年的机器的更新费用，即C5=41，其余同理类推。 当k=1时，由于设T=1，所以从第五年起先计算时，机器运用了1、2、3、4、5年，依据递推关系式 g5=maxR：I5-O5-C5+g6K： I5-O5+g6 可知 g5=maxR：43-2-41+0=0K：38-3+0=35=35，即x5=K g5=30，即x5=K g5=25，即x5=K g5=18，即x5=K g5=16，即x5=K 当k=4时， g4=maxR：I4-O4-C4+g5K： I4-O4+g5 g4=maxR：41-2-40+35=34K：36-3+30=63 =63，即x4=K g4=53，即x4=K g4=40，即x4=K g4=33，即x4=K 当k=3时， g3=maxR：I3-O3-C3+g4K： I3-O3+g4 g3=maxR： 38-3-39+63=59K：36-4+53=85=85，即x3=K g3=64，即x3=K g3=54，即x3=R 当k=2时， g2=maxR：I2-O2-C2+g3K： I2-O2+g3 g2=maxR： 37-3-37+85=82K：31-4+64=91=91，即x2=K g2=77，即x2=R 当k=1时， g1=maxR：I1-O1-C1+g1K： I1-O1+g1 g1=maxR： 32-4-40+91=79K：28-6+77=101=101，即x1=K 最终依据上面的结果反推之，可求得最优策略为 第一年机龄为1，最佳策略为K 其次年机龄为2，最佳策略为R 第三年机龄为1，最佳策略为K 第四年机龄为2，最佳策略为K 第五年机龄为3，最佳策略为K 最大收益为101。 4 总结 动态规划是一种将问题实例分解为更小的、相像的子问题，并存储子问题的解而避开计算重复的子问题，以解决最优化问题的算法策略。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，在动态规划的设计过程中，阶段的划分和状态的表示是特别重要的两步，这两步会干脆影响该问题的计算困难性，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。动态规划的优点是最优解是全局最优解，能得到一系列的最优解，不须要对系统状态转移方程、阶段效应函数等的解析性质作任何假设。缺点是没有统一的标准模型和标准的算法可供运用，应用有局限性。 【参考文献】 1运筹学M.3版.清华高校出版社 2动态规划案例OL.一百零一度文库. 3运筹学动态规划OL.一百零一度文库. 责任编辑：王静 第9页 共9页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页