线性规划问题解的性质.ppt

《线性规划问题解的性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1例1（原图解法例2）maxS=X1+2X2X14X23X1+2X28X1,X20化为标准形并写出标准形中A，C，b,pj1§2.3线性规划问题解的性质一、几个基本概念（名词）1、可行解、基础可行解；最优解、基础最优解。设：LP问题：①满足约束条件的向量②若可行解x0=o或x0中非零分量xsxt…所对应A中的③满足minS=CX0的可行解x0称为最优解④满足minS=CX0的基础可行解x0称为基础最优解称为可行解列向量pspt…是线性无关时，称为基础可行解2123X201o324X1AB

2、CD由上节得解②最优解在BC线段上（无穷最优解）①凸多边形OABCD上任一点都是可行解如E（1，2）点对应解是可行解O（0，0）点对应解是基础可行解∵p3p4p5无关如F（3，5/2）点对应解是最优解B（2，3）点对应解是基础最优解●F（3，5/2）●E（1，2）32、凸集（P31）在二维集合中：矩形、三角形、园是凸集园环不是凸集在三维集合中：立方体、棱柱、四面体是凸集空心球不是凸集例如：若连接n维点集S中任意两点x(1),x(2)的线段仍在S内则称S为凸集。即：4说明：二维点A,B连线上点C可

3、视为定比内分点ABC×若：则：令：则：写成向量形式：（等号为端点）结论可推至n维5123X201o324X1ABCD最优解在BC线段上B(2,3)C(4,2)无穷最优解:S=063、极点（P31）极点例如：矩形、三角形、四面体的顶点，园周上的点都是极点若凸集S中的点x，不能成为S中任何线段的内点，则称x为S的极点。即：若对S中任意两点x(1),x(2)不存在使：72例2集合：判断此集合的图形是否为凸集？找出极点。5AOx1x2可见：此集合是凸集极点有：O（0，0）A（0，5）8二、线性规划问题的

4、解的性质性质1、若(LP)问题有可行解，则可行解集必是凸集证明：设解集：有任意两个解应证明当：也是属于S的解1）2）∴x∈S9性质2、LP问题的可行解集S中点x为极点的充分必要条件是x为基础可行解。证明：1）若x=0，由定义可知必是基础可行解。2）若x≠0设x的非零分量为xj1xj2…xjk（k≤n）在A中对应的列向量为pj1pj2…pjk要证明它们为线性无关，则x就是基础可行解。用反证法证明。书上P32（略）10性质3、LP问题的最优值可在极点上达到证明：设最优解为x0，最优值S（x0）=Cx

5、01）若x0=0，由定义可知必是极点。2）若x0≠0用性质2的证法，由x0构造x（1），x（2）使其中一个的非零分量比x0少一个，且仍是最优解重复数次总能找到一个最优解，使其非零分量（为最少）它们对应的列向量线性无关，即为极点。（略）11性质2：可行解集中点X是极点性质1：LP问题的可行解集一定是凸集性质3：LP若有最优解必定可以在其可行解集的X是基础可行解某个极点得到。12A中m个列向量中的线性无关组的个数更少，是有限的基础可行解与矩阵A中的一组线性无关的列向量相对应由定理3可知LP问题的最优

6、解可从有限的几个极点中去找。——单纯形方法：从一个极点迭代到另一个极点，判断并找出最优解。基础可行解即极点个数有限当约束条件为m个，n个变量时所以极点的个数（基础可行解个数）是有限的在A中的任取m列共有（不超过上数）13例如图解法例题2123X201o324X1ABCDR（A）=3其中：无关的：p1p2p3p1p2p4p2p3p5p1p4p5p3p4p5对应B点对应C点对应D点对应A点对应O点p1p2p5p1p3p4p2p3p4相关的：p1p3p5p2p4p5最优解必在五个极点中不可行解14P3

7、7作业P37　　题315