线性规划和单纯形法.ppt

设线性规划的标准型minZ=CX（1.1）AX=b（1.2）X≥0（1.3）式中A是m×n矩阵，m≤n并且r（A）=m，显然A中至少有一个m×m子矩阵B，使得r（B）=m。基(basis)A中m×m子矩阵B并且有r（B）=m，则称B是线性规划的一个基（或基矩阵basismatrix）。当m=n时，基矩阵唯一，当mn时，基矩阵就可能有多个，但数目不超过【例1.14】线性规划【解】约束方程的系数矩阵为2×5矩阵求所有基矩阵。容易看出r(A)=2，2阶子矩阵有C52=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基矩阵只有9个，即0102由线性代数知，基矩阵B必为非奇异矩阵并且|B|≠0。当矩阵B的行列式等于零（即|B|=0）时就不是基当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基向量(basisvector)，其余列向量称为非基向量基向量对应的变量称为基变量(basisvariable)，非基向量对应的变量称为非基变量在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。可行解(feasiblesolution)满足式（1.2）及（1.3）的解x=（x1,x2…，xn)T称为可行解。基本可行解(basisfeasiblesolution)若基本解是可行解则称为是基本可行解（也称基可行解）。例如，与X=(0，0，0，3，2)都是例1的可行解。基本解(basissolution)对某一确定的基B，令非基变量等于零，利用式（1.２）解出基变量，则这组解称为基Ｂ的基本解。最优解(optimalsolution)满足式（1.1）的可行解称为最优解，即是使得目标函数达到最大值的可行解就是最优解，例如可行解是例2的最优解。非可行解(Infeasiblesolution)无界解(unboundsolution)显然，只要基本解中的基变量的解满足式（1.３）的非负要求，那么这个基本解就是基本可行解。在例1.13中，对Ｂ１来说，x1,x2是基变量，x3,x4，x5是非基变量，令x3=x4=x5=0，则式（1.２）为对B2来说，x1,x4,为基变量，令非变量x2,x3,x5为零，由式（1.2）得到，x4=4，因|B1|≠０，由克莱姆法则知，x1、x2有唯一解x1＝2/5,x2=1则基本解为由于是基本解，从而它是基本可行解，在中x10,因此不是可行解，也就不是基本可行解。反之，可行解不一定是基本可行解例如满足式（1.2）～（1.3），但不是任何基矩阵的基本解。基本解为可行基基可行解对应的基称为可行基；最优基基本最优解对应的基称为最优基；如上述B3就是最优基，最优基也是可行基。当最优解唯一时，最优解亦是基本最优解，当最优解不唯一时，则最优解不一定是基本最优解。例如右图中线段的点为最优解时，Q1点及Q2点是基本最优解,线段的内点是最优解而不是基本最优解。基本最优解最优解是基本解称为基本最优解。例如，满足式（1.1）~(1.3)是最优解,又是B3的基本解,因此它是基本最优解。基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示：基本最优解基本可行解可行解最优解基本解例如,B点和D点是可行解,不是基本解;C点是基本可行解;A点是基本最优解,同时也是最优解、基本可行解、基本解和可行解。【定理1.2】线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解。线性规划的基本定理【定理1.1】若线性规划可行解K非空,则K是凸集。01定理1.2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点（退化基