[理学]2最优化教案两阶段法与大M法.doc

4.2 两阶段法与大M法初始可行基的求法求解线性规划的步骤是：1） 已知一个初始基本可行解2） 从初始基本可行解出发，写出单纯型表，求出进基离基变量，做主元消去法，求出一个新的基本可行解且使目标函数值得到改善。3） 判断当前基本可行解是否是最优解那末，当观察不出来初始基本可行解时，怎么办？下面介绍的方法是几种求初始基本可行解的方法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），设得到的最优基本可行解是，此时必有下列三种情形之一：1. 这时（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 =30 仍然用主元消去法，主元用框号标出。迭代过程如下： 11-1001 0 2 1 -1 0-100 1 1 10 0110 0320-1-100 0 30 2 -1 101 -1 11-1 0-100 11 0 1 0 110 -1 20 2-1 100 -2 101- 0 10 0-10 00 1 0 0 0 00-1 -1 0 由于所有判别数0，因此达到最优解。在一阶段问题的最优解中，人工变量都是非基变量。这样，我们得到初始基本可行解 第一阶段结束后，修改最后的单纯形表。去掉人工变量和下面的列（也可保留，但人工变量不能再进基），把最后的判别数行按原来问题进行修正。其他不变。然后开始第二阶段迭代，即极大化目标函数。迭代过程如下：01 0 1 00 00 1 000 0 2 -1 1011 1-1 002 0-1 1 01 10 3-2 0040 1 0 1121 0 0 013 0-1 1 01 10 1 0 026 得到（4.2.5）的最优解（，）=（3，0），目标函数最优值 例4.2.2 用两阶段法求解下列问题 2 =4 =0 0引进松弛变量，把上述问题化成标准形式，再引进人工变量，得到下列一阶段问题： =2 + =4 +=0 0 ，6 先用单纯形法解一阶段问题，迭代如下： 其中是目标函数中基变量的系数构成的维行向量，是上表中的第列，是上表中的右端列。 -12 110 0 2 -44-101 0 4 10-100 10-34-200 0 4 1 0 0 1-2 0-3-21 00 1 0-1 00 1 0-1 0-4-20 00，取主元，经元消去得到下表： 01 00 1 00-5-21 2 0 10-100 10 再以为主元，进行主元消法，得到 01 0 0 1 00 1 0 10 0 0这样，基变量均为原来的变量，得到原来的问题的一个基本可行解 再把表中人工变量对应的列去掉（也可保留，但人工变量不能再进基），并把判别数行增加进去。正如前面曾经指出过的那样，初表中的判别数和目标函数值利用定义来计算，即 其中是目标函数中基变量的系数构成的维行向量，是上表中的第列，是上表中的右端列。 第二阶段的初表如下： 0 1 0 1 0 0 1 0 1 0 0 00 0 0 -1此表已是最优表。最优解是 目标函数值的最优值 例4.2.3 用两阶段法求解下列问题 +=2 + =10 0 引进人工变量。解第一阶段问题： + =4 + =6 + =2 + +=10 0 下面以表格形式给出迭代过程： 2-1 1 0 1 00 4 1 1 1 0 0 10 6 1 0 0 1 0 0023 0 2 00 01 106 0 4 00 0 0200-1 1 -2 1 00 0 0 1 1 -1 0 10 4 1 0 0 1 0 0020 0 2 -30 01 40 0 4 -60 0 0 80-1 1 -2 1 00 0 0 2 0 1 -1 10 4 1 0 0 1 0 0020 2 0 1-2 01 40 4 0 2-4 0 0 80 0 1 0 2 0 1 0 0 2 1 0 0 1 0 0020 0 0 0-1 -11 00 0 0 0-2-2 0 0第一阶段问题已经达到最优解。人工变量均取零值，但人工变量是基变量，应从基中替换出去。 现在修正表中判别数行。由于，和是基变量，相对的判别数均为零，只需计算非基变量对应的判别数： 在现行基本可行解处的目标函数值 去掉人工变量下面的列，得到第二阶段的初始单纯形表： 0 0 1 2 0 1 0 2 1 0 0 120 0 0 4此表已是最优表。得到最优解 目标函数的最优值 在两阶段法的第二阶段，可以保留人工变量下面的列，好处在于：最初单位矩阵所在的位置，在以后的每个单纯形表中，总是存 放现行基的逆。但必须注意，正如前面指出的，人工变量绝不可再进基。 4.2.2 大法大法的基本思想是：在约束中增加人工变量，同时修改目标函数，加上罚项，其中是很大的正数，这样，在极小化目标函数的过程中，由于大的存在，将迫使人工变量离基。我们仍考虑线性规划问题 0 （4.2.6） 引进人工变量，研究下列问题： （ 4.2.7） 0，0，用单纯形方法求解问题（4.2.7），其结果必为下列几种情形 之一： 1.达到（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.7）的可行域 是无界多面集，根据定理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-2 1 1 0 0 0 11 2 1-4 0-11 0 3 10-2 000 1 1 00 0 0-2 3 1 0 0 -1 10 0 1 0 0-11 -2 1 10-2 000 1 1 0 100 0 0 3 1 -2 2 -5 12 0 1 0 0-11 -2 1 10-2 000 1 1 0 0 10 -1 2 0 0 1 4 0 1 0 0-11 -2 1 10 0 9 0 0 0 -2 由于是很大的正数，因此所有的判别数0达到最优解。人工变量。原来问题的最优解 目标函数最优值 例： 解：引入剩余变量和人工变量，得到新的LP 问题 2 -1 -1 0 1 0 4 -3 10 -1 0 1 1 00 -1 0 -1 -1 1 1 5 -3 1 0 -1 01 1 0-3 0-3 辅助问题最优解中人工变量，所以原问题无解。 4.2.3 单个人工变量技巧这是针对常数项不是非负向量时，寻求初始基本可行解的方法。 我们考虑线性规划 （4.2.14） 0Min St 例 1 2 0标准型 =-1 =-1 1）让进基，离基变量选 例 4.2.5 求解下列线性规划问题： 1 2 0先引进松弛变量把约束写成等式，然后再用（-1）乘每个方程的两端，使系数矩阵包含二阶段单位矩阵，即确定，再引进人工变量，得到 （ 4.2.17） 0 把方程组（4.2.17）的增广矩阵置于表中： -1 1 10 -1 -1 1-2 01 -1 -2以第2行第5列元素（-1）为主元，经主元消去，得到-2 3 1-1 0 1 -1 2 0-1 1 2得到（4.2.17）的一个基本可行解。再用两阶段法或大法求解，现在用两阶段法，求解一阶段问题 0 迭代过程如下表： -23 1 -101 -12 0 -112 -120 -1021 0 01 0001-1 -1 23 10-2 -1 34 00 0 0-10 得到一个原来问题的一个基本可行解 由此基本可行解开始，进行两阶段法的第二阶段，本阶段的起始单纯形表为 01 -1 -13 10 -2 -14 00 -4 -310判别数均非正，已达到原来问题的最优解。这个最优解是 目标函数的最优值利用单个人工变量时，关于原来问题的解的状况的讨论，与前面关于两阶段法和大法的讨论类似，这里不再重复。 4.3 退 化 情 形 4.3.1 循环现象 我们曾经指出，当线性规划存在最优解时，在 非退化的情形下，单纯形方法经有限次迭代必达最优解，然而，对于退化情形，当最优解存在时，用前面介绍的方法，有可能经有限次迭代求不出最优解，即出现循环现象。事实上，已经有人给出循环例子。 下面的例题是给出的。 例4.3.1 用单纯形方法解下列问题: 0 下面列出迭代情况： 1 0 0 -8 -1 9 0 0 1 0 -12 3 0 00 1 00 1 0 1 0 0 0 -20 -6 0 4 0 0 1 -32 -4 36 0 0 1 0 0-11 -150 00 1 001 0 1 -3 0 00 4 -32 0 4 8 0 1 0 8 -84 0 0 0 1 0 00 1 001 0 1 -1-1 00 0 2 -18 0 1 0 0 1 0 0 10 0 -1 1 00 1 2-3 0 0 0 3 0 2 -6 0 56 1 0 0 0 0 10 -26 1 -560 0 1 1-1 0 -16