动态规划应用例.docVIP

南京航空航天大学 运筹学 课程论文 题目：动态规划应用举例 学号： 姓名： 完成日期：2013。5。16 摘 要 动态规划是解决最优控制的一种重要方法之一，算法的优点有：（1）易于确定全局最优解；（2）能得到一族解，有利于分析结果；（3）能利用经验，提高求解的效率。动态规划方法虽然存在许多不足之处，但随着计算机的日益普及，动态规划的应用越来越广泛，它能够巧妙地解决科学技术和实际生活中的许多实例。本文列举了一些典型例题，介绍了如何用动态规划去求解，不足之处是这些问题大多数都是确定型的，而对于连续型、随机型问题接触较少。 关键词：动态规划；应用； 正 文 一、 资源分配问题 所谓分配问题，就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品等等)，恰当地分配给若干个使用者，而使目标函数为最优。 设有某种原料，总数量为a，用于生产n种产品。若分配数量用于生产第i种产品，其收益为，问应如何分配，才能使生产n产品的总收入最大? 此问题可写成静态规划问题： 当都是线性函数时，它是一个线性规划问题；当是非线性函数时，它是一个非线性规划问题。但当n比较大时，具体求解是比较麻烦的。由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划的递推关系来求解。 在应用动态规划方法处理这类“静态规划”问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量为决策变量，将累计的量或随递推过程变化的量选为状态变量。 设状态变量表示分配用于生产第k种产品至第n种产品的原料数量。 决策变量表示分配给生产第k种产品的原料数，即= 状态转移方程： 允许决策集合： 令最优值函数表示以数量为的原料分配给第k种产品至第n种产品所得到的最大总收入。因而可写出动态规划的逆推关系式为： 利用这个递推关系式进行逐段计算，最后求得即为所求问题的最大总收入。 例1 某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表9-1所示。 表9-1 问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。 解 将问题按工厂分为三个阶段，甲、乙、丙三个工厂分别编号为1、2、3。 设表示为分配给第k个工厂至第n个工厂的设备台数。表示为分配给第k个工厂的设备台数，则为分配给第k+1个工厂至第n个工厂的设备台数。表示为台设备分配到第k个工厂所得的盈利值。表示为台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。 因而可写出逆推关系式为 下面从最后一个阶段开始向前逆推计算。 第三阶段：设将台设备(=0，1，2，3，4，5)全部分配给工厂丙时，则最大盈利值为，其中==0，1，2，3，4，5。因为此时只有一个工厂，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值，如下表。 表9-2 0 1 2 3 4 5 0 0 ? ? ? ? ? 0 0 1 ? 4 ? ? ? ? 4 1 2 ? ? 6 ? ? ? 6 2 3 ? ? ? 11 ? ? 11 3 4 ? ? ? ? 12 ? 12 4 5 ? ? ? ? ? 12 12 5 表中表示使为最大值时的最优决策。 第二阶段：设把台设备(=0，1，2，3，4，5)分配给工厂乙和工厂丙时，则对每个值，有一种最优分配方案，使最大盈利值为 其中。 因为给乙工厂台，其盈利为，余下的?台就给丙工厂，则它的盈利最大值为。现要选择的值，使取最大值。其数值计算如表9-3所示。 表9-3 ? ? 0 1 2 3 4 5 0 0 ? ? ? ? ? 0 0 1 0+4 5+0 ? ? ? ? 5 1 2 0+6 5+4 10+0 ? ? ? 10 2 3 0+11 5+6 10+4 11+0 ? ? 14 2 4 0+12 5+11 10+6 11+4 11+0 ? 16 1，2 5 0+12 5+12 10+11 11+6 11+4 11+0 21 2 第一阶段： 设把台(这里只有=5的情况)设备分配给甲、乙、丙三个工厂时，则最大盈利值为 其中 。 因为给甲工厂台，其盈利为，剩下的5?台就分给乙和丙两个工厂，则它的盈利最大值为。现要选择值，使取最大值，它就是所求的总盈利最大值，其数值计算如表9-4所示。 表9-4 ? ? 0 1 2 3 4 5 5 0+21 3+16 7+14 9+10 12+5 13+0 21 0，2 然后按计算表格的顺序反推算，可知最优分配方案有两个： (1) 由于=0 ，根据，查表9-3知=2，由，故，即得甲工厂