1、第第3章章 線性規劃對偶理論線性規劃對偶理論及其應用及其應用例例1 穗羊公司的例子穗羊公司的例子III每周可使用量每周可使用量A（千克）（千克）125B（噸）（噸）214C（百工時）（百工時）439單位產品利潤（萬元）單位產品利潤（萬元）323.1 線性規劃的對偶問題線性規劃的對偶問題穗家公司由于訂單較多，希望收購穗羊公司的各種穗家公司由于訂單較多，希望收購穗羊公司的各種資源以擴大自己的生產能力，那么穗羊公司的資源資源以擴大自己的生產能力，那么穗羊公司的資源該如何定價呢？該如何定價呢？0,934425223max2121212121xxxxxxxxs.t.xxz生產計劃問題（生產計劃問題（LP

2、1）資源定價問題（資源定價問題（LP2）原料原料A原料原料B工時工時CY1Y2Y3產品產品1產品產品2原料原料A原料原料B工時工時C產品產品1產品產品2方程對變量，變量對方程方程對變量，變量對方程 min w = 5y1+4y2+9y3 y1+ 2 y2 + 4y332 y1 + y2 + 3y32y1 , y2 , y3 03.1.2 規范形式線性規劃的對偶問題規范形式線性規劃的對偶問題0. .maxXbAXtsCXz0. .minYCYAtsYbw原問題（LP1）對偶問題（LP2） 原問題（LP1） 對偶問題 （LP2） 目標目標max型型 目標目標min型型 有有n個變量（非負）個變量（

3、非負） 有有n個約束（大于等于）個約束（大于等于） 有有m個約束個約束 （小于等于）（小于等于） 有有m個變量（非負）個變量（非負） 價值價值系數系數 資源系數資源系數 資源資源系數系數 價值價值系數系數 技術系數矩陣技術系數矩陣 技術系數矩陣的轉置技術系數矩陣的轉置(AB)=AB(AB)= BA(A)=A 矩陣轉置 max. .(3.1)0zCXAXbstXmin. .(3.2)0wb YA YCstY12nyyYy3.1.3 非規范形式線性規劃的對偶問題非規范形式線性規劃的對偶問題1 變量取值范圍不符合非負要求的情況變量取值范圍不符合非負要求的情況0,22122111.min2122112

4、12211yycyycyytsybybw0,22211211.max212211212211xxbxxbxxtsxcxcz0, 022211211. .max212211212211xxbxxbxxtsxcxcz0,22122111. .min212211212211yycyycyytsybybw將其約束方程第二行將其約束方程第二行左右同乘左右同乘-1： 0,22211211. .max212211212211xxbxxbxxtsxcxcz令令 022xx0,22122111. .min212211212211yycyycyytsybybw無約束212211212211, 022211211.

5、 .maxxxbxxbxxtsxcxcz0,22122111. .min212211212211yycyycyytsybybw解解:令令2 約束方程不是約束方程不是“”的情況的情況 0, 022211211. .max212211212211xxbxxbxxtsxcxcz解：約束方程第二解：約束方程第二行左右同乘行左右同乘1：其對偶規劃為：其對偶規劃為：令 得到原問題的對偶問題為： 0, 022211211. .max212211212211xxbxxbxxtsxcxcz無約束212211212211, 022122111. .minyycyycyytsybybw解解: :約束方程第二行的約束

6、方程第二行的等式拆為兩個不等式等式拆為兩個不等式: :其對偶規劃為：其對偶規劃為：令 得到原問題的對偶問題為： 3.1.4 總結總結方程對變量，變量對方程；方程對變量，變量對方程；正常對正常，不正常對不正常；正常對正常，不正常對不正常；變量正常是非負，方程正常看目標變量正常是非負，方程正常看目標(max ，min )。 max =7y1+4y2-2y3 2y1+ y2 - y3 3 y1 +3y3 2-4y1+ 2y2 -6 y1 - y2 - y3 0 3y1 + y3 1 y10, y20, y3無約束無約束 =min z=3x1+2x2-6x3+x5 2x1+ x2- 4x3+x4+3x

7、57 x1+ 2x3 -x4 4 -x1+3x2 -x4+ x5 = -2 x1,x2,x30; x4 0;x5無約束無約束 例例 求解下面線性規劃的對偶規劃求解下面線性規劃的對偶規劃0, 0, 04422923532. .532max43214321432143214321xxxxxxxxxxxxxxxxtsxxxxz無約束，無約束321321321321321321, 0, 053423122223. .495minyyyyyyyyyyyyyyytsyyywLP2: min w = 5y1+4y2+9y3 y1+ 2 y2 + 4y33 st. 2 y1 + y2 + 3y32 y1 ,

8、y2 , y3 0 x1 + 2x2 5 2x1+ x2 4 4x1+3x2 9 x1 ,x2 0LP1: max z=3x1+2x2st. .對偶變量對偶變量y1y2y3對偶變量對偶變量x1x2 x x1 1+ +2x2 +x3 = 52x1+ x2 +x4 = 44x1+3x2 +x5 = 9 x1 ,x2 ,x3 ,x4 , x50 y1 + 2y2 + 4y3 y4 = 32y1 + y2 + 3y3 y5 = 2 y1 , y2 , y3 , y4 , y5 0原原問題變量問題變量原問題松弛變量原問題松弛變量CBXBx1x2x3x4x5b032x3x1x20100011005/23/

9、2-2-3/2-1/213/23/21- -j j0001/21/213/2原問題松弛變量原問題松弛變量原原問題變量問題變量x3 x4x5x1x2對偶問題剩余變量對偶問題剩余變量對偶問題變量對偶問題變量y4 y5y1y2y3對偶問題變量對偶問題變量對偶問題剩余變量對偶問題剩余變量CBXBy1y2y3y4y5b49y2y3-5/415/21001-1/41/21/4-3/21/21/2j j3/2003/2113/232000CBXBx1x2x3x4x5b000 x3x4x5124213100010001549320000030 x3x1x50103/21/21100-1/21/2-200132

10、101/20-3/206032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/213/2max z = CX + 0XS st. AX +I XS = b ( I式式 ) X, XS0I 式式經過若干迭代，經過若干迭代，基矩陣為基矩陣為B，則則上式上式等價與等價與：max z = CBXB + CNXN + 0XS st. BXB + NXN+ I XS = b XB, XN, XS0max z = CX st. AX b X0LP:max Z = CB B -1b+（CN-CB B -1N）XN - CB B -1XS st. XB + B

11、-1N XN + B -1XS = B -1b XB ，XN，XS 0 單純形算法的矩陣表示單純形算法的矩陣表示基基解解 XB XN XSXSb B N I j CB CN 0基基解解 XB XN XSXBB -1b I B -1N B -1 j 0 CN - CB B 1N - CB B -1初始單純形表初始單純形表基為基為B時單純形表時單純形表單純形算法的矩陣表示單純形算法的矩陣表示Cj23 500bCBXBx1x2 x3x4x50 x42/3 1/3 4/31011/60 x52/3 4/3 10/30110/3j j23 50000 CN-CBB-1N-CBB-1CBB-1bCB CN

12、 00例例: max z = 2x1+3x2+5x3 2/3 x1+ 1/3 x2 + 4/3x311/6 st. 2/3 x1 + 4/3x2 + 10/3x310/3 x1 , x2 , x3 0BINB-1NIB-1Cj23 50 0bCBXBx1x2 x3x4 x52x11 0 12-1/223x20 1 2-1 13/2j j00 -3-1 -217/2初初始始表表最最終終表表3max z = 2x1+3x2+5x3 2/3 x1+ 1/3 x2 + 4/3x3 + x4= 11/6 st. 2/3 x1 + 4/3x2 + 10/3x3 + x5= 10/3 x1 , x2 , x

13、3 ，x4 , x5 0基基解解 XB XN XSXBB -1b I B -1N B -1 j 0 CN - CB B 1N - CB B -1基為基為B時單純形表時單純形表若若B為最優基，則為最優基，則 CB CBB 1B = 0CN CBB 1N 0 - CBB -1 0則則 AY C Y0= Yb = CBB1 b= z* 令令 Y = CBB1，Y = S S = CBB1YS = = C CBB1AC CBB 1A 0- CBB 10例：下表為例：下表為“max，”型線性規劃問題加入松弛變量型線性規劃問題加入松弛變量后的最優解單純形表后的最優解單純形表BV.x1x2x3x4x5bx1

14、100105x500-1/21/211x2011/2-1/20200-3/2-1/20（1 1）問題中有幾個約束方程、幾個決策變量、幾）問題中有幾個約束方程、幾個決策變量、幾個松弛變量？個松弛變量？（2 2）此線性規劃問題的最優解）此線性規劃問題的最優解x x* *=?=?（3 3）對偶問題的最優解）對偶問題的最優解y y* *=? =? 3.2 對偶規劃的基本性質對偶規劃的基本性質3.2.1 對稱性定理對稱性定理：線性規劃的對偶問題的對偶問題：線性規劃的對偶問題的對偶問題是原問題是原問題證明：證明： 對偶的定義對偶的定義對偶的定義對偶的定義max z=CXs.t. AXb X 0min w=

15、bYs.t. AYCY 0min z = - CXs.t. -AX -bX 0max w = -bYs.t. -AY-CY 0 以下定理以下定理3.2.2-3.2.5，假定原問題是，假定原問題是(3.1)，對，對偶問題是偶問題是(3.2)。 max. .(3.1)0zCXAXbstXmin. .(3.2)0wb YA YCstY3.2.2 弱對偶性定理弱對偶性定理：如果：如果X、Y分別是原問題和對分別是原問題和對偶問題的一個可行解，則其對應的原問題的目偶問題的一個可行解，則其對應的原問題的目標函數值不大于對偶問題的目標函數值，也即標函數值不大于對偶問題的目標函數值，也即YbCX0XbAX0YC

16、YAYbYAXYAXCXCX)(證明：因為證明：因為X、Y分別是原問題（分別是原問題（3.1）與對偶問題）與對偶問題（3.2）的可行解，故：）的可行解，故： 所以所以 推論一推論一：原問題任一可行解的目標函數值是其：原問題任一可行解的目標函數值是其對偶問題目標函數值的下界；反之對偶問題任對偶問題目標函數值的下界；反之對偶問題任一可行解的目標函數值是其原問題目標函數值一可行解的目標函數值是其原問題目標函數值的上界。的上界。 推論二推論二：如果原問題存在無界解，則對偶問題：如果原問題存在無界解，則對偶問題一定無可行解；反之，如果對偶問題存在無界一定無可行解；反之，如果對偶問題存在無界解，原問題也一

17、定不存在可行解。解，原問題也一定不存在可行解。( (若其中一若其中一個問題為無界解，則另一個問題無可行解個問題為無界解，則另一個問題無可行解) ) 注意，該推論的逆定理并不成立。注意，該推論的逆定理并不成立。 3.2.3 最優性定理最優性定理: :如果如果 是原問題的可行解，是原問題的可行解， 是其對偶問題的可行解，且有是其對偶問題的可行解，且有 ，則：則： 是原問題和對偶問題的最優解。是原問題和對偶問題的最優解。XYYbXC YX、證明證明: 假設假設X* ,Y*分別是原問題與對偶問題的分別是原問題與對偶問題的最優解，則顯然它們也是各自的可行解。最優解，則顯然它們也是各自的可行解。而根據最優

18、解的定義，而根據最優解的定義， *CXXCXCYbCX *由弱對偶性定理得：由弱對偶性定理得：所以所以 *CXXC因而因而 是也原問題的最優解是也原問題的最優解 X同理，可證同理，可證 也是其對偶問題的最優解。也是其對偶問題的最優解。 Y3.2.4 強對偶性定理（對偶定理）強對偶性定理（對偶定理）如果原問題存在最優解如果原問題存在最優解X*，則其對偶問題一定具，則其對偶問題一定具有最優解有最優解Y*，且，且*YbCX則則Y*=0, 且且AY* C所以由最優性定理知所以由最優性定理知Y*為對偶問題的最優解。為對偶問題的最優解。 如果原問題存在最優解，假設其對應的基是如果原問題存在最優解，假設其對

19、應的基是B，即，即 0,*1*NBXbBX令令)(1*BCYB所以所以Y*滿足對偶問題的約束條件滿足對偶問題的約束條件, 是其可行解是其可行解 又因為又因為 CX* = CBB1 b= (Y*)b=b Y*3.2.5 互補松弛定理互補松弛定理線性規劃問題的最優解中，線性規劃問題的最優解中，)0 x (bx a,0y siin1jjiji 即即則則若若0y ),0 x (bx aisiin1jjij 則則即即若若njxmibxatsxczjinjijijjnjj,2, 1,0,2, 1,.max11線性規劃問題的最優解中，線性規劃問題的最優解中，0y ,cy a,0 x sjjm1iiijj 即

20、即則則若若0 x ,0y ,cy ajsjjm1iiij 則則即即若若yi xSi = 0 xj ySj = 0miynjcyatsybwijmiijimiii,2, 1,0,2, 1,.min11yi0,分為兩種情況：分為兩種情況： yi0，變量比較松；，變量比較松；yi=0，變量比較緊；，變量比較緊；互補松弛定理的解釋互補松弛定理的解釋約束方程約束方程 分為兩種情況：分為兩種情況： , ,約束條件比較松；約束條件比較松； , ,約束條件比較緊約束條件比較緊injjijbxa1injjijbxa1injjijbxa1變量同其對偶問題的約束方程之間至多只能夠有一個取松弛的情況，當其中一個取松弛

21、的情況時，另外一個比較緊，即取嚴格等號 。 例例3.6 已知下面的已知下面的LP1和和LP2為一組對偶規劃，且已知為一組對偶規劃，且已知LP1的最優解為的最優解為X=（1.5，1）T。試運用互補松弛定理。試運用互補松弛定理求出對偶問題的最優解求出對偶問題的最優解Y。解：由解：由X=（1.5，1），得），得55 . 3221 xx01y0, 021xx232342321321yyyyyy聯立求解得：聯立求解得：5 . 0, 5 . 0, 0321yyy生產計劃問題（生產計劃問題（LP1）資源定價問題（資源定價問題（LP2） max z=3x1+2x2 x1 + 2x2 5 2x1+ x2 4 4

22、x1+3x2 9 x1 ,x2 0st. . y1+ 2 y2 + 4y33 st. 2 y1 + y2 + 3y32 y1 , y2 , y3 0 min w = 5y1+4y2+9y3 3.3 影子價格和靈敏度分析影子價格和靈敏度分析 3.3.1 影子價格影子價格 對偶變量的經濟含義就是資源的定價，然而對偶變量的經濟含義就是資源的定價，然而這種價格同市場價格不同，我們稱之為影子價格。這種價格同市場價格不同，我們稱之為影子價格。它反映了資源對于企業的緊缺程度、利潤貢獻程它反映了資源對于企業的緊缺程度、利潤貢獻程度等，并不能反映資源的生產成本，以及在外部度等，并不能反映資源的生產成本，以及在外

23、部市場的緊缺程度。市場的緊缺程度。 1 1、影子價格是邊際利潤、影子價格是邊際利潤wybYbCXzmiii1iiybw如果某種資源有剩余，則增加資源不會增加利潤；如果某種資源有剩余，則增加資源不會增加利潤；如果某種資源影子價格大于如果某種資源影子價格大于0 0，則資源一定沒有剩余。，則資源一定沒有剩余。說明資源增加說明資源增加1 1個單位，企業總利潤可以增加個單位，企業總利潤可以增加y yi i單位。單位。所以如果資源的市場價格低于所以如果資源的市場價格低于y yi i，就要買進。，就要買進。互補松弛定理互補松弛定理y1y2ym2、影子價格是影子價格是產品的機會成本產品的機會成本 (Oppor

24、tunity Cost)機會成本機會成本 表示減少一件產品所節省的資源可以增加的利潤表示減少一件產品所節省的資源可以增加的利潤mmjiijjjyayayaya2211減少一件產品可以節省的資源減少一件產品可以節省的資源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211增加單位資源可以增加的利潤增加單位資源可以增加的利潤如果該產品機會成本大于利潤，則該產品不生產。如果該產品機會成本大于利潤，則該產品不生產。對于原有產品，如果生產的，則其機會成本等于

25、對于原有產品，如果生產的，則其機會成本等于利潤。利潤。0jxjmiiijcya10jxjmiiijcya1miiijya1對于原有產品對于原有產品j j，其機會成本為，其機會成本為 在利潤最大化的生產計劃中在利潤最大化的生產計劃中 （1）影子價格大于）影子價格大于0的資源沒有剩余；的資源沒有剩余； （2）有剩余的資源影子價格等于）有剩余的資源影子價格等于0； （3）安排生產的產品機會成本等于利潤；）安排生產的產品機會成本等于利潤； （4）機會成本大于利潤的產品不安排生產。）機會成本大于利潤的產品不安排生產。總結3.3.2 靈敏度分析靈敏度分析1、目標函數系數、目標函數系數cj變化變化例例 3.

26、7 C由由(3.2)變為變為(3,1)，請問最優生產計劃如何變化？，請問最優生產計劃如何變化？32000CBXBx1x2x3x4x5b000 x3x4x512421310001000154932000032000CBXBx1x2x3x4x5b032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/211114 5初初始始表表最最優優表表z解：由原最優單純形表得：解：由原最優單純形表得：31000CBXBx1x2x3x4x5b031x3x1x20100011005/23/2-2-3/2-1/213/23/21000-5/21/211/2252325

27、4) 2(1300500 ( 3/2)3 ( 1/2) 1 1 1/20 所以原最優解不是新問題的最優解所以原最優解不是新問題的最優解 單純形迭代得：單純形迭代得：31000bCBxBx1x2x3x4x50 x30 3/21 -1/2033x11 1/20 1/2020 x50 10 -21 1 0 -1/20- 3/206所以得到新的最優生產計劃為產品所以得到新的最優生產計劃為產品I生產生產2件，件，產品產品II不生產，此時總利潤上升為不生產，此時總利潤上升為6萬元。萬元。例例3.8 假設產品假設產品II的價格不變，請問產品的價格不變，請問產品I的利潤在什的利潤在什么范圍內波動時，最優生產計

28、劃不變？么范圍內波動時，最優生產計劃不變？ 41 32 512欲使最優生產計劃不變，須欲使最優生產計劃不變，須02102311313解：假設解：假設c1由由3變為變為 ，則，則32000bCBxBx1x2x3x4x50 x30 0 1 5/2-3/23/23x11 0 0 3/2- 1/23/22x20 1 0 -2 1 1 0 0 0 - 1/2-1/213/2所以所以,當當-1/3,1,即即c1 8/3,4時時,最優生產計劃不變最優生產計劃不變最優解保持不變的最優解保持不變的C變化范圍變化范圍但要分兩種情況討論。只影響最優性時變為價格,ccc即可。故只要，為因只影響自己的檢驗數的價格系數是

29、非基變量0, (1)1jjBjjjjjPBCccxc 的范圍。解得只需由jjc 0。解得公共的應由所有的數這時要影響所有的檢驗的價格系數是基變量jiimiiiijjcPBcccccxc0,)( (2)112、約束條件右端向量、約束條件右端向量b的變化的變化 例例3.8 b由由(5 4 9)T變為變為(5 5 9)T，最優生產計劃如何變化？，最優生產計劃如何變化？32000CBXBx1x2x3x4x5b000 x3x4x512421310001000154932000032000CBXBx1x2x3x4x5b032x3x1x20100011005/23/2-2-3/2-1/213/23/2100

30、0-1/2-1/213/25b1 b2 b3 z初初始始表表最最優優表表1349551202/12/302/32/511bBXB解：解：顯然顯然X=(3,-1,4,0,0)T不是基可行解不是基可行解XB帶入原最終單純形表得：帶入原最終單純形表得：32000bCBxBx1x2x3x4x50 x30 0 1 5/2-3/24(1)3x11 0 0 3/2- 1/23(2)2x20 1 0 -2 1 -1 (3)0 0 0 - 1/2-1/27(4)jl因為因為x2=-10，所以令其，所以令其岀岀基。基。minbi/bi0=brl檢驗數所在行除以出基變量所在行，商最小的列對應的檢驗數所在行除以出基變量所在行，商最小的列對應的元素作為主元素元素作為主元素min /arj ,arj0 。這里。這里正數和零不能正數和零不能作為主元素作為主元素 。l本題中第三行只有本題中第三行只有a34=-20，所以選為主元素，進行對偶，所以選為主元素，進行對偶迭代迭代l迭代的目標：迭代的目標：