原始-对偶方法

原始-对偶方法的基本思想是为了得到原问题的基础容许解，常用的方法是首先在原问题中引入人工变量，将目标函数换成人工变量之和的负值；然后极大化目标函数，并将得到的最优基础容许解消去人工变量，此解即为原问题的基础容许解，如果对偶问题有容许解与原问题的基础容许解满足互补松弛条件，则原问题的基础容许解也就成为最优基础容许解1。

基本思想原始-对偶方法是求解线性规划的一种算法，指求解线性规划的一类特殊对偶型方法，其特殊性在于，它是以松弛互补性条件为基础去构造一个由原问题产生的限定问题，并通过求解此限定问题去改善解对原问题的可行性，这一过程含有单纯形法与对偶单纯形方法的思想，所以有此名2。

方法步骤设原问题(P)为，满足；其对偶问题(D)为，满足，已知y是(D)的一个可行解，即对于，均有，Aj为A的第j列，其方法为：

1.由已知y，记，求解限定问题(RP)：

满足

及(为人造变量)。

2.(最优判定) 是否? 若是，停止迭代，则当前解为最优解，否则，记为限定问题(RP)的对偶问题的最优解。

3.检验是否存在?若不存在，则停止迭代，原问题不可行。

4.(调整指标集Q及对偶解y)取

并以作为新的对偶解，转至第1步。

对于某些组合优化问题，如最短路问题等，相应的限定问题(RP)具有特定的简捷和直观的形式，给求解(RP)带来方便，因此，原始-对偶方法常常加以应用2。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所