【正文】 = 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è)約束不等式的方向，反之亦然。X≥0……(L) min w=Yb。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ì)偶問題無可行解，則其原問題或有無界解或無可行解。 推論 3 Yb≥CX(0) CX ≤ Y(0)b max z=CX。 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)解。 證明： 由定理 1可知，對(duì)于 (L)的任意可行解 X，有 CX ≤ Y(0)b 由于 CX(0) =Y(0)b， CX ≤CX(0) ， 故 X(0)為 (L) 的最優(yōu)解； 同理， 由定理 1可知， 對(duì)于 (D)的任意可行解 Y，有Yb≥CX(0)， 由于 CX(0) =Y(0)b， Yb≥Y(0)b， Y(0)為 (D)的最優(yōu)解。 同理，對(duì)于 (D)的任意可行解 Y， 由弱對(duì)偶定理 （推論 2） ， 有 Y b≥CX(0)，所以 Yb在可行域內(nèi)有下界，故 (D)有最優(yōu)解。 YA≥C。 對(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ù)。 37 ****1 2 3 42 2 3 2 0 ( 1 )xxxx? ? ? ?* * * *1 2 3 42 3 2 2 0 ( 2 )x x x x? ? ? ?** . . .122 1 2 0 4 1 6 1yy? ? ? ? ?** . . .122 2 4 0 2 2 6 2yy? ? ? ? ?**342 3 2 0xx??**343 2 2 0xx??x1*=x2*=0. 解：由于 y1* 0, y2* 0,由互補(bǔ)松弛性知 解得 x3*= x4*=4. 所以 (L)的最優(yōu)解為 X*=(0,0,4,4)T 因?yàn)? 代入 (1),(2)得 由互補(bǔ)松弛性知， 38 若 X*,Y* 分別為 (L),(D)的最優(yōu)解，那么 CX*=Y*b。 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à)格也不同 。 cj CB XB b x1 x2 x3 x4 x5 x6 σj 0 x4 0 x5 0 x6 4 8 2 1 1 1 1 0 0 1 1 2 0 1 0 0 1 1 0 0 1 0 1 2 3 0 0 0 1 2 3 0 0 0 正則解若是可行解，則它是最優(yōu)解。 (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)第二步。 ，有時(shí)需要用對(duì)偶單純形法。 四、右端項(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)基不變。 ?????? XB* = B1 ( b +λ b’ ) = B1b +B1 λ λ = 1 + 3 1 λ 2 1 1 λ = 1+4λ ≥0 2 2λ ??????????????????????????????**( ) * ( )()( , )11128 3 182BBBZ C B b bC B b C B b???????????????? ???????當(dāng) λ ＝ 1時(shí)， Z*=10， 達(dá)到最大。 B1 63 （ 2） 工廠新增 24公斤原材料 A，則 /39。j j B jc C B P? ???1j j B jc c C B P?? ? ? ?jjc?? ? ?討論： (1)當(dāng) σj’≤0，即 △ cj ≤ σj 時(shí)，原最優(yōu)解不變； (2)當(dāng) σj’ 0，即 △ cj σj 時(shí)，原最優(yōu)解改變。kj B j B k jc C B P c a?? ? ? ?? 39。39。,k k kB B Bc c c? ? ?kBckBx1 139。 c j 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 2 1/2 1 3 x2 2 0 1 1/2 1/8 0 σj 0 0 3/2 1/8 0 五、價(jià)值系數(shù) C 的變化分析 —— 例題 70 當(dāng) 3≤Δc2≤1， 即 0≤c2≤4 時(shí)，原最優(yōu)解不變。1 2 339。 利用單純形法進(jìn)行迭代 74 例 9 c j 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 1 1 0 5 x3’ 2 0 0 1 3 x2 0 1 σj 0 0 5 x3’ 0 1 0 0 最優(yōu)生產(chǎn)計(jì)劃： 生產(chǎn)產(chǎn)品 I 1件 產(chǎn)品 II 產(chǎn)品 III 2件 總利潤(rùn)為：