【正文】 （或原問題）目標(biāo)函數(shù)最小化個變量個約束約束條件限定向量（右邊項）目標(biāo)函數(shù)價值向量≥變量 ≤≥無限制約束 ≤＝目標(biāo)函數(shù)最大化（ ）個約束個變量目標(biāo)函數(shù)價值向量（系數(shù)）約束條件限定向量≤約束 ≥≥＝變量 ≤無限制對偶線性規(guī)劃 練習(xí) ： 試求下列線性規(guī)劃問題的對偶問題 答案： 3 2 1 3 4 2 max x x x Z ? ? . 10 3 2 1 ? ? x x x 5 3 4 3 2 1 ? ? x x x 8 5 2 3 3 2 1 ? ? x x x 0 1 ? x ， 0 2 ? x 3 2 1 8 5 10 min y y y S ? ? . 2 3 3 2 1 ? ? y y y 4 2 4 3 2 1 ? ? ? y y y 3 5 3 3 2 1 ? y y y 0 1 ? y ， 0 3 ? y 原問題原問題 （或?qū)ε紗栴}） 對偶問題對偶問題 （或原問題）目標(biāo)函數(shù)最大化 ( m ax Z )n 個變量m 個約束約束條件限定向量（右邊項）目標(biāo)函數(shù)價值向量（系數(shù)）≥ 0變量 ≤ 0 ≥無限制約束 ≤＝目標(biāo)函數(shù)最小化（ m i nS ）n 個約束m 個變量目標(biāo)函數(shù)價值向量（系數(shù)）約束條件限定向量（右邊項）≥約束 ≤≤ 0＝變量 ≥ 0 無限制原問題原問題 （或?qū)ε紗栴}） 對偶問題對偶問題 （或原問題）目標(biāo)函數(shù)最大化個變量個約束約束條件限定向量（右邊項）目標(biāo)函數(shù)價值向量（系數(shù)）≥變量 ≤≥無限制約束 ≤＝目標(biāo)函數(shù)最小化（ ）個約束個變量目標(biāo)函數(shù)價值向量（系數(shù)）約束條件限定向量（右邊項）≥約束 ≤≤＝變量 ≥無限制對偶線性規(guī)劃 變量決定約束是同號 ,約束決定變量是反號 練習(xí) ： 試求下列線性規(guī)劃問題的對偶問題 ????????????????????無約束432143242143214321,0,0642253532xxxxxxxxxxxxxxxxxxf m i n maxZ=5y1+4y2+6y3 y1+2y2≥ 2 y1 +2y2 +y3 ≤ 3 3y1 +y3 ≤ 5 y1 y2 +y3＝ 1 y1 ≥ 0, y2 , y3 ≤ 0 答案： 原問題原問題 （或?qū)ε紗栴}） 對偶問題對偶問題 （或原問題）目標(biāo)函數(shù)最小化 ( m i nS )n 個變量m 個約束約束條件限定向量（右邊項）目標(biāo)函數(shù)價值向量≥ 0變量 ≤ 0 ≥無限制約束 ≤＝目標(biāo)函數(shù)最大化（ m ax Z ）n 個約束m 個變量目標(biāo)函數(shù)價值向量（系數(shù)）約束條件限定向量≤約束 ≥≥ 0＝變量 ≤ 0無限制原問題原問題 （或?qū)ε紗栴}） 對偶問題對偶問題 （或原問題）目標(biāo)函數(shù)最小化個變量個約束約束條件限定向量（右邊項）目標(biāo)函數(shù)價值向量≥變量 ≤≥無限制約束 ≤＝目標(biāo)函數(shù)最大化（ ）個約束個變量目標(biāo)函數(shù)價值向量（系數(shù)）約束條件限定向量≤約束 ≥≥＝變量 ≤無限制對偶線性規(guī)劃 變量決定約束是反號 ,約束決定變量是同號 原問題 目標(biāo)函數(shù) max ?原問題 (minS) 與對偶之關(guān)系符號小結(jié) 同號 變量 對偶線性規(guī)劃 約束 反號 約束 變量 對偶問題 目標(biāo)函數(shù) min 21 線性規(guī)劃的對偶理論包括以下幾個基本定理。 線性規(guī)劃的對偶理論 定理 2 （弱對偶定理） 即對偶問題的對偶是原問題。 反之，若原（對偶）問題 有可行解 ,對偶（原）問題 無可行解 ，則原（對偶）問題一定 無界 ； 定理 4 （可行解是最優(yōu)解的性質(zhì)） 定理 5 （強(qiáng)對偶定理） 設(shè) X*是原問題的可行解， Y*是對偶問題的可行解，當(dāng)CX*=Y*b時， X*與 Y*是最優(yōu)解 。 對偶線性規(guī)劃 對 偶 問 題 有最優(yōu)解 無界 無可行解 原 有最優(yōu)解 √ 問 無 界 √ 題 無可行解 可能 可能 24 例 4 已知線性規(guī)劃問題 Max z=x1 + x2 . –x1 + x2 + x3 ≤ 2 – 2x1 + x2 – x3 ≤ 1 xi ≥ 0 (i=1,2 ,3) Min w = 2y1 +y2 . – y1 – 2y2 ≥ 1 ① y1 + y2 ≥ 1 ② y1 –y2 ≥ 0 ③ y1,y2 ≥ 0 ?應(yīng)用如上關(guān)系求解線性規(guī)劃問題 試用對偶理論證明上述規(guī)劃問題無最優(yōu)解。 [解 ] 該問題存在可行解，如 X=(0， 0， 0)； 其對偶問題為： 對偶問題無可行解 對偶線性規(guī)劃 25 定理 6（互補(bǔ)松弛定理） 在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零 ，則該約束條件取 嚴(yán)格等式 ；反之如果 約束條件取嚴(yán)格不等式 ，則其對應(yīng)的 對偶變量一定為零 。 當(dāng)線性規(guī)劃問題達(dá)到最優(yōu)時，我們不僅同時得到了原問題和對偶問題的最優(yōu)解，而且也還得到了變量和約束之間的一種對應(yīng)關(guān)系。 對偶線性規(guī)劃 27 線性規(guī)劃達(dá)到 最優(yōu) 時的關(guān)系： （嚴(yán)格等式 :松弛變量為零），該約束對應(yīng)的對偶變量應(yīng)大于或等于零； （ 嚴(yán)格不等式 :松弛變量大于零），則對應(yīng)的對偶變量必為零； 束 (嚴(yán)格等式 )； ，該變量對應(yīng)的對偶約束可能是緊約束 (嚴(yán)格等式 )，也可能是松約束 (嚴(yán)格不等式 )。 x2 = 0 x3 = 0 x4 = 0 等號 又因 y1,y2 ＞ 0，故原問題的兩個約束必為緊約束，即 x1+3 x5= 4 2x1+ x5 = 3 解得： x1 = x5 = 1。 線性規(guī)劃問題的對偶問題為： =8y1+6y2+6y3+9y4 . y1+2y2 +y4 ≥ 2 3y1+y2 + y3 +y4 ≥ 4 y3 +y4 ≥ 1 y1 +y3 ≥ 1 yj≥0（ j=1,2,3,4） 對偶線性規(guī)劃 30 ④ 為嚴(yán)格不等式，由互補(bǔ)松弛定知，必有 y4 = 0； Max Z=2x1+4x2+x3+x4 . x1+3x2 +x4≤8 2x1+x2 ≤6 x2 + x3 +x4≤6 x1 + x2 +x3 ≤9 xj≥0（ j=1,2,3,4） ① 8=8 ② 6=6 ③ 6=6 ④ 89 解之，有： y1=4/5, y2=3/5, y3=1， y4 = 0 答案：因為原問題的最優(yōu)解為 :X*=(2,2,4,0)T ： 又因 x1, x2 , x3＞ 0，故對偶問題的前三個約束必為緊約束 線性規(guī)劃問題的對偶問題為： MinS=8y1+6y2+6y3+9y4 . y1+2y2 +y4 ≥ 2 3y1+y2 + y3 +y4 ≥ 4 y3 +y4 ≥ 1 y1 +y3 ≥ 1 yj≥0（ j=1,2,3,4） y1+2y2 = 2 3y1+y2 + y3 = 4 y3 = 1 等號 對偶線性規(guī)劃 maxZ=16=minS 得對偶問題的最優(yōu)解 Y*=(4/5,3/5,1,0) minS=16 31 【 練習(xí) 】 已知線性規(guī)劃問題 ?????????????????????????4321214321432314321,2 6332 2 6863 m i nxxxxxxxxxxxxxxxxxxxz（ 1）寫出對偶問題； （ 2）已知原問題的最優(yōu)解為 X*=（ 2， 0， 1， 1） T，求對偶問題的最優(yōu)解。 注：證明過程參見教材 60頁性質(zhì) 6證明 檢驗數(shù)行的 (cjzj)值是其對偶問題的一個 基本解 yi ； 定理 7 對偶線性規(guī)劃 33 ?用單純形法同時求解 原問題 和 對偶問題 原問題是： maxZ=2x1 +x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 原問題的標(biāo)準(zhǔn)型是： maxZ=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi ≥0 對偶線性規(guī)劃 34 Cj 比 值 CB XB b 檢驗數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15 0 5 1 0 0 24 6 2 0 1 0 5 1 1 0 0 1 x3 x4 x5 0 0 0 0 2 1 0 0 0 maxZ=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi ≥0 24/6=4 5/1=5 原問題變量 原問題松馳變量 對偶問題剩余變量 y y5 對偶問題變量 y y2 、 y3 得原問題可行解 :X=(0,0,15,24,5)T 對偶問題解 :Y*=(0,0,0,2,1)T 檢驗數(shù)行的 － (cjzj)值是其對偶問題的一個 基本解 yi ； 對偶線性規(guī)劃 35 檢驗數(shù) ?j 15 0 5 1 0 0 4 1 1/3 0 1/6 0 1 0 2/3 0 1/6 1 x3 x1 x5 0 2 0 8 0 1/3 0 1/3 0 3 12 得原問題可行解 :X=(4,0,15,0,1)T，此時 Z=8 同時得對偶問題基礎(chǔ)解 :Y*=(0,1/3,0, 0,