第3章(1) 单纯形法.doc

第3章 单纯形法本章介绍求解线性规划问题的单纯形法，它是美国学者丹捷格（George Dantzig）在1947年提出来的，是求解线性规划问题的最有效的方法之一。为方便讨论，在第一节首先建立线性规划问题的标准形，然后在第二节讨论线性规划基本解的概念，第三节从几何概念和解释的角度介绍单纯形法，最后，介绍单纯形法的代数表达式和单纯形表。3.1线性规划问题的标准形式 线性规划问题的标准形式：max s.t. （3.1）其中 或简记为若记 ， ，则线性规划的标准形式还可以表示为如下几种形式：（1） 矩阵形式 （2） 向量形式其中“0”表示零向量。线性规划的一般形式转化为标准形式的方法（1） 目标函数的转化：若原问题的目标函数是求最小化，即 则可将目标函数乘以，等价转化为求如下最大化问题：（2） 不等式约束转化为等式约束：如果约束条件是线性不等式则通过引入松弛变量，将其转化为等价的等式约束条件 类似地，如果约束条件是线性不等式则通过引入剩余变量，将其转化为等价的等式约束条件（3） 变量约束的转换 如果原问题中某个变量是自由变量（即无非负限制）则可令代入原问题，即在原问题中将用两个非负变量之差代替。例1： 将下列线性规划问题化为标准形式为自由变量 解：原问题等价的线性规划标准形式：3.2线性规划问题的基本解对于线性规划问题的标准形式其中为n维行向量，分别为n维和m维列向量；为矩阵。假定矩阵A的秩为m，且m n.。A中任意一个阶可逆子方阵B (即)，称为线性规划问题的一个基阵或基。若基阵称为基向量，相应决策变量为基变量，A中其余的列向量（不在B中）称为非基向量，对应的决策变量称为非基变量。例2：第一章的例1中的线性规划问题引入松弛变量化为如下标准形式：故约束系数矩阵由于线性无关是可逆的。故是线性规划的一个基。对于基，是基变量，是非基变量。又由于线性无关也是线性规划的一个基。对于基，是基变量，是非基变量。对于线性规划的标准形式，当基确定以后，相应的基变量和非基变量也就确定，我们可以将系数矩阵写成分块的形式：其中，表示非基变量对应列向量构成的子矩阵。将基变量组成的向量记为，非基变量组成的向量记为，则X也可以写成分块形式：因此，约束方程组变为由于可逆，则存在，将左乘以上式的两边得移项后得 事实上，对约束方程组，可以看作一组独立变量，它可以取任意的值，令，则，此时约束方程组有一个特殊形式的解称为线性规划的基本解。由以上讨论可以看出，线性规划的基本解实际上是在约束方程组中将非基变量看作独立的自由变量并令其取值为0后，解方程组得出的解；当基确定时，基本解也唯一确定了。由于基可以是中任意m阶的可逆子矩阵，即它的列是从A中n列中选出的线性无关的m列，其选法最多有，故基的个数和基本解的个数均不会超过个。基本解满足约束方程，但不一定是可行解。因为，它不一定满足非负约束。我们把满足非负约束的基本解，即的基本解称为基本可行解或基可行解，此时对应的基B称为可行基。同理，线性规划问题基可行解的数目不超过个。下面我们给出例2中基阵、基本解、基本可行解以及可行区域顶点之间的对应关系，如表3-1所示：表3-1基阵B基变量基本解两个边界约束的交点可行域的顶点是否基本可行解是否是不可行基（）（）轴轴交点O(0,0)是是（）（）轴与的交点E(0,4)是是（）（）轴与的交点D(0,6)否否（）（）与的交点C(3,4)是是（）（）与的交点F(6,4)否否（）（）与的交点B(6,2)是是（）（）轴与的交点A(9,0)否否（）（）轴与的交点C(6,0)是是CDFGBEOA图3-1l3l2l17465321100654321879x2x1另外，A的另外两个n阶子矩阵（）和（）不可逆，不能构成基阵。由此例可以看出：（1）线性规划问题的每个基本解是原问题两个边界约束方程交点，（2）每个基本可行解对应于可行域的顶点，（3）相邻的顶点共享一个边界约束方程，（4）相邻顶点对应的基阵中只有一个基向量不同，其余两个相同。事实上，对于一般的线性规划问题（m个约束，n个决策变量）有类似的特性：（1） 每个基本可行解对应于可行域的顶点。（2） 可行域中相邻的两个顶点对应基阵中只有一个基向量不同，其