基础运筹学教程（第三版）- 第一章-3 单纯形法.ppt

**第一章线性规划*§1-3单纯形法一.线性规划的基本定义二.线性规划解之间的关系三.线性规划解的性质四.单纯形法引例五.单纯形法(SM)原理六.单纯形法的表算七.单纯形法的进一步讨论八.单纯形法的矩阵描述*对于标准的线性规划问题：以及其矩阵表达形式：我们首先给出几个基本的概念和定义。一.线性规划的基本定义*可行解(feasiblesolution)：满足约束条件(2),(3)的解X=(x1,…,xn)T,称为线性规划问题的可行解。可行域(feasibleregion)：全部可行解的集合称为可行域。最优解(optimalSolution)：使目标函数(1)达到最大值的可行解称为最优解。*基(basis)：约束方程的系数矩阵A的秩为m，且mn。设A=[BN]，B是A中m?m阶矩阵,N是m×(n-m)阶矩阵，其中B是非奇异子矩阵，即|B|≠0，也就是说B是A中m个线性无关向量组，则称B是A的一个基。（问题：同一个A有多少个基？）根据A的划分，其对应的变量X也可划分为：(XB,XN)T=(x1,x2,…,xm,xm+1,…,xn)T基变量(basicvariables)：不失一般性，设B是A的前m列，即B=(p1,p2,…,pm），则基B相对应的变量XB=(x1,x2,…,xm)T称为基变量；*非基变量(non-basicvariables)：A中后N列所对应的变量XN=(Xm+1,…,Xn)T称为非基变量。基解(basicsolution)：令所有非基变量等于零，则（x1,x2,…xm,0,…,0)T称为基解。基可行解（basicfeasiblesolution）:基解可正可负，负则不可行（违背非负性约束条件）。因此，称满足所有约束条件的基解为基可行解(线性规划的基可行解对应可行域的顶点)。*可行基：对应于基可行解的基称为可行基。退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。基解的数目：最多Cmn=n!/m!(n-m)!*例题：找出下列线性规划问题的所有基本解，指出哪些是基本可行解。解：这里m=2,n=4，其可能的基解个数为：最多有6个基，及其对应的基解。*设：因为：所以，B1=(P1,P2)构成基，令x3=x4=0,得基本解X1=(-4,5.5,0,0)T*B1=(P1,P2)构成基，令x3=x4=0,得基本解：X1=(-4,5.5,0,0)T同理可得：B2=(P1,P3)构成基，令x2=x4=0,得基本解：X2=(2/5,0,11/5,0)T；B3=(P1,P4)构成基，令x2=x3=0,得基本解：X3=(-1/3,0,0,11/6)T；B4=(P2,P3)构成基，令x1=x4=0,得基本解：X4=(0,1/2,2,0)T；B5=(P2,P4)构成基，令x1=x3=0,得基本解：X5=(0,-1/2,0,2)T；B6=(P3,P4)构成基，令x1=x2=0,得基本解：X6=(0,0,1,1)T。其中：X2、X4、X6为基本可行解（称满足所有约束条件的基解为基可行解）。X2、X4、X6所对应的B2、B4和B6称为可行基。*二.线性规划解之间的关系可行解与最优解最优解一定是可行解，但可行解不一定是最优解。2.可行解与基解基解不一定是可行解，可行解也不一定是基解。3.可行解与基可行解基可行解一定是可行解，但可行解不一定是基可行解。*4基解与基可行解基可行解一定是基解，但基解不一定是基可行解。5最优解与基解最优解一定是基解，基解也不一定是最优解。6问题：最优解与基可行解？*各解之间的关系可以用下图表示：非可行解可行解基可行解基本解*三.线性规划解的性质定理1：线性规划的可行域R是一个凸集，且有有限个顶点。——线性规划问题的可行域是一个凸集。定理2：X是线性规划可行域R顶点的充要条件是X是线性规划的基本可行解。—