人工变量法和大M法.pptVIP

1.4 单纯形法的进一步讨论 一、人工变量法 从前面的例子很容易看到,若LP问题的线性约束的关系不全是’≤’,则第一个可行基就不那么好找了.比如, 例7 这个在等式上增加的非负变量被称为人工变量,由此得到的基被称为人造基.相应的基解就称为人造基解. 问题:人工变量是虚拟的,迭代之后,在最优解里是否还含有人工变量(即人工变量是否为0)?显然地,若经过迭代,不能将人工变量都变成为非基变量,则表明原LP问题无可行解,当然就无最优解. 怎样做,才能在迭代中去将人工变量去除呢? 有两个方法,这就是大M法和两阶段法. 一、大M法 这种方法就是在目标函数中加上一个惩罚因素M作为人工变量的系数,其值可以无穷大,即 具体做的时候,所有的人工变量前统一的一个大M. 例8 用大M法求解下述LP问题 解: 引进人工变量x4,x5,于是得下述问题 初始单纯形表 用单纯形法迭代如下: 迭代到此,可以看到,所有的检验数非正,已得问题的最优解,即当x1=3,x3=1,x2=x4=x5=0时目标函数取最大,目标函数最大值为7. 因为人工变量全为0,即可将人工变量删去,即得原问题的最优解为:x1=3, x2=0,x3=1 目标函数最大值为7. 注意,如果由大M法得到的最优解中含有人工为基变量,则说明原LP问题无最优解. 另外,本例可以只在第一个线性约束加人工变量x4,因为第二个线性约束有一个x3,系数为正,且第一个线性约束无此变量. 二、两阶段法 引进人工变量来求解的一个目标是在找到第一个基可行解的同时去掉人工变量,因此我们可以考虑第一阶段的目标是求函数g(x)的最小值.1、如果在求得第一阶段最小值时能去掉人工变量(即人工变量全部为非基变量),则可以此时的可行基进入第二阶段,否则 2、由于有人工变量仍为基变量,则原LP问题就无最优解. 第二阶段,在第一阶段已求得的可行基上,去掉约束中的人工变量(因为人工变量全是非基变量),将基变量去消原来的目标函数中的元,继续单纯形法求解. 第一阶段迭代过程如下: 从第一阶段的结果看,由于最优解的基变量里不含人工变量,就可以去掉函数g和人工变量,以x1和x3作为可行基来解原来的LP问题. 于是有 先消去目标函数中的基变量,就得到第一张单纯形表,再从这张单纯形表继续. 至此,检验数全部非正,因此得原LP问题的最优解 x=(3,0,1)T,目标函数的最大值为7. * 化成标准形后为: 该问题的初始可行基不是一下就能看出的.经观察,可知,如果在第一个式子加一个非负变量x6,则可以和x3构成一个可行基. 迭代的目标就是要去掉目标函数中的大M,否则由于-M充分地小,目标函数就无法达到最优. 用单纯形法来解,过程如下: 1 0 3 -2 1 4 x5 0 1 -3 -2 3 6 x4 -M -M -2 -1 3 0 f x5 x4 x3 x2 x1 常数 1/2 - 1/6 1 -1 1/3 0 1 x3 1/2 1/6 0 - 2/3 1 3 x1 -10000 1/2 -10000 5/6 0 -1 2/3 0 -7 f 1 - 1/3 2 -2 2/3 0 2 x5 0 1/3 -1 2/3 1 2 x1 -10000 -10001 1 -3 0 -6 　 1 0 1 -2 1 4 x5 0 1 -3 2 3 6 x4 -10000 -10000 -2 -1 3 0 f x5 x4 x3 x2 x1 常数 　 例如对问题: 解 引入人工变量 x4和x5后,按两阶段来解,则第一阶段先解如下问题. 第一阶段,先解问题 化为标准形,则为 1/2 - 1/6 1 -1 1/3 0 1 x3 1/2 1/6 0 - 2/3 1 3 x1 -1 -1 0 0 0 0 -g 1 - 1/3 2 -2 2/3 0 2 x5 0 1/3 -1 2/3 1 2 x1 0 -1 1/3 2 -2 2/3 0 2 -g 1 0 1 -2 1 4 x5 0 1 -3 2 3 6 x4 0 0 -2 0 4 10 -g 1 0 1 -2 1 4 x5 0 1 -3 2 3 6 x4 -1 -1 0 0 0 　 -g x5 x4 x3 x2 x1 常数 　 用单纯形法继续求解,过程如下: 1 -1 1/3 0 1