05 第五章 动态规划

1、 通过本章的学习，你应该能够：通过本章的学习，你应该能够： 动态规划的最优化原理；动态规划建模的动态规划的最优化原理；动态规划建模的 特点及其求解步骤。特点及其求解步骤。 几种常见的动态规划问题模型的特点、几种常见的动态规划问题模型的特点、 结构及求解方法。结构及求解方法。动态规划的基本理论及其应用；多阶段决动态规划的基本理论及其应用；多阶段决 策过程的数学描述。策过程的数学描述。 某医院要制定明年某医院要制定明年14月份某种药品的采购方月份某种药品的采购方案案, 预计每月对该药品的需求量以及各月的固定订预计每月对该药品的需求量以及各月的固定订货费和单位存贮费用如表货费和单位存贮费用如表5-1

2、所示。如果每件药品的所示。如果每件药品的价格是价格是8千元，该院在每月初采购，问应如何安排千元，该院在每月初采购，问应如何安排每月的采购量，才能使总成本最小？每月的采购量，才能使总成本最小？ 月月 份份需求量需求量uk固定订货费固定订货费yk单位存贮费单位存贮费hk123422142.01.51.01.00.50.40.40.4 上述模型是医院药品存贮问题，由于要制定每月的上述模型是医院药品存贮问题，由于要制定每月的采购量，所以可以把采购量，所以可以把4个月看成个月看成4个阶段，属于多阶段决个阶段，属于多阶段决策问题，动态规划就是解决多阶段决策问题的有效方法。策问题，动态规划就是解决多阶段决策

3、问题的有效方法。 动态规划是运筹学的一个重要分支，它是解决多动态规划是运筹学的一个重要分支，它是解决多阶段决策问题的一种有效的数量化方法。动态规划可阶段决策问题的一种有效的数量化方法。动态规划可用于资源分配问题、最短路径问题、存贮问题、背包用于资源分配问题、最短路径问题、存贮问题、背包问题、设备更新问题、最优控制问题等等。它是现代问题、设备更新问题、最优控制问题等等。它是现代管理学中进行科学管理学中进行科学决策决策不可缺少的工具。不可缺少的工具。 本章将介绍本章将介绍几种特殊的动态规划问题：如距离问题，资源分配问几种特殊的动态规划问题：如距离问题，资源分配问题、背包问题，设备更新问题，医院药品

4、存贮问题等题、背包问题，设备更新问题，医院药品存贮问题等并给出相应的解法。并给出相应的解法。 （最短路线问题）（最短路线问题） 如图如图5-1，位于，位于A城市的某药城市的某药厂要把一批产品运往位于厂要把一批产品运往位于E城市的销售部。途中可能城市的销售部。途中可能经过的城市有经过的城市有8个：个：B1, B2, B3 ;C1, C2, C3 ;D1, D2 图中两图中两连线上方的数字表示两城市之间的距离。从连线上方的数字表示两城市之间的距离。从A到到E走不走不同的路线，则所经过的城市不同，因而总路程也不同，同的路线，则所经过的城市不同，因而总路程也不同，试求一条从试求一条从A到到E的运输路线

5、，使总路程最短的运输路线，使总路程最短。图图5-1 A城到城到E城的路线图城的路线图 这个问题的解决可分为四个阶段来考虑。第这个问题的解决可分为四个阶段来考虑。第一阶段，从一阶段，从A 到到B（B含三个城市）；第二阶段，从含三个城市）；第二阶段，从B到到C（C 含三个城市含三个城市 ）；第三阶段，从）；第三阶段，从C 到到D（D含二含二个城市）；第四阶段，从个城市）；第四阶段，从D到到E。这是一个四阶段决策。这是一个四阶段决策过程的最优化问题。用动态规划解决这个问题的方法过程的最优化问题。用动态规划解决这个问题的方法是把这个四阶段决策问题，转化为几个容易解决的单是把这个四阶段决策问题，转化为几

6、个容易解决的单阶段决策问题。阶段决策问题。 为解决例为解决例5-2的问题，采用从后向前的逆序解法。的问题，采用从后向前的逆序解法。即从最后一个阶段开始从终点即从最后一个阶段开始从终点E向始点向始点A方向逐段逆方向逐段逆推，直至找到众多线路中的最短线路，也就是问题推，直至找到众多线路中的最短线路，也就是问题的最优解的最优解。首先从第四阶段开始。该阶段中有两个始点首先从第四阶段开始。该阶段中有两个始点D1、 D2 ，终点只有一个点，终点只有一个点E点，于是无论始点是点，于是无论始点是D1 还还 是是 D2 ，最优终点都将选择，最优终点都将选择E点。将第四阶段的决策点。将第四阶段的决策 过程及优化结

7、果用表过程及优化结果用表5-6表示。表示。 始点始点终点及始点到终点及始点到E 的距离的距离到到E的最短的最短距离距离本阶段最佳终点本阶段最佳终点（最优决策）（最优决策）ED1D24343EE在第三阶段中共有三个始点在第三阶段中共有三个始点C1, C2, C3 ，两个终点，两个终点 D1, D2 ，第三阶段决策过程及优化结果见表第三阶段决策过程及优化结果见表5-7。 始点始点本阶段终点及始点到本阶段终点及始点到E的距离的距离到到E的最的最短距离短距离本阶段最佳终点本阶段最佳终点（最优决策）（最优决策）D1D2C1C2C33+4=76+4=101+4=55+3=82+3=53+3=6755D1D

8、2D1若全过程的最优路线经过若全过程的最优路线经过C2点，则点，则最优路线必为最优路线必为C2 D2E ；从上表可见：从上表可见：若全过程的最优路线经过若全过程的最优路线经过C3 点，则点，则最优路线必为最优路线必为C3 D1E 。第二阶段中共有三个始点第二阶段中共有三个始点B1, B2, B3 ，三个终点，三个终点C1, C2, C3 ，表，表5-8给出第二阶段的决策过程及优化结果。给出第二阶段的决策过程及优化结果。 始点始点终点及始点到终点及始点到E 的距离的距离到到E 的最的最短距离短距离本阶段最佳终点本阶段最佳终点（ 最优策略）最优策略）C1C2C3B16+7=134+5=99C2B2

9、8+7=157+5=126+5=1111C3B3 8+5=139+5=1413C2若全过程的最优路线经过若全过程的最优路线经过B2 点，则点，则最优路线必为最优路线必为 B2 C3 D1E ；从表从表5-8可以看到：可以看到：若全过程最优路线经过若全过程最优路线经过B3 点，则点，则最优路线一定是最优路线一定是 B3 C2 D2E。第一阶段中只有一个始点第一阶段中只有一个始点A，三个终点，三个终点B1, B2, B3 。 具体结果见表具体结果见表5-9。始点始点本阶段终点及始点到本阶段终点及始点到E的距离的距离到到E的最短的最短距离距离本阶段最本阶段最佳终点佳终点B1B2B3A13201813

10、B1 经过上面四个阶段的寻找得到了问题的最短路经过上面四个阶段的寻找得到了问题的最短路线（最优解）：线（最优解）： A B1 C2 D2E在动态规划解决问题时，首先将问题的全在动态规划解决问题时，首先将问题的全过程分成几个互相联系的阶段。一般阶段是按时间和空过程分成几个互相联系的阶段。一般阶段是按时间和空间划分的，以便能按一定的次序去求解。由于阶段往往间划分的，以便能按一定的次序去求解。由于阶段往往不是一个，因此可把阶段看成不是一个，因此可把阶段看成，常用，常用k 表示。表示。 2 状态是指每个阶段开始时所处的客观条状态是指每个阶段开始时所处的客观条件和自然状况，即每个阶段的起点。状态常取不同

11、件和自然状况，即每个阶段的起点。状态常取不同的值，它能描述过程的变化，能描述过程的过去，的值，它能描述过程的变化，能描述过程的过去，现在和将来的状况，因此，状态是变量，常称为现在和将来的状况，因此，状态是变量，常称为，记作，记作 ，它表示第，它表示第k 阶段所处的状态阶段所处的状态。 状态变量取值的全体称为状态变量取值的全体称为状态集合状态集合，记作，记作Sk 。 ks ：在某一过程中某一阶段的状态，在该：在某一过程中某一阶段的状态，在该阶段以后的发展，不受这阶段以前各阶段的影响，而阶段以后的发展，不受这阶段以前各阶段的影响，而只与当前的状态有关，与过程过去的历史以及过去如只与当前的状态有关，

12、与过程过去的历史以及过去如何发展无关。何发展无关。 状态变量的无后效性要求，在处理实际问题中必状态变量的无后效性要求，在处理实际问题中必须正确地选择状态变量，使它确定的过程满足无后效须正确地选择状态变量，使它确定的过程满足无后效性。只有这样才能正确地建立动态规划的模型，得到性。只有这样才能正确地建立动态规划的模型，得到问题的最优解问题的最优解。 决策是某一阶段内的决择。在多阶段决策决策是某一阶段内的决择。在多阶段决策过程中对每一阶段及其每一状态，往往可以做出不同过程中对每一阶段及其每一状态，往往可以做出不同的决择，使过程按决策的方式转移到下一阶段的某一的决择，使过程按决策的方式转移到下一阶段的

13、某一个状态。第个状态。第k 个阶段的决策与第个阶段的决策与第k 个阶段的状态有关，个阶段的状态有关，或者说决策是随状态的变化而不同，因此决策是变量，或者说决策是随状态的变化而不同，因此决策是变量，常称为常称为决策变量决策变量。 通常用通常用 表示第表示第k 个阶段处于个阶段处于sk 状态时的决状态时的决策，而这个决策又决定了第策，而这个决策又决定了第k +1阶段时的状态，显然阶段时的状态，显然决策变量是状态决策变量是状态sk 的函数。的函数。 决策变量一般可取若干个不同的值，决策变量取决策变量一般可取若干个不同的值，决策变量取值的全体称为允许决策集合，第值的全体称为允许决策集合，第k 阶段在状

14、态阶段在状态sk 的允的允许决策集合记为许决策集合记为Dk (sk ) 。 设多阶段决策过程的阶数为设多阶段决策过程的阶数为n，则由所有各，则由所有各阶段的决策组成的任一个可行的决策序列，称为全阶段的决策组成的任一个可行的决策序列，称为全过程的一个策略，简称过程的一个策略，简称，记为，记为 p1,n (s1 ) 。即。即 1,11122()(),(),()nnnpsx sxsxs 从第从第k 阶段开始到最后阶段的决策所组成的决策序阶段开始到最后阶段的决策所组成的决策序列称为列称为k 子过程策略，简称子过程策略，简称，记为，记为pk,n (sk ) 则则 ,11()(),(),()k nkkkk

15、knnpsxsxsxs 能达到全过程最优的策略叫做能达到全过程最优的策略叫做。所有可行的全过程策略构成的集合称为所有可行的全过程策略构成的集合称为，记作，记作 ，所有可行的子策略构成，所有可行的子策略构成的集合称为的集合称为，记作，记作 。 用来衡量多阶段决策过程优劣的数用来衡量多阶段决策过程优劣的数量指标，称为量指标，称为指标函数指标函数。 把从第把从第k 阶段始点阶段始点sk 到终点到终点xk (sk ) 的阶段指标记的阶段指标记为为dk (sk , xk )；而把从第；而把从第k 阶段的状态阶段的状态sk 开始，选定子开始，选定子策略策略pk,n (sk ) 的指标函数，记作的指标函数，

16、记作Vk,n (sk , pk,n (sk )（k =1，n）, 显然它是状态变量显然它是状态变量Sk 和决策变量和决策变量pk,n (sk ) 的函数。的函数。 当当k =1时，时，V1,n (s1 , p1,n (s1 ) 表示初始状态为表示初始状态为S1 ，采，采用策略用策略p1,n (s1 ) 时的全过程的指标函数值；时的全过程的指标函数值； 当当k 1时，时，Vk,n (sk , pk,n (sk )表示在表示在k阶段状态为阶段状态为sk ，采用子策略采用子策略pk,n (sk ) 时的子过程的指标函数值。时的子过程的指标函数值。 如在例如在例5-2中（中（n = 4），），V2,4

17、 (s2 , p2,4 (s2 ) 表示在第表示在第二阶段，以状态二阶段，以状态B(B1, B2, B3)为始点，以为始点，以E为终点的线路为终点的线路长度。长度。 状态状态B的选择有的选择有3种种(B1, B2, B3)，又每一个，又每一个Bi ( i =1,2,3)经状态经状态C(C1, C2, C3) ，再经状态，再经状态D(D1, D2)到达终点到达终点E，都，都有多种走法（子策略）。因此，指标函数有多种走法（子策略）。因此，指标函数V2,4 (s2 , p2,4 (s2 ) 可取许多数值，如可取许多数值，如B1 C1 D2E 这种走法（见图这种走法（见图5-1），它的线路长），它的线

18、路长14就是这些数值中的一个。而就是这些数值中的一个。而d2 (B1 , C2 )=4 ，则表示第二阶段从状态，则表示第二阶段从状态B1 开始经过决策开始经过决策x2 (B1 ) 到达终点到达终点C2 的阶段指标值（即线段的阶段指标值（即线段B1 C2 的长度）。的长度）。 指标函数最优值称为指标函数最优值称为最优指标函数最优指标函数，记作，记作 fk (Sk ) 。在。在例例5-2中中fk (Sk ) 表示从表示从k 阶段阶段 Sk到终点到终点 E 的最短距离，如的最短距离，如 f1 (S1 ) =13是全过程的始点是全过程的始点 A 到终点到终点 E 的最短距离，即问的最短距离，即问题的最

19、优解。题的最优解。 而而 f2 (B1 ) =9是从是从2阶段状态点阶段状态点B1到终点到终点 E 的最短距离，的最短距离，根据根据fk (Sk ) 的定义可知的定义可知)(,()(,)()(,knkknksPspkkspsVoptsfknkknk其中其中opt可根据实际问题取可根据实际问题取max或或min。 由前面的例题可以看到，多阶段决策由前面的例题可以看到，多阶段决策过程是一个序贯决策过程，前一阶段的终点就是后一阶段过程是一个序贯决策过程，前一阶段的终点就是后一阶段的始点，若已选定第的始点，若已选定第k阶段的状态变量阶段的状态变量sk ，且本阶段的决，且本阶段的决策变量策变量xk (s

20、k )也确定之后，第也确定之后，第k +1阶段的状态变量阶段的状态变量sk+1也也随之确定，记作随之确定，记作1(,()kkkkksT sx s这一关系式确定了由过程的第这一关系式确定了由过程的第k 阶段到第阶段到第k +1阶段的状阶段的状态转移规律，称为态转移规律，称为状态转移方程状态转移方程或或状态转移函数状态转移函数。 动态规划的动态规划的表述如下：表述如下：“作为整个过程作为整个过程的最优策略应具有这样的性质，无论过去的状态和决策的最优策略应具有这样的性质，无论过去的状态和决策如何，对于前面的决策所形成的状态而言，余下的诸决如何，对于前面的决策所形成的状态而言，余下的诸决策必须构成最优

21、策略策必须构成最优策略”。也就是说最优策略的任一子策。也就是说最优策略的任一子策略都是最优的。略都是最优的。 如在例如在例5-2中最优解问题即是求最短路线问题，其中最优解问题即是求最短路线问题，其最优解为为最优解为为 AB1 C2 D2E，这是一条从始点，这是一条从始点 A到终点到终点 E 的最短路线。的最短路线。 在这条最短路线上任意状态在这条最短路线上任意状态Sk 到终点到终点E，可能有几，可能有几条线路。条线路。 如以如以B1 为始点，则有四条路线到达终点为始点，则有四条路线到达终点E： 122BCDE121BCDE112BCDE111BCDE根据最优化原理在这四条路线（四个子策略）中必

22、应根据最优化原理在这四条路线（四个子策略）中必应选择最短的一条，才能构成全过程的最优策略（最短选择最短的一条，才能构成全过程的最优策略（最短路线），显然应选择路线），显然应选择:122BCDE 最优化原理阐述这样一个事实，对全过程的任一状最优化原理阐述这样一个事实，对全过程的任一状态点态点sk ，不考虑，不考虑sk 以前的决策，只保证以前的决策，只保证sk 以后的决策是以后的决策是最优的。在例最优的。在例5-2中对状态中对状态B1 而言，不关心从全过程始而言，不关心从全过程始点点 A到状态到状态B1 是如何决策的，只关注状态是如何决策的，只关注状态B1 后的决策，后的决策，只保证只保证B1 后

23、的决策是最优的即可。后的决策是最优的即可。 最优化原理为动态规划从最后阶段的优化开始，逐最优化原理为动态规划从最后阶段的优化开始，逐步向前一阶段优化扩展直至第一阶段，从而达到全程优步向前一阶段优化扩展直至第一阶段，从而达到全程优化的方法奠定了理论基础。化的方法奠定了理论基础。 由最后一个阶段优化开始，按逆向顺序逐步向前一由最后一个阶段优化开始，按逆向顺序逐步向前一阶段优化扩展，并将后一阶段的优化结果带到前一个阶阶段优化扩展，并将后一阶段的优化结果带到前一个阶段中去，依次逐步向前递推，直至全过程的优化结束。段中去，依次逐步向前递推，直至全过程的优化结束。 这种逆向顺序逐步向前递推的方法可简称为这

24、种逆向顺序逐步向前递推的方法可简称为逆序递逆序递推法推法，它是解动态规划问题中经常采用的一种方法。，它是解动态规划问题中经常采用的一种方法。 将所要解决的问题恰当地划分为若干将所要解决的问题恰当地划分为若干阶段，经常是按事物发展的时间和空间来划分不同阶段，经常是按事物发展的时间和空间来划分不同阶段，各阶段的首尾要互相衔接。阶段，各阶段的首尾要互相衔接。 正确地选择状态变量正确地选择状态变量Sk ，确定它在每一，确定它在每一阶段的取值范围。阶段的取值范围。 对每个状态变量对每个状态变量Sk （ k =1，2,n），找出），找出与其对应的决策变量与其对应的决策变量xk (Sk ) 以及允许决策集合

25、以及允许决策集合Dk (Sk ) 。 对每状态变量对每状态变量Sk ，及对应的决策变量，及对应的决策变量xk (Sk ) 计算出本阶段的各个指标值。计算出本阶段的各个指标值。 正确写出状态转移方程正确写出状态转移方程1(,()kkkkksT sx s)(),(11kkkkksfxsd11()()(,)()kkkkkkkkkkxDsfsoptdsxfs 对每一对对每一对Sk , xk (Sk ) ，计算指标值，计算指标值 把指标值进行比较取出最优的一个，即把指标值进行比较取出最优的一个，即 由由 k = n ，n 1,2,1 将上式依次逐步递推，将上式依次逐步递推，直至全过程的优化结束，即可求出

26、动态规划问题直至全过程的优化结束，即可求出动态规划问题的最优策略及最优指标值。的最优策略及最优指标值。 某药厂定期为某医药公司提某药厂定期为某医药公司提供某种药品，该医药公司采取预订方式购买，因此药厂供某种药品，该医药公司采取预订方式购买，因此药厂可以预测未来几个月的需求量（单位：件）。为保证需可以预测未来几个月的需求量（单位：件）。为保证需求，药厂为下一年前四个月制定一项生产计划，而这四求，药厂为下一年前四个月制定一项生产计划，而这四个月医药公司的需求情况见表个月医药公司的需求情况见表5-14。月份月份1 2 3 4需求量需求量2 4 1 3 该药厂的生产成本随生产数量的变化而变化。生该药厂

27、的生产成本随生产数量的变化而变化。生产准备费为产准备费为4（万元），若每月生产不超过（万元），若每月生产不超过2件，每件件，每件成本为成本为2；若超过；若超过2件，则超过件，则超过2件的部分每件成本为件的部分每件成本为1，而前而前2件每件成本仍为件每件成本仍为2 。 药厂的最大生产能力每月为药厂的最大生产能力每月为4件，件数与成本的件，件数与成本的关系见表关系见表5-15。生产件数生产件数 0 1 2 3 4成本（万元）成本（万元） 0 6 8 9 10 已知每件药品在仓库中每月的存贮费为已知每件药品在仓库中每月的存贮费为1，仓，仓库的最大存贮能力为库的最大存贮能力为3件，此外，又知道在件，此

28、外，又知道在1月初时月初时仓库里存有仓库里存有1件药品，要求件药品，要求4月末仓库的存贮量为零。月末仓库的存贮量为零。现要使得下一年前四个月的生产成本和库存费总费现要使得下一年前四个月的生产成本和库存费总费用最少，问该药厂应如何按排生产计划用最少，问该药厂应如何按排生产计划?Sk 表示第表示第k阶段开始时的库存量（状态变量）；阶段开始时的库存量（状态变量）；xk 表示第表示第k阶段的生产量（决策变量）；阶段的生产量（决策变量）； yk 表示第表示第k阶段的需求量；阶段的需求量；hk (sk , xk) 表示第表示第k阶段的存储费；阶段的存储费； 设：第设：第k个月为第个月为第k个阶段：（个阶段

29、：（k=1，2，3，4）。）。 ck (xk)表示从第表示从第k阶段到第阶段到第4阶段所用的生产成本；阶段所用的生产成本； dk (sk , xk )表示从第表示从第k阶段到第阶段到第4阶段的总费用（指标值）；阶段的总费用（指标值）； fk (sk )表示从第表示从第k阶段到第阶段到第4阶段的最低总费用。阶段的最低总费用。(,)(,) +() kkkkkkkkdsxh sxcx显然显然 由已知由已知s1 =11(1,2,3,4)iiiissxyi4440sxy 下面分四个阶段求解。下面分四个阶段求解。 又因又因s5 =0（4月末仓库的存贮量为零），于是月末仓库的存贮量为零），于是4444444

30、4444444()()()min(,)min(,3)xDsxDsfsds xdss44444444444()()min(,3)(,3)xDsfsdssdss 因为要求四月末的存贮量为零，所以第因为要求四月末的存贮量为零，所以第4阶段阶段的存储费的存储费h4 (s4 , x4 )=10=0，而总费用，而总费用 当状态变量当状态变量s4 取值确定时，变量取值确定时，变量x4 的取值只有一的取值只有一个，故有个，故有从从s4 + x4 - -y4 =0可以求出可以求出(,)(,)()kkkkkkkkdsxh sxcx 如当如当s4 =1时，则四月份需要生产时，则四月份需要生产s4 = 3- -s4

31、=3- -1=2件，由表件，由表5-15可确定成本可确定成本c4 (2) 的取值为的取值为8，即，即f4 (1) =8由此类推，可分别求出当由此类推，可分别求出当 s4 =0，2，3时的值，详见表时的值，详见表5-16。44444444(,)(,)()dsxh sxc x4444444444(,3)(,3)(3)(3)dssh sscscs4444()(3)fscs故有故有由此可见，第由此可见，第4阶段的最低总费用阶段的最低总费用 ：s4x4f4 ( s4 )012301230689986032 10*4x33333333( ,)( ,)()d s xh s xc x3334yxss由由333

32、333333433()( )min() 11)(1)xDsf sc xsxfsx 得得 计算表计算表5-17中数据中数据 ，当第三阶段初存贮量，当第三阶段初存贮量s3 =2，生产，生产件数件数x3 =1时，时， s3 + x3- -y3 =2+1-1=2，由表，由表5-15知生产件数知生产件数x3 =1时的生产成本为时的生产成本为6，第三阶段末存贮量，第三阶段末存贮量s3 + x3 - -y3 =2时的存贮费为时的存贮费为12=2，查表，查表5-16知知 4443334()()26fsfsxyf34333334(2,1)(2)( ,)()(2)dfh s xc xf334(2,1)(1)(2)

33、hcf于是可计算出于是可计算出 同理可以计算当第三阶段初存贮量同理可以计算当第三阶段初存贮量 s3 =0，1，3，生产件数，生产件数x3 取一切可行值时取一切可行值时f3 (s3 ) 的值，见表的值，见表5-17。 33333333433()(2)min()11)1)min 9,14,119xDsfc xsxfsx 类似可求类似可求 s3 =2， x3 =0，2时的总成本值。于是，时的总成本值。于是，3x*3xs3x3f3 ( s3)0123401230+0+9=90+1+8=90+2+6=86+0+9=156+1+8=156+2+6=146+3+0=98+1+8=178+2+6=168+3+

34、0=119+2+6=179+3+0=1210+3+0=131399840003x232224,yssxy222222222322()()min()1 (4)(4)xDsfscxsxfsx 二月份需求量二月份需求量 当第二阶段初存贮当第二阶段初存贮量量s2 =0，1，2，3，生产件数，生产件数取一切可行值时，可计算出取一切可行值时，可计算出 f2 (0 ), f2 (1), f2 (2), f2 (3) 的值，见表的值，见表5-18。 3x*2x112111112,1,1ysssxyxy 1111111121114( )1min()(1,)(1)xf sfc xhxfsx当第一阶段初存贮量当第一

35、阶段初存贮量s1 =1 ，生产件数，生产件数x1 取一切可行取一切可行值（值（ x1 =0，1，2，3，4）可计算出）可计算出f1 (1), 的值，见的值，见表表5-19。于是于是本阶段需求量本阶段需求量1s1x)(11sf*1x这时最低总成本为这时最低总成本为29万元。万元。*1234(,)1,4,4,0 x x x x*1234(,)2,4,0,3xxxx或 由于表由于表5-19中中 的值有两个，即的值有两个，即 ，再根据递推关系按表再根据递推关系按表5-19，表，表5-18，表，表5-17，表，表5-16的顺序最后得到两组最优解：的顺序最后得到两组最优解：*1x*111,2xx （设备更

36、新问题）（设备更新问题） 某医院要考虑一种设备在某医院要考虑一种设备在5年内的更新问题。在每年年初需作出决策，是继续使用年内的更新问题。在每年年初需作出决策，是继续使用还是更新。如果继续使用，则需支付维修费用。已知使还是更新。如果继续使用，则需支付维修费用。已知使用了不同年限后的设备每年所需的维修费用（单位：万用了不同年限后的设备每年所需的维修费用（单位：万元）如表元）如表5-36所示。所示。 使用年数使用年数 0 1 1 2 2 3 3 4 4 5每年维修费用每年维修费用 5 6 8 11 18 如果要更新设备，则已知在各年年初该种设备的价如果要更新设备，则已知在各年年初该种设备的价格如表格

37、如表5-37所示。所示。 年份年份 1 2 3 4 5 价格（万元）价格（万元） 11 11 12 12 13（1）如果开始时设备已使用）如果开始时设备已使用1年：问每年年初应怎样年：问每年年初应怎样做出决策，才能使做出决策，才能使5年内该项设备的购置和维修费最少年内该项设备的购置和维修费最少?（2）用逆序递推法求解时，求函数指标值）用逆序递推法求解时，求函数指标值f4 (2) 。 （1）以每年作为一个阶段，共分）以每年作为一个阶段，共分5个阶段：个阶段： 状态变量状态变量sk ：第：第k年年初设备已使用的年限（年年初设备已使用的年限（k=1，2，3，4，5）。如）。如s1=1，表示第一年年初

38、设备已使用的年，表示第一年年初设备已使用的年限为限为1；s2 =1，2则表示当上年设备更新则表示当上年设备更新s2=1，当上年，当上年设备继续使用设备继续使用s2=2。RxKxsskkkk, 1, 11状态转移方程：状态转移方程：决策变量决策变量xk ：在每一阶段每一状态所需作出的决策只：在每一阶段每一状态所需作出的决策只有两个，继续使用或更新有两个，继续使用或更新 xk =K 表示设备继续使用，表示设备继续使用， xk =R 表示更新设备。表示更新设备。 由于阶段由于阶段k的状态变量的状态变量sk 表示第表示第k年年初设备已使用的年年初设备已使用的年限，于是可得到各阶段不同状态下的最优解。年

39、限，于是可得到各阶段不同状态下的最优解。 对对k = 5，当决策继续使用时，函数指标值为，当决策继续使用时，函数指标值为R(s5) ；当决策更新时函数指标值为当决策更新时函数指标值为C5+R(0) 。5555( )min( ),(0)f sR sCR对对k 5，当决策继续使用时，函数指标值为，当决策继续使用时，函数指标值为而而1()(1)kkkR sfs1(0)(1)kkCRf11()min()(1),(0)(1)kkkkkkkfsR sfsCRf 0 1 2 3 4 5 6 8 11 18 k年份年份 1 2 3 4 5 11 11 12 12 13 ks()kR skC当决策更新时函数指标

40、值为当决策更新时函数指标值为而而其中其中R(sk) , Ck 的值可由表的值可由表5-36和表和表5-37得到，见表得到，见表5-38。用逆序递推法求问题的最优解。用逆序递推法求问题的最优解。 根据根据f5 (s5 ) 的计算公式及表的计算公式及表5-38可得到可得到f5 (s5 ) 在在s5 取不取不同值时的指标值，见表同值时的指标值，见表5-39。本阶段状态变量本阶段状态变量= 1，2，3，4，5。 继续使用继续使用 更新更新 1 6 18 6 继续使用继续使用 2 8 18 8 继续使用继续使用 3 11 18 11 继续使用继续使用 4 8 18 18 继续使用或更新继续使用或更新 5 18 18 更新更新5s 55fs*5x5x 根据根据fk (sk ) 的计算公式及表的计算公式及表5-38可得到可得到f4 (s4 ) 在在s4 取取不同值时的指标值，见表不同值时的指标值，见表5-40。 继续使用继续使用 更新更新 1 14 23 14 继续使用继续使用 2 19 23 19 继续使用继续使用 3 29 23 23 更新更新 4 36 23 23 更新