【正文】 1 2 31 2 31 2 31 2 31 2 322212:10 , , 0MinW u u uu u uu u uSTu u uu u u? ? ?? ? ???? ? ???? ? ? ??? ??? 無 約 束1 2 32M a x Z x x x? ? ?:ST???????1 2 3x x x??1 2 3x x x??1 2 32 x x x??2121 0x ? 20x ?3x 無 約 束???13 原問題 對(duì)偶問題 目標(biāo)函數(shù) Max z Min w 變量 n個(gè) 約束條件 n個(gè) ≥ ≤ = ≤0 ≥0 無約束 約束條件 m個(gè) ≥ ≤ = 變量 m個(gè) ≥0 ≤0 無約束 約束條件右端項(xiàng) 目標(biāo)函數(shù)變量的系數(shù) 目標(biāo)函數(shù)變量的系數(shù) 約束條件右端項(xiàng) 原問題 對(duì)偶問題 14 第二節(jié) LP問題的對(duì)偶理論 若 X(0),Y(0)分別為 (L),(D)的可行解，則有 CX(0)≤Y(0)b 定理 1(弱對(duì)偶定理 ): 極大化原問題目標(biāo)函數(shù)值總是不大于其對(duì)偶問題的目標(biāo)函數(shù)值。 對(duì)于 max ，約束為“ ?” ； 對(duì)于 min，約束為“ ?” 5 例 1 寫出下列 LP問題的對(duì)偶問題 對(duì)偶 Max Z =2x1+3x2 . x1+ 2x2≤8 4x1 ≤ 16 4x2≤ 12 x1 ,x2 ≥0 ???Min W =8y1+16y2+12y3 . y1+4y2 ≥2 2y1 +4y3 ≥3 y1 ,y2,y3 ≥0 ???6 （ 3）對(duì)偶問題的對(duì)偶是原問題 推導(dǎo)過程 變形 對(duì)偶 變 形 對(duì)偶 變 形 ()LMax Z=CX . AX≤b X≥0 ???()DMin W=Yb . YA≥C Y≥0 ???Max W ’= Yb . YA≤ C Y≥0 ???Min Z ’= (C)X . (A)X≥ (b) X≥0 ???()DDMax W ’= Y(b) . Y(A)≤ (C) Y≥0 ???7 121 2 31 2 31 2 31 2 3343 3 4 748:1, , 0Min W x xx x xx x xSTx x xx x x??? ? ???? ? ???? ? ??? ??1 2 31 2 31 2 31 2 31 2 3783 4 334: 4 0, , 0Max Z y y yy y yy y ySTy y yy y y? ? ?? ? ???? ? ? ???? ? ??? ??例 2 寫出下列 LP問題的對(duì)偶問題 解 : 上述 LP問題的 對(duì)偶問題為： 8 三、非對(duì)稱 LP問題的對(duì)偶問題 例 3 寫出下列 LP問題的對(duì)偶問題 解：用 x2= x2’, x3=x3’x3’’代入上述 LP問題，并將其化為第一類對(duì)稱形式 Max Z = x1+2x2+x3 x1+x2x3 ≤2 . x1 x2+x3 = 1 2x1+x2+x3 ≥2 x1≥0, x2≤0 ,x3無約束 ??? Max Z = x1－ 2x2’ +x3’ － x3’’ x1 － x2’ － x3’+x3’’ ≤ 2 x1+x2’+x3’ － x3’’ ≤ 1 . － x1 － x2’ － x3’+x3’’ ≤－ 1 － 2x1+x2’ － x3’+x3’’ ≤－ 2 x1, x2’, x3’, x3’’ ≥0 ?????x1 x2+x3 ≤ 1 x1 x2+x3 ≥ 1 x1 x2+x3 ≤ 1 x1 +x2x3 ≤ 1 2x1x2x3 ≤ 2 9 上述第一類對(duì)稱形式 LP問題的對(duì)偶問題為： 則上述問 題變?yōu)椋? Min W =2y1+y2 － y3－ 2y4 y1+y2 － y3－ 2y4 ≥ 1 － y1+y2 － y3 +y4 ≥2 . － y1+y2 － y3－ y4 ≥ 1 y1 － y2+y3 +y4 ≥1 y1, y2, y3, y4 ≥0 ???Min W =2u1+u2+2u3 u1+u2+2u3 ≥1 . u1 － u2+ u3 ≤2 － u1+u2+ u3 =1 u1≥0, u3≤0 ,u2無約束 ???令 u1= y1 u2=y2－ y3 u3=－ y4 Max Z = x1－ 2x2’ +x3’ － x3’’ x1 － x2’ － x3’+x3’’ ≤ 2 x1+x2’+x3’ － x3’’ ≤ 1 . x1 － x2’ － x3’+x3’’ ≤－ 1 － 2x1+x2’ － x3’+x3’’ ≤－ 2 x1, x2’, x3’, x3’’ ≥0 ?????y1+y2 y3 y4 ≤ 1 y1y2+y3 y4 ≤ 2 10 (D) Min W =2u1+u2+2u3 u1+u2+2u3 ≥1 . u1 u2+ u3 ≤2 u1+u2+ u3 =1 u1≥0, u3≤0 ,u2無約束 ???(L) Max Z = x1+2x2+x3 x1+x2x3 ≤2 . x1 x2+x3 = 1 2x1+x2+x3 ≥2 x1≥0, x2≤0 ,x3無約束 ???對(duì)偶關(guān)系： 一個(gè)問題第 i個(gè)變量的約束情況決定另一問題第 i個(gè)約束不等式的方向，反之亦然。Y≥0……(D) 又 Y(0)A≥C 用 X(0)(X(0)≥0)右乘上式，得 Y(0)AX(0) ≥CX(0) (2) 由（ 1），（ 2） 得： CX(0)≤Y(0)AX(0)≤Y(0)b 所以 CX(0)≤Y(0)b 16 推論 1(P119) 若對(duì)偶問題有無界解，則其原問題無可行解； 若對(duì)偶問題無可行解，則其原問題或有無界解或無可行解。 Y≥0……(D) 18 例 4 考慮下面一對(duì) LP問題 其對(duì)偶問題為： 由于 X(0) =(1,1,1,1)T, Y(0)=(1,1)T分別為(L),(D)的可行解， Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 ≤20 . 2x1+ x2+3x3+2x4 ≤20 x1,x2,x3,x4 ≥0 ??? Min W = 20y1+20y2 y1+2y2 ≥ 1 2y1+ y2 ≥ 2 . 2y1+3y2 ≥ 3 3y1+2y2 ≥ 4 y1,y2≥0 ???????Z(0)=10 W(0)=40 W≥10 推論 2 Z≤40 推論 3 故 Z≤40,W≥10. 19 例 121 2 31 2 31 2 3m ax221, , 0z x xx x xx x xx x x??? ? ? ?? ? ? ?? 試用對(duì)偶理論證明上述線性規(guī)劃問題無最優(yōu)解 證明：首先看到該問題存在可行解，如 X=(0,0,0) 上述問題的對(duì)偶問題為 1212121212m i n 22110,0 w y yyyyyyyyy??? ? ??????由第一約束條件知對(duì)偶問題無可行解，因原問題有可行解，由推論 1，原問題無最優(yōu)解。 同理，對(duì)于 (D)的任意可行解 Y， 由弱對(duì)偶定理 （推論 2） ， 有 Y b≥CX(0)，所以 Yb在可行域內(nèi)有下界，故 (D)有最優(yōu)解。 對(duì)偶問題的最優(yōu)解為 Y*=(3/2, 1/8, 0)T 運(yùn)用單純形法計(jì)算得原問題的最終表如下： 32 推論：對(duì)偶問題的最優(yōu)解對(duì)應(yīng)于原問題的最優(yōu)單純型表中松弛變量檢驗(yàn)數(shù)的相反數(shù)或剩余變量的檢驗(yàn)數(shù)。 39 1 0 0 1/4 0 0 0 2 1/2 1 0 1 1/2 1/8 0 4 4 2 2 x1 0 x5 3 x2 x1 x2 x3 x4 x5 CB XB b 2 3 0 0 0 cj 14 0 0 3/2 1/8 0 例 8 下面是一張 LP問題的最優(yōu)單純形表，其中 x3, x4, x5為松弛變量 則對(duì)偶問題的最優(yōu)解為 Y*=(, , 0)T 40 例 8 X* =(4, 2)T， Z* =14 Q(4, 2) Z=14 x1 x2 4x1=16 4x2=12 x1+2x2=8 4 4 0 8 3 Q(, ) Z= Q(4, ) Z= Q(4, 2) Z=14 Max Z =2x1+3x2 x1+ 2x2≤8 . 4x1 ≤ 16 4x2≤ 12 x1 ,x2 ≥0 ???8 X1* =(4, )T， Z1*= X2* =(, )T， Z2* = X3* =(4, 2)T， Z3* =14 41 資源的影子價(jià)格是針對(duì)具體生產(chǎn)或具體企業(yè)而言的： 1. 同一種資源在不同的生產(chǎn)條件下或不同的范圍內(nèi)可能有不同的影子價(jià)格； A 2. 產(chǎn)品的市場(chǎng)價(jià)格發(fā)生變化 ， 資源的影子價(jià)格也會(huì)發(fā)生變化； C 3. 資源的數(shù)量結(jié)構(gòu)不同 ， 資源的影子價(jià)格也不同 。 (2)若所有常數(shù)項(xiàng) bi≥0，則最優(yōu)解已經(jīng)達(dá)到，否則 bl=Min{bi|bi0}， 選取 bl所對(duì)應(yīng)的變量為出基變量； (3)計(jì)算 θk=Min{σj /alj |alj0}， 選取 θk所對(duì)應(yīng)的變量為進(jìn)基變量； (4)以 alk為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，轉(zhuǎn)第二步。 四、右端項(xiàng) b 的變化分析 —— 公式推導(dǎo) 56 cj 4 5 1 7 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 x7 0 x5 120 8 4 6 1 1 0 0 0 x6 30 1 3 2 2 0 1 0 0 x7 150 3 8 5 2 0 0 1 σ 4 5 1 7 0 0 0 例 2 下面是求解同一 LP問題的初始單純形表和最優(yōu)單純形表，求 b1,b2,b3的變化范圍，使原最優(yōu)基不變。 B1 63 （ 2） 工廠新增 24公斤原材料 A，則 /39。kj B j B k jc C B P c a?? ? ? ?? 39。,k k kB B Bc c c? ? ?kBckBx1 139。1 2 33