3.4单纯形法的进一步讨论(用人工变量法找初始可行基）二、大M法大M法：引入人工变量xn+i≥0（i=1,…,m）及充分大正数M。得到：Maxz=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2...am1x1+am2x2+…+amnxn+xn+m=bmx1，x2，…，xn，xn+1，…，xn+m≥0显然，xj=0j=1,…,n;xn+i=bii=1,…,m是基本可行解。对应的基是单位矩阵。结论：若得到的最优解满足xn+i=0i=1,…,m则是原问题的最优解；否则，原问题无可行解。Maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0大M法（LP-M）（一）两阶段法Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2...am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥0两阶段法：引入人工变量xn+i≥0，i=1,…,m；构造:Maxz=-xn+1-xn+2-…-xn+ms.t.a11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2...am1x1+am2x2+…+amnxn+xn+m=bmx1,x2...xn,xn+1,…,xn+m≥0第一阶段求解上述问题：显然，xj=0j=1,…,n;xn+i=bii=1,…,m是基本可行解,它对应的基是单位矩阵。例：（LP）Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20x1+2x2+4x3+x4=26x1,x2,x3,x4≥0第一阶段问题（LP-1）Maxz=-x5-x6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x6≥0第一阶段(LP-1）第二阶段把基本可行解填入表中注意：单纯形法中1、每一步运算只能用矩阵初等行变换；2、表中第3列(b列)的数总应保持非负（≥0）；3、当所有检验数均非正（≤0）时，得到最优单纯形表；4、当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解；5、如最后表中人工变量不出基，则原问题无最优解。