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:y<M); @for(b(i): @sum(a(j)y(j,i))>x(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:y<M); @for(b(i): @sum(a(j):y(j,i))>x(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));