动态规划应用举例 - 图文

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

题目：动态规划应用举例

学号： 姓名： 完成日期：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阶段采取最优分配方案进行生产后所得到的最大总收入。

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

?fn(sn)?max?g(un)?h(sn?un)?0?un?sn???g(uk)?h(sk?uk)?fk?1?auk?b(sk?uk)?? ?fk(sk)?0max?uk?sk? k?n?1,?,2,1??最后求出f1(s1)即为所求问题的最大总收入。

例2 机器负荷分配问题。某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中u1为投入生产的机器数量，年完好率a=0。7；在低负荷下生产的产量函数为h=5y，其中y为投入生产的机器数量，年完好率为b=0。9。

假定开始生产时完好的机器数量s1=1000台，试问每年如何安排机器在高、低负荷下的生产，使在五年内生产的产品总产量最高。

构造这个问题的动态规划模型： 设阶段序数k表示年度。

状态变量sk为第k年度初拥有的完好机器数量，同时也是第k?1年度末时的完好机器数量。 决策变量uk为第k年度中分配高负荷下生产的机器数量，于是sk?uk为该年度中分配在低负荷下生产的机器数量。

这里sk和uk均取连续变量，它们的非整数值可以这样理解，如sk=0。6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0。3，就表示一台机器在该年度只有3/10的时间能在高负荷下工作。

bks?u)s?u), k? ?1 ,2,状态转移方程为 sk?1?auk?(k?0.7uk?0.9(kkk段允许决策集合为 Dk(sk)??uk0?uk?sk? 设vk(sk,uk)为第k年度的产量，则

,5vk?8uk?5(sk?uk)

故指标函数为

V1,5??vk(sk,uk)

k?15令最优值函数fk(sk)表示由资源量sk出发，从第k年开始到第5年结束时所生产的产品的总产量最大值。因而有逆推关系式：

?f(s)?066???8uk?5(sk?uk)?fk?1?0.7uk?0.9(sk?uk)?? ?fk(sk)?umaxk?Dk(sk)??? k?1,2,3,4,5

从第5年度开始，向前逆推计算。

当k=5时，有f5(s5)?max8u5?5(s5?u5)?f6?0.7u5?0.9(s5?u5)?

0?u5?s5???max?8u5?5(s5?u5)??max?3u5?5s5?

0?u5?s50?u5?s5因f5是u5的线性单调增函数，故得最大解u5?s5，相应的有f5(s5)?8s5。

当k=4时，有f4(s4)?max8u4?5(s4?u4)?f5?0.7u4?0.9(s4?u4)?

0?u4?s4????max?8u4?5(s4?u4)?8?0.7u4?0.9(s4?u4)??0?u4?s4?max?13.6u4?12.2(s4?u4)??max?1.4u4?12.2s4?0?u4?s40?u4?s4

故得最大解，u4=s4，相应的有f4(s4)?13.6s4。依此类推，可求得

*?u3?s3, 相应的 f3(s3)?17.5s3?*?u2?0, 相应的 f2(s2)?20.8s2 ?*?u1?0, 相应的 f1(s1)?23.7s1?因s1=1000，故f1(s1)?23700（台）。

计算结果表明：最优策略为u1?0,u2?0,u3?s3,u4?s4,u5?s5，即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产。这样所得的产量最高，其最高产量为23700台。

在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即从始端向终端递推计算出每年年初完好机器数。已知s1=1000台，于是可得

*****s2?0.7u1*?0.9(s1?u1*)?0.9s1?900(台)**s3?0.7u2?0.2(s2?u2)?0.9s2?810(台)**s4?0.7u3?0.9(s3?u3)?0.7s3?567(台) **s5?0.7u4?0.9(s4?u4)?0.7s4?397(台)**s6?0.7u5?0.9(s5?u5)?0.7s5?278(台)下面讨论始端固定、终端自由的一般情形。

设有n个年度，在高、低负荷下生产的产量函数分别为g?cu1,h?du2，其中c、d>0，c>d。年回收率分别为a和b，0

sk?1?auk?b(sk?uk), k?1,2,?,n

k段的指标函数为

vk?cuk?b(sk?uk), k?1,2,?,n

令fk(sk)表示由状态sk出发，从第k年至第n年末时所生产的产品的总产量最大值。

可写出逆推关系式为：

?f(s)?0n?1n?1???cuk?d(sk?uk)?fk?1?auk?b(sk?uk)??(9?2) ?fk(sk)?0max?uk?sk??? k?1,2,?,n我们知道，在低负荷下生产的时间愈长，机器完好率愈高，但生产产量少。而在高负荷下生产产量会

增加，但机器损坏大。这样，即使每台产量高，总起来看产量也不高。

从前面的数字计算可以看出，前几年一般是全部用于低负荷生产，后几年则全部用于高负荷生产，这样才产量最高。如果总共为n年，从低负荷转为高负荷生产的是第t年，1≤t≤n。即是说，从1至t?1年在低负荷下生产，t至n年在高负荷下生产。现在要分析t与系数a、b、c、d是什么关系。

从回收率看，(b ? a)值愈大，表示在高负荷下生产时，机车损坏情况比在低负荷时严重得多，因此t值应选大些。从产量看，(c ? d)值愈大，表示在高负荷下生产较有利，故t应选小些。下面我们从(9-2)式这一基本方程出发来求出t与(b ? a)、(c ? d)的关系。

令?k?uksk。则在低负荷生产时有?k?0，高负荷生产时有?k?1。对第n段，有

fn(sn)?max?cun?d(sn?un)??max?(c?d)un?dsn??max?(c?d)?n?d?sn

0?un?sn0?un?sn0??n?1由于c＞d，所以?n应选1才能使fn(sn)最大。也就是说，最后一年应全部投入高负荷生产。故fn(sn)?csn

对n-1段，根据(9-2)式有

fn?1(sn?1)?maxun?10?un?1?sn?1?cun?1?d(sn?1?un?1)?fn(sn)??max?cun?1?d(sn?1?un?1)?csn??max?cun?1?d(sn?1?un?1)?c?aun?1?b(sn?1?un?1)??un?1

?max??(c?d)?c(b?a)?un?1?(d?cb)sn?1?un?1?max??(c?d)?c(b?a)??n?1?(d?cb)?sn?1?n?1(9?3)因此，欲要满足上式极值关系的条件是当

c?d?c(b?a)*(9?4)

*时，应取?n?1?1，即n ? 1年仍应全部在高负荷下生产。否则，当(9-4)式不满足时，应取?n?1?0，即n ? 1年应全部投入低负荷生产。 由前面知道，只要在第k年投入低负荷生产，那么递推计算结果必然是从第1年到第k年均为低负荷生产，即有?1??2????k?0。可见，算出?k?0后，前几年就没有必要再计算了。故只需研究哪一年由低负荷转入高负荷生产，即从?那一年开始变为1就行。根据这点，现只分析满足(9-4)式的情况。由于

*?n?1?1，故(9-3)式变为

****

fn?1(sn?1)?(c?ca)sn?1?c(1?a)sn?1

又由于sn?1?aun?2?b(sn?2?un?2)，将它代入上式得

fn?1(sn?1)?c(1?a)?(a?b)un?2?bsn?2?

对n-2段，由(9-2)式有

fn?2(sn?2)?maxun?20?un?2?sn?2?cun?2?d(sn?2-un?2)?fn?1(sn?1)?

?max?cun?2?d(sn?2?un?2)?c(1?a)?(a?b)un?2?bsn?2???max??(c?d)?c(1?a)(b?a)?un?2??d?c(1?a)b?sn?2?un?2?max??(c?d)?c(1?a)(b?a)??n?2?d?cb(1?a)?sn?2?n?2由此可知，只要满足极值条件式c?d?c(1?a)(b?a) 就应选?n?2?1，否则为0，即应继续在高负荷下生产。

依次类推，如果转入高负荷下生产的是第t年，则由

*ft(st)?max?cut?d(st?ut)?ft?1(st?1)?

ut可以推出，应满足极值关系的条件必然是：

2n?(t?1)?)(b?a)?c?d?c(1?a?a???a?2n?t??c?d?c(1?a?a???a)(b?a)(9?5)

相应的有最优策略

?n*??n*?1????t*?1???????*1*2*t?1?0

它就是例2在始端固定终端自由情况下最优策略的一般结果。

从这个例子看到，应用动态规划，可以在不求出数值解的情况下，确定最优策略的结构。 可见，只要知道了a，b，c，d四个值，就总可找到一个t值，满足(9-5)式，且1?t?n?1

例如题中给定的a?0.7,b?0.8,c?8,d?5，代入(9-5)式，应有

c?dc(b?a)?1?d/cb?a?1?5/80.9?0.7?31.6?1.875?(1?a)?1?0.7

可见n?t?1?5?t?1?1，所以t=3，即从第三年开始将全部机器投入高负荷生产，五年内总产量最高。

上面的讨论表明：当x在［0，s1］上离散地变化时，利用递推关系式逐步计算或表格法而求出数值解。当x在［0，s1］上连续地变化时，若g(x)和h(x)是线性函数或凸函数时，根据递推关系式运用解析法不难求出fk(x)和最优解；若g(x)和h(x)不是线性函数或凸函数时，一般来说，解析法不能奏效，那

只好利用递推关系式(9-1)求其数值解。首先要把问题离散化，即把区间［0，s1］进行分割，令x=0，Δ，2Δ，…，mΔ=s1。其Δ的大小，应根据计算精度和计算机容量等来确定。然后规定所有的fk(x)和决策变量只在这些分割点上取值。这样，递推关系式(9-1)便可写为

?fn(i?)?max?g(j?)?h(i??j?)?0?j?i???g(j?)?h(i??j?)?fk?1?a(j?)?b(i??j?)?? ?fk(i?)?max0?j?i? k?n?1,?,2,1??对i?0,1,?,m依次计算，可逐步求出fn(i?),fn?1(i?),?,f1(i?)及相应的最优决策，最后求得

f1(m?)?f1(s1)就是所求的最大总收入。这种离散化算法可以编成程序在计算机中计算。

1。2 二维资源分配问题

设有两种原料，数量各为a和b单位，需要分配用于生产n种产品。如果第一种原料以数量xi为单位，第二种原料以数量yi为单位，用于生产第i种产品，其收入为gi(xi,yi)。问应如何分配这两种原料于n种产品的生产使总收入最大?

此问题可写成静态规划问题：

?max?g1(x1,y1)?g2(x2,y2)???gn(xn,yn)???x1?x2???xn?a ?y?y???y?b2n?1?x?0,y?0, (i?1,2,?,n)且为整数i?i用动态规划方法来解，状态变量和决策变量要取二维的。

设状态变量(x，y):

x——分配用于生产第k种产品至第n种产品的第一种原料的单位数量。 y——分配用于生产第k种产品至第n种产品的第二种原料的单位数量。

决策变量(xk,yk)：

xk——分配给第k种产品用的第一种原料的单位数量。 yk——分配给第k种产品用的第二种原料的单位数量。 ??x?x;状态转换关系：xk??和?y?y?yk，式中xy分别表示用来生产第k+1种产品至第n种产品

的第一种和第二种原料的单位数量。

允许决策集合： Dk(x,y)??uk0?xk?x;0?yk?y?

fk(x,y)表示以第一种原料数量为x单位，第二种原料数量为y单位，分配用于生产第k种产品至第

n种产品时所得到的最大收入。故可写出逆推关系为

??fn(x,y)?gn(x,y)??gk(xk,yk)?fk?1(x?xk,y?yk)? ?fk(x,y)?0max?xk?x?0?yk?y?? k?n?1,?,1最后求得f1(a,b)即为所求问题的最大收入。 1。 拉格朗日乘数法

引入拉格朗日乘数λ，将二维分配问题化为

max?g1(x1,y1)?g2(x2,y2)???gn(xn,yn)??(y1?y2???yn)?

满足条件x1?x2???xn?a；xi?0,yi?0, i?1,2,?,n 且为整数，其中λ作为一个固定的参数。 令 hi(xi)?hi(xi,?)?max?gi(xi,yi)－?yi?

yi?0于是问题变为max?h1(x1)?h2(x2)???hn(xn)?，满足x1?x2???xn?a, xi?0且为整数

这是一个一维分配问题，可用对一维的方法去求解。这里，由于λ是参数，因此，最优解xi是参数λ的函数，相应的yi也是λ的函数。即xi?xi(?)，yi?yi(?)为其解。如果?yi(?)?b，则可证明xi,yii?1nnn??为原问题的最优解。如果?yi(?)?b，将调整λ的值(利用插值法逐渐确定λ )，直到?yi(λ)?b满足为

i?1i?1止。

这样的降维方法在理论上有保证，在计算上是可行的，故对高维问题，可用上述拉格朗日乘数法的思想来降低维数。

2。 逐次逼近法

这是另一种降维方法，先保持一个变量不变，对另一个变量实现最优化。然后交替地固定，以迭代的形式反复进行，直到获得某种要求为止。

先设x(0)??x(0)1,x(0)2,?,x(0)n?为满足?xi?1n(0)i?a的一个可行解，固定x在x(0)，先对y求解，则二维

分配问题变为一维问题：

(0)(0)(0)?g(x,y)?g(x,y)???g(x,yn)??max?111222nn?? ???y1?y2???yn?b,yi?0 且为整数可用对一维的方法来求解。设这解为y(0)(0)(0)??y1(0),y2,?,yn?，然后再固定y为y(0)，对x求解，即

n?(0)maxg(x,y)?iii??i?1 ?n?x?a,x?0 且为整数?ii??i?1设其解为x(k)(1)??x1(1),x2(1),?,xn(1)?，再固定x为x(1)，对y求解，这样依次轮换下去得到一系列的解

?x?，?y?(k?0,1,?)。

(k)因为

?gi(x,yi)??gi(x,y(0)i(0)ii?1i?1nn(0)i)??gi(xi(1),yi(0))，

i?1n?n(k)(k)?故函数值序列??gi(xi,yi)?是单调上升的，但不一定收敛到绝对的最优解，一般只收敛到某一局部?i?1?最优解。因此，在实际计算时，可选择几个初始点x一个最好的。

3．粗格子点法(疏密法)

在采用离散化的方法计算时，先将矩形定义域：0≤x≤a，0≤y≤b分成网格，然后在这些格子点上进行计算。如将a、b各分为m1和m2等份，则总共有(m1+1)·(m2+1)个格点，故对每个k值需要计算的fk(x,y)共有(m1+1)·(m2+1)个。因此，这里的计算量是相当大的。随着分点加多，格子点数也增多，那时的计算量将大得惊人。为了使计算可行，往往根据问题要求的精确度，采用粗格子点法逐步缩小区域来减少计算

量。

粗格子点法是先用少数的格子点进行粗糙的计算，在求出相应的最优解后，再在最优解附近的小范围内进一步细分，并求在细分格子点上的最优解，如此继续细分下去直到满足要求为止。这种方法可能会出现最优解“漏网”的情况，因此，应用此法时要结合对指标函数的特性进行分析。

1。3 固定资金分配问题

设有n个生产行业，都需要某两种资源。对于第k个生产行业，如果用第1种资源xk和第2种资源yk进行生产，可获得利润为rk(xk,yk)。若第1种资源的单位价格为a ，第2种资源的单位价格为b，现有资金Z。问应购买第1种资源多少单位(设为X)，第2种资源多少单位(设为Y)，分配到n个生产行业，使总利润最大?

此问题的数学模型可写为

(0)进行计算，然后从所得到的几个局部最优解中选出

nmax?rk(xk,yk)k?1?n??xk?X xk为非负整数?k?1 ?n ??yk?Y yk为非负整数?k?1?aX?bY?Z??(1) 把资源分配利润表换算成资金分配利润表，即将rk(xk,yk)换算成Rk(z), z?0,1,?,Z。但必须注意，分配的资金应先使较贵的资源单位最大。

设有资金z(0?z?Z)分配到第k个生产行业，则由Z?aX?bY知，在给定z的情况下，若购买第

2种资源yk单位，则留下的资金只能购买第1种资源xk单位，xk???z?byk?a??。于是得到资金利润函数?Rk(z)为

Rk(z)????z?byk?rk??yk?0,1,?,(z/b)???amax???,y?k?? ???式中(z/b)指以资金z购买第2种资源的最大单位数，购买第1种资源的最大单位数。

z?byka指以资金z购买了第2种资源yk单位以后能

(2) 计算最优资金分配所获得最大利润。规定最优值函数fk(z)表示以总的资金z分配到k至n个生产行业可能获得的最大利润。则有逆推关系式：

??Rk(zk)?fk?1(z?zk)??fk(z)?zkmax?0,1,?,z ???fn(z)?Rn(z)(3) 求出f1(z)，即为问题的解。这样，就把一个原含有两个状态变量的问题转化为只含有一个状态变量的问题。

二、生产与存储问题

在生产和经营管理中，经常遇到要合理地安排生产(或购买)与库存的问题，达到既要满足社会的需要，

又要尽量降低成本费用。因此，正确制定生产(或采购)策略，确定不同时期的生产量(或采购量)和库存量，以使总的生产成本费用和库存费用之和最小，这就是生产与存储问题的最优化目标。

2。1 生产计划问题

设某公司对某种产品要制定一项n个阶段的生产(或购买)计划。已知它的初始库存量为零，每阶段生产(或购买)该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应；在n阶段末的终结库存量为零。问该公司如何制定每个阶段的生产(或采购)计划，从而使总成本最小。

设dk为第k阶段对产品的需求量，xk为第k阶段该产品的生产量(或采购量)，vk为第k阶段结束时的产品库存量。则有vk?vk?1?xk?dk

ck(xk)表示第k阶段生产产品xk时的成本费用，它包括生产准备成本K和产品成本axk (其中a是单

位产品成本)两项费用。即

?0 当xk?0?ck(xk)??K?axk 当xk?1,2,?,m

?? 当x?mk?hk(vk)表示在第k阶段结束时有库存量vk所需的存储费用。

故k阶段的成本费用为ck(xk)?hk(vk) m表示每阶段最多能生产该产品的上限数。

上述问题的数学模型为

min g???ck(xk)?hk(vk)?k?1n?v0?0,vn?0?k?v??(x?d)?0 k?2,?,n?1

jj?k ?j?1?0?x?m k?1,2,?,nk???xk为整数 k?1,2,?,n用动态规划方法来求解，可看作一个n阶段决策问题。令vk?1为状态变量，它表示第k阶段开始时的库存量。xk为决策变量，它表示第k阶段的生产量。

状态转移方程为 vk?vk?1?xk?dk k?1,2,?,n

最优值函数fk(vk)表示从第1阶段初始库存量为0到第k阶段末库存量为vk时的最小总费用。 顺序递推关系式为：

fk(vk)?min?ck(xk)?hk(vk)?fk?1(vk?1)? k?1,?,n

0?xk??k其中?k?min(vk?dk,m)。这是因为一方面每阶段生产的上限为m；另一方面由于保证供应，故第k-1阶段末的库存量vk?1必须非负，即vk?dk?xk?0，所以xk?vk?dk。

边界条件为f0(v0)?0或f1(v1)?min?c1(x1)?h1(v1)?从边界条件出发，利用上面的递推关系式，对

x1??1

k?n?每个k ，计算出fk(vk)中的vk在0至min??dj,?(m?dj)?之间的值，最后求得的fn(0)即为所求的

j?1?j?k?1?最小总费用。

例3 某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如表9-5所示。

表9-5

时期(k) 需求量(dk) 1 2 2 3 3 2 4 4 假定该厂生产每批产品的固定成本为3千元，若不生产就为0；每单位产品成本为1千元；每个时期生产能力所允许的最大生产批量为不超过6个单位；每个时期末未售出的产品，每单位需付存储费0。5千元。还假定在第一个时期的初始库存量为0，第四个时期之末的库存量也为0。试问该厂应如何安排各个时期的生产与库存，才能在满足市场需要的条件下，使总成本最小。

解 用动态规划方法来求解，其符号含义与上面相同。

按四个时期将问题分为四个阶段。由题意知，在第k时期内的生产成本为

?0 当xk?0?ck(xk)??3?1?xk 当xk?1,2,?,6

?? 当x?6k?第k时期末库存量为vk时的存储费用为hk(vk)?0.5vk 故第k时期内的总成本为ck(xk)?hk(vk) 而动态规划的顺序递推关系式为

fk(vk)?min?ck(xk)?hk(vk)?fk?1(vk?dk?xk)?, k?2,3,4

0?xk??k其中?k?min(vk?dk,6)和边界条件f1(v1)?当k=1时，由 f1(v1)?x1?min(v1?d1,6)min?c1(x1)?h1(v1)?

x1?min(v1?2,6)min?c1(x1)?h1(v1)?

?4?对v1在0至min??dj,m?d1??min?9,6?2??4之间的值分别进行计算。

?j?2?v1?0 时， f1(0)?min?3?x1?0.5?0??5 所以x1?2x1?2v1?1 时， f1(1)?min?3?x1?0.5?1??6.5 所以x1?3

x1?3v1?2 时， f1(2)?min?3?x1?0.5?2??8 所以x1?4x1?4同理得

f1(3)?9.5 所以x1?5f1(4)?11 所以x1?6

2。2 不确定性的采购问题

在实际问题中，还会遇到某些多阶段决策过程，其状态转移不是完全确定的，出现了随机性因素，状态转移是按照某种已知概率分布取值的。

具有这种性质的多阶段决策过程称为随机性决策过程。

用动态规划方法也可处理这类随机性问题，又称为随机性动态规划。

例6 采购问题。某厂生产上需要在近五周内必须采购一批原料，而估计在未来五周内价格有波动，其浮动价格和概率已测得如表9-8所示。试求在哪一周以什么价格购入，使其采购价格的数学期望值最小，并求出期望值。

表9-8

单价 500 600 700 概率 0。3 0。3 0。4 解 价格是一个随机变量，按某种已知的概率分布取值。用动态规划方法处理，按采购期限5周分为5个阶段，将每周的价格看作该阶段的状态。设

yk——状态变量，表示第k周的实际价格。

xk——决策变量，xk =1时表示第k周决定采购；xk=0时表示第k周决定等待。 ykE——第k周决定等待，而在以后采取最优决策时采购价格的期望值。

fk(yk)——第k周实际价格为yk时，从第k周至第5周采取最优决策所得的最小期望值。

因而可写出逆序递推关系式为

fk(yk)?min?yk,ykE?, yk?skf5(yk)?y5, y5?s5其中 sk??500,600,700?, k?1,2,3,4,5由ykE和fk(yk)的定义可知：

(9?13)(9?14)

(9?15)

ykE?Efk?1(yk?1)?0.3fk?1(500)?0.3fk?1(600)?0.4fk?1(700)并且得出最优决策为：

(9?16)

??1(采购) 当fk(yk)?ykxk????0(等待) 当fk(yk)?ykE从最后一周开始，逐步向前递推计算，具体计算过程如下。

(9?17)

k=5时，因f5(y5)?y5,y5?s5，故有f5(500)?500,f5(600)?600,f5(700)?700 即在第五周时，若所需的原料尚未买入，则无论市场价格如何，都必须采购，不能再等。

k=4时，由(9-16)式可知

y4E?0.3f5(500)?0.3f5(600)?0.4f5(700)?0.3?500?0.3?600?0.4?700?610

于是，由(9-13)式得

f4(y4)?min?y4,y4E??min?y4,610?y4?s4y4?s4?500 若 y4?500???600 若 y4?600?610 若 y?7004?由(9-17)式，第4周最优决策为

?1(采购) 若 y4?500 或 600x4??

0(等待) 若 y?700?4同理求得

f3(y3)?min?y3,y3E??min?y3,574?y3?s3y3?s3 ?500 若 y3?500???574 若 y3?600 或 700所以 x3???1 若 y3?500?0 若 y3?600 或 700y2?s2y2?s2

f2(y2)?min?y2,y2E??min?y2,551.8? ?500 若 y2?500???551.8 若 y2?600 或 700所以 x2???1 若 y2?500?0 若 y2?600 或 700y1?s1y1?s1

f1(y1)?min?y1,y1E??min?y1,536.26? ?500 若 y1?500???536.26 若 y1?600 或 700所以 x1???1 若 y1?500?0 若 y1?600 或 700

由上可知，最优采购策略为：在第一、二、三周时，若价格为500就采购，否则应该等待；在第四周时，价格为500或600应采购，否则就等待；在第五周时，无论什么价格都要采购。

依照上述最优策略进行采购时，价格(单价)的数学期望值为

23333???500?0.3?1?0.7?0.7?0.7?0.7?0.4?600?0.30.7?0.4?0.7?????700?0.42?0.73

?500?0.80106?600?0.14406?700?0.05488?525.382?525且 0.8010?6

0.14?4060.?0 5

三、 背 包 问 题

有一个人带一个背包上山，其可携带物品重量的限度为a公斤。设有n种物品可供他选择装入背包中，这n种物品编号为1，2，…，n。已知第i种物品每件重量为wi公斤，在上山过程中的作用(价值)是携带数量xi的函数ci(xi)。问此人应如何选择携带物品(各几件)，使所起作用(总价值)最大。这就是著名的背包问题。类似的问题有工厂里的下料问题，运输中的货物装载问题，人造卫星内的物品装载问题等等。

设xi为第i种物品的装入件数，则问题的数学模型为

max f??ci(xi)i?1n ?nwx?a??ii?i?1?x?0 且为整数 (i?1,2,?,n)?i它是一个整数规划问题。如果xi只取0或1，又称为0—1背包问题。下面用动态规划方法来求解。

设按可装入物品的n种类划分为n个阶段。

状态变量w表示用于装第1种物品至第k种物品的总重量。

??w?xw 决策变量xk表示装入第k种物品的件数。则状态转移方程为wkk??w????允许决策集合为Dk(w)??xk0?xk????

??wk????最优值函数fk(w)是当总重量不超过w公斤，背包中可以装入第1种到第k种物品的最大使用价值。即

fk(w)?max?wixi?wk?c(x)

iii?1kxi?0且为整数(i?1,2,?,k)i?1因而可写出动态规划的顺序递推关系为：

f1(w)?fk(w)?x1?0,1,?,?w/w1?x1?0,1,?,?w/wk?max?c1(x1)max?ck(xk)?fk-1(w?wkxk)? 2?k?n

然后，逐步计算出f1(w),f2(w),?,fn(w)，及相应的决策函数x1(w),x2(w),?,xn(w)，最后得出的fn(a)就是所求的最大价值，其相应的最优策略由反推运算即可得出。

例7 max f?4x1?5x2?6x3

?3x1?4x2?5x3?10 ?x?0且为整数，i?1,2,3?i

解 用动态规划方法来解，此问题变为求f3(10)。

f3(10)?3x1?4x2?5x3?10xi?0,整数，i?1,2,3max?4x1?5x2?6x3??3x1?4x2?10?5x3xi?0,整数，i?1,2,3max?4x1?5x2?(6x3)??????max?6x3?max?4x1?5x2???max?6x3?f2(10?5x3)? 10?5x3?03x1?4x2?10?5x3x3?0,1,2?x3?0,整数?x?0,x?0,整数?12??max?0?f2(10),6?f2(5),12?f2(0)?由此看到，要计算f3(10)，必须先计算出f2(10),f0(5),f2(0)

f2(10)?3x1?4x2?10x1?0,x2?0,整数max?4x1?5x2??3x1?10?4x2x1?0,x2?0,整数max?4x1?(5x2)??????max?5x2?max(4x1)??max?5x2?f1(10?4x2)?10?4x2?03x1?10?4x2x2?0,1,2?x2?0,整数?x?0,整数?1??max?f1(10),5?f1(6),10?f1(2)?f2(5)?f2(0)?3x1?4x2?5x1?0,x2?0,整数

max?4x1?5x2??max?5x2?x?0,12f1(5?4x2)??max?f1(5),5?f1(1)?f1(0?4x2)??f1(0)3x1?4x2?0x1?0,x2?0,整数max?4x1?5x2??max?5x2?x?02为了要计算出f2(10),f2(5),f2(0)，必须先计算出f1(10),f1(6),f1(5),f1(2),f1(1),f1(0)，一般地有

f1(w)?max(4x1)?4?(不超过w/3的最大整数)?4??w/3?

3x1?wx1?0,整数相应的最优决策为x1=［w/3］，于是得到

f1(10)?4?3?12 (x1?3);f1(6)?4?2?8 (x1?2)f1(5)?4?1?4 (x1?1);f1(2)?4?0?0 (x1?0) f1(1)?4?0?0 (x1?0);f1(0)?4?0?0 (x1?0)从而

f2(10)?max?f1(10),5?f1(6),10?f2(0)??max?12,5?8,10?0??13 (x1?2,x2?1)f2(5)?max?f1(5),5?f1(1)??max?4,5?0??5 (x1?0,x2?1)f2(0)?f1(0)?0 (x1?0,x2?0)故最后得到

f3(10)?max?f2(10),6?f2(5),12?f2(0)??max?13,6?5,12?0??13 (x1?2,x2?1, x3?0)所以，最优装入方案为x1?2,x2?1,x3?0，最大使用价值为13。

***

如果再增加对背包体积的限制为b，并假设第i种物品每件的体积为vi立方米，问应如何装使得总价值最大。这就是“二维背包问题”，它的数学模型为

nmax f??ci(xi)i?1?n??wixi?a?i?1 n???vixi?b?i?1?xi?0,整数，i?1,2,?,n??用动态规划方法来解。这时，状态变量是两个(重量和体积的限制)，决策变量仍是一个(物品的件数)。设最优值函数为fk(w,v)表示当总重量不超过w公斤，总体积不超过v立方米时，背包中装入第1种到第k种物品的最大使用价值。故

fk(w,v)?max?wixi?wki?1k?c(x)

iii?1k?vixi?vi?1xi?0,整数i?1,2,?,k因而可写出顺序递推关系式为

fk(w,v)???w0?xk?min???w??kmax??v?,???vk????????ck(xk)?fk?1(w?wkxk,v?vkxk)?

1?k?nf0(w,v)?0最后算出fn(a,b)即为所求的最大价值。

四、复合系统工作可靠性问题

若某种机器的工作系统由n个部件串联组成，只要有一个部件失灵，整个系统就不能工作。为提高系统工作的可靠性，在每一个部件上均装有主要元件的备用件，并且设计了备用元件自动投入装置。显然，备用元件越多，整个系统正常工作的可靠性越大。但备用元件多了，整个系统的成本、重量、体积均相应加大，工作精度也降低。因此，最优化问题是在考虑上述限制条件下，应如何选择各部件的备用元件数，使整个系统的工作可靠性最大。

设部件i(i?1,2,?,n)上装有ui个备用件时，它正常工作的概率为pi(ui)。因此，整个系统正常工作的可靠性，可用它正常工作的概率衡量。即P??pi(ui)。

i?1n设装一个部件i备用元件费用为ci，重量为wi，要求总费用不超过c，总重量不超过w，则这个问题

有两个约束条件，它的静态规划模型为：

max P??pi(ui)i?1n ?ncu?c;wu?w??ii?iii?1?i?1?u?0且为整数，i?1,2,?,n?in这是一个非线性整数规划问题，因ui要求为整数，且目标函数是非线性的。此问题用动态规划方法来解，比较容易。

为构造动态规划模型，根据两个约束条件，取二维状态变量，采用两个状态变量：

xk——由第k个到第n个部件所容许使用的总费用。 yk——由第k个到第n个部件所容许具有的总重量。

决策变量uk为部件k上装的备用元件数，这里决策变量是一维的。 这样，状态转移方程为：xk?1?xk-ukck;yk?1?yk?ukwk (1?k?n)

m??inxk?允许决策集合为 Dk(xk,yk)?uk:0?uk??/c?k,yk/w ???k最优值函数fk(xk,yk)为由状态xk和yk出发，从部件k到部件n的系统的最大可靠性。 因此，整机可靠性的动态规划基本方程为：

?fk(xk,yk)?max?pk(uk)fk?1(xk?ckuk,yk?wkuk)?uk?Dk(xk,yk)?? ? k?n,n?1,?,1?f(x,y)?1n?1n?1n?1??边界条件为1，这是因为xn?1、yn?1均为零，装置根本不工作，故可靠性当然为1。最后计算得f1(c,w)，即为所求问题的最大可靠性。

例8 某厂设计一种电子设备，由三种元件D1,D2,D3组成。已知这三种元件的价格和可靠性如表9-9所示，要求在设计中所使用元件的费用不超过105元。试问应如何设计使设备的可靠性达到最大(不考虑重

量的限制)。

表9-9

元件 D1 D2 D3 单位/元 30 15 20 可靠性 0。9 0。8 0。5 解 按元件种类划分为三个阶段，设状态变量sk表示能容许用在Dk元件至D3元件的总费用；决策

变量xk表示在Dk元件上的并联个数；pk表示一个Dk元件正常工作的概率，则(1?pk)k为xk个Dk元件不正常工作的概率。令最优值函数fk(sk)表示由状态sk开始从Dk元件至D3元件组成的系统的最大可靠性。因而有

xf3(s3)?f2(s2)?x3?max?1?(0.5)?1?x3??s3/20??1?x2??s2/15maxf1(s1)?max1?x1??s1/30??1?(0.2)??f(s?15x)? ????1?(0.1)??f(s?30x)???x2322x1211由于s1=105，故此问题为求出f1(105)即可。

而 f1(105)?max?1?(0.1)x1?f(105 ?30x)1?max?0.9f(75),0.99f(45),0.999f(15)2222?1?x1?3??但f2(75)?max?1?(0.2)x2?f3(75-15x2)?max?0.8f3(60),0.96f3(45),0.992f3(30),0.9984f3(15)?

1?x2?4??可是 f3(60)?max1?(0.5)x3max?0.5,0.75,0.875??0.875

1?x3?3f3(45)?max?0.5,0.75??0.75 f3(30)?0.5

f3(15)?0所以f2(75)?max?0.8?0.875,0.96?0.75,0.992?0.5,0.9984?0??max?0.7,0.72,0.496??0.72 同理 f2(45)?max?0.8f3(30),0.96f3(15)??max?0.4,0??0.4

f2(15)?0

故 f1(105)?max?0.9?0.72,0.99?0.4,0.999?0??max?0.648,0.396??0.648。 从而求得x1?1,x2?2,x3?2为最优方案，即D1元件用1个， D2元件用2个，D3元件用2个。其总费用为100元，可靠性为0。648。

五、排序问题

设有n个工件需要在机床A、B上加工，每个

工件都必须经过先A而后B的两道加工工序(见图9-1)。以ai、bi分别表示工件i(1?i?n)在A、B上的加工时间。问应如何在两机床上图9-1安排各工件加工的顺序，使在机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少?

图9-1

下面用动态规划方法来研究同顺序两台机床加工n个工件的排序问题。

当加工顺序取定之后，工件在A上加工时没有等待时间，而在B上则常常等待。因此，寻求最优排序方案只有尽量减少在B上等待加工的时间，才能使总加工时间最短。设第i个工件在机床A上加工完毕以后，在B上要经过若干时间才能加工完，故对同一个工件来说，在A、B上总是出现加工完毕的时间差， 我们以它来描述加工状态。

现在，我们以在机床A上更换工件的时刻作为时段。以X表示在机床A上等待加工的按取定顺序排列的工件集合。以x表示不属于X的在A上最后加工完的工件。以t表示在A上加工完x的时刻算起到B上加工完x所需的时间。这样，在A上加工完一个工件之后，就有(X，t)与之对应。

选取(X，t)作为描述机床A、B在加工过程中的状态变量。这样选取状态变量，则当X包含有s个工件时，过程尚有s段，其时段数已隐含在状态变量之中，因而，指标最优值函数只依赖于状态而不明显依赖于时段数。

令f(X,t)为由状态(X，t)出发，对未加工的工件采取最优加工顺序后，将X中所有工件加工完所需时间。

f(X,t,i)为由状态(X，t)出发，在A上加工工件i后，对以后未加工的工件采取最优加工顺序后，将

X中所有工件加工完所需时间。

f(X,t,i,j)为由状态(X，t)出发，在A上相继加工工件i与j后，对以后加工的工件采取最优顺序后，

将X中的工件全部加工完所需要的时间。

不难得到 f(X,t,i)???ai?f(X/i,t?ai?bi) 当t?ai时?ai?f(X/i,bi) 当t?ai时

记zi(t)?max (t?ai,0)?bi，上式就可合并写成f(X,t,i)?ai?f?X/i,zi(t)? 其中X/i表示在集合X中去掉工件i后剩下的工件集合。

由定义，可得 f(X,t,i,j)?ai?aj?f ??X/?i,j?,zij(t)??

其中zij(t)是在机床A上从X出发相继加工工件i、j，并从它将j加工完的时刻算起，至在B上相继加工工件i、j并将工件加工完所需时间。故(X/?i,j?,zi j(t))是在A加工i、j后所形成的新状态。即在机床A上加工i、j后由状态(X，t)转移到状态(X/?i,j?,zi j(t))。

仿照zi(t)的定义，以X/?i,j?代替X/?i?，zi(t)代替t，aj代替ai，bj代替bi，则可得

zi j(t)?max??zi(t)?aj,0???bj

j故

zi j(t)?max?max(t?ai,0)?bi?aj,0??bjj?i??max?maxt?ai?aj?bi,bi?aj),0??bj j?i??max??t?ai?aj?bi?bj,bi?bj?aj,bj??i,j

将i、j对调，可得

f(X,t,j,i)?ai?aj?f??X/?i,j?,zji(t)??zj i(t)?max?t?ai?aj?bi?bj,bi?bj?ai,bi??i,j?

由于f(X,t)为t的单调上升函数，故当zi j(t)?zj i(t)时，有f(X,t,i,j)?f(X,t,j,i)

因此，不管t为何值，当zi j(t)?zj i(t)时，工件i放在工件j之前加工可以使总的加工时间短些。而由zi j(t)和zj i(t)的表示式可知，这只需要下面不等式成立就行。即

max (bi?bj?aj,bj)?max (bi?bj?ai,bi)

i,ji,j将上不等式两边同减去bi与bj，得max (?aj,?bi)?max (?ai,?bj)

i,ji,j即有 min(ai,bj)?min(aj,bi)

i,ji,j这个条件就是工件i应该排在工件j之前的条件。即对于从头到尾的最优排序而言，所有前后相邻接

的两个工件所组成的对，都必须满足上述不等式。根据这个条件，得到最优排序规则如下：

(1) 先给出工件加工时间的工时矩阵M???a1 a2?an??

?b1 b2?bn?(2) 在工时矩阵M中找出最小元素；若它在上行，则将相应的工件排在最前位置；若它在下行，则将相应的工件排在最后位置。

(3) 将排定位置的工件所对应的列从M中划掉，然后对余下的工件重复按(2)进行。但那时的最前位置(或最后位置)是在已排定位置的工件之后(或之前)。如此继续下去，直至把所有工件都排完为止。

例9 设有5个工件需在机床A、B上加工，加工的顺序是先A后B，每个工件所需加工时间(单位：小时)如表9-10所示。问如何安排加工顺序，使机床连续加工完所有工件的加工总时间最少?并求出总加工时间。

表9-10

加工时间 机床 工件号码 1 2 3 4 5 解 工件的加工工时矩阵为

A 3 7 4 5 7 B 6 2 7 3 4

?3M???6根据最优排序规则，故最优加工顺序为：

7247537? 4??1?3?5?4?2

总加工时间为28小时。

六、 设备更新问题

在工业和交通运输企业中，经常碰到设备陈旧或部分损坏需要更新的问题。从经济上来分析，一种设备应该用多少年后进行更新为最恰当，即更新的最佳策略应该如何，从而使在某一时间内的总收入达到最大(或总费用达到最小)。

现以一台机器为例，随着使用年限的增加，机器的使用效率降低，收入减少，维修费用增加。而且机器使用年限越长，它本身的价值就越小，因而更新时所需的净支出费用就愈多。设：

Ij(t)—— 在第j年机器役龄为t年的一台机器运行所得的收入。 Oj(t)—— 在第j年机器役龄为t年的一台机器运行时所需的运行费用。 Cj(t)—— 在第j年机器役龄为t年的一台机器更新时所需更新净费用。

?—— 折扣因子(0???1)，表示一年以后的单位收入的价值视为现年的?单位。

T —— 在第一年开始时，正在使用的机器的役龄。n —— 计划的年限总数。

gj(t)—— 在第j年开始使用一个役龄为t年的机器时，从第j年至第n年内的最佳收入。 xj(t)—— 给出gj(t)时，在第j年开始时的决策(保留或更新)。

为了写出递推关系式，先从两方面分析问题。若在第j年开始时购买了新机器，则从第j年至第n年得到的总收入应等于在第j年中由新机器获得的收入，减去在第j年中的运行费用，减去在第j年开始时役龄为t年的机器的更新净费用，加上在第j+1年开始使用役龄为1年的机器从第j+1年至第n年的最佳收入；若在第j年开始时继续使用役龄为t年的机器，则从第j年至第n年的总收入应等于在第j年由役龄为t年的机器得到的收入，减去在第j年中役龄为t年的机器的运行费用，加上在第j+1年开始使用役龄为t+1年的机器从第j+1年至第n年的最佳收入。然后，比较它们的大小，选取大的，并相应得出是更新还是保留的决策。

将上面的分析写成数学形式，即得递推关系式为：

?R:Ij(0)?Oj(0)?Cj(t)??gj?1(1)?gj(t)?max??K:I(t)?O(t)??g(t?1)??jjj?1??

(j?1,2,?,n ; t?1,2,?,j?1,j?T?1)其中“K”是Keep的缩写，表示保留使用；“R”是Replacement的缩写，表示更新机器。

由于研究的是今后n年的计划，故还要求gn?1(t)?0

例10 假设n?5,??1,T?1，其有关数据如表9-11所示。试制定5年中的设备更新策略，使在5年内的总收入达到最大。

表9-11

产品年序 机龄 项目 收入 运行费用 更新费用 第一年 0 1 2 3 4 0 第二年 1 2 3 第三年 0 1 2 第四年 第五年 0 1 0 32 4 34 期前 1 2 3 4 5 18 16 16 14 14 8 8 9 9 10 32 34 36 36 38 22 21 20 18 16 27 25 24 22 29 26 24 30 28 6 6 8 8 10 5 6 8 9 5 5 6 4 5 27 29 32 34 37 29 31 34 36 31 32 33 32 33

解 因第j年开始机龄为t年的机器，其制造年序应为j?t年，因此，I5(0)为第五年新产品的收入，

O3(2) =8。I3(2)为第一年的产品其机龄为2年的收入，)(故I5(0)=32。故I3(2)=20。同理O5(0)=4，而C51是第5年机龄为1年的机器(应为第四年的产品)的更新费用，故C5(1)=33 。同理C5(2)=33，C3(1) =31，其余类推。

当j=5时，由于设T=1 ，故从第5年开始计算时，机器使用了1、2、3、4、5年，则递推关系式为

?R:I5(0)?O5(0)?C5(t)?1?g6(1)?g5(t)?max ??

K:I(t)?O(t)?1?g(t?1)556??因此 g5(1)?max ??R:32?4?33?0??5??23 所以 x5(1)?K ??K:28?5?0?23??R:32?4?33?0??5?g5(2)?max ???18 所以 x5(2)?K

K:24?6?0?18??同理 g5(3)?13,x5(3)?K; g5(4)?6,x5(4)?K;g5(5)?4,x5(5)?K

当j=4时，递推关系为 g4(t)?max? )O0)C4?t()g?R:I4(0?4(?5?(1)?

t)?O4t(?)g5t?(1)??K:I4(? R:30?4?32?23?17?故 g4(1)?max???39 所以 x4(1)?K

K:26?5?18?39??同理 g4(2)?29,x4(2)?K;g4(3)?16,x4(3)?K;g4(4)?13,x4(4)?R

?R:I3(0)?O3(0)?C3(t)?g4(1)?当j=3时，有 g3(t)?max ??

K:I(t)?O(t)?g(t?1)334???R:29?5-31?39?32?g(1)?max 故 3?K:25?6?29?48??48 所以 x3(1)?K ??同理 g3(2)?31,x3(2)?R;g3(3)?27,x3(3)?R

?R:I2(0)?O2(0)?C2(t)?g3(1)?当j=2时，有g2(t)?max ??

K:I(t)?O(t)?g(t?1)223??故 g2(1)?max ??R:27?5?29?48?41??46 所以 x2(1)?K ??K:21?6?31?46??R:27?5?34?48?36?g2(2)?max ???36 x2(2)?R

K:16-8?27?35??

当j=1时，有 g1(t)?max ??R:I1(0)?O1(0)?C1(t)?g2(1)??

K:I(t)?O(t)?g(t?1)?112??R:22?6?32?46?30?故 g1(1)?max ???46 所以 x1(1)?K

K:18?8?36?46??根据上面计算过程反推之，可求得最优策略如表9-12，相应最佳收益为46单位。

表9-12

年 1 2 3 4 5

七、 货郎担问题

机龄 1 2 1 2 3 最 佳 策 略 K R K K K 货郎担问题在运筹学里是一个著名的命题。有一个串村走户卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄。问应如何选择行走路线，能使总的行程最短。类似的问题有旅行路线问题，应如何选择行走路线，使总路程最短或费用最少等。

现在把问题一般化。设有n个城市，以1，2，…，n表示之。dij表示从i城到j城的距离。一个推销员从城市1出发到其他每个城市去一次且仅仅是一次，然后回到城市1。问他如何选择行走的路线，使总的路程最短。这个问题属于组合最优化问题，当n不太大时，利用动态规划方法求解是很方便的。

由于规定推销员是从城市1开始的，设推销员走到i城，记

Ni??2,3,?,i?1,i?1,?,n?表示由1城到i城的中间城市集合。

S表示到达i城之前中途所经过的城市的集合，则有S?Ni

因此，可选取(i，S)作为描述过程的状态变量，决策为由一个城市走到另一个城市，并定义最优值函数fk(i,S)为从1城开始经由k个中间城市的S集到i城的最短路线的距离，则可写出动态规划的递推关系为

fk(i,S)?min??fk?1(j,S\\?j?)?dj i??j?s

(k?1,2,?,n?1 。i?2,3,?,n 。S?Ni)边界条件为f0(i,?)?d1i

Pk(i,S)为最优决策函数，它表示从1城开始经k个中间城市的S集到i城的最短路线上紧挨着i城前

面的那个城市。

例11 求解四个城市旅行推销员问题，其距离矩阵如表9-13所示。当推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，使总的行程距离最短。

表9-13

i 距离 j 1 2 3 4 0 6 7 9 8 0 9 7 5 8 0 9 6 5 5 0 1 2 3 4 解 由边界条件可知：f0(2,?)?d12?8,f0(3,?)?d13?5,f0(4,?)?d14?6 当k=1时，即从1城开始，中间经过一个城市到达i城的最短距离是：

f1(2,?3?)?f0(3,?)?d32?5?9?14f1(2,?4?)?f0(4,?)?d42?6?7?13f1(3,?2?)?8?8?16 f1(3,?4?)?6?8?14f1(4,?2?)?8?5?13 f1(4,?3?)?5?5?10当k=2时，即从1城开始，中间经过二个城市(它们的顺序随便)到达i城的最短距离是：

f2(2,[3,4])?min ??f1(3,?4?)?d32, f1(4,?3?)?d42???min ?14?9,10?7??17 所以 p2(2,?3,4?)?4f2(3,?2,4?)?min ?13?8,13?8??21 所以 p2(3,?2,4?)?2或4f2(4,?2,3?)?min ?14?5,16?5??19 所以 p2(4,?2,3?)?2当k=3时，即从1城开始，中间经过三个城市(顺序随便)回到1城的最短距离是：

f3(1,?2，3，4?)?min ??f2(2,?3,4?)?d21,f2(3,?2,4?)?d31,f2(4,?2,3?)?d41???min ?17?6,21?7,19?9??23所以 p3(1,?2,3,4?)?2

由此可知，推销员的最短旅行路线是1→3→4→2→1，最短总距离为23。

本文来源：https://www.bwwdw.com/article/dptx.html