换入变量,又称入基变量,是指在求最大目标函数的问题中,选基检验数大于0,被选定换到基变量中去的非基变量。
基本内容单纯形法的基本思路:从可行域中某一个顶点开始,判断此顶点是否是最优解,如不是,则再找另一个使得其目标函数值更优的顶点,称之为迭代,再判断此点是否是最优解。直到找到一个顶点为其最优解,就是使得其目标函数值最优的解,或者能判断出线性规划问题无最优解为止。
所谓最优性检验就是判断已求得的基本可行解是否是最优解。对于求最大目标函数的问题中,对于某个基本可行解,如果所有检验数 ,则这个基本可行解是最优解。对于求目标函数最小值的情况,只需把 改为 。1
确定方法在单纯形法的求解中,通过检验,如果这个初始基本可行解不是最优解,则需要进行基变换找到一个新的可行基。具体的做法是从可行基中换一个列向量,得到一个新的可行基,使得求解得到的新的基本可行解,其目标函数值更优。为了换基就要确定换入变量与换出变量。
从最优解判别定理知道,当某个 时,非基变量 变为基变量不取零值可以使目标函数值增大,故我们要选基检验数大于0的非基变量换到基变量中去(称之为换入变量)。若有两个以上的 ,则为了使目标函数增加得更大些,一般选其中的 最大者的非基变量为换入变量。
当存在退化问题时,需要用勃兰特法则来确定换入变量和换出变量。在所有检验数大于零的非基变量中,选一个下标最小的作为换入变量。2
举例例1.设线性规划问题为:
用单纯形法求解过程第一次迭代中的换入变量是?
解:单纯形法求解过程的单纯形表如下:
|| ||
在第一次迭代中,可以得到 ,一般选其中的 最大者的非基变量为换入变量,所以换入变量为 。
特殊情况1.对于求最大目标函数的问题,在某次迭代的单纯形表中,如果存在着一个大于零的检验数,并且该列的系数向量的每个元素 都小于或等于零,即确定了换入变量,却不能确定换出变量。则此线性规划问题是无界的。
2.在一个已得到最优解的单纯形表中,如果存在一个非基变量的检验数 为零,把这个非基变量作为换入变量进行迭代,在新的单纯形表中,基变量的检验数为零,用同样的方法可证明其他的非基变量的检验数不变,仍然小于零,这样就证明了新得到的基本可行解仍然是最优解。即对于某个最优的基本可行解,如果存在某个非基变量的检验数为零,则此线性规划问题有无穷多最优解。
3.在单纯形法计算过程中,在确定换入变量之后,确定换出变量时有时存在两个以上的相同的最小比值,这种情况称之为退化。1
应用单纯形法是一种主要的解决线性规划问题的方法,它在生活的成本问题、交通选择或规划学术问题等方面得到广泛应用。其中,要掌握单纯形法的计算过程,根据目标方程,约束条件建立初始单纯形表;找出初始可行基,确定初始基可行解;算出非基变量的检验数是否大于零;若检验数全部小于等于零,则可停止计算,若检验数有大于零,取最大的检验数所对应的为换入变量,再按规则找出换出变量,重新列出单纯形法,进行迭代。正确的应用单纯形法解决问题能够提高准确率,从而进行合理的规划安排,使得效果或收益达到期待化或最优化。3
本词条内容贡献者为:
王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所