3.2 线性规划的图解法

3.2.1 图解法示例

如何求解线性规划问题的模型呢？下面介绍一种基于几何图形的求解方法——图解法，这种方法简单直观，下面举例说明。

例3.1.1中的数学模型为

将所有约束条件放到以为坐标轴的直角坐标系中考察，每个约束条件都代表一个“半平面”。所有约束条件限定的区域如图3-2-1中的阴影部分，其中每个点（包括边界点）都是这个问题的解（称为可行解），此区域是问题的“解集合”，称为可行域。

目标函数在坐标平面上可以表示为以z为参数、-2/3为斜率的一组平行线：。位于同一直线上的点，具有相同的目标函数值，称它为“等线值”。当z值由小变大时，直线沿其法线方向向右上方移动。当移动到点时，z值在可行域边界上实现了最大化，这就得到了例3.1.1的最优解，其坐标为（4，2）注1。于是可以计算出最优目标函数值z*＝14。

由此，该线性规划问题有唯一的最优解，对应例3.1.1，也就是说应安排使用Ⅰ型炮弹4个基数、Ⅱ型炮弹2个基数，总的战斗力指数最大为14。

注1 想一想，为什么最优解不在Q2或Q4点？

3.2.2 解的4种情况

对于一般线性规划问题，求解结果可能出现以下几种情况：

（1）唯一的最优解，如例3.1.1。

（2）无穷多最优解（多重解），将例3.1.1中目标函数变为，则目标函数中以z为参数的这组平行直线与约束条件的边界线平行。当z由小变大时，其将与线段重合。线段上的任意一点都使z取得相同的最大值，此时线性规划问题有无穷多最优解（也称为多重解，见图3-2-2）。

（3）无界解，指线性规划问题的目标函数可以趋向无穷大（求最大化）或者趋向无穷小（求最小化）的情况，如下述线性规划问题：

用图解法求解如图3-2-3所示。可以看出，该问题可行域无界，目标函数值可以增大到无穷，称这种情况为无界解。

（4）无可行解，如果在例3.1.1的数学模型中增加一个约束条件，则该问题的可行域为空集，即无可行解，当然也不存在最优解。

当求解结果出现（3）和（4）两种情况时，一般说明线性规划问题数学模型有问题，要么是没有找到足够的约束条件，要么约束之间存在矛盾，这时需要建模者重新返回到问题分析的步骤中，针对性地重新分析建模。

从图解法中可以直观地看到，当线性规划问题的可行域非空时，它是有界或无界凸多边形；若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷最优解。

图解法虽然直观简便，但是当变量数多于3个时，它就无能为力了。下面介绍线性规划的通用求解方法——单纯形法。