Question

为什么线性规划问题的最优解一定能在可行域顶点中找到

Answer 1

最优解肯定能够在可行域的顶点中找到，也就是说，只要把可行域的所有顶点找出来，然后比较它们的函数值，最大的那个解就一定是最优解。其

实，几乎所有讲解线性规划的书籍都会证明这个结论，但其证明过程较为复杂。

使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称为该线性规划的一个最优解。

线性规划的最优解不一定唯一，若其有多个最优解，则所有最优解所构成的集合称为该线性规划的最优解域。

扩展资料:

只有直线z=mx+y跟可行域里面的某线段平行的时候才会出现无数最优解的可能，否则最优解只能有一个。

要求的是z最大值，直线y=-mx+z中的z就是y轴截距，所以就是y轴截距的最大值。

画出可行域，可以发现直线y=-mx+z应该跟(1，22/5)，(5，3)2点所成直线平行m=(22/5-3)/(1-5)。

解决线性规划问题的步骤：

①列出约束条件及目标函数。

②画出约束条件所表示的可行域。

③在可行域内求目标函数的最优解及最优值。

参考资料来源：百度百科——线性规划问题

Answer 2

们求解线性规划问题时会发现这样一个规律：最优解总能够在可行域的顶点中找到。

我们先给出肯定的回答：最优解肯定能够在可行域的顶点中找到，也就是说，只要你把可行域的所有顶点找出来，然后比较它们的函数值，最大的那个解就一定是最优解。其实，几乎所有讲解线性规划的书籍都会证明这个结论，但其证明过程较为复杂。因此，为了便于理解，我尽量以通俗易懂的方式向大家证明这个结论。

首先需要理解一下顶点的概念。如果图形中某一点不在任何其它不同的两点间的线段上，则称该点为图形的顶点。如下图所示，对于紫色点，都可以找到图形中另外不同的两点，使得紫色点恰好在那两点间的线段上。

用数学语言来定义就是：是图形的顶点当且仅当不存在实数和，满足且。
（注：两点间线段上任意一点可以用来表示。）

这个定义非常重要，在后面的证明中将反复利用。

我们先从直观上来看这个规律。如下图所示，只要最优解不是顶点，就可沿目标函数等值线移动直至达到某个约束方程的边界，如果此时仍然不是顶点，那么继续沿着等值线方向移动达到另一个约束方程的边界，如此继续一定找到最优顶点。

设线性规划的一般形式为

为了更好地刻画顶点，将上述一般形式等价转换为标准形式：

如何转换？利用以下两个线性式子的等价关系：

先利用(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时，一维的线性方程（组）必有唯一解，此时得到的最优解必为顶点。因此，按上述方法是一定可以找到一个最优解的顶点。

至此我们的问题已经证明完成。