1、1,第二章對偶理論與靈敏度分析,1 單純形法的矩陣描述 設(shè)max z = CX AX = b X 0 A為mn階矩陣 RankA=m ,取B為可行基, N為非基，,2,3,4,求解步驟：,5,6,現(xiàn)在出租，設(shè)y1為設(shè)備單位臺時的租金 y2,y3為材料A、B轉(zhuǎn)讓附加費(kg-1),則M2為M1的對偶問題， 反之亦然。,7,一般的，原問題：max z = CX AX b X 0,對偶問題：min w = Yb YA C Y 0,比較： max z min w 決策變量為n個 約束條件為n個 約束條件為m個 決策變量為m個 “” “”,8,3 對偶問題的化法 1、典型情況 eg.2max z = x

2、1 + 2x2 + x3 2x1 + x2 6 2x2 + x3 8 x1,x2,x3 0,9,2、含等式的情況 eg.3max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 = 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0,一般，原問題第i個約束取等式，對偶問題第i個變量無約束。,10,3、含“”的max問題 eg.4max z = x1 + 2x2 + 4x3 2x1 + x2 + 3x3 3 x1 + 2x2 + 5x3 4 x1,x2,x3 0,11,一般: max問題第i個約束取“”，則min問題第i個變量 0 ；, min問題第i個約束取“”，則

3、max問題第i個變量 0 ；, 原問題第i個約束取等式，對偶問題第i個變量 無約束；, max問題第j個變量 0 ,則min問題第j個約束取“” ；, min問題第j個變量 0 ，則max問題第j個約束取“” ；, 原問題第j個變量無約束，對偶問題第j個約束取等式。,12,eg.5min z = 2x1 + 3x2 - 5x3 + x4 x1 + x2 - 3x3 + x4 5 2x1 + 2x3 - x4 4 x2 + x3 + x4 = 6 x1 0,x2,x3 0,x4無約束,13,4 對偶問題的性質(zhì),1、對稱性 對偶問題的對偶為原問題.,14,15,16,推論： (1) max問題任一

4、可解的目標(biāo)值為min問題目標(biāo)值的一個下界； (2) min問題任一可解的目標(biāo)值為max問題目標(biāo)值的一個上界。,3、無界性 若原問題(對偶問題)為無界解，則對偶問題(原問題)為無可行解。,注：該性質(zhì)的逆不存在。若原(對偶)問題為無可行解，對偶(原問題)問題或為無界解，或為無可行解。,17,4、最優(yōu)性 設(shè)X*，Y*分別為原問題和對偶問題可行解，當(dāng) CX*=Y*b時， X*，Y*分別為最優(yōu)解。,18,5、對偶定理 若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解， 且目標(biāo)值相等。,19,Y*為對偶問題的最優(yōu)解，且原問題和對偶問題 的目標(biāo)值相等。 證畢,6、松弛性 若X*，Y*分別為原問題及對偶問題的可行解，

5、 那么Ys*X*=0，Y*Xs*=0，當(dāng)且僅當(dāng)X*，Y*分別為 最優(yōu)解。,證明：,20,將b,C分別代入目標(biāo)函數(shù)：,21,其中：,用分量表示：,22,7、檢驗數(shù)與解的關(guān)系 (1)原問題非最優(yōu)檢驗數(shù)的負值為對偶問題的一個基解。 (2)原問題最優(yōu)檢驗數(shù)的負值為對偶問題的最優(yōu)解。,檢驗數(shù)： = (C 0)- CBB-1(A I) = (C- CBB-1A - CBB-1) = (c s) c = C - CBB-1A X對應(yīng)的檢驗數(shù) s = - CBB-1 Xs對應(yīng)的檢驗數(shù),23,eg.6已知：min w = 20y1 + 20y2 的最優(yōu)解為y1*=1.2,y2*=0.2 -ys1 y1 + 2y

6、2 1 試用松弛性求對偶 -ys2 2y1 + y2 2 問題的最優(yōu)解。 -ys3 2y1 + 3y2 3 -ys4 3y1 + 2y2 4 y1,y2 0,y1*xs1* = 0 y2*xs2* = 0 ys1*x1* = 0 ys2*x2* = 0 ys3*x3* = 0 ys4*x4* = 0,24,y1*=1.2,y2*0.2 0 xs1* = xs2* = 0 由 y1* + 2y2* = 1.6 1 ys1* 0 x1* = 0 由 2y1* + y2* = 2.6 2 ys2* 0 x2* = 0 由 2y1* + 3y2* = 3 =右邊 ys3* = 0 x3*待定 由 3y

7、1* + 2y2* = 4 =右邊 ys4* = 0 x4*待定,最優(yōu)解：x1* = 0 x2* = 0 x3* = 4 x4* = 4 xs1* = 0 xs2* = 0 最大值：z* = 28 = w*,25,5 對偶問題的經(jīng)濟含義影子價格 最優(yōu)情況：z* = w* = b1y1* + + biyi* + + bmym*,26,6 對偶單純形法 單純形法：由 XB = B-1b 0，使j 0，j = 1,m 對偶單純形法：由j 0(j= 1,n)，使XB = B-1b 0,步驟：(1)保持j 0，j= 1,n，確定XB，建立計算表格；,(2)判別XB = B-1b 0是否成立？ 若成立，X

8、B為最優(yōu)基變量； 若不成立，轉(zhuǎn)(3)；,27,(4)消元運算，得到新的XB。,(3)基變換 出基變量，,入基變量，,重復(fù)（2）-（4）步，求出結(jié)果。,28,eg.8用對偶單純形法求解 min w = 2x1 + 3x2 + 4x3 x1 + 2x2 + x3 1 2x1 - x2 + 3x3 4 x1,x2,x3 0,29,x4,x5 0 非最優(yōu),x1,x4 0 最優(yōu),最優(yōu)解：x1* = 2，x2* = 0，x3* = 0，x4* = 1，x5* = 0 目標(biāo)值：w* = -z* = 4,30,7 靈敏度分析,分析 變化對最優(yōu)解的影響。,31,32,例1 已知下述問題的最優(yōu)解及最優(yōu)單純形表,33,最優(yōu)單純形表如下:,34,由最優(yōu)單純形表得:,35,36,不可行!,用對偶單純形法計算,37,3/4,-2,38,39,例2 求例1 c4的變化范圍,使最優(yōu)解不變.,解:,40,分析:,41,方法:,例3 求例1 c2的變化范圍,使最優(yōu)解不變.,42,解:,43,44,分析:,45,46,例4 求例1 a24的變化范圍,使最優(yōu)解不變.,解:,47,例5 在例1的基礎(chǔ)上，企業(yè)要增加一個 新產(chǎn)品,每件產(chǎn)品需2個臺時，原材料A 6kg， 原材料B 3kg，利潤 5元/件，問如何安排各產(chǎn) 品的產(chǎn)量，使利潤最大？ 解：,48,表明生產(chǎn)新品有利。,49,50,