《运筹学》课程教学资源（参考资料）3 网络计划模型

3网络计划模型 3.1引言 我们要关注网络模型主要是基于下面三个理由： 1)网络模型描述起来比较简单，而且借助于图形很容易理解： 2)在一些特殊条件下，网络模型会自然的给出整数解答： 3)与一般的LP相比较，求解网络模型往往更加容易。 最常见的网络模型就是管道运输线路网络和电力传输线路网络。任何一个企业，只要 他在不同的生产产品，并将产品销往不同的销地，利用网络LP设计出货策略是一个明智的 选择。 工厂 中间商 客户 -3 5 A 2 3-5 6 3 1 3 -4 B 2 图3-1三级分配网络 图3-1描述了一个公司如何利用中间商分派产品。公司有两个工厂，分别用A和B表示： 三个中间商分别用X、Y和Z表示：四个各户分别用1,2,3,4表示。每一个节点旁边的数字 表示产品的数量。例如，对于工厂A来说，有9个单位的运送能力。另一方面，对于客户3 来说，有-4个单位，它意味着需要接收4个单位的产品。每条边上的数字表示该线路运送单 位产品的成本。例如，工厂A运送5个单位的产品到中间商Y,则相应的成本为5×2=10。 问题是如何安排运输满足客户需求使得运输总成本达到最少。 一个网络问题LP的基本条件是它可以用一个网络来进行描述。它们也许有3级以上的 节点，两个节点之间线路上的运输量也可以由最大量和最小量的限制。 我们用最简明的方式定义变量，这个问题的LP模型如下： MODEL: MIN AX 2 AY 3 BX BY 2 BZ 5 X1 7 X2 9 Y1

1 3 网络计划模型 3.1 引言 我们要关注网络模型主要是基于下面三个理由： 1) 网络模型描述起来比较简单，而且借助于图形很容易理解； 2) 在一些特殊条件下，网络模型会自然的给出整数解答； 3) 与一般的LP相比较，求解网络模型往往更加容易。 最常见的网络模型就是管道运输线路网络和电力传输线路网络。任何一个企业，只要 他在不同的生产产品，并将产品销往不同的销地，利用网络LP设计出货策略是一个明智的 选择。 工厂 中间商 客户 图3-1 三级分配网络 图3-1描述了一个公司如何利用中间商分派产品。公司有两个工厂，分别用A和B表示； 三个中间商分别用X、Y和Z表示； 四个各户分别用1, 2, 3, 4表示。每一个节点旁边的数字 表示产品的数量。例如，对于工厂A来说，有9个单位的运送能力。另一方面，对于客户3 来说，有-4个单位，它意味着需要接收4个单位的产品。每条边上的数字表示该线路运送单 位产品的成本。例如，工厂A运送5个单位的产品到中间商Y，则相应的成本为5×2 = 10。 问题是如何安排运输满足客户需求使得运输总成本达到最少。 一个网络问题LP的基本条件是它可以用一个网络来进行描述。它们也许有3级以上的 节点，两个节点之间线路上的运输量也可以由最大量和最小量的限制。 我们用最简明的方式定义变量，这个问题的LP模型如下： MODEL: MIN = AX + 2 * AY + 3 * BX + BY + 2 * BZ + 5 * X1 + 7 * X2 + 9 * Y1

2 +6*Y2+7*Y3+8*Z2+7*Z3+4*Z4: AX AY 9; BX BY BZ 8; -AX-BX+X1+X2=0: -AY-BY+Y1+Y2+Y3=0; -BZ+Z2+Z3+Z4=0; -X1-Y1=-3: -X2-Y2-z2=-5: -Y3-Z3=-4; -Z4=-5; END 对于每一个节点来说，都有一个约束：“来源量=使用量”。例如，约束5是限制中间 商Y的，表明运出产品数量减去运入产品数量的结果为零。 下面列出了上面LP模型的系数矩阵，可以从另一个角度看出网络问题的结构。 AA BB BX XY YY Z ZZ X Y Z12 123 23 4 1: 1 2 2 2 57 9 67 87 4 MIN 2: 1 =9 3 1 =8 4: -1 -1 = 5 6 11 1 7 =-3 8: =5 9 =-4 10: -1=5 你也许注意到了一个网络问题约束矩阵的一个非常重要的特性。如果不靠个别变量的 界限约束，约束矩阵的每一列只有两个非零数，一个是+1，另一个是-1。下面给出这个问 题的解答： Optimal solution found at step: 1 Objective value: 121.0000 Variable Value Reduced Cost AX 3.000000 0.000000 AY 6.000000 0.000000 BX 0.000000 3.000000 BY 3.000000 0.000000 BZ 5.000000 0.000000 X1 3.000000 0.000000 X2 0.000000 0.000000 Y1 0.000000 5.000000

2 + 6 * Y2 + 7 * Y3 + 8 * Z2 + 7 * Z3 + 4 * Z4; AX + AY = 9; BX + BY + BZ = 8; - AX - BX + X1 + X2 = 0; - AY - BY + Y1 + Y2 + Y3 = 0; - BZ + Z2 + Z3 + Z4 = 0; - X1 - Y1 = -3; - X2 - Y2 - Z2 = -5; - Y3 - Z3 = -4; - Z4 = -5; END 对于每一个节点来说，都有一个约束：“来源量=使用量”。例如，约束 5 是限制中间 商 Y 的，表明运出产品数量减去运入产品数量的结果为零。 下面列出了上面 LP 模型的系数矩阵，可以从另一个角度看出网络问题的结构。 A X A Y B X B Y B Z X 1 X 2 Y 1 Y 2 Y 3 Z 2 Z 3 Z 4 1: 1 2 3 1 2 5 7 9 6 7 8 7 4 MIN 2: 1 1 = 9 3: 1 1 1 = 8 4: -1 -1 1 1 = 5: -1 -1 1 1 1 = 6: -1 1 1 1 = 7: -1 -1 = -3 8: -1 -1 -1 = -5 9: -1 -1 = -4 10: - 1 = -5 你也许注意到了一个网络问题约束矩阵的一个非常重要的特性。如果不靠个别变量的 界限约束，约束矩阵的每一列只有两个非零数，一个是+1，另一个是-1。下面给出这个问 题的解答： Optimal solution found at step: 1 Objective value: 121.0000 Variable Value Reduced Cost AX 3.000000 0.000000 AY 6.000000 0.000000 BX 0.000000 3.000000 BY 3.000000 0.000000 BZ 5.000000 0.000000 X1 3.000000 0.000000 X2 0.000000 0.000000 Y1 0.000000 5.000000

3 Y2 5.000000 0.000000 Y3 4.000000 0.000000 z2 0.000000 3.000000 z3 0.000000 1.000000 Z4 5.000000 0.000000 这个解答揭示了求解网络问题的两个特点是：： 1)如果约束右边的系数（生产能力或需求）是整数，那末变量也是整数。 2)如果目标函数系数是整数，那末对偶价格也是整数。 下面我们对网络LP做一个总结： ●与每一个节点对应的数字是节点的能力（负数表示需求）。 ●与每一条边对应的是： a)运送单位产品的成本（也可以是负数）： b)运送产品的最低数量（通常是0）： C)运送产品的最高数量（本例中是无穷大）。 我们的问题是在满足供应、需求和流量限制的条件下如何安排运输才能使得总成本最 小。 3.2典型案例 有一些普通的LP模型就是标准的网络LP案例。它们分别是： 1)运输问题。它是一个2级网络问题。所有的1级节点都是供应商。所有的2级 节点都是用户。供应商和用户之间只有一条线路。 2)最短路和最长路问题。假设已知美国的道路网络。人们希望能够找到从Bangor到 San Diego的最短距离。这个问题等价于从Bangor运送单位产品到San Diego的运输问题， 线路的运输成本就是线路的长度。关于最短路问题有简单而快速的计算程序。最短路问题 的姐妹问题就是在PERT或CPM分析中出现的最长路问题。 3)指派问题。如果一个运输问题中供应商的数量与用户的数量一样，每一个供应商 只提供一个产品而每一个用户只接受一个产品，这个运输问题就是指派问题。对于这个 问题己经出现高效率的计算程序。 4)最大流问题。给定一个有向网络，对于每一条线路有一个运输量的上限限制。人 们想知道从一个特定的出发点到一个特定的目的地的最大运输量是多少。这个问题可以用 于建筑运输和军事调动案例中。 在一个大型项目的管理过程中，计划评估法(PERT和关键线路法(CPM①是两个相关的 监控技术。PERT/CPM的关键是计算关键线路，就是确定一些必须按时完成的活动以保证 整个项目按期完成。 我们将通过例子来说明：关键线路的计算是一个很简单的网络LP问题。再具体一点 说关键线路就是一个最长的线路。 在下面的表格中，我们列出了建设一栋房子的主要作业。一项作业只有在他的所有 紧前作业完成之后才可以进行

3 Y2 5.000000 0.000000 Y3 4.000000 0.000000 Z2 0.000000 3.000000 Z3 0.000000 1.000000 Z4 5.000000 0.000000 这个解答揭示了求解网络问题的两个特点是：: 1）如果约束右边的系数（生产能力或需求）是整数，那末变量也是整数。 2）如果目标函数系数是整数，那末对偶价格也是整数。 下面我们对网络 LP 做一个总结： ⚫ 与每一个节点对应的数字是节点的能力（负数表示需求）。 ⚫ 与每一条边对应的是： a) 运送单位产品的成本（也可以是负数）； b) 运送产品的最低数量（通常是 0）； c) 运送产品的最高数量（本例中是无穷大）。 我们的问题是在满足供应、需求和流量限制的条件下如何安排运输才能使得总成本最 小。 3.2 典型案例 有一些普通的 LP 模型就是标准的网络 LP 案例。 它们分别是： 1） 运输问题。它是一个 2 级网络问题。所有的 1 级节点都是供应商。 所有的 2 级 节点都是用户。供应商和用户之间只有一条线路。 2） 最短路和最长路问题。假设已知美国的道路网络。人们希望能够找到从 Bangor 到 San Diego 的最短距离。这个问题等价于从 Bangor 运送单位产品到 San Diego 的运输问题， 线路的运输成本就是线路的长度。关于最短路问题有简单而快速的计算程序。最短路问题 的姐妹问题就是在 PERT 或 CPM 分析中出现的最长路问题。 3） 指派问题。如果一个运输问题中供应商的数量与用户的数量一样，每一个供应商 只提供一个产品而每一个用户只接受一个产品， 这个运输问题就是指派问题。对于这个 问题已经出现高效率的计算程序。 4） 最大流问题。给定一个有向网络，对于每一条线路有一个运输量的上限限制。人 们想知道从一个特定的出发点到一个特定的目的地的最大运输量是多少。这个问题可以用 于建筑运输和军事调动案例中。 在一个大型项目的管理过程中，计划评估法(PERT)和关键线路法(CPM)是两个相关的 监控技术。PERT/CPM 的关键是计算关键线路，就是确定一些必须按时完成的活动以保证 整个项目按期完成。 我们将通过例子来说明: 关键线路的计算是一个很简单的网络 LP 问题。再具体一点 说关键线路就是一个最长的线路。 在下面的表格中，我们列出了建设一栋房子的主要作业。 一项作业只有在他的所有 紧前作业完成之后才可以进行

4 作业 记号 作业时间 紧前作业 挖地基 DIG 浇灌基础 FOUND 4 DIG 浇灌地面 POURB 2 FOUND 安装拖梁 JOISTS 3 FOUND 安装围墙 WALLS 5 FOUND 安装椽子 RAFTERS 3 WALLS,POURB 安装地板 FLOOR 4 JOISTS 内部初装修 ROUGH 6 FLOOR 安装屋顶 ROOF 7 RAFTERS 内部精装修 FINISH 5 ROUGH.ROOF 美化环境 SCAPE 2 POURB,WALLS 在图3-1中，我们将说明这个项目的PET网络（箭线式网络）。我们将通过计算最少 的占用时间来完成这项工作。对于图3-1，我们对从左到右最长线路的长度感兴趣。如果 这个线路上的作业不能按时完成，那末这个项目就不能按时完成。经检验，关键线路由DIG, FOUND,WALLS,RAFTERS,ROOF和FINISH组成，长度为27。 虽然这个例子可以不用计算机来完成，但是我们还是来学习如何用公式来描述这个问 题，从而来用LP模型来求解。 Rough Floor 6 4 H Roof Joists 7 Finish 3 5 G Dig B Found Pour B 3 4 Rafters 2 3 Scape 5 2 Walls 图3-1建设一栋房子的网络图 首先定义变量DIG只取0或1用来表示作业DIG是否在关键线路上。对于其他的变 量也类似。等于1的变量就构成了关键线路。相应的目标函数就在PERT图中找出最长的 线路。 目标函数是： MAX 3 DIG +4 FOUND 2 POURB 3 JOISTS 5 WALLS 3 RAFTERS +4 FLOOR +6 ROUGH +7 ROOF 5 FINISH +2 SCAPE; 单就目标函数本身来说似乎有问题。我们并不是要求出项目的最大长度。当然，如果 我们适当地增加约束，我们将会看到这个目标函数就是求出了这个PET网络的最长线路。 增加的线路如下： 1)作业DG一定在关键线路上：

4 作业 记号 作业时间 紧前作业 挖地基 DIG 3 — 浇灌基础 FOUND 4 DIG 浇灌地面 POURB 2 FOUND 安装拖梁 JOISTS 3 FOUND 安装围墙 WALLS 5 FOUND 安装椽子 RAFTERS 3 WALLS, POURB 安装地板 FLOOR 4 JOISTS 内部初装修 ROUGH 6 FLOOR 安装屋顶 ROOF 7 RAFTERS 内部精装修 FINISH 5 ROUGH, ROOF 美化环境 SCAPE 2 POURB, WALLS 在图 3-1 中，我们将说明这个项目的 PERT 网络(箭线式网络) 。我们将通过计算最少 的占用时间来完成这项工作。对于图 3-1，我们对从左到右最长线路的长度感兴趣。如果 这个线路上的作业不能按时完成，那末这个项目就不能按时完成。经检验，关键线路由 DIG, FOUND, WALLS, RAFTERS, ROOF 和 FINISH 组成，长度为 27。 虽然这个例子可以不用计算机来完成，但是我们还是来学习如何用公式来描述这个问 题，从而来用 LP 模型来求解。 图 3-1 建设一栋房子的网络图 首先定义变量 DIG 只取 0 或 1 用来表示作业 DIG 是否在关键线路上。对于其他的变 量也类似。等于 1 的变量就构成了关键线路。相应的目标函数就在 PERT 图中找出最长的 线路。 目标函数是： MAX = 3 * DIG + 4 * FOUND + 2 * POURB + 3 * JOISTS + 5 * WALLS + 3 * RAFTERS + 4 * FLOOR + 6 * ROUGH + 7 * ROOF + 5 * FINISH + 2 * SCAPE; 单就目标函数本身来说似乎有问题。我们并不是要求出项目的最大长度。当然，如果 我们适当地增加约束，我们将会看到这个目标函数就是求出了这个 PERT 网络的最长线路。 增加的线路如下： 1) 作业 DIG 一定在关键线路上；

2)一个作业只有在它的紧前作业在关键线路上时它才可以在关键线路上。进一步说， 如果一个作业有紧后作业，只有在它的紧后作也在关键线路上时它才可以在关键线路上。 3)作业SCAPE或FINISH必定有一个在关键线路上。 通过加入下面的约束就可以实现上面的要求： -DIG=-1: FOUND DIG 0 JOISTS -POURB WALLS FOUND =0; FLOOR JOISTS =0; RAFTERS SCAPE POURB WALLS =0; ROUGH FLOOR 0; ROOF RAFTERS 0; FINISH ROUGH ROOF 0; FINISH SCAPE +1; 这个问题的解答如下： Optimal solution found at step: 2 Objective value: 27.00000 Variable Value Reduced Cost DIG 1.000000 0.000000 FOUND 1.000000 0.000000 POURB 0.000000 3.000000 JOISTS 0.000000 0.000000 WALLS 1.000000 0.000000 RAFTERS 1.000000 0.000000 FLOOR 0.000000 0.000000 ROUGH 0.000000 2.000000 ROOF 1.000000 0.000000 FINISH 1.000000 0.000000 SCAPE 0.000000 13.00000 注意关键线路上作业对应变量的值都是1。如果第一个约束“DIG=-1”被删除，结 果会如何？ 看看下面这个问题的系数结构也很有好处： R W F 0 0 G D D R H E 1: 6 2 MAX

5 2) 一个作业只有在它的紧前作业在关键线路上时它才可以在关键线路上。进一步说， 如果一个作业有紧后作业，只有在它的紧后作也在关键线路上时它才可以在关键线路上。. 3) 作业 SCAPE 或 FINISH 必定有一个在关键线路上。 通过加入下面的约束就可以实现上面的要求： - DIG = -1; - FOUND + DIG = 0; - JOISTS - POURB - WALLS + FOUND = 0; - FLOOR + JOISTS = 0; - RAFTERS - SCAPE + POURB + WALLS = 0; - ROUGH + FLOOR = 0; - ROOF + RAFTERS = 0; - FINISH + ROUGH + ROOF = 0; + FINISH + SCAPE = +1; 这个问题的解答如下： Optimal solution found at step: 2 Objective value: 27.00000 Variable Value Reduced Cost DIG 1.000000 0.000000 FOUND 1.000000 0.000000 POURB 0.000000 3.000000 JOISTS 0.000000 0.000000 WALLS 1.000000 0.000000 RAFTERS 1.000000 0.000000 FLOOR 0.000000 0.000000 ROUGH 0.000000 2.000000 ROOF 1.000000 0.000000 FINISH 1.000000 0.000000 SCAPE 0.000000 13.00000 注意关键线路上作业对应变量的值都是 1。如果第一个约束“-DIG = - 1”被删除，结 果会如何？ 看看下面这个问题的系数结构也很有好处： D I G F O U N D P O U N D J O I S T S W A L L S R A F T E R S F L O O R R O U G H R O O F F N I S H S C A P E 1: 3 4 2 3 5 3 4 6 7 5 2 MAX

6 =-l 3: 1 -1 -1 1 -1 7: 1 -1 8: 1 -1 9 -1 10: 1 注意：约束中每一个变量最多有两个非零悉数。如果有两个，它们是+1和-1。这 个一个网络LP最大的特点 现在让我们来研究另外一个解法。此解法是使得项目的占用时间达到最小。为了做到 这一点，在PET网络图中定义一个节点表示一个作业。例如，A表示挖地基，C表示 浇灌基础，I表示完成美化环境和内部精装修。 定义变量A,B,C,H,I表是相应作业的开始时间。我们的目标函数是： MIN I-A; 任何一个作业的开始时间只有在它的紧前作业完成之后才能开始。因此，作业开始 时间与他的紧前作业开始时间之差一定大于等于紧前作业的完成时间。这样就得到下面的 约束： B-A>= 3: ！DIG; C-B>= 4; ！FOUND;: E-C>= 2; D-C>= 3; E-C>= 5: E-D>= 4 G-E>= 3 H-E>= 6; H-G>= 7; I-H>= 5; I-E>= 2: 这个问题的解答是： Global optimal solution found at step: 2 Objective value: 27.00000 Variable Value Reduced Cost 27.00000 0.0000000 A 0.0000000 0.0000000 B 3.000000 0.0000000 e 7.000000 0.0000000

6 2: -1 = -1 3: 1 -1 = 4: 1 -1 -1 -1 = 5: 1 -1 = 6: 1 1 -1 -1 = 7: 1 -1 = 8: 1 -1 = 9: 1 1 1 1 -1 = 10: 1 1 1 1 = 1 注意：约束中每一个变量最多有两个非零悉数。如果有两个，它们是 +1 和 –1。这 个一个网络 LP 最大的特点 现在让我们来研究另外一个解法。此解法是使得项目的占用时间达到最小。为了做到 这一点，在 PERT 网络图中定义一个节点表示一个作业。例如， A 表示挖地基， C 表示 浇灌基础，I 表示完成美化环境和内部精装修。 定义变量 A, B, C, ., H, I 表是相应作业的开始时间。我们的目标函数是: MIN I - A; 任何一个作业的开始时间只有在它的紧前作业完成之后才能开始。因此， 作业开始 时间与他的紧前作业开始时间之差一定大于等于紧前作业的完成时间。这样就得到下面的 约束： B - A >= 3; ! DIG; C - B >= 4; ! FOUND; E - C >= 2; D - C >= 3; E - C >= 5; F - D >= 4; G - E >= 3; H - F >= 6; H - G >= 7; I - H >= 5; I - E >= 2; 这个问题的解答是： Global optimal solution found at step: 2 Objective value: 27.00000 Variable Value Reduced Cost I 27.00000 0.0000000 A 0.0000000 0.0000000 B 3.000000 0.0000000 C 7.000000 0.0000000

7 E 12.00000 0.0000000 0 12.00000 0.0000000 小 16.00000 0.0000000 G 15.00000 0.0000000 g 22.00000 0.0000000 注意：目标函数值等于关键线路的长度。我们可以借助具有非零对偶价格的约束间接 地确定关键作业。这些约束对应的作业就构成了关键线路。约束右边的数字是作业完成时 间。如果我们增加了关键线路上作业的完成时间，整个项目的完成时间就会延长，因此， 就会有一个非零的对偶价格。如果第一个变量被删除了，结果又会如何？ 下面是这个问题系数结构列表： H 1: -1 1 MIN 2: -1 1 >3 3: -1 1 >4 4: -1 >2 5: >3 6: >5 7: >4 8: -1 >3 9: -1 1 >6 10: 1 >7 11: -1 1>5 12: -1 1>2 注意：这个结构图完全是由前面结构图转动90度而产生。虽然这两个方法从表面看 毫不相干，然而实际上有着很密切的关系，这种关系数学家称之为对偶关系。 3.3案例及参考解答 3-1.Slick石油公司正在进行下个月的管线运输决策。洛杉矶需要200,000桶石油，可以 分别从怀俄明州的休斯敦或卡斯帕得到。从休斯敦到洛杉矶每桶石油的运输成本是$0.25： 而从卡斯帕到洛杉矶每桶石油的运输成本是$0.28。圣路易也需要120,000桶石油，如从休 斯敦供应则每桶运输成本是$018：如从卡斯帕供应则每桶运输成本是$0.22。印第安纳州 的Freshair也需要230,000桶石油，如从卡斯帕供应则每桶石油的运输成本是$0.21，如从休 斯敦供应则每桶石油的运输成本是$0.17。卡斯帕的石油供应总量是250,000桶，休斯敦的 石油供应总量是350,000桶。由于管线运输能力有限，下个月从卡斯帕到洛杉矶的最大运量 为180,000桶，从休斯敦到洛杉矶的最大运量为150,000桶。下个月，新泽西州的纽华克也 需要190,000桶石油，它仅仅可以从图蒂斯维尔得到供应，每桶的运输成本是$0.14。下个 月，亚特兰大也需要150.000桶石油，它既可以从图蒂斯维尔得到供应，每桶的运输成本是

7 E 12.00000 0.0000000 D 12.00000 0.0000000 F 16.00000 0.0000000 G 15.00000 0.0000000 H 22.00000 0.0000000 注意：目标函数值等于关键线路的长度。我们可以借助具有非零对偶价格的约束间接 地确定关键作业。这些约束对应的作业就构成了关键线路。约束右边的数字是作业完成时 间。如果我们增加了关键线路上作业的完成时间，整个项目的完成时间就会延长，因此， 就会有一个非零的对偶价格。 如果第一个变量被删除了，结果又会如何？ 下面是这个问题系数结构列表： A B C D E F G H I 1: -1 1 MIN 2: -1 1 > 3 3: -1 1 > 4 4: -1 1 > 2 5: -1 1 > 3 6: -1 1 > 5 7: -1 1 > 4 8: -1 1 > 3 9: -1 1 > 6 10: -1 1 > 7 11: -1 1 > 5 12: -1 1 > 2 注意：这个结构图完全是由前面结构图转动 90 度而产生。虽然这两个方法从表面看 毫不相干， 然而实际上有着很密切的关系，这种关系数学家称之为对偶关系。 3.3 案例及参考解答 3-1. Slick石油公司正在进行下个月的管线运输决策。洛杉矶需要200,000桶石油，可以 分别从怀俄明州的休斯敦或卡斯帕得到。从休斯敦到洛杉矶每桶石油的运输成本是$0.25； 而从卡斯帕到洛杉矶每桶石油的运输成本是$0.28。圣路易也需要120,000桶石油，如从休 斯敦供应则每桶运输成本是$0.18；如从卡斯帕供应则每桶运输成本是$0.22。印第安纳州 的Freshair也需要230,000桶石油，如从卡斯帕供应则每桶石油的运输成本是$0.21，如从休 斯敦供应则每桶石油的运输成本是$0.17。卡斯帕的石油供应总量是250,000桶，休斯敦的 石油供应总量是350,000桶。由于管线运输能力有限，下个月从卡斯帕到洛杉矶的最大运量 为180,000桶，从休斯敦到洛杉矶的最大运量为150,000桶。下个月，新泽西州的纽华克也 需要190,000桶石油，它仅仅可以从图蒂斯维尔得到供应，每桶的运输成本是$0.14。下个 月，亚特兰大也需要150,000桶石油，它既可以从图蒂斯维尔得到供应，每桶的运输成本是

$0.16,也可以从休斯敦得到供应，每桶的运输成本是$0.20。图蒂斯维尔的石油供应总量 是300,000桶。 建立这个问题的线性规划模型，使得总运输成本达到最小，并求出相应运输计划。 参考解答： Model: sets: a/1.3/:g: b/1.5/:x ab (a,b):p,m,y; endsets data: =@o1e('最优化案例3-1.x1s','X'): g=@o1e('最优化案例3-1.x1s','G'): p=@o1e('最优化案例3-1.x1s','P'): m=@o1e('最优化案例3-1.xls','M'); @o1e('最优化案例3-1.x1s','Y)=y: enddata @for(ab:yx(i) ) @for(a(i): @sum(b (j):y(i,j))<g(i) ) End 解答： 总费用$170,700 运输计划 洛杉衫颓 圣路易 Fresaair 纽华克 亚特兰大 供应量 休斯顿 20.000 120.000 170.000 0 40.000 350,000 卡斯帕 180,000 0 60,.300 0 0 250,000 图蒂斯尔维 0 0 0 190,000 110.000 300,000 需求量 20,000 120,000 230,000 190,000 150,000 3-2.路易斯是Boulangerie餐馆的老板。由于预订宴会的需要，在星期四、星期五和 星期六分别需要40块、70块和60块桌布。可以用租用的方式得到桌布，一块桌布租用三天 的价格是$2。每块桌布重新使用之前一定要清洗。头天晚上清洗一块桌布的价格是$1.50。 隔天干洗一块桌布的价格是（例如，星期四用完以后星期六还可以再用）$0.80。目前手头上 或在洗衣店里有20块干净的桌布。租用的桌布返还是不需要清洗。 a)决策变量是什么？ b)建立相应的LP模型使得桌布的租用和清洗总成本达到最小。对于每一天来说，干 净的桌布数量一定要大于等于当天的需求。对于头两天中的任何一天来说，被送到洗衣店

8 $0.16，也可以从休斯敦得到供应，每桶的运输成本是$0.20。图蒂斯维尔的石油供应总量 是300,000桶。 建立这个问题的线性规划模型，使得总运输成本达到最小，并求出相应运输计划。 参考解答： Model: sets: a/1.3/:g; b/1.5/:x; ab(a,b):p,m,y; endsets data: x=@ole('最优化案例3-1.xls','X'); g=@ole('最优化案例3-1.xls','G'); p=@ole('最优化案例3-1.xls','P'); m=@ole('最优化案例3-1.xls','M'); @ole('最优化案例3-1.xls','Y')=y; enddata @for(ab:yx(i) ); @for(a(i): @sum(b(j):y(i,j))<g(i) ); End 解答： 3-2. 路易斯是Boulangerie餐馆的老板。由于预订宴会的需要，在星期四、星期五和 星期六分别需要40块、70块和60块桌布。可以用租用的方式得到桌布，一块桌布租用三天 的价格是$2。每块桌布重新使用之前一定要清洗。头天晚上清洗一块桌布的价格是$1.50。 隔天干洗一块桌布的价格是(例如，星期四用完以后星期六还可以再用)$0.80。目前手头上 或在洗衣店里有20块干净的桌布。租用的桌布返还是不需要清洗。 a) 决策变量是什么? b) 建立相应的LP模型使得桌布的租用和清洗总成本达到最小。对于每一天来说，干 净的桌布数量一定要大于等于当天的需求。对于头两天中的任何一天来说，被送到洗衣店

9 桌布的数量不能超过脏桌布的数量。它是一个网络LP? 参考解答： Model: sets: a/1.3/:x,y,z,xuqiu,wi b/1.1/:xp,yp,zp,ck; endsets data: xuqiu=@o1e('最优化案例3-2.xls','uqiu'): p=@o1e('最优化案例3-2.x1s','p'): yp=@o1e('最优化案例3-2.xls','yp'): zp=@o1e('最优化案例3-2.x1s','zp'): ck=o1e('最优化案例3-2.x1s','ck'): @o1e(最优化案例3-2.x1s','x')=x; @ole('最优化案例3-2.x1s','y')=y: @o1e('最优化案例3-2.x1s','z')=z; enddata min=@sum(a:x)*xp(1)+@sum(a:y)*yp (1)+@sum(a:z)*zp(1); ck(1)+x(1)>xuqiu(1): ck(1)+×(1)+×(2)+y(1)>xuqiu(1)+xuqiu(2): ck(1)+x(1)+x(2)+×(3)+y(1)+y(2)+z(1)>xuqiu(1)+ug1u(2)+ugiu(3): @for(a:y+z<xuqiu); End 解答： 星期四 星期五 星期六 价格 租用毛巾数量 90 0 0 2 快洗毛巾数量 0 20 0 1.5 常洗毛巾数量 40 0 0 0.8 可用毛巾数量 110 70 60 毛巾需求量 40 70 60 总费用 ￥242.00 3-3.Millersburg供应公司使用的大批卡车都是从制造厂商那里租用的。在接下来的8个 月里，公司对卡车的需求预测如下： 月份 Jan Feb Mar Apr May Jun Jul Aug 需求的车辆 430 410440390425450465470 公司所需卡车可以从不同的厂商以不同的价格租用不等的时间。最好的租用方法是： 三个月期限，$1,700：四个月期限，$2,000：五个月期限，$2,600。租用卡车的计算时间都 是某个月的1号开始。1月1号公司己经租用了200辆卡车，这些卡车在二月底到期

9 桌布的数量不能超过脏桌布的数量。它是一个网络LP? 参考解答： Model: sets: a/1.3/:x,y,z,xuqiu,w; b/1.1/:xp,yp,zp,ck; endsets data: xuqiu=@ole('最优化案例3-2.xls','xuqiu'); xp=@ole('最优化案例3-2.xls','xp'); yp=@ole('最优化案例3-2.xls','yp'); zp=@ole('最优化案例3-2.xls','zp'); ck=@ole('最优化案例3-2.xls','ck'); @ole('最优化案例3-2.xls','x')=x; @ole('最优化案例3-2.xls','y')=y; @ole('最优化案例3-2.xls','z')=z; enddata min=@sum(a:x)*xp(1)+@sum(a:y)*yp(1)+@sum(a:z)*zp(1); ck(1)+x(1)>xuqiu(1); ck(1)+x(1)+x(2)+y(1)>xuqiu(1)+xuqiu(2); ck(1)+x(1)+x(2)+x(3)+y(1)+y(2)+z(1)>xuqiu(1)+xuqiu(2)+xuqiu(3); @for(a:y+z<xuqiu); End 解答： 3-3. Millersburg供应公司使用的大批卡车都是从制造厂商那里租用的。在接下来的8个 月里，公司对卡车的需求预测如下： 月份 Jan Feb Mar Apr May Jun Jul Aug 需求的车辆 430 410 440 390 425 450 465 470 公司所需卡车可以从不同的厂商以不同的价格租用不等的时间。最好的租用方法是： 三个月期限，$1,700；四个月期限，$2,000；五个月期限，$2,600。租用卡车的计算时间都 是某个月的1号开始。1月1号公司已经租用了200辆卡车，这些卡车在二月底到期

10 a)为了使得Millersburg供应公司在8个月的时间里卡车的租用成本达到最小，设计相 应的解决方法。 b)将这个问题表示成一个网络问题。 参考解答： Model: sets: a/1.8/:xuqiu,x,ku; b/1.3/:p,yue; ab(b,a):y;!y表示不同方式下租用车辆的数量； k/1.1/:f: endsets data: xuqiu=@ole('最优化案例3-3.xls','ugiu'): p=@o1e('最优化案例3-3.x1s','p'): ku=@ole('最优化案例3-3.x1s','ku'); yue=@ole('最优化案例3-3.xls','yue'): @o1e('最优化案例3-3.x1s','x')=x: @o1e('最优化案例3-3.x1s','f')=f: @ole('最优化案例3-3.xls','y')=y: enddata @for(a:x>xuqiu)i x (1)=ku(1)+@sum(b (j)@sum(a (i)li#le#1:y(j,i))); x(2)=ku(2)+@sum(b (j)@sum(a(i)li#le#2:y(j,i))); ×(3)=ku(3)+esum(b(j):esum(a()1i#1e#3:y(j,i))); x(4)=ku(4)+@sum(a(i)|i#1e#4#and#i#ge#2:y(1,i))+ @sum(a(i)li#le#4#and#i#ge#1:y(2,i))+@sum(a(i)li#le#4#and#i#ge#2: y(3,i)): x(5)=ku(5)+@sum(a(i)|i#1e#5#and#i#ge#3:y(1,i))+ @sum(a(i)li#le#5#and#i#ge#2:y(2,i))+@sum(a (i)li#le#4#and#i#ge#1: y(3,i)): x(6)=ku(6)+@sum (a (i)li#le#6#and#i#ge#4:y(1,i))+ @sum(a (i)li#le#6#and#i#ge#3:y(2,i))+@sum(a (i)li#le#6#and#i#ge#2: y(3,i)): x (7)=ku(7)+@sum(a(i)li#le#7#and#i#ge#5:y(1,i))+ @sum(a(i)li#le#7#and#i#ge#4:y(2,i))+@sum (a(i)li#le#7#and#i#ge#3: y(3,i)): x(8)=ku(8)+@sum(a(i)|i#1e#8#and#i#ge#6:y(1,i))+ @sum(a(i)li#le#8#and#i#ge#5:y(2,i))+@sum(a (i)li#le#8#and#i#ge#4: y(3,i)); @for(ab:@gin(y));

10 a) 为了使得Millersburg供应公司在8个月的时间里卡车的租用成本达到最小，设计相 应的解决方法。 b) 将这个问题表示成一个网络问题。 参考解答： Model: sets: a/1.8/:xuqiu,x,ku; b/1.3/:p,yue; ab(b,a):y;!y表示不同方式下租用车辆的数量; k/1.1/:f; endsets data: xuqiu=@ole('最优化案例3-3.xls','xuqiu'); p=@ole('最优化案例3-3.xls','p'); ku=@ole('最优化案例3-3.xls','ku'); yue=@ole('最优化案例3-3.xls','yue'); @ole('最优化案例3-3.xls','x')=x; @ole('最优化案例3-3.xls','f')=f; @ole('最优化案例3-3.xls','y')=y; enddata @for(a:x>xuqiu); x(1)=ku(1)+@sum(b(j):@sum(a(i)|i#le#1:y(j,i))); x(2)=ku(2)+@sum(b(j):@sum(a(i)|i#le#2:y(j,i))); x(3)=ku(3)+@sum(b(j):@sum(a(i)|i#le#3:y(j,i))); x(4)=ku(4)+@sum(a(i)|i#le#4#and#i#ge#2:y(1,i))+ @sum(a(i)|i#le#4#and#i#ge#1:y(2,i))+@sum(a(i)|i#le#4#and#i#ge#2: y(3,i)); x(5)=ku(5)+@sum(a(i)|i#le#5#and#i#ge#3:y(1,i))+ @sum(a(i)|i#le#5#and#i#ge#2:y(2,i))+@sum(a(i)|i#le#4#and#i#ge#1: y(3,i)); x(6)=ku(6)+@sum(a(i)|i#le#6#and#i#ge#4:y(1,i))+ @sum(a(i)|i#le#6#and#i#ge#3:y(2,i))+@sum(a(i)|i#le#6#and#i#ge#2: y(3,i)); x(7)=ku(7)+@sum(a(i)|i#le#7#and#i#ge#5:y(1,i))+ @sum(a(i)|i#le#7#and#i#ge#4:y(2,i))+@sum(a(i)|i#le#7#and#i#ge#3: y(3,i)); x(8)=ku(8)+@sum(a(i)|i#le#8#and#i#ge#6:y(1,i))+ @sum(a(i)|i#le#8#and#i#ge#5:y(2,i))+@sum(a(i)|i#le#8#and#i#ge#4: y(3,i)); @for(ab:@gin(y));