【文章內(nèi)容簡介】 CNXN =CBB1b＋（ CNCBB1N)XNCBB1XS 2021/6/16 浙江科技學院經(jīng)濟管理學院管工系 21 某一決策變量 xk系數(shù)列向量迭代前為 Pk，迭代后為 B1Pk。 0)PB()PB( )bB(m i n ik1ik1i1?? ????j1Bjj PBcc ????當 B為最優(yōu)基時 MaxZ=CBB1b＋（ CNCBB1N)XNCBB1XS ??????????????????????????????????????????????0BC0AB0BC0N)( B ,B0BC0N)BC,()C,(00BC0NBCC1B11B11B1BN1B1BNBBBBBBCCCCICCICC令 Y’=C BB1 0YC39。YA39。0Y0A39。YC?????????由此可以看出，當 X為最優(yōu)解時， Y為對偶問題的可行解。 且該可行解對應(yīng)的目標函數(shù)值 W=Y’b=CX* 2021/6/16 浙江科技學院經(jīng)濟管理學院管工系 22 非基變量 基變量 XB XN Xs 0 Xs b B N I cjzj CB CN 0 …… 基變量 非基變量 XB XN Xs CB XB B1b I B1N B1 cjzj 0 CNCBB1N CBB1 ?對應(yīng)初始單純形表中的單位矩陣 I，迭代后的單純形表中為 B1； ?初始單純形表中基變量 Xs=b，迭代后的表中為 XB=B1b； ?約束矩陣（ A， I）＝（ B， N， I），迭代后為 （ B1B， B1N， B1I）＝（ I， B1N， B1)； ?初始單純形表中 xj的系數(shù)向量為 Pj，迭代后為 Pj’ ，且 Pj’=B 1Pj’ 。 2021/6/16 浙江科技學院經(jīng)濟管理學院管工系 23 二、對偶問題的基本性質(zhì) 原始問題 max z=CX . AX≤b X ≥0 對偶問題 min w=Y’b . A’Y ≥ C’ Y ≥0 若 X0為原問題的可行解， Y0為對偶問題的可行解，則恒有 CX0≤Y0’b 證明： X0 ≥0為 LP的可行解， Y0 ≥0為 LD的可行解，則有： AX0 ≤b A’Y0 ≥ C’ → Y0’AX0 ≤Y0’b (A’Y0)’X0 ≥ (C’)’X0 → Y0’b ≥ Y0’AX0 ≥CX0 2021/6/16 浙江科技學院經(jīng)濟管理學院管工系 24 推論 : (LPMax LDMin) LD目標函數(shù)值的下界， 反之 LD任一可行解的目標函數(shù)是其 LP目標函數(shù)的上界。 Z=CX≤MaxZ=MinW ≤Y’b LP有可行解且目標函數(shù)值 無界 ，則其 LD無可行解 ； 反之 LD有可行解且目標函數(shù) 無界 ，則 LP無可行解 。 (對偶問題無可行解時，其原問題無界解或無可行解。 ) Z=CX→ +∞ ≤Y’b W= Y’b → ∞ ≥CX LP有可行解而其 LD無可行解時， LP目標函數(shù) 無界 反之，若 LD有可行解而其 LP無可行解時， LD目標函數(shù) 無界 。 2021/6/16 浙江科技學院經(jīng)濟管理學院管工系 25 若 X0為 LP的可行解， Y0為 LD的可行解，且 CX0＝ Y0’b,則X0， Y0分別為 LP和 LD的最優(yōu)解。 證明：設(shè) LP的最優(yōu)解為 X*,LD的最優(yōu)解為 Y* 又因為： CX* ≥CX0=Y0’b ≥Y*’b 又由弱對偶性定理： CX ≤Y’b 則 X0必為 X*,Y0必為 Y* 若原問題和對偶問題均具有可行解，則兩者均具有最優(yōu)解，且他們的最優(yōu)解的目標值相等。 2021/6/16 浙江科技學院經(jīng)濟管理學院管工系 26 如果 X*,Y*分別為 LP,LD問題的可行解，則 X*,Y*為最優(yōu)解的充要條件為： Y*’XS*=0 YS*’X*=0 ??????????0,0 SSXXbXAXCXM axZLP證明：設(shè) ???????????0Y,0YCYYbYi n WD 39。39。39。SSAML**39。*39。**39。***39。*39。***)()(,XYAYCXbYXAXYbYCXYXSS ???????為最優(yōu)解時，有當**39。S*S*39。 XYXY ???0XYXY0Y0,X,0Y0,X0X)Y(X)Y(**39。S*S*39。*39。S*S*39。***39。S*S*39。??????????????? 當 LP中第 i個約束是嚴格不等式，則 Y中的 Yi必為0，如果 Yi不為 0,則 LP中第 i個約束為嚴格等式。 當 LD中第 j個約束是嚴格不等式，則 X中的 xj必為0，如果 xj不為 0,則 LD中第 j個約束為嚴格等式。 2021/6/16 浙江科技學院經(jīng)濟管理學院管工系 27 課堂作業(yè) P74 課后作業(yè) (P75P76) 2021/6/16 浙江科技學院經(jīng)濟管理學院管工系 28 影子價格 闡述對偶變量的經(jīng)濟意義，即對偶變量的經(jīng)濟解釋 引例：美佳公司 ???????????????0,52426155LP2212121221xxxxxxxxxM a x Z???????????????3,2,1,012526LD5241532132321jyyyyyyyyyM i n Wj…… ① …… ② …… ③ …… ① …… ② 如果已知 LP的 X*=(7/2,3/2,15/2,0,0)’ Z*= Y*,W*？ 由對偶問題的基本性質(zhì)知： W*=Z*= → 15Y1+24y2+5y3= 又因為 Y*’XS*=0 X*代入 LP的約束條件中，知①為嚴格不等式，則 xS10，則 y1=0 由互補松弛定理： 因為 YS*‘X*=0 X10,X20則 yS1*=0, yS2*=0 ，即 LD的①，②為嚴格等式 6y2+y3=2 5y1+2y2+y3=1 → Y1=0 Y2=1/4 y3=1/2 2021/6/16 浙江科技學院經(jīng)濟管理學院管工系 29 ：根據(jù)對偶問題的基本性質(zhì) **mm*11m1i*iin1j*jj*nn*11* WybybybxcxcxcZ ????????? ??????對 LP為生產(chǎn)問題而言： bi表示 LP中第 i種資源