线性规划解的概念.ppt

线性规划解的概念 第一页，共二十六页，2022年，8月28日 图解法 对二维问题，可作出约束的图，简单直观地理解线性规划的解。 例 考察线性规划问题 等值线 x+3y=C 可行域 最优解 继续 第二页，共二十六页，2022年，8月28日 解的概念 可行解(feasible solution) ：满足线性规划问题(LP)的所有约束条件的解，称为线性规划问题的一个可行解。 可行域：(LP)的所有可行解组成的集合K称为(LP)的可行域。若可行域为空，则称不可行。对标准型线性规划问题，其可行域为 最优解(optimal solution) ：可行域中每个可行解都对应一个目标值，其中对应的目标函数值最小的可行解x*，称为(LP)的最优解，也称为(LP)的解。即 最优值：最优解对应的目标值称为最优值。 第三页，共二十六页，2022年，8月28日 基 设 为满秩矩阵(秩为m)， 是A中的非奇异子矩阵 ，则称B为（LP)的一个基。 基变量与非基变量 B是由A的m个线性无关的列组成，对应的变量称为基变量，剩下的变量称为非基变量。 基解 令非基变量变量等于0，可得线性方程组的一个解，称为基解(basic solution). 基可行解 若基解还是可行的，即满足非负性条件，则称为基可行解(basic feasible solution 简记为bfs)。 第四页，共二十六页，2022年，8月28日 基解的个数 非退化的基可行解：若基变量全部为正。 否则称为退化的基可行解，即有基变量为0 可行解 基解 基可 行解 非可行解 第五页，共二十六页，2022年，8月28日 例 求出线性规划问题 的全部基解，指出哪些是可行的。图解法 第六页，共二十六页，2022年，8月28日 线性规划解的几种可能情况 无可行解 可行域为空集，约束中存在矛盾方程。 有唯一的最优解（通常的情况），必是可行域的顶点。 有无穷多个最优解。 有可行解但无最优解 可行域必无界。 第七页，共二十六页，2022年，8月28日 §1.3线性规划问题的几何意义 第八页，共二十六页，2022年，8月28日 基本概念 凸集 设K为n维线性空间的一点集，若对K中任意两点x,y，及任意的 ，有 则称K为凸集。 规定空集和单点集为凸集。 第九页，共二十六页，2022年，8月28日 例 超平面 和半空间 都是凸集。 凸组合 设 为 中的点， 为满足下列条件的一组实数 则称 为 的凸组合。 极点 设K为凸集， ，若x不能表示成K中不同的两点的凸组合，则称x为K的一个极点(顶点)。 第十页，共二十六页，2022年，8月28日 基本定理 定理1 任意一组凸集的交集仍为凸集。 定理2 线性规划问题的可行域是凸集。 引理1 线性规划问题的可行解 为基可行解的充要条件是其正分量所对应的系数列向量是线性无关的。 证明： 必要性 若x是基解，由定义，正分量对应的列线性无关。 充分性 若正分量对应的列线性无关，则个数不超过m，若=m,则是基，若<m,可扩充成基。 第十一页，共二十六页，2022年，8月28日 定理3 线性规划问题的基可行解对应于可行域的顶点。 证明：若x是基可行解，设前m个分量为基变量，但不是极点，则存在x1,x2,0<λ<1, x=λx1 +(1-λ) x2.?x1,x2的后n-m个分量为0。 若x是极点，但不是基可行解，正分量对应的列线性相关。 对任意的实数 取充分小的 得两可行解x1,x2 ，使x= x1/2+x2/2。 第十二页，共二十六页，2022年，8月28日 推论 线性规划可行域的顶点个数有限。 引理2 若K为有界闭凸集，则其中任何一点可表示为其顶点的凸组合。 不证明，举例说明。 定理4 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点达到最优。 证明： 另外，若可行域无界，但有最优解，则一定也可在顶点处达到最优。 定理4换成代数说法就是：线性规划问题若存在最优解，则一定存在最优的基可行解。 第十三页，共二十六页，2022年，8月28日 第二章 单纯形法 第十四页，共二十六页，2022年，8月28日 穷举法的困难 已知线性规划问题的一基可行解，问题 此基可行解是否最优； 该问题是否无最优解； 如何改进（求一更好的基可行解）； 算法是否会有限步结束； 如何找一基可行解。 第十五页，共二十六页，2022年，8月28日 §2.1 单纯形表 为计算方便，将系数提出来，形成表格： x1 x2 … xn a11