案例1，原始问题：某公司现有三条生产线，由于原有产品出现销售量下降的情况，管理部门决定调整公司的产品线，停产不赢利的产品以释放产能来生产两种新产品。

其中，生产甲产品要占用生产线1和生产线3的部分产能，产品乙需要占用生产线2和3的部分产能。

管理部门需要考虑下列问题：1、公司是否应该生产这两种产品2、若生产，则两种产品的数量如何确定数据：运筹小组与管理部门研究后去顶，两种产品的数量如何确定以使产品的总利润最大因此，需要如下的信息：1、每条生产线的可得生产能力是多少2、生产每一单位产品需要每条生产线多少生产能力3、每种产品的单位利润是多少生产部门和财务部门经过分析，提出如下数据：模型：1、要做出什么决策（决策变量）2、做出的决策会有哪些条件限制（约束条件）3、这些决策的全部评价标准是什么（目标函数）max z=3x1+5x2st. x1<=42x2<=123x1+2x2<=18x1,x2>=0决策：x1=2,x2=6, z=3600生产时间信息：按模型所确定的生产方案需要生产线2和3的所有时间，只有生产线1有2小时的剩余。

1、用单纯形表求解以下线性规划问题（1）max z=x1-2x2+x3.x1+x2+x3≤122x1+x2-x3≤6-x1+3x2≤9x1,x2,x3≥0解：标准化，将目标函数转变成极小化，引进松弛变量x4,x5,x60,得到：z’min-x1+2x2-x3=.x1+x2+x3+x4=122x1+x2-x3+x5= 6-x1+3x2+x6= 9x1,x2,x3,x4,x5,x6≥0列出初始单纯形表z’x1x2x3x4x5x6RHSz’x412/1x5--x6--选取x3为进基变量，确定x4为离基变量z’x1x2x3x4x5x6RHSz’x312/1x518/3x6--得到最优解（x1, x2, x3, x4, x5, x6）=（0, 0, 12, 0, 18, 9），min z’=-12，max z=12由于其中非基变量x1在目标函数中的系数为0，x1进基，x5离基，可以得到另一最优解：z’x1x2x3x4x5x6RHSz’x3x1x6新的最优解为（x1,x2,x3,x4,x5,x6）=（6, 0, 6, 0, 0, 15），min z’=-12，max z=12原问题最优解的全体为：x x x x x x 123456001201891606001566066018156⎡⎣⎢⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎥=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎥+-⎡⎣⎢⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎥=-+-⎡⎣⎢⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎥λλλλλλ()，（0≤≤1），都有max z=12（2） max z= x 1 +3x 2 +4x 3. 3x 1 +2x 2 ≤13 x 2 +3x 3 ≤172x 1 +x 2 +x 3 =13x 1,x 2,x 3≥0解：将目标函数转化成极小化，引进松弛变量x 4，x 5，x 6≥0，得到min z’= -x 1 -3x 2 -4x 3. 3x 1 +2x 2 +x 4 =13 x 2 +3x 3 +x 5 =17 2x 1 +x 2 +x 3 =13x 1,x 2,x 3,x 4,x 5,≥0引进人工变量x 60，构造辅助问题：minz’’= x 6. 3x 1 +2x 2 +x 4 =13 x 2 +3x 3 +x 5 =172x 1+x 2+x 3+x 6=13x1,x2,x3,x4,x5,x6≥0列出辅助问题的系数矩阵表：z’x1x2x3x4x5x6RHS’z’’x4x5x6消去基变量x6在目标函数中的系数，并开始单纯形叠代：z’x1x2x3x4x5x6RHS’z’’x413/3 x5--x613/2 x1进基，x4离基，z’x1x2x3x4x5x6RHS’z’’x1--x517/3x613/3 x3进基，x6离基，z’x1x2x3x4x5x6RHS’z’’x1x5x3辅助问题已经获得最优解，且min z’’=0，因而可以转入第二阶段，其系数矩阵表为：z’x1x2x3x4x5RHSz’x1x5x3消去基变量x1，x3在目标函数中的系数：z’x1x2x3x4x5RHSz’x113/2x54/2x3--x2进基，x5离基z’x1x2x3x4x5RHSz’x1x2x3得到原问题的最优解：（x1, x2, x3）=（3, 2, 5），min z’=-29，max z=293、用对偶单纯形法求解以下问题(1)min z=4x1+6x2+18x3.x1+3x3≥3x2+2x3≥5x1,x2,x3≥0引进松弛变量x4、x5≥0min z=4x1+6x2+18x3.-x1-3x3+x4=-3-x2-2x3+x5=-5x1,x2,x3，x4，x5≥0列出单纯形表zx4x54/118/3x 4离基，x 1进基z x 1 x 56/16/2x 5离基，x 3进基z x 1x 324x 1离基，x 2进基z x 2 x 3最优解为x 1=0，x 2=3，x 3=1，x 4=0，x 5=0，min z=36某工厂用甲、乙、丙三种原料生产A,B,C,D 四种产品，每种产品消耗原料定额以及（1） 求使总利润最大的生产计划和按最优生产计划生产时三种原料的耗用量和剩余量；（2） 求四种产品的利润在什么范围内变化，最优生产计划不会变化 （3） 求三种原料的影子价格和四种产品的机会成本，并解释最优生产计划中有的产品不安排生产的原因。

（4） 在最优生产计划下，哪一种原料更为紧缺如果甲原料增加120吨，这时紧缺程度是否有变化(1)利润最大化的线性规划模型为： max z= 25x 1 +12x 2 +14x 3 +15x 4 . 3x 1 +2x 2+x 3 +4x 4 ≤2400 2x 1 +2x 3+3x 4 ≤3200 x 1 +3x 2 +2x 4 ≤1800x 1,x 2,x 3,x 4≥0单纯形表为： z x 1 x 2 x 3 x 4 x 5 x 6 x 7 RHS zx 5 x 6 x 7x 1进基，x 5离基 z x 1 x 2 x 3x 4x 5 x 6 x 7 RHS zx 1 x 6x7x3进基，x6离基z x1x2x3x4x5x6x7RHS Arrayzx1x3x7x2进基，x1离基z x1x2x3x4x5x6x7RHSzx2x3x7最优解为：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+-12 -14 -15 0 0 0 0z x 1 x 2 x 3 x 4 x 5 x 6 x 7 RHS -C B z 1 -1- 0 0 -21 -6 -4 0 -27200 -12 x 2 0 1 1 0 5/4 1/2 -1/4 0 400 -14 x 3 0 1 0 1 3/21/2 0 1600 0x 7-2-7/4 -3/23/41600-1-≤0，≥-1，-c 1’=-c 1+≥-25-1=-26，即c 1≤26（万元/万件） 产品B 利润变化范围：-C-25-12+-14-15z x 1 x 2 x 3 x 4 x 5 x 6 x 7 RHS -C Bz1-1--21+5/4-6+1/2-4-1/4 0-27200+400-12+x 2115/41/2-1/40 400-14 x 3 0 1 0 1 3/2 0 1/2 0 1600 0x 7-2-7/4-3/23/41600--≤-+≤-+≤--≤⎧⎨⎪⎪⎩⎪⎪102154061204140δδδδ///，δδδδ≥-≤≤≥-⎧⎨⎪⎪⎩⎪⎪18451216/，-1≤≤12，-13≤-12+≤0，-13≤-c 2’≤0， 即：0≤c 2’≤13。

产品C 利润的变化范围：-C-25-12-14+-15zx 1x 2x 3x 4x 5x 6x 7RHS-C B z 1 -1-0 0 -21+3/2-6 -4+1/20 -27200+1600-12 x 2 0 1 1 0 5/4 1/2 -1/4 0 400 -14+x 3113/21/21600x 7 0 -2 0 0 -7/4 -3/2 3/4 1 600--≤-+≤-+≤⎧⎨⎪⎩⎪10213204120δδδ//，δδδ≥-≤≤⎧⎨⎪⎩⎪1148 -1≤≤8，-15≤-14+≤-6，-15≤-c 3’≤-6，6≤c 3’≤15 产品D 的变化范围-C-25-12-14-15+z x 1 x 2 x 3 x 4 x 5 x 6 x 7 RHS -C Bz1-1-21--6-4-27200-12 x 2 0 1 1 0 5/4 1/2 -1/4 0 400 -14 x 3 0 1 0 1 3/2 0 1/2 0 1600 0x 7-2-7/4-3/23/41600-21-≤0，≥-21，-15+≥-36，-c 4’≥-36，c 4’≤36。

（3） 求三种原料的影子价格和四种产品的机会成本 由最优单纯形表可知，原料甲、乙、丙的影子价格分别为：6万元/吨、4万元/吨、0万元/吨。

产品A 、B 、C 、D 的机会成本分别为：26万元/万件、12万元/万件、14万元/万件、36万元/万件。

产品A 、D 在最优解中不安排生产的原因是机会成本大于利润。

（4） 在最优解中，原料甲的影子价格（6万元/吨）最大，因此这种原料最紧缺。

如果原料A 增加120吨，最优单纯形表的右边常数成为：B b -'=--⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥+⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥=⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥+-⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥=⎡⎣⎢⎢⎢⎤⎦⎥⎥⎥≥11214001203234124001203200180040016006006000180100016004200///// 因此最优基保持不变，影子价格不变，原料的紧缺程度不变。

一、以下集合中，哪些是凸集，哪些不是凸集（1） {(x 1,x 2)| x 1+x 2≤1}是凸集 （2） {(x 1,x 2,x 3)| x 1+x 2≤1,x 1-x 3≤2} 是凸集 （3） {(x 1,x 2)| x 1-x 2=0}是凸集（4） {(x 1,x 2,x 3)| x 1≥x 2,x 1+x 2+x 3≤6} 是凸集 （5） {(x 1,x 2)| x 1=1,|x 2|≤4}是凸集 （6） (x 1,x 2,x 3)| x 3=|x 2|, x 1≤4}不是凸集。