1.2 线性规划图解法

图解法是在直角坐标系中用作图的方法来求线性规划问题的解，它适用于仅含两个决策变量的线性规划问题的数学模型求解。虽然这种方法的应用范围受到很大的限制，但这种方法简单、直观，特别是有助于理解线性规划问题单纯形法求解的基本原理。

例1-3 用图解法求解线性规划问题。

解：

（1）绘制平面直角坐标系x1Ox2。

（2）由约束条件①、②、③所确定的可行域为多边形OABCD中任意一点（包括其边界点），见图1-1中阴影部分。

（3）绘制法向量。因为我们只关心其方向而不关心其长度，所以将法向量延长。

（4）画一条垂直于法向量的等值线l。因为目标函数为求最大值，所以让直线l沿法向量方向平移，直到移到直线BC上为止。

此时，线段BC上任意一点均为最优解。解出点B、C的坐标值，分别为B（），C（3,2），所以最优解为点B、C以及线段BC内的点。

对应的最优值为z*=5。

例1-4 用图解法求解线性规划问题。

解：可行区域D如图1-2所示。在区域OA1A2A3A4O的内部及边界上的每一个点都是可行点，目标函数的等值线z=−x1+x2（z取定某一个常值）的法线方向（梯度方向）（-1,1）是函数值增加最快的方向（负梯度方向是函数值减小最快的方向）。

沿着函数的负梯度方向移动，函数值会减小，当移动到点A2=（1,4）时，再继续移动就离开区域D了。于是A2点就是最优解，而最优值为z*=−3。

图解法步骤可以总结为：

（1）求可行域。在平面直角坐标系中，可行域是各约束条件所表示的半平面的公共部分。

（2）求最优解。将目标函数z看成参数，做出等值线，然后根据原问题求最大值（或最小值）的要求，令等值线沿z值增加（或减少）方向在可行域内平行移动，直到找到等值线与可行域最后相交的一点，即为所要求的最优解。

由图解法可以看出，对于一般线性规划的解存在4种情况：

（1）唯一最优解，则此最优解只能在可行域的某个顶点上达到；

（2）无穷多最优解，则最优解在顶点所连的线段上达到；

（3）无界解，存在可行解，但目标函数值无界；

（4）无可行解，因而无最优解。

从图解法的几何直观容易得到下面几个重要结论：

（1）线性规划的可行区域D是若干个半平面的交集，它形成了一个多面凸集（也可能是空集）。如果可行域无界，线性规划问题的目标函数可能出现无界的情况。

（2）对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到，在这种情况下还包含两种情况：有唯一最优解和有无穷多最优解。因此，寻求线性规划问题的最优解，只需沿着可行域的边界搜索，后面介绍的单纯形法正是循着这个思路来求解线性规划问题最优解的。