单纯形法-人工变量法

1、单纯形法的进一步讨论,一、 目标函数为min的情形,三种处理方法,1 令z= -z = max z= -cx,2 求min z， 当所有检验数cj-zj=0 时为最优，否则要迭代，换入检验数最小的那个变量，确定换出变量的方法和前面max的情形一样,3 规定检验数为zj - cj， 其余过程和前面max的情形一样,几种情况,其中第2、3个约束方程中无明显基变量，分别加上人工变量x6, x7,二、 约束方程为“=”或“=”的情形（加人工变量,这时，初始基和初始基可行解很明显。x(0)=(0，0，0，11，0，3，1)t不满足原来的约束条件。如何使得可从x(0)开始，经迭代逐步得到x6=0，x7=0

2、 的基可行解，从而求得问题的最优解，有两种方法,反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例8的单纯形表格为,只要原问题有可行解，随着目标函数向最大化方向的改善，人工变量一定会逐步换出基，从而得到原问题的基可行解，进而得到基最优解,大m法,在目标函数中加上惩罚项,max =3x1-x2-x3-mx6-mx7 其中m为充分大的正数,3-6m m-13m-1 0-m 0 0,0 x4 10 3 -2 0 1 0 0 -1 -m x6 1 0 1 0 0 -1 1 -2 1 -1 x3 1 -2 0 1 0 0 0 1,1 -1+m 0 0-m 0 -3m+1

3、,11 3/2 1,5.3 两阶段法,第一阶段：以人工变量之和最小化为目标函数。 min = x6+x7,第二阶段：以第一阶段的最优解(不含人工变量)为初始解，以原目标函数为目标函数,约束方程为“=”或“=”的情形（加人工变量,人工变量法（确定初始可行基,原约束方程：ax=b,加入人工变量：xn+1，xn+m,人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解,max z=2x1+ x 2+ x 3 s.t. 4x1+2x2+ 2x 34 2x1+4x2 2

4、0 4x1+8x2+ 2x 316 x1，x2，x 30,用两阶段法求下面线性规划问题的解,5. 4 线性规划问题解的讨论,一、无可行解 max z=2x1+4x2 x1 +x2 10 2x1 +x2 40 x1 ,x2 0,人工变量不能从基底换出，此时原线性规划问题无可行解,两阶段法,例: max z=3x1+4x2 x1 +x2 40 2x1+x260 x1-x2 =0 x1 ,x2 0,此题初始解是退化的。最优解也是退化解。 退化解迭代中，当换入变量取零值时目标函数值没有改进,例 max z=3x1+5x2 3x1 +5x2 15 2x1 + x2 5 2x1+2x2 11 x1 ,x2 0,如果将x1换入基底，得另一解，由可行域凸性易知，有两个最优解必有无穷多组最优解 当非基底变量的检验数中有取零值，或检验数中零的个数大于基变量个数时，有无穷多解,四、无（有）界解 max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x23 x1 ,x2 0,若检验数有大于0，而对应系数列中元素全部小于或等于零（无换出变量）则原问题有无界解,练习：写出单纯形表,分析检验数 与系数关系并画图验证,线性规划解除有唯一最优解的情况外，还有如下几种情况,无可行解 退化 无穷多解 无界解,人工变量不能从基底中换出,基可行解中非零元素个数小于