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

1 §2.3 * * 例1（原图解法例2） maxS = X1 + 2X2 X1? 4 X2 ? 3 X1 +2X2 ? 8 X1 , X2 ?0 化为标准形 并写出标准形中 A，C，b, pj 线性规划问题解的性质 一、几个基本概念（名词） 1、可行解、基础可行解；最优解、基础最优解。 设：LP问题： ① 满足约束条件的向量 ② 若可行解 x0=o 或 x0 中非零分量 xs xt …所对应A中的 ③ 满足 minS=CX0 的可行解 x0 称为 最优解 ④ 满足 minS=CX0 的基础可行解 x0 称为 基础最优解 称为可行解 列向量 ps pt … 是线性无关时，称为 基础可行解 1 2 3 X2 0 1 o 3 2 4 X1 A B C D 由上节得解 ② 最优解在 BC 线段上（无穷最优解） ① 凸多边形OABCD上任一点都是可行解 如 E（1，2）点对应解 是可行解 O（0，0）点对应解 是基础可行解 ∵ p3 p4 p5　无关 如 F（3，5/2）点对应解 是最优解 B（2，3）点对应解 是基础最优解 ● F（3，5/2） ● E（1，2） 2、凸集（ P31） 在二维集合中：矩形、三角形、园是凸集 园环不是凸集 在三维集合中：立方体、棱柱、四面体是凸集 空心球不是凸集 例如： 若连接 n 维点集S中任意两点 x(1), x(2)的线段仍在S内 则称 S为凸集。 即： 说明：二维点 A,B 连线上点 C 可视为定比内分点 A B C × 若： 则 ： 令 ： 则 ： 写成向量形式 ： （等号为端点） 结论可推至 n 维 1 2 3 X2 0 1 o 3 2 4 X1 A B C D 最优解在 BC 线段上 B(2,3) C(4,2) 无穷最优解: S=0 3、极点 （P31） 极点 例如：矩形、三角形、四面体的顶点， 园周上的点都是极点 若凸集S中的点 x ，不能成为S中任何线段的内点， 则称 x 为 S 的极点。 即：若对 S 中任意两点x(1), x(2)不存在 使： 2 例 2 集合： 判断此集合的图形是否为凸集？找出极点。 5 A O x1 x2 可见：此集合是凸集 极点有：O（0，0） A（0，5） 二、线性规划问题的解的性质 性质1、若(LP)问题有可行解，则可行解集必是凸集 证明：设解集： 有任意两个解 应证明当： 也是属于S的解 1） 2） ∴ x∈ S 性质2、LP问题的可行解集 S 中点 x 为极点 的充分必要条件是 x 为基础可行解。 证明：1） 若 x = 0 ，由定义可知必是基础可行解。 2） 若 x ≠ 0 设 x 的非零分量为 xj1 xj2 … xjk （k≤n） 在 A中对应的列向量为 pj1 pj2 … pjk 要证明它们为线性无关，则 x 就是基础可行解。 用反证法证明。 书上 P32 （略） 性质3、LP问题的最优值可在极点上达到 证明：设最优解为 x0 ，最优值 S（ x0 ）= C x0 1） 若 x0 = 0 ，由定义可知必是极点。 2） 若 x0 ≠ 0 用性质2的证法，由 x0 构造 x（1）， x（2） 使其中一个的非零分量比 x0 少一个，且仍是最优解 重复数次总能找到一个最优解，使其非零分量（为最少） 它们对应的列向量线性无关，即为极点。 （略）