线性规划最优解 一定是可行域顶点吗 |
您所在的位置:网站首页 › 非线性规划一定可以找到最优解 › 线性规划最优解 一定是可行域顶点吗 |
们求解线性规划问题时会发现这样一个规律:最优解总能够在可行域的顶点中找到。 我们先给出肯定的回答:最优解肯定能够在可行域的顶点中找到,也就是说,只要你把可行域的所有顶点找出来,然后比较它们的函数值,最大的那个解就一定是最优解。其实,几乎所有讲解线性规划的书籍都会证明这个结论,但其证明过程较为复杂。因此,为了便于理解,我尽量以通俗易懂的方式向大家证明这个结论。 首先需要理解一下顶点的概念。如果图形中某一点不在任何其它不同的两点间的线段上,则称该点为图形的顶点。如下图所示,对于紫色点,都可以找到图形中另外不同的两点,使得紫色点恰好在那两点间的线段上。 用数学语言来定义就是:是图形的顶点当且仅当不存在实数和,满足且。(注:两点间线段上任意一点可以用来表示。) 这个定义非常重要,在后面的证明中将反复利用。 我们先从直观上来看这个规律。如下图所示,只要最优解不是顶点,就可沿目标函数等值线移动直至达到某个约束方程的边界,如果此时仍然不是顶点,那么继续沿着等值线方向移动达到另一个约束方程的边界,如此继续一定找到最优顶点。 设线性规划的一般形式为 为了更好地刻画顶点,将上述一般形式等价转换为标准形式: 如何转换?利用以下两个线性式子的等价关系: 先利用(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时,一维的线性方程(组)必有唯一解,此时得到的最优解必为顶点。因此,按上述方法是一定可以找到一个最优解的顶点。 至此我们的问题已经证明完成。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |