线性规划问题解的相关问题

线性规划问题的基解、可行解与基可行解

对于$n$维空间中的线性规划问题，$n$个线性无关的约束条件的交点即为线性规划问题的一个基解。可行域为所有约束条件的交集，可行域中所有的解均为可行解，在可行域中的基解为基可行解。如下以一个2维空间为例说明线性规划问题的基解、可行解与基可行解。
$$maxz=2x_1+3x_2$$$$s.t.\{\begin{array}{l}{x}_1+2x_2\le 8,\\ 4x_1\le 16,\\ 4x_2\le 12,\\ x_1,x_2\ge 0.\end{array}\text{\hspace{1em}(1)}$$
如下图所示，$x_1+2x_2\le 8$, $4x_1\le 16$, $4x_2\le 12$, $x_1\ge 0$, $x_2\ge 0$，这五个约束条件共同组成了该线性规划问题的可行域（橙色部分）。五个条件两两之间线性无关，五个条件共有8个交点，故该线性规划问题共有8个基解，其中5个基解落于可行域的边界，即该线性规划问题共有5个基可行解。可行域内部以及可行域边界上的任意一点均为该线性规划问题的可行解。

                                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~                                                          图1

线性规划问题目标函数的走向

对于只有两个变量的线性规划问题而言，图解法是一种常用的求解方法。求解过程中涉及目标函数等值线的移动问题，若线性规划问题的目标为最大化，那么目标函数需要朝增加的方向移动。反之，若线性规划问题的目标为最小化，那么目标函数需要朝减小的方向移动。目标函数的增加或减小方向需要根据目标函数的梯度来确定。

多元函数的梯度是一个向量，它是多元函数在某一点处变化率最大的方向。梯度的各个分量表示多元函数在各个决策变量方向上的变化率。

对于只有两个变量的线性规划问题而言，目标函数的梯度为一个常数向量，即目标函数值增加最快的方向是唯一确定的，即对于只有两个变量的线性规划问题而言，其目标函数的变化幅度是线性的。依然以（1）式的线性规划问题为例，说明目标函数的增加与减小方向。

                                                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~                                                                   图2

       ~~~~~~       以上三条红绿蓝直线分别为 $x_1+2x_2\le 8$, $4x_1\le 16$, $4x_2\le 12$三个线性约束条件的边界，黑色虚线为目标函数的一族等值线。目标函数的梯度为$(2,3)$，目标函数增加最快的方向即为上图中红色箭头直线所指的方向，即梯度方向为从原点出发，一直指向点(2,3)的一个向量。从图中可看出目标函数的梯度向量与目标函数等值线垂直。
       ~~~~~~       此外，若上述线性规划问题的目标函数该为最小化，那么其目标函数值减小最快的方向即为负梯度方向，即$(-2,-3)$。
       ~~~~~~       还需要指出的一点是，图2中蓝色的虚线箭头方向同样也为目标函数增加的方向，但目标函数值在这些方向上的增加值都要小于梯度方向。
基于目标函数的走向，可以说明线性规划问题的最优解不会在可行域的内部取得，通常都在可行域的顶点处（此时目标函数有唯一最优解）或可行域的边界（此时目标函数有无穷多最优解）取得。这是因为

分析1：如果可行域为有界凸集的话，则任何一个在可行域内部的点均可以表示为可行域的顶点的凸组合。假定线性规划问题的最优解在可行域内部的一点取得，那么将该点表示为可行域顶点的线性组合带入目标函数中，那么目标函数值可表示为以所有顶点作为解取得的目标函数值的凸组合形式，则总会存在一个顶点上的目标函数值小于或大于在可行域内部的一点上的目标函数值，这显然与最优解在可行域内部的一点取得矛盾。

分析2：在线性规划问题中，目标函数的变化幅度是线性的，即无论目标函数增加还是减小，其值的变化都是单向的，如果在可行域的内部存在一个更优的点，以目标函数需要最大化为例，沿着梯度方向目标函数还可以继续移动，直至达到可行域的边界为止，此时目标函数的取值要大于在可行域内部那一点取得的值。