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

《2.3线性规划问题解的性质.ppt》由会员分享，可在线阅读，更多相关《2.3线性规划问题解的性质.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1例例1 1（原图解法例（原图解法例2 2）maxSmaxS=X=X1 1+2X+2X2 2 X X1 1 4 4 X X2 2 3 3 X X1 1+2X+2X2 2 8 8 X X1 1,X X2 2 0 0化为标准形化为标准形并写出标准形中并写出标准形中 A A，C C，b,b,p pj j12.32.3线性规划问题解的性质线性规划问题解的性质一、几个基本概念一、几个基本概念（名词）1 1、可行解、基础可行解；最优解、基础最优解。、可行解、基础可行解；最优解、基础最优解。设：LP问题：满足约束条件的向量 若可行解 x x0 0=o o 或 x x0 0 中非零分量 x xs s x xt

2、 t 所对应A中的 满足 minS=CX0 的可行解 x x0 0 称为 最优解最优解 满足 minS=CX0 的基础可行解 x x0 0 称为 基础最优解基础最优解称为可行解可行解列向量 ps pt 是线性无关时，称为 基础可行解基础可行解2123X201o324X1ABCD由上节得解 最优解在 BC 线段上（无穷最优解）凸多边形OABCD上任一点都是可行解如 E E（1，2）点对应解 是可行解可行解 O O（0，0）点对应解是基础可行解基础可行解 p3 p4 p5无关如 F F（3，5/2）点对应解 是最优解最优解 B B（2，3）点对应解是基础最优解基础最优解F（3，5/2）E（1，2）

3、32 2、凸集凸集（P31）在二维集合中：矩形、三角形、园是凸集在二维集合中：矩形、三角形、园是凸集园环不是凸集园环不是凸集在三维集合中：立方体、棱柱、四面体是凸集在三维集合中：立方体、棱柱、四面体是凸集空心球不是凸集空心球不是凸集例如：若连接 n 维点集S中任意两点任意两点 x x(1)(1),x x(2)(2)的线段的线段仍仍在在S S内内则则称称 S S为凸集。为凸集。即：即：4说明说明：二维点：二维点 A,BA,B连线上连线上点点 C C 可视为定比内分点可视为定比内分点ABC若：若：则则 ：令令 ：则则 ：写成向量形式写成向量形式 ：（等号为端点）（等号为端点）结论可推至结论可推至

4、n n 维维5123X201o324X1ABCD最优解在最优解在 BC BC 线段上线段上B(2,3)C(4,2)无穷最优解无穷最优解:S=063 3、极点极点 （P31）极点例如：矩形、三角形、四面体的顶点，例如：矩形、三角形、四面体的顶点，园周上的点都是极点园周上的点都是极点若凸集若凸集S S中的点中的点 x x，不能成为不能成为S S中任何线段的内点，中任何线段的内点，则称则称 x x 为为 S S 的极点的极点。即：若对即：若对 S S 中任意两点中任意两点x x(1)(1),x x(2)(2)不存在不存在使：使：72例例 2 2 集合：集合：判断此集合的图形是否为凸集？找出极点。判断

5、此集合的图形是否为凸集？找出极点。5AOx1x2可见：此集合是凸集可见：此集合是凸集极点有：极点有：O O（0 0，0 0）A A（0 0，5 5）8二、线性规划问题的解的性二、线性规划问题的解的性质质性质性质1 1、若、若(LP)(LP)问题有可行解，则可行解集必是凸集问题有可行解，则可行解集必是凸集 证明：设解集：证明：设解集：有有任意两个解任意两个解应应证明当：证明当：也是属于也是属于S S的解的解1）2）x Sx S9性质性质2 2、LPLP问题的可行解集问题的可行解集 S S 中点中点 x x 为极点为极点的充分必要条件是的充分必要条件是 x x 为为基础可行解。基础可行解。证明：证

6、明：1 1）若若 x=x=0 0，由定义可知必由定义可知必是是基础可行解。基础可行解。2 2）若若 x x 0 0设设 x x 的非零的非零分量为分量为 x xj1 j1 x xj2j2 x xjkjk （knkn）在在 A A中对应的列向量为中对应的列向量为 p pj1j1 p pj2j2 p pjkjk 要证明它们为要证明它们为线性无关，线性无关，则则 x x 就就是是基础可行解。基础可行解。用用反证法证明。反证法证明。书上书上 P32 P32 （略）（略）10性质性质3、LP问题的最优值可在问题的最优值可在极点极点上达到上达到证明：设最优解为证明：设最优解为 x x0 0 ，最优值最优值

7、 S S（x x0 0 ）=C=C x x0 0 1 1）若若 x x0 0=0 0，由定义可知必由定义可知必是极点是极点。2 2）若若 x x0 0 0 0用用性质性质2 2的证法，由的证法，由 x x0 0 构造构造 x x（1 1），x x（2 2）使使其中一个的非零分量比其中一个的非零分量比 x x0 0 少一个，且仍是最优解少一个，且仍是最优解 重复数次总能找到一个最优解，使其非零分量重复数次总能找到一个最优解，使其非零分量（为最少）（为最少）它们对应的列向量线性无关，即为它们对应的列向量线性无关，即为极点。极点。（略）略）11性质性质2：可行解集中点：可行解集中点X是极点是极点 性

8、质性质1：LP问题的问题的可行解集一定是凸集可行解集一定是凸集性质性质3：LP若有若有最优解最优解必定可以必定可以在在其可行解集的其可行解集的X是基础可行解是基础可行解某个极点某个极点得到。得到。12A A中中m m 个列向量中的线性无关组的个数更少，是有限的个列向量中的线性无关组的个数更少，是有限的基础可行解与矩阵基础可行解与矩阵 A A中的一组线性无关的列向量相对应中的一组线性无关的列向量相对应由定理3可知LPLP问题的最优解可从有限的几个极点中去找。问题的最优解可从有限的几个极点中去找。单纯形方法：从一个极点迭代到另一个极点，单纯形方法：从一个极点迭代到另一个极点，判断并找出最优解。判断

9、并找出最优解。基础可行解即基础可行解即极点极点个数有限个数有限当约束条件为当约束条件为m m个，个，n n个变量时个变量时所以极点的个数（基础可行解个数）是有限的所以极点的个数（基础可行解个数）是有限的在在A A中的任取中的任取 m m 列共有列共有（不超过上数）13例如图解法例题例如图解法例题2 2123X201o324X1ABCDR R（A A）=3=3其中：无关的：其中：无关的：p1p2p3p1p2p4p2p3p5p1p4p5p3p4p5对应B点对应C点对应D点对应A点对应O点p1p2p5p1p3p4p2p3p4相关的：相关的：p1p3p5p2p4p5最优解必最优解必在在五个极点中五个极点中不不可可行行解解14P37作作 业业P37题题 315