《运筹学》课程教学资源（参考资料）2 覆盖切割模型

2覆盖切割模型 2.1引言 覆盖切割问题常常会现在服务行业和工业生产中。其重要的特征是存在一组需求要满 足。我们可以使用多个作业，每个作业只能满足部分需求，任何一个作业都不能满足全部 需求。覆盖问题的基本模式为： 选择一组成本最小的作业满足：被选作业覆盖所有需求。 下表给出了一些不同类型的覆盖问题。 问题 番求 作业 职员安排 每天（每周）需要人员值班 轮班（每班满足部分时间） 邮件问题 要访问所有的顾客 各种线路（每条满足部分顾客） 切割原材料 提供各种尺寸的产品 切割方法（每种方法满足部分） 接下来我们将详细地讨论上面几个问题。 2.2职员配置问题 大多数的服务机构在管理中都会遇到职员配置问题。那就是要决定在轮班过程中人员 的数量。象电话公司、露天停车场、大医院和通常提供便民服务机构的人事部门都会遇到 这样的问题。 解决这个问题至少有三步：(1)做好每个时间段对人员需求的预测。(2)确定可能的轮班 方式，这种方式要在兼顾员工、劳动协议和规则的基础之上切实可行。一个特别的轮班方 式为：从星期二到星期六连续工作5天，然後休息二天。(3)在满足(1)所确定的需求基础 之上，决定每班安排多少人员，使得成本达到最小。所有三步都很困难。LP可以帮助我们 解决第三步。 埃迪在1954年首次发表了利用最优化解决职员配置问题的论文。他发明了一种方法为 纽约港的过路收费亭配置工作人员。他的讨论虽然有点过时，但是依然很有见地、很透彻。 他在他的论文摘要中提到：“在林肯隧道做了一个试验·。对每一个收费员都明确了值班 的时间和换班的时间，而且要求严格按时间表执行.。堵车的现象的确没有发生.。如果 不是收费亭的警察吸引你的注意力，你一定会注意到收费人员的变动和收费亭的开关。虽 然收费亭的数目有时略显过剩，但比以前好多了·。无庸置疑，达到了一个满意的结果。 2.3职员配置问题实例 芝加哥郊外有一个收费停车场，一天24小时对职员人数的需求如下：

1 2 覆盖切割模型 2.1 引言 覆盖切割问题常常会现在服务行业和工业生产中。其重要的特征是存在一组需求要满 足。我们可以使用多个作业，每个作业只能满足部分需求，任何一个作业都不能满足全部 需求。覆盖问题的基本模式为： 选择一组成本最小的作业满足：被选作业覆盖所有需求。 下表给出了一些不同类型的覆盖问题。 问题 需求 作业 职员安排 每天（每周）需要人员值班 轮班（每班满足部分时间） 邮件问题 要访问所有的顾客 各种线路（每条满足部分顾客） 切割原材料 提供各种尺寸的产品 切割方法（每种方法满足部分） 接下来我们将详细地讨论上面几个问题。 2.2 职员配置问题 大多数的服务机构在管理中都会遇到职员配置问题。那就是要决定在轮班过程中人员 的数量。象电话公司、露天停车场、大医院和通常提供便民服务机构的人事部门都会遇到 这样的问题。 解决这个问题至少有三步：(1)做好每个时间段对人员需求的预测。(2)确定可能的轮班 方式，这种方式要在兼顾员工、劳动协议和规则的基础之上切实可行。一个特别的轮班方 式为：从星期二到星期六连续工作5天，然後休息二天。(3)在满足（1）所确定的需求基础 之上，决定每班安排多少人员，使得成本达到最小。所有三步都很困难。LP可以帮助我们 解决第三步。 埃迪在1954年首次发表了利用最优化解决职员配置问题的论文。他发明了一种方法为 纽约港的过路收费亭配置工作人员。他的讨论虽然有点过时，但是依然很有见地、很透彻。 他在他的论文摘要中提到：“在林肯隧道做了一个试验.。对每一个收费员都明确了值班 的时间和换班的时间，而且要求严格按时间表执行.。堵车的现象的确没有发生.。如果 不是收费亭的警察吸引你的注意力，你一定会注意到收费人员的变动和收费亭的开关。虽 然收费亭的数目有时略显过剩，但比以前好多了.。无庸置疑，达到了一个满意的结果。 2.3 职员配置问题实例 芝加哥郊外有一个收费停车场，一天24小时对职员人数的需求如下：

2 时间 收费员人数 12 A.M.to 6A.M. 2 6A.M.to 10 A.M. 8 10A.M.to Noon 4 Noon to 4 P.M. 3 4 P.M.to6 P.M. 6 6 P.M.to 10 P.M J 10 PM.to 12 Midnight 3 每位收费员连续工作4个小时后休息一个小时，然後在工作四个小时。每位收费员可 以在任何时候上班。假设目标是使得雇佣的人员最少，那么每小时应该开始雇佣多少收费 员？ ·陈述和求解 定义决策变量： x=在午夜12点开始工作的人数， x2=在早上1点开始工作的人数， x24=在下午11点开始工作的人数。 一天里，每个小时都会有一个约束。那时开始工作的收费员人数必须满足需求。目标 是使得整个一天内所雇佣的人数最少。更具体一点： Minimize xI+x2:+x2+X24 subject to X+X24+X23+X22+x20+x19:+X18+X7>=2(12 midnight to1A.M.). X2+X1+X24+X23+X21+X20:+X19+XI8>=2(1A.M.to2A.M) x7+X6+X5+X4+X2+X1:+X24+X23>=8(6A.M.to7A.M) 44t.444 x24+X23+x22:+X21+x19+X18:+X17+X6>=3(11P.M.to12 midnight) 利用LINGO中的集合来陈述这个问题非常简洁。这里有两个集合：一天的24小时和9 个小时的轮换。注意：用函数@WRAP来调用变量X的索引。 MODEL: SETS:!24小时值班表，每班先上4个小时，休息1个小时，再上4个小时： HOURS/1.24/:X,NEED; SHIFT/1.9/:: ENDSETS DATA: NEED=22222288884433336655 5533: ENDDATA MIN @SUM(HOURS:X); @FOR(HOURS (I):

2 时间 收费员人数 12 A.M. to 6 A.M. 2 6 A.M. to 10 A.M. 8 10 A.M. to Noon 4 Noon to 4 P.M. 3 4 P.M. to 6 P.M. 6 6 P.M. to 10 P.M. 5 10 PM. to 12 Midnight 3 每位收费员连续工作4个小时后休息一个小时，然後在工作四个小时。每位收费员可 以在任何时候上班。假设目标是使得雇佣的人员最少，那么每小时应该开始雇佣多少收费 员？ ⚫ 陈述和求解 |定义决策变量: xl =在午夜12点开始工作的人数， x2 =在早上1点开始工作的人数， . x24 =在下午11点开始工作的人数。 一天里，每个小时都会有一个约束。那时开始工作的收费员人数必须满足需求。目标 是使得整个一天内所雇佣的人数最少。更具体一点： Minimize xl + x2: + x2 + . x24 subject to xl + x24 + x23 + x22 + x20 + x19: + x18 + xl7 >= 2 （12 midnight to 1 A.M.）. x2 + x1 + x24 + x23 + x21 + x20: + x19 + xl8 >=2 (1 A.M. to 2 A.M.) . x7 + x6 + x5 + x4 + x2 + x1: + x24 + x23 >= 8 (6 A.M. to 7 A.M.) . x24 + x23 + x22: + x21 + x19 + x18: + x17 + xl6 >= 3 (1 1 P.M. to 12 midnight) 利用LINGO中的集合来陈述这个问题非常简洁。这里有两个集合：一天的24小时和9 个小时的轮换。注意：用函数@WRAP来调用变量X的索引。 MODEL: SETS:! 24 小时值班表，每班先上4个小时，休息1个小时，再上4个小时; HOURS/1.24/: X, NEED; SHIFT/1.9/:; ENDSETS DATA: NEED = 2 2 2 2 2 2 8 8 8 8 4 4 3 3 3 3 6 6 5 5 5 5 3 3; ENDDATA MIN = @SUM( HOURS: X); @FOR( HOURS(I):

3 @SUM(SHIFT(J)IJ#NE#5:X(@WRAP((I-J+1),24)))>=NEED(I)); END 当我们求解后，得到目标值为15.75，变量的非零值如下： X2=5 x5=0.75 X11=1 X16=1 X3=0.75 X6=0.75 X14=1 X17=1 X4=0.75 X7=0.75 X15=2 X18=1 由于有变量取分数值，结果无效，增加下面的语句： @FOR(HOURS:@GIN(X)); 当我们再次求解时，得到目标值为16。下面是非零的变量值：， X=4 X5=1 X14=1 X17=2 X3=1 X6=1 X15=1 X18=1 X4=1 X7=1 X16=2 这类职员配置问题在电话呼叫中心常常会遇到。在信用卡服务中心也会遇到。在那里 的轮换方式也有所不同。8个小时中有两个15分钟的休息和半个小时的午餐时间。 2.4切割原料问题 在工业中，当生产开始的时候，大量的原材料都是原始尺码，例如纸，塑料和布匹。 这些原材料都必须切割成较各种小块，从而变成符合消费者要求，更加适用的尺寸。那么， 如何切割才能使得成本最低就是切割原料问题。下面是一个一维切割的例子。假设机器生 产的原材料的宽度是72英寸。那么就可以进行多种切割。下图就表示了两种不同的切割方 式： 图2-1切割方式例题 方式1有2英寸的浪费(72-2×35=2)，然而方式2只有1英寸浪费(72-2×18-35=1)。 当然，除非18英寸材料的需求正好是36英寸材料需求的两倍，否则方式2并不是很有用。 切割原材料问题的过程也是前面提及的三步。(1)预测所需材料的宽度。(2)尽可能多地 设计切割方式。(3)在满足需求的前提下，决定切割方式和切割的数量使得总成本最少。最 优化可以帮助我们解决第三步

3 @SUM(SHIFT(J) |J#NE#5:X(@WRAP((I-J+1) ,24) ) )>=NEED(I) ); END 当我们求解后，得到目标值为15.75，变量的非零值如下： x2 = 5 x5 = 0.75 x11 = 1 x16 = 1 x3 = 0.75 x6 = 0.75 x14 = 1 x17 = 1 x4 = 0.75 x7 = 0.75 x15 = 2 x18 = 1 由于有变量取分数值，结果无效，增加下面的语句： @FOR( HOURS: @GIN(X) ); 当我们再次求解时，得到目标值为16。下面是非零的变量值：. x2 = 4 x5 = 1 x14 = 1 x17 = 2 x3 = 1 x6 = 1 x15 = 1 x18 = 1 x4 = 1 x7 = 1 x16 = 2 这类职员配置问题在电话呼叫中心常常会遇到。|在信用卡服务中心也会遇到。在那里 的轮换方式也有所不同。8个小时中有两个15分钟的休息和半个小时的午餐时间。 2.4 切割原料问题 在工业中，当生产开始的时候|，大量的原材料都是原始尺码，例如纸，塑料和布匹。 这些原材料都必须切割成较各种小块，从而变成符合消费者要求，更加适用的尺寸。那么， 如何切割才能使得成本最低就是切割原料问题。下面是一个一维切割的例子。假设机器生 产的原材料的宽度是72英寸。那么就可以进行多种切割。下图就表示了两种不同的切割方 式： 图2-1 切割方式例题 方式1有2英寸的浪费(72- 2 × 35=2)，然而方式2只有1英寸浪费(72- 2 × 18- 35=1)。 当然，除非18英寸材料的需求正好是36英寸材料需求的两倍，否则方式2并不是很有用。 切割原材料问题的过程也是前面提及的三步。(1)预测所需材料的宽度。(2)尽可能多地 设计切割方式。(3)在满足需求的前提下，决定切割方式和切割的数量使得总成本最少。最 优化可以帮助我们解决第三步

许多大的纸业公司为解决切割原料问题都建立了以LP为基础的处理程序。现实中的切 割原料问题还会涉及到其他多种成本因素（除了边角料）。以LP为基础的处理程序的作用 取决于这些其他因素。下面的实例没有涉及到其它的成本因素，它说明了切割原料问题的 基本原理。 2.5切割原料问题实例 某器械公司生产电冰箱、火炉等一系列的家用电器。购买钢板的成本占材料费用的很 大一部分。通常，所购买的钢板是宽度为72英寸、48英寸和36英寸的卷钢。在生产过程中 需要8种不同宽度的钢板，宽度为：60,56,42,38,34,24,15和10英寸。所有钢板的 质量和厚度都是一样的。 接下来的就是废料问题。如果宽度为72英寸的钢板被切割成一个宽度为38英寸和两个 宽度为15英寸的钢板，则就会产生4英寸的废料。 三不同宽度的原料每英尺的价格分别是：15美分（宽度36英寸），19美分（宽度48英 寸)和28美分（宽度72英寸）。我们可以算出三种不同宽度的钢板每英寸×英尺的价格分 别为：15/36=0.416667美分（宽度36英寸），0.395833美分/（宽度48英寸），和0.38889美分 (宽度72英寸)。 可行的切割方式以及产生的废料见7.2.2中的表格。 例如，切割方式C4就是将72英寸的钢板切割成一个宽度为24英寸，4个宽度为10英寸。 这时有8个英寸的废料。 对各种宽度钢板的需求如下： 宽度（英寸） 60" 56" 42" 38" 34" 24" 15" 10" 需求长度（英尺） 500 400 300 450 350 100 800 1000 假设可用的原材料：72英寸宽的为1600英尺， 48和36英寸宽的都为1000英尺。 我们的问题是：在满足需求的前提下，每种方式要切割多少英尺使得成本最少？ ● 用公式表示问题并求解 假设下表中的变量A1,A2,·,E4表示对应切割方式切割的原材料的长度，单位是 英尺。 切割原材料的方式 生产中对原材料的需求宽度 60 56" 42"38"34" 24" 15" 10" 切割方式名称 72-Inch Raw Material 废料宽度 Al 1 0 0 0 0 0 0 1 2 A2 1 0 0 0 0 1 0 A3 0 1 0 0 0 0 0 1 6 A4 0 0 1 0 0 0 0 6 A5 0 0 1 0 0 0 2 0 0 A6 0 0 0 0 0 5

4 许多大的纸业公司为解决切割原料问题都建立了以LP为基础的处理程序。现实中的切 割原料问题还会涉及到其他多种成本因素（除了边角料）。以LP为基础的处理程序的作用 取决于这些其他因素。下面的实例没有涉及到其它的成本因素，它说明了切割原料问题的 基本原理。 2.5 切割原料问题实例 某器械公司生产电冰箱、火炉等一系列的家用电器。购买钢板的成本占材料费用的很 大一部分。通常，所购买的钢板是宽度为72英寸、48英寸和36英寸的卷钢。在生产过程中 需要8种不同宽度的钢板，宽度为：60，56，42，38，34，24，15 和10英寸。所有钢板的 质量和厚度都是一样的。 接下来的就是废料问题。如果宽度为72英寸的钢板被切割成一个宽度为38英寸和两个 宽度为15英寸的钢板，则就会产生4英寸的废料。 三不同宽度的原料每英尺的价格分别是：15美分（宽度36英寸），19美分（宽度48英 寸）和28美分（宽度72英寸）。我们可以算出三种不同宽度的钢板每英寸×英尺的价格分 别为：15/36 = 0.416667 美分/(宽度36英寸), 0.395833 美分/(宽度48英寸), 和0.38889美分 （宽度72英寸）。 可行的切割方式以及产生的废料见7.2.2中的表格。 例如，切割方式C4就是将72英寸的钢板切割成一个宽度为24英寸，4个宽度为10英寸。 这时有8个英寸的废料。 对各种宽度钢板的需求如下： 宽度（英寸） 60" 56" 42" 38" 34" 24" 15" 10" 需求长度（英尺） 500 400 300 450 350 100 800 1000 假设可用的原材料：72英寸宽的为1600英尺，48和36英寸宽的都为1000英尺。 我们的问题是：在满足需求的前提下，每种方式要切割多少英尺使得成本最少？ ⚫ 用公式表示问题并求解 假设下表中的变量Al，A2，.，E4 表示对应切割方式切割的原材料的长度，单位是 英尺。 切割原材料的方式 生产中对原材料的需求宽度 60" 56" 42'" 38" 34" 24" 15" 10" 切割方式名称 72-Inch Raw Material 废料宽度 A1 1 0 0 0 0 0 0 1 2 A2 0 1 0 0 0 0 1 0 1 A3 0 1 0 0 0 0 0 1 6 A4 0 0 1 0 0 1 0 0 6 A5 0 0 1 0 0 0 2 0 0 A6 0 0 1 0 0 0 1 1 5

Av 0 0 1 0 0 0 0 3 0 A8 0 0 0 1 1 0 0 0 0 A9 0 0 1 0 1 0 0 BO 0 0 0 1 0 0 2 0 4 Bl 0 0 1 0 0 1 9 B2 0 0 0 1 0 0 0 3 4 B3 0 0 0 0 2 0 0 0 4 B4 0 0 0 0 1 1 0 1 × B5 0 0 0 0 1 0 2 0 8 B6 0 0 0 0 1 0 1 2 3 B7 0 0 0 0 1 0 0 3 8 B8 0 0 0 0 0 3 0 0 0 B9 0 0 0 0 0 1 0 9 CO 0 0 0 0 0 2 0 2 4 C1 0 0 0 0 0 1 3 0 3 C2 0 0 0 0 0 2 8 C3 0 0 0 0 0 1 1 3 3 C4 0 0 0 0 0 1 0 4 8 Cs 0 0 0 0 0 0 2 C6 0 0 0 0 0 0 3 2 7 C7 0 0 0 0 0 0 4 2 C8 0 0 0 0 0 0 1 5 7 C9 0 0 0 0 0 0 0 7 2 48-Inch Raw Material DO 0 0 1 0 0 0 0 0 6 DI 0 0 0 1 0 0 0 1 0 D2 0 0 0 0 1 0 0 1 4 D3 0 0 0 0 0 2 0 0 0 D4 0 0 0 0 0 1 1 0 0 D5 0 0 0 0 0 1 0 2 4 D6 0 0 0 0 0 3 0 w D7 0 0 0 0 0 0 2 1 8 D& 0 0 0 0 0 0 1 3 3 D9 0 0 0 0 0 0 0 P

5 Av 0 0 1 0 0 0 0 3 0 A8 0 0 0 1 1 0 0 0 0 A9 0 0 0 1 0 1 0 1 0 B0 0 0 0 1 0 0 2 0 4 B1 0 0 0 1 0 0 1 1 9 B2 0 0 0 1 0 0 0 3 4 B3 0 0 0 0 2 0 0 0 4 B4 0 0 0 0 1 1 0 1 4 B5 0 0 0 0 1 0 2 0 8 B6 0 0 0 0 1 0 1 2 3 B7 0 0 0 0 1 0 0 3 8 B8 0 0 0 0 0 3 0 0 0 B9 0 0 0 0 0 2 1 0 9 C0 0 0 0 0 0 2 0 2 4 C1 0 0 0 0 0 1 3 0 3 C2 0 0 0 0 0 1 2 1 8 C3 0 0 0 0 0 1 1 3 3 C4 0 0 0 0 0 1 0 4 8 Cs 0 0 0 0 0 0 4 1 2 C6 0 0 0 0 0 0 3 2 7 C7 0 0 0 0 0 0 2 4 2 C8 0 0 0 0 0 0 1 5 7 C9 0 0 0 0 0 0 0 7 2 48-Inch Raw Material D0 0 0 1 0 0 0 0 0 6 D1 0 0 0 1 0 0 0 1 0 D2 0 0 0 0 1 0 0 1 4 D3 0 0 0 0 0 2 0 0 0 D4 0 0 0 0 0 1 1 0 9 D5 0 0 0 0 0 1 0 2 4 D6 0 0 0 0 0 0 3 0 3 D7 0 0 0 0 0 0 2 1 8 D8 0 0 0 0 0 0 1 3 3 D9 0 0 0 0 0 0 0 4 8

6 36-Inch Raw Material EO 0 0 0 0 1 0 0 0 2 El 0 0 0 0 0 1 0 2 E2 0 0 0 0 0 0 2 0 6 E3 0 0 0 0 0 0 1 2 1 E4 0 0 0 0 0 0 0 3 6 为了计算方便：我们定义下面的变量： T1=切割宽72英寸原材料的长度（单位：英尺）， T2=切割宽48英寸原材料的长度（单位：英尺）， T3=切割宽36英寸原材料的长度（单位：英尺）， W1=切割宽72英寸原材料的废料（单位：inch×feet), W2=切割宽48英寸原材料的废料（单位：inch×feet) W3=切割宽36英寸原材料的废料（单位：inch×feet), X1=超过60英寸宽度需求材料的长度（单位：英尺）， X2=超过56英寸宽度需求材料的长度（单位：英尺）， X8=超过10英寸宽度需求材料的长度（单位：英尺）。 这个问题的目标函数又是什么？人们自然会想到计算一下废料的成本，然后再求出废 料成本最小的切割方式。 例如 MIN=0.3888891W1+0.395833W2+0.416667W3: 当然，这很可能得到废料很少，而成本很高的解答。特别是当不同规格的原材料每平 方英寸的价格不相等时，这种结果就可能发生。更合理的目标是使得总成本达到最少。 MIN=28*T1+19*T2+15*T3; 这样我们就得到下面的模型： MODEL: SETS: !SUPP工E表示三种原材料集合，在这个模型里10对应了0： SUPPLY/1.3/:T,W,C,WCOST,S; !三种原材料的价格C,废料，废料成本WCOST和数量S及三种原材料的实际用量T: !WHICH表示5类切割方式的集合： WHICH./1.5/:; !ISIT表示原材料与切割方式的乘积： ISIT(SUPPLY,WHICH):YN; !YN表示对原材料可进行的切割类别： PATTERN/1.10/:; STYLE WHICH,PATTERN):AMT,WASTE;

6 36-1nch Raw Material E0 0 0 0 0 1 0 0 0 2 El 0 0 0 0 0 1 0 1 2 E2 0 0 0 0 0 0 2 0 6 E3 0 0 0 0 0 0 1 2 1 E4 0 0 0 0 0 0 0 3 6 为了计算方便：我们定义下面的变量： T1 = 切割宽72英寸原材料的长度（单位：英尺）， T2 = 切割宽48英寸原材料的长度（单位：英尺）， T3 = 切割宽36英寸原材料的长度（单位：英尺）， W1 = 切割宽72英寸原材料的废料（单位：inch × feet）， W2 = 切割宽48英寸原材料的废料（单位：inch × feet） W3 = 切割宽36英寸原材料的废料（单位：inch × feet）, X1 = 超过60英寸宽度需求材料的长度（单位：英尺）， X2 = 超过56英寸宽度需求材料的长度（单位：英尺）， . X8 = 超过10英寸宽度需求材料的长度（单位：英尺）。 这个问题的目标函数又是什么？人们自然会想到计算一下废料的成本，然后再求出废 料成本最小的切割方式。 例如 MIN = 0.3888891W1 + 0.395833W2 + 0.416667W3; 当然，这很可能得到废料很少，而成本很高的解答。特别是当不同规格的原材料每平 方英寸的价格不相等时，这种结果就可能发生。更合理的目标是使得总成本达到最少。 MIN= 28 * T1 + 19 * T2 + 15 * T3; 这样我们就得到下面的模型： MODEL: SETS: !SUPPLE表示三种原材料集合，在这个模型里10对应了0; SUPPLY/1.3/: T, W, C, WCOST, S; !三种原材料的价格C，废料W，废料成本WCOST和数量S及三种原材料的实际用量T; !WHICH表示5类切割方式的集合; WHICH/1.5/:; !ISIT表示原材料与切割方式的乘积; ISIT( SUPPLY, WHICH): YN; !YN表示对原材料可进行的切割类别; PATTERN/1.10/:; STYLE( WHICH, PATTERN): AMT, WASTE;

!WASTE表示废料宽度，AMT表示每种切割方式下原材料的实际用量，N表示需求长度； WIDTH/1.8/:N,X; NUMBER(STYLE,WIDTH):NUM; !NUM表示切割计划； ENDSETS DATA: C= 28 19 15: WCOST 0.388889 0.3958330.416667: S= 1600 10000 10000; N=5004003004503501008001000: YN=11100 00010 00001: WASTE=2166050000 9444838094 3838272724 0409438386 2616000002: NUM 10000001 00000121 01000010 00000113 01000001 00000104 00100100 00000041 00100020 00000032 00100011 00000024 00100003 00000015 00011000 00000007 00010101 00000202 00000000 00010001 00010011 00001001 00010003 00000200 00002000 00000110 00001101 00000102 00001020 00000030 00001012 00000021 00001003 00000013 00000300 00000004 00000210 00100000 00010020 00000101 00000130 00000020

7 !WASTE表示废料宽度，AMT表示每种切割方式下原材料的实际用量，N表示需求长度; WIDTH/1.8/: N, X; NUMBER( STYLE, WIDTH): NUM; !NUM表示切割计划; ENDSETS DATA: C = 28 19 15; WCOST = 0.388889 0.395833 0.416667; S= 1600 10000 10000; N = 500 400 300 450 350 100 800 1000; YN= 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1; WASTE = 2 1 6 6 0 5 0 0 0 0 9 4 4 4 8 3 8 0 9 4 3 8 3 8 2 7 2 7 2 4 0 4 0 9 4 3 8 3 8 6 2 6 1 6 0 0 0 0 0 2; NUM = 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 2 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 3 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 3 0 0 0 0 2 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 2 0 0 0 0 0 1 0 1 2 0 0 0 0 1 0 0 3 0 0 0 0 0 3 0 0 0 0 0 0 0 2 1 0 0 0 0 1 0 0 2 0 0 0 0 0 0 1 3 0 0 0 0 0 0 1 2 1 0 0 0 0 0 1 1 3 0 0 0 0 0 1 0 4 0 0 0 0 0 0 4 1 0 0 0 0 0 0 3 2 0 0 0 0 0 0 2 4 0 0 0 0 0 0 1 5 0 0 0 0 0 0 0 7 0 0 0 0 0 2 0 2 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 3 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 4 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 2 0

8 00000012 00000000 00000003 00000000 00000000 00000000 00000000 00001000: ENDDATA !将虚设的变量A10和E5~E9取为0值： @FOR (PATTERN (I)I#GE#5#AND#I#LE#9:AMT (5,I)=0) AMT(1,10)=0: ！目标函数； MIN=@SUM(SUPPLY:T*C); !这不是废料最少，但看起来有点象； NOTMIN=@SUM (SUPPLY:W*WCOST); !下面是(U72),(048),and(036): @FOR(SUPPLY(I): T(I)=@SUM(STYLE (J,K)YN (I,J)*AMT (J,K)); ！(s72),(S48),MD(S36): W(I)=@SUM(STYLE (J,K)YN (I,J)*WASTE (J,K)*AMT (J,K)); !供应约束；T(I)<S(I)): ！(D60)through(D10): @FOR(WIDTH (K)N(K)+X (K)=@SUM(STYLE (I,J)NUM(I,J,K)*AMT (I,J))); END 约束(s72)、(s48)和(s36)限制有效的原材料宽度，约束(u72),(u48)和(u36)定义变量T1, T2,和T3。约束(D10)到(D60)限制8种需求必须满足。例如，(D60)限制宽度为60英寸的产 品至少有500英尺，而(D10)限制宽度为10英寸的产品至少达到最低要求。 下表给出了用两种目标函数求出的两个结果，以便进行对比： 切割原料解答 非零的切割方式 废料最小解答 总成本最小的解答 Al 500 500 A2 400 400 A5 200 171.4286 A7 100 128.5714 A8 350 350 A9 50 3.571429 B8 0 32.14286 C9 0 14.28571 DI 150 96.42857 D3 9850 0 废料成本 $5.44 $5.55

8 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0; ENDDATA !将虚设的变量Al0和E5~E9取为0值; @FOR(PATTERN(I)|I#GE#5#AND#I#LE#9:AMT(5,I)=0); AMT(1,10)=0; !目标函数; MIN=@SUM(SUPPLY:T*C); !这不是废料最少，但看起来有点象; NOTMIN=@SUM(SUPPLY:W*WCOST); !下面是(U72),(U48),and(U36) ; @FOR(SUPPLY(I): T(I)=@SUM(STYLE(J,K):YN(I,J)*AMT(J,K)); !(S72),(S48),MD(S36); W(I)=@SUM(STYLE(J,K): YN(I,J)*WASTE(J,K)*AMT(J,K)); !供应约束;T(I)<S(I) ); !(D60) through (D10); @FOR(WIDTH(K):N(K)+X(K)= @SUM(STYLE(I,J): NUM(I,J,K) * AMT(I,J) ) ); END 约束(s72)、(s48)和(s36)限制有效的原材料宽度，约束(u72)，(u48)和(u36)定义变量T1， T2，和T3。约束(D10)到(D60)限制8种需求必须满足。例如，(D60)限制宽度为60英寸的产 品至少有500英尺，而(D10)限制宽度为10英寸的产品至少达到最低要求。 下表给出了用两种目标函数求出的两个结果，以便进行对比： 切割原料解答 非零的切割方式 废料最小解答 总成本最小的解答 A1 500 500 A2 400 400 A5 200 171.4286 A7 100 128.5714 A8 350 350 A9 50 3.571429 B8 0 32.14286 C9 0 14.28571 D1 150 96.42857 D3 9850 0 废料成本 $5.44 $5.55

9 总成本 $2348.00 $466.32 X4 100.000 0 X6 19650 0 TI 1600 1600 T2 10000 96.429 T3 0 0 使用"Min trim waste"产生的解答与第一个解答最关键的差别是使用了较多的48英寸 宽的原材料，而且切割方式也比较单一，从而废料很少。但是，由于42英寸的产品和34英 寸的产品超过了需求，也是一种浪费。而这部分浪费并没有记入废料中。 两种解答都会涉及到分数问题。如果小数部分相对整数比较小的话，实际问题中往往 是通过取整的办法进行处理（就是取最接近的整数）。 2.6案例及参考解答 2-1.某些设备的生产必须一周每天都开工才能完成，它们所面临的问题就是如何根据 每天劳动力的需求来进行人员的配置。劳动力的需求是一周天数的函数。这类问题普遍存 在于公共服务和运输部门中。也许多数职工安置问题都会涉及到如何安排专职职员的休假 问题。特别规定每一名劳动力每周休息两天。如果给定了每周每天的劳动力需求，问题是 在满足每周对劳动力需求的前提下，需要聘用劳动力的最小数量是多少？同时指出一周每 天劳动力的实际人数。 为了明确起见，我们研究下面Festus城市公交公司的问题。每周每天需要的驾驶员人数 如下： Mon Tues Wed Thurs Fri Sat Sun 18161516191412 如果一名驾驶员一周连续工作5天，一周每天各有多少驾驶员在值班？ 建立这个问题的LP模型，并求出最优解。 参考解答： Model: MIN=M T W R F S+N; M+ +R+F +S +N >=18: 山 T +F +S +N >=16; M +T +W +S +N >=15; 4 T +W +R +N >=16: +W R +F >=19: T+W R +F +S >=14; W +R +F +S +N >=12: End 解答： Objective value: 22.00000

9 总成本 $2348.00 $466.32 X4 100.000 0 X6 19650 0 T1 1600 1600 T2 10000 96.429 T3 0 0 使用"Min trim waste"产生的解答与第一个解答最关键的差别是使用了较多的48英寸 宽的原材料，而且切割方式也比较单一，从而废料很少。但是，由于42英寸的产品和34英 寸的产品超过了需求，也是一种浪费。而这部分浪费并没有记入废料中。 两种解答都会涉及到分数问题。如果小数部分相对整数比较小的话，实际问题中往往 是通过取整的办法进行处理（就是取最接近的整数）。 2.6 案例及参考解答 2-1. 某些设备的生产必须一周每天都开工才能完成，它们所面临的问题就是如何根据 每天劳动力的需求来进行人员的配置。劳动力的需求是一周天数的函数。这类问题普遍存 在于公共服务和运输部门中。也许多数职工安置问题都会涉及到如何安排专职职员的休假 问题。特别规定每一名劳动力每周休息两天。如果给定了每周每天的劳动力需求，问题是 在满足每周对劳动力需求的前提下，需要聘用劳动力的最小数量是多少？同时指出一周每 天劳动力的实际人数。 为了明确起见，我们研究下面Festus城市公交公司的问题。每周每天需要的驾驶员人数 如下： Mon Tues Wed Thurs Fri Sat Sun 18 16 15 16 19 14 12 如果一名驾驶员一周连续工作5天，一周每天各有多少驾驶员在值班？ 建立这个问题的LP模型，并求出最优解。 参考解答： Model: MIN=M + T + W + R + F + S + N; M + + R + F + S + N >=18; M + T + F + S + N >=16; M + T + W + S + N >=15; M + T + W + R + N >=16; M + T + W + R + F >=19; T + W + R + F + S >=14; W + R + F + S + N >=12; End 解答： Objective value: 22.00000

10 Variable Value Reduced Cost 4 8.000000 0.0000000 2 2.000000 0.0000000 命 2.000000 0.0000000 R 4.000000 0.0000000 E 3.000000 0.0000000 S 3.000000 0.0000000 N 0.0000000 0.0000000 一周每天值班人数和需求一样，总人数未22人。 2-2.上面Festus城市公交公司的问题中我们无意忽略了几个重要的细节（看前面的问 题)： )每周平时每人每小时的工资是$50，星期六是$75，星期天是$90。 b)最多可以聘用三个兼职人员。主要是在星期五、星期六和星期天这三天。三个小 时一班，每班工资是200美元。 适当地修改模型。用否聘用兼职人员？ 参考解答： 如果不聘用兼职人员，总费用是33000美元（一天6小时工作制）。聘用兼职人员的模 型如下： Model: MIN=(M+T+W+R+F+S+N)*5*6*50+P*3*200; +R+F+S+N >=18: 四 + +F +S+N >=16: M + +W +S +N >=15: 西 +T +W +R +N >=16: M + +W +R +F +p/2 >=19; R +F +S p/2 >=14: 今 +R +F +S +N p/2 >=12: End 运行模型后P=O,说明不要聘用兼职人员。 2-3.Uncommon Result是一个政治性的组织，它想用发行大量邮件的方式来来获取基 金。邮件接收人可以分为6种类型。可以通过购买现有8个邮件发送清单来得到各类邮件接 收人的真实姓名。每个邮件清单仅仅包含部分类型的邮件接收人，具体包含哪些如下表所 示： 邮件接收人 邮件列表医学博士.法学博士D.D.S.商业经理人砖工水管工成本 Y NY N N $5000 2 N N N N $4000

10 Variable Value Reduced Cost M 8.000000 0.0000000 T 2.000000 0.0000000 W 2.000000 0.0000000 R 4.000000 0.0000000 F 3.000000 0.0000000 S 3.000000 0.0000000 N 0.0000000 0.0000000 一周每天值班人数和需求一样，总人数未22人。 2-2. 上面Festus城市公交公司的问题中我们无意忽略了几个重要的细节(看前面的问 题)： a) 每周平时每人每小时的工资是$50，星期六是$75，星期天是$90。 b) 最多可以聘用三个兼职人员。主要是在星期五、星期六和星期天这三天。三个小 时一班，每班工资是200美元。 适当地修改模型。用否聘用兼职人员？ 参考解答： 如果不聘用兼职人员，总费用是33000美元（一天6小时工作制）。聘用兼职人员的模 型如下： Model: MIN=(M + T + W + R + F + S + N)*5*6*50+P*3*200; M + + R + F + S + N >=18; M + T + F + S + N >=16; M + T + W + S + N >=15; M + T + W + R + N >=16; M + T + W + R + F + p/2 >=19; T + W + R + F + S + p/2 >=14; W + R + F + S + N + p/2 >=12; End 运行模型后P=0，说明不要聘用兼职人员。 2-3. Uncommon Result是一个政治性的组织，它想用发行大量邮件的方式来来获取基 金。邮件接收人可以分为6种类型。可以通过购买现有8个邮件发送清单来得到各类邮件接 收人的真实姓名。每个邮件清单仅仅包含部分类型的邮件接收人，具体包含哪些如下表所 示： 邮件接收人 邮件列表 医学博士. 法学博士 D.D.S. 商业经理人 砖工 水管工 成本 1 Y N N Y N N $5000 2 N Y Y N N N $4000