原始-对偶方法的基本思想是为了得到原问题的基础容许解，常用的方法是首先在原问题中引入人工变数，将目标函式换成人工变数之和的负值；然后极大化目标函式，并将得到的最优基础容许解消去人工变数，此解即为原问题的基础容许解，如果对偶问题有容许解与原问题的基础容许解满足互补鬆弛条件，则原问题的基础容许解也就成为最优基础容许解。
基本介绍
- 中文名：原始-对偶方法
- 所属学科：数学
- 所属问题：组合学（组合最最佳化)
- 简介：求解线性规划的一种算法
- 相关概念：鬆弛互补定理
基本思想
原始-对偶方法是求解线性规划的一种算法，指求解线性规划的一类特殊对偶型方法，其特殊性在于，它是以鬆弛互补性条件为基础去构造一个由原问题产生的限定问题，并通过求解此限定问题去改善解对原问题的可行性，这一过程含有单纯形法与对偶单纯形方法的思想，所以有此名。
方法步骤
设原问题(P)为
，满足
；其对偶问题(D)为
，满足
，已知y是(D)的一个可行解，即对于
，均有
，Aj为A的第j列，其方法为：
1.由已知y，记
，求解限定问题(RP)：
2.(最优判定) 是否
? 若是，停止叠代，则当前解为最优解，否则，记
为限定问题(RP)的对偶问题的最优解。
3.检验是否存在
?若不存在，则停止叠代，原问题不可行。
4.(调整指标集Q及对偶解y)取
对于某些组合最佳化问题，如最短路问题等，相应的限定问题(RP)具有特定的简捷和直观的形式，给求解(RP)带来方便，因此，原始-对偶方法常常加以套用。
