1.4 线性规划图解法

人们在各种生产、运输等经济事务活动中，创造了很多求解线性规划的方法。例如1958年我国粮食部门研究和推广应用的图上作业法，在粮食调运方面取得了很好的效果。但大多数方法是针对具体类型问题而言，要分别不同情况才能加以利用。

线性规划数学模型解法目前最常用的有两种方法：图解法和单纯形法。图解法简单直观，但只适用于两个变量的数模；单纯形法是线性规划通用方法，适用于任意多个变量的数模。本节先讨论图解法。

图解法求解线性规划是利用数模中方程式的几何图形来直接找到最优解。从原理上说，我们可以平面和立体空间图形分别求解两变量和三个变量的线性规划问题，但从作图麻烦程度来看，求解三个变量的规划问题已不太适用了。由于图解法只适用于两个变量，故其实用意义不大。图解法的一个重要目的是在于利用它的直观图形看问题，这样有助于了解和剖析线性规划的原理及过程。所以图解法的重点是说明线性规划的几何意义。

1.4.1 求解步骤

图解法在操作上分为以下几个步骤。

第一步 将所有约束方程用图形绘出，即约束半平面。

第二步 确定可行解域，即所有约束方程图形的公共部分。

第三步 绘出目标函数直线。

第四步 确定最优点的方位，根据目标函数形式可知，最优点落在可行解域的右上方。

第五步 将目标函数直线向可行解域的右上方平行移动，直至与可行解域相切为止，这个切点就是数学模型的最优解。

第六步 确定数学模型的最优解（切点的坐标）及最优目标函数值。

现以上述【例1-1】的数学模型介绍图解法的求解过程，数学模型如下。

第一步 将所有约束方程用图形绘出，即约束半平面。

对约束方程为3x1+ 9x2≤ 540。首先画出直线3x1+ 9x2= 540，由于原点O满足约束条件②，所以原点O位于约束条件②所示的图形范围内部，而原点O位于该直线的左下方，所以该直线的左下方就是约束条件②所示图形的范围。其他约束条件所示图形的范围同理可得出，如图1-3所示。

第二步 确定可行解域，即所有约束方程图形的公共部分，即图1-3中的阴影部分。

第三步 绘出目标函数直线。根据Max Z = 70x1+30x2，在x1坐标上取70，在x2坐标上取30，得两点，加上原点共三个点可构成一个矩形，由此产生第四个顶点，从原点和第四个顶点作一条对角线，然后作该对角线的垂线，该垂线即是目标函数直线，如图1-4所示。

第四步 确定目标函数直线移动方向P。根据目标函数的表达式Max Z = 70x1+30x2，要使Z增大，必须使x1（可行解域的右方向）、x2（可行解域的上方向）增大，因此最优点位于可行解域的右上方（可行解域的边界上）。所以方向P就是可行解域的右上方。

第五步 确定最优解及最优目标函数值。将目标函数直线向可行解域的右上方向P 平行移动，直至与可行解域相切为止，如图1-4所示，这个切点h就是所求的最优点，对应的解（75,15）就是最优解，即数学模型的最优解为：

X*=(75,15)T, Z*=5700

由此可得原问题的最优决策方案：该公司应该安排甲、乙产品产量分别为75千克、15千克，可使公司获得最大利润5700元。

1.4.2 几何意义

图解法简单直观，单纯形法相对抽象，但它们之间有许多共性的东西。我们可以把它们共性的东西提取出来，使单纯形法中抽象的东西用低维的图形表示出来，有助于理解单纯形法原理，这就是线性规划的几何意义所在。由图解法的过程及上述基本概念，可以归纳出线性规划的几何意义。

（1）闭合的可行解域是凸多边形（凸集）。

（2）可行解域有有限个顶点：如O、a、h、k、b，对应的解为基本可行解。

（3）最优点若唯一存在，则必在其可行解域的某一顶点上得到。

1.4.3 特殊的数学模型

可行解域可能是闭合的，也可能是发散的；最优解可能唯一存在，也可能有无限多个最优解，或者无最优解。下面分别列出这些图解法进行说明。

1．有无穷多个最优解（或称多重最优解）

【例1-8】考虑下列数学模型，此线性规划问题的最优点在Q2Q3线段上，如图1-5所示，即线段Q2Q3上任意一点都使Z取得相同的最大值，这个线性规划数学模型有无穷多个最优解。由此可以得出，若数学模型有两个最优解，则必有无穷多个最优解。

2．解无界：可行解域无界，解值无限增大

【例1-9】现有下列数学模型

用图解法求解结果如图1-6所示，从图中可以看到，该问题可行解域无界，解值和目标函数值可以增大到无穷大，称这种情况为无界解或无最优解。

3．无可行解域：约束条件相互矛盾，无可行解

【例1-10】现有下列数学模型

用图解法求解结果如图1-7所示，可以看出，该问题可行解域为空集，即无可行解域（约束条件相互矛盾），当然也就无最优解。