线性规划问题解的性质

1、1,1,例1（原图解法例2）,化为标准形 并写出标准形中 A，C，b, pj,2,2.3,线性规划问题解的性质,一、几个基本概念（名词）,1、可行解、基础可行解；最优解、基础最优解。,设：LP问题：, 满足约束条件的向量, 若可行解 x0=o 或 x0 中非零分量 xs xt 所对应A中的, 满足 minS=CX0 的可行解 x0 称为 最优解, 满足 minS=CX0 的基础可行解 x0 称为 基础最优解,称为可行解,列向量 ps pt 是线性无关时，称为 基础可行解,3,由上节得解, 最优解在 BC 线段上（无穷最优解）, 凸多边形OABCD上任一点都是可行解,如 E（1，2）点对应解 是

2、可行解,O（0，0）点对应解,是基础可行解, p3 p4 p5无关,如 F（3，5/2）点对应解 是最优解,B（2，3）点对应解,是基础最优解,4,2、凸集（ P31）,在二维集合中：矩形、三角形、园是凸集,园环不是凸集,在三维集合中：立方体、棱柱、四面体是凸集,空心球不是凸集,例如：,若连接 n 维点集S中任意两点 x(1), x(2)的线段仍在S内,则称 S为凸集。,即：,5,说明：二维点 A,B,连线上点 C 可视为定比内分点,A,B,C,若：,则 ：,令 ：,则 ：,写成向量形式 ：,（等号为端点）,结论可推至 n 维,6,最优解在 BC 线段上,B(2,3) C(4,2),无穷最优解

3、:,S=0,7,3、极点 （P31）,极点,例如：矩形、三角形、四面体的顶点，,园周上的点都是极点,若凸集S中的点 x ，不能成为S中任何线段的内点，,则称 x 为 S 的极点。,即：若对 S 中任意两点x(1), x(2)不存在,使：,8,2,例 2 集合：,判断此集合的图形是否为凸集？找出极点。,5,A,O,可见：此集合是凸集,极点有：O（0，0）,A（0，5）,9,二、线性规划问题的解的性质,性质1、若(LP)问题有可行解，则可行解集必是凸集,证明：设解集：,有任意两个解,应证明当：,也是属于S的解,1）,2）, x S,10,性质2、LP问题的可行解集 S 中点 x 为极点,的充分必要

4、条件是 x 为基础可行解。,证明：1） 若 x = 0 ，由定义可知必是基础可行解。,2） 若 x 0,设 x 的非零分量为 xj1 xj2 xjk （kn）,在 A中对应的列向量为 pj1 pj2 pjk,要证明它们为线性无关，则 x 就是基础可行解。,用反证法证明。 书上 P32 （略）,11,性质3、LP问题的最优值可在极点上达到,证明：设最优解为 x0 ，最优值 S（ x0 ）= C x0,1） 若 x0 = 0 ，由定义可知必是极点。,2） 若 x0 0,用性质2的证法，由 x0 构造 x（1）， x（2）,使其中一个的非零分量比 x0 少一个，且仍是最优解,重复数次总能找到一个最优

5、解，使其非零分量（为最少）,它们对应的列向量线性无关，即为极点。,（略）,12,性质2：可行解集中点X是极点,性质1：LP问题的可行解集一定是凸集,性质3：LP若有最优解,必定可以在其可行解集的,X是基础可行解,某个极点得到。,13,A中m 个列向量中的线性无关组的个数更少，是有限的,基础可行解与矩阵 A中的一组线性无关的列向量相对应,由定理3可知,LP问题的最优解可从有限的几个极点中去找。,单纯形方法：从一个极点迭代到另一个极点，,判断并找出最优解。,基础可行解即极点个数有限,当约束条件为m个，n个变量时,所以极点的个数（基础可行解个数）是有限的,在A中的任取 m 列共有,（不超过上数）,14,例如图解法例题2,R（A）= 3,其中：无关的：,p1p2p3,p1p2p4,p2p3p5,p1p4p5,p3p4p5,对应B点,对应C点,对应D点,对应