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