动态规划应用举例讲解VIP免费

南京航空航天大学运筹学课程论文题目：动态规划应用举例学号：姓名：完成日期：2013。5。16摘要动态规划是解决最优控制的一种重要方法之一，算法的优点有：（1）易于确定全局最优解；（2）能得到一族解，有利于分析结果；（3）能利用经验，提高求解的效率。动态规划方法虽然存在许多不足之处，但随着计算机的日益普及，动态规划的应用越来越广泛，它能够巧妙地解决科学技术和实际生活中的许多实例。本文列举了一些典型例题，介绍了如何用动态规划去求解，不足之处是这些问题大多数都是确定型的，而对于连续型、随机型问题接触较少。关键词：动态规划；应用；正文一、资源分配问题所谓分配问题，就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品等等)，恰当地分配给若干个使用者，而使目标函数为最优。设有某种原料，总数量为a，用于生产n种产品。若分配数量ix用于生产第i种产品，其收益为()iigx，问应如何分配，才能使生产n产品的总收入最大?此问题可写成静态规划问题：112212max()()()0,1,2,,nnnizgxgxgxxxxaxin当()iigx都是线性函数时，它是一个线性规划问题；当()iigx是非线性函数时，它是一个非线性规划问题。但当n比较大时，具体求解是比较麻烦的。由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划的递推关系来求解。在应用动态规划方法处理这类“静态规划”问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量ix为决策变量，将累计的量或随递推过程变化的量选为状态变量。设状态变量ks表示分配用于生产第k种产品至第n种产品的原料数量。决策变量ku表示分配给生产第k种产品的原料数，即ku=kx状态转移方程：1kkkkkssusx允许决策集合：()0kkkkkkDsuuxs令最优值函数()kkfs表示以数量为ks的原料分配给第k种产品至第n种产品所得到的最大总收入。因而可写出动态规划的逆推关系式为：10()max()(),1,,1()max()kknnkkkkkkkxsnnnnxsfsgxfsxknfsgx利用这个递推关系式进行逐段计算，最后求得1()fa即为所求问题的最大总收入。例1某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表9-1所示。表9-1工厂盈利/万元备设台数甲乙丙000013542710639111141211125131112问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。解将问题按工厂分为三个阶段，甲、乙、丙三个工厂分别编号为1、2、3。设ks表示为分配给第k个工厂至第n个工厂的设备台数。kx表示为分配给第k个工厂的设备台数，则1kkkssx为分配给第k+1个工厂至第n个工厂的设备台数。()kkPx表示为kx台设备分配到第k个工厂所得的盈利值。()kkfs表示为ks台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。因而可写出逆推关系式为1044()max()(),3,2,1()0kkkkkkkkkxsfsPxfsxkfs下面从最后一个阶段开始向前逆推计算。第三阶段：设将3s台设备(3s=0，1，2，3，4，5)全部分配给工厂丙时，则最大盈利值为33333()max()xfsPx，其中3x=3s=0，1，2，3，4，5。因为此时只有一个工厂，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值，如下表。表9-23x3s33()Px33()fs3x012345000014412662311113412124512125表中3x表示使33()fs为最大值时的最优决策。第二阶段：设把2s台设备(2s=0，1，2，3，4，5)分配给工厂乙和工厂丙时，则对每个2s值，有一种最优分配方案，使最大盈利值为22222322()max()()xfsPxfsx其中20,1,2,3,4,5x。因为给乙工厂2x台，其盈利为22()Px，余下的2s-2x台就给丙工厂，则它的盈利最大值为322()fsx。现要选择2x的值，使22322()()pxfsx取最大值。其数值计算如表9-3所示。表9-32x2s22322()()pxfsx22()fs*2x012345000010+45+05120+65+410+010230+115+610+411+014240+125+1110+611+411+0161，250+125+1210+1111+611+411+0212第一阶段：设把1s台(这里只有1s=5的情况)设备分配给甲、乙、丙三个工厂时，则最大盈利值为111121(5)max()(5)xfpxfx其中10,1,2,3,4,5x。因为给甲工厂1x台，其盈利为11()px，剩下的5-1x台就分给乙和丙两个工厂，则它...