第3章 线性规划 §4 单纯形方法 2013

1、实验实验o 时间：14周，周一下午5-8节（12月2号？查校历）o 地点：工程实训楼（具体到时候大屏幕会有指示）。第第3章章 线性规划线性规划Linear Programming 4 单纯形方法单纯形方法结合结合例2.4.1p60薛毅讲讲（同前上次课的例子）直接表上操作，单纯形表的样子提前。直接表上操作，单纯形表的样子提前。例(2.4.1p60，同例2.3.6,p46，薛毅)(在黑板上讲，书中也有主要步骤，也可参考)。 min -2x1 - 5x2 st x1 + 2x2 8 x1 4 x2 3 x1 , x2 0第一步，化为标准形min -2x1 - 5x2 st x1 + 2x2 + x3

2、 = 8 x1 + x4 = 4 x2 + x5 = 3 x1 , x2 , x3 , x4 , x5 0A = b =c = (-2,-5, 0, 0, 0)单纯形表对应线性规划的标准形o 用来表示一个线性规划问题，含有约束方程组和 目标函数（不含非负约束，目标函数也有变形）。o 例子（原来的）基变量基变量f - cTx = 0bA1210010010010018432500001000fx1x2x3x4x5RHSx3x4x5典式典式o 是线性规划的一种形式，它的单纯形表满足下面3个条件:第一，矩阵A中有一个基（矩阵），其基向量为 (0,., 1, .,0)T形式。第二，右边的b0。第三，目

3、标函数 f 行（首行）基变量对应的数为0。 典式典式 化为典式的形式后，可看出一个基本可行解 以及该解所对应的目标函数值。 该基（单位向量组成的这个）是一个可行基是一个可行基。4 单纯形(simplex)方法 重点内容！重点内容！o 已经讲过，可以在线性规划的基本可行解，也即可行域的顶点，中搜索最优解。o 单纯形方法是从已知线性规划的一个基本可行解开是从已知线性规划的一个基本可行解开始的（或可行基）开始的，始的（或可行基）开始的，然后找到目标函数值更小的基本可行解， 逐步找到最优的基本可行解。n 等价于从已知线性规划的一个可行基开始。等价于从已知线性规划的一个可行基开始。n 等价于从已知一个典

4、式开始。等价于从已知一个典式开始。o 以目标函数值下降下降为导向，同时满足非负约束。o 结合例子说明。基本可行解的改进改进o 设已知线性规划问题的一个基本可行解 ，找新的新的基本可行解，并且使目标函数值减小。换基换基，包括3步。o 1. 选择一个进基变量选择一个进基变量：选1个非基变量，变为基变量。方法：在大于0的检验数检验数中选一个(通常选值最大的)，令它所对应的变量进基，成为新的基变量。 k = max j | j0, j R， R是非基变量的下标集，则选择xk进基进基。在xk相应的检验数上加*标记。检验数的定义见下页检验数的定义见下页检验数，最优性条件o检验数或判别数检验数或判别数：是当

5、线性规划形式为典式时， 单纯形表中第一行中非基变量的对应的数。 检验数或判别数记为记为j, jR, R是非基变量下标集。 例中R=1, 2，1=2， 2=5。回上页（选进基变量）o 2. 选择出基变量，出基变量，即选择一个基变量，将它变为非基变量。 （一进一出，保持基变量个数恒定）设进基变量为xk，约束矩阵A中xk的系数aik，i 为行号,第 i 行右端常数为bi，若min bi /aik，aik 0 = br /ark (某个某个r)则第r行对应的原来的基变量被选为出基变量，出基变量，将成为非基变量。(进基变量新的取值为br /ark。把ark框/圈起来。)o 3. 换基换基（也叫转轴，旋转

6、）。（坐标系变换） 利用行的初等变换，把ark变为1，把ark所在列的其它元素(包括第一行的那个)都变为0。 化成了新的典式。得到了新的基本可行解(以及新的可行基，换基了),并使f的值变小了。重复这3步。 使用单纯形方法的求解线性规划的步骤使用单纯形方法的求解线性规划的步骤o化为标准形o设已知线性规划问题的一个基本可行解 (或典式，或者一个可行基)，先用行变换化为典式， 然后换基换基，以进行基本可行解的改进o 选择进基变量，或者已经找到最优解。o 选择出基变量，或判断为无(有限有限)最优解.o (最优解在无穷远处)o 换基。o 重复这3步，或找到最优解，或为无(有限有限)最优解.上面几个步骤中

7、会遇到的几种情况(1)第一步，选进基变量如果检验数中没有大于0的怎么办？这时该基本可行解已经是最优解了。结论结论1：线性规划形式为典式时，如果检验数全0, 则此时的基本可行解为最优解。 检验数全0称为最优性条件最优性条件。练习：下页例2.4.2 p62薛毅 有无穷多个最优解的情况 min -x1 - 2x2 st x1 + 2x2 8 x1 4 x2 3 x1 , x2 0结论结论2：线性规划形式为典式时，如果检验数全0, 并且有的检验数为0，则有无穷多个最优解。有一个这样类型的作业题。 这时以为以为0的检验数对应的非基变量为进基变量的检验数对应的非基变量为进基变量，然后选择出基变量、换基，又

8、可求出一个最优基本可行解（顶点）。两个最优两个最优顶点的连线段上的点都是最优解，有无穷多个顶点的连线段上的点都是最优解，有无穷多个。有时有最优解面.上面几个步骤中会遇到的几种情况(2)（自学，非重点）自学，非重点）第二步 选择出基变量若在约束矩阵A中进基变量的系数全0，怎么办？无(有限)最优解。结论结论2 线性规划形式为典式时，若某个检验数0,并且相应的变量在约束矩阵A中的系数全0，则该线性规划问题的最优解在无穷远处（无有最优解在无穷远处（无有限最优解）限最优解）。例（2.4.3p64薛毅，自学）o 会不会出现无可行解的情况？不会。因为已知一个基本可行解。练习（或再看一遍例题p60），是怎样求

9、解的。单纯形方法的几何意义o 单纯形方法是从已知的一个基本可行解（或典式）单纯形方法是从已知的一个基本可行解（或典式）出发，从一个基本可行解换到另一个基本可行解出发，从一个基本可行解换到另一个基本可行解（或典式）的过程，在这个过程中，目标函数值（或典式）的过程，在这个过程中，目标函数值 逐步减小，直到找到最优解（和最优目标函数值），逐步减小，直到找到最优解（和最优目标函数值），或者判定最优解在无穷远处。或者判定最优解在无穷远处。 几何上看几何上看：可用2维的情况予以说明(例1，下页) 。 基本可行解 即 可行域顶点。单纯形方法的不足和重要性o 只用只用单纯形方法并不能求解所有的线性规划问题。n

10、不是典式、基本可行解未知时，不能直接用。n是退化的线性规划(下页)时，有时会陷入循环。若陷入循环，则无法求解。o 要解任意一个线性规划，还要用一些小的技巧小的技巧 n大大M方法方法，两阶段方法(可得一个基本可行解)nBland防止循环的方法（求解退化LP问题6）o 单纯形方法单纯形方法是线性规划求解方法的核心核心， 而且实用效果很好。退化的线性规划o 基本解中若非0分量少于m个，称为退化的基本解退化的基本解,若非0分量为m个，称为非退化的基本解非退化的基本解。 （基本解的非0分量不可能多余m个）o 若线性规划所有的所有的可行基本解都是非退化的， 称线性规划为非退化的非退化的。否则为退化的退化的线性规划。 （书上的该定义