第三节线性规划图解法及其几何意义

线性规划的图解法就是用几何作图的方法分析并求出其最优解的一种方法。适应于求解两个变量的线性规划问题，其特点是简单、直观。

图解法解题的基本步骤为：

第1步：以决策变量为坐标轴建立平面直角坐标系；

第2步：根据约束条件在平面直角坐标系上画出可行域；

第3步：画出目标函数等值线；

第4步：移动等值线求解。

下面通过一些例子来讨论图解法的解题过程，用图解法求解例1.1的数学模型。

第一步：建立以为坐标轴的直角坐标系。

第二步：根据约束条件画出可行域。在以为坐标轴的直角坐标系中，非负条件是指第一象限，前三个约束条件分别代表一个半平面，第一个约束条件代表直线左下方的半平面，第二个约束条件代表直线左下方的半平面，第三个约束条件代表直线左下方的半平面，同时满足这四个条件点为四块区域的交集部分，见图1-2中的阴影部分。

图1-2 可行域

第三步：画出目标函数等值线。如图1-3，在此坐标平面上，目标函数表示以/50为纵轴上截距，以-4/5为斜率的一族平行线：

位于同一直线上的点，其对应的参数取相同的值，即具有相同的目标函数值，将此线称为“等值线”。

图1-3 目标函数等值线

第四步：移动等值线求解。如图1-3，当等值线向右平行称动时，其截距由小变大，即的值由小变大。在可行域内，当等值线移动到点C时，其截距最大，即的值在可行域内得到了最大值。C为直线与直线的交点，解以下方程组可得其坐标。

解得，即原线性规划的最优解，目标函数的最大值。说明该企业的最优生产计划方案是：生产甲15吨，生产乙7.5吨，可获得最大利润97.5万元。

上例中求得的线性规划最优解是唯一的，但对于一般线性规划问题，还可能会出现以下几种解的情况：

(1)多重最优解

【例1.5】用图解法求解以下线性规划。

解：用图解法求解的结果见图1-4。从图中可以看出，等值线与可行域的边界直线平行，在可行域内移动等值线到此边界时，可使等值线在纵轴上的截距达到最大，即取最大值，则直线上的所有点都是此线性规划问题的最优解。

图1-4 图解法求解的结果

(2)无界解

【例1.6】用图解法求解以下线性规划。

解：用图解法求解的结果见图1-5，从图中可以看出，该线性规划的可行域无界，等值线向右平移到无穷远时，可使目标函数增大到无穷大，这种情况称为无界解。

图1-5例1.6图解法求解结果

(3)无可行解

【例1.7】用图解法求解以下线性规划。

解：该线性规划的可行域为空集，说明该线性规划无可行解，也不存在最优解。

上面介绍的图解法虽然简单直观，解题时不需要将数学模型化为标准型，而且可以直接看出线性规划解的几种情况，但这种方法只适用于两个变量的线性规划问题。当变量数增多时，图解法就无法满足了。这时，就要用解析计算的方法——单纯形法来求解。