-
強對偶性
鎖定
- 中文名
- 強對偶性
- 外文名
- strong duality property
- 所屬學科
- 數學
- 所屬問題
- 運籌學(線性規劃的對偶理論)
- 相關概念
- 線性規劃,最優解,目標函數等
強對偶性強對偶性定理
若
有最優解
,則
亦有最優解
,而且
的最優解對應的目標函數值相等,即
強對偶性定理證明
證明: 把
分別用矩陣表示。
下面把(1)化為標準形,並求全體檢驗數的表示式。
本定理的逆命題也成立,證法類同。
強對偶性線性規劃的對偶理論
線性規劃的對偶理論指研究線性規劃問題和它對應的對偶問題之間存在的變量、係數及數學符號的嚴格對應關係的理論。線性規劃的對偶理論,不僅存在於原始問題與對偶問題的數學模型中,而且存在於整個求解過程中。線性規劃的對偶理論主要有:
(1)對稱性。即對偶問題的對偶是原始問題。
(3)最優性。若
是原始問題的一個可行解,
是對偶問題的一個可行解,且
,那麼
是原始問題的一個最優解。
(4)無界性。若原始問題(對偶問題)的解無界,那麼對偶問題(原始問題)無可行解。
(5)強對偶性。若原始問題(對偶問題)有一個確定的最優解,那麼對偶問題(原始問題)也有一個確定的最優解,而且這兩個最優解所對應的目標函數值相等,即
。
(6)原始問題(對偶問題)的檢驗數對應於對偶問題(原始問題)的一個解。線性規劃問題的對偶理論,不僅為建立對偶問題的數學模型提供了依據,而且為進一步擴大單純形法求解線性規劃問題的範圍,形成對偶單純形法和進行靈敏度分析奠定了理論基礎
[1]
。
原始問題 | 對偶問題 |
有最優解 | 有最優解 |
有可行解,無有界最優解 | 無可行解 |
無可行解 | 有可行解,無有界最優解 |
無可行解 | 無可行解 |