1-5 单纯形法的进一步讨论

1、1.5 单纯形法的进一步讨论,一、人工变量法（大M法） 约束条件： “” 减一个剩余变量后，再加一个人工变量 “” 加一个人工变量 目标函数： 人工变量的系数为“M”，即罚因子 若线性规划问题有最优解则人工变量必为0。,大M法,在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数的取值无影响，为此可取人工变量在目标函数中的系数为-M(M为非常大的正数)，这样目标函数要实现最大化，人工变量只能取零，因此必须把人工变量从基变量中换出，否则目标函数就不可能实现最大化。,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2

2、,3,增加人工变量后，线性规划问题中就存在一个B为单位矩阵， 后面可以根据我们前面所讲的单纯形法来进行求解。,MaxZ=-3x1+x3-Mx6-Mx7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7,标准化及变形,单纯形表,j,-3-2M,4M,1,0,0, ,3,x2入，x6出,-M,0,4,1, ,j,6M-3,0,4M+1,0,-4M, ,-,x1入，x7出,3M,0,1,1, ,j,0,0,3,0,-M-3/2, ,9,x3入，x1出,3/2,-M+1/2,3/2,-, ,j,-9/2,0,0,0,-M+3/

3、4,-3/4,-M-1/4,所以：X*=(x2,x3,x4)T=(5/2,3/2,0)T Z*=3/2,2、 两阶段法,由于大M法在使用电子计算机求解时，只能用很大的数代替M，这就可能造成计算上的出错。故下面介绍两阶段法。,二、两阶段法 第一阶段暂不考虑原问题是否存在基可行解，给原问题加入人工变量，并构建一个仅含人工变量的目标函数（求极小化），人工变量的价值系数一般为1，约束条件和原问题的一样。 当第一阶段中目标函数的最优值0，既人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，既人工变量不等于0，则判断原问题为无解。 第二阶段：将第一阶段计算所得的单纯形表划去人工变量所在的列

4、，并将目标函数换为原问题的目标函数作为第二阶段的初始单纯形表，进行进一步的求解。,求解辅助问题，得到辅助问题的最优解,引进人工变量x6，x7，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化,MaxW=0?,原问题没有可行解。,把辅助问题的最优解作为原问题的初始基础可行解,用单纯形法求解原问题，得到原问题的最优解,否,是,两阶段法的算法流程图,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,MaxW=-x6-x7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7

5、=9 xi 0,j=1,7,(第一阶段）单纯形表1,j,-2,4,0,0,0, ,3,x2入，x6出,-1,0,4,1, ,j,6,0,4,0,-4, ,x1入，x7出,3,0,1,1, ,j,0,0,0,0,-1,0,-1,所以：已得最优解，且人工变量为非基变量，则可去掉人工变量，得原问题的一个即可行基。,（第二阶段）单纯形表2,j,0,0,3,0,3/2, ,-,9,3/2, ,x3入，x1出,j,-9/2,0,0,0,-3/4,所以：X*=(x2,x3,x4)T=(5/2,3/2,0)T Z*=3/2,目标函数极大化时解的最优性判别； 退化解的判别； 无可行解的判别； 无界的判别； 无穷

6、多最优解的判别； 唯一最优解的判别.,三、单纯形法计算中的几个问题,当所有非基变量的j0时为最优解；,最优解中基变量有取值为0的值时；,最优解中人工变量为非0的基变量时；,存在某个k0，且所有的aik0时；,得最优解时，有检验数为0的非基变量；,得最优解时，所有非基变量检验数为负；,j,40,45,0,25,100/3,40, 3 ,x2入，x3出,j,0,0,0,-5,因为j全0,且1=0,则有无穷多最优解。 所以：X*=(0,80/3,20,0,0),Z*=1700,例:,0,-10,j,1,1,0,0,-,50, ,x1入，x4出,j,0,2,0,-1,因为2=2,且ai2全0所以：无界

7、,例:,例:,下表为一极大化问题对应的单纯形表,讨论在a1,a2,a3,a4,a5,a6取何值的情况下，该表中的解为： 唯一最优解； 无穷多最优解； 退化解； 无界； 无可行解； X3换入，x2换出,A40,a20, a30 a40,a50, x4或x2为人工变量，a60 ；x1为人工变量a60 A40,a4a5;a6/a12a10 a60 a1 0,设有线性规划,其中Amn且r(A)=m,X0应理解为X大于等于零向量，即xj0,j=1,2,n。,单纯形法矩阵向量描述,不妨假设A（P1，P2，Pn）中前m个列向量构成一个可行基，记为B=(P1，P2，Pm)。矩阵A中后nm列构成的矩阵记为N（P

8、m+1,Pn）,则A可以写成分块矩阵A=（B，N）。对于基B，基变量为XB=（x1,x2，xm ）T, 非基变量为XN=(xm+1,xm+2,xn)T。,则X可表示成 同理将C写成分块矩阵C=（CB，CN），,CB=(C1,C2,Cm), CN=(Cm+1Cm+2，cn) 则AX=b可写成,因为r（B）=m（或|B|0）所以B 1存在，因此可有,令非基变量XN=0，XB=B1b，由 B是 可行基的假设，则得到基本可行解,X=(B1b，0)T,将目标函数写成,得到下列五个计算公式：,(令XN=0),非基变量,基变量,max,B,N,I,I,B-1b,非基变量,基变量=CBB-1B-CB=0,ma

9、x,max,基变量在目标函数中的系数等于0， 基变量在约束条件中的系数是一个单位矩阵,单纯形表的结构和性质,注意： Z行中有m 个0，它们与基变量相对应。一般情况下，这m个0分散在Z行的各列中，并与基变量相对应。 其余m行中有一个m阶单位矩阵I，其各列与基变量相对应。一般情况下，组成I的各列分散在表的各列中，它们与基变量相对应。,单纯形表的结构,上述公式可用下面较简单的矩阵表格运算得到，设初始矩阵单纯形表1-15,将B化为I（I为m阶单位矩阵）,CB化为零,即求基本可行解和检验数。用B1左乘表中第二行,得到表1-16,表115,表116,再将第二行左乘CB后加到第三行,得到,XB,Z0,表11

10、7,五个公式的应用,【例1.24】线性规划,已知可行基,求(1)单纯形乘子; (2)基可行解及目标值; (3)求3; (4)B1是否是最优基,为什么;,(5)当可行基为 时求1及3。,【解】(1)因为B1由A中第一列、第二列组成,故x1、x2为基变量，x3、x4、x5为非基变量,有关矩阵为,CB=(c1,c2)=(1,2) CN=(c3,c4,c5)=(1,0,0),故单纯形乘子,(2)基变量的解为,故基本可行解为,目标函数值为,(3) 求3,(4) 要判断B1是不是最优基,亦是要求出所有检验数则否满足j0,j=1,5。x1,x2是基变量,故1=0,2=0,而 剩下来求4,5，由N计算公式得,因j0, j=1,5,故B1是最优基。,(5) 因B2是A中第四列与第二列组成的,x4、x2是基变量x1、x3、x5是非基变量,这时有,即,【例1.26】求解线性规划,解 用大M单纯形法，加入人工变量x4、x5，构造数学模型,1.5.4 退化与循环,表118,单纯形法迭代对于