第四章 部分习题 2.一家出版社准备在某市建立两个销售代理点,向7个区的大学生售书,每个区的大学生 数量(单位:千人)已经表示在图上,每个销售代理点只能向本区和一个相邻区的大学生售 书,这两个销售代理点应该建在何处,才能使所供应 的大学生的数量最大?建立该问题的整数线性规划模 型并求解 3.某储蓄所每天的营业时间是上午9:00到下午5:00 根据经验,每天不同时间段所需要的服务员数量如下: 71 时间段(时)9-1010-111-1212-11-22-33-4451 服务员数量4 储蓄所可以雇佣全时和半时两类服务员,全时服务员每天报酬100元,从上午9:00到下午 5:00工作,但中午1200到下午2:00之间必须安排1小时的午餐时间,储蓄所每天可以雇 佣不超过3名的半时服务员,每个半时服务员必须连续工作4小时,报酬40元,问该储蓄 所应该如何雇佣全时和半时两类服务员?如果不能雇佣半时服务员,每天至少增加多少费 用?如果雇佣半时服务员的数量没有限制,每天可以减少多少费用? 6.某公司将4种不同含硫量的液体原料(分别记为甲、乙、丙、丁)混合生产两种产品(分 别记为A,B),按照生产工艺要求,原料甲、乙、丁必须首先倒入混合池中混合,混合后 的液体再分别与原料丙混合生产A、B。已知,原料甲、乙、丙、丁的含硫量分别是3,1, 2,1(%),进货价格分别为6,16,10,15(千元/吨);产品A、B的含硫量分别不能超过 2.5,1.5(%),售价分别为9,15(千元吨),根据市场信息,原料甲、乙、丙的供应量有 限制,原料丁的供应量最多为50吨:产品A、B的市场需求分别为100,200吨,问应如何 安排生产? 参考答案 2.将大学生数量为34,29,42,21,56,18,71的区分别标号为1,2,3,4,5,6,7区, 划出区与区之间的如下相邻关系图:
第四章 部分习题 2. 一家出版社准备在某市建立两个销售代理点，向 7 个区的大学生售书，每个区的大学生 数量（单位：千人）已经表示在图上，每个销售代理点只能向本区和一个相邻区的大学生售 书，这两个销售代理点应该建在何处，才能使所供应 的大学生的数量最大？建立该问题的整数线性规划模 型并求解 3. 某储蓄所每天的营业时间是上午 9:00 到下午 5:00, 根据经验，每天不同时间段所需要的服务员数量如下： 时间段（时） 9—10 10—11 11—12 12—1 1—2 2—3 3—4 4—5 服务员数量 4 3 4 6 5 6 8 8 储蓄所可以雇佣全时和半时两类服务员，全时服务员每天报酬 100 元，从上午 9:00 到下午 5:00 工作，但中午 12:00 到下午 2:00 之间必须安排 1 小时的午餐时间，储蓄所每天可以雇 佣不超过 3 名的半时服务员，每个半时服务员必须连续工作 4 小时，报酬 40 元，问该储蓄 所应该如何雇佣全时和半时两类服务员？如果不能雇佣半时服务员，每天至少增加多少费 用？如果雇佣半时服务员的数量没有限制，每天可以减少多少费用？ 6. 某公司将 4 种不同含硫量的液体原料（分别记为甲、乙、丙、丁）混合生产两种产品（分 别记为 A，B），按照生产工艺要求，原料甲、乙、丁必须首先倒入混合池中混合，混合后 的液体再分别与原料丙混合生产 A、B。已知，原料甲、乙、丙、丁的含硫量分别是 3，1， 2，1（%），进货价格分别为 6，16，10，15（千元/吨）；产品 A、B 的含硫量分别不能超过 2.5，1.5（%）,售价分别为 9，15（千元/吨），根据市场信息，原料甲、乙、丙的供应量有 限制，原料丁的供应量最多为 50 吨；产品 A、B 的市场需求分别为 100，200 吨，问应如何 安排生产？ 参考答案 2. 将大学生数量为 34，29，42，21，56，18，71 的区分别标号为 1，2，3，4，5，6，7 区， 划出区与区之间的如下相邻关系图：
记r为第区的大学生人数,用01变量x=1表示(,)区的大学生由一个销售代理点供 应图书(≤且,/相邻),否则x,=0,建该问题的整数线性规划模型 ax∑(+rkx ∑x≤ ∑x+∑ ji≤ xn∈Q} Mnx63x12+67x13+71x23+50x24+85x25+63x34+77x4+39x46+92x47+74x56+89x67 1x12+x13+x23+x24+x25+x34+x45+x46+x,+6+x,≤2 x 1 x13+x23+x34≤1 x24+x34+x45+x46+x47≤1 x2+x4+x。≤1 0或1 用LⅠNDO求解得到:最优解为x25=x47=1(其他为0)最优值为177千人 3.设储蓄所每天雇佣的全时服务员中以12:00~为午餐时间的有x1名,以1:00~2:00 为午餐时间的有x名;半时服务员中从9:00,10:00,11:00,12:00,1:00开始工作 的分别为y1,y2,y3,y4,y5名,列出模型: Mi100x1+100x2+40y1+40y2+40y3+40y4+40y5
记 i r 为第 i 区的大学生人数，用 0-1 变量 xij = 1 表示 (i, j) 区的大学生由一个销售代理点供 应图书 (i j且i, j相邻) ，否则 xij = 0 ,建该问题的整数线性规划模型 ( + ) i j相邻 i j ij Max r r x , i j ij st x , . . 2 + 1 j j ij x ji i xij 0,1 即 63 12 67 13 71 23 50 24 85 25 63 34 77 45 39 46 92 47 74 56 89 67 Max x + x + x + x + x + x + x + x + x + x + x = + + + + + + + + + + + + + + + + + + + + + + + + + 0 1 1 1 1 1 1 1 1 2 . . 4 7 6 7 4 6 5 6 6 7 2 5 4 5 5 6 2 4 3 4 4 5 4 6 4 7 1 3 2 3 3 4 1 2 2 3 2 4 2 5 1 2 1 3 1 2 1 3 2 3 2 4 2 5 3 4 4 5 4 6 4 7 5 6 6 7 xi j 或 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x st 用 LINDO 求解得到：最优解为 x25 = x47 =1 （其他为 0）最优值为 177 千人. 3. 设储蓄所每天雇佣的全时服务员中以 12：00～为午餐时间的有 1 x 名，以 1：00～2：00 为午餐时间的有 x2 名；半时服务员中从 9：00，10：00，11：00，12：00，1：00 开始工作 的分别为 1 2 3 4 5 y , y , y , y , y 名，列出模型： 100 1 100 2 40 1 40 2 40 3 40 4 40 5 Min x + x + y + y + y + y + y
y1≥4 +x2+y1+y2≥3 +x+y1+y2+y2≥4 y1+y2+y3+y4≥6 y1+y2+y3+y4+y5≥5 st +y3+y4+y≥6 +y4+y5≥8 XI ≥8 +y1+y2+y3+y4+ys≤3 ≥0且为整数 (1)求解得到最优解x1=3,x2=4,y=0,y2=0,y3=2,y4=0,y3=1,最小费用为820 (2)如果不能雇佣半时服务员,则最优解为 x1=5x2=6,y1=0,y2=0,y3=0,y4=0,y5=0,最小费用为100远,即每天至少增 加1100-820=280元。 (3)如果雇佣半小时服务员的数量没有限制,则最优解为 x1=0,x2=0,y1=4,y2=0,y3=0,y4=2,y5=8,最小费用为560元,既每天可以减少 820-560=260元 6.设y1=1分别是产品A中是来自混合池和原料丙的吨数,y2,=2分别是产品B中是来自混 合池和原料丙的吨数:混合池中原料甲乙丙所占的比例分别为x,x2,x4。优化目标是总利 润最大,即 Mx(9-6x1-16x2-15x1)y1+(15-6x,-16x2-15x)y2+(0-101+(15-10)k2 约束条件为 1)原料最大供应量限制:x4(v+y2)≤50 2)产品最大需求量限制:y+1≤100,y2+二2≤200 3)产品最大含硫量限制: 对产品A, (3x1+x2+x)y ≤25,即(3x1+x2+x4-25)y1-0.5=1≤0 y+1 对产品B(3x1+x2+x4-1.5)y2+0.5z2≤0 4)其他限制:x1+x2+x4=1,x1,x2,x4,y1,=1,y2,2≥0 用LNGO求解得到结果为:x2=x4=0.5,y2=二2=100其余为0;目标函数值为
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + , , , , , , 0且为整数 3 8 8 6 5 6 4 3 4 . . 1 2 1 2 3 4 5 1 2 3 4 5 1 2 5 1 2 4 5 1 2 3 4 5 1 1 2 3 4 5 2 1 2 3 4 1 2 1 2 3 1 2 1 2 1 2 1 x x y y y y y y y y y y x x y x x y y x x y y y x y y y y y x y y y y x x y y y x x y y x x y st (1) 求解得到最优解 x1 = 3, x2 = 4, y1 = 0, y2 = 0, y3 = 2, y4 = 0, y5 =1,最小费用为 820 元。 (2) 如果不能雇佣半时服务员，则最优解为 x1 = 5, x2 = 6, y1 = 0, y2 = 0, y3 = 0, y4 = 0, y5 = 0 ，最小费用为 1100 远，即每天至少增 加 1100-820=280 元。 (3) 如果雇佣半小时服务员的数量没有限制，则最优解为 x1 = 0, x2 = 0, y1 = 4, y2 = 0, y3 = 0, y4 = 2, y5 = 8 ，最小费用为 560 元，既每天可以减少 820-560=260 元。 6. 设 1 1 y ,z 分别是产品 A 中是来自混合池和原料丙的吨数， 2 2 y ,z 分别是产品 B 中是来自混 合池和原料丙的吨数；混合池中原料甲乙丙所占的比例分别为 1 2 4 x , x , x 。优化目标是总利 润最大，即 ( ) ( ) ( ) ( ) 9 6 1 16 2 15 4 1 15 6 1 16 2 15 4 2 9 10 1 15 10 2 Max − x − x − x y + − x − x − x y + − z + − z 约束条件为: 1)原料最大供应量限制： x4 (y1 + y2 ) 50 2) 产品最大需求量限制： y1 + z1 100, y2 + z2 200 3) 产品最大含硫量限制： 对产品 ( ) 2.5 3 2 , 1 1 1 2 4 1 1 + + + + y z x x x y z A ，即 (3x1 + x2 + x4 − 2.5)y1 − 0.5z1 0 对产品 B, (3x1 + x2 + x4 −1.5)y2 + 0.5z2 0 4)其他限制： x1 + x2 + x4 =1, x1 , x2 , x4 , y1 ,z1 , y2 ,z2 0 用 LINGO 求解得到结果为： 0.5, 100, x2 = x4 = y2 = z2 = 其余为 0；目标函数值为
450
450