第3章321线性规划问题的图解法

一、一、 线性规划的图解法线性规划的图解法解的几何表示解的几何表示 1什麽是图解法？什麽是图解法？线性规划的图解法就是用几何作图线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以求解的思路是：先将约束条件加以图解，求得满足约束条件和非负条件的图解，求得满足约束条件和非负条件的解的集合（即可行域），然后结合目标解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。函数的要求从可行域中找出最优解。2. 图解法举例图解法举例 实施图解法，以求出 最优最优 生产计划 （ 最优解最优解 ） , 给出 最优值。最优值。例 3-1由于线性规划模型中只有两个决策由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就变量，因此只需建立平面直角坐标系就可以进行图解了。可以进行图解了。第一步：第一步： 建立平面直角坐标系标出坐标原点 , 坐标轴的指向和单位长度。用 x1轴表示产品 A的产量，用 x2轴表示产品 B的产量。第二步：第二步： 对约束条件加以图解。 第三步：第三步： 画出目标函数等值线，结合目标函数的要求求出最优解：最优生产方案。第四步：第四步： 最优解带入目标函数，得出最优值。约束条件的图解 :每一个约束不等式在平面直角坐标系中都代表一个半平面，只要 先画出该半平面的先画出该半平面的边界边界 ，然后 确定是哪个半平面确定是哪个半平面 。 ?以第一个约束条件 : 为例 , 说明图解过程。怎麽画边界怎麽画边界 怎麽确定怎麽确定 半平面半平面代表一个半平面其边界 : x1+2 x2 =8x1+2 x2 =8及 x1， x2 0 AOB点点 A、 B连线连线 AB 经济含义经济含义 ？ A0B1203x241 2 3x185 6 7Q4BA点点 A(8,0)：连接连接 AB：设备全部占用所生产 、 数量对应的点的集合。全部的设备都用来生产 产品而不生产 产品 ,那么 产品的最大可能产量为 8台 ,计算过程为： x1+208 x18 0 B：设备没有全部占用所生产 、 数量对应的点的集合 。1203x241 2 3x185 6 7Q4BA约束条件及约束条件及非负条件非负条件 x1,x2 0代表的公共部分图中阴影区，就是满足所代表的公共部分图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行。在这个区域中的每一个点都对应着一个可行的生产方案。的生产方案。 另两个约束条件的另两个约束条件的边界直线边界直线 CD、 EF: 4x116， 4 x2 1285 6 7x1A3x2 BCDE41 2 3102F令 Z=2x1+3x2=c, 其中 c为任选的一个常为任选的一个常数数 ，在图 中画出直线 2x1+3x2=c, 即对应着一个可行的生产结果，即使两种产品的总利润达到 c。这样的直线有无数条，且相互平行，称这样的直线为 目标函数等值线目标函数等值线 。 只要只要 画两条目标函数 等值线等值线 ，如令c 0和 c=6，可看出 目目标函数值变化的方向标函数值变化的方向 ,即虚线 l1和 l2,箭头为产品的总利润递增的方向。最优点最优点85 6 7x1A3x2 BCDE41 2 3102F对应坐标 x1=4, x2=2 是最佳的产品组合 , 4,2T就是线性规划模型的 最优解最优解使产品的总利润达到最大值maxZ=24+32=14就是目标函数 最优值最优值 。 沿着箭头沿着箭头 方向 平移平移 目标函数等值线，达到 可可行域中的最远点行域中的最远点 E, E点就是 最优点最优点 ;最优点最优点85 6 7x1A3x2 BCDE41 2 3102F尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是 用解联立方程的方法求出最优解的精用解联立方程的方法求出最优解的精确值。确值。比如 C点对应的坐标值我们可以通过求解下面的联立方程，即求直线 AB和 CD的交点来求得。直线 AB: x1+2x2=8直线 CD: 4x1=16最优点最优点85 6 7x1A3x2BCDE41 2 3102F结果有唯一最优解有唯一最优解可行域是一个非空有界区域可行域是一个非空有界区域用图解法求解线性规划的各种可能的结果可行域有几种可能可行域有几种可能 ?解有几种可能解有几种可能 ?讨论唯一最优解唯一最优解 例例 3-3 将例将例 3-1中目标要求改为极小化中目标要求改为极小化，目标函数和约束条件均不变，则可行域，目标函数和约束条件均不变，则可行域与例与例 3-1相同，目标函数等值线也完全相同相同，目标函数等值线也完全相同，只是在求最优解时，应沿着与箭头相反，只是在求最优解时，应沿着与箭头相反的方向平移目标函数等值线，求得的结果的方向平移目标函数等值线，求得的结果是有是有 唯一最优解唯一最优解 x1=4,x2=2,对应着图中对应着图中的坐标原点。的坐标原点。 无穷多个最优解无穷多个最优解c1,c285 6 7x13x241 2 3102BA沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将与可行域的一条边界线段 AB重合。 结果表明，该线性规划有 无穷多个无穷多个最优解最优解 线段 AB上的所有点都是最优点，它们都使目标函数取得相同的最大值Zmax=14。 无界解无界解2406x21 2 543x1如图中可行域是一个无界区域，如阴影区所示。虚线为目表函数等值线，沿着箭头指的方向平移可以使目标函数值无限制地增大，但是找不到最优解。这种情况通常称为 无无 “有限最优解有限最优解 ” 或或 “最优最优解无界解无界 ”。如果一个实际问题抽象成像例 1-4这样的线性规划