§1.2 解与性质

1.2.1 线性规划问题的图解法

对于只含有两个决策变量的线性规划问题，由于变量的取值可以用在二维坐标平面上的点来表示，因此可以用图解法进行求解。图解法不仅简单、直观，而且有助于我们了解线性规划解的性质和求解的基本原理。一个线性规划问题有解，是指能找到一组决策变量满足所有的约束条件，称这组决策变量为线性规划的可行解。

例1.4 用图解法求解线性规划

建立以变量x₁为横轴，x₂为纵轴的直角坐标系，非负约束x₁，x₂≥0是指第一象限。其他每个约束条件均代表一个半平面，如4x₁≤16是代表x₁ =4这条直线上的点及其左侧的半平面；4x₂≤12是代表x₂ =3这条直线上的点及其下方的半平面；x₁+2x₂≤8是代表x₁+2x₂=8这条直线上的点及其左下方的半平面。同时满足例1.4中所有约束条件的点如图1.1中阴影部分所示，图中凸多边形OABCD所包含的阴影部分区域中的每一个点（包括边界点）都是这个线性规划问题的可行解，将该区域称为线性规划问题的可行解区域，即可行域。

目标函数z=2x₁+3x₂可表示为斜率为，截距为的一条直线，即

位于这条直线上的点，具有相同的目标函数值，该直线也被称为目标函数的“等值线”。例如取z =6，则直线2x₁+3x₂=6的截距为2，如图1.1所示。随着参数z从小到大变化，直线沿其法线方向向右上方移动（图1.1中箭头方向）。一直移动到目标函数直线与可行解区域相切时为止，切点即代表最优解的点。当直线移动到B点时，目标函数的值在可行域边界上实现最大化，此时，即得到了例1.4的最优解，即在B点取到唯一最优解。由B点坐标知，最优解为x₁ =4，x₂ =2，最优目标函数值maxz =14。

然而对于一般的线性规划问题的求解还可能出现其他情况。

（1）最优解不唯一。如例1.4中的目标函数改为z=2x₁+4x₂，此时目标函数的等值线与可行域的边界x₁+2x₂=8平行。当目标函数值由小变大，即目标函数等值线向右上方移动直至z最大。此时目标函数等值线与可行域的边界在BC线段上相切，如图1.2所示，则线段BC上任一一点均为线性规划问题的最优解。

图1.1 图解法

图1.2 最优解不唯一

（2）无界解。如例1.4中的约束条件改为

通过图1.3可以看出，可行域可以向右侧无限延伸，该问题的可行域无界。目标函数的等值线可以向右上方无限移动，目标函数值可无限增大，那么称这种情况为无界解。

图1.3 无界解

（3）无可行解。若例1.4中的约束条件改为

根据图解法求解时，可以看出满足所有约束的可行解不存在，即可行域为空集。说明线性规划问题无可行解。

一般来说出现无界解和无可行解的两种情形时，说明线性规划的数学模型有误。前者缺乏必要的约束条件，后者则意味约束条件互相矛盾。通过讨论可以知道，线性规划的解有如图1.4所示的几种情况。

图1.4 线性规划解的情况

1.2.2 线性规划问题的基本概念

在讨论线性规划问题一般的求解方法之前，首先需要了解线性规划解的基本概念和性质。因为任一线性规划问题都可以转化为其标准形式，记，，则线性规划的标准型还可以写成如下向量形式：

（1）可行解和最优解。满足约束条件式（1.2.2）和式（1.2.3）的解称为线性规划问题的可行解，可行解组成的集合称为可行域。其中，使目标函数达到最大值的可行解称为最优解。

约束条件式（1.2.2）的系数矩阵

是m× n矩阵（设m< n），A的秩r(A )≤m。若r(A )<m，则称该线性规划问题是退化的，否则就称为是非退化的。

（2）基。若系数矩阵A的秩r(A )=m，称A的任一m× m非奇异子矩阵B为线性规划问题的一个基。不失一般性，设

当确定了线性规划的一个基B，则B中的每一个列向量称为基向量，与基向量 P_j所对应的变量x_j称为基变量。线性规划中其他的变量均称为非基变量。

（3）基解。在线性规划的约束条件式（1.2.2）中，令所有的非基变量，式（1.2.2）可表示成

且由于B为线性规划的一个基，因此B为可逆阵。由式（1.2.5）可得m个基变量的唯一解

将这个解加上n-m个非基变量取0的值，则得到线性规划的一个解，其称为线性规划问题的基解。由于线性规划中基的个数不超过C^m_n个，故基解的个数也不超过C^m_n个。

（4）基可行解。满足非负约束式（1.2.3）的基解称为基可行解。

下面结合一个线性规划的例子，来说明有关线性规划解的概念。

例1.5 对于线性规划问题

其系数矩阵为，矩阵A的秩r(A )=3，因此该线性规划为非退化的。在矩阵A中有个3× 3的子矩阵。例如，取A的非奇异子矩阵，则其构成线性规划的一个基。与之对应的x₃，x₄和x₅称为基变量，其余的变量x₁和x₂称为非基变量。令所有非基变量，得出基变量的唯一解，即，我们把这个解称为基解，该基解满足非负约束，也被称为基可行解。

又如，取下列非奇异子矩阵

该矩阵也构成线性规划的一个基。与之对应的x₂，x₃和x₄称为基变量，其余的变量x₁和x₅为非基变量。令所有非基变量x₁=x₅=0，同理求得：x₂=8，x₃=16，。可见，该基解不满足非负约束，故称为基非可行解。

对于线性规划来说，可行解、基解、基可行解三者之间的关系如图1.5所示。

图1.5 线性规划解的关系

1.2.3 线性规划问题解的性质

1.基本概念

定义1.2.1 设集合为n维欧氏空间的一个点集，若S中的任意两点连线上的所有点仍在S中，则称S为凸集。

如实心圆（球）或实心椭圆（球）、长方形（体）或多边形（体）等都是凸集，圆环等不是凸集。如图1.6中的（a）、（b）和（c）都是凸集，（d）和（e）都不是凸集。需要我们注意的是，凸集的交集为凸集，但凸集的并集不一定是凸集。

图1.6 凸集与非凸集示例

定义1.2.2 设是n维欧氏空间Rⁿ中的k个点，若存在，满足且0≤w_i≤1，，则称

为的凸组合。（当0<w_i<1时，称为严格凸组合）

定义1.2.3 设S为凸集，x∈S，若x不能用S中两个不同点x⁽¹⁾，x⁽²⁾的一个严格凸组合来表示，则称x为S中的一个顶点（或极点）。

2.相关性质

以下通过几个定理说明线性规划问题解的相关性质。

定理1.2.1 若线性规划问题存在可行解，则线性规划问题的可行域是凸集。

证明 由式（1.1.5），记线性规划的可行域为。设和为S中任意两点，有X⁽¹⁾≥0，X⁽²⁾≥0且

X⁽¹⁾和X⁽²⁾连线上的任意一点可表示为，其中。易知，X≥0。由式（1.2.6），可得

所以X∈S，根据凸集的定义，S为凸集。

定理1.2.2 线性规划问题的可行解为基可行解的充分必要条件是X的正分量所对应的系数列向量线性无关。

证明 （1）必要性：由基可行解的定义显然成立。

（2）充分性：若线性规划问题可行解的正分量所对应的系数列向量线性无关，由于（rA）=m，则k≤m。

若k=m，那么是线性规划问题的一个基，对应的基可行解就是；若k<m，那么一定可以从A的其余个列向量中选择个列，与构成一个基，其对应的解恰为X，根据定义知，其为基可行解。

定理1.2.3 线性规划问题的基可行解X对应于可行域S的一个顶点。

证明 不失一般性，假设基可行解X的前m个分量为正。因此有

现在用反证法分两方面来证明。

（1）X不是基可行解不是可行域的顶点。根据定理1.2.2，若X不是基可行解，则其正分量所对应的系数列向量线性相关，即存在一组不全为零的数，使得

将式（1.2.8）两端分别乘以μ（μ>0）得

用式（1.2.7）分别加上和减去式（1.2.9），得

令

当μ充分小时，可使得，且，即X是X(1)，X⁽²⁾连线的中点，X不是可行域S的顶点。

（2）X不是可行域S的顶点不是基可行解。

若不是可行域S的顶点，故在可行域S中可以存在两个不同的点和，使得（0<α<1），也可写为。若可行解X的非零分量的个数超过m个，它一定不是基可行解；如果可行解X的非零分量的个数不超过m个，不妨设前m个分量不等于零，其余分量都等于零，即当j>m时，必有，进而可得

将式（1.2.10）和式（1.2.11）相减，得

因，所以式（1.2.12）中，不全为零，故线性相关，因此X不是基可行解。

定理1.2.4 如果线性规划问题式（1.1.5）存在最优解，则一定存在一个基可行解是最优解。

证明 设是线性规划可行域S的全部顶点。设最优解X⁽⁰⁾不是顶点，目标函数在处达到最大，即。因为X⁽⁰⁾不是顶点，所以X⁽⁰⁾可用S的顶点的凸组合表示为，，因此

在所有的顶点中必然能找到一个点X^*，使，根据式（1.2.13），则有

根据假设CX(0)是目标函数的最大值，又由于，因此目标函数在顶点X^*处也达到最大值，可知基可行解X^*也为最优解。

对于目标函数可能在多个顶点处达到最优的情形，不妨设是目标函数达到最优的顶点，则它们的凸组合

仍然使目标函数达到最优，此时线性规划问题有无穷多个最优解。

通过以上定理，可以得到以下结论。

（1）线性规划问题的可行域（可行解集）是一个凸集，可能有界也可能无界，但其顶点（极点）的个数是有限的。

（2）线性规划问题的每个基可行解都对应于可行域的顶点。

（3）若线性规划问题有最优解，则其最优解必在可行域的某个（或多个）顶点上。

上述结论为我们提供了寻求线性规划问题最优解的途径，在基可行解中寻找最优解，在一个线性规划问题中基可行解的个数是有限的，不会超过基解的个数，同时基解的个数不会超过C^m_n，其中m， n分别为线性规划问题[式（1.1.5）]中系数矩阵A的行数和列数。