《(2.7.1)--02_7大M法-罚函数法.pdf》由会员分享，可在线阅读，更多相关《(2.7.1)--02_7大M法-罚函数法.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、单纯形法的进一步讨论 不同LP标准型的判别准则:maxmin最优解换入变量换出变量j 0j 0人工变量 标准化后找不到单位阵，采用人造基给方程加入人工变量即:当约束条件为“”或“=”型，引入剩余变量和人工变量 由于所添加的剩余变量的技术系数为 1,不能构成初始基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量人工变量为虚拟变量,在原问题的解中是不能存在的，最终取值必须为零,要求把它从基变量中逐个换出，基变量中不再含非零的人工变量。因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定。两种方法 大M法 二阶段法大
2、M法minZ=-3x1+x2+x3x1-2 x2+x3 11 -4 x1+x2+2x3 3 2x1-x3=-1x1，x2，x3 0 x1-2 x2+x3+x4 =11 -4 x1+x2+2x3 x5=3 -2x1+x3 =1x1-2 x2+x3+x4=11 -4 x1+x2+2x3 x5+x6 =3 -2x1+x3+x7=1M是仸意大的正数x1,x2，x3,x4,x5,x6,x7 0 x1-2 x2+x3+x4=11 -4x1+x2 +2x3 x5+x6=3 -2x1+x3+x7=1minZ=-3x1+x2+x3+0 x4+0 x5+M x6+M x7用单纯形法进行计算cj-31100MMiC
3、BXBbx1x2x3x4x5x6x70 x4111-21100011/1=11Mx63-4120-1103/2Mx71-20100011/1=cj-zj0M000 x4103-20100-1-Mx610100-11-21/11x31-2010001-=cj-zj-11-M00M03M-10 x4123001-22-512/3=41x210100-11-2-1x31-2010001-=cj-zj-10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3=cj-zj0001/31/3M-1/3-3+6M 1-M1-3M此问题的最优解为:x1*=4,x2*=1,x3*=9,x4*=x5*=x6*=x7*=0,z*=-3 4+9+1=-2Slide 6 大M法实质上与原单纯型法一样，M可看成一个很大的常数 人工变量被迭代出去后就不会再成为基变量 当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解大M法的一些说明目标函数中的价值系数:目标函数为max-M目标函数为min+M