《线性规划问题解的基本性质和几何意义.ppt》由会员分享，可在线阅读，更多相关《线性规划问题解的基本性质和几何意义.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 3 3线性规划问题解的基本性质线性规划问题解的基本性质3.1解的基本概念 定义4 在(LP)的一个基基可可行行解解中，如果它的所有的基基变变量量都取正正值值（即非零分量恰为m个),则称它是非退化的解；反之，如果有的基变量也取零零值值，则称它是退退化化的解。一个(LP),如果它的所所有有基基可可行行解解都是非非退退化化的，就称该问题是非非退退化化的，否则就称它是退退化化的。类似的可以求出其他的基可行解。p24表3-1CDFGBEOA图图3-1l3l2l17465321100654321879x2x1 由此例可以看出：（1）线性规划问题的每个基本解是原问题两个边界约束方程交点，（2）每个基本可行
2、解对应于可行域的顶点。3.2 解的基本性质 定理1:(LP)的可可行行解解 是基基可可行行解解的充要条件是它的非零分量非零分量所对应的列向量线性无关。推论1:(LP)的满足约束方程组的任意一个解 是基基本本解解的充要条件是它的非非零零分分量量所对应的列向量线性无关列向量线性无关。定理2:若(LP)有可行解可行解，则它必有基可行解。定理3:若(LP)有最优解最优解，则一定存在一个基可行解是它的最优解。44线性规划问题解的基本性质线性规划问题解的基本性质1 1、凸集定义：凸集定义：设C是n维欧氏空间维欧氏空间En的一个集合，若C中的任意两点x(1),x(2)的连线上的一切点x仍在C中，则称C为凸集。即：若任意两点x(1),x(2)C，存在01 使得x=x(1)+(1-)x(2)C,则称为凸集.x=x(1)+(1-)x(2)C称为x(1),x(2)的凸组合。凸集凸集非凸集非凸集定理4 线性规划问题（）的可行解集 ，X=0是凸集凸集。定理5 线性规划问题的可行解集D中的点x是顶顶点点(极极点点)的充分必要条件是：x是基础可行解。(极点与基可行解的等价性定理)