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

1 §4.2 两阶段法与大 M法————初始可行基的求法 求解线性规划的步骤是： 1） 已知一个初始基本可行解 2） 从初始基本可行解出发，写出单纯型表，求出进基离基变量，做主元消去法，求出一个新的基本可行解且使目标函数值得到改善。 3） 判断当前基本可行解是否是最优解 那末，当观察不出来初始基本可行解时，怎么办？下面介绍的方法是几种求初始基本可行解的方法 4.2.1 两 阶 段 法 min cx ts. bAx  x ≥0 其中 A 是nm矩阵，b ≥0。若 A 中有 m阶单位矩阵，则初始基本可行解立即得到。比如，NIAm,，那么 2 0bxxxNB 就是一个基本可行解。若A 中不包含m 阶单位矩阵，就需要用某种方法求出一个基本可行解。 介绍两阶段法之前，先引入人工变量的概念。 设A 中不包含m阶单位矩阵，为使约束方程的系数矩阵中含有m阶单位矩阵，把每个方程增加一个非负变量，令 bxAxa  （4.2.2） x≥0 ，ax≥0 即 bxxIAam),( （4.2.3） x≥0 ，ax ≥0 3 显然， bxxa0 是（4.2.3）的一个基本可行解。 向量ax≥0 是人为引入的，它的每个分量成为人工变量。人变量与前面介绍过的松弛变量是两个不同的概念。松弛变量的作用是把不等式约束改写成等式约束，改写前后的两个问题是等价的。因此，松弛变量是“合法”的变量。而人工变量的引入，改变了原来的约束条件从这个意义上讲，它们是“不合法”的变量。 第一阶段是用单纯形方法消去人工变量（如果可能的话）： min aT xe ts.bxAx （4 .2.4） 4 x≥0 ，ax≥0 其中Te)1,,1,1(是分量全是 1 的m维列向量， Tmnnaxxx),,(1是 人 工 变量构成的m 维列向量。 由于bxxa  ,0是（4 .2.4）的一个基本可行解，目标函数值在可行域上有下界，因此问题（4 .2.4）必存在最优基本可行解。 求解（4 .2.4），设得到的最优基本可行解是TaTT xx),(，此时必 有下列三种情形之一： 1 . 0ax这时（4 .2.1）无可行解。因为如果（4 .2.1）存在可行解 xˆ 则 5 0ˆxxxa 是（4 .2.4）的可行解。在此点，问题（4 .2.4）的目标函数值 00ˆ0Texf＜aT xe 而aT xe是目标函数值的最优值，矛盾。 2 . 0ax且ax 的分量都是非基变量。这时，m个基 变 量 都 是原 来 的变 量 ， 又 知 ...