第一章 线性规划与单纯形法(2)

?a11a12?a1n????a21a22?a2n? A?? ???????a??m1am2?amn?A称为约束方程组的系数矩阵。

第二节 两个变量线性规划问题的图解法

一、可行解和最优解 给定线性规划问题

max(min)z??cjxjj?1n ?nax?(?,?)b(i?1,2,?,m)i??ijjs..t?j?1?xj?0(j?1,2,?,m)?所谓求解线性规划问题，就是从满足约束条件的解中找出一个解，使目标函数达到最优。下面介绍两个线性规划解的概念。

可行解： 满足约束条件的解X??x1,x2,?,xn?，称为线性规划问题的可行解。全部可行解的集合称为可行域。

最优解： 使目标函数达到最有利的可行解称为最优解，这里所说的最有利是最大化或最小化，要依模型的具体情况而定。

求解一个线性规划问题的过程就是一个寻找最优解的过程。

二、图解法

对于只有两个决策变量的线性规划问题，由于可行域可以用一个平面区域来表示，因此可以采用图解法寻找最优解。图解法简单直观，有助于理解求解一般线性规划问题的单纯形法的思路。

例1.4 用图解法求解例1.1中的线性规划问题：

minz?30x1?50x2

x1?4??x2?6?s.t.?

?3x1?2x2?18??x1?0,x2?0解：首先，分别以x1和x2为横坐标和纵坐标建立平面直角坐标系，通过划定各个约束条件的取值范围的边界线，从而确定约束条件允许的(x1,x2)的取值范围，即可行域的范围。注意到非负性约束x1?0和x2?0，即要求(x1,x2)的取值位于第一象限。考虑到约束条件

x1?4，意味着x1的取值不能位于直线x1?4的右边，结果见图1.1，图中阴影部分包含

- 10 -

可行的取值。

使用同样的方法，约束条件x2?6，意味着直线x2?6应该是可行域的上边界。最后一个约束条件是3x1?2x2?18，要求所有可能的(x1,x2)值在直线3x1?2x2?18的下方。这样我们就可以得到(x1,x2)的所有可能取值范围——可行域，如图1.2阴影部分所示。

图1.1 图1.2

其次，在可行域中选择使目标函数z?30x1?50x2取最大值的点。分析目标函数的几何意义，目标函数z?30x1?50x2中，将z看成一个待定参数，将其改写成

x2??(3/5)x1?(1/50)z，由解析几何知，这是参量为z、斜率为?3/5的一族平行的直线，

如图1.3所示。位于同一直线上的点，具有相同的目标函数值，因而称其为“等值线”。当z值由小变大时，直线x2??(3/5)x1?(1/50)z向右上方移动，越来越远离坐标原点。

图1.3

通过实验发现，当z?100时，直线30x1?50x2?100的一段在可行域内，即说明这一段上点(x1,x2)是可行解且其使目标函数值为100。将直线向右上方移动，当z?200时，直线30x1?50x2?200仍有一段在可行域内，故这一段上点(x1,x2)是可行解且其使目标函数值为200。继续将直线向右上方移动，当z?360时，直线30x1?50x2?360上有且仅有一点(2,6)属于可行域，故仅有点(2,6)是可行解且使目标函数值为360。此时直线

30x1?50x2?360右上方没有可行域阴影，即不可能有可行解使目标函数值大于360。故(2,6)即是要求的最优解。

- 11 -

这个结果可表示为最优解为

目标函数最优值为maxz?360。

这说明为了获得最大的利润，应每天生产木框架窗2个，铝框架窗6个。

通过上面的例子，可以看出用图解法寻找线性规划问题的最优解，就是在至少包含可行域中一个点的目标函数等值线中，选择z取得最大值所对应的直线，它所包含的可行域中的点就是最优解，其对应的z值就是最优目标函数值。

在实际操作中，可以先确定目标函数等值线的斜率，以该斜率任做一条与可行域相交的直线，即一条等值线。利用直尺将这条直线向z增大的方向平移，始终保持与可行域相交的状态，直到再移动就与可行域不相交时为止，所得到的直线与可行域的交点即最优解，所对应的z值就是最优目标函数值。

上例中用图解法得到问题的最优解是唯一的，但在线性规划问题的求解中，解的情况还可能出现以下几种：

1. 无穷多最优解

若将例1.1中目标函数变为求maxz?30x1?20x2，模型变为：

?x1?2 ?x?6?2maxz?30x1?20x2

x1?4??x2?6?s.t.?

3x?2x?182?1??x1?0,x2?0如图1.4所示，目标函数的等值线恰好与约束条件3x1?2x2?18的边界线平行。当z值由小变大时，等值线向右上方平行移动，最后与可行域阴影交于线段AB。由于等值线不能再向右上方平移，故线段AB上任意一点都使z值取得相同的最大值，这个线性规划问题有无穷多最优解。

当线性规划问题有无穷多最优解时，可用最优解所在线段的两个端点作为这无穷多最优解的代表。在本例中，两个最优解分别为：

?x?2A:?1?x2?6?x?4 B:?1?x2?3目标函数的最优值为maxz?180。

一般地，如果线性规划问题有两个最优解，则它一定有无穷多最优解。

- 12 -

图1.4 2. 无界解

如果例1.1中的约束条件只考虑x1?4以及非负约束x1?0和x2?0，不考虑其他约束，则模型变为：

maxz?30x1?50x2

s.t. ??x1?4?x1?0,x2?0

如图1.5所示，决策变量x2的取值可以无限增大，目标函数等值线可以一直向上移动，故目标函数值也可以一直增大到无穷大。这种情况称线性规划问题具有无界解。

一般来说，出现无界解的情况是由于在建立实际问题的数学模型时，忽略了某些必要的约束条件。

图1.5 3. 无可行解

如果在例1.1中增加一个约束条件x1?6，则模型变为

- 13 -

maxz?30x1?50x2 x1?4??x1?6??x2?6s.t.? ?3x1?2x2?18???x1?0,x2?0显然，约束条件x1?4和x1?6相互矛盾，故无法找到满足所有约束条件的可行解，可行域为空集。此时称线性规划问题无可行解。

一般来说，出现无可行解的情况是因为建立数学模型时出现了错误，此时需要检查建模过程，重新建立数学模型。

使用图解法可以解决含有两个决策变量的线性规划问题。经过适当的扩展也可以用来解决含有三个决策变量的线性规划问题，有兴趣的同学可以做一些思考。对于更多的决策变量，图解法由于几何表示上的限制，就有些力不从心了。但它的解题思路和几何上的直观表示，对求解一般线性规划问题的单纯形法有很重要的启示，即

（1）线性规划问题的解一般有唯一最优解、无穷多最优解、无界解和无可行解四种情况； （2）线性规划问题的可行域一般为有界或无界凸多边形；

（3）若线性规划问题最优解存在，即有唯一最优解或无穷多最优解，则必可在可行域的某个顶点上找到最优解。

（4）若有两个最优解，则它们连线上任意一点都是最优解。

基于以上的启示，在求解线性规划问题时，只须在可行域顶点集上寻找线性规划问题的最优解就可以了，而不需要寻遍整个可行域。

第三节 线性规划问题数学模型的标准形

线性规划问题数学模型的目标函数依具体问题可取max或min，每个约束条件可取?、=或?。这样，线性规划问题的形式就有很多种，不便于给出一般的求解方法。因此，有必要给出一个统一的标准形式以及将一般线性规划标准化的方法。

从本章第一节可知，线性规划问题数学模型的一般形式如下：

max(min)z?c1x1?c2x2??cnxn?a11x1?a12xx???a1nxn?(?,?)b1?ax?ax???ax?(?,?)b21122x2nn2? ?s..t???ax?ax???ax?(?,?)bmnnm?m11m2xx1,x2,?,xn?0??定义线性规划问题的标准形式为：

- 14 -

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第一章 线性规划与单纯形法(2)在线全文阅读。