任务二　线性规划的图解法

在建立了线性规划的模型之后，接下来就要求解模型了。在求解线性规划模型时，最简单的方法就是图解法。

当线性规划问题中变量个数为2时，我们可以在直角坐标系中把变量及其变化方向、范围等用图直观地表示出来，从而求得目标函数的最佳取值，这种方法就是图解法。在应用中，图解法相对是比较缺乏实际意义的，但通过这种方法，可以形象地说明线性规划的许多特征。

接下来，我们用图解法求解例2-1-1。之前，我们建立出了例2-1-1的模型：

在以x1，x2为坐标轴的直角坐标系中，非负条件是指位于第一象限。每一个约束条件都代表一个半平面。我们先将这个规划的可行域画出来。约束条件x1＋2x2≤8表示以直线x1＋2x2＝8为边界（包括边界）的左下半平面。同理，4x1≤16表示以直线4x1＝16为边界，包括边界在内的左下半平面，而4x2≤12则表示以直线4x2＝12为边界，包括边界在内的左下半平面。因此，结合非负约束限定的第一象限，我们可以作出同时满足所有约束条件的区域，如图2-2-1所示。在线性规划中，满足所有约束条件的解称为可行解。我们可以看到，在图2-2-1中，阴影区域中的每一个点（包括边界点）都是可行解。阴影部分就是同时满足了4个约束条件的解的集合，我们把这个区域称为该线性规划问题的可行域。

图2-2-1

目标函数z＝2x1＋3x2在这个坐标平面上，它可以表示以z为参数、为斜率的一族平行线：，其中代表斜率，代表截距。现在我们要在这个可行域中求得一个使目标函数达到最大的点，其实也就是说，当目标函数z＝0时，作出目标函数的一条直线，在这条直线上，决策变量x1，x2的任何取值，对应目标函数z的取值都相等，我们把这条直线叫做等值线。随着z的增大，直线一直向右平移，当直线平移到刚好要离开阴影部分的临界点时，再向右平移就与可行域没有交点了，这时就得到了z的最大化目标值，如图2-2-2所示。

图2-2-2

因此，在等值线与阴影区域的临界交汇点就是满足约束条件的最优解，该点坐标x1＝4，x2＝2就是满足约束条件的最优解，将它们代入目标函数求得z＝14，也就是目标函数的最优值。

同理，当平行线向下移动时，当它移动到刚好要离开阴影部分的临界点时，我们就能得到z的最小值。因此，图解法既可以求解最大化问题，也可以求解最小化问题。

另外，由图2-2-2可以看出，线性规划的最优解出现在可行域的一个顶点上，此时线性规划问题有唯一解。但有时线性规划问题还可能出现其他解的情况。接下来通过例题来说明。

（1）如果将例2-1-1中的目标函数改为求maxz＝2x1＋4x2，这时目标函数的等值线就与边界线x1＋2x2＝8平行，所以当等值线向右平移到阴影区域时，临界点不是一个点，而是一条边界线，这时，边界线上的任意一点都是这个线性规划的最优解，如图2-2-3所示。这时，线性规划问题有无穷多个最优解。

图2-2-3

（2）如果在例2-1-1的基础上增加约束条件x1＋x2≥9，那么该问题的可行域是空集，所以，这个问题不存在可行解，当然更不可能存在最优解，如图2-2-4所示。

图2-2-4

例2-2-1　用图解法求解线性规划。

解：这个线性规划问题，当我们画出它的可行域和目标函数时，我们发现，这是个无界集，不管目标函数的等值线怎么向右平移，目标函数和可行域总是有交集，这时目标函数值可以无限增大，也就是说，这个问题有可行解，但没有最优解，如图2-2-5所示。

图2-2-5

所以我们可以看出，线性规划可能有一个最优解，可能有可行解而无最优解，可能有无穷多最优解，也可能根本就没有可行解。