原始-對偶方法的基本思想是為了得到原問題的基礎容許解，常用的方法是首先在原問題中引入人工變數，將目標函式換成人工變數之和的負值；然後極大化目標函式，並將得到的最優基礎容許解消去人工變數，此解即為原問題的基礎容許解，如果對偶問題有容許解與原問題的基礎容許解滿足互補鬆弛條件，則原問題的基礎容許解也就成為最優基礎容許解。
基本介紹
- 中文名：原始-對偶方法
- 所屬學科：數學
- 所屬問題：組合學（組合最最佳化)
- 簡介：求解線性規劃的一種算法
- 相關概念：鬆弛互補定理
基本思想,方法步驟,
基本思想
原始-對偶方法是求解線性規劃的一種算法，指求解線性規劃的一類特殊對偶型方法，其特殊性在於，它是以鬆弛互補性條件為基礎去構造一個由原問題產生的限定問題，並通過求解此限定問題去改善解對原問題的可行性，這一過程含有單純形法與對偶單純形方法的思想，所以有此名。
方法步驟
設原問題(P)為
，滿足
；其對偶問題(D)為
，滿足
，已知y是(D)的一個可行解，即對於
，均有
，Aj為A的第j列，其方法為：
1.由已知y，記
，求解限定問題(RP)：
2.(最優判定) 是否
? 若是，停止疊代，則當前解為最優解，否則，記
為限定問題(RP)的對偶問題的最優解。
3.檢驗是否存在
?若不存在，則停止疊代，原問題不可行。
4.(調整指標集Q及對偶解y)取
對於某些組合最佳化問題，如最短路問題等，相應的限定問題(RP)具有特定的簡捷和直觀的形式，給求解(RP)帶來方便，因此，原始-對偶方法常常加以套用。
