線性規(guī)劃對偶理論

1、1運(yùn)籌學(xué)Operations Research2線性規(guī)劃對偶理論p線性規(guī)劃對偶理論概述p線性規(guī)劃對偶問題提出p線性規(guī)劃對偶問題規(guī)范形式p線性規(guī)劃對偶問題一般形式p線性規(guī)劃對偶問題基本性質(zhì)p線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋3線性規(guī)劃對偶理論概述 p線性規(guī)劃對偶理論自1947年提出以來，已經(jīng)有了很大發(fā)展，已成為線性規(guī)劃的必不可少的重要基礎(chǔ)理論。p對偶理論是線性規(guī)劃中的一個(gè)最重要的最有趣的概念。支持對偶理論的基本思想是，每一個(gè)線性規(guī)劃問題都存在一個(gè)與其對偶的問題。在求出一個(gè)問題解的時(shí)候，也同時(shí)給出了另一問題的解。p線性規(guī)劃對偶問題以及對偶理論中對偶定理的運(yùn)用是線性規(guī)劃中主要考點(diǎn)。4對偶問題的提出 5對偶問

2、題的提出6對偶問題的提出pLP1與與LP2 兩個(gè)線性規(guī)劃問題的兩個(gè)線性規(guī)劃問題的表現(xiàn)形式和系數(shù)之間存在許多對表現(xiàn)形式和系數(shù)之間存在許多對應(yīng)關(guān)系。應(yīng)關(guān)系。 并且并且p我們稱前者為原問題，后者是前我們稱前者為原問題，后者是前者的對偶問題。者的對偶問題。wzminmax7規(guī)范形式下對偶關(guān)系的一般形式 8規(guī)范形式下對偶關(guān)系的一般形式 9規(guī)范形式原問題與對偶問題變換規(guī)則 10線性規(guī)劃問題對偶問題舉例 例例3.1 寫出下列線性規(guī)劃問題的對偶問題寫出下列線性規(guī)劃問題的對偶問題11非規(guī)范形式的對偶關(guān)系 12如何直接寫出非對稱形式的對偶問題13如何直接寫出非對稱形式的對偶問題14原問題（或?qū)ε紗栴}）原問題（或?qū)?/p>

3、偶問題）對偶問題（或原問題）對偶問題（或原問題） 目標(biāo)函數(shù)目標(biāo)函數(shù)max目標(biāo)函數(shù)系數(shù)（資源限量）目標(biāo)函數(shù)系數(shù)（資源限量）約束條件系數(shù)矩陣約束條件系數(shù)矩陣A(AT) 目標(biāo)函數(shù)目標(biāo)函數(shù)min資源限量（目標(biāo)函數(shù)系數(shù)）資源限量（目標(biāo)函數(shù)系數(shù)）約束條件系數(shù)矩陣約束條件系數(shù)矩陣AT(A)變變量量n個(gè)變量個(gè)變量第第j個(gè)變量個(gè)變量0第第j 個(gè)變量個(gè)變量0第第j個(gè)變量無約束個(gè)變量無約束約約束束 n個(gè)約束個(gè)約束第第j個(gè)約束為個(gè)約束為第第j個(gè)約束為個(gè)約束為第第j個(gè)約束為個(gè)約束為=約約束束m個(gè)約束個(gè)約束第第i個(gè)約束個(gè)約束第第i個(gè)約束個(gè)約束第第i個(gè)約束為個(gè)約束為=變變量量m個(gè)變量個(gè)變量第第i個(gè)變量個(gè)變量0第第i個(gè)變量個(gè)

4、變量0第第i個(gè)變量無約束個(gè)變量無約束 表表3-115如何直接寫出非對稱形式的對偶問題只要記住規(guī)范形式下的對偶關(guān)系以及上述規(guī)則，就可以準(zhǔn)確只要記住規(guī)范形式下的對偶關(guān)系以及上述規(guī)則，就可以準(zhǔn)確無誤并很快寫出其對偶問題。無誤并很快寫出其對偶問題。 16【例【例3.3】寫出下列線性規(guī)劃的對偶問題】寫出下列線性規(guī)劃的對偶問題 0, 0,1482105618827945min43213214243214321xxxxxxxxxxxxxxxxxZ無約束【解】目標(biāo)函數(shù)求最小值，應(yīng)將【解】目標(biāo)函數(shù)求最小值，應(yīng)將表表31的右邊看作原問題，左邊的右邊看作原問題，左邊是對偶問題，原問題有是對偶問題，原問題有3個(gè)約束個(gè)

5、約束4個(gè)變量，則對偶問題有個(gè)變量，則對偶問題有3 個(gè)變量個(gè)變量4個(gè)約束，對偶問題為：個(gè)約束，對偶問題為：123131231312max1810147226885wyyyyyyyyyyyy=1549y10， y20，y3無約束17線性規(guī)劃對偶問題的基本性質(zhì) 下面下面介紹介紹對偶基本性質(zhì)時(shí)，一般假定是如下規(guī)范對偶關(guān)系。對偶基本性質(zhì)時(shí)，一般假定是如下規(guī)范對偶關(guān)系。0maxXbAXCXZ對偶問題是（記為對偶問題是（記為DP）：）：0minYCYAYbw這里這里A是是mn矩陣矩陣X是是n1列向量，列向量，Y是是1m行向量。假設(shè)行向量。假設(shè)Xs與與Ys分別是（分別是（LP）與（）與（DP）的松馳變量。）的

6、松馳變量。設(shè)原問題是（記為設(shè)原問題是（記為LP）：）： 18【性質(zhì)【性質(zhì)1】 對稱性對稱性 對偶問題的對偶是原問題。對偶問題的對偶是原問題。 【證】設(shè)原問題是【證】設(shè)原問題是0,maxXbAXCXZ0,minYCYAYbw它與下列線性規(guī)劃問題是等價(jià)的：它與下列線性規(guī)劃問題是等價(jià)的：0,)max(YCYAYbw再寫出它的對偶問題。再寫出它的對偶問題。0,)min(XbAXCXw它與下列線性規(guī)劃問題是等價(jià)的它與下列線性規(guī)劃問題是等價(jià)的0,maxXbAXCXZ即是原問題。即是原問題。 可知，它的對偶問題是可知，它的對偶問題是19 【證】因?yàn)椤咀C】因?yàn)閄、Y是可行解，故有是可行解，故有AXb, X0及

7、及YAC，Y0,將不等式將不等式 AXb【性質(zhì)【性質(zhì)2】 弱對偶性弱對偶性 設(shè)設(shè)X、Y分別為分別為LP(max)與與DP(min)的可行解，則的可行解，則 bYCX00兩邊左乘兩邊左乘Y，得，得Y0AXY0b再將不等式再將不等式Y(jié)AC兩邊右乘兩邊右乘X，得，得C XYAX故故 C XYAXYb這一性質(zhì)說明了兩個(gè)線性規(guī)劃互為對偶時(shí)，求最大值的線性這一性質(zhì)說明了兩個(gè)線性規(guī)劃互為對偶時(shí)，求最大值的線性規(guī)劃的任意目標(biāo)值都不會大于求最小值的線性規(guī)劃的任一目規(guī)劃的任意目標(biāo)值都不會大于求最小值的線性規(guī)劃的任一目標(biāo)值，標(biāo)值，不能理解為原問題的目標(biāo)值不超過對偶問題的目標(biāo)值不能理解為原問題的目標(biāo)值不超過對偶問題的

8、目標(biāo)值。20【性質(zhì)【性質(zhì)3】 無界性無界性 若原問題（對偶問題）有無界若原問題（對偶問題）有無界解，則其對偶問題（原問題）無可行解。解，則其對偶問題（原問題）無可行解。 可理解為：在互為對偶的兩個(gè)問題中，若一個(gè)問題可行且具有無可理解為：在互為對偶的兩個(gè)問題中，若一個(gè)問題可行且具有無界解，則另一個(gè)問題無可行解界解，則另一個(gè)問題無可行解證：假定原問題有無界解，對偶問題有可行解證：假定原問題有無界解，對偶問題有可行解 Y， Yb 。原問題有無界解，即存在。原問題有無界解，即存在C X ，根據(jù)若，根據(jù)若對偶性有，對偶性有， Yb C X ，顯然矛盾，故命題成立。，顯然矛盾，故命題成立。注意注意：（：（

9、1）這個(gè)定理的逆定理不成立，即若一個(gè)問題無可這個(gè)定理的逆定理不成立，即若一個(gè)問題無可行解，另一問題不一定有無界解，也可能無可行解；行解，另一問題不一定有無界解，也可能無可行解； （2）若原問題可行且另一個(gè)問題不可行，則原問題具）若原問題可行且另一個(gè)問題不可行，則原問題具有無界解有無界解21例如：例如：0,22212min21212121xxxxxxxxz無可行解，而對偶問題無可行解，而對偶問題0,221122max21212121yyyyyyyyw有可行解，由性質(zhì)（有可行解，由性質(zhì)（3）知必有無界解。）知必有無界解。22【性質(zhì)【性質(zhì)4】最優(yōu)性定理】最優(yōu)性定理 設(shè)設(shè)X0與與Y0分別是（分別是（L

10、P）與（）與（DP）的可）的可行解，則當(dāng)行解，則當(dāng)C X0= Y0b 時(shí)，時(shí)，X0、Y0是（是（LP）與（）與（DP）的最優(yōu)解）的最優(yōu)解【證】若【證】若C X0= Y0b ，由性質(zhì)，由性質(zhì)2，對偶問題的所有可行解，對偶問題的所有可行解Y都都存在存在 Y b CX。因?yàn)?。因?yàn)镃 X0= Y0b ，所以，所以Y b Y0b ，可見，可見Y0是使目標(biāo)函數(shù)取值最小的可行解，因而是使目標(biāo)函數(shù)取值最小的可行解，因而Y0是最優(yōu)解。同理可是最優(yōu)解。同理可證，證， X0是最優(yōu)解是最優(yōu)解23【性質(zhì)【性質(zhì)5】 弱對偶性若互為對偶的兩個(gè)問題其中一個(gè)有弱對偶性若互為對偶的兩個(gè)問題其中一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且

11、最優(yōu)值相同。最優(yōu)解，則另一個(gè)也有最優(yōu)解，且最優(yōu)值相同?！咀C】設(shè)（【證】設(shè)（LP）有最優(yōu)解）有最優(yōu)解X0,那么對于最優(yōu)基那么對于最優(yōu)基B必有必有C-CBB-1A0與與CBB-10，即有，即有YAC與與Y0，這里，這里Y= CBB-1 ，從而，從而Y是是可行解，對目標(biāo)函數(shù)有可行解，對目標(biāo)函數(shù)有bYbBCXCCXBBB010由性質(zhì)由性質(zhì)4知知Y是最優(yōu)解。是最優(yōu)解。由性質(zhì)由性質(zhì) 5 還可推出還可推出另一結(jié)論另一結(jié)論：若（：若（LP）與（）與（DP）都有可行解，）都有可行解，則兩者都有最優(yōu)解，若一個(gè)問題無最優(yōu)解，則另一問題也無最優(yōu)則兩者都有最優(yōu)解，若一個(gè)問題無最優(yōu)解，則另一問題也無最優(yōu)解。解。24【例【

12、例3.4】 證明下列線性規(guī)劃無最優(yōu)解：證明下列線性規(guī)劃無最優(yōu)解：3 , 2 , 1, 0324min32131321jxxxxxxxxxZj【證】容易看出【證】容易看出X=（4，0，0）是一可行解，故問題可行。對）是一可行解，故問題可行。對偶問題偶問題0, 0121134max212122121yyyyyyyyyw將三個(gè)約束的兩端分別相加得將三個(gè)約束的兩端分別相加得而第二個(gè)約束有而第二個(gè)約束有y21，矛盾，故對偶問，矛盾，故對偶問題無可行解，題無可行解，因而原問題具有無界因而原問題具有無界解，即無最優(yōu)解。解，即無最優(yōu)解。 212y25【性質(zhì)【性質(zhì)6】互補(bǔ)松弛定理】互補(bǔ)松弛定理 設(shè)設(shè)X0、Y0分

13、別為（分別為（LP）與（）與（DP）的可）的可行解，行解，XS和和YS是它的松弛變量的可行解，則是它的松弛變量的可行解，則X0和和Y0是最優(yōu)解當(dāng)且是最優(yōu)解當(dāng)且僅當(dāng)僅當(dāng)YSX0=0和和Y0XS=0【證】設(shè)【證】設(shè)X和和Y是最優(yōu)解是最優(yōu)解,由性質(zhì)由性質(zhì)4 ，C X0= Y0b，由于，由于XS和和YS是松弛變量，則有是松弛變量，則有A X0XSbY0AYS=C將第一式左乘將第一式左乘Y0，第二式右乘，第二式右乘X0得得Y0A X0Y0XSY0bY0A X0YS X0=C X026顯然有顯然有 Y0XS=YS X0又因?yàn)橛忠驗(yàn)閅、Xs、Ys、X0，所以有，所以有YXS=0和和YS X=0成立。成立。反

14、之，反之， 當(dāng)當(dāng)YXS=0和和YS X=0時(shí)，有時(shí)，有YA XYbYA X=C X顯然有顯然有Y0b=C X,由性質(zhì)由性質(zhì)4知知Y與與X是（是（LP）與（）與（DP）的最）的最優(yōu)解。證畢。優(yōu)解。證畢。27性質(zhì)性質(zhì)6告訴我們已知一個(gè)問題的最優(yōu)解時(shí)求另一個(gè)問題的最優(yōu)解告訴我們已知一個(gè)問題的最優(yōu)解時(shí)求另一個(gè)問題的最優(yōu)解的方法，即已知的方法，即已知Y*求求X*或已知或已知X*求求Y*。Y * XS=0和和YS X * =0兩式稱為互補(bǔ)松弛條件。將互補(bǔ)松弛條件寫成下式兩式稱為互補(bǔ)松弛條件。將互補(bǔ)松弛條件寫成下式*1*100ijmiSinSjjy xy x由于變量都非負(fù)，要使求和式等于零，則必定每一分量為

15、零，由于變量都非負(fù)，要使求和式等于零，則必定每一分量為零，因而有下列關(guān)系：因而有下列關(guān)系：28(1)當(dāng)yi*0時(shí)， ,反之當(dāng) 時(shí)yi*=0；0iSx0iSx*(2)00,00jjSjjSyxxy時(shí)反之當(dāng)時(shí)利用上述關(guān)系，建立對偶問題（或原問題）的約束線性方程組，利用上述關(guān)系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。方程組的解即為最優(yōu)解。性質(zhì)性質(zhì)6的結(jié)論和證明都是假定（的結(jié)論和證明都是假定（P）與（）與（D）為對稱形式，事實(shí)）為對稱形式，事實(shí)上對于非對稱形式，性質(zhì)上對于非對稱形式，性質(zhì)6的結(jié)論仍然有效。的結(jié)論仍然有效?！纠纠?.5】 已知線性規(guī)劃已知線性規(guī)劃3 , 2 ,

16、 1, 0162210243max321321321jxxxxxxxxxxzj的最優(yōu)解是的最優(yōu)解是 求對偶問題的最優(yōu)解。求對偶問題的最優(yōu)解。TX)0 , 2 , 6(29【解】對偶問題是【解】對偶問題是0,1422321610min2121212121yyyyyyyyyyw因?yàn)橐驗(yàn)閄10，X20，所以對偶問題的第一、，所以對偶問題的第一、二個(gè)約束的松弛變量等于零，即二個(gè)約束的松弛變量等于零，即422322121yyyy解此線性方程組得解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為從而對偶問題的最優(yōu)解為Y=（1，1），最優(yōu)值），最優(yōu)值w=26。30【例【例3.6】 已知線性規(guī)劃已知線

17、性規(guī)劃 無約束321321321321, 0, 06422minxxxxxxxxxxxxz的對偶問題的最優(yōu)解為的對偶問題的最優(yōu)解為Y=（0，2），求原問題的最），求原問題的最優(yōu)解。優(yōu)解?！窘狻繉ε紗栴}是【解】對偶問題是021264max2121212121yyyyyyyyyyw無約，31解方程組得：解方程組得：x 1=5,x 3=1, 所以原問題的最優(yōu)解為所以原問題的最優(yōu)解為X=（5，0，1），最優(yōu)值），最優(yōu)值Z=12。643131xxxx因?yàn)橐驗(yàn)閥20，所以原問題第二個(gè)松弛變量，所以原問題第二個(gè)松弛變量 =0，由，由y1=0、y2=-2知，松弛變量知，松弛變量 ，故，故x2=0，則原問題的約

18、束條件為線性方程組：，則原問題的約束條件為線性方程組： 0, 1, 0321SSSyyy2Sx323334353637【性質(zhì)【性質(zhì)6】互補(bǔ)對偶性】互補(bǔ)對偶性LP(max)的檢驗(yàn)數(shù)的相反的檢驗(yàn)數(shù)的相反數(shù)對應(yīng)于數(shù)對應(yīng)于DP(min)的一組基本解的一組基本解. 其中第其中第j個(gè)決策變量個(gè)決策變量xj的檢驗(yàn)數(shù)的相反數(shù)對應(yīng)于（的檢驗(yàn)數(shù)的相反數(shù)對應(yīng)于（DP）中第中第j個(gè)松弛變量個(gè)松弛變量 的解，第的解，第i個(gè)松弛變量個(gè)松弛變量 的檢驗(yàn)數(shù)的相反數(shù)對應(yīng)于第的檢驗(yàn)數(shù)的相反數(shù)對應(yīng)于第i個(gè)對偶變量個(gè)對偶變量yi的解。反的解。反之，（之，（DP）的檢驗(yàn)數(shù)（注意：不乘負(fù)號）對應(yīng)于）的檢驗(yàn)數(shù)（注意：不乘負(fù)號）對應(yīng)于（LP）的一組基本解。）的一組基本解。證明略。證明略。jSyiSx38【例【例3.9】 線性規(guī)劃線性規(guī)劃0,442226max32131321321xxxxxxxxxxxz（1）用單純形法求最優(yōu)解；）用單純形法求最優(yōu)解；（2）寫出每步迭代對應(yīng)對偶問題的基本解；）寫出每步迭代對應(yīng)對偶問題的基本解；（3）從最優(yōu)表中寫出對偶問題的最優(yōu)解；）從最優(yōu)