运筹学课件_线性规划解的概念、性质及图解法.pptVIP

图解法求解步骤 由全部约束条件作图求出可行域； 作目标函数等值线，确定使目标函数最优的移动方向； 平移目标函数的等值线，找出最优点，算出最优值。 线性规划问题求解的 几种可能结果 线性规划问题求解的 几种可能结果 图解法的几点结论:（由图解法得到的启示） 可行域是有界或无界的凸多边形。 若线性规划问题存在最优解，它一定可以在可行域的顶点得到。 若两个顶点同时得到最优解，则其连线上的所有点都是最优解。 解题思路：找出凸集的顶点，计算其目标函数值，比较即得。 练习：用图解法求解LP问题  (30,10)  (30,10) 　　　根据以上例题，进一步分析讨论可知线性规　　　　　　　 划的可行域和最优解有以下几种可能的情况 1.可行域为封闭的有界区域 (a)有唯一的最优解； (b)有无穷多个最优解； 2.可行域为非封闭的无界区域 (c)有唯一的最优解； 　　　　　(d)有无穷多个最优解； (e)目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减少)，因而没有有限最优解。 3.可行域为空集 (f)没有可行解，原问题无最优解 1.图解法求解步骤 由全部约束条件作图求出可行域； 作目标函数等值线，确定使目标函数最优的移动方向； 平移目标函数的等值线，找出最优点，算出最优值。 1.可行域为封闭的有界区域 (a)有唯一的最优解； (b)有无穷多个最优解； 2.可行域为非封闭的无界区域 (c)有唯一的最优解； 　　　　　(d)有无穷多个最优解； (e)目标函数无界(即虽有可行解，但在 可行域中，目标函数可以无限增大或无限 减少)，因而没有有限最优解。 3.可行域为空集 (f)没有可行解，原问题无最优解 定义 线性规划的标准型： A 是m×n矩阵，m≤n 并且r(A)=m。 （5）基本解：对某一确定的基B，令非基变量等于零，由式（1-2）解出基变量，称这组解为基本解。 （6）基本可行解：基本解是可行解则称为是基本可行解（即非负的基本解） 。 （9）凸集 定义 2 设 则称 ＬＰ的可行域以及最优解有以下性质: 1.若线性规划的可行域非空，则可行域必定为一凸集． 2.若线性规划的可行域非空，则至多有有限个极点. 3.若线性规划有最优解,则至少有一个极点是最优解. （8）可行基 基可行解对应的基称为可行基； 最优基 基本最优解对应的基称为最优基； （7）基本最优解 最优解是基本解称为基本最优解。 基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示： 基本最优解 基本可行解 可行解 最 优 解 基本解 当最优解唯一时，最优解亦是基本最优解， 当最优解不唯一时，则最优解不一定是基本最优解。 系数阵A中可找出多个基B 返回 非负的基本解就是基本可行解 每个基B都对应于一个基本解 注意：线性规划的基本解、基本可行解和可行基只与线性规划问题标准形式的约束条件有关。与目标函数无关。 定义1 设集合 是 n 维欧氏空间中的一个点 集，如果 及实数 则称 K 是一个凸集。 几何意义：如果集合中任意两点连线上的一切点都在 该集合中，则称该集合为凸集。 凸集 为点 的一个凸组合。 定义3 设凸集 两点 表示为 则称 x 为 K 的一个极点（或顶点）。 定理 LP 问题的可行解集 （10）凸组合 （11）极点 【定理1.1】 若线性规划可行解K非空,则K是凸集。 【定理1.2】线性规划的可行解集合K的点X是极点的 充要条件为X是基本可行解。 定理1.3】若线性规划有最优解,则最优值一定可以在可行解集合的某个极点上得到,最优解就是极点的坐标向量。 定理