每個(gè)線性規(guī)劃問(wèn)題都有一個(gè)與之對(duì)應(yīng)的對(duì)偶問(wèn)題。對(duì)偶問(wèn)題是以原問(wèn)題的約束條件和目標(biāo)函數(shù)為基礎(chǔ)構(gòu)造而來(lái)的。對(duì)聯(lián)問(wèn)題也是一個(gè)線性規(guī)劃問(wèn)題，因此可以采用單純形法求解。對(duì)偶問(wèn)題的最優(yōu)解也可以通過(guò)原問(wèn)題的最優(yōu)解得到，反之亦然。而且，在某些情況下，利用對(duì)偶理論求解線性規(guī)劃問(wèn)題更為簡(jiǎn)單，而且有助于深入了解待求問(wèn)題的本質(zhì)。
概述
對(duì)偶線性規(guī)劃的經(jīng)濟(jì)背景是：若原問(wèn)題是利用有限資源安排最優(yōu)生產(chǎn)方案，以獲得最大總產(chǎn)值的線性規(guī)劃問(wèn)題，則它的對(duì)偶問(wèn)題就是在相同資源的條件下，正確估計(jì)資源的使用價(jià)值，以達(dá)到支付最少費(fèi)用的線性規(guī)劃問(wèn)題。簡(jiǎn)言之，若原問(wèn)題為求解資源的最優(yōu)配置問(wèn)題，則對(duì)偶問(wèn)題就是求解估價(jià)資源的使用價(jià)值問(wèn)題。
構(gòu)建方法
原問(wèn)題中的每個(gè)變量都變?yōu)閷?duì)偶問(wèn)題中的一個(gè)限制條件；原問(wèn)題中的每個(gè)限制條件都變?yōu)閷?duì)偶問(wèn)題中的一個(gè)變量；原問(wèn)題若是求目標(biāo)函數(shù)的最大值，則對(duì)偶問(wèn)題是求最小值，反之亦然。
對(duì)偶定理
對(duì)于互相對(duì)偶的最大化問(wèn)題甲與最小化問(wèn)題乙，我們有如下兩個(gè)定理。
弱對(duì)偶定理
若{\displaystyle x\in \mathbb {R} ^{n}}、{\displaystyle y\in \mathbb {R} ^{m}}分別滿足問(wèn)題甲、乙的限制條件，則：{\displaystyle c^{T}x\leq b^{T}y}。
強(qiáng)對(duì)偶定理
若{\displaystyle x^{*}\in \mathbb {R} ^{n}}、{\displaystyle y^{*}\in \mathbb {R} ^{m}}分別滿足問(wèn)題甲、乙的限制條件，則：{\displaystyle x^{*},y^{*}}分別為問(wèn)題甲、乙的最優(yōu)解（即{\displaystyle x^{*}=\operatorname {argmax} _{x}c^{T}x}，{\displaystyle y^{*}=\operatorname {argmin} _{y}b^{T}y}），當(dāng)且僅當(dāng){\displaystyle c^{T}x^{*}=b^{T}y^{*}}。換言之，若甲、乙均有解，則{\displaystyle \max _{x}c^{T}x=\min _{y}b^{T}y}。
無(wú)限值解與無(wú)解問(wèn)題
若原問(wèn)題有無(wú)限值解，則其對(duì)聯(lián)問(wèn)題無(wú)解；
若對(duì)偶問(wèn)題有無(wú)限值解，則其原問(wèn)題無(wú)解。
但是，原問(wèn)題和對(duì)偶問(wèn)題可同時(shí)無(wú)解。
基本性質(zhì)
原始線性規(guī)劃與對(duì)偶線性規(guī)劃問(wèn)題不僅在數(shù)學(xué)模型的形式上存在著相互對(duì)應(yīng)的關(guān)系，而且它們的目標(biāo)函數(shù)、可行解及最優(yōu)解之間也存在著確定的聯(lián)系。
設(shè)有一對(duì)線性規(guī)劃問(wèn)題為：
（1）原始問(wèn)題
求
滿足
（2）對(duì)聯(lián)問(wèn)題
求
滿足
定理：互為對(duì)偶的線性規(guī)劃（1）和（2）有最優(yōu)解的充分必要條件是它們同時(shí)有可行解。
證明：必要性是顯然的，下面來(lái)證明充分性。
設(shè) 是（1）的可行解, 是 (2) 的可行解。
則有
若 是 (1) 的任意一個(gè)可行解, 則有
成立。用 左乘 式子，得
用右乘不等式 的兩邊，得
由 和 兩個(gè)式子，得
上式說(shuō)明原始問(wèn)題 (1) 的目標(biāo)函數(shù) 在可行解集合上有上界，所以 (1) 有最優(yōu)解。
設(shè) 是 (2) 的任意一個(gè)可行解，用同樣的推理方法可得
上式表示對(duì)偶問(wèn)題（2）的目標(biāo)函數(shù) 在可行解集合上有下界，所以（2）有最優(yōu)解。證明完畢。
參考資料 >