(精品)运筹学大M法和两阶段法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二节,大,M,法和两阶段法,如果线性规划模型中约束条件系数矩阵中不存在单位向量组，解题时应先加入人工变量，人工地构成一个单位向量组。,人工变量只起过渡作用，不应影响决策变量的取值。,两种方法可控制人工变量取值。,大,M,法,两阶段法,例,解：引入松弛变量,x,4,、剩余变量,x,5,，将数学模型标准化,观察约束条件系数矩阵,A,A,矩阵不存在完全单位向量组。,应人工地构建一个完全单位向量组。,人为增加两列,相当于又加入两个变量,x,6,、,x,7,调整后的,A,矩阵还原成约束条件为：,由于加入的两个变量只起辅助计算的作用，不能影响目标函数和约束条件，因此它的取值只能是,0,。,两种方法可控制人工变量的取值,大,M,法,两阶段法,一、大,M,法,原理：,引入一个非常大的正数,M,，,用来制约人工变量的取值，并使目标函数变为：,这样，如果计算结果,x,t,0,，,那么由于,M,是一个非常大的正数，可以使得,F0,，,也就是使,F,无法达到最大值。所以，,M,也被称为罚金系数，这种方法称为大,M,法。,例：加入人工变量,x,6,，,x,7,后,，原模型变为,：,用单纯形法求解,此时，各系数矩阵、向量为：,段,Cj,0,3,-1,-1,0,0,-M,-M,i,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,-M,x,6,3,-4,1,2,0,-1,1,0,-M,x,7,1,-2,0,1,0,0,0,1,Cj-Zj,初始表,段,Cj,0,3,-1,-1,0,0,-M,-M,i,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,-M,x,6,3,-4,1,2,0,-1,1,0,-M,x,7,1,-2,0,1,0,0,0,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,检验数判断,检验数,Cj-Zj,=,aM+b,：,当,a0,时，认为检验数为正。,若最终检验数,Zj-Cj,均为非正，而,b,列中对应的检验数,Cb-Zb,（,即最优值）中仍有,M,存在，说明没有得到确定的最优值，可以解释为约束条件过于苛刻，该线性规划问题无可行解。,段,Cj,0,3,-1,-1,0,0,-M,-M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,11,-M,x,6,3,-4,1,2,0,-1,1,0,3/2,-M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,段,Cj,0,3,-1,-1,0,0,-M,-M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,11,-M,x,6,3,-4,1,2,0,-1,1,0,3/2,-M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,2,0,x,4,0,-M,x,6,0,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,段,Cj,0,3,-1,-1,0,0,-M,-M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,11,-M,x,6,3,-4,1,2,0,-1,1,0,3/2,-M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,2,0,x,4,10,3,-2,0,1,0,0,-1,-M,x,6,1,0,1,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,段,Cj,0,3,-1,-1,0,0,-M,-M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,11,-M,x,6,3,-4,1,2,0,-1,1,0,3/2,-M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,2,0,x,4,10,3,-2,0,1,0,0,-1,-M,x,6,1,0,（,1,）,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,M+1,1,M-1,0,0,-M,0,-3M+1,段,Cj,0,3,-1,-1,0,0,-M,-M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,11,-M,x,6,3,-4,1,2,0,-1,1,0,3/2,-M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,2,0,x,4,10,3,-2,0,1,0,0,-1,-M,x,6,1,0,（,1,）,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,M+1,1,M-1,0,0,-M,0,-3M+1,3,0,x,4,0,-1,x,2,1,0,1,0,0,-1,1,-2,-1,x,3,0,Cj-Zj,段,Cj,0,3,-1,-1,0,0,-M,-M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,11,-M,x,6,3,-4,1,2,0,-1,1,0,3/2,-M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,2,0,x,4,10,3,-2,0,1,0,0,-1,-M,x,6,1,0,（,1,）,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,M+1,1,M-1,0,0,-M,0,-3M+1,3,0,x,4,12,（,3,）,0,0,1,-2,2,-5,-1,x,2,1,0,1,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,段,Cj,0,3,-1,-1,0,0,-M,-M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,11,-M,x,6,3,-4,1,2,0,-1,1,0,3/2,-M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,2,0,x,4,10,3,-2,0,1,0,0,-1,-M,x,6,1,0,（,1,）,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,M+1,1,M-1,0,0,-M,0,-3M+1,3,0,x,4,12,（,3,）,0,0,1,-2,2,-5,-1,x,2,1,0,1,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,2,1,0,0,0,-1,-M+1,-M-1,段,Cj,0,3,-1,-1,0,0,-M,-M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,11,-M,x,6,3,-4,1,2,0,-1,1,0,3/2,-M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,2,0,x,4,10,3,-2,0,1,0,0,-1,-M,x,6,1,0,（,1,）,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,M+1,1,M-1,0,0,-M,0,-3M+1,3,0,x,4,12,（,3,）,0,0,1,-2,2,-5,-1,x,2,1,0,1,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,2,1,0,0,0,-1,-M+1,-M-1,4,3,x,1,4,1,0,0,1/3,-2/3,2/3,-5/3,-1,x,2,0,-1,x,3,0,Cj-Zj,段,Cj,0,3,-1,-1,0,0,-M,-M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,11,-M,x,6,3,-4,1,2,0,-1,1,0,3/2,-M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,2,0,x,4,10,3,-2,0,1,0,0,-1,-M,x,6,1,0,（,1,）,0,0,-1,1,-2,1,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,M+1,1,M-1,0,0,-M,0,-3M+1,3,0,x,4,12,（,3,）,0,0,1,-2,2,-5,-1,x,2,1,0,1,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,2,1,0,0,0,-1,-M+1,-M-1,4,3,x,1,4,1,0,0,1/3,-2/3,2/3,-5/3,-1,x,2,1,0,1,0,0,-1,1,-2,-1,x,3,9,0,0,1,2/3,-4/3,4/3,-7/3,Cj-Zj,段,Cj,0,3,-1,-1,0,0,-M,-M,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,4,11,1,-2,1,1,0,0,0,11,-M,x,6,3,-4,1,2,0,-1,1,0,3/2,-M,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4M,-6M+3,M-1,3M-1,0,-M,0,0,2,0,x,4,10,3,-2,0,1,0,0,-1,-M,x,6,1,0,（,1,）,0,0,-1,1,-2,1,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,M+1,1,M-1,0,0,-M,0,-3M+1,3,0,x,4,12,（,3,）,0,0,1,-2,2,-5,-1,x,2,1,0,1,0,0,-1,1,-2,-1,x,3,1,-2,0,1,0,0,0,1,Cj-Zj,2,1,0,0,0,-1,-M+1,-M-1,4,3,x,1,4,1,0,0,1/3,-2/3,2/3,-5/3,-1,x,2,1,0,1,0,0,-1,1,-2,-1,x,3,9,0,0,1,2/3,-4/3,4/3,-7/3,Cj-Zj,-2,0,0,0,-1/3,-1/3,-M+1/3,-M+2/3,结论,c,j,-z,j,均为非正数,得到最优解和最优值。,x,1,=4,，,x,2,=1,，,x,3,=9,，,x,4,=x,5,=x,6,=x,7,=0,，,minF=-maxF=-2,二、两阶段法：,原理：分两阶段求解。,第一阶段，构筑一个只包括人工变量的目标函数：,minF=,x,t,，,在原约束条件下求解，如果计算结果是人工变量均为0，则继续求解；进入第二阶段，如果人工变量不为0，说明原问题无解。,如上例：人工变量为,x,6,，,x,7,，,第一阶段,解题过程,段,Cj,0,0,0,0,0,0,-1,-1,Qi,注,基,b,P,1,P,2,P,3,P,4,P,5,P,6,P,7,1,0,x,5,11,1,-2,1,0,1,0,0,11,-1,x,6,3,-4,1,2,-1,0,1,0,3/2,-1,x,7,1,-2,0,（,1,）,0,0,0,1,1,Cj-Zj,4,-6,1,3