《运筹学》课程教学资源（参考资料）4 多期规划模型

4多期规划模型 4.1引言 在多期规划制定过程中，最优化也有着重要的应用。我们到目前为止所涉及的大多数 问题都是单期的规划问题。本附录陈述的模型具有这样的特点：一个时期的决策多多少少 会影响下一个时期。例如，在一个时期里生产的产品超过了这一时期的需求，就会产生多 余的产品。在这个时期，这些多余的产品没有价值，但是，它们却可以为下一个时期所使 用。 这种在各个时期之间的交互作用可以用最优化模型简单地描述出来。事实上，现实问 题中的多数线性规划模型都是多期模型。与多期等价的同义词是“动态”（例如，一个多 期LP也可以说成是一个动态规划模型)。 在一些实际应用问题中，需求表现为多期是显而易见的。例如，为干酪产品的生产而 建立的LP模型就是一个多期模型，它的生产可能涉及数年的时间。每月，甚至每周就要 做一次生产决定。许多干酪的生产需要数月的时间。例如，用脱脂乳制成的坚硬的意大利 干酪就需要存储10个月以上。美国人称之为瑞士干酪产品的生产也要2到4个月。英国 切达干酪的级别就取决于它存储的时间。一个高档的切达干酪需要存储一年以上。显然， 对于这样的实际应用问题，多期应该是这类模型的重要特征。 为了建立模型，我们要将时间分解为若干个时期。整个模型就被分解为若干个相关的 单个时期的模型的组合。这些单个时期的模型（静态模型）是通过下面的方式进行连接的： 1) 对每一种物品和每一个时期，有一个存储变量（或一个连接变量）。存储变量表 示从一个时期到下一个时期物品传输的数量。 2) 对于每一种物品和每一个时期来说，有一个“来源量=使用量”约束（物质平 衡约束)。这一约束最简单的形式为：“开始存货量+生产量=期末存货量+需求 量”。 多期模型通常以一种滚动的或滑动的形式出现。在每一个时期的开始的时候求解模 型。当第一个时期的解答被执行后，便可以获得更多的数据和预测，模型就转向下一个时 期。这是第二个时期就变成了第一个时期，等等，整个过程重复进行。 在多期问题中，每个时期的长度也未必相等。例如，一个石油公司在为下一年做生产 计划的时候，很显然应该按季节来划分。一种可行的划分是：冬季从12月1日到3月15 日：春季从3月16日到5月15日：夏季从5月16日到9月15日：秋季从9月16日到 11月30日。 有一些公司，例如林木生产公司或矿产公司，它们的计划要长达50年以上。头两期 可能是一年一期，接下来可能是两年一期，再接下来可能是三年一期，最后三期可能是10 年一期。 各个时期之间的相互作用是通过引入存储变量来实现的。这些变量连接着邻近的时

1 4 多期规划模型 4.1 引言 在多期规划制定过程中，最优化也有着重要的应用。我们到目前为止所涉及的大多数 问题都是单期的规划问题。本附录陈述的模型具有这样的特点：一个时期的决策多多少少 会影响下一个时期。例如，在一个时期里生产的产品超过了这一时期的需求，就会产生多 余的产品。在这个时期，这些多余的产品没有价值，但是，它们却可以为下一个时期所使 用。 这种在各个时期之间的交互作用可以用最优化模型简单地描述出来。事实上，现实问 题中的多数线性规划模型都是多期模型。与多期等价的同义词是“动态”（例如，一个多 期 LP 也可以说成是一个动态规划模型）。 在一些实际应用问题中，需求表现为多期是显而易见的。例如，为干酪产品的生产而 建立的 LP 模型就是一个多期模型，它的生产可能涉及数年的时间。每月，甚至每周就要 做一次生产决定。许多干酪的生产需要数月的时间。例如，用脱脂乳制成的坚硬的意大利 干酪就需要存储 10 个月以上。美国人称之为瑞士干酪产品的生产也要 2 到 4 个月。英国 切达干酪的级别就取决于它存储的时间。一个高档的切达干酪需要存储一年以上。显然， 对于这样的实际应用问题，多期应该是这类模型的重要特征。 为了建立模型，我们要将时间分解为若干个时期。整个模型就被分解为若干个相关的 单个时期的模型的组合。这些单个时期的模型（静态模型）是通过下面的方式进行连接的： 1) 对每一种物品和每一个时期，有一个存储变量（或一个连接变量）。存储变量表 示从一个时期到下一个时期物品传输的数量。 2) 对于每一种物品和每一个时期来说，有一个“来源量=使用量”约束（物质平 衡约束）。这一约束最简单的形式为：“开始存货量+生产量=期末存货量+需求 量”。 多期模型通常以一种滚动的或滑动的形式出现。在每一个时期的开始的时候求解模 型。当第一个时期的解答被执行后，便可以获得更多的数据和预测，模型就转向下一个时 期。这是第二个时期就变成了第一个时期，等等，整个过程重复进行。 在多期问题中，每个时期的长度也未必相等。例如，一个石油公司在为下一年做生产 计划的时候，很显然应该按季节来划分。一种可行的划分是：冬季从 12 月 1 日到 3 月 15 日；春季从 3 月 16 日到 5 月 15 日；夏季从 5 月 16 日到 9 月 15 日；秋季从 9 月 16 日到 11 月 30 日。 有一些公司，例如林木生产公司或矿产公司，它们的计划要长达 50 年以上。头两期 可能是一年一期，接下来可能是两年一期，再接下来可能是三年一期，最后三期可能是 10 年一期。 各个时期之间的相互作用是通过引入存储变量来实现的。这些变量连接着邻近的时

2 期。作为一个例子，假设我们对每一个时期有一个明确的决策变量。也就是产品的生产量。 P表示第j期的生产量。更进一步，假设我们有一个合同，规定第j时期的产品销售量为 d。定义I表示第j期末的存储量。根据这个定义，第j期开始的存储量为I1。对于每一 个时期，按照LP设计，应该有“产品的来源=产品的使用”的约束。对于第二期，产品的 来源是第一期的存储量I1和本期的生产量P2。产品的使用量是本期的需求d2和本期末的 存储量量I2。例如，如果d2=60和d=40,对于第二期，约束是： I1+P2=60+2或I1+P2-I260 第三期的约束是： I2+P3-I3=40 注意：两个时期是如何通过I2进行何连接的（就是I2出现在第二期和第三期的约束之 中)。 在一些实际问题中，本时期的流出量并不需要一定等于下一期的流入量。例如，如果 产品是现金，连接变量是短期借贷。对于第二期借贷的每一美元来说，如果每期的利率为 5%,那么进入第三期就变为$1.05。 另一方面，如果产品是劳动力，那么每期估计会有10%的损耗。这样上面的两个约束 就变为： 0.90I1+P2-I2=60 0.90I2+P3-I3=40 这里，P是第I期租用的劳动力人数。 通过下面的例子可以对于单期计划和多期计划做一个简单的说明。 4.2一个多期生产规划问题 假设某一个公司生产一种产品，4个季度对该产品的需求预测如下： Spring Summer Autumn Winter 20 30 50 60 假设所有的需求都要满足，有下面两种极端的决策可以执行： 1)由需求来决定产量，没有存储： 2)每期生产40个单位，允许有存储，可以用它来满足需求。 存储会产生成本。改变生产水平也会产生成本。所以人们希望的成本最低的方案应该 是(1)和(2)某种组合（就是存储一定的产品，同时适当地改变生产水平）。 假设公司估计：从一个时期到下一个时期如果改变生产水平，则单位产品需要$600成 本，这些成本称为“租用和开张”成本：如果存储单位产品，则需要$700成本。初始的存 储量为0。每一个季度的生产水平是40个单位。我们在冬季结束的时候要恢复这一水平。 我们可以计算出在无存储情况下，改变生产水平而产生的成本如下： $600×(20+10+20+10+20)=$48,000 另一方面，在固定生产水平的情况下，存储成本如下： $700×(20+30+20+0)=$49.000 最低的成本决策可能是上面两个极端决策的某种结合。借助于LP,我们可以找到成

2 期。作为一个例子，假设我们对每一个时期有一个明确的决策变量。也就是产品的生产量。 Pj 表示第 j 期的生产量。更进一步，假设我们有一个合同，规定第 j 时期的产品销售量为 dj。定义 Ij 表示第 j 期末的存储量。根据这个定义，第 j 期开始的存储量为 Ij-1。对于每一 个时期，按照 LP 设计，应该有“产品的来源=产品的使用”的约束。对于第二期，产品的 来源是第一期的存储量 I1 和本期的生产量 P2。产品的使用量是本期的需求 d2 和本期末的 存储量量 I2。例如，如果 d2=60 和 d3=40，对于第二期，约束是： I1+P2=60+I2 或 I1+P2-I2=60 第三期的约束是： I2+P3-I3=40 注意：两个时期是如何通过 I2 进行何连接的（就是 I2 出现在第二期和第三期的约束之 中）。 在一些实际问题中，本时期的流出量并不需要一定等于下一期的流入量。例如，如果 产品是现金，连接变量是短期借贷。对于第二期借贷的每一美元来说，如果每期的利率为 5%，那么进入第三期就变为$1.05。 另一方面，如果产品是劳动力，那么每期估计会有 10%的损耗。这样上面的两个约束 就变为： 0.90I1+P2-I2=60 0.90I2+P3-I3=40 这里，Pi 是第 I 期租用的劳动力人数。 通过下面的例子可以对于单期计划和多期计划做一个简单的说明。 4.2 一个多期生产规划问题 假设某一个公司生产一种产品，4 个季度对该产品的需求预测如下： Spring Summer Autumn Winter 20 30 50 60 假设所有的需求都要满足，有下面两种极端的决策可以执行： 1） 由需求来决定产量，没有存储； 2） 每期生产 40 个单位，允许有存储，可以用它来满足需求。 存储会产生成本。改变生产水平也会产生成本。所以人们希望的成本最低的方案应该 是（1）和（2）某种组合（就是存储一定的产品，同时适当地改变生产水平）。 假设公司估计：从一个时期到下一个时期如果改变生产水平，则单位产品需要$600 成 本，这些成本称为“租用和开张”成本；如果存储单位产品，则需要$700 成本。初始的存 储量为 0。每一个季度的生产水平是 40 个单位。我们在冬季结束的时候要恢复这一水平。 我们可以计算出在无存储情况下，改变生产水平而产生的成本如下： $600 × (20 + 10 + 20 + 10 + 20) = $48,000 另一方面，在固定生产水平的情况下，存储成本如下： $700 × (20 + 30 + 20 + 0) = $49,000 最低的成本决策可能是上面两个极端决策的某种结合。借助于 LP，我们可以找到成

3 本最低的决策。 4.2.1描述 定义下面的变量： P=第i期的生产量，i=1,2,3,4: I=第i期末的存储量，i=1,2,3,4: U=从第i-1期到i期生产水平的增加量，i=1,2,3,4: D=从第i-1期到i期生产水平的减少量，i=1,2,3,4。 变量P:是决策变量。利用变量I、U:和D,我们可以计算出每个时期的成本。 为了使得一年的成本达到最小，我们要将要使下面的成本之和（存储成本和生产变动 成本)达到最小： (存储成本) $7001+$700I2+$700I3+$700I4+ (生产水平变动成本)$600U1+$600U2+$600U3+$600U4+S600U5 +$600D1+$600D2+$600D3+$600D4+S600D5 为了将第4期结束后生产水平恢复到40个单位，我们增加了变量U5和D5。 4.2.2约束 在每一个多期问题中，对于每一种产品和每一个时期都会有“来源=使用”约束（物 质平衡约束)。这类约束用语言来说就是： 开始时的存储+生产量结束时的存储=需求量。具体写出来就是： P1-I1 =20 I1+P2-I2=30 2+P3-I3=50 I3+P4 =60 注意：4和1并没有在第一个约束和最后一个约束出现，这是因为在最初和结束时的 存储要求是零。 如果现在就求解上面的模型，没有什么东西可以迫使U1、D1等等大于0。这样，解答 只能是极端策略。也就是，P1=20,P=30,P3=50,P4=60。这一解答暗示在每个时期结束 的时候，产量都要增加（最后一个时期除外）。当生产量增加时，我们用下面的约束来迫 使U1、U2、U3和U4取相应的的值： U1=>P1-40 U2=>P2-P1 U3=>P3-P2 U4=>P4-P3 当产量下降时，我们给出4个类似的约束： D1=>40-P1

3 本最低的决策。 4.2.1 描述 定义下面的变量： Pi = 第 i 期的生产量，i = 1, 2, 3, 4； Ii = 第 i 期末的存储量，i = 1, 2, 3, 4； Ui = 从第 i – 1 期到 i 期生产水平的增加量，i = 1, 2, 3, 4； Di = 从第 i – 1 期到 i 期生产水平的减少量，i = 1, 2, 3, 4。 变量 Pi 是决策变量。利用变量 Ii、Ui 和 Di，我们可以计算出每个时期的成本。 为了使得一年的成本达到最小，我们要将要使下面的成本之和（存储成本和生产变动 成本）达到最小： （存储成本） $700 Il + $700 I2 + $700 I3 + $700 I4+ （生产水平变动成本）$600 U1 + $600U2 + $600 U3 + $600 U4 + $600 U5 + $600 D1 + $600 D2 + $600 D3 + $600 D4 + $600 D5. 为了将第 4 期结束后生产水平恢复到 40 个单位，我们增加了变量 U5 和 D5。 4.2.2 约束 在每一个多期问题中，对于每一种产品和每一个时期都会有“来源=使用”约束（物 质平衡约束）。这类约束用语言来说就是： 开始时的存储+生产量-结束时的存储=需求量。具体写出来就是： P1 – I1 =20 I1 + P2 –I2 =30 I2 + P3 –I3 =50 I3 + P4 =60 注意：I4 和 I0 并没有在第一个约束和最后一个约束出现，这是因为在最初和结束时的 存储要求是零。 如果现在就求解上面的模型，没有什么东西可以迫使 U1、D1 等等大于 0。这样，解答 只能是极端策略。也就是，P1 = 20, P2 = 30, P3 =50, P4 = 60。这一解答暗示在每个时期结束 的时候，产量都要增加（最后一个时期除外）。当生产量增加时，我们用下面的约束来迫 使 U1、U2、U3 和 U4 取相应的的值： U1=> P1 - 40 U2=> P2 - P1 U3=> P3 - P2 U4=> P4 - P3. 当产量下降时，我们给出 4 个类似的约束： D1=> 40 - P1

D2=>P1-P2 D3=>P2-P3 D4=>P3-P4 为了达到在冬季结束时的生产水平回到40个单位的目的，我们引进了变量U5和D5, 以测定最后一个时期结束时生产量的变化水平。U5和D应该满足下面的约束： U5=>40-P4 D5=>P4-40 在运行模型之前，我们可以将上面关于产量变化约束由10个减少到5个。我们观察 下面两个约束： U2=>P2-P1 D2=>P1-P2 可以用下面一个约束取代： U2-D2=P2-P1 这样做非常经济。上面公式的目的就是迫使：当PB-P1=>0时，U2=P2-P1:当P1-P2 =>0时，D2=P1-P2。从经济的角度来看，在最优解答中，D2和P2最多只有一个大于0。 这是因为如果它们两个都大于0，则可以同时减去一个常数，使得变量既满足约束，又使 目标成本有所下降。 下面就是完整的模型： MODEL: !Minimize存储+生产水平变动成本； MIN 700*工1+700*工2+700*工3 +700*工4 +600*01+600*02+600*03 +600*04 +600*D1+600*D2+600*D3+600*,D4 +600*05+600*D5; !生产及存储的初始条件： [CNDBI]I0 0; [CNDBP]PO 40; !初始存储+生产=需求+期末存储： [INV1]I0+P1=20+I1: [INV2] I1+P2=30+I2: [INV3]I2+P3=50+I3: [INV4]I3 P4 60+工4： !上变化量-下变化量=这一时期的产量-前一时期的产量； [cHG1】01-D1=P1-P0: [CHG2] 02-D2=P2-P1; [CHG3]03-D3=P3-P2: [CHG4]04-D4=P4-P3: [CHG5]05-D5=P5-P4; !结束条件： [CNDEI]I4 0;

4 D2=> P1 –P2 D3=> P2 –P3 D4=> P3 –P4. 为了达到在冬季结束时的生产水平回到 40 个单位的目的，我们引进了变量 U5和 D5， 以测定最后一个时期结束时生产量的变化水平。U5 和 D5 应该满足下面的约束： U5=> 40 – P4 D5=> P4 - 40 在运行模型之前，我们可以将上面关于产量变化约束由 10 个减少到 5 个。我们观察 下面两个约束： U2=> P2 – P1 D2=> P1 - P2 可以用下面一个约束取代： U2 - D2 = P2 - P1 这样做非常经济。上面公式的目的就是迫使：当 P2 - P1 => 0 时，U2 = P2 - P1；当 P1 - P2 => 0 时，D2 = P1 - P2。从经济的角度来看，在最优解答中，D2 和 P2 最多只有一个大于 0。 这是因为如果它们两个都大于 0，则可以同时减去一个常数，使得变量既满足约束，又使 目标成本有所下降。 下面就是完整的模型： MODEL: !Minimize 存储 + 生产水平变动成本; MIN = 700 * I1 + 700 * I2 + 700 * I3 + 700 * I4 + 600 * U1 + 600 * U2 + 600 * U3 + 600 * U4 + 600 * D1 + 600 * D2 + 600 * D3 + 600 * D4 + 600 * U5 + 600 * D5; !生产及存储的初始条件; [CNDBI] I0 = 0; [CNDBP] P0 = 40; !初始存储+生产=需求+期末存储; [INV1] I0 + P1 = 20 + I1; [INV2] I1 + P2 = 30 + I2; [INV3] I2 + P3 = 50 + I3; [INV4] I3 + P4 = 60 + I4; !上变化量-下变化量 = 这一时期的产量- 前一时期的产量; [CHG1] U1 - D1 = P1 - P0; [CHG2] U2 - D2 = P2 - P1; [CHG3] U3 - D3 = P3 - P2; [CHG4] U4 - D4 = P4 - P3; [CHG5] U5 - D5 = P5 - P4; !结束条件; [CNDEI] I4 = 0;

5 [CNDEP]P5 40; END 解答是： Global optimal solution found at step: 15 Objective value: 43000.00 Variable Value Reduced Cost I1 5.000000 0.0000000 I2 0.0000000 200.0000 I3 5.000000 0.0000000 I4 0.0000000 0.0000000 01 0.0000000 1200.000 U2 0.0000000 250.0000 U3 30.00000 0.0000000 04 0.0000000 250.0000 D1 15.00000 0.0000000 D2 0.0000000 950.0000 D3 0.0000000 1200.000 D4 0.0000000 950.0000 05 0.0000000 1200.000 D5 15.00000 0.0000000 I0 0.0000000 0.0000000 PO 40.00000 0.0000000 P1 25.00000 0.0000000 P2 25.00000 0.0000000 P3 55.00000 0.0000000 P4 55.00000 0.0000000 P5 40.00000 0.0000000 Row slack or Surplus Dual Price 1 43000.00 -1.000000 CNDBI 0.0000000 -950.0000 CNDBP 0.0000000 -600.0000 INV1 0.0000000 950.0000 INV2 0.0000000 250.0000 INV3 0.0000000 -250.0000 INV4 0.0000000 -950.0000 CHG1 0.0000000 600.0000 CHG2 0.0000000 -350.0000 CHG3 0.0000000 -600.0000 CHG4 0.0000000 -350.0000 CHG5 0.0000000 600.0000

5 [CNDEP] P5 = 40; END 解答是： Global optimal solution found at step: 15 Objective value: 43000.00 Variable Value Reduced Cost I1 5.000000 0.0000000 I2 0.0000000 200.0000 I3 5.000000 0.0000000 I4 0.0000000 0.0000000 U1 0.0000000 1200.000 U2 0.0000000 250.0000 U3 30.00000 0.0000000 U4 0.0000000 250.0000 D1 15.00000 0.0000000 D2 0.0000000 950.0000 D3 0.0000000 1200.000 D4 0.0000000 950.0000 U5 0.0000000 1200.000 D5 15.00000 0.0000000 I0 0.0000000 0.0000000 P0 40.00000 0.0000000 P1 25.00000 0.0000000 P2 25.00000 0.0000000 P3 55.00000 0.0000000 P4 55.00000 0.0000000 P5 40.00000 0.0000000 Row Slack or Surplus Dual Price 1 43000.00 -1.000000 CNDBI 0.0000000 -950.0000 CNDBP 0.0000000 -600.0000 INV1 0.0000000 950.0000 INV2 0.0000000 250.0000 INV3 0.0000000 -250.0000 INV4 0.0000000 -950.0000 CHG1 0.0000000 600.0000 CHG2 0.0000000 -350.0000 CHG3 0.0000000 -600.0000 CHG4 0.0000000 -350.0000 CHG5 0.0000000 600.0000