運(yùn)籌學(xué)第三章對(duì)偶理論

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

2、1）資源定價(jià)問題（資源定價(jià)問題（LP2）原料原料A原料原料B工時(shí)工時(shí)CY1Y2Y3產(chǎn)品產(chǎn)品1產(chǎn)品產(chǎn)品2原料原料A原料原料B工時(shí)工時(shí)C產(chǎn)品產(chǎn)品1產(chǎn)品產(chǎn)品2方程對(duì)變量，變量對(duì)方程方程對(duì)變量，變量對(duì)方程 min w = 5y1+4y2+9y3 y1+ 2 y2 + 4y332 y1 + y2 + 3y32y1 , y2 , y3 03.1.2 規(guī)范形式線性規(guī)劃的對(duì)偶問題規(guī)范形式線性規(guī)劃的對(duì)偶問題0. .maxXbAXtsCXz0. .minYCYAtsYbw原問題（LP1）對(duì)偶問題（LP2） 原問題（LP1） 對(duì)偶問題 （LP2） 目標(biāo)目標(biāo)max型型 目標(biāo)目標(biāo)min型型 有有n個(gè)變量（非負(fù)）個(gè)變量（

3、非負(fù)） 有有n個(gè)約束（大于等于）個(gè)約束（大于等于） 有有m個(gè)約束個(gè)約束 （小于等于）（小于等于） 有有m個(gè)變量（非負(fù)）個(gè)變量（非負(fù)） 價(jià)值價(jià)值系數(shù)系數(shù) 資源系數(shù)資源系數(shù) 資源資源系數(shù)系數(shù) 價(jià)值價(jià)值系數(shù)系數(shù) 技術(shù)系數(shù)矩陣技術(shù)系數(shù)矩陣 技術(shù)系數(shù)矩陣的轉(zhuǎn)置技術(shù)系數(shù)矩陣的轉(zhuǎn)置(AB)=AB(AB)= BA(A)=A 矩陣轉(zhuǎn)置 max. .(3.1)0zCXAXbstXmin. .(3.2)0wb YA YCstY12nyyYy3.1.3 非規(guī)范形式線性規(guī)劃的對(duì)偶問題非規(guī)范形式線性規(guī)劃的對(duì)偶問題1 變量取值范圍不符合非負(fù)要求的情況變量取值范圍不符合非負(fù)要求的情況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：其對(duì)偶規(guī)劃為：其對(duì)偶規(guī)劃為：令 得到原問題的對(duì)偶問題為： 0, 022211211. .max212211212211xxbxxbxxtsxcxcz無約束212211212211, 022122111. .minyycyycyytsybybw解解: :約束方程第二行的約束

6、方程第二行的等式拆為兩個(gè)不等式等式拆為兩個(gè)不等式: :其對(duì)偶規(guī)劃為：其對(duì)偶規(guī)劃為：令 得到原問題的對(duì)偶問題為： 3.1.4 總結(jié)總結(jié)方程對(duì)變量，變量對(duì)方程；方程對(duì)變量，變量對(duì)方程；正常對(duì)正常，不正常對(duì)不正常；正常對(duì)正常，不正常對(duì)不正常；變量正常是非負(fù)，方程正?？茨繕?biāo)變量正常是非負(fù)，方程正?？茨繕?biāo)(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無約束無約束 例例 求解下面線性規(guī)劃的對(duì)偶規(guī)劃求解下面線性規(guī)劃的對(duì)偶規(guī)劃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. .對(duì)偶變量對(duì)偶變量y1y2y3對(duì)偶變量對(duì)偶變量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對(duì)偶問題剩余變量對(duì)偶問題剩余變量對(duì)偶問題變量對(duì)偶問題變量y4 y5y1y2y3對(duì)偶問題變量對(duì)偶問題變量對(duì)偶問題剩余變量對(duì)偶問題剩余變量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 式式經(jīng)過若干迭代，經(jīng)過若干迭代，基矩陣為基矩陣為B，則則上式上式等價(jià)與等價(jià)與：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時(shí)單純形表時(shí)單純形表單純形算法的矩陣表示單純形算法的矩陣表示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時(shí)單純形表時(shí)單純形表若若B為最優(yōu)基，則為最優(yōu)基，則 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，”型線性規(guī)劃問題加入松弛變量型線性規(guī)劃問題加入松弛變量后的最優(yōu)解單純形表后的最優(yōu)解單純形表BV.x1x2x3x4x5bx1

14、100105x500-1/21/211x2011/2-1/20200-3/2-1/20（1 1）問題中有幾個(gè)約束方程、幾個(gè)決策變量、幾）問題中有幾個(gè)約束方程、幾個(gè)決策變量、幾個(gè)松弛變量？個(gè)松弛變量？（2 2）此線性規(guī)劃問題的最優(yōu)解）此線性規(guī)劃問題的最優(yōu)解x x* *=?=?（3 3）對(duì)偶問題的最優(yōu)解）對(duì)偶問題的最優(yōu)解y y* *=? =? 3.2 對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì)3.2.1 對(duì)稱性定理對(duì)稱性定理：線性規(guī)劃的對(duì)偶問題的對(duì)偶問題：線性規(guī)劃的對(duì)偶問題的對(duì)偶問題是原問題是原問題證明：證明： 對(duì)偶的定義對(duì)偶的定義對(duì)偶的定義對(duì)偶的定義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)，對(duì)，對(duì)偶問題是偶問題是(3.2)。 max. .(3.1)0zCXAXbstXmin. .(3.2)0wb YA YCstY3.2.2 弱對(duì)偶性定理弱對(duì)偶性定理：如果：如果X、Y分別是原問題和對(duì)分別是原問題和對(duì)偶問題的一個(gè)可行解，則其對(duì)應(yīng)的原問題的目偶問題的一個(gè)可行解，則其對(duì)應(yīng)的原問題的目標(biāo)函數(shù)值不大于對(duì)偶問題的目標(biāo)函數(shù)值，也即標(biāo)函數(shù)值不大于對(duì)偶問題的目標(biāo)函數(shù)值，也即YbCX0XbAX0YC

16、YAYbYAXYAXCXCX)(證明：因?yàn)樽C明：因?yàn)閄、Y分別是原問題（分別是原問題（3.1）與對(duì)偶問題）與對(duì)偶問題（3.2）的可行解，故：）的可行解，故： 所以所以 推論一推論一：原問題任一可行解的目標(biāo)函數(shù)值是其：原問題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問題目標(biāo)函數(shù)值的下界；反之對(duì)偶問題任對(duì)偶問題目標(biāo)函數(shù)值的下界；反之對(duì)偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。的上界。 推論二推論二：如果原問題存在無界解，則對(duì)偶問題：如果原問題存在無界解，則對(duì)偶問題一定無可行解；反之，如果對(duì)偶問題存在無界一定無可行解；反之，如果對(duì)偶問題存在無界解，原問題也一

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

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

19、應(yīng)的基是B，即，即 0,*1*NBXbBX令令)(1*BCYB所以所以Y*滿足對(duì)偶問題的約束條件滿足對(duì)偶問題的約束條件, 是其可行解是其可行解 又因?yàn)橛忠驗(yàn)?CX* = CBB1 b= (Y*)b=b Y*3.2.5 互補(bǔ)松弛定理互補(bǔ)松弛定理線性規(guī)劃問題的最優(yōu)解中，線性規(guī)劃問題的最優(yōu)解中，)0 x (bx a,0y siin1jjiji 即即則則若若0y ),0 x (bx aisiin1jjij 則則即即若若njxmibxatsxczjinjijijjnjj,2, 1,0,2, 1,.max11線性規(guī)劃問題的最優(yōu)解中，線性規(guī)劃問題的最優(yōu)解中，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，變量比較緊；，變量比較緊；互補(bǔ)松弛定理的解釋互補(bǔ)松弛定理的解釋約束方程約束方程 分為兩種情況：分為兩種情況： , ,約束條件比較松；約束條件比較松； , ,約束條件比較緊約束條件比較緊injjijbxa1injjijbxa1injjijbxa1變量同其對(duì)偶問題的約束方程之間至多只能夠有一個(gè)取松弛的情況，當(dāng)其中一個(gè)取松弛

21、的情況時(shí)，另外一個(gè)比較緊，即取嚴(yán)格等號(hào) 。 例例3.6 已知下面的已知下面的LP1和和LP2為一組對(duì)偶規(guī)劃，且已知為一組對(duì)偶規(guī)劃，且已知LP1的最優(yōu)解為的最優(yōu)解為X=（1.5，1）T。試運(yùn)用互補(bǔ)松弛定理。試運(yùn)用互補(bǔ)松弛定理求出對(duì)偶問題的最優(yōu)解求出對(duì)偶問題的最優(yōu)解Y。解：由解：由X=（1.5，1），得），得55 . 3221 xx01y0, 021xx232342321321yyyyyy聯(lián)立求解得：聯(lián)立求解得：5 . 0, 5 . 0, 0321yyy生產(chǎn)計(jì)劃問題（生產(chǎn)計(jì)劃問題（LP1）資源定價(jià)問題（資源定價(jià)問題（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 影子價(jià)格和靈敏度分析影子價(jià)格和靈敏度分析 3.3.1 影子價(jià)格影子價(jià)格 對(duì)偶變量的經(jīng)濟(jì)含義就是資源的定價(jià)，然而對(duì)偶變量的經(jīng)濟(jì)含義就是資源的定價(jià)，然而這種價(jià)格同市場(chǎng)價(jià)格不同，我們稱之為影子價(jià)格。這種價(jià)格同市場(chǎng)價(jià)格不同，我們稱之為影子價(jià)格。它反映了資源對(duì)于企業(yè)的緊缺程度、利潤貢獻(xiàn)程它反映了資源對(duì)于企業(yè)的緊缺程度、利潤貢獻(xiàn)程度等，并不能反映資源的生產(chǎn)成本，以及在外部度等，并不能反映資源的生產(chǎn)成本，以及在外

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

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

25、對(duì)于原有產(chǎn)品，如果生產(chǎn)的，則其機(jī)會(huì)成本等于利潤。利潤。0jxjmiiijcya10jxjmiiijcya1miiijya1對(duì)于原有產(chǎn)品對(duì)于原有產(chǎn)品j j，其機(jī)會(huì)成本為，其機(jī)會(huì)成本為 在利潤最大化的生產(chǎn)計(jì)劃中在利潤最大化的生產(chǎn)計(jì)劃中 （1）影子價(jià)格大于）影子價(jià)格大于0的資源沒有剩余；的資源沒有剩余； （2）有剩余的資源影子價(jià)格等于）有剩余的資源影子價(jià)格等于0； （3）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤；）安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤； （4）機(jī)會(huì)成本大于利潤的產(chǎn)品不安排生產(chǎn)。）機(jī)會(huì)成本大于利潤的產(chǎn)品不安排生產(chǎn)?？偨Y(jié)3.3.2 靈敏度分析靈敏度分析1、目標(biāo)函數(shù)系數(shù)、目標(biāo)函數(shù)系數(shù)cj變化變化例例 3.

26、7 C由由(3.2)變?yōu)樽優(yōu)?3,1)，請(qǐng)問最優(yōu)生產(chǎn)計(jì)劃如何變化？，請(qǐng)問最優(yōu)生產(chǎn)計(jì)劃如何變化？32000CBXBx1x2x3x4x5b000 x3x4x512421310001000154932000032000CBXBx1x2x3x4x5b032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/211114 5初初始始表表最最優(yōu)優(yōu)表表z解：由原最優(yōu)單純形表得：解：由原最優(yōu)單純形表得：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 所以原最優(yōu)解不是新問題的最優(yōu)解所以原最優(yōu)解不是新問題的最優(yōu)解 單純形迭代得：?jiǎn)渭冃蔚茫?1000bCBxBx1x2x3x4x50 x30 3/21 -1/2033x11 1/20 1/2020 x50 10 -21 1 0 -1/20- 3/206所以得到新的最優(yōu)生產(chǎn)計(jì)劃為產(chǎn)品所以得到新的最優(yōu)生產(chǎn)計(jì)劃為產(chǎn)品I生產(chǎn)生產(chǎn)2件，件，產(chǎn)品產(chǎn)品II不生產(chǎn)，此時(shí)總利潤上升為不生產(chǎn)，此時(shí)總利潤上升為6萬元。萬元。例例3.8 假設(shè)產(chǎn)品假設(shè)產(chǎn)品II的價(jià)格不變，請(qǐng)問產(chǎn)品的價(jià)格不變，請(qǐng)問產(chǎn)品I的利潤在什的利潤在什么范圍內(nèi)波動(dòng)時(shí)，最優(yōu)生產(chǎn)計(jì)

28、劃不變？么范圍內(nèi)波動(dòng)時(shí)，最優(yōu)生產(chǎn)計(jì)劃不變？ 41 32 512欲使最優(yōu)生產(chǎn)計(jì)劃不變，須欲使最優(yōu)生產(chǎn)計(jì)劃不變，須02102311313解：假設(shè)解：假設(shè)c1由由3變?yōu)樽優(yōu)?，則，則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所以所以,當(dāng)當(dāng)-1/3,1,即即c1 8/3,4時(shí)時(shí),最優(yōu)生產(chǎn)計(jì)劃不變最優(yōu)生產(chǎn)計(jì)劃不變最優(yōu)解保持不變的最優(yōu)解保持不變的C變化范圍變化范圍但要分兩種情況討論。只影響最優(yōu)性時(shí)變?yōu)閮r(jià)格,ccc即可。故只要，為因只影響自己的檢驗(yàn)數(shù)的價(jià)格系數(shù)是

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

30、0-1/2-1/213/25b1 b2 b3 z初初始始表表最最優(yōu)優(yōu)表表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因?yàn)橐驗(yàn)閤2=-10，所以令其，所以令其岀岀基?；?。minbi/bi0=brl檢驗(yàn)數(shù)所在行除以出基變量所在行，商最小的列對(duì)應(yīng)的檢驗(yàn)數(shù)所在行除以出基變量所在行，商最小的列對(duì)應(yīng)的元素作為主元素元素作為主元素min /arj ,arj0 。這里。這里正數(shù)和零不能正數(shù)和零不能作為主元素作為主元素 。l本題中第三行只有本題中第三行只有a34=-20，所以選為主元素，進(jìn)行對(duì)偶，所以選為主元素，進(jìn)行對(duì)偶迭代迭代l迭代的目標(biāo)：迭代的目標(biāo)：