线性规划解的性质.ppt

图解法 线性规划问题求解的几种可能结果 由图解法得到的启示 线性规划解的概念 凸集的概念 线性规划的基本定理,第二节 线性规划问题的解,线性规划问题解的概念,标准型 可行解:满足AX=b, X=0的解X称为线性规划问题的可行解。 最优解：使Z=CX达到最大值的可行解称为最优解。,A为mn阵 m n,基：若B是矩阵A中mm阶非奇异子矩阵（B0），则B是线性规划问题的一个基。不妨设：, j=1，2，,m 基向量。 ，j=1，2，,m 基变量。 , j=m+1,n 非基变量。,线性规划问题解的概念,线性规划的基、基变量、非基变量,=,=,目标函数,约束条件,行列式0 基矩阵,右边常数,求解,线性规划问题解的概念,基解：称上面求出的X解为基解。 基可行解：非负的基解X称为基可行解 可行基：对应基可行解的基称为可行基,线性规划问题解的概念,min,max,基变量x1、x2、x3，非基变量x4、x5、x6,基解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0， 0，0） 是基可行解，表示可行域的一个极点。,基变量x1、x2、x4，非基变量x3、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基础可行解，表示可行域的一个极点。,基变量x1、x2、x5，非基变量x3、x4、x6,基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基础解，但不是可行解，不是一个极点。,基变量x1、x2、x6，非基变量x3、x4、x5,基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基础可行解，表示可行域的一个极点。,基变量x2、x3、x4，非基变量x1、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基础解，但不是可行解。,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基础可行解，表示可行域的一个极点。,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基础解但不是可行解。,线性规划解的关系图,非可行解,可行解,基可行解,基解,线性规划问题解的概念,最优解？,例：求基解、基可行解、最优解。,线性规划问题解的概念,最优解,线性规划问题解的概念,解：,注：x1x3x4及x2x4x5所对应的系数不够成基,可行解、基础解和基础可行解举例,几何概念,代数概念,约束直线,满足一个等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集： 凸多边形,满足一组不等式约束的解,约束直线的交点,基解,可行域的极点,基可行解,目标函数等值线： 一组平行线,目标函数值等于一个常数的解,线性规划问题的几何意义,基本概念 凸集：,线性规划问题的几何意义,顶点:若K是凸集，XK；若X不能用不同的两点 的线性组合表示为： 则X为顶点.,凸集,线性规划问题的几何意义,例如：三角形的三个角点，实心圆圆周上的任一点，实心球球面上的任一点。,一个点是凸集，一段直线是凸集，平面上的凸多边形、实心圆，空间中的实心球、实心立方体等多面体，都是凸集。,从直观上讲，凸集没有凹入部分，其内部没有空洞。左图中的(a)(b)是凸集，(c)不是凸集。 右图中的阴影部分是凸集。 任何两个凸集的交集是凸集，见左图 (d),上图中（1）（2）是凸集，（3）（4）不是凸集,基本定理,证明:,定理1: 若线性规划问题存在可行域, 则其可行域: 是凸集.,只要验证X在D中即可,定理4：若可行域有界，线性规划 问题的目标函数一定可以在 其可行域的顶点上达到最优。,定理2：线性规划问题的基可性解X 对应于可行域D的顶点。 证明：反证法。分两步。,几点结论：,线性规划问题的可行域是凸集。 基可行解与可行域的顶点一一对应，可行域有有限多个顶点。 最优解必在顶点上得到。,图解法,9 8 7 6 5 4 3 2 1 0,x2,可行域为凸集 目标函数不同时 等值线的斜率不同 最优解在顶点产生,目标函数等值线的斜率,最优解,图解法,9 8 7 6 5 4 3 2 1 0,x2,可行域为凸集 目标函数不同时 等值线的斜率不同 最优解在顶点产生,目标函数等值线的斜率,最优解,图解法,9 8 7 6 5 4 3 2 1 0,x2,可行域为凸集 目标函数不同时 等值线的斜率不同 最优解在顶点产生,目标函数等值线的斜率,最优解,上述定理的一些有意义的启示：,线性规划的基本可行解和可行域的顶点是一一对应的（类似于坐标与点的对应关系！） 在可行域中寻找LP的最优解可以转化为只在可行域的顶点中找，从而把一个无限的问题转化为一个有限的问题。,线性规划理论的小结,1、一般意义上说： （1）如果线性规划问题有可行解，则一定有基本可行解。 （2）线性规划问题如果有最优解，则最优解一定可以从基本可行解中找得到。 （3）由于基本可行解的个数有限，所以经过有限次迭代，就一定能找到最优解。,2、从几何意义上说： （1） 基本解对应所有可行域边界延长线、坐标轴之间的交点； （2） 线性规划问题可行域中的每一个极点都对应着一个基本可 行解。 （3） 由于最优解必定要从基本可行解中寻找，所以所谓求解 线性规划问题，实际上就是比较极点处的目标函数值的 大小。 （4） 极点的个数是有限的(不大于 个)，那么只要经过有限 次寻找（枚举法）就一定能够找到基