第三章 单纯形法(,两节).pptVIP

第三章 单纯形法 本章主要介绍求解线性规划问题的单纯形法及解的类型，其基本要求为： 1. 理解凸集的极点（顶点）与线性规划问题 解的关系。 2. 熟练掌握单纯形法的迭代过程和应用。 3. 熟悉线性规划问题的标准型掌握两阶段法 和大M法。 4.了解改进单纯形法。 知识结构 第一节 线性规划问题的几何意义 第一节 线性规划问题的几何意义 凸集定义的另外一种表示形式： 设X（1）、X（2） （X（1）≠X（2））是n维欧氏空间（高等数学中常用名词，参看文献（3）中的一个点集，任意两点X（1）、X（2）∈K 的连线上一切点[αX（1）+（1-α）X（2）] ∈K（0α1）,则称K为凸集。 请按如下思路理解：以X（1）、X（2））（X（1）≠X（2））为端点的线段上的任一点都可以表示为[αX（1）+（1-α）X（2）] （0α1）当α在（0，1）之间变化时，上式表示的点就在以X（1）、X（2）为端点的线段上滑动，（α=1/2时，在二维空间中（初等平面解析几何中），上式就是中点坐标）。这与前面的定义实质上是一致的。 第一节 线性规划问题的几何意义 2.极点: 设K是凸集，X∈K ；若X不能用不同的两点X(1) ∈K ， X(2) ∈K 的线性组合表示为X=αX（1）+（1-α）X（2） （0α1） ，则称此点是K的一个极点或顶点，其直观意义就是X不是K中任何线段的内点，也就是说点X不能在以K内的任意两点为端点的线段上。如三角形、长方体的顶点就是凸集的集点。 第一节 线性规划问题的几何意义 线性规划问题的解 1.可行解 ：满足线性规划问题全部约束条件的解。所有可行解的集合称为可行域。 2.最优解 ：在线性规划问题的可行解中，使目标函数值达到最优的解。 3.基本解及基本可行解 在线性规划问题约束条件方程中，由与约束条件个数相等的若干个系数列向量组成的满秩矩阵叫基本矩阵。 一个有n个变量m个约束（m≤n）的线性规划问题至多可以有Cnm个基本矩阵所谓满秩矩阵，就是给这个矩阵作行线性变换不会出现某一行元素 第一节 线性规划问题的几何意义 全为零的情况(与方程组有关的线性变换不考虑列变换)；所谓矩阵的行线性变换就是给矩阵的某一行元素同乘以一个非零常数或给矩阵的某一行同乘以非零常数后再加到另一行，过程与我们中学学过的解方程组的消元法完全一致。详细内容请参看文献（3）中与此有关的内容。 令不与基本矩阵中列向量对应的变量（这些变量就叫非基变量 ）为零后，约束方程中剩余的与基本矩阵对应的变量就可唯一求得（这些变量就叫基变量），求得的这个解就叫基本解（参看课本16页）。 简单的说，就是“通过基本矩阵求得的线性规划问题的解”。 第一节 线性规划问题的几何意义 基本解的形式是 X=（x1*, x2*,…, xm*,0,0,…,0） ， 基变量 非基变量 若每一个分量大于或等于零，这个解就叫基本可行解。 三、 凸集的极点与线性规划问题的基本可行解 定理1 约束条件为AX=b，X≥0线性规划问题的可行解 集是凸集。 定理3 线性规划问题的基本可行解 X对应于可行域D的极点。 第一节 线性规划问题的几何意义 定理4 线性规划问题若有可行解必有基本可行解。换句话说，线性规划问题的可行域D如为非空凸集，则必有极点。 定理5 线性规划问题若有最优解，则一定可以在可行域D的极点上达到。 注意：这并不是说，只有极点才能使目标函数值最大，其它点不能。而是说，如在其它点上使目标函数值达到最大，则一定可以找到一个极点X（m）使目标函数值达到此最大值。 有了定理5，求线性规划问题的最优解可不必在无穷多的可行解中有哪些信誉好的足球投注网站，只需在有限个基本可行解中有哪些信誉好的足球投注网站即可。虽然基本可行解至多有个，当n、m较大时， 仍是一个很大的数字。 第一节 线性规划问题的几何意义 例如: 当n=5，m=2，基本矩阵的个数可能为10个，所谓可能为，就说明还有一些不是，这还需要一个一个的判断。所以对比较大是线性规划问题用穷举法将所有的基本可行解都找出并计算其目标函数值，选取最优，计算量很大甚至是行不通的。著名的单纯形法用迭代法而不用穷举法很好地解决了这个问题。 第二节 单纯形法 本节主要介绍单纯形法的计算步骤及线性规划解的讨论方面的内容 第二节 单纯形法 二、基本过程及主要方法 1．如何