运筹学第一章1-2-1线性规划问题的图解法.ppt

一、 线性规划的图解法;1．什麽是图解法？ 线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。 求解的思路是：先将约束条件加以图解，求得满足约束条件和非负条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。 ;2. 图解法举例 ; 由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。; 约束条件的图解: 每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边界，然后确定是哪个半平面。 ; 代表一个半平面 其边界: x1+2 x2 =8;点A(8,0)：; 约束条件及非负条件x1,x2 ?0代表的公共部分－－图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。 ; 令 Z=2x1+3x2=c, 其中c为任选的一个常数，在图 中画出直线 2x1+3x2=c, 即对应着一个可行的生产结果，即使两种产品的总利润达到c。 这样的直线有无数条，且相互平行，称这样的直线为目标函数等值线。只要画两条目标函数等值线，如令 c＝0和c=6，可看出目 标函数值变化的方向, 即虚线 l1和l2,箭头为产 品的总利润递增的方向。;对应坐标x1=4, x2=2 是最佳的产品组合, [4,2]T就是线性规划模型的最优解 使产品的总利润达到最大值maxZ=2?4+3?2=14就是目标函数最优值。 ; 尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。 比如C点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。 直线AB: x1+2x2=8 直线CD: 4x1=16 ;最优点;将例1-1稍作改动形成案例1，仍使用图解法来求解。 ; 设三种产品的产量分别是x1、x2、x3吨，由于有三个决策变量，用图解法求解下面的线性规划时，必须首先建立空间直角坐标系。;结果 有唯一最优解 可行域是一个非空有界区域;唯一最优解 ; 无穷多个最优??; 沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界线段AB重合。 ;无界解; 如图中可行域是一个无界区域，如阴影区所示。虚线为目表函数等值线，沿着箭头指的方向平移可以使目标函数值无限制地增大，但是找不到最优解。这种情况通常称为无“有限最优解” 或“最优解无界”。