運(yùn)籌學(xué)第二章__線性規(guī)劃的對偶理論(新)a管理精品資料課件

1、第二章 線性規(guī)劃的對偶理論第一節(jié) 對偶問題的提出資源利用問題:原問題： max z=2x1+3x2 s.t 2x1+2x212 y1 0 4x1 16 y2 0 5x215 y3 0 x10 x20對偶問題： min w=12y1+16 y2 +15y3 s.t 2y1+ 4y2 +0y3 2 2y1+ 0y2 +5y3 3 y1, y2 , y3 0 顯然，只有當(dāng)max z= min w時(shí)，該經(jīng)理認(rèn)為這兩種方案具有相同的結(jié)果，都是最優(yōu)方案。推廣到一般情況，可得：原問題： max z=c1x1 +c2x2 + cnxn s.t a11x1+ a12x2 + a1nxn b1 a21x1+ a2

2、2x2 + a2nxn b2 am1x1+ am2x2 + amnxnbm x1 ,x2 , , xn 0 對偶問題： min w=b1y1 +b2y2 + bmym s.t a11y1+ a21y2 + am1ym c1 a12y1+ a22y2 + am2ym c2 . a1ny1+ a2ny2 + amnym cn y1 ,y2 , , ym 0 以上為標(biāo)準(zhǔn)對應(yīng)關(guān)系。（見表2-1)代數(shù)形式：矩陣形式： 原問題 對偶問題第二節(jié) 原問題與對偶問題的一般對應(yīng)關(guān)系例1、例2.結(jié)論：LP對偶問題的對偶問題就是原問題。例3. 寫出下列LP的對偶問題 原問題： min z=7x1+ 4x2 -3x3

3、s.t - 4x1+ 2 x2 - 6x3 24 y1 0 -3x1+ x2 +2x3 15 y2 0 5x2 +3x3 = 30 y3 無約束 2x1- 2x2 +4x3 -1 y4 0 x1 0 , x2取值無約束，x30 對偶問題： max z=24y1+ 15y2 +30y3 - 10y4 s.t - 4y1- 3y2 + 0y3 + 2y4 7 2y1+ y2 + 5y3 2y4 = 4 - 6y1+ 2y2 + 3y3 + 4y4 -3 y1 0 , y20, y3無約束,y40 原問題與對偶問題的一般對應(yīng)關(guān)系見表2-2。作業(yè)：P78 2.1(b)(c) 2.2 2.4第三節(jié) 對偶

4、問題的基本性質(zhì) 原問題 對偶問題定理1.（弱對偶性定理） 若X，Y分別為LP原問題及其對偶問題的可行解，則恒有： CXYb證明：對AX b，兩端同時(shí)左乘可行解Y,得： YAX Yb ； 對YA C, 兩端同時(shí)右乘可行解X,得： YAX CX,從而得： CXYb 證畢。定理2.（最優(yōu)性定理）若X，Y分別為LP原問題及其對偶問題的可行解，且有： CX=Yb則X，Y分別為LP原問題及其對偶問題的最優(yōu)解。 （充要條件）證明：（充分性）設(shè)X* 為LP原問題的最優(yōu)解，設(shè)Y* 為LP對偶問題的最優(yōu)解，由弱對偶性定理知： 又已知 故又有：因此X ，Y分別為LP原問題及其對偶問題的最優(yōu)解。（必要性：CBB-1b

5、）定理3.（無界性） 如果原問題（或?qū)ε紗栴}）有無界解，則其對偶問題（或原問題）無可行解。如果原問題（或?qū)ε紗栴}）無可行解，則其對偶問題（或原問題）或是無可行解或是無界解。 原問題 對偶問題 最優(yōu)解 最優(yōu)解 無界解 無可行解 無可行解 無界解定理4. （對偶定理） 若原問題有最優(yōu)解，則其對偶問題也一定有最優(yōu)解，且它們的最優(yōu)目標(biāo)函數(shù)值相等。證明：設(shè)X*是LP的最優(yōu)解，它所對應(yīng)的基為B，則檢驗(yàn)數(shù)必滿足： = CCBB-1A0令Y=CBB-1 (單純形因子) ,則有：YA C，因此，Y是對偶問題的可行解。 又知LP的最優(yōu)目標(biāo)函數(shù)值為： z*= CX*= CBB-1b =Yb=w 由最優(yōu)性定理（定理2

6、）可知， Y=CBB-1是對偶問題的最優(yōu)解。定理5. (互補(bǔ)松弛定理） 原問題及其對偶問題的可行解是最優(yōu)解的充要條件是：證明： （必）由化成標(biāo)準(zhǔn)形式：因此可得：若 和 分別是原問題和對偶問題的可行解，且 則必有: z = w 由最優(yōu)性定理可知 和 分別為原問題和對偶問題的最優(yōu)解。 （充）因?yàn)?和 分別為原問題和對偶問題的最優(yōu)解，故：從而：又：故必有：定理6. (解的對應(yīng)關(guān)系) 在同一步迭代中（同一個(gè)單純形表中），LP原問題的檢驗(yàn)數(shù)對應(yīng)于對偶問題的一個(gè)解，且目標(biāo)函數(shù)值相等（z=w)。其對應(yīng)關(guān)系為： 原問題 對偶問題 決策變量X 松弛變量YS 松弛變量XS 決策變量Y 基變量XB 非基變量YN 非

7、基變量XN 基變量YB證明: (1)由得：或?qū)懗桑涸瓎栴}的檢驗(yàn)數(shù)為： ( X , XS )=( CCBB-1A ， CBB-1 ) ( -YS , -Y )(2)由LP模型的矩陣表達(dá)式：寫出其對偶問題： （XB, XN, XS ）=( 0， N ， S ) =( 0， CNCBB-1N， CBB-1 ) =( -YS1, -YS2, -Y )Cj CB CN 0CBXBb XB XN XSCBXBB-1b I B-1N B-1 j=cj-zj 0 CN - CBB-1N - CBB-1Cj CB CN 0CBXBb XB XN XS 0XSb B N I j=cj-zj CB CN 0 結(jié)論：

8、 LP原問題的檢驗(yàn)數(shù)的相反數(shù)是其對偶問題的一個(gè)解。 在最優(yōu)條件下， = (CCBB-1A) 0其相反數(shù)則為對偶問題的一個(gè)可行解，且z = w 。此時(shí)， Y=CBB-1 是對偶問題的最優(yōu)解。補(bǔ)充例4.已知LP問題 max z=6x1+ 14x2 +13x3 (1/2)x1+ 2x2 + x324 y1 x1+ 2x2 +4x360 y2 x1 ， x2 ，x30最終表為： （ x4 ，x5 為松弛變量）原問題的解為： X=(36，0，6，0，0)T對偶問題的解為： Y=（11，1/2，0，9，0）最優(yōu)值為： max z= 636+136 =294 min w=2411+60(1/2)=294Cj

9、 6 14 13 0 0CBXBb x1 x2 x3 x4 x5 613x1x336 6 1 6 0 4 -1 0 -1 1 -1 1/2= cj-zj 0 -9 0 -11 -1/2 例3. 對本章的兩個(gè)互為對偶的LP數(shù)學(xué)模型，將其分別化為標(biāo)準(zhǔn)形式： (注：= zj-cj ) 原問題： max z=2x1+3x2 s.t 2x1+2x2+x3 =12 y1 0 4x1 +x4 =16 y2 0 5x2 +x5=15 y3 0 x1, x2, x3, x4, x50對偶問題： min w=12y1+16 y2+15y3 s.t 2y1+ 4y2 +0y3-y4 = 2 x10 2y1+ 0y2

10、 +5y3 -y5= 3 x20 y1, y2 , y3 , y4 , y50 對偶問題： max w=-12y1-16 y2-15y3 s.t -2y1- 4y2- 0y3+y4 =-2 x10 -2y1- 0y2- 5y3 +y5=-3 x20 y1, y2 , y3 , y4 , y50 兩個(gè)問題的最終單純形表及變量對應(yīng)關(guān)系分別見表2-3和2-4。補(bǔ)充例5. 已知LP原問題為 max z=1x1+ 2x2 + 3x2 +4x2 1x1+ 2x2 + 2x3 +3x420 y1 2x1+ 1x2 + 3x3 +2x420 y2 xj0 (j=1,2,3,4) 若其對偶問題的最優(yōu)解為Y=（1

11、.2，0.2），求原問題的最優(yōu)解和最優(yōu)值。解：1.寫出對偶問題。2.結(jié)合松緊定理計(jì)算。3.max z=min w=201.2+200.2=28根據(jù)互補(bǔ)松弛定理，在最優(yōu)情況下將上述結(jié)果，代入原問題的約束方程，得二元線性方程組解得所以原問題的最優(yōu)解為 ，相應(yīng)的最大值Z=28。原問題與對偶問題解的對應(yīng)關(guān)系：第四節(jié) 影子價(jià)格 （LP模型計(jì)算結(jié)果的經(jīng)濟(jì)解釋） 在最優(yōu)條件下，原問題和對偶問題的目標(biāo)函數(shù)分別是： max z=c1x1 +c2x2 + cnxn =min w=b1y1 +b2y2 + bmym對xj、bi求偏導(dǎo)數(shù)得：例3. 對以下（第一章例2）的LP數(shù)學(xué)模型標(biāo)準(zhǔn)形式： max z=2x1+3x

12、2 s.t 2x1+2x2+x3 =12 y1 0 4x1 +x4 =16 y2 0 5x2 +x5=15 y3 0 x1, x2, x3, x4, x50初始表和最終表見下：cj 2 3 0 0 0CBXBb x1 x2 x3 x4 x5000 x3x4x5121615 2 2 1 0 0 4 0 0 1 0 0 (5) 0 0 112/215/5*cj-zj0 2 3 0 0 0203x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj -15 0 0 -1 0 -1/5最優(yōu)解 X =(3，3，0，4)T。最優(yōu)值 max z=1

13、5X =(3，3，0，4，0)T。 最優(yōu)值 z=15b1 =13時(shí)，X1=(7/2，3，0，2，0)T z1=16 z1-z=16-15=1 (= y1)b2 =17時(shí)，X1=(3，3，0，5，0)T z1=15 z1-z=15-15=0 (= y2)b3=16時(shí)， X1=(14/5，16/5，0，34/5，0)T z1=76/5 z1-z=76/5-75/5=1/5 (= y3) （見圖2-1）影子價(jià)格：某稀缺資源每增加一個(gè)單位時(shí)給目標(biāo)函數(shù)帶來的變化量，它反映了資源的稀缺程度，也反映了局部或個(gè)體的經(jīng)濟(jì)活動(dòng)對整體經(jīng)濟(jì)效果的影響。幾點(diǎn)說明：1.說明資源的稀缺程度（互補(bǔ)松弛定理）；2.影子價(jià)格與生

14、產(chǎn)價(jià)格是兩個(gè)不同的概念；3.影子價(jià)格是一個(gè)動(dòng)態(tài)的、局部（或微觀）的經(jīng)濟(jì)尺度（系統(tǒng)觀點(diǎn)）；4.邊際價(jià)格；5.影子價(jià)格的確定方法。影子價(jià)格的作用：1.輔助決策2.專業(yè)化協(xié)作3.使資源得到合理利用。作業(yè)：P79 2.6（a) 第五節(jié) 對偶單純形法 對偶單純形法就是將單純形法用于對偶問題。 對偶單純形法的基本思想：在保持對偶問題為可行解的基礎(chǔ)上（這時(shí)原問題一般為非可行解），通過迭代，減少目標(biāo)函數(shù)，當(dāng)原問題也達(dá)到可行解時(shí)，即得到目標(biāo)函數(shù)最優(yōu)值。 可用表2-5說明。例5.用對偶單純形法求解下列LP問題： min w=12y1+16 y2+15y3 s.t 2y1+ 4y2 +0y3-y4 = 2 x10

15、2y1+ 0y2 +5y3 -y5= 3 x20 y1, y2 , y3 , y4 , y50 解：將模型化為標(biāo)準(zhǔn)形式 max w=-12y1-16 y2-15y3 s.t -2y1- 4y2- 0y3+y4 =-2 x10 -2y1- 0y2- 5y3 +y5=-3 x20 y1, y2 , y3 , y4 , y50 列表求解：原問題最優(yōu)解： Y=(1，0，1/5，0，0)對偶問題最優(yōu)解： X=(3，3，0，4，0)T 最優(yōu)值： min w= - max(w) = -(-12)1+(-15)1/5=15或max z= -(-2)3+(-3)3=15（作業(yè)：P79 2.8 2.9 ）第六節(jié)

16、靈敏度分析靈敏度分析：系統(tǒng)或事物由于環(huán)境條件發(fā)生變化而顯示出來的敏感程度的分析。 在前面的討論中，都假設(shè)了模型中的參數(shù)aij、bi、cj是常數(shù)，但是實(shí)際上由于這些數(shù)字是一些估計(jì)或預(yù)測的數(shù)字，往往隨外界情況的變化而變化。因此，就要考慮如下的問題：1. 當(dāng)參數(shù)aij、bi、cj在什么范圍內(nèi)變化時(shí)，才不致影響原問題的最優(yōu)解和最優(yōu)值？2. 當(dāng)參數(shù)aij、bi、cj的變化超出了最優(yōu)值要求的范圍時(shí)，新的最優(yōu)解和最優(yōu)值是什么？ 這就是靈敏度分析和參數(shù)線性規(guī)劃所要解決的問題。 從數(shù)學(xué)上來看，靈敏度分析和參數(shù)線性規(guī)劃就是研究LP問題最優(yōu)解的穩(wěn)定性。 由矩陣關(guān)系式可知，當(dāng)模型（或初始表）中的參數(shù)發(fā)生變化時(shí)，不必從

17、頭計(jì)算，只需將變化后的參數(shù)利用最終表中的B-1直接反映到最終表中，然后看最終表的最優(yōu)性是否受到影響，若最優(yōu)性受到影響，則繼續(xù)迭代，求新的最優(yōu)解和最優(yōu)值即可。靈敏度分析的步驟: (P65)1. 將參數(shù)的改變通過矩陣計(jì)算反映到最終表中（見矩陣關(guān)系式）；2. 檢查原問題是否可行解；3. 檢查對偶問題是否可行解；4. 按以下原則得出結(jié)論或決定繼續(xù)計(jì)算的步驟。Cj CB CN 0CBXBb XB XN XS 0XSb B N I j=cj-zj CB CN 0Cj CB CN 0CBXBb XB XN XSCBXBB-1b I B-1N B-1 j=cj-zj 0 CN - CBB-1N - CBB-1

18、 . 6-1 分析cj變化時(shí)，對最優(yōu)值的影響 由矩陣關(guān)系式可知，cj的變化僅僅影響到檢驗(yàn)數(shù) =(0， N ， S ) =(0， CNCBB-1N， CBB-1 ) 1.當(dāng)cj是非基變量系數(shù)時(shí)，cj的變化只影響非基變量xj的檢驗(yàn)數(shù)；2.當(dāng)cj是基變量系數(shù)時(shí)， cj的變化就會(huì)影響所有非基變量的檢驗(yàn)數(shù)。下面分別討論。1.設(shè)cj是非基變量xj的目標(biāo)函數(shù)系數(shù) 當(dāng)cj， =cj +（ 是變化量）時(shí)，要保證在最終表中j，0，應(yīng)有： j， cj，- CBB-10 cj，CBB-1或： j， cj + - CBB-1 j + 0 即 j （注：j 0）用單純形法求解下列LP問題的結(jié)果見下頁 以上例中的c3為例。

19、由于c3是非基變量x3的價(jià)值系數(shù)，因此c3的變化只影響到檢驗(yàn)數(shù)3，所以c3的變化，只要能保持30，則最優(yōu)解不變?，F(xiàn)在將c3作為參數(shù)，討論c3在什么范圍內(nèi)變化，才能保持30 。由上表的最終表知： 這說明，只要產(chǎn)品A3的單位銷售價(jià)不大于50元，最優(yōu)解不變，即還是按原最優(yōu)計(jì)劃安排生產(chǎn)。2.設(shè)cr是基變量xr的目標(biāo)函數(shù)系數(shù) 此時(shí)， cr CB，所以 cr的變化就會(huì)影響所有非基變量的檢驗(yàn)數(shù)。 當(dāng)cr， =cr +（ 是變化量）時(shí)，要保證在最終表中j，0，應(yīng)有： j，cj - CB，B-1cj - （CB +（0，0， ， ，0）B-1cj - CBB-1 arj，j arj，0 （j=1,2,n) 或

20、arj， j (arj，是最終表中基變量xr行非零的約束系數(shù)）即例6. 已知LP問題 max z=(2+1) x1 +(3 +2) x2 s.t 2x1+2x212 4x1 16 5x215 x10 x20 試分別分析1，2在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)解不變。解：1=2=0時(shí)的最終表為：cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj -15 0 0 -1 0 -1/51. 當(dāng)2=0時(shí)，將1的變化直接反映到最終表中(表2-9)。為使表中的解仍為最優(yōu)解，應(yīng)有

21、例：若c1=4，求新的最優(yōu)解，最優(yōu)值。解：將c1的變化直接反映到最終表中。cj 4 3 0 0 0CBXBb x1 x2 x3 x4 x5403x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 -2 1 (4/5) 0 1 0 0 1/54/(4/5)3/(1/5)cj-zj -21 0 0 -2 0 1/5403x1x5x2 4 5 2 1 0 0 1/4 0 0 0 -5/2 5/4 1 0 1 1/2 -1/4 0cj-zj -22 0 0 -3/2 -1/4 0新的最優(yōu)解為 X=(4，2，0，0，5)T，最優(yōu)值為 max z= 44+ 32 =226-2 資源數(shù)量bi變化

22、的影響 由矩陣關(guān)系式b，=B-1b和z = CB B-1b 可知，bi的的變化僅僅影響到最終表中常數(shù)項(xiàng)列數(shù)字和目標(biāo)函數(shù)值z的變化，此時(shí)，原問題檢驗(yàn)數(shù)不受影響（即對偶問題保持可行），只需檢查原問題是否可行即可。例7. 已知LP問題 max z=2x1 + 3 x2 s.t 2x1+2x212+1 4x1 16+2 5x215+3 x10 x20 分別分析1，2 ,3在什么范圍內(nèi)變化時(shí)，問題的最優(yōu)解不變。解：先分析1的變化。當(dāng)2 =3=0時(shí)的最終表為：cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5000 x3x4x5121615 2 2 1 0 0 4 0 0 1 0 0 5

23、0 0 1cj-zj 0 2 3 0 0 0cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj -15 0 0 -1 0 -1/5cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x23+(1/2)1 4-21 3 1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj-15-1 0 0 -1 0 -1/5要保持上述基仍為最優(yōu)基，應(yīng)有： 3+(1/2)10， 4-210解得：-612，或： 6 b

24、114 同理可推得：-42 ，或： 12b2 -5315，或： 10b330 例：設(shè)b1=20，求新的最優(yōu)解，最優(yōu)值。解：將b1的變化直接反映應(yīng)到最終表中(1=8)。cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x2 7-12 3 1 0 1/2 0 -1/5 0 0 (-2) 1 4/5 0 1 0 0 1/5cj-zj-23 0 0 -1 0 -1/5203x1x3x2 4 6 3 1 0 0 1/4 0 0 0 1 -1/2 -2/5 0 1 0 0 1/5cj-zj -17 0 0 0 -1/2 -3/5新的最優(yōu)解為 X=(4，3，6，0，0)T，最優(yōu)

25、值為 max z= 24+ 33 =176-3 增加一個(gè)變量的分析 增加一個(gè)變量相當(dāng)于增加一種新的產(chǎn)品，是否生產(chǎn)這種產(chǎn)品關(guān)鍵是看它的檢驗(yàn)數(shù)是否大于零。因此，分析步驟是：1. 計(jì)算新增變量xj的檢驗(yàn)數(shù) j cj - CBB-12. 若j0 ，則原最優(yōu)解不變；若j 0，則轉(zhuǎn)3;3. 計(jì)算Pj，= B-1,再按單純形法繼續(xù)迭代。 例8. 在第一章例2中，增加一個(gè)變量x6，且c6=4， P6 =(2，4，5)T,試分析最優(yōu)解的變化。解： 6=c6 - CBB-16 =4-(1，0，1/5)(2，4，5)T =4 - 3=1 因檢驗(yàn)數(shù)6 0 ，故將有關(guān)參數(shù)反映到最終單純形表中，用單純形法繼續(xù)計(jì)算。cj

26、2 3 0 0 0 4CBXB b x1 x2 x3 x4 x5 x6203x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 0 -2 1 4/5 (4) 0 1 0 0 1/5 14/4*3/1cj-zj-15 0 0 -1 0 -1/5 1243x1x6x2 3 1 2 1 0 1/2 0 -1/5 0 0 0 -1/2 1/4 1/5 1 0 1 1/2 -1/4 0 0cj-zj -16 0 0 -1/2 -1/4 -2/5 0新的最優(yōu)解為X=(3，2，0，0，0，1)T,最優(yōu)值為max z=23+32+41=166-4 增加一個(gè)約束條件的分析 增加一個(gè)約束條件，相當(dāng)于增

27、添了一道工序或資源限制。分析步驟：1. 將原來問題的最優(yōu)解代入這個(gè)新增的約束條件之中。若滿足，則說明新約束條件不形成限制，否則轉(zhuǎn)下一步；2. 將新增約束條件直接反映到最終表中，再進(jìn)行分析。例9. 在第一章例2中，增添一個(gè)約束條件 3x1+2x214試分析最優(yōu)解的變化。解：1. 將原問題的最優(yōu)解代入新約束得： 33+23=15 14不滿足。 將新增約束加上松弛變量x6后寫成 ： 3x1+2x2+x6=14 直接反映到最終表中，并將基矩陣化為單位矩陣。這時(shí)，原問題成為非可行解，故用對偶單純形法繼續(xù)迭代。cj 2 3 0 0 0 0CBXB b x1 x2 x3 x4 x5 x62030 x1x4x

28、2x6 3 4 314 1 0 1/2 0 -1/5 0 0 0 -2 1 4/5 0 0 1 0 0 1/5 0 3 2 0 0 0 1cj-zj-15 0 0 -1 0 -1/5 02030 x1x4x2x6 3 4 3 -1 1 0 1/2 0 -1/5 0 0 0 -2 1 4/5 0 0 1 0 0 1/5 0 0 0 (-3/2) 0 1/5 1cj-zj-15 0 0 -1 0 -1/5 0cj 2 3 0 0 0 4CBXB b x1 x2 x3 x4 x5 x62030 x1x4x2x3 8/316/3 3 2/3 1 0 0 0 -2/15 1/3 0 0 0 1 8/15

29、 -4/3 0 1 0 0 1/5 0 0 0 1 0 -2/15 -2/3cj-zj-43/3 0 0 0 0 -1/3 -2/3新的最優(yōu)解為X=(8/3，3，2/3，16/3，0，0)T,最優(yōu)值為max z=2(8/3)+33=43/36-5 約束系數(shù)aij變化的影響（補(bǔ)） 假如xj在最終表中為非基變量，則aij的變化將使最終表中xj的檢驗(yàn)數(shù)j發(fā)生變化，若j0,則用單純形法繼續(xù)計(jì)算。 假如xj在最終表中為基變量，則aij的變化將使最終表中的B-1發(fā)生變化，因此有可能出現(xiàn)原問題和對偶問題均為非可行解的情況，此時(shí)，須引入人工變量，將原問題轉(zhuǎn)化為可行解，再用單純形法繼續(xù)計(jì)算。Cj CB CN 0

30、CBXBb XB XN XS 0XSb B N I j=cj-zj CB CN 0Cj CB CN 0CBXBb XB XN XSCBXBB-1b I B-1N B-1 j=cj-zj 0 CN - CBB-1N - CBB-1 . 例. 已知LP問題 max z=2x1+x2 s.t. 5x215 6x1+2x224 x1+ x25 x10 x20 最終表為：最優(yōu)解為X=（7/2，3/2，15/2，0，0）T ,最優(yōu)值為max z=2(7/2)+1(3/2)=17/2=8.5若c2=3，P2 =（8，4，1）T,試分析最優(yōu)解的變化。解：2 = c2 - CBB-12 =3（0，1/4，1/2

31、）（8，4，1）T =3（3/2）=3/2 0 將有關(guān)參數(shù)反映到最終單純形表中。 對表中的第一個(gè)約束，可寫成： x3+ 4x4 24x5 =9兩端同乘（1），再加上人工變量x6得： x3 4x4 24x5 x6 9用上式替換表中的第一個(gè)約束，得表2-19，因5 0 ，故用單純形法繼續(xù)迭代。新的最優(yōu)解為X=（11/4，15/8，0，0，3/8，0）T，最優(yōu)值為max=2(11/4)+3(15/8)=89/8P80 2.10(d)第七節(jié) 參數(shù)線性規(guī)劃靈敏度分析：研究使問題的最優(yōu)解或最優(yōu)基保持不變時(shí)的參數(shù)值變化范圍。參數(shù)線性規(guī)劃：研究線性規(guī)劃中的參數(shù)aij，cj，bi超出靈敏度分析的范圍而連續(xù)變化時(shí)

32、，最優(yōu)解的變化情況。參數(shù)線性規(guī)劃要求： 當(dāng)問題中有多個(gè)參數(shù)變化時(shí)，應(yīng)使目標(biāo)函數(shù)z()是的線性函數(shù)。例如：（1）當(dāng)有多個(gè)bi值變動(dòng)時(shí)，可將常數(shù)項(xiàng)寫為bi=bi+i，式中i可以是任意的實(shí)數(shù)；（2）當(dāng)有多個(gè)cj值變動(dòng)時(shí)，可將目標(biāo)函數(shù)系數(shù)寫為cj=cj+j，式中j可以是任意的實(shí)數(shù)。求解參數(shù)線性規(guī)劃的步驟：1.令=0，求解原來問題的最終單純形表；2.將參數(shù)的變化反映到最終表中去；3.讓逐步增加（或減少），觀察原問題和對偶問題解的變化，看哪一個(gè)首先出現(xiàn)非可行解，用單純形法或?qū)ε紗渭冃畏ɡ^續(xù)迭代，確定的范圍。例10. 求解以下參數(shù)線性規(guī)劃問題 max z()=(2+2) x1 +(3 +) x2 s.t 2

33、x1+2x212 4x1 16 5x215 x10 x20解：=0時(shí)的最終表為：將參數(shù)的變化反映到最終表中（表2-16）cj 2 3 0 0 0CBXB b x1 x2 x3 x4 x5203x1x4x2 3 4 3 1 0 1/2 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5cj-zj -15 0 0 -1 0 -1/5cj2+2 3+ 0 0 0CBXB b x1 x2 x3 x4 x52+203+x1x4x2 3 4 3 1 0 (1/5) 0 -1/5 0 0 -2 1 4/5 (-11） 0 1 0 0 1/5cj-zj -15-9 0 0 -1- 0 -1/5+(

34、1/5) 當(dāng)-1時(shí)，可將x3作為換入變量進(jìn)行單純形迭代，得表2-17。cj2+2 3+ 0 0 0CBXB b x1 x2 x3 x4 x5003+x3x4x2 616 3 2 0 1 0 -2/5 4 0 0 1 0 (-3-1） 0 1 0 0 (1/5)cj-zj -9-32+2 0 0 0 -3/5-(1/5) 000 x3x4x5 12 16 15 2 2 1 0 0 4 0 0 1 0 (-3） 0 5 0 0 1cj-zj 02+2 3+ 0 0 0當(dāng)1時(shí)，可將x5作為換入變量進(jìn)行單純形迭代，得表2-18。cj2+2 3+ 0 0 0CBXB b x1 x2 x3 x4 x52+203+x1x5x2 4 5 2 1 0 0 1/4 0 0 0 -5/2 5/4 1(1) 0 1 1/2 -1/4 0cj-zj-14-10 0 0 -3/2-(1/2)