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

《2最优化教案(两阶段法与大M法)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、§4.2两阶段法与大M法————初始可行基的求法求解线性规划的步骤是：1）已知一个初始基本可行解2）从初始基本可行解出发，写出单纯型表，求出进基离基变量，做主元消去法，求出一个新的基本可行解且使目标函数值得到改善。3）判断当前基本可行解是否是最优解那末，当观察不出来初始基本可行解时，怎么办？下面介绍的方法是几种求初始基本可行解的方法4.2.1两阶段法≥0其中A是矩阵，≥0。若A中有阶单位矩阵，则初始基本可行解立即得到。比如，，那么35就是一个基本可行解。若A中不包含阶单位矩阵，就需要用某种方法求出一个基本可行解。介绍两阶段法之前，先引入人工变量

2、的概念。设A中不包含阶单位矩阵，为使约束方程的系数矩阵中含有阶单位矩阵，把每个方程增加一个非负变量，令（4.2.2）≥0，≥0即（4.2.3）≥0，≥035显然，是（4.2.3）的一个基本可行解。向量≥0是人为引入的，它的每个分量成为人工变量。人变量与前面介绍过的松弛变量是两个不同的概念。松弛变量的作用是把不等式约束改写成等式约束，改写前后的两个问题是等价的。因此，松弛变量是“合法”的变量。而人工变量的引入，改变了原来的约束条件从这个意义上讲，它们是“不合法”的变量。第一阶段是用单纯形方法消去人工变量（如果可能的话）：（4.2.4）35≥0，≥

3、0其中是分量全是1的维列向量，是人工变量构成的维列向量。由于是（4.2.4）的一个基本可行解，目标函数值在可行域上有下界，因此问题（4.2.4）必存在最优基本可行解。求解（4.2.4），设得到的最优基本可行解是，此时必有下列三种情形之一：1.这时（4.2.1）无可行解。因为如果（4.2.1）存在可行解则35是（4.2.4）的可行解。在此点，问题（4.2.4）的目标函数值＜而是目标函数值的最优值，矛盾。2.且的分量都是非基变量。这时，个基变量都是原来的变量，又知是（4.2.4）的基本可行解，因此是（4.2.1）的一个基本可行解。3且35的某些分量

4、是基变量。这时，可用主元消去法把原来变量中的某些非基变量引进基，替换出基变量中的人工变量，再开始两阶段法的第二阶段。应指出，为替换出人工变量而采用的主元消去，在主元的选择上，并不要求遵守单纯形法确定离进基变量的规则。第二阶段，就是从得到的基本可行解出发，用单纯形方法求（4.2.1）的最优解。例4.2.1用两阶段法求下列问题的最优解≥2≥1≤3≥0先引进松弛变量，把问题化成标准形式。由于此标准形式中约束方程的系数矩阵并不包含3阶单位矩阵，因此还引进人工变量。下面先求解一阶段问题：35+=2=1=3≥0仍然用主元消去法，主元用框号标出。迭代过程如下

5、：11-100102351-10-100111001100320-1-1000302-1101-111-10-10011010110-1202-1100-2101-0100-1000100000-1-1035由于所有判别数≤0，因此达到最优解。在一阶段问题的最优解中，人工变量都是非基变量。这样，我们得到初始基本可行解第一阶段结束后，修改最后的单纯形表。去掉人工变量和下面的列（也可保留，但人工变量不能再进基），把最后的判别数行按原来问题进行修正。其他不变。然后开始第二阶段迭代，即极大化目标函数。迭代过程如下：0103510000100002-11

6、0111-10020-1101103-20040101121000130-11011010026得到（4.2.5）的最优解（，）=（3，0），目标函数最优值例4.2.2用两阶段法求解下列问题35≤2=4=0≥0引进松弛变量，把上述问题化成标准形式，再引进人工变量，得到下列一阶段问题：=2+=4+=0≥0，…，6先用单纯形法解一阶段问题，迭代如下：35其中是目标函数中基变量的系数构成的维行向量，是上表中的第列，是上表中的右端列。-1211002-44-1010410-10010-34-200041001-20-3-210010-10010-10-

7、4-200035，取主元，经元消去得到下表：0100100-5-212010-10010再以为主元，进行主元消法，得到0100100101000这样，基变量均为原来的变量，得到原来的问题的一个基本可行解35再把表中人工变量对应的列去掉（也可保留，但人工变量不能再进基），并把判别数行增加进去。正如前面曾经指出过的那样，初表中的判别数和目标函数值利用定义来计算，即其中是目标函数中基变量的系数构成的维行向量，是上表中的第列，是上表中的右端列。第二阶段的初表如下：010100101000000-1此表已是最优表。最优解是35目标函数值的最优值例4.2.

8、3用两阶段法求解下列问题+=2+=10≥0引进人工变量。解第一阶段问题：+=4+=6+=235++=10≥0下面以表格形式给出迭代过程：2-11010