第十二讲   动态规划

（教材： 第十二章   动态规划）



1 2 3 4(本页)

下面具体计算是由后向前推算。

•  在第 4 阶段，所能利用的原料数量为 ，

。

由于 ，取 可达到最大值， 。

•  在第 3 阶段，所能利用的原料数量为 ，

。

由于 以及 ，上式变成



上述最大值是对  取的。取 =0 可达到最大值， 。

•  在第 2 阶段，所能利用的原料数量为 ，



由于 以及 ，上式变成



上述最大值是对 而取的， 可达到最大值， 。

•  在第 1  阶段，所能利用的原料数量为 ，

由于 以及 ，

上述最大值是对 而取的， 可达到最大值。因而  。由已知条件，得 (万元)。

 〔例 3〕生产自动线加工顺序问题（教材 P159 例4）某自动生产线轮番成批加工五种零件。已知加工完一种零件后改换加工别的零件时，其生产准备时间（小时）如下表所示：

从     到	1	2	3	4	5
1	0	3	1	5	4
2	1	0	5	4	3
3	5	4	0	2	1
4	3	1	3	0	3
5	5	2	4	1	0

试设计一种零件轮番加工顺序，使自动线用于生产准备的停工时间最短。

解 教材中将加工的零件看作城市，加工完某种零件后再换另一种零件加工看作售货员从一个城市出发到另一个城市，更换加工零件时的生产准备时间看作城市间距离。因此五种零件轮番加工一遍相当于售货员走遍所有城市回到原出发城市，教材中将上述问题看作旅行售货员问题。这里我们直接应用动态规划方法来解该问题。

假设加工周期开始时处于加工零件 1 的状态。分一个加工周期为 5 个阶段，加工第 1 个零件为第 1 阶段，，加工第 5 个零件为第 5 阶段。前四个阶段应把零件 加工一遍，在第 5 个阶段应回至加工零件 1。

为描述每个阶段开始时自动线的状态，应该指明两个信息：一是已经加工了几个零件，一是现在处于加工哪个零件的状态。因此以 （）来表示第 个阶段的状态变量：其中 是第 个阶段前已经加工的零件， 表示自动线在第 个阶段开始时处于加工第  个零件的状态。根据假设，零件 1 不列入各阶段已经加工的零件集合 之内。

每个阶段的决策变量是该阶段将加工的零件。第 个阶段的决策变量 应该在尚未加工的零件 之内选择。第 5 个阶段的决策变量只取零件 1。

用 表示加工完 种零件后转为加工 种零件所需的生产准备时间。这是动态规划模型中的直接指标。以 表示在第 个阶段处于状态（）时以最少的生产准备时间加工完剩余的零件并回到加工零件 1 的状态所需的时间，也即第 个阶段处于状态（）时的最优后部过程指标。

我们从最后阶段 ( ) 向前推算。该阶段所有零件 都已加工一遍，因而 ，状态变量的形式为 ，此处的 可以取 2、3、4、5 中的某一个。下一步将回到加工零件 1，因而 。其最优后部过程指标等于转而加工零件 1 的生产准备时间 。







。

当 时，已经加工的零件数为 3，后部过程最优指标计算结果如下表所示：

	8	6	8	-	5
	7	5	-	4	4
	10	-	8	9	3
	-	5	2	3	2

计算举例:



。

上表中的 列标明了该阶段在对应状态下的最佳决策。

当  时，已经加工的零件数为 2，后部过程最优指标计算结果如下表所示：

	7	5	-	-	5
	11	-	9	-	3
	10	-	-	9	3
	-	4	6	-	5
	-	4	-	3	4
	-	-	8	9	3

计算举例:



。

同理，当 k=2 时，已经加工的零件数为 1，后部过程最优指标计算结果如下表所示：

	10	－	－	－	3
	－	4	－	－	5
	－	－	7	－	3
	－	－	－	8	3

计算举例：

。

当 k=1 时，最优后部过程指标为

。

因此轮番加工的最短时间为 5 小时，加工顺序为 1 。

作业简答

思考题

1 2 3 4(本页)