最优化教案两阶段法与大M法

§4.2两阶段法与大M法————初始可行基的求法求解线性规划的步骤是：已知一个初始基本可行解从初始基本可行解出发，写出单纯型表，求出进基离基变量，做主元消去法，求出一个新的基本可行解且使目标函数值得到改善。判断当前基本可行解是否是最优解那末，当观察不出来初始基本可行解时，怎么办？下面介绍的方法是几种求初始基本可行解的方法4.2.1≥0其中A是矩阵，≥0。若A中有阶单位矩阵，则初始基本可行解立即得到。比如，，那么就是一个基本可行解。若A中不包含阶单位矩阵，就需要用某种方法求出一个基本可行解。介绍两阶段法之前，先引入人工变量的概念。设A中不包含阶单位矩阵，为使约束方程的系数矩阵中含有阶单位矩阵，把每个方程增加一个非负变量，令（4.2.2）≥0，≥0即（4.2.3）≥0，≥0显然，是（4.2.3）向量≥0是人为引入的，它的每个分量成为人工变量。人变量与前面介绍过的松弛变量是两个不同的概念。松弛变量的作用是把不等式约束改写成等式约束，改写前后的两个问题是等价的。因此，松弛变量是“合法”的变量。而人工变量的引入，改变了原来的约束条件从这个意义上讲，它们是“不合法”的变量。第一阶段是用单纯形方法消去人工变量（如果可能的话）：（4.2.4）≥0，≥0其中是分量全是1的维列向量，是人工变量构成的维列向量。由于是（4.2.4）的一个基本可行解，目标函数值在可行域上有下界，因此问题（4.2.4求解（4.2.4），设得到的最优基本可行解是，此时必有下列三种情形之一：这时（4.2.1）无可行解。因为如果（4.2.1）存在可行解则是（4.2.4）的可行解。在此点，问题（4.2.4＜而是目标函数值的最优值，矛盾。2.且的分量都是非基变量。这时，个基变量都是原来的变量，又知是（4.2.4）的基本可行解，因此是（4.2.1）的一个基本可行解。3且的某些分量是基变量。这时，可用主元消去法把原来变量中的某些非基变量引进基，替换出基变量中的人工变量，再开始两阶段法的第二阶段。应指出，为替换出人工变量而采用的主元消去，在主元的选择上，并不要求遵守单纯形法确定离进基变量的规则。第二阶段，就是从得到的基本可行解出发，用单纯形方法求（4.2.1例4.2.1≥2≥1≤3≥0先引进松弛变量，把问题化成标准形式。由于此标准形式中约束方程的系数矩阵并不包含3阶单位矩阵，因此还引进人工变量。下面先求解一阶段问题：+=2=1=3≥0仍然用主元消去法，主元用框号标出。迭代过程如下：11-1001021-10-100111001100320-1-1000302-1101-111-10-10011010110-1202-1100-2101-0100-1000100000-1-10由于所有判别数≤0，因此达到最优解。在一阶段问题的最优解中，人工变量都是非基变量。这样，我们得到初始基本可行解第一阶段结束后，修改最后的单纯形表。去掉人工变量和下面的列（也可保留，但人工变量不能再进基），把最后的判别数行按原来问题进行修正。其他不变。然后开始第二阶段迭代，即极大化目标函数。迭代过程如下：01010000100002-110111-10020-1101103-20040101121000130-11011010026得到（4.2.5）的最优解（，）=（3，0），目标函数最优值例4.2.2≤2=4=0≥0引进松弛变量，把上述问题化成标准形式，再引进人工变量，得到下列一阶段问题：=2+=4+=0≥0，…，6先用单纯形法解一阶段问题，迭代如下：其中是目标函数中基变量的系数构成的维行向量，是上表中的第列，是上表中的右端列。-1211002-44-1010410-10010-34-200041001-20-3-210010-10010-10-4-2000，取主元，经元消去得到下表：0100100-5-212010-10010再以为主元，进行主元消法，得到0100100101000这样，基变量均为原来的变量，得到原来的问题的一个基本可行解再把表中人工变量对应的列去掉（也可保留，但人工变量不能再进基），并把判别数行增加进去。正如前面曾经指出过的那样，初表中的判别数和目标函数值利用定义来计算，即其中是目标函数中基变量的系数构成的维行向量，是上表中的第列，是上表中的右端列。第二阶段的初表如下：010100101000000-1此表已是最优表。最优解是目标函数值的最优值例4.2.3+=2+=10≥0引进人工变量。解第一阶段问题：+=4+=6+=2++=10≥0下面以表格形式给出迭代过程：2-110100411100106100100023020001106040000200-11-21000011-1010410010002002-30014004-600080-11-210000201-1104100100020201-20140402-40080010201002100100020000-1-1100000-2-200第一阶段问题已经达到最优解。人工变量均取零值，但人工变量是基变量，应从基中替换出去。现在修正表中判别数行。由于，和是基变量，相对的判别数均为零，只需计算非基变量对应的判别数：在现行基本可行解处的目标函数值去掉人工变量下面的列，得到第二阶段的初始单纯形表：00120102100120004此表已是最优表。得到最优解目标函数的最优值在两阶段法的第二阶段，可以保留人工变量下面的列，好处在于：最初单位矩阵所在的位置，在以后的每个单纯形表中，总是存放现行基的逆。但必须注意，正如前面指出的，人工变量绝不可再进基。4.2.2大法大法的基本思想是：在约束中增加人工变量，同时修改目标函数，加上罚项，其中是很大的正数，这样，在极小化目标函数的过程中，由于大的存在，将迫使人工变量离基。我们仍考虑线性规划问题≥0（4.2.6）引进人工变量，研究下列问题：（4.2.7）≥0，≥0，用单纯形方法求解问题（4.2.71.达到（4.2.7）的最优解，且。此时，得到的即为问题（4.2.6）的最优解。2.达到（4.2.7）的最优解，且＞0。这时，原（4.2.6）无可行解。因为如果（4.2.6）有可行解，比如说，则，是（4.2.7）的可行解。问题（4.2.7）在这一点的目标函数值（4.2.8）设（4.2.7则最优值（4.2.9）由于是很大的正数，＞0，因此可以很大，从而由（4.2.8）和（4.2.9）推知＜，这与为最优值矛盾。3.（4.2.7）问题不存在有限最优值，在单纯形表格中，

＞0≤0，这时，问题（4.2.6）无界。理由是：在此情形下，原来的问题必存在一个可行解。由于（4是无界多面集，根据定理2.1.1和定理3.2.2，存在方向≥0使得＜0(4.2.10)由于可取任意大的正数，因此由上式可推知。是原来问题的可行域的方向，根据定理3.2.2，问题(4.2.6)无界。4.问题(4.2.7)不存在有限最优值，在单纯形表中，＞0，≤0，有些人工变量不等于零，即。这时，(4.2.6)无可行解。例4.2.4用大法求解下列问题≤11≥3≥0引进松弛变量和人工变量，用单纯形方法解下列问题：=11=3=1≥0在下面的迭代中，选择最大判别数时要注意是很大的正数，它的数值可超过每个已知的正数。迭代过程如下：1-2110001121-40-110310-2000110000-23100-1100100-11-2110-20001101000031-22-5120100-11-2110-2000110010-1200140100-11-211009000-2由于是很大的正数，因此所有的判别数≤0达到最优解。人工变量。原来问题的最优解目标函数最优值例：解：引入剩余变量和人工变量，得到新的LP问题2-1-10104-310-101100-10-1-1115-310-10110-30-3辅助问题最优解中人工变量，所以原问题无解。4.2.3单个人工变量技巧这是针对常数项不是非负向量时，寻求初始基本可行解的方法。我们考虑线性规划（4.2.14）≥0MinSt例≥1≥2≥0标准型=-1=-11）让进基，离基变量选例4.2.5≥1≥2≥0先引进松弛变量把约束写成等式，然后再用（-1）乘每个方程的两端，使系数矩阵包含二阶段单位矩阵，即确定，再引进人工变量，得到（4.2.17）≥0把方程组（4.2.17-1110-1-11-201-1-2以第2行第5列元素（-1）为主元，经主元消去，得到-231-101-120-112得到（4.2.17）的一个基本可行解。再用两阶段法或大法求解，现在用两阶段法，求解一阶段问题≥0迭代过程如下表：-231-101-120-112-120-10210010001-1-12310-2-1340000-10得到一个原来问题的一个基本可行解由此基本可行解开始，进行两阶段法的第二阶段，本阶段的起始单纯形表为01-1-1310-2-1400-4-310判别数均非正，已达到原来问题的最优解。这个最优解是目标函数的最优值利用单个人工变量时，关于原来问题的解的状况的讨论，与前面关于两阶段法和大法的讨论类似，这里不再重复。§4.3退化情形4.3.1循环现象我们曾经指出，当线性规划存在最优解时，在非退化的情形下，单纯形方法经有限次迭代必达最优解，然而，对于退化情形，当最优解存在时，用前面介绍的方法，有可能经有限次迭代求不出最优解，即出现循环现象。事实上，已经有人给出循环例子。下面的例题是给出的。例4.3.1用单纯形方法解下列问题:≥0下面列出迭代情况：