动态规划应用举例.docx

南京航空航天大学运筹学课程论文 题目：动态规划应用举例 学号： 姓名： 完成日期：2013。5。16 摘要 利用这个递推关系式进行逐段计算，最后求得 利用这个递推关系式进行逐段计算，最后求得 fa)即为所求问题的最大总收入。 动态规划是解决最优控制的一种重要方法之一，算法的优点有： (1)易于确定全局最优解；(2)能得 到一族解，有利于分析结果； (3)能利用经验，提高求解的效率。动态规划方法虽然存在许多不足之处， 但随着计算机的日益普及，动态规划的应用越来越广泛，它能够巧妙地解决科学技术和实际生活中的许多 实例。本文列举了一些典型例题，介绍了如何用动态规划去求解，不足之处是这些问题大多数都是确定型 的，而对于连续型、随机型问题接触较少。 关键词：动态规划；应用； 正文 一、资源分配问题 所谓分配问题，就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品等等)， 恰当地分配给若干个使用者，而使目标函数为最优。 设有某种原料，总数量为a，用于生产n种产品。若分配数量x用于生产第i种产品，其收益为gi (xi)， 问应如何分配，才能使生产 n产品的总收入最大？ 此问题可写成静态规划问题： max z gi(Xi) g2(X2) L gn(Xn) x-i x2 L xn a Xi 0, i 1,2,L , n 当gi(\)都是线性函数时，它是一个线性规划问题；当 gi(xj是非线性函数时，它是一个非线性规划 问题。但当n比较大时，具体求解是比较麻烦的。由于这类问题的特殊结构，可以将它看成一个多阶段决 策问题，并利用动态规划的递推关系来求解。 在应用动态规划方法处理这类 静态规划”问题时，通常以把资源分配给一个或几个使用者的过程作为 一个阶段，把问题中的变量 Xi为决策变量，将累计的量或随递推过程变化的量选为状态变量。 设状态变量sk表示分配用于生产第 k种产品至第n种产品的原料数量。 决策变量Uk表示分配给生产第 k种产品的原料数，即Uk = Xk 状态转移方程： sk 1 sk uk sk xk 允许决策集合：以6) Uk 0 Uk Xk Sk 令最优值函数fk(sj表示以数量为Sk的原料分配给第k种产品至第n种产品所得到的最大总收入。 因 而可写出动态规划的逆推关系式为： fk(Sk) 0max gk(Xk) fk 16 Xk) , k n 1丄,1 0 Xk环 fn(Sn) maXgn(Xn) Xn Sn 例1某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工 厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表 9-1所示。 这五台设备如何分配给各工厂，才能使国家得到的盈利最大。 解将问题按工厂分为三个阶段，甲、乙、丙三个工厂分别编号为 1、2、3。 设Sk表示为分配给第k个工厂至第n个工厂的设备台数。Xk表示为分配给第k个工厂的设备台数，则 Sk 1 Sk Xk为分配给第k+1个工厂至第n个工厂的设备台数。Pk（Xk）表示为Xk台设备分配到第k个工厂 所得的盈利值。fk（Sk）表示为Sk台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。 因而可写出逆推关系式为 fk（Sk） max R（Xk） fk 16 Xk） , k 3,2,1 0 Xk Sk f4（S4）0 下面从最后一个阶段开始向前逆推计算。 第三阶段：设将S3台设备（S3 =0， 1， 2， 3， 4， 5）全部分配给工厂丙时，则最大盈利值为 f3（Ss） max P3（X3），其中X3 = S3 =0，1，2，3，4，5。因为此时只有一个工厂，有多少台设备就全部分 配给工厂丙，故它的盈利值就是该段的最大盈利值，如下表。 表9-2 \ X3 S3 P3( X3 ) f3(s3) X3 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  表中x3 表中x3表示使f3（S3） 12 12 5 | 为最大值时的最优决 策。 第二阶段：设把S2台设备（s2=o, 1, 2, 3, 4, 5）分配给工厂乙和工厂丙时，则对每个 s2值，有一种 最优分配方案，使最大盈利值为 f2（S2） max 巳区）f3（S x?） 其中 x2 0,1,2,3,4,5。 第一阶段：因为给乙工厂X2台，其盈利为F2（X2），余下的S2-X2台就给丙工厂，则它的盈利最大值为 f3（S2 X2）。 第一阶段： P2(X2)f3(S2 X2) f2（S2） * X2 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