运 筹 学 “运筹学”课题组.

Presentation on theme: "运 筹 学 “运筹学”课题组."— Presentation transcript:

1 运 筹 学 “运筹学”课题组

2 第五章 动态规划 本章内容重点 5.1 多阶段决策过程与方法 5.2 动态规划的基本概念和递归方程 5.3 最优性原理与建模方程
5.1 多阶段决策过程与方法 5.2 动态规划的基本概念和递归方程 5.3 最优性原理与建模方程 5.4 动态规划的应用案例 5.5 实际应用案例:机器生产负荷分配 5.6 习 题

3 动态规划（dynamic programming）是求解多阶段决策问题的一种最优化方法。
第五章 动态规划 概 述 动态规划（dynamic programming）是求解多阶段决策问题的一种最优化方法。

4 概 述 20世纪50年代初，R. E. Bellman等人在研究多阶段决策过程优化问题时，提出了著名的最优性原理（principle of optimality）,即把多阶段决策过程转化为一系列单阶段问题，逐个求解，创立了解决这类多阶段优化问题的新方法—动态规划。1957年R. E. Bellman出版了《Dynamic Programming》，这是该领域的第一本著作。

5 5．1 多阶段决策过程与方法 所谓多阶段决策过程，是指这样一类的决策问题：由问题的特性可将整个决策过程按时间、空间等标志划分为若干个互相联系又互相区别的阶段。在它的每一阶段都需要作出决策，从而使整个过程达到最好的效果。

6 5．1 多阶段决策过程与方法 因此，各个阶段决策的不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个决策过程的一条活动路线，这样一个前后关联具有链状结构的多阶段决策过程就称为多阶段决策过程，也称为序贯决策过程（见图5－1所示），这种问题称为多阶段决策问题。

7 图5－1 在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，因此处理这种问题的方法称为动态规划方法。

8 这是一个以空间位置为特征的多阶段决策问题, 决策顺序为 ABCDE。
例5.1 如图5－2所示，给定一个线路网络，两点之间连线上的数字表示两点间的距离（或费用）。试求一条由A到E的线路，使总长度最小（或总费用最小）。 A D2 D1 C1 B3 B2 D3 E B1 1 2 3 5 4 C2 图5－2 这是一个以空间位置为特征的多阶段决策问题, 决策顺序为 ABCDE。

9 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。

10 如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。

11 问题：试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。
显然，这是一个以时间为特征的多阶段决策问题。

12 例5.1通常称为最短路径问题，这是一个典型的多阶段决策问题。以它为例来说明用动态规划求解多阶段决策问题的特点与方法原理。

13 从图5－2可以看出，从A到E一共有18条不同的线路，即18种不同的方案。显然其中必存在一条从全过程看效果最好的线路，称之为最佳线路。
D2 D1 C1 B3 B2 D3 E B1 1 2 3 5 4 C2 图5－2

14 对最佳线路来说，它具有如下的重要性质：设最佳线路第二、三、四阶段决策的结果是选择 ， （见图5－3）。
对最佳线路来说，它具有如下的重要性质：设最佳线路第二、三、四阶段决策的结果是选择 ， （见图5－3）。

15 其中从第二阶段初始状态 到E点的路径也是从 到E点一切可能路径中的最佳路径，这性质很容易用反证法证明：设从 到E另有一条更短的路线 。则用

16 显然这个性质不仅对 是成立的，而且对最短路径中的任一个中间点都是成立的。因此，最佳路径中任一个状态（中间点）到最终状态（最终点）的路径也是该状态到最终状态一切可能路径中的最短路径。

17 图5－3

18 这种由后向前逆向递推的方法正是动态规划中常用的逆序法(逆向归纳法)。
利用这个性质，从最后一段开始，由终点向起点逐阶递推，寻求各点到终点的最短路径，当递推到起始点A时，便是全过程的最短路径。 这种由后向前逆向递推的方法正是动态规划中常用的逆序法(逆向归纳法)。

19 我们以例5.1为例,说明如何用逆向归纳法来求解多阶段决策问题。 由图5－2，将决策全过程分为四个阶段。

20 从最后一个阶段开始计算： （1）k =4，第四阶段 在第四阶段，有三个初时状态：D1,D2 与D3，而全过程的最短路径究竟是经过D1，D2 ，D3中的哪一点，目前无法肯定，因此只能将各种可能都考虑，若全过程的最短路径经过D1，则从D1到终点的最短路径距离为：f4(D1)=3； 而类似可得：f4(D2)=1 , f4(D3)=5 。

21 （2） ，第三阶段 在第三阶段有两个初始状态：C1 与C2。同样我们无法确定全过程的最短路径是经过C1还是C2。因此两种状态都要计算。

22 若全过程最短路径经过C1，则由C1到E有三条支路：C1－D1－E、C1－D2－E及C1－D3－E，而对支路C1－D1－E，其最短路径应为：从C1－D1的距离 ，再加上D1－E的最短路径 ，故有

23 由前述性质可知，若全过程最短路径经过C1，则C1到终点E应是一切可能路径中最短路径，因此可有
即由C1－E的最短路径为C1－D1－E，最短距离为5。同理，有 即由C2－E的最短路径为C2－D1－E， 最短距离为4。

24 从 的最短路径为B1－C2－D1－E，最短距离：7 从 的最短路径为B2－C1－D1－E，最短距离：6
（2） ，第二阶段 第二阶段有三种初始状态： 。 同理可得到 因此 从 的最短路径为B1－C2－D1－E，最短距离：7 从 的最短路径为B2－C1－D1－E，最短距离：6 从 的最短路径为B3－C1－D1－E，最短距离：8

25 （4） ，第一阶段 第一阶段只有一种初始状态A，可计算： 即从A—E 的最短路径为A－B2－C1－D1－E ， 最短距离为8。

26 从以上的计算过程可看出，动态规划方法的基本思想是，把一个比较复杂的问题分解成一系列同一类型的更容易求解的子问题，对每个子问题，计算过程单一化，便于应用计算机。同时由于对每个子问题都考虑到最优效果，于是就系统地删去了大量的中间非最优化的方案组合，使得计算工作量比穷举法大大减少,但是其本质还是穷举法。

27 由上述分析，可将动态规划方法求解多阶段决策问题的特点归纳如下：

28 （1）每个阶段的最优决策过程只与本阶段的初始状态有关，而与以前各阶段的决策无关。换言之，本阶段之前的状态与决策，只是通过系统在本阶段所处的初始状态来影响系统的未来。具有这种性质的状态称为无后效性（即马尔可夫性）状态。 动态规划方法适用于求解具有无后效性的多阶段决策问题。

29 （2）对最佳路径（最优决策过程）所经过的各个阶段，其中每个阶段始点到全过程终点的路径，也是子决策中的最佳路径，整体最优必然有局部最优。
这就是Bellman提出的著名的最优化原理。

30 （3）在逐段递推过程中，每阶段选择最优决策时，不应只从本阶段的直接效果出发，而应从本阶段开始的往后全过程的效果出发，
应该考虑两种效果：一是本阶段初到本阶段终（下阶段初）所选决策的直接效果；二是由所选决策确定的下阶段初往后直到终点的所有决策过程的总效果，也称为间接效果。 这两种效果的结合必须是最优的。

31 （4）经过递推计算得到各阶段的有关数据后，反方向即可求出相应的最优决策过程。

32 5．2 动态规划的基本概念和递归方程 （1）阶段 阶段(step)是对整个决策过程的自然划分。通常根据时间顺序或空间顺序的特征,来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用 k=1,2, …,n表示。

33 （2）状态 状态（state）表示每个阶段开始时决策过程所处的自然状况……。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常要求状态是直接的或间接可以观测的。

34 （2）状态 描述状态的变量称状态变量（state variable）。变量允许取值的范围称允许状态集合(set of admissible states)。用xk表示第k阶段的状态变量，它可以是一个数或一个向量。用Xk表示第k阶段的允许状态集合,有xk ∈ Xk 。

35 （2）状态 n个阶段的决策过程有n+1个状态变量， xn+1表示xn演变的结果。根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便,有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。

36 （3）决策 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择过程称为决策（decision），在最优控制问题中也称为控制（control）。

37 （3）决策 描述决策的变量称决策变量（decision variable），变量允许取值的范围称为允许决策集合（set of admissible decisions）。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数， 用Uk(xk)表示xk的允许决策集合,决策过程就是选择uk(xk) ∈ Uk(xk)的过程。决策变量简称决策。

38 （4）策略 决策组成的序列称为策略（policy）。由初始状态 开始的全过程的策略记作 ，即: 由第k阶段的状态开始到终止状态的后部子过程的策略记作 ，即: .

39 ， （4）策略 类似地，由第k到第j阶段的子过程的策略记作 :可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，表示为：

40 （5）状态转移方程 在确定性决策过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定,这个过程称作状态转移。用状态转移方程（equation of state transition）表示这种演变规律，写作为: （5.1）

41 （6）指标函数和最优值函数 指标函数(objective function)是衡量决策过程和决策结果优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数。表示为： 指标函数应具有可分离性，即 可表为 的函数，记为

42 这些形式下第k 到第j 阶段子过程的指标函数为 。
决策过程在第j阶段的阶段指标取决于状态xj和决策uj，用 vj (xj,uj) 表示,即为对整体目标函数的贡献。整体指标函数由 vj (j=1,2,…,n)组成，常见的形式有： 阶段指标之和，即： 阶段指标之积，即： 阶段指标之极（或极小），即： 这些形式下第k 到第j 阶段子过程的指标函数为 。

43 根据状态转移方程,指标函数 Vnk 还可以表示为状态xk和策略pnk的函数，即Vnk (xk, pnk)。在 给定时,指标函数Vnk 对pnk 的最优值称为最优值函数（optimal value function），记为 fk (xk) ，即： 实际上, fk (xk)是从状态xk开始的后继最有决策的目标函数值。

44 （7）最优策略和最优轨线 使指标函数Vnk 达到最优值的策略是从k开始的后部子过程的最优子策略，记作 。 是全过程的最优策略，简称最优策略（optimal policy）。从初始状态 出发，决策过程按照 和状态转移方程演变所经历的状态序列 称为最优轨线（optimal trajectory）。

45 （8）递归方程 如下方程称为递归方程 fn+1 (xn+1) 称作边界条件。
(5-2)

46 （8）递归方程 递归方程中 当 为加法时，fn+1 (xn+1) =0 当 为乘法时， fn+1 (xn+1)=1 递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子策略。用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由k=n+1逆推至k=1，故这种解法称为逆序解法。当然，对某些动态规划问题，也可采用顺序解法。

47 5．3 最优性原理与建模方程 动态规划的最优性原理是
“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优决策” 简言之，一个最优策略的子策略总是最优的。

48 但是，随着人们深入地研究动态规划，逐渐认识到：对于不同类型问题所建立的严格定义的动态规划模型，必须对相应的最优性原理给以必要的验证。即是说，最优性原理不是对任何决策过程都普遍成立的。而且，“最优性原理”与动态规划基本方程并不是无条件等价的，两者之间也不存在确定的蕴含关系。

49 而动态规划的递归方程在动态规划的理论和方法中起着更为重要的作用，反应动态规划递归方程的是最优性原理，递归方程是策略最优性的充要条件，而最优性原理仅仅是策略最优性的必要条件。所以把动态规划的递归方程作为动态规划的理论基础可能更为合理。

50 设阶段数为n 的多阶段决策过程，其阶段编号为k=0，1，…，n-1 。允许策略
动态规划的递归方程： 设阶段数为n 的多阶段决策过程，其阶段编号为k=0，1，…，n-1 。允许策略 最优策略的充要条件，是对任一个k， 0<k<n-1和s0 ∈ S0有， 其中， 。它是由给定的初始状态s0和子策略p0,k-1所确定的k段状态。当V是效益函数时，opt取max；当V是损失函数时，opt取min。

51 推论:若允许策略 是最优策略，则对任意的k， k=0，1，…，n-1, 它的子策略 对于 为起点的k到n-1子过程来说，必是最优策略。
此推论就是前面提到的动态规划的“最优性原理”，它仅仅是最优性策略的必要性，所以，动态规划的递归方程是动态规划的理论基础。

52 （2）正确选择状态变量xk ，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合Xk 。
纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列6个步骤，首先建立起动态规划的数学模型： （1）将决策过程划分成恰当的阶段。 （2）正确选择状态变量xk ，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合Xk 。 （3）选择决策变量uk ，确定允许决策集合Uk (xk) 。

53 （4）写出状态转移方程。 （5）确定阶段指标 vk (xk, uk)及指标函数Vnk 的形式（阶段指标之和，阶段指标之积，阶段指标之极大或极小等）。 （6）写出基本方程,即最优值函数满足的递归方程，以及边界条件。

54 建立动态规划模型，基本上是按照上述顺序，逐步确定。
建模是解决问题的第一步，也是较困难的一步，动态规划不像线性规划那样有统一的模型和处理方法，须针对具体问题具体分析，综合考虑多方面因素。譬如，如何划分阶段，如何选择正确的状态变量和决策变量，如何构造递归方程等。需要一定的技巧，需要练习，不断总结和积累经验。

55 5．4 动态规划的应用案例 5．4．1 背包问题 它是一个典型的多阶段决策问题。一维背包问题是：一位旅行者的背包能承受最大载重量是b(kg)，现有i种物品供他选择装入，第i种物品单件重量为ai (kg) ,其价值（或其他参数）为ci ，1 ≤ i ≤ n 。设装载数量是 xi ,则总价值是携带数量xi的函数,即ci xi 。问旅行者应如何选择所携带物品的件数,以使总装载价值最大？

56 背包问题实际上就是运输问题中车船的最优配载问题，还可以广泛地用于解决其他的问题,或者作为其他复杂问题的子问题。其一般的整数规划模型可表述为：

57 （1）阶段k ：即需要装入的n种物品的次序，每段装入一种物品，共n段。
下面用动态规划方法来求解。 （1）阶段k ：即需要装入的n种物品的次序，每段装入一种物品，共n段。 （2）状态变量sk ：即在第k段开始时允许装入物品的总重量，即可以动用的资源。显然有s1 = b 。 （3）决策变量xk ：即装入第k种物品的件数。

58 （4）状态转移方程： sk+1 =sk - akxk 允许的决策集合是 （5）递归（基本）方程是：

59 例5.3 一分销商拟用一10吨载重的大卡车装载3种货物，资料见表5－1，问应如何组织装载，可使总价值最大？
表5－1 数据资料 解：设装载第i种货物的件数为xi ，则有整数线性规划 货物编号 单位质量 单位价值

60 用动态规划方法的顺序解法求解，则 当 k=3时， 计算结果列入表5－2。 表5－2
s3 x3 f3(s3)

61 当 k=2 时， 计算结果列入表5－3。 表5－3 s2 4 5 6 7 8 9 10 x2 0 1 V2 0 5 V2+ f3 6 5 f2(s2) 11 12 1 2

62 当 k=1 时, 即 ，依状态转移方程反推，此时有 ，依第2段计算结果, 。有 ，由第3段计算结果知， 。 即最优方案为 ，最大价值为13。
即 ，依状态转移方程反推，此时有 ，依第2段计算结果, 。有 ，由第3段计算结果知， 。 即最优方案为 ，最大价值为13。

63 5．4．2 投资问题 例5.4 现有资金5百万元，可对三个项目进行投资，投资额均为整数（单位：百万元），其中2＃项目的投资不得超过3百万元，1＃和3#项目得投资均不得超过4百万元，3#项目至少要投资1百万元，每个项目投资5年后，投资额与预计收益见表5－4。

64 问如何投资可望获得最大收益。 表5－4 投资收益
投资项目 1 2 3 4 1＃ 6 10 12 2＃ 5 － 3＃ 8 11 15

65 解： 此投资问题可分三个阶段，在第k阶段确定k# 项目的投资额，令状态变量sk为对1＃，2＃，…,( k-1)#项目投资后剩余的资金额； xk为对k＃项目的投资额； rk(xk)为对k#项目投资xk的收益， fk(sk)为应用剩余的资金sk 对k# ， k# ,(k+1)#，…，N#进行最优化投资可获得的最大收益。 状态转移方程为：

66 解： 为了获得最大收益，必须将5百万元全部用于投资，故假想有第4阶段存在时，必有s4 =0，于是得递归方程：

67 当 k=3，（3＃至多投资4百万元，至少投资1百万元） 当 k=2，（2＃投资不超过3百万元）

68 当k=1 时， s1 =5 （最初有5百万元，3＃至少投资1百万元） 应用顺序反推可知最优投资方案。 方案1： ； 方案2： 。 最大收益均为21百万元。

69 一、定价问题 某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元和8元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年的利润如表3-1所示。 表3-2 每年预计利润额 单价 第一年 第二年 第三年 第四年 第五年 5元 6元 7元 8元 10 12 14 16 13 15 20 18 25 24

70 建立数学模型 按年划分阶段，k=1,2,...,5 每阶段的状态变量为本年（上一年已确定）的价格，状态变量的可行集 Sk=(5,6,7,8)。 决策变量为每年依据当年价格为下一年度决定价格，根据题意决策变量的可行集合： 采用逆序算法，因此状态转移方程是 最优值函数递推方程为

71 采用逆序法，设 当k=5时，S5=(5,6,7,8)，由表3-1得到 当k=4时， S4=(5,6,7,8)，由递推方程 得
进行各阶段的计算 采用逆序法，设 当k=5时，S5=(5,6,7,8)，由表3-1得到 当k=4时， S4=(5,6,7,8)，由递推方程 得

72 继续求解 同理得其它各阶段的最优解

73 反推得最优路线 按照与求最优值函数方向相反的顺序求最优状态路线：最优决策变量。
即从第一年单价应为8元开始，向后推算，得第二年定价8元，第三年定价7元，第四年定价6元，第五年定价5元。 最大利润值为92万元。

74 也可用决策图求解

75 某公司将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂得设备后可产生如表3-2所示的利润，应怎么分配设备可使公司总利润最大？
二、资源分配问题 某公司将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂得设备后可产生如表3-2所示的利润，应怎么分配设备可使公司总利润最大？ 工厂 设备数 甲 乙 丙 丁 1 2 3 4 5 6 7 10 12 15 9 13 11

76 建立数学模型 按工厂次序划分阶段，k=1，2，3，4 状态变量为各阶段可用于分配的设备总台数 决策变量是分配给第k工厂的设备数
采用逆序算法，状态转移方程 最优值函数递推方程

77 第4阶段的最优解 当k=4时，S4=(0,1,2,3,4,5) 1 2 3 4 5 6 11 12

78 第3阶段的最优解 当k=3时，S3=(0,1,2) 1 5 4 2 10 6 9

79 第3阶段的最优解（续） 当k=3时，S3=3 3 1 2 5 10 11 6 4 14

80 第3阶段的最优解（续） 当k=3时，S3=4 4 1 2 3 5 10 11 12 6 16 15 1，2

81 第3阶段的最优解（续） 当k=3时，S3=5 5 1 2 3 4 10 11 12 6 17 21 15

82 第2阶段的最优解 当k=2时，S2=(0,1,2) 1 3 5 2 7 10 8

83 第2阶段的最优解（续） 当k=2时，S2=3 3 1 2 7 9 14 10 5 13 12

84 第2阶段的最优解（续） 当k=2时，S2=4 4 1 2 3 7 9 12 16 14 10 5 17 1，2

85 第2阶段的最优解（续） 当k=2时，S2=5 5 1 2 3 4 7 9 12 13 21 16 14 10 19 17 15 0，2

86 第1阶段的最优解（续） 当k=1时，S1=5 5 1 2 3 4 6 7 10 12 15 21 17 14 23 20

87 反向求最佳状态路线 方案一 方案二 工厂名 分配设备数 甲 乙 丙 丁 1 2

88 某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。
三、生产存储问题 某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。 时期（月） 需求量（dk） 1 2 3 4

89 已知的其它条件 已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优生产计划。 设第k月的生产量uk，存储量为Sk,则总成本为

90 建立数学模型 以月划分阶段，k=1,2,3,4 各阶段决策变量为该阶段生产量uk， 状态变量为该阶段存储量Sk。
采用逆序算法，则状态转移方程为 最低成本递推公式是

91 当k=4时，d4=4,因第四阶段末无存货， 因此S4=(0,1,2,3,4)
第四阶段的最优解 当k=4时，d4=4,因第四阶段末无存货， 因此S4=(0,1,2,3,4) S4 u4 本期成本 C4 S5 f5(S5) f4(S4) 生产 存储 1 2 3 4 7 6 5 0.5 1.5 6.5 5.5

92 当k=3时，由于 ，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6)
第三阶段最优解 当k=3时，由于 ，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6) S3 u3 本期成本 C3 S4 f4(S4) f3(S3) 生产 存储 2 3 4 5 6 7 8 9 1 6.5 5.5 12 12.5 13 13.5 11

93 第三阶段最优解:S3=1 S3 u3 C3 S4 f4(S4) f3(S3) 1 2 3 4 5 6 7 8 0.5 4.5 5.5 6.5
本期成本 C3 S4 f4(S4) f3(S3) 生产 存储 1 2 3 4 5 6 7 8 0.5 4.5 5.5 6.5 7.5 8.5 11.5 12.0 12.5 13.0 10.5

94 第三阶段最优解:S3=2 S3 u3 C3 S4 f4(S4) f3(S3) 2 1 3 4 5 6 7 8 6.5 5.5 11.5
本期成本 C3 S4 f4(S4) f3(S3) 生产 存储 2 1 3 4 5 6 7 8 6.5 5.5 11.5 12.0 12.5 10.0

95 第三阶段最优解:S3=3,4 S3 u3 C3 S4 f4(S4) f3(S3) 3 1 2 4 5 6 1.5 5.5 6.5 7.5 8
本期成本 C3 S4 f4(S4) f3(S3) 生产 存储 3 1 2 4 5 6 1.5 5.5 6.5 7.5 8 11.5 12.0 9.5 7 9

96 第三阶段最优解:S3=5,6 S3 u3 C3 S4 f4(S4) f3(S3) 5 1 4 2.5 6.5 3 5.5 2 8 8.5 6
本期成本 C3 S4 f4(S4) f3(S3) 生产 存储 5 1 4 2.5 6.5 3 5.5 2 8 8.5 6

97 当k=2时，d2=3，由于最生产能力为6，而d1=2，因此S2=(0,1,2,3,4)
第二阶段最优解 当k=2时，d2=3，由于最生产能力为6，而d1=2，因此S2=(0,1,2,3,4) S2 u2 本期成本 C2 S3 f3(S3) f2(S2) 生产 存储 3 4 5 6 7 8 9 1 2 11.0 10.5 8.0 17 17.5 16

98 第二阶段最优解:S2=1 S2 u2 C2 S3 f3(S3) f2(S2) 1 2 3 4 5 6 7 8 9 0.5 5.5 6.5
本期成本 C2 S3 f3(S3) f2(S2) 生产 存储 1 2 3 4 5 6 7 8 9 0.5 5.5 6.5 7.5 8.5 9.5 11.0 10.5 8.0 16.5 17 15.5 17.5

99 第二阶段最优解:S2=2 S2 u2 C2 S3 f3(S3) f2(S2) 2 1 3 4 5 6 7 8 9 10 11.0 10.5
本期成本 C2 S3 f3(S3) f2(S2) 生产 存储 2 1 3 4 5 6 7 8 9 10 11.0 10.5 8.0 16.0 16.5 15.0 17.0 18.0

100 第二阶段最优解:S2=3 S2 u2 C2 S3 f3(S3) f2(S2) 3 1 2 4 5 6 7 8 9 1.5 5.5 6.5
本期成本 C2 S3 f3(S3) f2(S2) 生产 存储 3 1 2 4 5 6 7 8 9 1.5 5.5 6.5 7.5 8.5 9.5 10.5 11.0 8.0 5.0 12.5 16.0 14.5 15.5 16.5 17.5

101 第二阶段最优解:S2=4 S2 u2 C2 S3 f3(S3) f2(S2) 4 1 2 3 5 6 7 8 9 10 10.5 8.0
本期成本 C2 S3 f3(S3) f2(S2) 生产 存储 4 1 2 3 5 6 7 8 9 10 10.5 8.0 5.0 12.5 14 15 16 17

102 第一阶段最优解 当k=1时，d1=2，S1=0 S1 u1 C1 S2 f2(S2) f1(S1) 2 3 4 5 6 7 8 9 1
本期成本 C1 S2 f2(S2) f1(S1) 生产 存储 2 3 4 5 6 7 8 9 1 16.0 15.5 15.0 12.5 21 21.5 22 20.5

103 最优解 从第一阶段向后反推最优路线，总结可得 时期 K 最优生产量 总成本 Sk Sk+1 1 2 3 4 5 6 8 1.5 9 20.5
期初存货 期末存货 最优生产量 该期成本 总成本 Sk Sk+1 1 2 3 4 5 6 8 1.5 9 20.5 12.5 11

104 5．4．3 排序问题 设有 n个工件需要在机床A、B上加工，每个工件都必须讲过先A而后B得两道加工工序。以ai ,bi分别表示工件i(0 ≤ i ≤ n) 在A、B上的加工时间。问应如何在两机床上安排加工得顺序，使在机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少？

105 加工工件在机床A和B上各有加工顺序问题，它们在A、B两台机床上加工工件的顺序是可以不同的。当机床B上的加工顺序与机床A不同时，意味着在机床A上加工完毕的某些工件，不能在机床B上立即加工，而是要等到另一个或一些工件加工完毕后才能加工。这样，使机床B的等待加工时间加长，从而使总的加工时间加长了。

106 可以证明：最优加工顺序在两台机床上可同时实现。因此，最优排序方案可以在机床A、B上加工顺序相同的排序中去寻找。即使如此，所有可能的方案仍有n
可以证明：最优加工顺序在两台机床上可同时实现。因此，最优排序方案可以在机床A、B上加工顺序相同的排序中去寻找。即使如此，所有可能的方案仍有n! 个，这是一个不小的数，用穷举法是不现实的。下面用动态规划方法来研究同顺序两台机床加工n 个工件的排序问题。

107 当加工顺序取定之后，工件在A上加工时没有等待时间，而在B上则常常等待，因此，寻求最优排序方案只有尽量减少在B上等待加工的时间，才能使总加工时间最短。

108 设第 i个工件在机床A上加工完毕以后，在B上要经过若干等待时间才能加工，故对同一个工件来说，在A、B上总是出现加工完毕的时间差，我们可以它来描述加工状态。

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

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

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

112 f(X, t,i)为由状态 (X, t)出发，在A上先加工工件i ，然后再对以后的加工工件采取最优顺序后，把X中工件全部加工完所需要的时间。

113 f(X, t,i,j)为由状态(X, t) 出发，在A上相继加工工件i与 j后，对以后加工的工件采取最优顺序后，将把X 中的工件全部加工完所需要的时间。

114 因而，不难得到 式中状态t 的转换关系参看图5－4。

115 记 上式就可合并写成 其中 表示在集合X中去掉工件i后剩下的工件集合。

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

117 代替t ， aj代替ai ，bj 代替bi ，则可得
仿照 的定义，以 代替 ， 代替t ， aj代替ai ，bj 代替bi ，则可得 故 将i，j 对调，可得 由于f(X,t) 为t的单调上升函数，故当 时，有

118 因此，不管t 为何值，当 时，工件 i放在工件j 之前加工可以使总的加工时间更短。而由 和 的表示式可知，这只需要下面不等式成立就行。即
将上不等式两边减去 a与 b，得 即

119 这个条件就是工件i应该排在工件 j之前的条件。即对于从头到尾的最优排序而言，它的所有前后相邻接的两个工件所组成的工件对，都必须满足上述不等式。

120 根据以上条件，得到确定最优排序的规则如下：
（1）输入工件的加工时间的工时矩阵: （2）在工时矩阵M中找出最小元素(若最小的不止一个，可任选其一)；若它在上行，则将相应的工件排在最前位置；若它在下行，则将相应的工件排在最后位置。

121 （3）将排定位置的工件所对应的列从M中划掉，然后对余下的工件重复按（2）进行。如此继续下去，直至把所有工件都排完为止。
这个同顺序同台机床加工n个工件的最优规则，概括起来说，它的基本思想是：尽量减少在机床B上等待加工的时间。因此，把在机床B上加工时间长的工件先加工，在B上加工时间短的工件后加工。

122 例5.5 设有5个工件需要在机床A、B上加工，加工的顺序是先A后B，每个工件所需加工时间（单位：小时）如表5－5所示，问如何安排加工顺序，使机床连续加工完所有工件的加工总时间最少？并求出总加工时间。 表5－5 工件加工时间 工件号码 A机床 B机床 1 3小时 6小时 2 7小时 2小时 3 4小时 4 5小时 5

123 解：工件的加工工时矩阵为 根据最优排列规则，故最优加工顺序为： 总加工时间为28小时。

124 5．4．4 旅行售货商问题（TSP） 旅行售货商问题就是在网络 N上找一条从初始点出发，经过每个点v1 ,v2 ,…,vn各一次最后返回初始点的最短路线和最短路程。

125 5．4．4 旅行售货商问题（TSP） 先把它看成一个多阶段决策问题。从初始点出发，每次选择下一步要经过的点，经过n个阶段，每个阶段的决策是选择下一个点。

126 5．4．4 旅行售货商问题（TSP） 如果用所在的位置来表示状态，那么状态和阶段数就不能完全决定决策集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用(vi,V) 表示状态， vi是阶段所处的初始点，V是还没有经过的点集合。在状态 (vi,V)的决策集合V中，取决策vi ∈ V ，获得的效益是vi 到vj 的距离dij ，转入下一个状态 (vj,V \{vj }) ，现在用最优化原理来找递推公式。

127 用 表示从vi点出发，经过V中的点各一次，最后回到 v0点的最短路程， V是一个顶点集合，|V |=k， dij是 vi到vj 的弧长，则
(5.3)

128 例5.6 对图5－5，求出从v1出发，经过v2 ,v3 ,v4 各一次，又返回到v1的最短路线和最短路程。用矩阵D表示vi 到vj的距离，即 vi 到vj的距离为矩阵D的每一个元素dij 。
图5-5

129 按照 的定义， 表示从v1出发，经过v2,v3,v4各一次，最后回到v1的最短路，利用（5.3）则得

130 k=1时的求解： k=2时的求解： ，

131 该案例中的阶段数不是按照时间因素划分的，也不是子决策的个数。而是在不同的状态下，还需要经过的顶点个数。在具体的实际问题中，需要创造性的解决。
k=3时的求解： 最优路线为 ，路程长为23。 该案例中的阶段数不是按照时间因素划分的，也不是子决策的个数。而是在不同的状态下，还需要经过的顶点个数。在具体的实际问题中，需要创造性的解决。

132 5．4．5 Stackelberg 博弈 将动态规划中逆向归纳法的思想应用于企业在市场上进行竞争时的互动决策，就得到所谓Stackelberg博弈。

133 5．4．5 Stackelberg 博弈 假定有两个企业在同一产品市场上进行产量决策竞争。 企业1是领先者（Leader），先做决策，具有先动优势；企业2是跟随者（Follower）,后做决策。后行动者能观察到先行动者的产量决策结果，具有信息优势。 设企业i的产量为qi ，利润为 其中

134 k=2时，企业2做决策。企业2会选择产量q2 ，满足： k=1时，企业1做决策。企业1会选择产量q1 ，满足：
按照决策顺序，划分为两个阶段。 k=2时，企业2做决策。企业2会选择产量q2 ，满足： k=1时，企业1做决策。企业1会选择产量q1 ，满足： 即给定式（5.4）确定的反应函数 ，企业1选择其最优产量 ，它由式（5.5）决定，企业2选 。 Stackelberg在1934年提出了这一动态决策概念。称这种博弈为Stackelberg博弈（Stackelberg game）。 (5-4) (5-5)

135 利用下面的例子来说明Stackelberg博弈的动态决策过程。
设有两个生产同质产品并在同一市场展开竞争的企业，记为企业1和企业2。我们将企业的选择变量定义为企业可选择的产量qi ，企业追求利润最大化。选择变量的范围为 ， 为逆需求函数，也可以理解为价格, c为单位变动成本。 则企业的利润函数为 i=1,2

136 通过 和 看到：领导者的产量变大了，追随者的产量变小了。这反映出了决策顺序对决策结果的影响。
k=2 时，企业2做决策。由 得到 k=1 时，企业1做决策。由 得到 代入 ，得 。 通过 和 看到：领导者的产量变大了，追随者的产量变小了。这反映出了决策顺序对决策结果的影响。

137 5．4．6 动态规划在非线性规划 求解中的应用 非线性规划有自己特有的求解方法。 非线性规划中，一些特殊的问题（如目
标可分离）可以用动态规划的方法求解。 例5.7 求解如下的非线性规划问题：

138 解：该问题可看作将资源c分配给 ，分配的目标是使目标 最大化。 该问题划分为3个阶段，状态变量sk 可以看作确定 xk时尚拥有的资源。

139

140 5．4．7 动态规划在基础数学中的应用 几何平均值不等式是纯数学中的一个熟知结论。
动态规划的思想也可以应用到基础数学中。例如 几何平均值不等式是纯数学中的一个熟知结论。 即： n个非负的实数 ，满足 ,则 , n个数相等时其乘积最大。

141 下面试图用动态规划的思想证明这个结论。 定义函数 则函数 有递归方程和边界条件:
则函数 有递归方程和边界条件:

142 用数学归纳法，证明 有如下的形状: k=1 时，结论是正确的。假设 k=m+1 时，结论 是正确的,则根据递归方程,有: 上式对 am求导数,发现 时达到最大值。 因此有 根据 则有

143 5.5 动态规划实际应用案例: —机器生产负荷分配
5.5 动态规划实际应用案例: —机器生产负荷分配 某企业投入1000台机器加工生产一种产品,设备可以在高、低两种不同的负荷下进行生产。高负荷下，每台机器的年产值为8千万,设备的损耗率为30%,即有30%的设备报废。低负荷下，每台机器的年产值为5千万,设备的损耗率为10%.试 制定一个五年生产计划，在每年开始时决定分配机器的工作方式，使企业五年的总产值最大。

144 这是一个5阶段的动态决策问题。阶段变量k表示年度，状态变量sk表示第k年初拥有的可以投入生产的机器数量,决策变量uk表示第k年度中分配在高负荷下生产的机器数量,自然sk-uk就是该年度分配在低负荷下生产的机器数量。这里 sk , uk可以取为连续变量,可以这样来理解：例如sk=0.6,表示一台机器在该年度正常工作时间只占60%； uk=0.3 表示一台机器在该年度的3/10时间里在高负荷下工作。

145 状态转移方程: 阶段的允许决策集合: 第k年度产品产值: 指数函数是: 定义最优值函数fk (sk)为第k年初从sk出发 到第5年度结束产品最大产值. 递推关系为:

146 计算过程如下： 因为 f5 的表示式是 u5 的单调函数，所以最 优决策 ,即在第5年,将全 部机器进行高负荷生产； 同理，最优决策 即在第4年,将全部机器进行高负荷生产；

147 从上面的计算可知，最优策略是前两年将全部完好机器投入低负荷生产，后三年将全部机器投入高负荷生产，最高产值是23700万元。
依次可以： 从上面的计算可知，最优策略是前两年将全部完好机器投入低负荷生产，后三年将全部机器投入高负荷生产，最高产值是23700万元。

148 Thank You !