运筹学 练习题

1、.案例1，原始问题：某公司现有三条生产线，由于原有产品出现销售量下降的情况，管理部门决定调整公司的产品线，停产不赢利的产品以释放产能来生产两种新产品。其中，生产甲产品要占用生产线1和生产线3的部分产能，产品乙需要占用生产线2和3的部分产能。管理部门需要考虑下列问题：1、 公司是否应该生产这两种产品？2、 若生产，则两种产品的数量如何确定？数据：运筹小组与管理部门研究后去顶，两种产品的数量如何确定以使产品的总利润最大？因此，需要如下的信息：1、 每条生产线的可得生产能力是多少？2、 生产每一单位产品需要每条生产线多少生产能力？3、 每种产品的单位利润是多少？生产部门和财务部门经过分析，提出如下数

2、据：生产线产品甲产品乙生产线每周可用时间一104二0212三3218单位产品利润35模型：1、 要做出什么决策？（决策变量）2、 做出的决策会有哪些条件限制？（约束条件）3、 这些决策的全部评价标准是什么？（目标函数）max z=3x1+5x2st. x1=42x2=123x1+2x2=0决策：x1=2,x2=6, z=3600生产时间信息：按模型所确定的生产方案需要生产线2和3的所有时间，只有生产线1有2小时的剩余。1、用单纯形表求解以下线性规划问题（1）maxz=x1-2x2+x3s.t.x1+x2+x3122x1+x2-x36-x1+3x29x1,x2,x30解：标准化，将目标函数转变成

3、极小化，引进松弛变量x4,x5,x60,得到：minz=-x1+2x2-x3s.t.x1+x2+x3+x4=122x1+x2-x3+x5= 6-x1+3x2+x6= 9x1,x2,x3,x4,x5,x60列出初始单纯形表zx1x2x3x4x5x6RHSz11-210000x401111001212/1x5021-10106-x60-1300019-选取x3为进基变量，确定x4为离基变量zx1x2x3x4x5x6RHSz10-30-100-12x301111001212/1x503201101818/3x60-1300019-得到最优解（x1, x2, x3, x4, x5, x6）=（0, 0

4、, 12, 0, 18, 9），min z=-12，max z=12由于其中非基变量x1在目标函数中的系数为0，x1进基，x5离基，可以得到另一最优解：zx1x2x3x4x5x6RHSz10-30-100-12x3001/312/3-1/306x1012/301/31/306x60011/301/31/3115新的最优解为（x1,x2,x3,x4,x5,x6）=（6, 0, 6, 0, 0, 15），min z=-12，max z=12原问题最优解的全体为：，（0l1），都有max z=12（2）maxz=x1+3x2+4x3s.t.3x1+2x213x2+3x3172x1+x2+x3=13x

5、1,x2,x30解：将目标函数转化成极小化，引进松弛变量x4，x5，x60，得到minz=-x1-3x2-4x3s.t.3x1+2x2+x4=13x2+3x3+x5=172x1+x2+x3=13x1,x2,x3,x4,x5,0引进人工变量x60，构造辅助问题：minz=x6s.t.3x1+2x2+x4=13x2+3x3+x5=172x1+x2+x3+x6=13x1,x2,x3,x4,x5,x60列出辅助问题的系数矩阵表：zx1x2x3x4x5x6RHSz100000-10x4032010013x5001301017x6021100113消去基变量x6在目标函数中的系数，并开始单纯形叠代：zx1

6、x2x3x4x5x6RHSz121100013x403201001313/3x5001301017-x602110011313/2x1进基，x4离基，zx1x2x3x4x5x6RHSz10-1/31-2/30013/3x1012/301/30013/3-x500130101717/3x600-1/31-2/30113/313/3x3进基，x6离基，zx1x2x3x4x5x6RHSz100000-10x1012/301/30013/3x500202104x300-1/31-2/30113/3辅助问题已经获得最优解，且min z=0，因而可以转入第二阶段，其系数矩阵表为：zx1x2x3x4x5RH

7、Sz1134000x1012/301/3013/3x50020214x300-1/31-2/3013/3消去基变量x1，x3在目标函数中的系数：zx1x2x3x4x5RHSz1011/307/30-65/3x1012/301/3013/313/2x500202144/2x300-1/31-2/3013/3-x2进基，x5离基zx1x2x3x4x5RHSz1000-4/3-11/6-29x10100-1/3-1/33x2001021/22x30001-1/31/65得到原问题的最优解：（x1, x2, x3）=（3, 2, 5），min z=-29，max z=293、用对偶单纯形法求解以下问题

8、(1)minz=4x1+6x2+18x3s.t.x1+3x33x2+2x35x1,x2,x30引进松弛变量x4、x50minz=4x1+6x2+18x3s.t.-x1-3x3+x4=-3-x2-2x3+x5=-5x1,x2,x3，x4，x50列出单纯形表zx1x2x3x4x5RHSz1-4-6-18000x40-10-310-3x500-1-201-54/118/3x4离基，x1进基zx1x2x3x4x5RHSz10-6-6-4012x10103-103x500-1-201-56/16/2x5离基，x3进基zx1x2x3x4x5RHSz10-30-4-327x101-3/20-13/2-9/2

9、x3001/210-1/25/224x1离基，x2进基zx1x2x3x4x5RHSz1-200-2-636x20-2/3102/3-13x301/301-1/301最优解为x1=0，x2=3，x3=1，x4=0，x5=0，min z=36某工厂用甲、乙、丙三种原料生产A,B,C,D四种产品，每种产品消耗原料定额以及三种原料的数量如下：产品ABCD原料数量（t）甲原料（t/万件）32142400乙原料（t/万件）2-233200丙原料（t/万件）13-21800单位产品的利润（万元/万件）25121415（1） 求使总利润最大的生产计划和按最优生产计划生产时三种原料的耗用量和剩余量；（2） 求四

10、种产品的利润在什么范围内变化，最优生产计划不会变化（3） 求三种原料的影子价格和四种产品的机会成本，并解释最优生产计划中有的产品不安排生产的原因。（4） 在最优生产计划下，哪一种原料更为紧缺？如果甲原料增加120吨，这时紧缺程度是否有变化？(1)利润最大化的线性规划模型为：maxz=25x1+12x2+14x3+15x4s.t.3x1+2x2+x3+4x424002x1+2x3+3x43200x1+3x2+2x41800x1,x2,x3,x40单纯形表为：zx1x2x3x4x5x6x7RHSz1251214150000x5032141002400x6020230103200x701302001

11、1800x1进基，x5离基zx1x2x3x4x5x6x7RHSz10-14/317/3-55/3-25/300-20000x1012/31/34/31/300800x600-4/34/31/3-2/3101600x7007/3-1/32/3-1/3011000x3进基，x6离基zx1x2x3x4x5x6x7RHSz1010-79/4-11/2-17/40-26800x101105/41/2-1/40400x300-111/4-1/23/401200x700203/4-1/21/411400x2进基，x1离基zx1x2x3x4x5x6x7RHSz1-100-21-6-40-27200x20110

12、5/41/2-1/40400x301013/201/201600x70-200-7/4-3/23/41600最优解为：x1=0，x2=400，x3=1600，x4=0，x5=0，x6=0，x7=600，max z=27200即最优生产计划为：产品A：不生产；产品B：400万件；产品C：1600万件；产品D：不生产，最大利润：27200万元。原料甲：耗用2400吨，没有剩余；原料乙：耗用3200吨，没有剩余；原料丙：耗用1200吨，剩余600吨。（2） 产品A利润变化范围：-C-25+d-12-14-150000zx1x2x3x4x5x6x7RHS-CBz1-1-d00-21-6-40-2720

13、0-12x201105/41/2-1/40400-14x301013/201/2016000x70-200-7/4-3/23/41600-1-d0，d-1，-c1=-c1+d-25-1=-26，即c126（万元/万件）产品B利润变化范围：-C-25-12+d-14-150000zx1x2x3x4x5x6x7RHS-CBz1-1-d00-21+5/4d-6+1/2d-4-1/4d0-27200+400d-12+dx201105/41/2-1/40400-14x301013/201/2016000x70-200-7/4-3/23/41600，-1d12，-13-12+d0，-13-c20，即：0c

14、213。产品C利润的变化范围：-C-25-12-14+d-150000zx1x2x3x4x5x6x7RHS-CBz1-1-d00-21+3/2d-6-4+1/2d0-27200+1600d-12x201105/41/2-1/40400-14+dx301013/201/2016000x70-200-7/4-3/23/41600，-1d8，-15-14+d-6，-15-c3-6，6c315产品D的变化范围-C-25-12-14-15+d0000zx1x2x3x4x5x6x7RHS-CBz1-100-21-d-6-40-27200-12x201105/41/2-1/40400-14x301013/201/2016000x70-200-7/4-3/23/41600-21-d0，d-21，-15+d-36，-c4-36，c436。（3） 求三种原料的影子价格和四种产品的机会成本由最优单纯形表可知，原料甲、乙、丙的影子价格分别为：6万元/吨、4万元/吨、0万元/吨。产品A、B、C、D的机会成本分别为：26万元/万件、12万元/万件、14万元/万件、36万元/万件。产品A、D在最优解中不安排生产的原因是机会成本大于利润。（4） 在最优解中，原料甲的影子价格（6万元/吨）最大，因此这种原料最紧缺。如果原料A增加120吨，最优单