《运筹学》课程授课教案（讲稿）第25讲 动态规划的应用举例

课程名称：《运筹学》第_22_讲次授课题目动态规划的应用举例本讲目的要求及重点难点：【目的要求】了解和掌握若干典型问题的动态规划模型及求解技巧：如最短路线、资源分配、生产计划、货物存储、设备更新与系统可靠性问题、背包问题、推销商问题等。【重点及难点】动态规划问题的具体应用。内容[本讲课程的引入]动态规划应用十分广泛，本节通过几个具体实例展示它在管理领域的应用，并进-步阐述动态规划方法。[本讲课程的内容]一、资源分配问题资源分配问题就是将一定数量的一种或若干种资源（原材料、资金、设备等）合理分配给若干使用者，使得资源分配后总结果最优。一种资源的分配问题称为一维资源分配问题，两种资源的分配问题称为二维资源分配问题。假设有一种资源，数量为α，将其分配给n个使用者，分配给第i个使用者数量x,时，相应的收益为gi（x），问如何分配使得总收入最大？这就是一维资源分配问题，该问题的数学模型为：max z=gi(xi)+g2(x2)+...+g.(xn)x+x+..+x=a[x, ≥0 i=1,2,,n解按变量个数划分阶段，k=1，2，，n；设决策变量u=x，表示分配给第k个使用者的资源数量设状态变量为sk，表示分配给第k个至第n个使用者的总资源数量；状态转移方程：Sk+I=S-X，其中s=a;允许决策集合：Dk（s）=（x/0≤x≤s）阶段指标函数：Ve（sk，u）=gk（x）表示分配给第k个使用者数量x时的收益；最优指标函数f（st）表示以数量s的资源分配给第k个至第n个使用者所得到的最大收益，则动态规划基本方程为：

课程名称：《运筹学》 第 22 讲次 授课题目 动态规划的应用举例 本讲目的要求及重点难点： 目的要求] 了解和掌握若干典型问题的动态规划模型及求解技巧：如最短路线、资源分 配、生产计划、货物存储、设备更新与系统可靠性问题、背包问题、推销商问题等。 [重点及难点] 动态规划问题的具体应用。 内 容 [本讲课程的引入] 动态规划应用十分广泛，本节通过几个具体实例展示它在管理领域的应用，并进一 步阐述动态规划方法。 [本讲课程的内容] 一、资源分配问题 资源分配问题就是将一定数量的一种或若干种资源（原材料、资金、设备等）合理分配给若干使 用者，使得资源分配后总结果最优。一种资源的分配问题称为一维资源分配问题，两种资源的分 配问题称为二维资源分配问题。 假设有一种资源，数量为 a，将其分配给 n 个使用者，分配给第 i 个使用者数量 xi 时，相应的收 益为 gi（xi），问如何分配使得总收入最大？这就是一维资源分配问题，该问题的数学模型为：              x i n x x x a z g x g x g x i n n n 0 1,2, , max ( ) ( ) ( ) 1 2 1 1 2 2    解 按变量个数划分阶段，k=1，2，.，n； 设决策变量 uk=xk，表示分配给第 k 个使用者的资源数量； 设状态变量为 sk，表示分配给第 k 个至第 n 个使用者的总资源数量； 状态转移方程：sk+1=sk－xk，其中 s1=a； 允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝ 阶段指标函数：vk（sk，uk）=gk（xk）表示分配给第 k 个使用者数量 xk 时的收益； 最优指标函数 fk（sk）表示以数量 sk的资源分配给第 k 个至第 n 个使用者所得到的最大收益，则 动态规划基本方程为：

内容fr(s)=max [g(x)+fk+1(Sh+1)k=n,,l0≤xSsfu+I(sn+1)=0由后向前逐段递推，f（α）即为所求问题的最大收益。例5-6某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表5-4所示。试问在各地区如何设置销售点可使每月总利润最大。表 5-4销售点地区23014300162532120121721220310141617解如前所述，建立动态规划数学模型：将问题分为3个阶段，k=1，2，3；决策变量x表示分配给第k个地区的销售点数；状态变量为S表示分配给第k个至第3个地区的销售点总数；状态转移方程：Sk+I=Sk一Xk，其中s/=4；允许决策集合：Dk（s）=（xl0≤x≤sk）阶段指标函数：gk（x）表示x个销售点分配给第k个地区所获得的利润；最优指标函数f（sk）表示将数量为s的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：fe(st)=max[g(xx)+ fk+(sh-x))k= 3,2,10≤XSSAf.(s.)= 0k=3 时,f.(s,)=max[g,(x,))Xj=5数值计算如表5-5所示。表 5-5g3 (xg)3fi(s3)X312304S30000110101214214316316441717

内 容               ( ) 0 ( ) max [ ( ) ( )] , ,1 1 1 1 1 0 n n k k k k x s k k f s f s g x f s k n k k  由后向前逐段递推，f1（a）即为所求问题的最大收益。 例 5-6 某公司打算在 3 个不同的地区设置 4 个销售点，根据市场部门估计，在不同地区 设置不同数量的销售点每月可得到的利润如表 5-4 所示。试问在各地区如何设置销售点可使 每月总利润最大。 表 5-4 地区 销售点 0 1 2 3 4 1 2 3 0 0 0 16 12 10 25 17 14 30 21 16 32 22 17 解 如前所述，建立动态规划数学模型： 将问题分为 3 个阶段，k=1，2，3； 决策变量 xk表示分配给第 k 个地区的销售点数； 状态变量为 sk表示分配给第 k 个至第 3 个地区的销售点总数； 状态转移方程：sk+1=sk－xk，其中 s1=4； 允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝ 阶段指标函数：gk（xk）表示 xk 个销售点分配给第 k 个地区所获得的利润； 最优指标函数 fk（sk）表示将数量为 sk 的销售点分配给第 k 个至第 3 个地区所得到的最 大利润，动态规划基本方程为：             ( ) 0 ( ) max [ ( ) ( )] 3,2,1 4 4 1 0 f s f s g x f s x k k k k k k x s k k k k k=3 时， ( ) max[ ( )] 3 3 3 3 3 3 f s g x x s  数值计算如表 5-5 所示。 表 5-5 g3（x3） f3(s3) x3 * 0 1 2 3 4 0 1 2 3 4 0 10 14 16 17 0 10 14 16 17 0 1 2 3 4 f x3 s3

内?容k=2 时,f,(s,)=max[g2(x,)+ f;(s, -x,)]JSxSs计算结果见表5-6所示。表5-6g2(x2)+f(s2—x2)专fe(s2)X23s?0140000112+0120+10120+1412+1017+022132720+1612+1417+1021+040+173112+1617+1421+1022+02.3k=1 时，f(s,)= max[gi(x,)+ f2(s, -x,))0≤x≤Sk=1时，只有si=4的情况。.(s)= max[g,(x)+ f2(4-x,)0≤x≤4计算结果如表5-7所示。表5-7gi(xi)+f(s1x1)fi(st)XiXS10123440+3116+2725+2230+1232+0472所以最优解为：x=2，x2=1，x3=-1，J(4)=47，即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。例5-7机器负荷问题某工厂有100台机器，拟分四期使用，每一期都可在高、低两种不同负荷下进行生产。若把x台机器投入高负荷下进行生产，则在本期结束时将有1/3x台机器损坏报废：余下的机器全部投入低负荷下进行生产，则在期末有1/10的机器报废。如果高负荷下生产时每台机器可获利润为10，低负荷下生产时每台机器可获利润为7，问怎样分配机器使四期的总利润最大？解将问题按周期分为4个阶段，k-1，2，3，4；

内 容 k=2 时， ( ) max [ ( ) ( )] 2 2 3 2 2 0 2 2 2 2 f s g x f s x x s      计算结果见表 5-6 所示。 表 5-6 g2(x2)+f3(s2－x2) f2(s2) x2 * 0 1 2 3 4 0 1 2 3 4 0 0+10 0+14 0+16 0+17 12+0 12+10 12+14 12+16 17+0 17+10 17+14 21+0 21+10 22+0 0 12 22 27 31 0 1 1 2 2,3 k=1 时， ( ) max [ ( ) ( )] 1 1 2 1 1 0 1 1 1 1 f s g x f s x x s      k=1 时，只有 s1=4 的情况。 ( ) max[ ( ) (4 )] 1 1 2 1 0 4 1 1 1 f s g x f x x      计算结果如表 5-7 所示。 表 5-7 g1(x1)+f2(s1－x1) f1(s1) x1 * 0 1 2 3 4 4 0+31 16+27 25+22 30+12 32+0 47 2 所以最优解为：x1 * =2，x2 * =1，x3 * =1，f1(4)=47，即在第 1 个地区设置 2 个销售点，第 2 个地区设置 1 个销售点，第 3 个地区设置 1 个销售点，每月可获利润 47。 例 5-7 机器负荷问题 某工厂有 100 台机器，拟分四期使用，每一期都可在高、低两种不同负荷下进行生产。 若把 x 台机器投入高负荷下进行生产，则在本期结束时将有 1/3x 台机器损坏报废；余下的 机器全部投入低负荷下进行生产，则在期末有 1/10 的机器报废。如果高负荷下生产时每台 机器可获利润为 10，低负荷下生产时每台机器可获利润为 7，问怎样分配机器使四期的总利 润最大？ 解 将问题按周期分为 4 个阶段，k=1，2，3，4； f x2 s2 f x1 s1

内容状态变量s表示第k阶段初完好的机器数，Si=100，0≤s≤100；决策变量x表示第k阶段投入高负荷下生产的机器数，则S一x表示第k阶段投入低负荷下生产的机器数：允许决策集合：Dk（s）=（x/0≤x≤sk）状态转移方程：Sk+I=Tk（sk，xk），即第k+1阶段初拥有的完好机器数Sk+I为：29-(SK-X);Sk3×+10X+阶段指标函数：Vk（sk，x）=10x+7（sk—x）表示第k阶段所获得的利润；最优指标函数f（st）表示从第k阶段初完好机器数为s至第四阶段的最大利润，动态规划基本方程为：fi(s,)= max [v (st,x,)+ fk+I(Sk+)]k = 4.3,2,10SxSsfs(ss)=0k=4 时,f4(s4)=max [10x4 +7(s4-x4)]= max (3x4 +7s4)=10s4X4 =S40SX≤s0SyS4k=3 时,fs(s,)=max[10x, +7(ss -x,)+f(s4)0≤x3S53max[10x,+7(s-x,+10s]=0SxSsy2x +9=max10x;+7(x)+10+(s,-x)0≤x3S532= max (_x3 +16ss)0≤xg≤s33503.. X3=S3k=2 时,f2(s2)= max [10x2 +7(s2 -x2)+ fs(s,)]0≤2≤5250= max [10x, +7(s, - x2) +S,J30S.x2 ≤3250,29max 10x, +7(s2-X5X2S100≤x2S52338=max(22s5）90558=22S2

内 容 状态变量 sk 表示第 k 阶段初完好的机器数，s1=100，0≤sk≤100； 决策变量 xk表示第 k 阶段投入高负荷下生产的机器数， 则 sk－xk表示第 k 阶段投入低负荷下生产的机器数； 允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝ 状态转移方程：sk+1=Tk（sk，xk），即第 k+1 阶段初拥有的完好机器数 sk+1 为： ( ) 10 9 3 2 k 1 k k k s  x  s  x  ； 阶段指标函数：vk（sk，xk）=10xk+7（sk－xk）表示第 k 阶段所获得的利润； 最优指标函数 fk（sk）表示从第 k 阶段初完好机器数为 sk 至第四阶段的最大利润，动态 规划基本方程为：             ( ) 0 ( ) max [ ( , ) ( )] 4,3,2,1 5 5 1 1 0 f s f s v s x f s k k k k k k x s k k k k k=4 时， 4 4 4 0 4 4 4 0 4 ( 4 ) max [10 7( )] max (3 7 ) 10 4 4 4 4 f s x s x x s s x s x s           x4 * =s4 k=3 时， 3 3 3 0 3 3 3 3 3 3 0 3 3 3 4 0 3 3 3 4 4 0 3 3 3 50 16 ) 3 2 max ( ( )] 10 9 3 2 max 10 7( ) 10[ max [10 7( ) 10 ] ( ) max [10 7( ) ( )] 3 3 3 3 3 3 3 3 s x s x s x x s x x s x s f s x s x f s x s x s x s x s                                ∴ x3 * =s3 k=2 时， 2 2 2 0 2 2 2 2 2 2 0 2 2 2 3 0 2 2 2 3 3 0 2 2 22 ) 9 8 max (22 ( )] 10 9 3 2 [ 3 50 max 10 7( ) ] 3 50 max [10 7( ) ( ) max [10 7( ) ( )] 2 2 2 2 2 2 2 2 s s x x s x x s x x s x s f s x s x f s x s x s x s x s                               

内?容: x2=0k=1 时,f,(s,) = max[10x, +7(s, -x,)+ f,(s,)]0≤X,≤s= max[10x, +7(s, -x,)+22s2]0S.XI SS)29max10x, + 7(s, -x,)+22[=x, +=(s, -x,))0≤xs10313432VmaxXS1-5150≤xjs134S.. x=0因为S=100，所以f（100）=2680，逆向追踪得：Si=100,xi'=092x2'=0-(s -x)= 90S2 =34+102.9专+x; =s;=81(s2-x,)=81S3=1032*.9(ss-x)=54x4=S4=54S4 =+3310即，第1，2期把全部完好机器投入低负荷下生产，第3，4期把全部完好机器投入高负荷下生产所得利润最大。、生产计划问题在企业生产经营活动中，经常会遇到如何合理安排生产、库存及销售计划，使总效益最高的问题，这一类问题统称为生产计划问题。例5-8（生产一库存问题）某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。解以每个时期作为一个阶段，该问题分为4个阶段，k1，2，3，4；决策变量x表示第k阶段生产的产品数；状态变量s表示第k阶段初的库存量：

内 容 ∴ x2 * =0 k=1 时， 1 1 1 0 1 1 1 1 1 1 0 1 1 1 2 0 1 1 1 2 2 0 1 1 5 134 ) 15 32 5 134 max ( ( )] 10 9 3 2 max 10 7( ) 22[ max [10 7( ) 22 ] ( ) max [10 7( ) ( )] 1 1 1 1 1 1 1 1 s s x x s x x s x x s x s f s x s x f s x s x s x s x s                                ∴ x1 * =0 因为 s1=100，所以 f1（100）=2680，逆向追踪得： s1=100， x1 * =0 ( ) 90 10 9 3 2 * 1 1 * s2  x1  s  x  x2 * =0 ( ) 81 10 9 3 2 * 2 2 * s3  x2  s  x  x3 * =s3=81 ( ) 54 10 9 3 2 * 3 3 * s4  x3  s  x  x4 * =s4=54 即，第 1，2 期把全部完好机器投入低负荷下生产，第 3，4 期把全部完好机器投入高负 荷下生产所得利润最大。 二、生产计划问题 在企业生产经营活动中，经常会遇到如何合理安排生产、库存及销售计划，使总效益最 高的问题，这一类问题统称为生产计划问题。 例 5-8 （生产—库存问题） 某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对 该产品的需求量分别为 2，3，2，4 单位，假设每批产品固定成本为 3 千元，若不生产为 0， 每单位产品成本为 1 千元，每个时期最大生产能力不超过 6 个单位，每期期末未出售产品， 每单位需付存贮费 0.5 千元，假定第 1 期初和第 4 期末库存量均为 0，问该厂如何安排生产 与库存，可在满足市场需求的前提下总成本最小。 解 以每个时期作为一个阶段，该问题分为 4 个阶段，k=1，2，3，4； 决策变量 xk表示第 k 阶段生产的产品数； 状态变量 sk 表示第 k 阶段初的库存量；

内容以d表示第k阶段的需求，则状态转移方程：S+/=St+X—dkk=4，,3，2,1(5.4)由于期初及期末库存为0，所以S,=0，S5=0；允许决策集合Dk（st）的确定：当s≥d时，x可以为0，当sk<d时，至少应生产dk一Sk，故x的下限为max（0，d一st)；每期最大生产能力为6，x最大不超过6，由于期末库存为0，x还应小于本期4至4期需求之和减去本期的库存量，-Sk，所以x的上限为min(d, S, 6),Zd,-jekJ=k故有：De (s) = (xl max (0, d-s) ≤x<min (Zd,)(5.5)Sk，6))k阶段指标函数rk（st：x）表示第k期的生产费用与存贮费用之和：(0.5s kX =0r(Sk,X)=3+x+0.5skx=1,2,3,4,5,6最优指标函数f（sk）表示第k期库存为s到第4期末的生产与存贮最低费用，动态规划基本方程为：[ft(s)=min [r (Skxx)+ fk($++)]k=4,3,2,1XAEDR(Skfs(ss)=0先求出各状态允许状态集合及允许决策集合，如表5-8所示。0Di(si(2,3,4,5,6))01234S2D2(0,1,2,3,4,5,6(0,1,2,3,4,5)(s2(3,4,5,6)(2,3,4,5,6)(1,2,3,4,5,6))2134056D;(0,1,2)(0)(0,1,2,3)(0,1)(s3(2,3,4,5,6)(1,2,3,4,5)(0,1,2,3,4))2013454D.(1)(0)(4)(3)(2)(s4)

内 容 以 dk表示第 k 阶段的需求，则状态转移方程： sk+1=sk+xk－dk k=4，3，2，1 （5.4) 由于期初及期末库存为 0，所以 s1=0，s5=0； 允许决策集合 Dk（sk）的确定： 当 sk≥dk 时，xk可以为 0，当 sk<dk时，至少应生产 dk－sk，故 xk 的下限为 max（0， dk－sk）；每期最大生产能力为 6，xk 最大不超过 6，由于期末库存为 0，xk还应小于本期 至 4 期需求之和减去本期的库存量， k j k j d  s  4 ，所以 xk的上限为 min（ k j k j d  s  4 ，6）， 故有： Dk（sk）=｛xk| max（0，dk－sk）≤xk≤min（ k j k j d  s  4 ，6）｝ （5.5) 阶段指标函数 rk（sk，xk）表示第 k 期的生产费用与存贮费用之和：         3 0.5 1,2,3,4,5,6 0.5 0 ( , ) k k k k k k k k x s x s x r s x 最优指标函数 fk（sk）表示第 k 期库存为 sk到第 4 期末的生产与存贮最低费用，动态规 划基本方程为：            ( ) 0 ( ) min [ ( , ) ( )] 4,3,2,1 5 5 1 1 ( ) f s f s r s x f s k k k k k k x D s k k k k k 先求出各状态允许状态集合及允许决策集合，如表 5-8 所示。 s1 0 D1 (s1 ) ｛2,3,4,5,6｝ s2 0 1 2 3 4 D2 (s2 ) ｛3,4,5,6｝ ｛2,3,4,5,6｝ ｛1,2,3,4,5,6｝ ｛0,1,2,3,4,5,6 ｝ ｛0,1,2,3,4,5｝ s3 0 1 2 3 4 5 6 D3 (s3 ) ｛2,3,4,5,6｝ ｛1,2,3,4,5｝ ｛0,1,2,3,4｝ ｛0,1,2,3｝ ｛0,1,2｝ ｛0,1｝ ｛0｝ s4 0 1 2 3 4 D4 (s4 ) ｛4｝ ｛3｝ ｛2｝ ｛1｝ ｛0｝

内?容k=4 时,JA(s4)=min, [r(S4,x4)+fs(s,))X4ED4(54=min [r(s4,x4)]4-0414计算结果见表5-9所示。表5-90.5sx4 =0r(s4,x)=fs(ss)fa(s4)S4x43+X4+0.5s4X+0Ss77*4*0003*16.506.5*022006*63105.5*5.5 00*04202*k=3 时,Js(s,)=min [5(3,x3)+ f(s4)]X3ED3(33=min [r(s3,xg)+f(s, +x-2)]3ED3(3)计算结果见表5-10所示，表 5-10[0.5s;x=0Ssrs(s3,x)=f(s4)f(s3)x3S4= S3+ X3—23±0[3+X3+0.5s35207126316.512.57261304813.5535.596°4211*04.57111.515.56.5122266.512.51347.535.5135'4210.5*8.5001875116.511.526262123735.512.5

内 容 k=4 时， min [ ( , )] ( ) min [ ( , ) ( )] 4 4 4 ( ) 4 4 4 5 5 ( ) 4 4 4 4 4 4 4 4 r s x f s r s x f s x D s x D s      计算结果见表 5-9 所示。 表 5-9 s4 x4         3 0.5 0 0.5 0 ( , ) 4 4 4 4 4 4 4 4 x s x s x r s x s5 f5(s5) f4(s4) 0 1 2 3 4 4 * 3 * 2 * 1 * 0 * 7 6.5 6 5.5 2 0 0 0 0 0 0 0 0 0 0 7 * 6.5* 6 * 5.5* 2 * k=3 时， min [ ( , ) ( 2)] ( ) min [ ( , ) ( )] 3 3 3 4 3 3 ( ) 3 3 3 4 4 ( ) 3 3 3 3 3 3 3 3         r s x f s x f s r s x f s x D s x D s 计算结果见表 5-10 所示。 表 5-10 S3 x3         3 0.5 0 0.5 0 ( , ) 3 3 3 3 3 3 3 3 x s x s x r s x s4= s3+ x3－2 f4(s4) f3(s3) 0 2 3 4 5 6 * 5 6 7 8 9 0 1 2 3 4 7 6.5 6 5.5 2 12 12.5 13 13.5 11* 1 1 2 3 4 5 * 4.5 5.5 6.5 7.5 8.5 0 1 2 3 4 7 6.5 6 5.5 2 11.5 12 12.5 13 10.5* 2 0 * 1 2 3 1 5 6 7 0 1 2 3 7 6.5 6 5.5 8 * 11.5 12 12.5

内?容84421001.5186.5 2615.511.5336.55.521237.5429.522068*63415.511.57292430*8*2.55.551246.58.50*325*64k=2 时,Je(s2)=mmin, [n(s2,x,)+ J(s)X2ED2($2)=min [r2(s2,x2)+f(s2+X2-3)]X2ED2(52)计算结果见表5-11所示。表5-11[0.5s2X2 =02(S2,x2)=S2[3+X2+0.5s2X2+0S3=S2+X2—3f(s3)fe(s2)X2603111747110.517.50828J16°69381725.501116.531176.510.52815.5*47.513588.516.5869.5417.5510111626110.516.5723815°2838164945817105861801.501112.5*1315.510.5162286.514.5

内 容 4 8 4 2 10 3 0 * 1 2 3 1.5 5.5 6.5 7.5 1 2 3 4 6.5 6 5.5 2 8 * 11.5 12 9.5 4 0 * 1 2 2 6 7 2 3 4 6 5.5 2 8* 11.5 9 5 0 * 1 2.5 6.5 3 4 5.5 2 8 * 8.5 6 0 * 3 4 2 5 * k=2 时， min [ ( , ) ( 3)] ( ) min [ ( , ) ( )] 2 2 2 3 2 2 ( ) 2 2 2 3 3 ( ) 2 2 2 2 2 2 2 2         r s x f s x f s r s x f s x D s x D s 计算结果见表 5-11 所示。 表 5-11 S2 x2         3 0.5 0 0.5 0 ( , ) 2 2 2 2 2 2 2 2 x s x s x r s x s3= s2+ x2－3 f3(s3) f2(s2) 0 3 4 5 * 6 6 7 8 9 0 1 2 3 11 10.5 8 8 17 17.5 16* 17 1 2 3 4 * 5 6 5.5 6.5 7.5 8.5 9.5 0 1 2 3 4 11 10.5 8 8 8 16.5 17 15.5* 16.5 17.5 2 1 2 3 * 4 5 6 5 6 7 8 9 10 0 1 2 3 4 5 11 10.5 8 8 8 8 16 16.5 15* 16 17 18 3 0 * 1 2 1.5 5.5 6.5 0 1 2 11 10.5 8 12.5* 16 14.5

内容337.5815.54848.516.5859.5517.566510.515.510210.512.5*26814178315248481639584175106515k=1 时,(s)= min [r(s1,x)+f(s,)]= min [r;(s,x,) + f,(s, + x, -2)]XIEDI(S1)计算结果见表5-12所示。表5-12[0.5s,X =0Sir(si,x)=J(s2)fi(st)S2= Xi—2Xi[3+x +0.5s,x ±0502162161315.521.5742152205*8320.5*12.596412.521.5逆向追踪可得：Xi=5，82=3，x2=0，83=0，x3=6，S4=4，x4=0，即第1时期生产5个单位，第3时期生产6个单位，第2，4时期不生产，可使总费用最小，最小费用为20.5千元。三、背包问题有人携带背包上山，其可携带物品的重量限度为α公斤，现有n种物品可供选择，设第i种物品的单件重量为a,公斤，其在上山过程中的价值是携带数量x,的函数c，（x），问应如何安排携带各种物品的数量，使总价值最大。这就是背包问题，类似的货物装载问题，下料问题都等同于背包问题。背包问题的数学模型为：

内 容 3 4 5 6 7.5 8.5 9.5 10.5 3 4 5 6 8 8 8 5 15.5 16.5 17.5 15.5 4 0 * 1 2 3 4 5 2 6 7 8 9 10 1 2 3 4 5 6 10.5 8 8 8 8 5 12.5* 14 15 16 17 15 k=1 时， min [ ( , ) ( 2)] ( ) min [ ( , ) ( )] 1 1 1 2 1 1 ( ) 1 1 1 2 2 ( ) 1 1 1 1 1 1 1 1         r s x f s x f s r s x f s x D s x D s 计算结果见表 5-12 所示。 表 5-12 S1 x1         3 0.5 0 0.5 0 ( , ) 1 1 1 1 1 1 1 1 x s x s x r s x s2= x1－2 f2(s2) f1(s1) 0 2 3 4 5 * 6 5 6 7 8 9 0 1 2 3 4 16 15.5 15 12.5 12.5 21 21.5 22 20.5* 21.5 逆向追踪可得：x1 * =5，s2=3，x2 * =0，s3=0，x3 * =6，s4=4，x4 * =0，即第 1 时期生产 5 个 单位，第 3 时期生产 6 个单位，第 2，4 时期不生产，可使总费用最小，最小费用为 20.5 千 元。 三、背包问题 有人携带背包上山，其可携带物品的重量限度为 a 公斤，现有 n 种物品可供选择，设第 i 种物品的单件重量为 ai 公斤，其在上山过程中的价值是携带数量 xi 的函数 ci（xi），问应如 何安排携带各种物品的数量，使总价值最大。这就是背包问题，类似的货物装载问题，下料 问题都等同于背包问题。 背包问题的数学模型为：

内容max z =c(x)+c2(x)+...+c,(x,)ax+ax+...+a.n<a[x,≥0且为整数(i=1,2,n)下面用动态规划方法求解：按照装入物品的种类划分阶段，k=1，2，，n；状态变量S表示装入第k种至第n种物品的总重量；决策变量x表示装入第k种物品的件数：状态转移方程为：SA+I=SK-aRXA允许决策集合为：1,x为整数Dr(s)=30≤≤[a其中[]表示不超过的最大整数；akak阶段指标函数ck（x）表示第k阶段装入第k种商品x件时的价值：最优指标函数f（s）表示第k阶段装入物品总重量为s时的最大价值，动态规划基本方程为：[ft(s)=max[c (x)+ fe(sk+1)]k=n,n-l,...,=0,1,[Jn+I(sn+1) = 0例7-9某工厂生产三种产品，各产品重量与利润关系如表5-13所示，现将此三种产品运往市场销售，运输能力总重量不超过6吨，问如何安排运输使总利润最大？表5-1323种类1234单位重量（吨）80单位利润（元）130180解设x为装载第i种货物的件数，-1，2，3，该问题数学模型为：maxz=80x,+130x,+180x[2x, +3x2 +4x, ≤6[x,≥0且为整数(i=1,2,3)按前述方法建立动态规划模型；k=3 时,Js(ss)=max(180x)3=0,-[]计算结果如表5-14所示。表5-14

内 容              0 ( 1,2, , ) max ( ) ( ) ( ) 1 1 2 2 1 1 2 2 x i n a x a x a x a z c x c x c x i n n n n    且为整数 下面用动态规划方法求解： 按照装入物品的种类划分阶段，k=1，2，.，n； 状态变量 sk 表示装入第 k 种至第 n 种物品的总重量； 决策变量 xk表示装入第 k 种物品的件数； 状态转移方程为： sk+1=sk－akxk 允许决策集合为：          k为整数 k k k k k k x a s D (s ) x 0 x [ ], 其中 [ ] k k a s 表示不超过 k k a s 的最大整数； 阶段指标函数 ck（xk）表示第 k 阶段装入第 k 种商品 xk 件时的价值； 最优指标函数 fk（sk）表示第 k 阶段装入物品总重量为 sk 时的最大价值，动态规划基本 方程为：                ( ) 0 ( ) max [ ( ) ( )] , 1, ,1 1 1 1 1 0,1, ,[ ] n n k k k k a s x k k f s f s c x f s k n n k k k   例 7-9 某工厂生产三种产品，各产品重量与利润关系如表 5-13 所示，现将此三种产品 运往市场销售，运输能力总重量不超过 6 吨，问如何安排运输使总利润最大？ 表 5-13 种类 1 2 3 单位重量（吨） 2 3 4 单位利润（元） 80 130 180 解 设 xi 为装载第 i 种货物的件数，i=1，2，3，该问题数学模型为：            0 ( 1,2,3) 2 3 4 6 max 80 130 180 1 2 3 1 2 3 x i x x x z x x x i 且为整数 按前述方法建立动态规划模型； k=3 时， ( ) max (180 ) 3 ] 4 0,1, ,[ 3 3 3 3 f s x s x    计算结果如表 5-14 所示。 表 5-14