第一章 线性规划
这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。
最后，来讨论线性规划的可行域和最优解的几种可能的情况。 1、可行域为封闭的有界区域 (a)有唯一的最优解； (b)有一个以上的最优解； 2、可行域为非封闭的无界区域 (a)有唯一的最优解； (b)有一个以上的最优解；
(c)目标函数无界（即虽有可行解，但在可行域中，目标函数可以无限增大或无限减小），因而没有最优解。
3、可行域为空集，因而没有可行解。 以上几种情况的图示如下：
(a)可行域封闭，唯一最优解 (b)可行域封闭，多个最优解 (c)可行域开放，唯一最优解
(d)可行域开放，多个最优解
(e)可行域开放，目标函数无界
(f) 可行域为空集
图1.4
16
第一章 线性规划
§1.5 线性规划的基、基础可行解
由于图解法无法解决三个变量以上的线性规划问题，我们必须用代数方法来求得可行域的极点。先从以下的例子来看。 例1.9
max z= x1 +2x2 s.t.
x1 +x2 ≤3
x2 ≤1 x2 ≥0
x1,
(1) (2)
这个问题的图解如图1.5所示。引进松弛变量x3，x4?0，问题变成为标准形式 max z= x1 +2x2 s.t.
3 2 1 C x1=0 O 0 x2=0 1 2 A 3 x1 x2 D x1
x1
x2 x2 +x2 +x3
x3
=3 x4 ?0
(1) (2)
+x4 =1
x3=0 B x4=0 图 1.5
由上图可以看出，直线AD对应于约束条件(1)，位于AD左下侧半平面上的点满足约束条件x1+x2<3，即该半平面上的点，满足x3>0。直线AD右上侧半平面上的点满足约束条件x1+x2>3，即该半平面上的点，满足x3<0，而直线AD上的点，相应的x3=0。同样，直线BC上的点满足x4=0，BC以下半平面中的点，满足x4>0。BC以上半平面中的点，满足x4<0。另外，OA上的点满足x2=0，OD上的点满足x1=0。
17
第一章 线性规划
由此可见，上图中约束直线的交点O，A，B，C和D可以由以下方法得到：在标准化的等式约束中，令其中某两个变量为零，得到其他变量的唯一解，这个解就是相应交点的坐标，如果某一交点的坐标（x1，x2，x3，x4）全为非负，则该交点就对应于线性规划可行域的一个极点（如点A，B，C和O）；如果某一交点的坐标中至少有一个分量为负值（如点D），则该交点不是可行域的极点。
由图1.5可知，O点对应于x1=0，x2=0，在等式约束中令x1=0，x2=0，得到x3=3，x4=1。即O点对应于极点X=(x1，x2，x3，x4)T=(0，0，3，1)T。由于所有分量都为非负，因此O点是一可行域的极点。
同样，A点对应于x2=0，x3=0，x1=3，x4=1；B点对应于x3=0，x4=0，x1=2，x2=1；C点对应于x1=0，x4=0，x2=1，x3=2。以上都是极点。而D点对应于x1=0，x3=0，x2=3，x4=-2，x4的值小于0，因而不是极点。
同时，我们也注意到，如在等式约束中令x2=0，x4=0，由于线性方程组的系数行列式等于0，因而x1、x3无解。这在图1.5中也容易得到解释，这是由于对应的直线x2=0和x4=0平行，没有交点的缘故。
对于一般的问题，获得线性规划可行域极点的方法可描述如下： 设线性规划的约束条件为
a11x1a21x1
?a12x2???a1nxn?a22x1???a2nxn????b1?b2? ?bm?0?am1x1?am2x1???amnxnx1x2xn其中系数矩阵为m×n的矩阵，设n>m，并假设系数矩阵的秩为m，即系数矩阵的m个行向量是线性无关的。在约束等式中，令X=(x1，x2，?，xn)T中n-m个变量为零，如果剩下的m个变量在线性方程组中的系数矩阵是非奇异的，这m个变量有唯一解。这n个变量的值组成的向量X就对应于n维空间中若干个超平面的一个交点。当这n个变量的值都是非负时，这个交点就是线性规划可行域的一个极点。
根据以上分析，得到以下定义： 定义1.6 线性规划的基、基变量、非基变量
标准化的线性规划问题的约束系数为m×n阶矩阵，m>n，矩阵的秩为m。矩阵中的一个非奇异的m×m子矩阵称为线性规划的一个基。
与基矩阵对应的变量称为基变量，其余的变量称为非基变量。 定义1.7 线性规划问题的基础解、基础可行解和可行基
18
第一章 线性规划
对于线性规划的一个基（m×m阶矩阵），n个变量划分为m个基变量、n-m个非基变量。令n-m个非基变量全等于0，m个基变量有唯一解。这样得到的n个变量的一个解成为基础解。如果基础解中所有的变量都是非负的，这个解称为基础可行解。 如果一个基对应的基础解是可行解，这个基称为可行基。
根据以上的分析，我们不加证明地给出以下定理： 定理1.1 线性规划的基础可行解就是可行域的极点。
这个定理是线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基础可行解这一代数概念联系起来，因而可以通过求基础可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。 例1.10 求例1.9中线性规划可行域的所有极点。
这个线性规划问题的标准形式的约束条件为： x1 +x2 +x3
系数矩阵
?1110?A??a1,a2,a3,a4???? 0101?? =3
x2 +x4 =1
x1, x2, x3, x4 ≥0
A矩阵包含以下六个2×2的子矩阵：
?1B1??a1a2????0?1B4??a2a3????1其中
1? ?1?1? 0???1B2??a1a3????0?1B5??a2a4????11??1 ??B?aa?314?00???0??1 ??B?aa?634?01???0? ?1?0? 1???11?B2??a1,a3???? 00??其行列式det B2=0，因而B2不是线性规划的一个基。其余均为非奇异方阵，因此该问题共有5个基。
对于基B1=[a1，a2]，基变量为x1，x2，非基变量为x3，x4。令非基变量x3，x4
等于0，求解线性方程组
x1
得到基变量的值
x1=2，x2=1
19
+x2 x2
=3 =1
第一章 线性规划
基变量全为非负，因而B1是可行基。
（x1，x2，x3，x4）=（2，1，0，0）
为对应于基B1的一个基础解。由于这个基础解的各变量均为非负，故这是一个基础可行解，因而对应于一个极点。这个极点就是图1.5中的极点B。
对于基B3=[a1，a4]，基变量为x1，x4，非基变量为x2，x3。令非基变量x2，x3
等于0，求解线性方程组
x1
得到基变量的值
x1=3，x4=1
（x1，x2，x3，x4）=（3，0，0，1）
基变量全为非负，因而B1是可行基。
为对应于基B3的一个基础解。由于这个基础解的各变量均为非负，故这是一个基础可行解，因而对应于一个极点。这个极点就是图1.5中的极点A。
对于基B4=[a2，a3]，基变量为x2，x3，非基变量为x1，x4。令非基变量x1，x4
等于0，求解线性方程组
x2 x2
得到基变量的值
x2=1，x3=2
（x1，x2，x3，x4）=（0，1，2，0）
基变量全为非负，因而B1是可行基。
为对应于基B4的一个基础解。由于这个基础解的各变量均为非负，故这是一个基础可行解，因而对应于一个极点。这个极点就是图1.5中的极点C。
对于基B5=[a2，a4]，基变量为x2，x4，非基变量为x1，x3。令非基变量x1，x3
等于0，求解线性方程组
x2 x2
得到基变量的值
x2=3，x4=-2
（x1，x2，x3，x4）=（0，3，0，-2）
20
基变量出现负数，因而B5不是可行基。
+x4
=3 =1 +x3
=3 =1 x4
=3 =1