解答-运筹学-第一章-线性规划及其单纯形法习题.ppt

课后练习（一）1 用图解法求下列线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界界还是无可行解。无可行解X*=(10,6)无界解无穷多最优解唯一解.2、将下述线性规划问题化成标准形式解：.3 对下述线性规划问题找出所有基解，指出那些是基可行解，并确定最优值。关键：判断2个列向量线性相关性，若线性无关，则成为基.序号向量组是否线性无关是否为基1p1 p22p1 p33p1 p44p2 p35p2 p46p3 p4p1 p2 p3 p4序号基基解是否为基可行解1p1 p2(-4,11/2,0,0)2p1 p3(2/5,0,11/5,0)3p1 p4(-1/3,0,0,11/6)4p2 p3(0,1/2,2,0)5p2 p4(0,-1/2,0,2)6p3 p4(0,0,1,1).4、已知线性规划问题:序号X1X2X3X4X5A24300B100-504C30274D14.540-0.5E02562F04520下表中所列的解均满足约束条件1-3，试指出表中哪些是可行解，哪些是基解，哪些是基可行解。1234.p1 p2 p3 p4 p5是基是基是基基解有(a),(b),(f);基可行解有(a)(f).可行解有(a),(c),(e),(f);.5 已知某线性规划问题的约束条件为 判断下列各点是否为该线性规划问题可行域上的顶点：.不是基，故不是基解，更不可能是基可行解是基，故是基解又由于其每个分量非负，故为基可行解为非可行域上的点，故不是.不是基，故不是基解，更不可能是基可行解.课后练习（二）1、分别用图解法和单纯形法求解下述线性规划问题，并指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点.Cj比值CBXBb检验数jx1x2x3x4105009341085201x3x4009/3=38/5 0 10 5 0 0检验数检验数 j8/512/501/521/5014/51-3/5-80/5 010-2x3x10103/24检验数检验数 j3/2015/14-3/14x2x1510110-1/72/7-175/1000-5/14-25/14.同理：（2）X*=(3.5,1.5,7.5,0,0)Z*=8.5.2 用单纯形法求解下列线性规划问题.Cj比比值值CBXBb检验数检验数 j2-11000 x1x2x3x4x5x660311100101-120102011-1001x4x5x600002-1100060/3=2010/1=1020/1=20检验数检验数 jx4x1x6020101-120103004-51-301002-30-11-2001-30-2030/4=7.5-10/2=5.检验数检验数 jx4x1x6020101-120103004-51-301002-30-11-2001-30-2030/4=7.5-10/2=5检验数检验数 j501-3/20-1/21/2x4x1x202-115101/201/21/2100011-1-2-2500-3/20-3/2-1/2.同理：（2）为无界解.3 用单纯形法中的大M法求解下列线性规划问题，并指出属那一类解化为标准式有.Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -M8 1 4 2 -1 0 1 00 -2 -3 -1 0 0 -M -Mx6x7-M-M6 3 2 0 0 -1 0 1Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -M8 1 4 2 -1 0 1 014M 4M-2 6M-3 2M-1-M -M 0 0 x6x7-M-M6 3 2 0 0 -1 0 1.Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -M8 1 4 2 -1 0 1 014M 4M-2 6M-3 2M-1-M -M 0 0 x6x7-M-M6 3 2 0 0 -1 0 123Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -Mx2x7-3-M2 1/4 1 1/2 -1/4 0 1/4 02 5/2 0 -1 1/2 -1 -1/2 184/5.Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -Mx2x7-3-M2 1/4 1 1/2 -1/4 0 1/4 02 5/2 0 -1 1/2 -1 -1/2 184/5Cj比值CBXBb检验数jx1 x2 x3 x4 x5 x6 x7-2 -3 -1 0 0 -M -Mx2x1-3-29/5 0 1 3/5-3/10 1/10 3/10 -1/104/5 1 0 -2/5 1/5-2/5 -1/5 2/5.4、求解线性规划问题当某一变量的取值无约束时，通常用 来替换，其中 ，。试说明，能否在基变量中同时出现，为什么？不可能。因为故.5、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 约束形式为 x3、x4为松弛变量，表中解代入目标函数后得Z=10X1X2X3x4X3 2X1 acd0e101/51Cj-Zjb-1fg(1)ag的值(2)表中给出的解是否为最优解.因为目标函数值为10，而Z=5x1+3x2,由单纯形表可知x1=a,x2=0，故a=2因为x1、x2为基变量，所以因当满足高斯消元的形式(proper form from Gaussian elimination),故c=0,d=1,b=0;f=0由检验数的定义可知：13（00 e5）e=4/5 g=0（01/515）g=5.a=2,b=0,c=0,d=1,e=4/5,f=0,g=-5由于所有检验非正，故该解是最优解这个表格为最终单纯形表综上所述：.6、已知某线性规划问题的初始单纯形表和用单纯刑法迭代后得到的表如下所示，试求括弧中未知数al的值项目Cj-ZJX1 X2 X3 X4 X5X4X561(b)(c)(d)1 0-1 3 (e)0 1Cj-ZJX1X5(f)4(g)2 -1 1/2 0(h)(i)1 1/2 1(a)-12 0 00-7(j)(k)(l).首先由于x1、x5为基变量，故g=1,h=0,l=0再有那么 b=1 c=2 d=-1 c+3=i d+e=1b=2c=4d=-2i=5e=2.又有f=3还剩下检验数 a、j、k检验数的定义为如何求得c呢？.对初始单纯形表的检验数行即为目标函数中的系数C。对迭代后的单纯形表有：a=c1=3至此我们已获得所有的目标函数的系数j=2（3101）5k=0（31/201/2）3/2.a=3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0i=5,j=5,k=-3/2,l=0综上所述：.7、设 是线性规划问题的最优解。若目标函数中用 代替 C后，问题的最优解变为 求证：证明：因为（1）（2）将（2）（1）有.某厂生产I、II、III三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品产品I可在A、B任何一种设备上加工；产品产品II可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品产品III只能在A2和B2设备上加工。.设备产品设备有效台时设备加工费 I II IIIA151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料费0.250.350.50售价1.252.002.80.设备产品设备有效台时设备加工费 I II IIIA151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料费0.250.350.50售价1.252.002.80产品I有6种加工方案（A1,B1）、(A1，B2)、(A1，B3)（A2,B1）、(A2，B2)、(A2，B3)其各自产量分别用.设备产品设备有效台时设备加工费 I II IIIA151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料费0.250.350.50售价1.252.002.80产品II有6种加工方案（A1,B1）、(A2，B1)其各自产量分别用 代表.设备产品设备有效台时设备加工费 I II IIIA151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料费0.250.350.50售价1.252.002.80产品III只有1种加工方案（A2,B2）其各自产量用 代表.