(7.6.1)--07-6+动态规划的应用举例.pdf

《(7.6.1)--07-6+动态规划的应用举例.pdf》由会员分享，可在线阅读，更多相关《(7.6.1)--07-6+动态规划的应用举例.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划的应用举例一、资源分配问题把有限的资源(如资金、材料、设备、人力等)分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。资源可以有一种或若干种，只有一种资源可供分配的问题称之为一维资源分配问题。设有某种资源（如电、煤等）可用于n项活动，假设资源数量为a，已知用于第 i 项活动的资源数为xi，可以得到收益试确定资源分配方案使总收益最大。该问题的数学模型可以表示为：当是线性函数时，上述问题是线性规划问题；而当是非线性函数时，如果采用非线性规划的方法是比较麻烦的。然而这类问题可以将其看成是一个多阶段决策问题，并采用动态规划的方法求解。在用动态规划方法处理这类一维资源分配问题时,通常将

2、资源分给每项活动的过程看是一个阶段，每个阶段都要确定对一种资源的投放量。设状态变量 s k 表示分配用于生产第k种产品至第n种产品原料的数量。决策变量 u k表示分配给生产第k种产品的原料量，即 u k=x k状态转移方程：允许决策集合：表示以数量s k的原料分配给第k种产品至第n种产品所得到的最大利润，则有例7-6：某工业部门按国家计划的安排，拟将某高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如下表所示。问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。动态规划的数学模型将三个分厂看作是三个阶段，即阶段变量 k=1,2,3;状态变量

3、sk表示第k阶段初可分配的设备台数,0sk5;决策变量xk 表示第k 阶段分配给分厂k 的设备台数，允许决策集合Xk(sk)=xk 0 xksk;状态转移方程为 sk+1=sk-xk;阶段指标Pk(sk,xk)表示第k阶段从sk台设备中分配给k分厂xk台设备的阶段效益;最优指数函数fk(sk)表示第k阶段从sk开始到最后阶段采用最优分配策略取得的最大的效益值;递推方程函数式逆序求解第三阶段：设将S3台设备（S30,1,2,3,4,5）全部分配给丙厂时，此时只有一个工厂，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值。最大盈利值为：f3(S3)maxP3(X3)其中X3S30,

4、1,2,3,4,5 X3*表示使得f3(S3)为最大值时的最优决策。表71第二阶段：设将S2台设备（S20,1,2,3,4,5）分配给乙厂和丙厂时，对每一个S2值，都有一种最优分配方案.如果给乙工厂x2台，其盈利为P2(x2),余下s2-x2台就是给丙厂的，则丙的盈利最大值为：f3(s2-x2),现在要选择x2的值,使得P2(x2)+f3(S2x2)取最大值.即将 s 2台设备分给乙丙获得最大盈利值为：f2(S2)max P2(x2)+f3(S2x2)，x20,1,2,3,4,5计算过程如下.当共有0台设备给乙，丙时，当共有1台设备给乙和丙时，2种情况。给乙或丙，则当共有2台设备给乙和丙时，3

5、种情况。给乙或丙，则当共有3台设备给乙和丙时，4种情况。给乙或丙，则当共有4台设备给乙和丙时，5种情况。则当共有5台设备给乙和丙时，6种情况。则利润甲甲乙乙丙丙0120370510046利润甲甲乙乙丙丙345912131112111111120123450 1 2 3 4 5x2P2(x2)+f3(s2-x2)s2f2(s2)x*200+45+000510+65+410+01025+60+1110+414211+00+125+1110+611+411+05+12161，20+1210+1111+611+411+0212乙厂在丌同设备台数下所获利润第丙厂在设备台数为s3下所获得的最大利润表72第

6、一阶段：设将S1台设备（S15）分配给甲厂、乙厂和丙厂时，因为给甲工厂x1台，其盈利值为 p1(x1),剩下的5-x1台设备就分别给乙和丙工厂，则它的盈利值为f2(5-x1)，现要选择 x1的值，使P1(x1)f2(5x1)最大值，则最大盈利值为：f1(S1)max P1(X1)+f2(5X1)其中，x10,1,2,3,4,5甲厂在不同设备台数下所获利润乙厂在设备台数为s2下所获得的最大利润利润甲甲乙乙丙丙0120370510046利润甲甲乙乙丙丙34591213111211111112按计算表格的顺序反推，可知最优分配方案有两个：1）由X1*0，S2S1X1*505。再由表72，可知X2*2。S3S2X2*523，故X3*S33。即得甲厂分得0台，乙厂分得2台，丙厂分得3台。2）由X1*2，S2S1X1*523。再由表72，可知X2*2。S3S2X2*321，故X3*S31。即得甲厂分得2台，乙厂分得2台，丙厂分得1台。以上两种最优方案的总盈利均为21万元。如果原设备台数丌是5台，而是4台或3台，用其它方法解时，往往要从头再算。但用动态规划解时，这些列出的表仍然有用，只需修改最后的表格，就可以得到。