【正文】 偶單純形法的舉例 第一類對稱形式 46 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 cj 1 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 1 x1 4 1 1 1 1 0 0 0 x5 4 0 2 1 1 1 0 0 x6 2 0 1 1 0 0 1 σj 4 0 3 2 1 0 0 1 2 3 0 0 0 Min{4， 2} θ=Min{ } 1 1 3 1 , Min{2} θ=Min{ } 3 1 47 * 6 2 0X ? T（，）cj 1 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 1 x1 6 1 0 0 1 0 1 0 x5 0 0 0 3 1 1 2 2 x2 2 0 1 1 0 0 1 σj 10 0 0 5 1 0 3 Z* = x1* +2x2*+3x3*=10 所以 48 二、對偶單純形法的步驟 (1)化 LP問題的約束條件為 “ ≤”形式 ,引入松弛變量 ,建立初始表 。 44 第四節(jié) 對偶單純形法 從一基可行解 (B1b≥0) 出發(fā)，在滿足可行解的基礎(chǔ)上，通過逐次基可行解的轉(zhuǎn)換，直至 σ j≤0( j∈J) 成立 （對 max問題），即達到可行的正則解，從而判斷是否得到最優(yōu)解或無最優(yōu)解。相應(yīng)的基稱為正則基。 b I II 設(shè) 備 1 2 8臺時 原材料 A 4 0 16公斤 原材料 B 0 4 12公斤 2 3 a21=3 (, 1/6, 0) c2=4 (2, 0, 0) b1=10 (0, , ) 42 （ 1）告訴管理者增加何種資源對企業(yè)更有利； cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 0 x5 3 x2 4 4 2 1 0 0 1/4 0 0 0 2 1/2 1 0 1 1/2 1/8 0 14 0 0 3/2 1/8 0 （ 2）告訴管理者花多大代價買進資源或賣出資源是合適的（在完全市場經(jīng)濟的條件下，當某種資源的市場價低于影子價格時，企業(yè)應(yīng)買進該資源用于擴大生產(chǎn)；而當當某種資源的市場價高于影子價格時，企業(yè)決策者應(yīng)把已有資源賣掉）； （ 3）為新產(chǎn)品定價提供依據(jù)。 對偶問題的最優(yōu)解實際上就是右端常數(shù)項的單位變化所引起的目標值的變化。 由 Z*= Y*b =y1*b1+y2*b2+? +ym*bm 可知 ?Z*/ ?b= Y* yi*=?Z*/ ?bi yi*表示資源量 bi 變化 1個單位對目標函數(shù)最優(yōu)值 Z 產(chǎn)生的影響，稱之為 第 i 種資源的影子價格 。 設(shè) X(0),Y(0)分別為 (L),(D)的 可行解，則 X(0),Y(0)分別為 (L),(D)的最優(yōu)解的充要條件為 ,有 m (1)若 xl(0) 0， 則 ∑ ail yi(0) = Cl i=1 m (2)若 ∑ ail yi(0) Cl ， 則 xl(0) = 0 i=1 n (3)若 yk(0) 0， 則 ∑ akj xj(0) = bk j=1 n (4)若 ∑ akj xj(0) bk ， 則 yk(0) =0 j=1 35 證明 （ P120） 36 ()L例 7 考慮下面問題 Max Z = x1+2x2+3x3 +4x4 x1+2x2+2x3+3x4 ≤20 . 2x1+ x2+3x3+2x4 ≤20 x1,x2,x3,x4 ≥0 ???()D Min W = 20y1+20y2 y1+2y2 ≥ 1 2y1+ y2 ≥ 2 . 2y1+3y2 ≥ 3 3y1+2y2 ≥ 4 y1,y2≥0 ???????已知 (D)的 最優(yōu)解為 Y*=(6/5,1/5)T 用互補松弛定理求出 (L)的最優(yōu)解。 33 Min z=2x1+3x2 x1+x2 ≥350 x1 ≥125 2x1+x2 ≤ 600 x1, x2 ≥0 Max w=350y1+125y2+600y3 . y1+ y2+2y3≤2 y1 + y3 ≤ 3 y1 ,y2 ≥0 。 例 5 求下列問題對偶問題的最優(yōu)解 Max Z =2x1+3x2 . x1+ 2x2≤8 4x1 ≤ 16 4x2≤ 12 x1 ,x2 ≥0 ???解：化為標準型 Max Z =2x1+3x2+0x3+0x4+0x5 . x1+ 2x2+x3 = 8 4x1 +x4 =16 4x2 +x5=12 x1 ,x2 , x3, x4, x5≥0 ???C CB XB b XB XN XS Z CB XB B1b CB CN 0 I CNCBB1N B1N B1 0 CBB1 CBB1b 31 cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 0 x5 3 x2 4 4 2 1 0 0 1/4 0 0 0 2 1/2 1 0 1 1/2 1/8 0 14 0 0 3/2 1/8 0 此時達到最優(yōu)解 X*=(4, 2)T, Max Z=14。 Y≥0……(D) 29 則 (σA,σS)= (C,0) –CBB1(A, I)=(C –CBB1A, –CBB1)≤0 由于 C–CBB1A≤0， 所以 CBB1A ≥C (1) 又 –CBB1≤0， 故 CBB1≥0. (2) 令 Y(0)=CBB1， 由 (1)、 (2)知 Y(0)是 (D)的可行解 . 因為 CX(0)=(CB, CN) XB(0) =CBXB(0)+CNXN(0) = CBB1b XN(0) 而 Y(0)b = CBB1b 則 CX(0)=Y(0)b ，由最優(yōu)性準則知， X(0),Y(0)分別為 (L)， (D)的最優(yōu)解 , 且目標函數(shù)最優(yōu)值相等。 X≥0……(L) min w=Yb。 設(shè) (L)的最優(yōu)解為 X(0)，且 X(0)所對應(yīng)的最優(yōu)基為 B， X(0)可以表示為 X(0) = XB(0) = B1b XN(0) 0 ????????????max z=CX。 證明： 設(shè) X(0),Y(0)分別為 (L)， (D)的可行解 ,由弱對偶定理(推論 3)，對于 (L)的任意可行解 X，有 CX ≤ Y(0)b，所以CX在可行域內(nèi)有上界，故 (L)有最優(yōu)解。 21 例 5 ()DMax 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 ???????由于 X(0)=(0,0,4,4)T, Y(0)=(6/5,1/5)T是 (L)， (D)的 可行解且 CX(0)=bTY(0)=28，所以 X(0),Y(0)分別為 (L)， (D)的最優(yōu)解。 (P57) 若 X(0),Y(0)分別為 (L)， (D)的可行解 ,且 CX(0)＝ Y(0)b, 則 X(0),Y(0)分別為 (L)， (D)的最優(yōu)解。 若 LP問題無可行解， 則對偶問題或有無界解 或無可行解。 YA≥C。 AX≤b。 極小化問題（ D）的任何一個可行解所對應(yīng)的目標 函數(shù)值都是其對偶問題 （ L） 目標函數(shù)值的上界。 x2 x1 1 1 1 1 y2 y1 1 1 1 1 原問題 對偶問題 若 LP問題有無界解，則其對偶問題無可行解 (弱對偶性 )； 若 LP問題無可行解，則對偶問題或有無界解或無可行解。YA≥C。YA≥C。AX≤b。 正常的對正常的，不正常的對不正常的 原問題約束條件是等式對應(yīng)于對偶問題決策變量無約束，反之亦然 11 例 3 直接寫出 LP問題的對偶問題 1 2 31 2 31 2 31 2 31 2 32 2 1:2 20 , 0 ,M a x Z x x xx x xx x xSTx x xx x x? ? ?? ? ???? ? ???? ? ??? ??? 無 約 束1 2 322M i n W u u u? ? ?1 2 3u u u? ? ?1 2 32u u u??1 2 3u u u??12???1 0u ? ，1:ST??????? 2u 無 約 束 ， 3 0u ?12