《运筹学—104线性规划的基本定理.ppt》由会员分享，可在线阅读，更多相关《运筹学—104线性规划的基本定理.ppt（24页珍藏版）》请在三一文库上搜索。
1、,信息系 刘康泽,线性规划的基本定理,1、基矩阵: 若A中的mm子矩阵B有 r (B)m ， 则称B是LP问题的一个基矩阵（简称为基）。,当 mn 时，基矩阵唯一，当 m n 时，基矩阵就可能有多个，但数目不超过 个。,线性规划的基本定理,设LP问题的标准型:,约束系数矩阵A是mn 矩阵，mn ，并且 r (A)m，于是A中至少有一个mm子矩阵B，使得：r (B)m。,一、几个概念,约束方程的系数矩阵为：,【例】设,易看出 r（A）=2，2 阶子矩阵有 = 10个，而基矩阵只有9个，,由线性代数知，基矩阵B必为非奇异矩阵并且 | B |0。当矩阵B的行列式等式零，即 | B |0 时就不是基。
2、,2、基向量: 当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为 基向量，其余列向量称为非基向量。,3、基变量: 基向量对应的变量称为基变量，非基向量对应的变量称为非基变量。,例如：基B2的对应的基向量是A中的第一列和第四列，其余列向量是非基向量，x1 , x4是基变量，x2 , x3 , x5是非基变量。,x1 x4,5、可行解: 称满足Axb，且x0的解为LP问题的可行解。,【注】基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。,4、基解: 对于某一确定的基B，令所有的非基变量等于零 ，求出 Axb 的解，称这组解为LP问题的关于基 的基本解 。（简称基解）
3、,6、基可行解： 若基解同时又是可行解， 则称为是基可行解。基可行解对应的基称为可行基。,显然，只要基解中的基变量满足非负要求，那么这个基解就一定是基可行解。,因 |，由克菜姆法则知，x1 , x2有唯一解 则关于1的基解为:,同理： 是关于9 的基解。,x1 x2,在 中x1 0，因此它不是可行解，也当然不是基可行解。,【注】可行解不一定是基解，当然不一定是基可行解。,关于2基解为,例如： 是LP的可行解。,对2来说，x1 , x4 为基变量，令非基变量 x2 , x3 , x5为零，,但它不是任何基的基解。,x1 x4,得到:,7、最优解 满足Axb，x0的可行解，且使得目标函数达到最大值
4、就是最优可行解（简称最优解）。,例如：可行解 是最优解。,【注】最优可行解不一定是基解。（因可行解不一定是基解）,9、最优基: 基最优解对应的基称为最优基，如上述B3就是最优基，最优基也是可行基。,8、基最优解 : 最优解是基解称为基最优解。,例如：可行解 是最优解。又是对应B3的基解，因此它是基最优解。,当最优解唯一时，最优解亦是基最优解，当最优解不唯一时，则最优解不一定是基本最优解。例如右图中线段 上的点都为最优 解时，Q1点及Q2点是基最优解,但线段 的内点也是最优解，而不是基最优解。,与基向量 相对应的变量为,不妨设前m个变量的系数列向量是线性无关的，则约束条件可写为,一般地: 设,或
5、,令非基变量为0，则,利用克莱姆法则可得一个基解：,这个解的非零分量的个数不大于方程个数 m.,特别的: 若,注意到: 这个特别情形中的约束系数矩阵之中对应基变量的基阵是单位矩阵,例如:问题,对应基阵,基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示：,例如,B点和D点是可行解,不是基本解;C点是基本可行解;A点是基本最优解,同时也是最优解、基本可行解、基本解和可行解。,二、线性规划的基本定理,【定理1】（LP问题的基本定理）设标准形式的线性规划问题 ,【引理】 线性规划问题中 为基可行解的充要条件是 的正分量所对应的系数列向量是线性无关的。,（1）若问题存在一个可行解，则必存在一
6、个基可行解；,（2）若问题存在一个最优可行解，则必存在一个最优的基可行解 (基最优解)。,定理1给了我们一个启示，寻求最优解不是在可行解域的无限个可行解中去找，而只需要在有限个基可行解中去寻求就行了，而基可行解的数目是有限的，基可行解不超过 个。 下一节将介绍的单纯形算法就是一种在基可行解中去寻求最优解的有效方法。,1 、凸集：设K是n维欧氏空间的一个点集，对任意两点,则称K是一个凸集。,就是以 为端点的线段方程，点 x 的位置由 的取值确定，,都是凸集,三、LP问题的几何特性,实心立方体, 实心圆，实心球体，实心椭球体，圆锥等都是凸集。而空心球体不是凸集。从直观上讲，凸集没有凹入部分，且其内
7、部也没有空洞。,都不是凸集,【定理2】 若线性规划的可行解域 K 非空,则K是一个凸集.,【注1】若K是一个凸集，a是一个实数，则a K也是一个凸集。,【注2】若K，L都是凸集，则 也是凸集。,【注3】若K，L都是凸集，则 也是凸集。,【注4】若K，L都是凸集，则 不一定是凸集。,不是凸集,【注5】,换句话说：若 x 不可能成为 K 中的某一线段的内点，只能是K中某一线段的端点。则x 就是 K 的一个极点。,例如：矩形、三角形、凸多面体的顶点都是极点；圆域的圆周、球体的球面上的点都是极点。,【定理3】设 K 是LP问题的可行解集合，则点 x是 K 的极点的充要条件为 x 是LP问题的基可行解.
8、,即: LP问题的基可行解对应于可行域的极点。,定理3刻划了可行解域的极点与基可行解的对应关系，一个极点对应一个基可行解，反之，基可行解一定对应一个极点，但它们并非一一 对应，有可能两个或几个基可行解对应于同一极点（退化基可行解时）。,【定理4】若LP问题有最优解，则最优值一定可以在可行解集合的某个极点上到达，最优解就是极点的坐标向量。,例,【推论1】 若LP问题的可行解集非空且有界，则最优解一定可以在可行解域的极点达到。,LP问题的所有可行解构成的集合是凸集（也可能为无界域），但它们只有有限个极点；LP问题的每个基可行解对应可行域的一个极点；若LP问题有最优解，必定可在某极点（顶点）处得到。显然顶点数目是有限的 (它不超过 个)，,若可行解集无界，则LP问题可能有最优解，也可能没有最优解。,【推论2】若LP问题的最优解在可行解域的 t 个极点达到，则在这些极点的凸组合上也达到最优解。,极点、最优解,极点的凸组合仍是最优解,极点、最优解,.,.,无界解(无最优解),