Question

线性规划最优解 一定是可行域顶点吗

Answer 1

们求解线性规划问题时会发现这样一个规律：最优解总能够在可行域的顶点中找到。
我们先给出肯定的回答：最优解肯定能够在可行域的顶点中找到，也就是说，只要你把可行域的所有顶点找出来，然后比较它们的函数值，最大的那个解就一定是最优解。其实，几乎所有讲解线性规划的书籍都会证明这个结论，但其证明过程较为复杂。因此，为了便于理解，我尽量以通俗易懂的方式向大家证明这个结论。
首先需要理解一下顶点的概念。如果图形中某一点不在任何其它不同的两点间的线段上，则称该点为图形的顶点。如下图所示，对于紫色点，都可以找到图形中另外不同的两点，使得紫色点恰好在那两点间的线段上。
用数学语言来定义就是：是图形的顶点当且仅当不存在实数和，满足且。
（注：两点间线段上任意一点可以用来表示。）
这个定义非常重要，在后面的证明中将反复利用。
我们先从直观上来看这个规律。如下图所示，只要最优解不是顶点，就可沿目标函数等值线移动直至达到某个约束方程的边界，如果此时仍然不是顶点，那么继续沿着等值线方向移动达到另一个约束方程的边界，如此继续一定找到最优顶点。
设线性规划的一般形式为
为了更好地刻画顶点，将上述一般形式等价转换为标准形式：
如何转换？利用以下两个线性式子的等价关系：
先利用(1)在约束条件不等式左边引入一个非负变量，然后再将无约束的变量写成两个新的非负变量之差，从而就等价转换成了标准形式。
有了上面这些准备工作，就可以开始证明我们的问题了。证明思路：任取一个最优解x0，如果它是顶点，那么问题已得证；如果它不是顶点，那么就再找另一个最优解x1，使得新的最优解x1的非零分量个数比x0的少。如果x1也不是顶点，那么就继续寻找使非零分量数减少的最优解x2,x3...，直到找到顶点最优解xr。最后还需要证明xr可以在有限步内找到。
把写成一个的矩阵a，并定义它的列向量形式。再定义。
设是线性规划的一个最优解，若是顶点，则问题已得证。
下面假设不是顶点。不妨设的前k个分量为正数，第k+1到n个分量为零。根据顶点的定义，存在和可行域内的，，满足。设
对每个i，代入式子，得到
因为，所以和符号相反或同时为0。不妨设对所有i都有，。
注意到当i>k时，
因此当i>k时有。
再定义点，由于，因此在和之间（可能与重合），如下图所示：
因此也是一个可行解。
由于是最优解，因此
可以解得，因此，从而也是最优解。
因为当i>k时有，故。再设，定义，那么，并且有
由于和不重合，因此不全为0。不妨设不为0（）。那么令
再令
当时，，
当时，，并且根据的定义，存在某个使得，那么。
因此，的非零分量个数比要少，并且
说明也是一个最优解。
如果不是顶点，那么继续按照前面叙述的方法构造出非零分量个数比少的最优解，直到最优解为顶点为止。由于当非零变量个数为1时，一维的线性方程（组）必有唯一解，此时得到的最优解必为顶点。因此，按上述方法是一定可以找到一个最优解的顶点。
至此我们的问题已经证明完成。

Answer 2

一般是，但要看定义域，，，

Answer 3

也有可能是可行域的一条边