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