運籌學課件 6

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

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

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

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

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

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

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

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

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

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

11、4,u1,u2,u3,四、原始-對偶關系一覽表,解：根據(jù)表3，得出對偶線性規(guī)劃問題如下：,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自由變量.,,課堂練習,第二節(jié) 對偶問題的基本性質(zhì),本節(jié)以對稱形式的原始-對偶問題為討論的基礎，除非特別需要，一般不再專門說明。,一、單純形法計算的矩陣描述,原問題通過加入松弛變量 Xs 可以化為標準形式：,其中，I 是對應于松弛變量的單位方陣。,,單純形法計算時，總是選擇 I 為初始可行

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

14、為B，價值系數(shù)為CB 。A去掉B 的若干列后，剩余的列向量組成子矩陣N，對應的變量組合記為XN ，價值系數(shù)記為CN 。,CB XB b1,基變量,非基變量,XB,XN Xs,I,,檢驗數(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,代入目標函數(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,式中帶陰影的就是非基變量的檢驗數(shù)， z0 對應于當前的目標函數(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,如果表中的檢驗數(shù)滿足最優(yōu)性條件，即 CN － CB B –1 N≤0 － CB B –1= CS－ CB B –1 I≤0,由于基變量的

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

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

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

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

22、標函數(shù)值的上界。（2）如果原問題有可行解且目標函數(shù)值無界（無界解），則對偶問題無可行解；反之，對偶問題有可行解且目標函數(shù)值無界，則原問題無可行解。 注意：本性質(zhì)的逆不成立。因為當對偶不可行時，要么原問題無界，要么原問題無可行解。（3）如果原問題有可行

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

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

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

26、 如果原始問題和對偶問題都有可行解，則兩者都有最優(yōu)解，并且目標函數(shù)值相同。,證明：由于兩者都有可行解，根據(jù)弱對偶性的推論知：原問題目標函數(shù)值有上界，對偶問題目標函數(shù)值有下界，因此，兩者都有有限的最優(yōu)目標函數(shù)值。其次，用單純形法求原問題最優(yōu)解時，最優(yōu)性判斷條件是：檢驗數(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是對偶問題的可行解。由于該可行解的 目標函數(shù)值與原問題的目標函數(shù)值相同，由最優(yōu)性可知，兩者都是最優(yōu)解。,,根據(jù)上述的對偶性質(zhì)（理論），不難看出原問題和對偶問題的解

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

29、#39;X 0 + Xs 'Y 0 = 0進一步地， Ys 'X 0 = 0， Y 0' Xs = 0,證明：把可行解X 0，Y 0 ，松弛變量Xs、Ys代入原問題和對偶問題的約束中，得 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、解，右端為零，互補松弛性成立；由于式中的每一個向量都是非負的，所以，它們的點積（內(nèi)積）非負。而如果兩個非負項相加等于零，那么，每一個非負項必須等于零。即 Y'sX 0 = 0， Y 0 'Xs = 0,經(jīng)濟意義：如果某種資源有剩余（約束為嚴格不等式），則它的價值為零。,其對偶問題的最優(yōu)解為 y1﹡ = 4/5， y2 ﹡ =3/5。試確定原問題的最優(yōu)解。,將

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

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

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

35、引起影子價格的變動。,（2）影子價格是一種邊際價格。,目標函數(shù)對資源b的偏導數(shù)表明，影子價格是在其它條件都不變化的情況下，單位資源變化所引起的目標函數(shù)最優(yōu)值的變化量。,二、影子價格的特點和應用,在圖解法中，我們曾解決過如下問題：,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）影子價格是一種機會成本。 在純市場經(jīng)濟條件下，如果第二種資源的市場價低于2，可以買進這種資源；相反，當市場價格高于影子價格2時，應該賣出庫存的該種資源，因為經(jīng)過企業(yè)加工后，資源不但沒有升值，反而貶值了。隨著資源的買進賣出，它的影子價格也在變化，一直到影子價格與市場價格相同時，才會處于平衡狀態(tài)（沒有投機的機會）。,（4）影子價格反映了資源利用的狀況。根據(jù)互補松弛性質(zhì)，當某種資源未

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

52、新產(chǎn)品的生產(chǎn)量為x6 ，它的檢驗數(shù)為,因為檢驗數(shù)大于零，所以，新產(chǎn)品可以生產(chǎn)。,（2）計算新產(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 在最終單純形表里是非基變量，可以按照增加一個變量的方法處理。如果 xj 是基變量，則參數(shù)aij的變化有可能同時影響可行性和最優(yōu)性。,六、分析參數(shù)aij 的變化,例2.5.4 由于產(chǎn)品工藝結構改變，產(chǎn)品1的技術系數(shù)向量變?yōu)?P1′=（4，5，2）T。每件產(chǎn)品的利潤為4元（原來為2元）。問：該企業(yè)應如何安排生產(chǎn)計劃？,解：先將改變工藝結構后的產(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)過迭代獲得最優(yōu)解，如表示。,,,2/5,X*=(2/3,8/3,0,38/3,0,0) Z*=32/3,1.減少一個約束條件： 通常，減少約束條件可以使變量的取

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

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

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

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

60、）允許λ值的變動范圍； （2）當λ值超出范圍時用單純形法或?qū)ε紗渭冃畏ㄇ蟮眯碌慕猓?、重復上一步，直到λ值繼續(xù)增大或減小時，表中的解（基）不再出現(xiàn)變化為止。例（略） DEA,習題,1、寫出下面規(guī)劃問題的對偶問題,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ī)劃問題的初始單純形表和最終單純形表，求表中未知數(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ī)劃問題,（1）寫出其對偶問題，（2）用圖解法求解對偶問題（3）利用對偶問題基本性質(zhì)寫出原問題的最優(yōu)解,,,y1,y2,,,,(8/5,-1/5),x1 + 2x2+3x3 = 2,- 2x

63、1 + x2 –x3 =-3,,2x1 + 3x2+5x3=19/5,無窮多最優(yōu)解,x4=0,X=(7/5,0,1/5,0)T Z=19/5,4、已知線性規(guī)劃問題,證明：該線性規(guī)劃問題具有無界解,,,y1,y2,,,,,,,-y1 – 2 y2 = 1,證明：由圖可知，對偶問題無可行解。取X=(0，0，0)T為原問題的一可行解，根據(jù)對偶問題基本性質(zhì)，則原問題具有無界解,36,5、用對偶單純形法求解下面的規(guī)劃問題。,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)品，若設x,y,z分別為A，B，C三種產(chǎn)品的產(chǎn)量，為制定最優(yōu)生產(chǎn)計劃建立如右所示模型：,（1） 用表格單純形法求出最優(yōu)生產(chǎn)計劃 （2） 在所得最優(yōu)表格基礎上，分別就以下情況進行分析。 ① 由于市場需求變化，產(chǎn)品B的單位利潤可能改變，試求出保持最優(yōu)生產(chǎn)計劃不需改

67、變的產(chǎn)品B單位利潤的變化范圍；若產(chǎn)品B單位利潤由3變?yōu)?，求相應最優(yōu)生產(chǎn)計劃。  ② 由于原材料市場變化，原材料1的供應從100單位降低至50個單位，此時是否會影響最優(yōu)生產(chǎn)計劃？若影響，求其最優(yōu)生產(chǎn)計劃？ ③  由于生產(chǎn)技術改進，產(chǎn)品C的單位利潤消耗原材料1，2及工時由原來的4，6，2依次變?yōu)?，2，1，求相應的最優(yōu)生產(chǎn)計劃？,,,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,