动态规划应用举例 - 图文

南京航空航天大学 运筹学 课程论文

题目：动态规划应用举例

学号： 姓名： 完成日期：2013。5。16

摘 要

动态规划是解决最优控制的一种重要方法之一，算法的优点有：（1）易于确定全局最优解；（2）能得到一族解，有利于分析结果；（3）能利用经验，提高求解的效率。动态规划方法虽然存在许多不足之处，但随着计算机的日益普及，动态规划的应用越来越广泛，它能够巧妙地解决科学技术和实际生活中的许多实例。本文列举了一些典型例题，介绍了如何用动态规划去求解，不足之处是这些问题大多数都是确定型的，而对于连续型、随机型问题接触较少。 关键词：动态规划；应用；

正 文

一、 资源分配问题

所谓分配问题，就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品等等)，恰当地分配给若干个使用者，而使目标函数为最优。

设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi)，问应如何分配，才能使生产n产品的总收入最大? 此问题可写成静态规划问题：

?max z?g1(x1)?g2(x2)???gn(xn)? ?x1?x2???xn?a?x?0, i?1,2,?,n?i当gi(xi)都是线性函数时，它是一个线性规划问题；当gi(xi)是非线性函数时，它是一个非线性规划问题。但当n比较大时，具体求解是比较麻烦的。由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划的递推关系来求解。

在应用动态规划方法处理这类“静态规划”问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量xi为决策变量，将累计的量或随递推过程变化的量选为状态变量。

设状态变量sk表示分配用于生产第k种产品至第n种产品的原料数量。 决策变量uk表示分配给生产第k种产品的原料数，即uk=xk 状态转移方程：sk?1?sk?uk?sk?xk 允许决策集合：Dk(sk)??uk0?uk?xk?sk?

令最优值函数fk(sk)表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收入。因而可写出动态规划的逆推关系式为：

?fk(sk)?max?gk(xk)?fk?1(sk?xk)?, k?n?1,?,10?xk?sk? ?fn(sn)?maxgn(xn)?xn?sn ?利用这个递推关系式进行逐段计算，最后求得f1(a)即为所求问题的最大总收入。

例1 某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表9-1所示。

表9-1

工厂 盈利/万元 备设 台数 0 1 2 3 4 5 甲 乙 丙 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。

解 将问题按工厂分为三个阶段，甲、乙、丙三个工厂分别编号为1、2、3。

设sk表示为分配给第k个工厂至第n个工厂的设备台数。xk表示为分配给第k个工厂的设备台数，则

sk?1?sk?xk为分配给第k+1个工厂至第n个工厂的设备台数。Pk(xk)表示为xk台设备分配到第k个工厂

所得的盈利值。fk(sk)表示为sk台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。

因而可写出逆推关系式为

??Pk(xk)?fk?1(sk?xk)?, k?3,2,1?fk(sk)?0max?xk?sk ???f4(s4)?0下面从最后一个阶段开始向前逆推计算。

第三阶段：设将s3台设备(s3=0，1，2，3，4，5)全部分配给工厂丙时，则最大盈利值为

f3(s3)?max?P3(x3)?，其中x3=s3=0，1，2，3，4，5。因为此时只有一个工厂，有多少台设备就全部分

x3配给工厂丙，故它的盈利值就是该段的最大盈利值，如下表。

表9-2

x3 s3 0 1 2 3 4 5

P3(x3) f3(s3) 0 0 1 4 2 6 3 11 4 12 12 5 0 4 6 11 12 12 ?x3 0 1 2 3 4 5

表中x3表示使f3(s3)为最大值时的最优决策。

第二阶段：设把s2台设备(s2=0，1，2，3，4，5)分配给工厂乙和工厂丙时，则对每个s2值，有一种最优分配方案，使最大盈利值为

?f2(s2)?max?P2(x2)?f3(s2?x2)?

x2其中x2?0,1,2,3,4,5。

因为给乙工厂x2台，其盈利为P2(x2)，余下的s2?x2台就给丙工厂，则它的盈利最大值为f3(s2?x2)。现要选择x2的值，使p2(x2)?f3(s2?x2)取最大值。其数值计算如表9-3所示。

表9-3

x2 p2(x2)?f3(s2?x2) f2(s2) *x2 s2 0 1 2 3 4 5 第一阶段： 0 1 2 3 4 5 0 5 10 14 16 21 0 1 2 2 1，2 2 0 0+4 5+0 0+6 5+4 10+0 0+11 5+6 10+4 11+0 0+12 5+11 10+6 11+4 0+12 5+12 10+11 11+6 11+0 11+4 11+0 设把s1台(这里只有s1=5的情况)设备分配给甲、乙、丙三个工厂时，则最大盈利值为

f1(5)?max?p1(x1)?f2(5?x1)?

x1其中 x1?0,1,2,3,4,5。

因为给甲工厂x1台，其盈利为p1(x1)，剩下的5?x1台就分给乙和丙两个工厂，则它的盈利最大值为

f2(5?x1)。现要选择x1值，使p1(x1)?f2(5?x1)取最大值，它就是所求的总盈利最大值，其数值计算如

表9-4所示。

表9-4

x1 p1(x1)?f2(5?x1) f1(5) x1* s1 5 0 0+21 1 3+16 2 7+14 3 9+10 4 12+5 5 13+0 21 0，2 然后按计算表格的顺序反推算，可知最优分配方案有两个：

(1) 由于x1=0 ，根据s2?s1?x1?5?0?5，查表9-3知x2=2，由s3?s2?x2?5?2?3，故

*x3?s3?3，即得甲工厂分配0台，乙工厂分配2台，丙工厂分配3台。

******?*(2) 由于x1=2，根据s2?s1?x1?5?2?3，查表9-3知x2=2，由s3?s2?x2?3?2?1，故

*x3?s3?1，即得甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。

以上两个分配方案所得到的总盈利均为21万元。 资源连续分配问题

设有数量为s1的某种资源，可投入A和B两种生产。第一年若以数量u1投入生产A，剩下的量s1?u1就投入生产B，则可得收入为g(u1)?h(s1?u1)，其中g(u1)和h(u1)为已知函数，且g(0)=h(0)=0。这种资源在投入A、B生产后，年终还可回收再投入生产。设年回收率分别为0

此问题写成静态规划问题为

max z??g(u1)?h(s1?u1)?g(u2)?h(s2?u2)???g(un)?h(sn?un)??s2?au1?b(s1?u1)?s?au2?b(s2?u2)?3????s?au?b(s?u)nnn?n?1??0?ui?si, i?1,2,?,n下面用动态规划方法来处理。

设sk为状态变量，它表示在第k阶段(第k年)可投入A、B两种生产的资源量。

uk为决策变量，它表示在第k阶段(第k年)用于A生产的资源量，则sk?uk表示用于B生产的资源量。

状态转移方程为sk?1?auk?b(sk?uk)

最优值函数fk(sk)表示有资源量sk ，从第k阶段至第n阶段采取最优分配方案进行生产后所得到的最大总收入。

因此可写出动态规划的逆推关系式为