线性规划单纯形法计算步骤详解
线性规划中,如何已知原问题的最优解,直接写出对偶问题的最优解?
线性规划中,如何已知原问题的最优解,直接写出对偶问题的最优解?
是的。根据对偶论,对偶问题与原问题是互为对偶问题的,且对偶问题的目标函数恰好等于原问题最有目标函数,并且可以证明这一目标函数值也是最优的,反过来同样成立,假设对偶问题的最优解不唯一,那么其对偶问题(也就是原问题)的最优解也不唯一,这与原问题有唯一解矛盾。
因为原问题与对偶问题是相互对偶的,所以他们有一定的对应关系。在有限最优解的方面:原问题有有限最优解只能保证对偶问题有有有限最优解。原问题松弛变量的检验数的相反数就是对偶问题的最优解。
对偶理论(Duality theory)研究线性规划中原始问题与对偶问题之间关系的论。发展简在线性规划早期发展中最重要的发现是对偶问题,即每一个线性规划问题(称为原始问题)有一个与它对应的对偶线性规划问题(称为对偶问题)。
扩展知识:
对偶问题的最优解:从原始问题的最终单纯形表中(最优单纯形算子)可直接得到对偶问题的最优解。原始问题中松弛变量的检验数对应着对偶问题的解(符号相反)。
在用单纯形法时每一步迭代可得到原始问题的可行解x0和对偶问题的补充解y0且cx0y0b,若x0不是原始问题的最优解,y0就不是对偶问题的可行解。最后一步迭代得到原始问题的最优解x*和对偶问题的补充最优解y*,且cx*y*b。y*是原始问题的影子价格。
对偶问题:每一个线性规划问题都伴随有另一个线性规划问题,称为对偶问题。原来的线性规划问题则称为原始线性规划问题,简称原始问题。对偶问题有许多重要的特征,它的变量能提供关于原始问题最优解的许多重要资料,有助于原始问题的求解和分析。
线性规划的基本特征?
线性规划问题的形式特征,三个要素组成:
1、变量或决策变量;
2、目标函数;
3、约束条件。
求解线性规划问题的基本方法是单纯形法,已有单纯形法的标准软件,可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。
为了提高解题速度,又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题,也可采用图解法求解。
这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解,但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。