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

1、课后练习（一）,1 用图解法求下列线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界界还是无可行解。,无可行解,X*=(10, 6),无界解,无穷多最优解,唯一解,1,2、将下述线性规划问题化成标准形式,解：,2,3 对下述线性规划问题找出所有基解，指出那些是基可行 解，并确定最优值。,关键：判断2个列向量线性相关性，若线性无关，则成为基,3,p1 p2 p3 p4,4,4、已知线性规划问题 :,下表中所列的解均满足约束条件1-3，试指出表中哪些是可行解，哪些是基解，哪些是基可行解。,12 34,5,p1 p2 p3 p4 p5,是基,是基,是基,基解有(a), (b), (f); 基

2、可行解有(a) (f).,可行解有(a), (c), (e), (f);,6,5 已知某线性规划问题的约束条件为,判断下列各点是否为该线性规划问题可行域上的顶点：,7,不是基，故,不是基解，更不可能是基可行解,为非可行域上的点，故不是,8,不是基，故,不是基解，更不可能是基可行解,9,课后练习（二）,1、分别用图解法和单纯形法求解下述线性规划问题，并指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点,10,0 10 5 0 0,11,同理： （2） X*=(3.5, 1.5, 7.5, 0, 0) Z*=8.5,12,2 用单纯形法求解下列线性规划问题,13,14,15,同理： （2）为

3、无界解,16,3 用单纯形法中的大M法求解下列线性规划问题，并指出属那一类解,化为标准式有,17,x1 x2 x3 x4 x5 x6 x7,-2 -3 -1 0 0 -M -M,8 1 4 2 -1 0 1 0,0 -2 -3 -1 0 0 -M -M,6 3 2 0 0 -1 0 1,x1 x2 x3 x4 x5 x6 x7,-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,6 3 2 0 0 -1 0 1,18,x1 x2 x3 x4 x5 x6 x7,-2 -3 -1 0 0 -M -M,8 1 4 2 -1

4、 0 1 0,14M 4M-2 6M-3 2M-1 -M -M 0 0,6 3 2 0 0 -1 0 1,2 3,x1 x2 x3 x4 x5 x6 x7,-2 -3 -1 0 0 -M -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,19,x1 x2 x3 x4 x5 x6 x7,-2 -3 -1 0 0 -M -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,x1 x2 x3 x4 x5 x6 x7,-2 -3 -1 0 0 -M -M,9/5 0 1

5、3/5 -3/10 1/10 3/10 -1/10,4/5 1 0 -2/5 1/5 -2/5 -1/5 2/5,20,4、求解线性规划问题当某一变量的取值无约束时，通常用 来替换，其中 ， 。试说明，能否在基变量中同时出现，为什么？,21,5、 下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 约束形式为 x3、x4为松弛变量，表中解代入目标函数后得Z=10,ag的值 表中给出的解是否为最优解,22,因为目标函数值为10，而Z=5x1+3x2,由单纯形表可知x1=a, x2=0， 故a = 2,因为x1、x2为基变量，所以因当满足高斯消元的形式(proper form from

6、 Gaussian elimination), 故c=0, d=1, b=0; f=0,由检验数的定义可知：,13 （00 e5） e=4/5,g=0（01/515） g=5,23,a=2, b=0, c=0, d=1, e=4/5, f=0, g=-5,由于所有检验非正，故该解是最优解 这个表格为最终单纯形表,综上所述：,24,6、已知某线性规划问题的初始单纯形表和用单纯刑法迭代后得到的表如下所示，试求括弧中未知数al的值,X1 X2 X3 X4 X5,X4 X5,6 1,(b) (c) (d) 1 0,-1 3 (e) 0 1,X1 X5,(f) 4,(g) 2 -1 1/2 0,(h)

7、(i) 1 1/2 1,(a)-12 0 0,0 -7 (j)(k) (l),25,首先由于x1、x5为基变量，故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,26,又有,f=3,还剩下检验数 a、j、k,检验数的定义为,如何求得c呢？,27,对初始单纯形表的检验数行即为目标函数中的系数C。,对迭代后的单纯形表有：,a=c1=3,至此我们已获得所有的目标函数的系数,j=2（3101）5,k=0（31/201/2）3/2,28,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,综上所述：,29,7、设 是线性规划问题 的最优解。若目标函数中用 代替 C后，问题的最 优解变为,求证：,证明：因为,（1）,（2）,将（2）（1）有,30,某厂生产I、II、III三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1、B2、B3三种设备可用于完成B工序。 已知产品I可在A、B任何一种设备上加工； 产品II可在任何规格的A设备上加工，但完成B工序时， 只能在B1设备上加工； 产品III只能在A2和B2设备上加工。,31,32,产品I有6种加工方案（A1, B1）、(A1，B2)、(A1，