-
對偶理論
鎖定
- 中文名
- 對偶理論
- 外文名
- Duality theory
- 提出者
- J·von·諾依曼
- 提出時間
- 1947年
- 適用領域
- 自動控制與系統工程範疇
- 應用學科
- 運籌學
對偶理論簡介
對偶理論:研究線性規劃中原始問題與對偶問題之間關係的理論。
對偶理論屬自動控制與系統工程範疇。
對偶理論主要研究經濟學中的相互確定關係,涉及到經濟學的諸多方面。產出與成本的對偶、效用與支出的對偶,是經濟學中典型的對偶關係。經濟系統中還有許多其他這樣的對偶關係。
利用對偶性來進行經濟分析的這種方法,就叫做對偶方法。
每一個線性規劃問題都存在一個與其對偶的問題,在求出一個問題解的同時,也給出了另一個問題的解。
對偶理論發展簡史
在線性規劃早期發展中最重要的發現就是對偶問題,即每一個線性規劃問題(稱為原始問題)都有一個與它對應的對偶線性規劃問題(稱為對偶問題)。1928年美籍匈牙利數學家 J·von·諾伊曼在研究對策論時已發現線性規劃與對策論之間存在着密切的聯繫。兩人零和對策可表達成線性規劃的原始問題和對偶問題。他於1947年提出對偶理論。1951年G.B.丹齊克引用對偶理論求解線性規劃的運輸問題,研究出確定檢驗數的位勢法原理。1954年C.萊姆基提出對偶單純形法,成為管理決策中進行靈敏度分析的重要工具。對偶理論有許多重要應用:在原始的和對偶的兩個線性規劃中求解任何一個規劃時,會自動地給出另一個規劃的最優解;當對偶問題比原始問題有較少約束時,求解對偶規劃比求解原始規劃要方便得多;對偶規劃中的變量就是影子價格。
對偶問題:每一個線性規劃問題都伴隨有另一個線性規劃問題,稱為對偶問題。原來的線性規劃問題則稱為原始線性規劃問題,簡稱原始問題。對偶問題有許多重要的特徵,它的變量能提供關於原始問題最優解的許多重要資料,有助於原始問題的求解和分析。對偶問題與原始問題之間存在着下列關係:①目標函數對原始問題是極大化,對對偶問題則是極小化。②原始問題目標函數中的收益係數是對偶問題約束不等式中的右端常數,而原始問題約束不等式中的右端常數則是對偶問題中目標函數的收益係數。③原始問題和對偶問題的約束不等式的符號方向相反。④原始問題約束不等式係數矩陣轉置後即為對偶問題的約束不等式的係數矩陣。⑤原始問題的約束方程數對應於對偶問題的變量數,而原始問題的變量數對應於對偶問題的約束方程數。⑥對偶問題的對偶問題是原始問題,這一性質被稱為原始和對偶問題的對稱性。
[1]
對偶理論基本定理
原始問題和對偶問題的標準形式如下:
設原始問題為:
min z=cx
s.t. Ax <= b
x>= 0
則對偶問題為:
max w=yb
s.t. yA >= c
y>=0
式中max表示求極大值,min表示求極小值,s.t.表示“約束條件為”;z為原始問題的目標函數,w為對偶問題的目標函數;x為原始問題的決策變量列向量(n×1),y為對偶問題的決策變量行向量(1×m);A為原始問題的係數矩陣(m×n),b為原始問題的右端常數列向量(m×1),c為原始問題的目標函數係數行向量(1×n)。在原始問題與對偶問題之間存在着一系列深刻的關係,現已得到嚴格數學證明的有如下一些定理。
[2]
對偶理論弱對偶定理
對偶理論強對偶定理
對偶理論最優準則定理
對偶理論互補鬆弛定理
對偶理論鬆弛定理
若上述原始問題和對偶問題分別有可行解x0和y0,且u0和v0分別為它們的鬆弛變量,則當且僅當v0x0=0 和u0y0=0時, x0和y0分別為它們的最優解。v0x0=0和u0y0=0這兩個等式稱為互補鬆弛條件。
對稱對偶線性規劃 具有對稱形式的線性規劃的特點是:
②全部變量均為非負。
列出對稱對偶線性規劃的步驟是:
①規定非負的對偶變量,變量數等於原始問題的約束方程數。
②把原始問題的目標函數係數作為對偶問題約束不等式的右端常數。
③把原始問題約束不等式的右端常數作為對偶問題的目標函數係數。
⑤把原始問題約束條件中的不等號反向作為對偶問題約束條件的不等號。
⑥將原始問題目標函數取極大化改成對偶問題目標函數取極小化。
非對稱對偶線性規劃 有時線性規劃並不以對稱方式出現,如約束條件並不都是同向不等式,變量可以是非正的或沒有符號約束。
列寫非對稱對偶線性規劃可參照原始-對偶表按下列步驟進行:
①規定對偶變量,變量個數等於原始問題約束不等式數。
②把原始問題的目標函數係數作為對偶問題約束不等式的右端常數。
③把原始問題約束不等式的右端常數作為對偶問題的目標函數係數。
④把原始問題的係數矩陣轉置後作為對偶問題的係數矩陣。
⑤根據原始問題的約束不等式情況,確定對偶變量的符號約束。
⑥根據原始問題決策變量的符號約束,確定對偶問題約束不等式的符號方向。