单纯形法-人工变量法

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工变量的引入及其解法,当约束条件为“,”型，引入剩余变量和人工变量,由于所添加的剩余变量的技术系数为,1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量,由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定,两种方法,大M法,二阶段法,其中第2、3个约束方程中无明显基变量，分别加上人工变量,x,6, x,7,约束方程为“=”或“=”的情形,（,加,人工变量,）,这时，初始基和初始基可行解很明显。,X,(0),=(0，0，0，11，0，3，1),T,不满足原来的约束条件。如何使得可从,X,(0),开始，经迭代逐步得到,x,6,=0，,x,7,=0 的基可行解，从而求得问题的最优解，有两种方法：,反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例的单纯形表格为：,只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解。,大M法,在目标函数中加上惩罚项。,max =,3,x,1,-,x,2,-,x,3,-,M,x,6,-,M,x,7,其中M为充分大的正数。,3,-,6M M,-,13M,-,1 0,-,M 0 0,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,1,-1+M 0 0,-,M 0 -3M+1,0,x,4,12,3,0 0 1 -2,-1,x,2,1 0 1 0 0 -1 4,-1,x,3,1 -2 0 1 0 0,1,0 0 0,-1,3,x,1,4 1 0 0 1/3 -2/3,-1,x,2,1 0 1 0 0 -1,-1,x,3,9 0 0 1 2/3 -4/3,-2,0 0 0,-1/3 -1/3,X,*,= (4，1，9，0，0),T, z,*,= 2,11,3/2,1, ,两阶段法,第一阶段,：以,人工变量之和,最小化为目标函数。,min,=,x,6,+,x,7,第二阶段,：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数。,约束方程为“=”或“=”的情形,（,加,人工变量,）,人工变量法（确定初始可行基）：,原约束方程：AX=b,加入人工变量：x,n+1,，,，x,n+m,人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。,Max Z=2x,1,+ x,2,+ x,3,s.t. 4x,1,+2x,2,+ 2x,3,4,2x,1,+4x,2,20,4x,1,+8x,2,+ 2x,3,16,x,1,，x,2,，x,3,0,用两阶段法求下面线性规划问题的解,线性规划问题解的讨论,一、无可行解,max z=2x,1,+4x,2,x,1,+x,2,10,2x,1,+x,2,40,x,1,x,2,0,人工变量不能从基底换出，此时原线性规划问题无可行解。,x,1,x,2,C,B,X,B,b,X3,x5,0,-1,0 0 0 0 -1,x,1,x,2,x,3,x,4,x,5,40 2 1 0 -1 1,10 1 1 1 0 0,c,j,10,40/2,x1,x5,0,-1,20 0 -1 -2 -1 1,10 1 1 1 0 0,c,j,-z,j,0 -1 -2 -1 0,c,j,-z,j,2 1 0 -1 0,Z,0,=-40,Z,1,=-20,两阶段法,例,:,max z=3x,1,+4x,2,x,1,+x,2,40,2x,1,+x,2,60,x,1,-x,2,=0,x,1,x,2,0,此题初始解是退化的。最优解也是退化解。,退化解迭代中，当换入变量取零值时目标函数值没有改进，,x,1,x,2,0,x,3,40 1 1 1 0 0,0,x,4,60 2 1 0 1 -1,-M,x,5,0 1 -1 0 0 1,0,x,3,40 0 2 1 0,0,x,4,60 0 3 0 1,3,x,1,0 1 -1 0 0,3+M 4-M 0 0 0,z,j,-,c,j,0 0 0 -7/3,z,j,-,c,j,0,x,3,0 0 0 1 -1/3,4,x,2,20 0 1 0 1/3,3,x,1,20 1 0 0 1/3,c,j,3 4 0 0 -M,C,B,X,B,b,x,5,x,1,x,2,x,3,x,4,0 7 0 0,z,j,-,c,j,0 0 -3.5 0,z,j,-,c,j,4,x,2,20 0 1 1/2 0,0,x,4,0 0 0 -3/2 1,3,x,1,20 1 0 1/2 0,例 max z=3x,1,+5x,2,3x,1,+5x,2,15,2x,1,+ x,2,5,2,x,1,+2x,2,11,x,1,x,2,0,如果将x,1,换入基底，得另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解,当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解,。,C,B,X,B,b,x3,x4,x5,0,0,0,3 5 0 0 0,x,1,x,2,x,3,x,4,x,5,5 2 1 0 1 0,15 3 5 1 0 0,3,5,11/2,x2,x4,x5,5,0,0,3 3/5 1 1/5 0 0,2 7/5 0 -1/5 1 0,5 4/5 0 -2/5 0 1,c,j,-z,j,0 0 -1 0 0,c,j,-z,j,3 5 0 0 0,Z,0,=0,11 2 2 0 0 1,Z,1,=15,x,1,x,2,四、无（有）界解,max z=x,1,+x,2,-2x,1,+x,2,4,x,1,- x,2,2,-3,x,1,+x,2,3,x,1,x,2,0,若检验数有大于0，而对应系数列中元素全部小于或等于零（无换出变量）则原问题有无界解。,练习：写出单纯形表,分析检验数,与系数关系并画图验证。,线性规划解除有,唯一最优解,的情况外，还有如下几种情况,无可行解,退化,无穷多解,无界解,人工变量不能从基底中换出,基可行解中非零元素个数小于基变量数,检验数中零的个数多于基变量的个数,检验数大于零，但对应列元素小于等于零，无换出变量,唯一最优解,否,否,否,是,是,是,添加松弛变量,、,人工变量 列出初始单纯形表,计算非基变量,各列的检验数,j,所有,j,0,基变量中,有非零的,人工变量,某非基变量检验数为零,无可行解,无穷多最优解,对任一,j,0,有a,ik,0,无界解,令,k,=max,j,x,k,为换入变量,对所有a,ik,0计算,i,=b,i,/a,ik,令,l,=min,i,第l个基变量,为换出变量，,a,l,k,为主元素,迭代运算,.,用非基变量x,k,替换换出变量,.,对主元素行(第l行),令 b,l,/a,lk,b,l,;a,lj,/a,lk,a,jl,对主元素列(第k列)令1,a,lk,;0,其它元素表中其它行列元素,令 a,ij,-a,li,/a,lk,a,ik,a,ij,b,i,-b,l,/a,lk,a,ik,b,i,j,- a,lj,/a,lk, ,k, ,j,否,对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图：,