運(yùn)籌學(xué)課件 6

1、第 二 章線性規(guī)劃對(duì)偶理論與靈敏度分析,教學(xué)時(shí)數(shù)：12學(xué)時(shí)教學(xué)目的與要求：理解線性規(guī)劃對(duì)偶問(wèn)題理論與影子 價(jià)格概念,掌握對(duì)偶單純形法及靈敏度分析技巧教學(xué)內(nèi)容：1.線性規(guī)劃對(duì)偶問(wèn)題及相關(guān)理論2.影子價(jià)格3.對(duì)偶單純形法4.靈敏度分析及參數(shù)規(guī)劃教學(xué)重點(diǎn)：影子價(jià)格及靈敏度分析教學(xué)難點(diǎn)：對(duì)偶理論,第二章 線性規(guī)劃對(duì)偶理論與靈敏度分析講授內(nèi)容,第一節(jié) 線性規(guī)劃的對(duì)偶問(wèn)題,解：利用第一章的知識(shí)，設(shè)三種產(chǎn)品的生產(chǎn)量分

2、別為x1， x2和 x3 ，可以建立線性規(guī)劃模型如下:,一、對(duì)偶問(wèn)題的提出,假如企業(yè)不進(jìn)行生產(chǎn)，而是把全部可利用的資源轉(zhuǎn)讓給其他企業(yè)。此時(shí)，企業(yè)必須考慮一個(gè)合適的資源價(jià)格，使得：1.有企業(yè)愿意接受轉(zhuǎn)讓；2.企業(yè)自身沒有經(jīng)濟(jì)損失。,設(shè)四種資源的價(jià)格確定為 y1, y2 , y3 , y4 。,,y1,y2,y3,y4,而企業(yè)自身沒有經(jīng)濟(jì)損失的要求可做如下思考：生產(chǎn)一件產(chǎn)品，比如A，需要四種資源的量分別為3，2，1，1個(gè)單位。由于要

3、把生產(chǎn)A 產(chǎn)品的這些資源賣出去，所以，單件總賣值不應(yīng)比企業(yè)自己生產(chǎn)時(shí)的收益（2000）低，即， 3 y1 + 2 y2 + y3 + y4 ≥2000 對(duì)產(chǎn)品B：4 y1 + y2 + 3 y3 + 2 y4 ≥ 4000 對(duì)產(chǎn)品C ：2 y1 + 2 y2 +3 y3 +4 y4 ≥3000,則有企

4、業(yè)愿意接受轉(zhuǎn)讓的條件是極小化資源總價(jià)，即 w =600 y1+ 400 y2 + 300 y3 + 200 y4,原問(wèn)題,對(duì)偶問(wèn)題,兩個(gè)線性規(guī)劃問(wèn)題的比較中，可以初步發(fā)現(xiàn)：原問(wèn)題的目標(biāo)函數(shù)求極大， 對(duì)偶問(wèn)題的目標(biāo)函數(shù)求極小；原問(wèn)題目標(biāo)函數(shù)中的系數(shù) 在

5、對(duì)偶問(wèn)題中變?yōu)榧s束條件的右端常數(shù)項(xiàng)；約束條件的不等式方向改變了；約束方程的系數(shù)矩陣發(fā)生了轉(zhuǎn)置；原問(wèn)題約束數(shù)目與對(duì)偶問(wèn)題的變量數(shù)相等。,對(duì)稱形式的條件： （1）變量全部具有非負(fù)約束； （2）目標(biāo)函數(shù)求極大值時(shí)，約束不等式符號(hào)全

6、部為≤；目標(biāo)函數(shù)為求極小值時(shí)，約束不等式的符號(hào)全部為≥。,對(duì)偶問(wèn)題的一般形式為：,二、對(duì)稱形式的原始-對(duì)偶關(guān)系,,Y=(y1,y2,…,ym)′,說(shuō)明：表 2的變量行與參數(shù)行相乘組成原始問(wèn)題的約束條件和目標(biāo)函數(shù)；表2 的變量列與參數(shù)列相乘組成對(duì)偶問(wèn)題的約束條件和目標(biāo)函數(shù)。,,600,400,300,200,2000,4000,3000,≥0,非對(duì)稱形式是指一般情況下的線性規(guī)劃問(wèn)題，是目標(biāo)函數(shù)求極小或求極大；約束條件≥、=、≤；變量≥0、

7、≤0或者無(wú)限制的隨意組合。,建立非對(duì)稱形式線性規(guī)劃問(wèn)題的對(duì)偶模型可采取以下步驟： （1）通過(guò)變換，把線性規(guī)劃問(wèn)題化為具有對(duì)稱形式的原問(wèn)題。

8、 （2）根據(jù)原問(wèn)題，寫出對(duì)偶問(wèn)題。（此時(shí)的對(duì)偶并非是原線性規(guī)劃問(wèn)題的對(duì)偶） （3）通過(guò)變量代換等，把參數(shù)還原為最初的形式（必須做）。,三、非對(duì)稱形式的原始-對(duì)偶問(wèn)題,解：（1）把原線性規(guī)劃問(wèn)題化為對(duì)稱形式要

9、求的形狀——目標(biāo)函數(shù)求極大；約束條件全部為“≤”符號(hào)；變量全部非負(fù)。,第一個(gè)約束條件的符號(hào)符合要求，保留不變。 第二個(gè)約束條件分解為： x1－ x2 + x3 ≥ 1 和 x1－ x2 + x3 ≤ 1第一個(gè)

10、分解式乘以 - 1 變?yōu)?- x1+ x2 － x3 ≤ - 1 第三個(gè)約束條件乘以-1 得： -2x1－ x2 － x3 ≤- 2,,（2）寫出上述對(duì)稱形式線性規(guī)劃問(wèn)題的對(duì)偶。,,（3）還原為原來(lái)的參數(shù)符號(hào),令 u1 = y1 , u2 = - y2 + y3 , u3 = - y

11、4,u1,u2,u3,四、原始-對(duì)偶關(guān)系一覽表,解：根據(jù)表3，得出對(duì)偶線性規(guī)劃問(wèn)題如下：,max w =2 y1 + y2 +4 y3,st.,,2 y1 + 3 y2 + y3 ≥ 1 3 y1 － y2 + y3 ≤ 4 y1

12、 + y3 = 3 y1 ≥ 0, y2 ≤0, y3自由變量.,,課堂練習(xí),第二節(jié) 對(duì)偶問(wèn)題的基本性質(zhì),本節(jié)以對(duì)稱形式的原始-對(duì)偶問(wèn)題為討論的基礎(chǔ)，除非特別需要，一般不再專門說(shuō)明。,一、單純形法計(jì)算的矩陣描述,原問(wèn)題通過(guò)加入松弛變量 Xs 可以化為標(biāo)準(zhǔn)形式：,其中，I 是對(duì)應(yīng)于松弛變量的單位方陣。,,單純形法計(jì)算時(shí)，總是選擇 I 為初始可行

13、基，松弛變量作為初始基變量的。由于松弛變量作為基變量意味著資源沒有被利用，所以，單純形法迭代若干步后，松弛變量會(huì)被置換出基變量集合。,,項(xiàng) 目,0 Xs b,非基變量,基變量,XB XN,Xs,B N,I,檢驗(yàn)數(shù),CB CN,0,設(shè)新的基變量組合為XB，在初始單純形表中的系數(shù)矩陣

14、為B，價(jià)值系數(shù)為CB 。A去掉B 的若干列后，剩余的列向量組成子矩陣N，對(duì)應(yīng)的變量組合記為XN ，價(jià)值系數(shù)記為CN 。,CB XB b1,基變量,非基變量,XB,XN Xs,I,,檢驗(yàn)數(shù),,,N1 S1,0,σN σS,Xs,XB,XN,x1x2,B,I,N,I,N1,S1,σN σS,CB

15、 CN,根據(jù)上述劃分，約束方程可改寫為：,B XB + N XN+ I Xs = b,XB = B –1 b － B –1 N XN－ B –1 Xs,代入目標(biāo)函數(shù)中，得,z = max z = CX +0Xs =CB XB + CN XN + 0 Xs = CB (B –1 b － B –1 N XN－ B –1 Xs ) + CN XN + 0 Xs = CB B –1 b － CB B –1 N XN－ CB

16、 B –1 Xs + CN XN + 0 Xs = z0 + ( CN － CB B –1 N ) XN + (0 － CB B –1 ) Xs,式中帶陰影的就是非基變量的檢驗(yàn)數(shù)， z0 對(duì)應(yīng)于當(dāng)前的目標(biāo)函數(shù)值,AX + IXs = b,,( CN － CB B –1 N ),(0－ CB B –1 ),B –1 b,B –1 N,B –1,( CN － CB B –1 N ),-CB B –1,,XB

17、 = （x1，x3）T,XS = （x4，x5）T,XN = x2,B-1N=,B-1=,( CN － CB B –1 N ),-CB B –1,如果表中的檢驗(yàn)數(shù)滿足最優(yōu)性條件，即 CN － CB B –1 N≤0 － CB B –1= CS－ CB B –1 I≤0,由于基變量的

18、檢驗(yàn)數(shù)可以寫為 CB － CB I = CB － CB B–1 B = 0,所以，上述3個(gè)式子可以重寫為 C － CB B –1 A≤0,令 Y'= CB B –1 單純形乘子,A'Y ≥C' Y ≥0,,當(dāng)原問(wèn)題達(dá)到最優(yōu)時(shí)， Y '= CB B –1對(duì)應(yīng)于對(duì)偶問(wèn)題的一個(gè)可行解。將該解代入對(duì)偶問(wèn)題的目

19、標(biāo)函數(shù)，可知w =Y 'b = CB B–1 b = z 。對(duì)偶理論將進(jìn)一步說(shuō)明，對(duì)偶與原始問(wèn)題具有相同的最優(yōu)目標(biāo)函數(shù)值。,XB = B –1 b,Y '= CB B –1,Max z=CX=CB B –1 b,w=Y'b=CB B –1 b,原問(wèn)題的對(duì)偶變量 y1 y2,,,對(duì)偶問(wèn)題的對(duì)偶變量（原問(wèn)題） x1 x2

20、 x3,,,,,,14 4,﹣9 ﹣4,994,14 0 4,性質(zhì)1. 弱對(duì)偶性。如果X 0，Y 0分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解，則 CX 0 ≤Y 0 'b,證明：因?yàn)閄 0，Y 0是可行解,它們滿足約束條件和非負(fù)性限制,,二、對(duì)偶問(wèn)題的基本性質(zhì),A X 0 ≤b X 0 ≥0 (1) A′Y

21、 0 ≥ C ′ Y 0 ≥0 Y0′A≥ C (2) 用Y 0′左乘第一個(gè)不等式， X 0右乘第二個(gè)不等式，得 Y 0' A X 0 ≤ Y 0' b Y 0' A X 0 ≥ C X 0 比較上面兩個(gè)不等式可知，弱對(duì)偶性成立。,推論：（1）原問(wèn)題任一可行解的目標(biāo)函數(shù)值是對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之，對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是原問(wèn)題目

22、標(biāo)函數(shù)值的上界。（2）如果原問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界（無(wú)界解），則對(duì)偶問(wèn)題無(wú)可行解；反之，對(duì)偶問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界，則原問(wèn)題無(wú)可行解。 注意：本性質(zhì)的逆不成立。因?yàn)楫?dāng)對(duì)偶不可行時(shí)，要么原問(wèn)題無(wú)界，要么原問(wèn)題無(wú)可行解。（3）如果原問(wèn)題有可行

23、解，對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題目標(biāo)函數(shù)值無(wú)界；反之，對(duì)偶問(wèn)題有可行解，原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界。,,,maxZ,原問(wèn)題可行解,minW,,,對(duì)偶可行解,114,用途：判斷線性規(guī)劃問(wèn)題有無(wú)最優(yōu)解。因?yàn)樵己蛯?duì)偶問(wèn)題可行解的目標(biāo)函數(shù)值分別是對(duì)偶、原始的下、上界，所以，只要找到原始、對(duì)偶的可行解，就可斷定原始、對(duì)偶問(wèn)題有無(wú)最優(yōu)解 。,,可以看出，原問(wèn)題有可行解，比如X =（1，1，1，1）T，對(duì)偶問(wèn)題有可行解Y=（1，1），

24、所以，原線性規(guī)劃問(wèn)題有最優(yōu)解。,,,性質(zhì)2 . 最優(yōu)性。 如果X 0，Y 0分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解，且有 CX 0 = Y 0' b ， 則X 0，Y 0分別是原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。,證明：設(shè)X＊，Y＊分別是原始問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。 根據(jù)最優(yōu)解的定義知： CX 0 ≤ C X

25、＊ , Y 0' b ≥ Y＊'b。又根據(jù)弱對(duì)偶性， C X＊ ≤ Y＊'b ，所以， C X＊ ≤ Y 0' b = CX 0 ，X 0是原問(wèn)題的最優(yōu)解。同理， C X＊ ≤ Y＊'b ，Y 0 'b = CX 0 ≤ Y＊b，所以，Y 0是對(duì)偶問(wèn)題的最優(yōu)解。,性質(zhì)3 強(qiáng)對(duì)偶性（或?qū)ε级ɡ恚?

26、 如果原始問(wèn)題和對(duì)偶問(wèn)題都有可行解，則兩者都有最優(yōu)解，并且目標(biāo)函數(shù)值相同。,證明：由于兩者都有可行解，根據(jù)弱對(duì)偶性的推論知：原問(wèn)題目標(biāo)函數(shù)值有上界，對(duì)偶問(wèn)題目標(biāo)函數(shù)值有下界，因此，兩者都有有限的最優(yōu)目標(biāo)函數(shù)值。其次，用單純形法求原問(wèn)題最優(yōu)解時(shí)，最優(yōu)性判斷條件是：檢驗(yàn)數(shù)≤0，即 C － CB

27、B –1 A ≤0 － CB B –1≤0 令Y '= CB B –1 ，則，Y' A ≥ C， Y ≥0 。即，Y'= CB B –1是對(duì)偶問(wèn)題的可行解。由于該可行解的 目標(biāo)函數(shù)值與原問(wèn)題的目標(biāo)函數(shù)值相同，由最優(yōu)性可知，兩者都是最優(yōu)解。,,根據(jù)上述的對(duì)偶性質(zhì)（理論），不難看出原問(wèn)題和對(duì)偶問(wèn)題的解

28、存在有如下關(guān)系。,性質(zhì)4. 互補(bǔ)松弛性（或松緊定理）。在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)于某一約束條件的對(duì)偶變量值不為零，則該約束條件取嚴(yán)格的等式符號(hào)；反之，如果約束條件取嚴(yán)格不等式符號(hào)，則其對(duì)應(yīng)的對(duì)偶變量一定取零值。,或：如果X 0，Y 0分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解，Xs、Ys分別是原問(wèn)題和對(duì)偶問(wèn)題的松弛變量和剩余變量，則X 0，Y 0為最優(yōu)解的條件是 Ys &

29、#39;X 0 + Xs 'Y 0 = 0進(jìn)一步地， Ys 'X 0 = 0， Y 0' Xs = 0,證明：把可行解X 0，Y 0 ，松弛變量Xs、Ys代入原問(wèn)題和對(duì)偶問(wèn)題的約束中，得 A X 0 + Xs = b

30、 A'Y 0－ Ys = C',前式左乘Y 0' ，后式轉(zhuǎn)置后右乘X 0 ，得 Y 0 'A X 0 + Y 0 'Xs = Y 0' b Y 0 'A X 0 － Ys' X 0 = C X 0,Y 0' Xs +Ys'X 0 = Y 0 'b － C X 0,顯然，如果X 0，Y 0 是最優(yōu)

31、解，右端為零，互補(bǔ)松弛性成立；由于式中的每一個(gè)向量都是非負(fù)的，所以，它們的點(diǎn)積（內(nèi)積）非負(fù)。而如果兩個(gè)非負(fù)項(xiàng)相加等于零，那么，每一個(gè)非負(fù)項(xiàng)必須等于零。即 Y'sX 0 = 0， Y 0 'Xs = 0,經(jīng)濟(jì)意義：如果某種資源有剩余（約束為嚴(yán)格不等式），則它的價(jià)值為零。,其對(duì)偶問(wèn)題的最優(yōu)解為 y1﹡ = 4/5， y2 ﹡ =3/5。試確定原問(wèn)題的最優(yōu)解。,將

32、對(duì)偶問(wèn)題最優(yōu)解代入對(duì)偶約束中可知，第2、3、4約束為嚴(yán)格不等式，x2﹡= x3﹡ = x4﹡ = 0。,對(duì)偶問(wèn)題的解大于零，所以，原問(wèn)題的約束條件在最優(yōu)時(shí)取等號(hào)，即 x1﹡ + 3 x5﹡ = 4 2x1﹡ + x5﹡ = 3,X ﹡ =（1，0，0，0，1）

33、T。,求解后得， x1* = 1， x5* =1。,第三節(jié) 影 子 價(jià) 格,二、影子價(jià)格的特點(diǎn)和應(yīng)用,一、影子價(jià)格的概念、定義,一、影子價(jià)格的概念、定義,從對(duì)偶問(wèn)題的基本性質(zhì)可以看出，當(dāng)線性規(guī)劃原問(wèn)題求得最優(yōu)解時(shí)，其對(duì)偶問(wèn)題也得到了最優(yōu)解，且目標(biāo)函數(shù)值相同，即 Z﹡ = CB XB﹡ = CB B –1 b =Y'﹡ b = w﹡,由于 b是線性規(guī)劃原問(wèn)題約束條件的右端常數(shù)項(xiàng)，表示企

34、業(yè)對(duì)資源的擁有量，如果 Z﹡是企業(yè)所創(chuàng)造的總收益的話， Y﹡就是資源在生產(chǎn)中作用和貢獻(xiàn)的有效性估價(jià)。為區(qū)別于資源的市場(chǎng)價(jià)格，稱 Y﹡為影子價(jià)格。,影子價(jià)格也叫經(jīng)濟(jì)價(jià)格，它有廣泛的含義。一般認(rèn)為，凡用各種方法計(jì)算出來(lái)的非自然形成的價(jià)格，以及由國(guó)際市場(chǎng)引進(jìn)的價(jià)格，只要不在現(xiàn)實(shí)生活中發(fā)生作用，都可以稱為影子價(jià)格。,（1）資源的市場(chǎng)價(jià)格是已知數(shù)，相對(duì)比較穩(wěn)定。而影子價(jià)格則有賴于資源的利用情況，是未知數(shù)。企業(yè)人、財(cái)、物、技術(shù)、管理的變化，都會(huì)直接

35、引起影子價(jià)格的變動(dòng)。,（2）影子價(jià)格是一種邊際價(jià)格。,目標(biāo)函數(shù)對(duì)資源b的偏導(dǎo)數(shù)表明，影子價(jià)格是在其它條件都不變化的情況下，單位資源變化所引起的目標(biāo)函數(shù)最優(yōu)值的變化量。,二、影子價(jià)格的特點(diǎn)和應(yīng)用,在圖解法中，我們?cè)鉀Q過(guò)如下問(wèn)題：,max z = 3x1+x2,,x1－x2≤1x1+ x2≤2,x1 , x2 ≥0,,x1-x2=1,,,x1+x2=2,可行域,Z=3x1+x2,,,,,,,,A(3/2,1/2); Z=5,x1+

36、x2=1,,,,B(1,0);Z=3,（3）影子價(jià)格是一種機(jī)會(huì)成本。 在純市場(chǎng)經(jīng)濟(jì)條件下，如果第二種資源的市場(chǎng)價(jià)低于2，可以買進(jìn)這種資源；相反，當(dāng)市場(chǎng)價(jià)格高于影子價(jià)格2時(shí)，應(yīng)該賣出庫(kù)存的該種資源，因?yàn)榻?jīng)過(guò)企業(yè)加工后，資源不但沒有升值，反而貶值了。隨著資源的買進(jìn)賣出，它的影子價(jià)格也在變化，一直到影子價(jià)格與市場(chǎng)價(jià)格相同時(shí)，才會(huì)處于平衡狀態(tài)（沒有投機(jī)的機(jī)會(huì)）。,（4）影子價(jià)格反映了資源利用的狀況。根據(jù)互補(bǔ)松弛性質(zhì)，當(dāng)某種資源未

37、得到充分利用時(shí)，該資源的影子價(jià)格等于零；當(dāng)資源的影子價(jià)格不等于零時(shí)，該資源在生產(chǎn)中已耗費(fèi)完畢。,（5）影子價(jià)格有助于給新產(chǎn)品定價(jià)和確定新產(chǎn)品是否值得生產(chǎn)。 各種產(chǎn)品在使用相同資源的情況下，新產(chǎn)品的定價(jià)一定要高于它的成本，反映到單純形表里，就是要求檢驗(yàn)數(shù)大于零：,檢驗(yàn)數(shù)的第一項(xiàng)是產(chǎn)品的價(jià)

38、格（產(chǎn)值），第二項(xiàng)是所耗費(fèi)資源的隱含成本。檢驗(yàn)數(shù)大于零說(shuō)明新產(chǎn)品可以投產(chǎn)，能為企業(yè)帶來(lái)附加收益。,（6）影子價(jià)格能確定資源的相對(duì)重要性，有助于決策。影子價(jià)格大小指明了資源的相對(duì)重要性次序。一般來(lái)說(shuō)，企業(yè)的資金是有限的，按照影子價(jià)格的大小，決策者可以方便地決定資源采購(gòu)的先后順序。,（7）一般來(lái)說(shuō)，對(duì)線性規(guī)劃問(wèn)題的求解解決的是資源的最優(yōu)分配方案；而對(duì)對(duì)偶問(wèn)題的求解則主要集中于資源的估價(jià)或資源是否得到合理利用問(wèn)題上。,（8）上述分析是基于最優(yōu)

39、可行基不變的前提下展開的，如果最優(yōu)可行基發(fā)生變化，則需要修正所得到的結(jié)論。,第 四 節(jié) 對(duì)偶單純形法,一、對(duì)偶單純形法的思路,二、對(duì)偶單純形法的計(jì)算步驟,對(duì)偶單純形法不是解對(duì)偶問(wèn)題的，而是在單純形表上進(jìn)行對(duì)偶運(yùn)算的方法。為了了解對(duì)偶單純形法的實(shí)質(zhì)，我們回顧一下單純形法。,單純形法開始于初始基可行解。如果不滿足最優(yōu)性條件，則要轉(zhuǎn)到能使目標(biāo)函數(shù)值得到改善的鄰近頂點(diǎn)上。在這個(gè)轉(zhuǎn)換過(guò)程中，存在兩個(gè)原則: 一是保持原問(wèn)題的解仍是可行的，

40、二是要求目標(biāo)函數(shù)值有改善。,一、對(duì)偶單純形法的思路,當(dāng)目標(biāo)函數(shù)值無(wú)法改善時(shí)（因退化出現(xiàn)循環(huán)的情況除外），所有的檢驗(yàn)數(shù)都≤0（求極大時(shí)≤0 ，求極小時(shí)，檢驗(yàn)數(shù)≥0）?！皺z驗(yàn)數(shù) ≤0 ”意味著在獲得原問(wèn)題最優(yōu)解的同時(shí)，也獲得了對(duì)偶問(wèn)題的一個(gè)可行解。因?yàn)樵瓎?wèn)題與對(duì)偶問(wèn)題的解都可行，并且目標(biāo)函數(shù)值相同，根據(jù)對(duì)偶理論，這個(gè)對(duì)偶可行解就是對(duì)偶問(wèn)題的最優(yōu)解。,因此，單純形法迭代過(guò)程的實(shí)質(zhì)是：在保持原問(wèn)題可行性的前提下，驅(qū)使對(duì)偶問(wèn)題從不可行（起始點(diǎn)、

41、中間點(diǎn)）轉(zhuǎn)變?yōu)榭尚械模ㄗ顑?yōu)點(diǎn)）發(fā)展歷程。,把上述思想移植到對(duì)偶問(wèn)題上。 如果保持對(duì)偶問(wèn)題的可行性（只要檢驗(yàn)數(shù)≤0即可），通過(guò)改變對(duì)偶問(wèn)題的可行基，使原問(wèn)題由不可行變?yōu)榭尚?，根?jù)對(duì)偶理論，這兩個(gè)可行解就是原始和對(duì)偶問(wèn)題的最優(yōu)解。,使用對(duì)偶單純形法必須滿足兩個(gè)條件：（1）單純形表中的所有檢驗(yàn)數(shù)必須符合最優(yōu)性要求,即對(duì)偶可行. （2）右端常數(shù)項(xiàng)列向量必須有負(fù)分量（如果原問(wèn)題可行，則直接用單純形法）,（1）把線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式，

42、找出對(duì)偶問(wèn)題的初始可行基，列出單純形表。表的格式與第一章的單純形表完全相同。,（2）確定換出基的變量。這一點(diǎn)與單純形法正好相反，那里是先確定換入變量。因?yàn)槌?shù)項(xiàng)有負(fù)分量，所以令br = min{bi},第 i 行對(duì)應(yīng)的基變量 xr 作為換出變量。,二、對(duì)偶單純形法的計(jì)算步驟,（3）確定換入基的變量。 這里要注意：?jiǎn)渭冃畏ù_定換出變量時(shí)用的是換入變量列向量與常數(shù)項(xiàng)列的最小比值； 對(duì)偶單純形法確定換入變量時(shí)

43、則用檢驗(yàn)數(shù)行與換出變量所在行的最小比值。,. 如果所有的arj≥0，則原問(wèn)題沒有可行解。停止計(jì)算。如果存在arj ＜0，則計(jì)算最小比值。,(4) 選擇 ar s 為主元素，把該列向量變?yōu)閱挝涣邢蛄?。這里的旋轉(zhuǎn)運(yùn)算和單純形法一樣，主元素處變?yōu)?，其余變?yōu)?即可。,（5）重復(fù)步驟（2）—（4），直至原問(wèn)題變?yōu)榭尚薪鉃橹埂?,在標(biāo)準(zhǔn)形式里，目標(biāo)函數(shù)系數(shù)滿足使用對(duì)偶單純形法的一個(gè)條件，但是，約束條件的右端常數(shù)項(xiàng)非負(fù)，且沒有單位矩陣。為此，把約束

44、方程兩邊都乘以-1，得,,,根據(jù)對(duì)偶單純形法，首先選擇換出變量：顯然常數(shù)項(xiàng)列最負(fù)的元素是-2，所以第一行的基變量 x4 作為換出變量。,換入變量的確定:第一行與檢驗(yàn)數(shù)行對(duì)應(yīng)分量比值的最小值為： 最小比值={—，-24/-6，-5/-1} = 4 -6是主元素， x2是換入變量。,,,負(fù)元素是-1/3，第二行基變量 x5 作為換出變量。,換入變量的確定:最小比值={-15/-5，-1/（-2/3），-

45、 4/（-1/3）} = 3/2 -2/3是主元素， x3是換入變量。,,,-2/3,由于原始，對(duì)偶都已經(jīng)可行，對(duì)應(yīng)的解是最優(yōu)解。,注意：具有本例題形式的線性規(guī)劃問(wèn)題在求最優(yōu)解時(shí)，可以不使用人工變量，對(duì)偶單純形法能使求解過(guò)程更簡(jiǎn)便。,第 五 節(jié) 靈敏度分析,一、線性規(guī)劃的基本假設(shè),靈敏度分析的概念：是指對(duì)系統(tǒng)或事物因周圍環(huán)境

46、條件發(fā)生變化所表現(xiàn)出來(lái)的敏感程度的分析。,二、靈敏度分析及其步驟,70頁(yè),(2) 檢查原問(wèn)題是否仍可行：基變量的取值是否仍全部≥0；,（3）檢查對(duì)偶問(wèn)題是否仍可行：檢驗(yàn)數(shù)行是否仍滿足最優(yōu)性條件,（4）按下表所列情況得出結(jié)論，即決定繼續(xù)計(jì)算的步驟。,按與變量的對(duì)應(yīng)關(guān)系劃分，價(jià)值系數(shù)可分為基變量?jī)r(jià)值系數(shù)和非基變量?jī)r(jià)值系數(shù)兩種。由于價(jià)值系數(shù)的變化直接影響到檢驗(yàn)數(shù)，所以，價(jià)值系數(shù)變化的結(jié)果只有兩個(gè)：原始，對(duì)偶問(wèn)題均可行，最優(yōu)解不變；原始問(wèn)題可行

47、，但對(duì)偶問(wèn)題不可行，需要用單純形法繼續(xù)求解。,三、價(jià)值系數(shù)cj的變化分析,,XN XS,CN CS,CN,XB,CB,CB,CB,1．非基變量 xj的價(jià)值系數(shù)cj 發(fā)生變化。 設(shè)價(jià)值系數(shù)的增量為⊿ cj ，要保證

48、最優(yōu)基不變，必須使最終表中的檢驗(yàn)數(shù)仍≤0，即,或者,（2）基變量xr的價(jià)值系數(shù)cr 發(fā)生變化。,所以，非基變量在最終表的檢驗(yàn)數(shù)變?yōu)?如果要求原最優(yōu)基不變，非基變量的檢驗(yàn)數(shù)必須滿足≤0的條件,于是，基變量?jī)r(jià)值系數(shù) cr 的變化范圍是,上式僅適用于一個(gè)基變量?jī)r(jià)值系數(shù)發(fā)生變化的情況。,注意：在進(jìn)行靈敏度分析時(shí)，可以用上面的公式確定參數(shù)的變化范圍，也可以把價(jià)值系數(shù)當(dāng)作未知數(shù)在表上進(jìn)行直接計(jì)算。(*),,（1）當(dāng)產(chǎn)品1的價(jià)值系數(shù)由 2變?yōu)?3，產(chǎn)

49、品2的價(jià)值系數(shù)從3變?yōu)? 時(shí)，最優(yōu)解會(huì)如何變化？產(chǎn)品2的價(jià)值系數(shù)的變化范圍是什么？,,,,四、資源量bi的變化分析,b,b,設(shè)第r 種資源發(fā)生變化，資源量從 br變?yōu)閎r +⊿ br 。其它系數(shù)維持不變。這樣，在最終表中的基解相應(yīng)地改變?yōu)?只要XB′≥0，最終表中的檢驗(yàn)數(shù)不變，則最優(yōu)基不變（注意，最優(yōu)解的值已經(jīng)改變）。為保持最優(yōu)基不變，資源增量的變化范圍如下：,這是可行基矩陣B的逆矩陣B﹣1的第 r 列,這樣，最終表里保持最優(yōu)基不變的b

50、列元素滿足,企業(yè)又購(gòu)進(jìn)資源A 4個(gè)單位用于生產(chǎn)。求此時(shí)的最優(yōu)方案。,,,B﹣1⊿b =,,=,附加資源帶來(lái)了獲利水平的提高，最優(yōu)的目標(biāo)函數(shù)值為17,資源B在何范圍變動(dòng)時(shí),最優(yōu)基不變。,B﹣1⊿b =,,=,-8≤ ⊿b2 ≤16,五、增加一個(gè)新變量 xk 的分析,XP,P,CP,XP,B-1P,CP –CBB-1P,增加新變量在實(shí)踐中對(duì)應(yīng)于增加一種新產(chǎn)品。分析步驟是：,（1）利用新產(chǎn)品的數(shù)據(jù)計(jì)算檢驗(yàn)數(shù)，

51、 (cp－zp) = cp－Y ′ Pp 。（2）計(jì)算新產(chǎn)品在單純形表中的系數(shù)列向量 Pp *=B﹣1 Pp 。（3）如果檢驗(yàn)數(shù)≤0，最優(yōu)基不變，只要把上面計(jì)算的結(jié)果放在單純形表的最后一列即可。如果檢驗(yàn)數(shù)大于零，則要用單純形法繼續(xù)迭代，求出最優(yōu)解。,例:在上述模型中，企業(yè)打算生產(chǎn)一種新產(chǎn)品，每件產(chǎn)品消耗 3種資源的量分別為2、6和3個(gè)單位，單件可獲利5元。問(wèn)可否投產(chǎn)？,解：（1）新產(chǎn)品能否投產(chǎn)關(guān)鍵看能否為企業(yè)帶來(lái)利潤(rùn)。設(shè)

52、新產(chǎn)品的生產(chǎn)量為x6 ，它的檢驗(yàn)數(shù)為,因?yàn)闄z驗(yàn)數(shù)大于零，所以，新產(chǎn)品可以生產(chǎn)。,（2）計(jì)算新產(chǎn)品在單純形表中的系數(shù)列向量 P6* =B﹣1 P6 。,B﹣1 P6 =,0 1/4 0 -2 1/2 1 1/2 -1/8 0,263,5 x6,5/4,3/2 21/4,,,,參數(shù) aij變化使得系數(shù)矩陣A

53、也隨之發(fā)生變化。如果變量 xj 在最終單純形表里是非基變量，可以按照增加一個(gè)變量的方法處理。如果 xj 是基變量，則參數(shù)aij的變化有可能同時(shí)影響可行性和最優(yōu)性。,六、分析參數(shù)aij 的變化,例2.5.4 由于產(chǎn)品工藝結(jié)構(gòu)改變，產(chǎn)品1的技術(shù)系數(shù)向量變?yōu)?P1′=（4，5，2）T。每件產(chǎn)品的利潤(rùn)為4元（原來(lái)為2元）。問(wèn)：該企業(yè)應(yīng)如何安排生產(chǎn)計(jì)劃？,解：先將改變工藝結(jié)構(gòu)后的產(chǎn)品x1′作為新產(chǎn)品看待。,4 x1′ 5/4-7/21

54、1/8-21/8,由于x1是基變量，所以，要把 x1′的系數(shù)列向量變成與 x1相同的單位列向量（主元素為5/4）。然后，把的x1系數(shù)列向量劃去，僅保留的x1′系數(shù)列向量。,x1 + 1/5 x4 = 16/5,- 2 x3 +6/5 x4 +x5 = 76/5,x2 +1/2 x3 - 2/5x4 = -12/5,,x2 + 1/2 x3 - 2

55、/5x4 = -12/5,－ x2 －1/2 x3 + 2/5x4 = 12/5,+ x6,x1,x5,-M x6 0 0 1 0,x4作為換入變量，2/5作為主元素，經(jīng)過(guò)迭代獲得最優(yōu)解，如表示。,,,2/5,X*=(2/3,8/3,0,38/3,0,0) Z*=32/3,1.減少一個(gè)約束條件： 通常，減少約束條件可以使變量的取

56、值空間變大，自由度增加。如果要?jiǎng)h除的約束與基變量無(wú)關(guān)，可以很方便地去掉，因?yàn)榇思s束是多余約束；如果要?jiǎng)h除的約束與基變量有關(guān)，刪除此約束會(huì)影響到最優(yōu)解。這時(shí)，可以在約束方程中同時(shí)加上和減去一個(gè)非負(fù)的松弛變量，經(jīng)過(guò)迭代之后，約束會(huì)自動(dòng)失去作用。,七、增加或減少一個(gè)約束條件的分析,2.增加一個(gè)約束條件： 增加約束條件一般意味著活動(dòng)空間的縮小，靈活性的降低。此時(shí)，通常有兩種情況發(fā)生，一是基變量沒有改變，二是基變量不適應(yīng)新增加的約束條

57、件。 (1)第一種情況，因?yàn)樵黾蛹s束可能使可行域減小或保持不變，只要基變量仍然可行，最優(yōu)解肯定沒變化。（方法：把基變量的值代入約束條件中，如果滿足新的約束條件，就可斷定最優(yōu)解沒有變化。 (2) 第二種情況，必須另找新的最優(yōu)解。此時(shí)，只要在原來(lái)的單純形表（注意：是最終單純形表）里增加一行，用對(duì)偶單純形法求解.,1 3 0 0 0,0 x6 0 0

58、0 1 0,對(duì)于例2.5.1的原問(wèn)題，如果增加一道生產(chǎn)工序 ，要求產(chǎn)品滿足約束條件 x1+ 3 x2 ≤ 9 ，試問(wèn)應(yīng)如何安排生產(chǎn)，可以使利潤(rùn)最大？,0 x6 9,x1+ 3 x2 ≤ 9,+ x6=,,第 六 節(jié) 參數(shù)線性規(guī)劃,靈敏度分析是研究cj、bi等參數(shù)對(duì)最優(yōu)基或最優(yōu)解的影響；參數(shù)線性規(guī)劃是指線性規(guī)劃問(wèn)題中價(jià)值系數(shù)cj 、資源量bi或目標(biāo)函數(shù)z中含有參數(shù)的線性規(guī)劃

59、問(wèn)題。,當(dāng)目標(biāo)函數(shù)中C值按（C+λC*）連續(xù)變化時(shí)，其參數(shù)線性規(guī)劃的形式為：,當(dāng)約束條件右端項(xiàng)中b值按（b+λb*）連續(xù)變化時(shí)，其參數(shù)線性規(guī)劃的形式為：C、b分別為原線性規(guī)劃問(wèn)題的價(jià)值系數(shù)和資源量向量，C*和b*為變動(dòng)向量，λ為參數(shù)。,參數(shù)線性規(guī)劃問(wèn)題的分析步驟：,1、令λ=0求解得最終單純形表；2、將λC*或λb*項(xiàng)反映到最終單純形表中去；3、隨λ值的增大或減小，觀察原問(wèn)題或?qū)ε紗?wèn)題： （1）確定表中現(xiàn)有解（基

60、）允許λ值的變動(dòng)范圍； （2）當(dāng)λ值超出范圍時(shí)用單純形法或?qū)ε紗渭冃畏ㄇ蟮眯碌慕猓?、重復(fù)上一步，直到λ值繼續(xù)增大或減小時(shí)，表中的解（基）不再出現(xiàn)變化為止。例（略） DEA,習(xí)題,1、寫出下面規(guī)劃問(wèn)題的對(duì)偶問(wèn)題,minZ=∑∑cijxij,i=1,j=1,m,n,∑xij=ai (i=1

61、,…,m),j=1,n,∑xij=bj (j=1,…,n),i=1,m,xij ≥0 (i=1,…,m;j=1,…,n),,x11+x12+x13+…+x1n=a1,x21+x22+x23+…+x2n=a2,xm1+xm2+xm3+…+xmn=am,………………,x11+x21+x31+…+xm1=b1,x12+x22+x32+…+xm2=b2,x1n+x2n+x3n+…+xmn=bn,………………,u1,v1,u2,um,v2

62、,vn,………..,2、已知某求極大化線性規(guī)劃問(wèn)題的初始單純形表和最終單純形表，求表中未知數(shù)據(jù)。,k=0,l=1,h=-1/2,b=10,i=-1/4,a=2,c=3,d=1/4,e=5/4,f=-1/2,g=-3/4,j=-1/4,3、給出線性規(guī)劃問(wèn)題,（1）寫出其對(duì)偶問(wèn)題，（2）用圖解法求解對(duì)偶問(wèn)題（3）利用對(duì)偶問(wèn)題基本性質(zhì)寫出原問(wèn)題的最優(yōu)解,,,y1,y2,,,,(8/5,-1/5),x1 + 2x2+3x3 = 2,- 2x

63、1 + x2 –x3 =-3,,2x1 + 3x2+5x3=19/5,無(wú)窮多最優(yōu)解,x4=0,X=(7/5,0,1/5,0)T Z=19/5,4、已知線性規(guī)劃問(wèn)題,證明：該線性規(guī)劃問(wèn)題具有無(wú)界解,,,y1,y2,,,,,,,-y1 – 2 y2 = 1,證明：由圖可知，對(duì)偶問(wèn)題無(wú)可行解。取X=(0，0，0)T為原問(wèn)題的一可行解，根據(jù)對(duì)偶問(wèn)題基本性質(zhì)，則原問(wèn)題具有無(wú)界解,36,5、用對(duì)偶單純形法求解下面的規(guī)劃問(wèn)題。,x1

64、 x2 x3 x4 x5,cj,-5 -2 -4 0 0,CB,XB,b,00,x4 x5,-4-10,-1 -3,-2 -5,1 0,0 1,-3 -6,-5 -2 -4 0 0,,,-2 x2 10/3 2 1 5/3

65、 0 -1/3,0 x4 -2/3 -1 0 -1/3 1 -1/3,,,-1 0 -2/3 0 -2/3,,,,-5 x1 2/3 1 0 1/3 -1 1/3,-2 x2 2 0

66、 1 1 2 -1,,,0 0 -1/3 -1 -1/3,6.某工廠生產(chǎn)A，B，C三種產(chǎn)品，若設(shè)x,y,z分別為A，B，C三種產(chǎn)品的產(chǎn)量，為制定最優(yōu)生產(chǎn)計(jì)劃建立如右所示模型：,（1） 用表格單純形法求出最優(yōu)生產(chǎn)計(jì)劃 （2） 在所得最優(yōu)表格基礎(chǔ)上，分別就以下情況進(jìn)行分析。 ① 由于市場(chǎng)需求變化，產(chǎn)品B的單位利潤(rùn)可能改變，試求出保持最優(yōu)生產(chǎn)計(jì)劃不需改

67、變的產(chǎn)品B單位利潤(rùn)的變化范圍；若產(chǎn)品B單位利潤(rùn)由3變?yōu)?，求相應(yīng)最優(yōu)生產(chǎn)計(jì)劃。  ② 由于原材料市場(chǎng)變化，原材料1的供應(yīng)從100單位降低至50個(gè)單位，此時(shí)是否會(huì)影響最優(yōu)生產(chǎn)計(jì)劃？若影響，求其最優(yōu)生產(chǎn)計(jì)劃？ ③  由于生產(chǎn)技術(shù)改進(jìn)，產(chǎn)品C的單位利潤(rùn)消耗原材料1，2及工時(shí)由原來(lái)的4，6，2依次變?yōu)?，2，1，求相應(yīng)的最優(yōu)生產(chǎn)計(jì)劃？,,,3,4 x 100/3 1 1/3

68、 2 0 1/3 0,0 k3 20 0 0 -4 0 -1 1,0 k1 100/3 0 4/3 0 1 -2/3 0,,,0 5/3 -5 0 -4/3 0,,,,4/3,