《运筹学》课程授课教案（讲稿）第2讲 图解法及概念

课程名称：《运筹学》第_2_讲次2.2图解法授课题目2.3线性规划解的概念、本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，掌握线性规划解的概念，学会用图解法求解线性规划的一般方法。[重点及难点】利用图解法求解线性规划。内容[本讲课程的引入]上一讲我们学习了生产计划问题、营养配餐问题、运输问题等实际问题的建模方法今天开始我们学习线性规划解的基本概念以及用图解法解线性规划的方法。[本讲课程的内容]（一）线性规划的图解法（解的几何表示）对于只有两个变量的线性规划问题，可以在二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下：（1）分别取决策变量xl，x2为坐标向量建立直角坐标系：（2）对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面。各约束半平面交出来的区域（存在或不存在），若存在，其中的点表示的解称为此线性规划的可行解。这些符合约束限制的点集合，称为可行集或可行域。进行（3）：否则该线性规划问题无可行解。（3）任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置（有时交于无穷远处，此时称无有限最优解）。若有交点时，此目标函数等值线与可行域的交点即最优解（一个或多个)，此目标函数的值即最优值

课程名称：《运筹学》 第 2 讲次 授课题目 2.2 图解法 2.3 线性规划解的概念、 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，掌握线性规划解的概念，学会用图解法求解线性规划 的一般方法。 [重点及难点] 利用图解法求解线性规划。 内 容 [本讲课程的引入] 上一讲我们学习了生产计划问题、营养配餐问题、运输问题等实际问题的建模方法， 今天开始我们学习线性规划解的基本概念以及用图解法解线性规划的方法。 [本讲课程的内容] （一）线性规划的图解法（解的几何表示） 对于只有两个变量的线性规划问题，可以在二维直角坐标平面上作图表示线性规划问题的有关概 念，并求解。图解法求解线性规划问题的步骤如下： （1）分别取决策变量 x1 ，x2 为坐标向量建立直角坐标系； （2）对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断确定不等 式所决定的半平面。各约束半平面交出来的区域（存在或不存在），若存在，其中的点表示的解称为 此线性规划的可行解。这些符合约束限制的点集合，称为可行集或可行域。进行（3）；否则该线性规 划问题无可行解。 （3）任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向， 平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置（有时交于无穷远 处，此时称无有限最优解）。若有交点时，此目标函数等值线与可行域的交点即最优解（一个或多个）， 此目标函数的值即最优值

内容（二）图解法图解法简单直观，有助于理解线性规划问题求解的基本原理。对例1进行图解，如图2-1：X2X1+2X2= 84XI=164X2=120Q2(4, 2)21O101234图 1-1图中阴影区域中的每一个点（包括边界点）都是这个线性规划问题的界（称可行解），因而此区域是例1的线性规划问题的解集合，称它为可行域。目标函数z=2x1+3x2，在这个坐标平面上，可表示为以z为参数，-2/3为斜率的一族平行线，位于同一直线上的点，具有相同的目标函数值，称它为等值线。当z由小变大时，等值线沿其法线方向向右上方移动，当移动到Q2点时，z在可行域顶点上实现了最大化，得到例1的最优解Q2（4，2），同时可计算出z=14。例1有唯一最优解，但对一般的线性规划问题，求解结果还可能出现以下几种情况：（1）无可行解。可行域为空集，即无可行解，当然也不存在最优解。（2）无界解。可行域无界，目标函数值可以增大到无穷大，称这种情况为无界解或无最优解。（3）无穷多最优解（多重解）。等值线与某条可行域边界线平行。课堂演示：例 1用图解法求解

内 容 （二）图解法 图解法简单直观，有助于理解线性规划问题求解的基本原理。对例 1 进行图解， 如图 2-1： 图中阴影区域中的每一个点（包括边界点）都是这个线性规划问题的界（称可行解）， 因而此区域是例 1 的线性规划问题的解集合，称它为可行域。 目标函数 z = 2x1 + 3x2 ，在这个坐标平面上，可表示为以 z 为参数，-2/3 为斜率 的一族平行线，位于同一直线上的点，具有相同的目标函数值，称它为等值线。当 z 由小 变大时，等值线沿其法线方向向右上方移动，当移动到 Q2 点时，z 在可行域顶点上实现 了最大化，得到例 1 的最优解 Q2（4，2），同时可计算出 z = 14。 例 1 有唯一最优解，但对一般的线性规划问题，求解结果还可能出现以下几种情况： （1）无可行解。可行域为空集，即无可行解，当然也不存在最优解。 （2）无界解。可行域无界，目标函数值可以增大到无穷大，称这种情况为无界解或 无最优解。 （3）无穷多最优解（多重解）。等值线与某条可行域边界线平行。 课堂演示： 例 1 用图解法求解 图 1-1 0 1 2 3 4 1 2 3 Q1 Q4 Q3 Q2（4，2） X1 X2 4X2 = 12 4X1= 16 X1+2X2 = 8

内容maxz=xl + x2S.1.x1 +2x2≤4xl -2x2≥5xl,x2≥0例2用图解法求解：max==2x1+x2s.1.xl+x2≥2xl -2x2≤0xl，x2≥0例3用图解法求解：max==40x1+30x2s.1.4xl+3x2≤1202xl +x2≤50xl≥0，x2≥0小结：从图解法直观地看到，当线性规划问题的可行域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。[本讲小结】今天我们给大家重点介绍了利用图解法求解线性规划的基本思想和方法，希望大家课下要很好的复习，争取熟练掌握其解题方法。[本讲课程的作业]43页第一题

内 容 max z = x1 + x2 s.t. x1 + 2x2  4 x1 - 2x2  5 x1, x2  0 例 2 用图解法求解： max z = 2x1 + x2 s.t. x1 + x2  2 x1 - 2x2  0 x1 , x2  0 例 3 用图解法求解： max z = 40x1 + 30x2 s.t. 4x1 + 3x2  120 2x1 + x2  50 x1 0，x2 0 小结：从图解法直观地看到，当线性规划问题的可行域非空时，它是有界或无界凸多 边形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时 得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。 [本讲小结] 今天我们给大家重点介绍了利用图解法求解线性规划的基本思想和方法，希 望大家课下要很好的复习，争取熟练掌握其解题方法。 [本讲课程的作业] 43 页第一题