运筹学人工变量及其处理方法.pptVIP

第五节人工变量及其处理方法 以 X(0)作初始基本可行解进行迭代时，怎样才能较快地将所有的人工变量从基变量中全部“赶”出去（如果能全部“赶”出去的话）。这会影响到得到最优解的迭代次数。 一.大M法 大M法的不足 在用计算机求解时，不容易确定M 的取值，且M过大容易引起计算误差。 几个问题 1.目标函数为极小化时解的最优性判别： 小 结 * * 为了使初始可行基为一个单位矩阵，在有些约束条件中需要加入人工变量。 人工变量 人工变量 但加入人工变量后的LP与未加入时的LP一般是不等价的 新LP： LP： 在每一个约束方程左边加上一个人工变量 ，得 含有一个m阶单位矩阵，以 为基向量，得到一个初始基本可行解 解中只要含有非零人工变量，实质上该解不是可行解。 只有当最优解中，人工变量都取零值时，才可认为两个问题的最优解是相当的。 结 论 1. 若新LP的最优解中，人工变量都处在非基变量位置（即取零值）时，原LP有最优解。 2.若新LP的最优解中，包含有非零的人工变量，则原LP无可行解。 3.若新LP的最优解的基变量中，包含有人工变量，但该人工变量取值为零。这时可将某个非基变量引入基变量中来替换该人工变量，从而得到原LP的最优解。 －－大M法与两阶段法 M是一个很大的正数。 手工计算时，只要认定M是一个很大的数。 计算机计算时，必须对M给出一个具体数值，通常取比原问题中最大数据高1~2个数量级的数值。并视求解情况对M作适当调节。 将目标函数修改为 例：用大M法求解LP 解： 引入松弛变量、剩余变量和人工变量 将问题标准化，得： 以 对应的系数列向量构成一单位矩阵 ， 取初始基 为基变量， 为 非基变量。 初始单纯形表： [ ] 确定 为进基变量，而 为离基变量，以 为主元素。 基变换＋调基 [ ] [ ] 最优解： （4，1，9，0，0，0，0）T， 最优值：2 人工变量x6,x7已不在基变量中，故原LP的最优解为 （4，1，9，0，0）T， 最优值为2 二. 两阶段法 将新LP的求解过程分成两个阶段： 第一阶段：求解第一个LP： 辅助LP 原LP： 辅助LP： 原LP的可行域：D 辅助LP的可行域：D’ 目的：通过解辅助LP来获得原LP的初始解 用单纯形法计算辅助LP的结果有三种可能情形： 1. 最优值 ,且人工变量皆为非基变量。 从第一阶段的最优解中去掉人工变量后，即为原LP的 一个基本可行解。作为原LP的一个初始基本可行解， 再求原问题，从而进入第二阶段。 2. 最优值 ,说明至少有一个人工变量不为零。 原LP无可行解。不再需要进入第二个阶段计算。 3. 最优值 ,且存在人工变量为基变量，但取值为零 把某个非基变量与该人工变量进行调换。 两阶段法的第一阶段求解的目的： 1.判断原LP有无可行解。 2.若有，则可得原LP的一个初始基本可行解，再对原LP进行第二阶段的计算。 例：用两阶段法求解LP 第一阶段： 初始可行基 初始基本可行解 初始单纯形表 [ ] 0 [ ] 人工变量x6,x7已从基变量中换出。 第二阶段： 初始单纯形表 [ ] 最优解：（4，1，9，0，0）T 最优值：2 进基变量： 2.退化与循环的问题 定义：一个基本可行解如果存在取零值的基变量，则称为是退化的基本可行解，相应的基称为是退化基。 如果所有的基变量都大于零，就是非退化的基本可行解。 在非退化情形下，用单纯形方法经过有限次迭代一定可达到最优解。 在退化情形下，用单纯形方法进行迭代可能得不到最优解。 基迭代经过若干次后又回到先前的可行基 B1 B2 ... B1 循环 例： 为避免循环，伯兰特(Bland)规则： 1. 当存在多个 ，始终选取下标值为最小的变量作为进基变量。 2.当 出现两个以上相同的最小比值时，始终选取下标值为最小的变量为离基变量 *