线性规划问题解的概念

五、线性规划问题解的概念

对于只有两个决策变量的线性规划问题，我们可以用作图方法来求解.图解法不仅直观，而且可以从中得到有关线性规划问题的许多重要结论，有助于我们理解线性规划问题求解方法的基本原理.

例8 以例4为例说明图解法的主要步骤.例4的数学模型如下

首先作一个以x1，x2为坐标的直角坐标系（如图8-1所示）.约束条件（8.5）中有三个不等式，暂且将第一个不等式30x1+20x2≤160变为等式30x1+20x2=160，它在坐标系中应该是一条直线，记为L1，显然L1上的点的坐标（x1，x2）都满足30x1+20x2=160.则坐标（x1，x2）满足30x1+20x2＜160的点都在直线L1的左下方（显然坐标满足30x1+20x2＞160的点都在直线L1的右下方）.即直线L1将平面Ox1x2上的点分为两半.因此我们通常也称为不等式30x1+20x2≤160为半平面（含直线L1），如图8-1所示.同理，设直线5x1+x2=15为L2，则5x1+x2≤15为L2的左下半平面.满足x1≤4的点位于直线L3：x1=4的左半边平面.满足非负约数条件x1≥0及x2≥0的点分别为坐标平面的上半平面及右半平面.

因此满足约束条件（8.5）的点，应是上述5个半平面的交集，即图8-1中的四边形OABC区域（含边界）称为可行域.满足约束条件及非负约束条件的解（x1，x2）T称为可行解.本题即变为要在可行域OABC中找出一个点（解）X*=（x1*，x2*）T，它的目标函数（8.4）中Z的值为所有可行解中达到最大.目标函数Z=5x1+2x2，在坐标平面Ox1x2中，可视为以x1，x2为变量、Z为参数的一族直线.如5x1+2x2=5，即为图8-1中的直线l1；5x1+2x2=10，即为l2，…因此5x1+2x2=Z是以Z为参数的一族互相平行的直线.在同一条直线5x1+2x2=Z0上的点（x1，x2），它们的目标函数值都相等，因此称为等值线族.在这等值族中取得最大且又要在可行域内（或说与可行域相切）的直线l*便是我们要寻找的.其与可行域的交点就是最优解X*.具体做法是，首先求出Z=5x1+2x2的梯度.记梯度向量▽Z的方向为t，在坐标平面上画出t，然后将任意一根等值线如l1，沿t方向（即Z增加的方向）推平行线，直到该平行线将离开而还未离可行域时的一根等值线即为l*，在图8-1中即为过B点的等值线，B点即为最优解.容易计算，B点的坐标为（2，5）.因此本题的最优解X*=（2，5）T.最优值为Z*=5×2+2×5=20.即该厂每周安排生产甲种药品生产量为2 t，乙种为5 t.每周可获最大利润为20万元.

假若数学模型中对目标函数Z是求极小值，显然等值线应按负梯度方向即-▽Z方向推平行线，从而求得l*及最优解X*.

从图解法作图结果来分析，线性规划问题应有以下几种可能出现的结果：

（1）有唯一最优解，如例4.

（2）有无穷多个最优解.

例9

解 由约束条件（8.7）做出可行域K（图8-2）为多边形OABC　D.对目标函数Z=-2x1-4x2，求出▽Z=（-2，-4）T，作等值线l1：-2x1-4x2=-4.将l1沿-▽Z=-t=（2，4）T方向推平行线，平行线将离开可行域K而尚未离开时，与K相切边为BC，因此l*即为边BC，而线段BC上任意一点的目标函数值均相等，一次线段BC上任意一点是最优解.故本例题有无穷多个最优解：如点B （2，3），点C（ 4，2），点E （3，2.5）等.最小值为Z*=-2×2-4×3=-16.

（3）无界解（也称无最优解）.

例10

解 在Ox1x2坐标平面中可做出可行域K（图8-3），可看出可行域K是个无界的不封闭区域.做出等值域Z=x1+x2的梯度向量：▽Z=（1，1）T，记作t=（1，1）T.任意找出一条等值域l1，如x1+x2=3.将l1沿着t方向即Z增大方向推平行线，显然得不到取最大值的等值线，因此本题无最优解.

要注意的是，并非无界的可行域一定是最优解.若本题改为求目标函数最小化：min Z=x1+x2，则将l1沿-t（即Z值域减小的方向）推平行，可得到最优解等值域为过O点的l1（图8-3）.最优解为X*=（0，0）T，最优解Z*=0.

（4）无可行解——可行域为空集.

例11

解 在Ox1x2平面中，做出L1：x1+x2=7，L2：x1+2x2=8，L3：x1=4，L4：x2=3；L5：x1=0；L6：x2=0共6条直线，而x1+x2≥7应在L1的右上半平面.由例9可知，后面5个半平面的交集为OABCD，交集为空集，因此本例题的约束条件所组成的可行域为空集.即本例题无可行解（图8-4）.

从上述的分析讨论中，可以得到以下关于线性规划问题可行域与解之间的性质：

（1）若可行域非空且有界，则可行域是一个多边形，其顶点个数是有限个；若可行域非空但无界，其顶点个数也有有限个.

（2）若可行域非空且有界则必有最优解；若可行域无界，则可能有最优解，也可能无最优解.

（3）若线性规划问题有最优解（不论可行域是有界还是无界），其最优解必可以在某个顶点上达到.最优解的个数或是唯一的，或有无穷多个.