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