课程名称：《运筹学》第_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 阶段初的库存量；