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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,解答 运筹学 第一章 线性规划及其单纯形法习题,3,对下述线性规划问题找出所有基解，指出那些是基可行,解，并确定最优值。,关键：判断,2,个列向量线性相关性，若线性无关，则成为基,序号,向量组,是否线性无关,是否为基,1,p1 p2,2,p1 p3,3,p1 p4,4,p2 p3,5,p2 p4,6,p3 p4,p,1,p,2,p,3,p,4,序号,基,基解,是否为基可行解,1,p1 p2,(-4,11/2,0,0),2,p1 p3,(2/5,0,11/5,0),3,p1 p4,(-1/3,0,0,11/6),4,p2 p3,(0,1/2,2,0),5,p2 p4,(0,-1/2,0,2),6,p3 p4,(0,0,1,1),4,、已知线性规划问题,:,序号,X1,X2,X3,X4,X5,A,2,4,3,0,0,B,10,0,-5,0,4,C,3,0,2,7,4,D,1,4.5,4,0,-0.5,E,0,2,5,6,2,F,0,4,5,2,0,下表中所列的解均满足约束条件,1-3,，试指出表中哪些是可行解，哪些是基解，哪些是基可行解。,12,34,p,1,p,2,p,3,p,4,p,5,是基,是基,是基,基解有,(a),(b),(f);,基可行解有,(a)(f).,可行解有,(a),(c),(e),(f);,5,已知某线性规划问题的约束条件为,判断下列各点是否为该线性规划问题可行域上的顶点：,不是基，故,不是基解，更不可能是基可行解,是基，故,是基解,又由于其每个分量非负，故为基可行解,为非可行域上的点，故不是,不是基，故,不是基解，更不可能是基可行解,课后练习（二）,1,、分别用图解法和单纯形法求解下述线性规划问题，并指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,10,5,0,0,9,3,4,1,0,8,5,2,0,1,x,3,x,4,0,0,9/3=3,8/5,0 10 5 0 0,检验数,j,8/5,1,2/5,0,1/5,21/5,0,14/5,1,-3/5,-80/5,0,1,0,-2,x,3,x,1,0,10,3/2,4,检验数,j,3/2,0,1,5/14,-3/14,x,2,x,1,5,10,1,1,0,-1/7,2/7,-175/10,0,0,-5/14,-25/14,同理：,（,2,）,X*=(3.5,1.5,7.5,0,0)Z*=8.5,2,用单纯形法求解下列线性规划问题,C,j,比,值,C,B,X,B,b,检验数,j,2,-1,1,0,0,0,x,1,x,2,x,3,x,4,x,5,x,6,60,3,1,1,1,0,0,10,1,-1,2,0,1,0,20,1,1,-1,0,0,1,x,4,x,5,x,6,0,0,0,0,2,-1,1,0,0,0,60/3=20,10/1=10,20/1=20,检验数,j,x,4,x,1,x,6,0,2,0,10,1,-1,2,0,1,0,30,0,4,-5,1,-3,0,10,0,2,-3,0,-1,1,-20,0,1,-3,0,-2,0,30/4=7.5,-,10/2=5,检验数,j,x,4,x,1,x,6,0,2,0,10,1,-1,2,0,1,0,30,0,4,-5,1,-3,0,10,0,2,-3,0,-1,1,-20,0,1,-3,0,-2,0,30/4=7.5,-,10/2=5,检验数,j,5,0,1,-3/2,0,-1/2,1/2,x,4,x,1,x,2,0,2,-1,15,1,0,1/2,0,1/2,1/2,10,0,0,1,1,-1,-2,-25,0,0,-3/2,0,-3/2,-1/2,同理：,（,2,）为无界解,3,用单纯形法中的大,M,法求解下列线性规划问题，并指出属那一类解,化为标准式有,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,8 1 4 2 -1 0 1 0,0 -2 -3 -1 0 0 -M -M,x,6,x,7,-M,-M,6 3 2 0 0 -1 0 1,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,8 1 4 2 -1 0 1 0,14M 4M-2 6M-3 2M-1-M -M 0 0,x,6,x,7,-M,-M,6 3 2 0 0 -1 0 1,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,8 1 4 2 -1 0 1 0,14M 4M-2 6M-3 2M-1-M -M 0 0,x,6,x,7,-M,-M,6 3 2 0 0 -1 0 1,2,3,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,x,2,x,7,-3,-M,2 1/4 1 1/2 -1/4 0 1/4 0,2 5/2 0 -1 1/2 -1 -1/2 1,8,4/5,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,x,2,x,7,-3,-M,2 1/4 1 1/2 -1/4 0 1/4 0,2 5/2 0 -1 1/2 -1 -1/2 1,8,4/5,C,j,比,值,C,B,X,B,b,检验数,j,x,1,x,2,x,3,x,4,x,5,x,6,x,7,-2 -3 -1 0,0,-M,-M,x,2,x,1,-3,-2,9/5 0 1,3/5-3/10 1/10 3/10 -1/10,4/5 1 0 -2/5 1/5-2/5 -1/5 2/5,4,、求解线性规划问题当某一变量的取值无约束时，通常用 来替换，其中 ，。试说明，能否在基变量中同时出现，为什么？,不可能,。因为,故,5,、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 约束形式为,x,3,、,x,4,为松弛变量，表中解代入目标函数后得,Z=10,X,1,X,2,X,3,x,4,X,3,2,X,1,a,c,d,0,e,1,0,1/5,1,C,j,-Z,j,b,-1,f,g,ag,的值,表中给出的解是否为最优解,因为目标函数值为,10,，而,Z=5x,1,+3x,2,由单纯形表可知,x,1,=a,x,2,=0,，故,a=2,因为,x1,、,x2,为基变量，所以因当满足高斯消元的形式,(proper form from Gaussian elimination),故,c=0,d=1,b=0;f=0,由检验数的定义可知：,1,3,（,00,e5,）,e=4/5,g=0,（,01/5,15,）,g=,5,a=2,b=0,c=0,d=1,e=4/5,f=0,g=-5,由于所有检验非正，故该解是最优解,这个表格为最终单纯形表,综上所述：,6,、已知某线性规划问题的初始单纯形表和用单纯刑法迭代后得到的表如下所示，试求括弧中未知数,al,的值,项目,C,j,-Z,J,X,1,X,2,X,3,X,4,X,5,X,4,X,5,6,1,(b)(c)(d)1 0,-1 3 (e)0 1,C,j,-Z,J,X,1,X,5,(f),4,(g)2 -1 1/2 0,(h)(i)1 1/2 1,(a)-12 0 0,0-7(j)(k)(l),首先由于,x,1,、,x,5,为基变量，故,g=1,h=0,l=0,再有,那么,b=1,c=2,d=-1,c+3=i,d+e=1,b=2,c=4,d=-2,i=5,e=2,又有,f=3,还剩下检验数,a,、,j,、,k,检验数的定义为,如何求得,c,呢？,对初始单纯形表的检验数行即为目标函数中的系数,C,。,对迭代后的单纯形表有：,a=c1=3,至此我们已获得所有的目标函数的系数,j=2,（,3,1,01,）,5,k=0,（,31/2,01/2,）,3/2,a=3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=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,III,A1,5,10,6000,0.05,A2,7,9,12,10000,0.03,B1,6,8,4000,0.06,B2,4,11,7000,0.11,B3,7,4000,0.05,原料费,0.25,0.35,0.50,售价,1.25,2.00,2.80,设备,产品,设备有效台时,设备加工费,I,II,III,A1,5,10,6000,0.05,A2,7,9,12,10000,0.03,B1,6,8,4000,0.06,B2,4,11,7000,0.11,B3,7,4000,0.05,原料费,0.25,0.35,0.50,售价,1.25,2.00,2.80,产品,I,有,6,种加工方案（,A1,B1,）、,(A1,，,B2),、,(A1,，,B3),（,A2,B1,）、,(A2,，,B2),、,(A2,，,B3),其各自产量分别用,设备,产品,设备有效台时,设备加工费,I,II,III,A1,5,10,6000,0.05,A2,7,9,12,10000,0.03,B1,6,8,4000,0.06,B2,4,11,7000,0.11,B3,7,4000,0.05,原料费,0.25,0.35,0.50,售价,1.25,2.00,2.80,产品,II,有,6,种加工方案（,A1,B1,）、,(A2,，,B1),其各自产量分别用 代表,设备,产品,设备有效台时,设备加工费,I,II,III,A1,5,10,6000,0.05,A2,7,9,12,10000,0.03,B1,6,8,4000,0.06,B2,4,11,7000,0.11,B3,7,4000,0.05,原料费,0.25,0.35,0.50,售价,1.25,2.00,2.80,产品,III,只有,1,种加工方案（,A2,B2,）,其各自产量用 代表,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,