运筹学单纯形法中，为什么检验数小于等于零才有最优解？？77

发布网友发布时间：2023-09-22 16:32

我来回答

共4个回答

热心网友时间：2023-10-20 00:57

因为基本可行解的个数有限，故经有限次转换必能得出问题的最优解。

从线性方程组找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小了，决定下一步选择的单纯形。通过优化迭代，直到目标函数实现最大或最小值。

如果线性问题存在最优解，一定有一个基可行解是有最优解。因此单纯形法迭代的基本思路是：先找出一个基可行解，判断其是否为最优解。如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直找到最优解为止。

扩展资料：

由于目标函数和约束条件内容和形式上的差别，线性规划问题可以有多种表达式。因此，为了便于讨论和制定统一的算法，在制定单纯形法时，规定使用单纯形法求解的线性规划问题需要有一个标准形式，它有下面三个特征：

(1) 标准形式目标函数统一为求极大值或极小值，但单纯形法主要用来求解极大值；

(2) 所有约束条件（除非负条件外）都是等式，约束条件右端常数项bi全为非负值；

(3) 所有变量的取值全为非负值。

热心网友时间：2023-10-20 00:57

对于线性规划问题标准型，最优性判别条件所有检验数均小于等于零。如果是求最小问题，则最优性判别条件是所有检验数均大于等于零。
检验数是用非基变量表示基变量，带入目标函数的表达式中得来的非基变量的系数。它的含义是对应非基变量如果取得一个大于零的值时，能给目标函数增大的量为该值的检验数倍。对最大化问题，如果检验数均小于等于零，意味着再进行迭代，也不能使目标函数增大了。最小化问题，同理！

热心网友时间：2023-10-20 00:58

用非基变量表示目标函数的表达式：Z=Z0+(Cj-Zj)Xn
Xn为非基变量，Cj-Zj为检验数，Z0为求出的基可行解.
从表达式很明显看出只有Cj-Zj≤0,Z达到最大值,即最优解.

热心网友时间：2023-10-20 00:58

举例来说基变量价值系数C和基变量系数P相乘，再累加求和是目标函数z

假设基变量是货物，z是总利润，基变量的售价是价值系数Cj，也就是单价

根据检验数公式
可以形象理解为：Cj如果大于z，也就是售出基变量，那么说明卖价值系数为Cj的单品比售出基变量的总利润还要大（即检验数大于零），那么，售卖该货物实则会有更大的利润，可使目标函数z继续增大。

如果说所有的检验系数都小于等于0那么证明变更售卖任何其他一种货物（变量）均不可能使得利润（z）变大。