-
對偶線性規劃
鎖定
每個線性規劃問題都有一個與之對應的對偶問題。對偶問題是以原問題的約束條件和目標函數為基礎構造而來的。對偶問題也是一個線性規劃問題，因此可以採用單純形法求解。對偶問題的最優解也可以通過原問題的最優解得到，反之亦然。而且，在某些情況下，利用對偶理論求解線性規劃問題更為簡單，而且有助於深入瞭解待求問題的本質。
- 中文名
- 對偶線性規劃
- 外文名
- dual linear programming
- 應用學科
- 數學術語
- 範 疇
- 數理科學
- 解 法
- 對偶單純形法
- 涉 及
- 對偶問題
- 釋 義
- 每個線性規劃問題都有一個與之對應的對偶問題
對偶線性規劃信息介紹
每個線性規劃問題都有一個與之對應的對偶問題。對偶問題是以原問題的約束條件和目標函數為基礎構造而來的。對偶問題也是一個線性規劃問題，因此可以採用單純形法求解。對偶問題的最優解也可以通過原問題的最優解得到，反之亦然。而且，在某些情況下，利用對偶理論求解線性規劃問題更為簡單，而且有助於深入瞭解待求問題的本質。
對偶線性規劃的經濟背景是：若原問題是利用有限資源安排最優生產方案，以獲得最大總產值的線性規劃問題，則它的對偶問題就是在相同資源的條件下，正確估計資源的使用價值，以達到支付最少費用的線性規劃問題.簡言之，若原問題為求解資源的最優配置問題，則對偶問題就是求解估價資源的使用價值問題。
對偶線性規劃基本性質
原始線性規劃與對偶線性規劃問題不僅在數學模型的形式上存在着相互對應的關係，而且它們的目標函數、可行解及最優解之間也存在着確定的聯繫。
設有一對線性規劃問題為：
（1）原始問題
求
滿足
（2）對偶問題
求
滿足
定理：互為對偶的線性規劃（1）和（2）有最優解的充分必要條件是它們同時有可行解。
證明：必要性是顯然的，下面來證明充分性。
設
是（1）的可行解，
是（2）的可行解。
則有
若
是（1）的任意一個可行解，則有
設
是（2）的任意一個可行解，用同樣的推理方法可得
