運(yùn)籌學(xué)線性規(guī)劃進(jìn)一步研究

1、第二章 線性規(guī)劃的進(jìn)一步研究線性規(guī)劃早期發(fā)展過程中的最為重要的理論成果之一就是線性規(guī)劃的對偶問題及其相關(guān)理論的提出。線性規(guī)劃的對偶理論是解釋資源的影子價(jià)格、線性規(guī)劃問題的靈敏度分析等的理論基礎(chǔ)。第一節(jié) 對偶問題一、對偶問題的提出在第一章例1.1的生產(chǎn)計(jì)劃問題中，從安排生產(chǎn)使企業(yè)利潤最大的角度考慮，若用x1、x2分別代表甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量，則問題的線性規(guī)劃數(shù)學(xué)模型為：問題A max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20現(xiàn)在從另一個角度考慮，即企業(yè)不安排生產(chǎn)，而轉(zhuǎn)讓三種資源，應(yīng)如何給三種資源定價(jià)？設(shè)y1、y2、y3分別代表A、B、C三種資源

2、的價(jià)格，即轉(zhuǎn)讓單位數(shù)量所獲收益。對于決策者，首先當(dāng)然會考慮如下兩個條件：約束條件1：生產(chǎn)一件產(chǎn)品甲所耗資源數(shù)量轉(zhuǎn)讓所得總收益不能低于一件產(chǎn)品甲所獲利潤，即1y1+ 2y2 50約束條件2：生產(chǎn)一件產(chǎn)品乙所耗資源數(shù)量轉(zhuǎn)讓所得總收益不能低于一件產(chǎn)品乙所獲利潤，即1y1+ 1y2+ 1y3 100而企業(yè)將現(xiàn)有三種資源全部轉(zhuǎn)讓所得總收益，即目標(biāo)函數(shù)為：w=300y1 +400y2 +250y3從數(shù)學(xué)的角度分析，若目標(biāo)函數(shù)極大化，則問題為無界解，即問題無意義，故目標(biāo)函數(shù)只能極小化。從經(jīng)濟(jì)的角度看，A、B、C三種資源的轉(zhuǎn)讓是與企業(yè)利用這三種資源進(jìn)行最優(yōu)生產(chǎn)進(jìn)行比較的，因此，企業(yè)的決策者可以從這種比較中了解

3、在不低于企業(yè)最優(yōu)生產(chǎn)所獲利潤條件下各資源的最低轉(zhuǎn)讓價(jià)格，這樣問題的目標(biāo)函數(shù)也是要求為極小化。因此問題的數(shù)學(xué)模型為：問題B min w=300y1 +400y2 +250y3y1+2y2 50y1+ y2+ y3 100 y1、y2、y3 0稱問題B為問題A的對偶問題，問題A為原問題。二、對偶問題的定義定義2.1 設(shè)有線性規(guī)劃問題max z=CXAXbX0其對偶問題定義為min w=YbYACY0且前者稱為原問題，后者稱為對偶問題。具體的數(shù)量對應(yīng)關(guān)系為原問題 max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1a21x1+a22x2+a2nxn b2 am1x1+a

4、m2x2+amnxn bm x1，x2，xn0對偶問題 min w =b1y1+b2y2+bmym a11y1+a21y2+am1ym c1a12y1+a22y2+am2ym c2 a1ny1+a2ny2+amnym cn y1，y2，ym0根據(jù)對偶問題的定義不難推出，對于線性規(guī)劃問題：min w=Yb；YAC；Y0其對偶問題為：max z=CX；AXb；X0即兩線性規(guī)劃問題互為對偶。事實(shí)上，任一線性規(guī)劃問題都有一個固定的線性規(guī)劃問題與之對偶，且二者互為對偶關(guān)系，線性規(guī)劃的這種性質(zhì)稱為對稱性。更進(jìn)一步有，對于線性規(guī)劃問題：max z=CX；AX = b，X0其對偶問題為：min w=Yb；YA

5、C，Y無限制根據(jù)以上分析，線性規(guī)劃原問題與對偶問題的數(shù)量關(guān)系可用表21描述。表21原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)函數(shù)max zmin w目標(biāo)函數(shù)變量n個00無約束n個=約束條件約束條件m個=m個00無約束變量約束條件右端常數(shù)項(xiàng)目標(biāo)函數(shù)變量系數(shù)目標(biāo)函數(shù)變量系數(shù)約束條件右端常數(shù)項(xiàng)例2.1 寫出下列線性規(guī)劃問題的對偶問題 max z=2x1+2x24x3x1 + 3x2 + 3x3 304x1 + 2x2 + 4x380x1、x2，x30解：其對偶問題為min w=30y1+ 80y2y1+ 4y2 23y1 + 2y2 23y1 + 4y2 4y1、y20例2.2 寫出下列線性規(guī)劃問

6、題的對偶問題 min z=2x1+8x24x3x1 + 3x23x3 30x1 + 5x2 + 4x3 = 804x1 + 2x24x350x10、x20，x3無限制解：其對偶問題為max w=30y1+80 y2+50 y3 y1 y2 + 4 y3 23y1+5y2 + 2y3 83y1 + 4y24y3 =4y10，y2無限制，y30第二節(jié) 對偶理論一、 單純形法的矩陣描述為了更好地闡述對偶理論，這里先用矩陣的形式描述單純形法的計(jì)算過程。設(shè)有線性規(guī)劃問題max z=CXAXbX0加上松弛變量XS=（xn+1，xn+2，xn+m）T，將其化為標(biāo)準(zhǔn)形式得到max z=CX+0XSAX+I X

7、S = bX0，XS0其中 I為m×m階單位陣。設(shè)A中存在一可行基B，相應(yīng)的變量X分成基變量XB和非基變量XN，價(jià)格系數(shù)C也相應(yīng)地分成CB和CN兩部分，A陣也分成B、N兩部分，即A=（B，N），X=（XB，XN）T，C=（CB，CN）這樣因而有 BXB+NXN + I XS = b即 XB = B-1bB-1NXNB-1XS用非基變量XN表示目標(biāo)函數(shù)有 = CBXB+CNXN+0XS將XB = B-1bB-1NXNB-1XS代入得z = CB（B-1bB-1NXNB-1XS）+CNXN+0XS= CBB-1b+（CNCBB-1N）XNCBB-1XS令 XN=0，XS=0得到對應(yīng)于基B

8、的基可行解 X=（XB，XX，XS）T=（B-1b，0，0）T目標(biāo)值為 z = CBB-1b相應(yīng)的非基變量的檢驗(yàn)數(shù)為N=（CNCBB-1N，CBB-1）若將基變量一起考慮有=（0，CNCBB-1N，CBB-1）=（CCBB-1A，CBB-1）此外，從上式中可推出計(jì)算某一具體變量xj的檢驗(yàn)數(shù)計(jì)算公式，即j=cjCBB-1pj上述過程可用如下單純形表描述。表22 CCBCN0bCBXBXBXNXSCBXBIB-1NB-1B-1bz0CNCBB-1NCBB-1CBB-1b由最優(yōu)性判別定理可知，當(dāng)=（CCBB-1A，CBB-1）0時(shí)， X=（XB，XX，XS）T=（B-1b，0，0）T為線性規(guī)劃的最優(yōu)

9、解；若存在j=cjCBB-1pj>0，（jJ），有B-1pj0，則線性規(guī)劃問題有無界解。二、對偶問題的基本定理定理2.1(弱對偶定理) 設(shè)X(0)是原問題max z=CX，AXb，X0的可行解，Y（0）是其對偶問題min w=Yb，YAC，Y0的可行解，則有CX（0）Y（0）b。證 由X（0）、Y（0）分別為原問題和對偶問題的可行解的條件可知AX（0）b ，X（0）0； Y（0）AC，Y（0）0因此有 Y（0）AX（0）Y（0）b綜合上兩式有 CX（0）Y（0）b得證弱對偶定理說明，如果原問題是極大化問題，則它的任一可行解對應(yīng)的目標(biāo)函數(shù)值不大于其對偶問題的（最小化問題）的任一可行解對應(yīng)目

10、標(biāo)函數(shù)值。定理2.2(最優(yōu)性定理) 設(shè)X(0)是原問題max z=CX，AXb，X0的可行解，Y（0）是其對偶問題min w=Yb，YAC，Y0的可行解，若CX（0）= Y（0）b，則X（0）、Y（0）分別是它們的最優(yōu)解。證 設(shè)是原問題的任一可行解，由弱對偶定理可知CY（0）b = CX（0）故 X（0）為原問題的最優(yōu)解。同理可證Y（0）為對偶問題的最優(yōu)解。 證畢。定理2.3(對偶定理) 若原問題max z=CX，AXb，X0有最優(yōu)解，則其對偶問題min w=Yb，YAC，Y0一定有最優(yōu)解，且二者的目標(biāo)函數(shù)值相等。證 設(shè)X*是原問題的最優(yōu)解，相應(yīng)的最優(yōu)基為B，則其檢驗(yàn)數(shù)必滿足CCBB-1A0令

11、 Y*=CBB-1則有 Y*AC，Y*0即Y為對偶問題的可行解。又 Y*b=CBB-1b=z*=CX*由最優(yōu)性定理可知，對偶問題也有最優(yōu)解。證畢。定理2.4(互補(bǔ)松弛定理) 原問題max z=CX，AXb，X0及其對偶問題min w=Yb，YAC，Y0 的可行解X（0）、Y（0）是最優(yōu)解的充要條件是 Y（0）XS = 0 ； YSX（0）= 0其中，XS、YS分別是原問題松弛變量向量和對偶問題剩余變量向量。（證明略）例2.3 已知線性規(guī)劃問題 max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4202x1 + x2 + 3x3 +2x420x1、x2，x3，x40其對

12、偶問題的最優(yōu)解為y1*=6/5，y2*=1/5。試用互補(bǔ)松弛定理求該線性規(guī)劃問題的最優(yōu)解。解：其對偶問題為min w=20y1+ 20y2y1 + 2y2 1 （1）2y1 + y2 2 （2）2y1 +3y2 3 （3）3y1 +2y2 4 （4）y1、y20將y1*=6/5，y2*=1/5代入上述約束條件，得（1）、（2）為嚴(yán)格不等式；由互補(bǔ)松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原問題的兩個約束條件應(yīng)取等式，所以2x3* +3x4* = 203x3* +2x4* = 20解得x3* = x4* = 4。故原問題的最優(yōu)解為 X*=（0，0，4，4）

13、T定理2.5 原問題單純形表的檢驗(yàn)數(shù)行對應(yīng)對偶問題的一個基本解。該定理的進(jìn)一步解釋有：若原問題最優(yōu)解存在，則原問題最優(yōu)單純形表的檢驗(yàn)數(shù)行中，松弛變量或剩余變量的檢驗(yàn)數(shù)對應(yīng)對偶問題的最優(yōu)解。例2.4 （原問題為極大化問題）對于原問題： max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20其對偶問題為： min w=300y1 +400y2 +250y3y1+2y2 50y1+ y2+ y3 100 y1、y2、y3 0解 原問題最優(yōu)單純形表如表23所示，對應(yīng)的對偶問題最優(yōu)解列于表中最后一行。表23 Cj50100000b CBXB x1 x2x3x4x

14、5 50x11010-1500 0x400-21150 100x2010-01250z005005027500對偶問題最優(yōu)解y1*y2*y3*表中x3、x4、x5為松弛變量；原問題最優(yōu)解為：X*=（500，250）T， z*=27500對偶問題的最優(yōu)解為：Y*=（y1*，y2*，y3*）=（50，0，50）， w*=27500例2.5 （原問題為極小化問題）對于原問題： min z=2x1+ 3x2x1 + x2350x1 1252x1 +x2600x1、x20其對偶問題為：max w=350y1 +125y2 +600y3y1+ y2 +2y3 2y1+ y3 3y1、y20、y3 0解 用

15、以極小化為標(biāo)準(zhǔn)形式的單純形法求得原問題最優(yōu)單純形表如表24所示，對應(yīng)的對偶問題最優(yōu)解列于表中最后一行。表24Cj23000MMb CBXB x1 x2x3x4x5x6x73X201-20-1201002X110101-102500X400111-1-1125z004014+MM-800對偶問題最優(yōu)解y1*y2*y3*表中x3、x4為剩余變量，x5為松弛變量；原問題最優(yōu)解為：X*=（250，100）T， Z*=800對偶問題的最優(yōu)解為：Y*=（y1*，y2*，y3*）=（4，0，1）， w*=800從上述兩個例子可以總結(jié)出：對偶問題的最優(yōu)解對應(yīng)原問題最優(yōu)單純形表中松弛變量檢驗(yàn)數(shù)的相反數(shù)或剩余變量

16、的檢驗(yàn)數(shù)。第三節(jié) 對偶問題的經(jīng)濟(jì)意義一、資源的影子價(jià)格如前所述，若X*為線性規(guī)劃max z=CX，AXb，X0的最優(yōu)解，則z*=CX*；若Y*為其對偶問題的最優(yōu)解，則有w*=Y*b。根據(jù)對偶定理有 z*=w*即 z*=Y*b因此 即 由此可以看出，對偶問題的最優(yōu)解實(shí)際上是右端常數(shù)項(xiàng)的單位變化所引起的目標(biāo)值的變化；若原問題描述的是資源有限條件下最優(yōu)生產(chǎn)決策問題，則其對偶問題的最優(yōu)解yi*(i=1,，m)表示第i種資源在最優(yōu)生產(chǎn)決策下的邊際值，即若其他條件不變，增加單位第i種資源將會使目標(biāo)函數(shù)值增加yi*。其經(jīng)濟(jì)意義是：yi*描述了第i種資源在具體生產(chǎn)中的一種估價(jià)，這種估價(jià)不同于該種資源的市場價(jià)格

17、，而是該種資源在給定條件某生產(chǎn)的最優(yōu)生產(chǎn)方案下的一種實(shí)際存在而又看不見的真實(shí)價(jià)值，因此稱之為影子價(jià)格（shadow price）。本節(jié)表23描述的就是第一章例1.1的最優(yōu)單純形表，從中可以看出A、B、C三種資源的影子價(jià)格分別為50、0和50元/kg，分別表示這三種資源的單位變化引起企業(yè)利潤的變化量。資源的影子價(jià)格是針對具體生產(chǎn)或具體企業(yè)而言的。從yi*在單純形表中的計(jì)算過程可知：（1）同一種資源在不同的生產(chǎn)條件或不同的范圍可能有不同的影子價(jià)格；（2）產(chǎn)品的市場價(jià)格變化，資源的影子價(jià)格也會發(fā)生變化；（3）資源的數(shù)量結(jié)構(gòu)不同，資源的影子價(jià)格也不同。影子價(jià)格對于擁有資源的決策者來說有著非常重要的作用

18、。具體有：（1）當(dāng)資源的市場價(jià)格低于影子價(jià)格時(shí)，可適量買進(jìn)該種資源，組織和增加生產(chǎn)；相反，資源的市場價(jià)格高于影子價(jià)格時(shí)，可以賣出資源而不安排生產(chǎn)或提高產(chǎn)品的價(jià)格；（2）要提高資源的影子價(jià)格，可以對生產(chǎn)工藝進(jìn)行革新，以降低這種資源的單耗，從而增加企業(yè)的利潤。（3）可以指導(dǎo)管理部門對緊缺資源進(jìn)行“擇優(yōu)分配”；（4）幫助預(yù)測產(chǎn)品的價(jià)格。買方要購入賣方的產(chǎn)品作為資源投入生產(chǎn)，要求其價(jià)格必須小于該產(chǎn)品作為自己最優(yōu)生產(chǎn)資源的影子價(jià)格，否則將無利可圖；賣方要求出售產(chǎn)品的價(jià)格必須大于自己的生產(chǎn)“成本”，否則，利益受到損失。因此，產(chǎn)品的價(jià)格應(yīng)在“成本”和影子價(jià)格之間。（5）影子價(jià)格的高低可以作為同類企業(yè)經(jīng)濟(jì)效益

19、的評估標(biāo)準(zhǔn)之一。二、任務(wù)的邊際成本對于目標(biāo)函數(shù)極小化約束條件為大等號的問題min z=CX，AXb，X0，其右端常數(shù)項(xiàng)可理解為需要完成的任務(wù)。因此，該類線性規(guī)劃一般為描述完成一定任務(wù)使耗費(fèi)的資源最小的問題。此時(shí)，其對偶問題的最優(yōu)解yi*(i=1,，m)表示第i種任務(wù)的邊際成本，即單位任務(wù)的增加引起的資源耗費(fèi)的增加量。例2.6 某工廠使用A、B兩種原材料生產(chǎn)甲、乙兩種產(chǎn)品。產(chǎn)品甲、乙的產(chǎn)量分別不小于100和160，每單位甲消耗1單位的原材料A，每單位乙消耗0.8單位的原材料A或1單位原材料B，原材料A、B的價(jià)格分別為1000元和800元每單位。問在滿足生產(chǎn)計(jì)劃的條件下，如何購買原材料使耗費(fèi)的資金

20、最?。咳魓1、x2分別表示原材料A、B的購買數(shù)量，則問題的線性規(guī)劃模型為min z=1000x1+800x2x1 1000.8x1 + x2 160x1、x20用大M法（極小化為標(biāo)準(zhǔn)形式）求解得問題的最優(yōu)單純形表如表25。 表25Cj100080000Mb CBXB x1 x2x3x4x51000x110-101100800x201-0.8-1-0.880z001640800-164000對偶問題最優(yōu)解y1*y2*從表中可知，對偶問題的最優(yōu)解為：y1*=1640，y2*=800，分別表示每增加一單位的產(chǎn)品甲和產(chǎn)品乙所增加的工廠的成本，即最優(yōu)購買決策條件下的甲、乙兩產(chǎn)品的邊際成本。三、對偶價(jià)格無

21、論對偶問題的最優(yōu)解表示的是資源的影子價(jià)格還是任務(wù)的邊際成本，只要為正，則表示右端常數(shù)項(xiàng)增加目標(biāo)函數(shù)值增加，為負(fù)則表示右端常數(shù)項(xiàng)增加目標(biāo)函數(shù)值減少。而對于極大化的問題，目標(biāo)函數(shù)值增加表明目標(biāo)函數(shù)得到改善，對于極小化的問題，目標(biāo)函數(shù)減少表明目標(biāo)函數(shù)得到改善。為了二者的統(tǒng)一，定義如下對偶價(jià)格。定義2.2 線性規(guī)劃問題某約束條件的右端常數(shù)項(xiàng)的單位增加量所引起的目標(biāo)函數(shù)的改善量稱為該右端常數(shù)項(xiàng)的對偶價(jià)格。因此，若對偶價(jià)格為正，則增加右端常數(shù)項(xiàng)，目標(biāo)函數(shù)值得到改善；若對偶價(jià)格為負(fù)，則增加右端常數(shù)項(xiàng)，目標(biāo)函數(shù)值將會“惡化”。根據(jù)該定義，對于極大化的問題，對偶價(jià)格就等于其對偶問題的最優(yōu)解；對于極小化問題，對偶

22、價(jià)格就等于其對偶問題最優(yōu)解的相反數(shù)。例如本節(jié)例2.4的極大化問題三個約束條件的對偶價(jià)格分別為50，0和50；本節(jié)例2.6的極小化問題兩個約束條件的對偶價(jià)格分別為1640和800；下面在舉一個含有等號約束的例子。例2.7 求下列線性規(guī)劃問題各約束條件的對偶價(jià)格 min z=2x1+3x2+4x3  x1 + x2 + x3 1202x1 + x2 + x3 60 x1 +2x2 + x3 =80x1、x2，x30用大M法（極小化為標(biāo)準(zhǔn)形式）求解得問題的最優(yōu)單純形表如表26。 表26Cj23400MMb CBXB x1 x2x3x4x5x6x70x2001/311/3-1/3-

23、1/3220/32x1101/30-2/32/3-1/340/33x4011/301/3-1/32/3100/3z007/301/31/3+M4/3+M-380/3對偶問題最優(yōu)解y1*y2*y3*+M故對偶問題的最優(yōu)解為y1*=0，y2*=1/3，y3*=4/3。由于是極小化問題，所以三個約束條件的對偶價(jià)格為對偶問題最優(yōu)解的相反數(shù)，即分別為0、1/3和4/3。即第二個約束條件的右端常數(shù)項(xiàng)增加1個單位，則目標(biāo)函數(shù)值“惡化”1/3個單位，即為380/3+1/3=381/3，若第二個約束條件的右端常數(shù)項(xiàng)減少一個單位，則目標(biāo)函數(shù)值“改善”1/3個單位，即為380/31/3=379/3。對于第一和第三個

24、約束條件可作同樣的分析。第四節(jié) 對偶單純形法一、對偶單純形法的基本思想定義2.3 設(shè)X（0）為線性規(guī)劃問題max z=CX，AX=b，X0的一個基本解，若對應(yīng)的檢驗(yàn)數(shù)j0（jJ），則稱X（0）為該線性規(guī)劃問題的一個正側(cè)解。相應(yīng)的基稱為正側(cè)基。正側(cè)解一般為非可行解，若正側(cè)解同時(shí)為可行解，則該正側(cè)解就是線性規(guī)劃問題的最優(yōu)解。由正側(cè)解的這一性質(zhì)，我們就有與單純形法基本思想對應(yīng)的對偶單純形法的基本思想。單純形法的基本思想是：從一基可行解（B-1b0）出發(fā)，在滿足可行解的基礎(chǔ)上，通過逐次基可行解的轉(zhuǎn)換，直至j0（jJ）成立，即達(dá)到可行的正側(cè)解，從而判斷是否得到最優(yōu)解或無最優(yōu)解。對偶單純形法的基本思想是：

25、從一正側(cè)解（j0（jJ）出發(fā)，在滿足正側(cè)解的基礎(chǔ)上，通過逐次基轉(zhuǎn)換，直至B-1b0成立，即達(dá)到滿足條件的正側(cè)解可行解，從而判斷是否得到最優(yōu)解或無最優(yōu)解。需要指出的是：對偶單純形法是求解線性規(guī)劃問題的另一種方法，而不是求解線性規(guī)劃對偶問題的單純形法。二、對偶單純形法用對偶單純形法求解線性規(guī)劃問題的一般步驟為：（1）尋找初始正側(cè)基，列對應(yīng)初始單純形表；（2）若右端常數(shù)項(xiàng)bi0，則已得到問題的最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)下一步；（3）確定出基變量。按minbi|bi<0，i=1，m=br，則br所在行對應(yīng)的變量xr為出基變量。若br所在行對應(yīng)的A陣中各元素arj0，則問題無可行解，停止計(jì)算。否則轉(zhuǎn)

26、下一步；（4）確定進(jìn)基變量。按=minj/arj|arj<0，jJ=k/ark，則對應(yīng)的變量xk為出基變量。（5）以ark為主元素，按原單純形法同樣方法進(jìn)行迭代計(jì)算，得到新的正側(cè)解，轉(zhuǎn)（2）。例2.8 用對偶單純形法求解下列線性規(guī)劃 min z=4x1+2x2+6x32x1 +4x2 +8x3 244x1 + x2 + 4x38x1、x2，x30解 將問題改寫成如下形式 max（z）=4x12x26x32x1 4x2 8x3 + x4 =244x1 x2 4x3 +x5 =8x1、x2，x3，x4，x50顯然，p4、p5可以構(gòu)成現(xiàn)成的單位基，此時(shí)，非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)數(shù)，因此

27、p4、p5構(gòu)成的就是初始正側(cè)基。整個問題的計(jì)算過程列在表27中。 表27Cj42600bCBXBx1x2x3x4x50x4-2-4-810-240x5-4-1-401-8z-4-2-6000-4/-2-2/-4-6/-1000-2x21/212-1/4060x5-7/20-2-1/41-2z-30-2-1/20-120-3/(-7/2)0-2/-2(-1/2)/(-1/4)0-2x2-310-1/214-6x37/4011/8-1/24z-1/200-1/4-1-32最后一個單純形表中，已得到一個可行的正側(cè)解，因而得到問題的最優(yōu)解為 X*=（0，4，4）T最優(yōu)值為z*=32對偶單純形法在以下情

28、況下較為方便。（1）對于形如min z=CX，AXb，X0，且C0的線性規(guī)劃問題。因?yàn)閷⑵涓膶憺閙ax (z) =CX，AX+XS=b，X0，則立即可以得到初始正側(cè)解； （2）當(dāng)變量多于約束條件時(shí)，對這樣的線性規(guī)劃問題用對偶單純形法計(jì)算可以減少計(jì)算工作量；（3）在靈敏度分析中，有時(shí)需要用對偶單純形法，可使問題的處理簡化。第五節(jié) 靈敏度分析前面討論線性規(guī)劃問題時(shí)，aij、bi、cj等都是常數(shù)，但實(shí)際上，這些系數(shù)往往是估計(jì)值或預(yù)測值或是目前值，隨著時(shí)間的推移，它們都可能會發(fā)生變化。其中，aij與企業(yè)技術(shù)水平有關(guān)，技術(shù)進(jìn)步可能引起其變化；bi與資源數(shù)量結(jié)構(gòu)有關(guān)；cj與市場有關(guān)，市場的波動可能引起其變

29、化。這些系數(shù)的變化，都會影響企業(yè)的決策。靈敏度分析就是分析這些因素中的一個或幾個的變化給生產(chǎn)決策帶來的影響。靈敏度分析的內(nèi)容是：（1）aij、bi、cj中一個或幾個發(fā)生某一具體變化時(shí)，線性規(guī)劃問題的最優(yōu)決策相應(yīng)會發(fā)生什么樣的變化；（2）aij、bi、cj在什么范圍內(nèi)變化，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變；靈敏度分析一般是在已得到線性規(guī)劃問題最優(yōu)基的基礎(chǔ)上進(jìn)行的?，F(xiàn)在假定一個線性規(guī)劃已經(jīng)求出其最優(yōu)解，如果它的一個或幾個系數(shù)有改變，沒有必要重新求解它，只需要看改變后的系數(shù)是否破壞了最優(yōu)性條件。如果最優(yōu)性條件仍然成立，說明最優(yōu)基的地位沒有變化；如果最優(yōu)性條件不成立了，說明原來的最優(yōu)基的地位已經(jīng)改變，

30、在這種情況下要繼續(xù)迭代，直至求出新的最優(yōu)基。再來觀察一下表22的單純形表。若表中的基B就是最優(yōu)基，現(xiàn)在討論線性規(guī)劃問題的各系數(shù)的變化會引起最優(yōu)單純形表的哪些部分改變。CCBCN0bCBXBXBXNXSCBXBIB-1NB-1B-1bz0CNCBB-1NCBB-1CBB-1b從表中不難看出：bi的改變只會引起B(yǎng)-1b的改變；cj的改變只會引起檢驗(yàn)數(shù)=（CNCBB-1N，CBB-1）的改變；aij的改變有兩種情況，若aij屬于N中某一非基向量中的一個元素，則其改變只會引起檢驗(yàn)數(shù)的改變；若aij屬于B中某一基向量中的一個元素，則aij的改變引起B(yǎng)-1的改變，從而引起檢驗(yàn)數(shù)（CNCBB-1N，CBB-

31、1）和右端常數(shù)項(xiàng)B-1b的同時(shí)改變。這些系數(shù)的改變可能會出現(xiàn)如表28中所列的情況，這些情況也有相應(yīng)的處理辦法。 表28原問題對偶問題結(jié)論或處理方法可行解可行解非可行解非可行解可行解非可行解可行解非可行解最優(yōu)基不變單純形法迭代求最優(yōu)解對偶單純形法迭代求最優(yōu)解引入人工變量，編制新的單純形表，求最優(yōu)一、目標(biāo)函數(shù)中價(jià)值系數(shù)cj的變化分析1若cj為非基變量的價(jià)格系數(shù)根據(jù)以上分析，此時(shí)cj的變化只會影響j的變化，因此設(shè) cjcj = cj +cj則 j= cj CBB-1pj = cj +cjCBB-1pj  = j +cj當(dāng) j0，即cjj 時(shí)，原線性規(guī)劃問題的最優(yōu)解不變；否則，需要將xj作為

32、進(jìn)基變量用單純形法迭代計(jì)算，求新的最優(yōu)解。例2.9 設(shè)某線性規(guī)劃問題的初始單純形表和最優(yōu)單純形表分別為 表29（初始單純形表）Cj54300bCBXBx1x2x3x4x50x411110600x52140180z543000 表210（最優(yōu)單純形表）Cj54300bCBXBx1x2x3x4x54x201-22-1405x1103-1120z00-4-3-1-260現(xiàn)在要問：（1）c3在什么范圍內(nèi)變化，表中最優(yōu)解不變？（2）c3從3變?yōu)?，求新的最優(yōu)解解（1）由于在最優(yōu)單純形表中，c3為非基變量的價(jià)格系數(shù)，因此其變化僅會影響到檢驗(yàn)數(shù)3=4，因此當(dāng)c33=4時(shí)，表中最優(yōu)解不變。（2）當(dāng)c3從3變?yōu)?/p>

33、8時(shí)，則表中的檢驗(yàn)數(shù)3從4變?yōu)?，即表中的最優(yōu)解將發(fā)生變化，用單純形法求解得到如表211中所示的新的最優(yōu)解。 表211Cj54800bCBXBx1x2x3x4x54x201-22-1405x1103-1120z001-3-1-2604x22/3104/3-1/3160/35x31/301-1/31/320/3z00-4-3-1-740/3即新的最優(yōu)解為X*=（0，160/3，20/3）T。2若ck為基變量的價(jià)格系數(shù)由于ck是向量CB的一個分量，所以當(dāng)ck改變時(shí)，可能使最優(yōu)單純形表中多個檢驗(yàn)數(shù)都受到影響。設(shè) ckck = ck +ck CB=（0，0，ck，0，0）即 CB= CB+CB這樣 j

34、= cjCB B-1pj     = cj(CB+CB)B-1pj   = cjCBB-1pjCBB-1pj   = j（0，ck，0）（1j，2j，mj）T從而 j= jckkj j=1，n式中 kj為最優(yōu)單純形表中，基變量xk所在行的第j個元素。要使最優(yōu)基不變，必須滿足 j=jckkj0 j=1，n當(dāng)kj>0時(shí) ckj / kj；當(dāng)kj<0時(shí) ckj / kj；因此有 即ck的變化范圍 ck，minckck，max或ck的變化范圍 ck+ck，minckck+ck，max當(dāng)ck或ck超過該范圍，則問題的最優(yōu)解將發(fā)生變化

35、，此時(shí)應(yīng)用單純形法計(jì)算得到新的最優(yōu)解。例2.10 計(jì)算表210中使最優(yōu)解不變的基變量價(jià)格系數(shù)c1和c2的變化范圍。解 對于c1有max4/3，1/1c1min3/1即 1c13或 4c18對于c2有max3/2c2min4/2，1/1即 3/2c21或 5/4c29二、約束條件中資源數(shù)量bk的變化分析bk的變化僅會影響最優(yōu)單純形表中的B-1b以及最優(yōu)值CBB-1b。設(shè) bkbk = bk +bk 令 b=（0，0，bk，0，0）T即 b=b+b這樣 B-1b=B-1（b+b）  =B-1b+B-1b又令 因此有 為使B的最優(yōu)基不變，必須有解此不等式組：當(dāng)ik>0時(shí)有 當(dāng)ik&l

36、t;0時(shí)有 綜合有 即bk的變化范圍 bk，minbkbk，max或bk的變化范圍 bk+bk，minbkbk+bk，max例2.11 某工廠在計(jì)劃期內(nèi)要安排甲、乙兩種產(chǎn)品，已知生產(chǎn)一件產(chǎn)品所消耗的A、B、C三種原材料的數(shù)量以及單位產(chǎn)品的利潤如下表所示： 表212產(chǎn)品單位消耗原材料甲乙資源限量（kg）ABC121311908045單位產(chǎn)品利潤（千元/件）54若x1、x2分別表示工廠生產(chǎn)甲、乙產(chǎn)品的數(shù)量，則使工廠獲得最大利潤的生產(chǎn)計(jì)劃數(shù)學(xué)模型為： max z=5x1+4x2  x1 +3x2 902x1  + x2 80  x1

37、0; + x2 45x1、x2，x30用單純形法求解該問題時(shí)，其初始單純形表和最優(yōu)單純形表分別如表213和314所示，試分析使最優(yōu)基不變的b3的變化范圍。 表213（初始單純形表）Cj54000bCBXBx1x2x3x4x50x313100900x421010800x51100145z540000 表214（最優(yōu)單純形表）Cj54000bCBXBx1x2x3x4x50x30012-5255x11001-1354x2010-1210z000-1-3-215解 由表213和表214可知，當(dāng)B=（p3，p1，p2）時(shí)，有 當(dāng)下式成立時(shí)，最優(yōu)基不變。即 255b30，35b30，10+b30

38、解不等式有 5b35此外，以B-1的第三列各元素去除最優(yōu)單純形表中右端常數(shù)項(xiàng)對應(yīng)各列，用公式可直接求出b3，即同樣可得 5b35因此，不影響最優(yōu)基的b3的變化范圍是40，50。三、技術(shù)系數(shù)aij的變化分析企業(yè)里設(shè)備、工藝、技術(shù)和管理等方面的改進(jìn)和提高，都可能引起實(shí)際問題的資源消耗量的改變，這些改變反映到線性規(guī)劃模型中就是技術(shù)系數(shù)aij的改變。這種靈敏度分析比較復(fù)雜，這里僅討論如下幾種情況。1非基變量xj的系數(shù)列向量pj的改變設(shè)列向量pj有改變量pj，即 pj=pj+pjpj的改變將影響到檢驗(yàn)數(shù)的改變，即j= cjCB B-1pj = cjCB B-1（pj+pj）  =jCB B-1

39、pj要使最優(yōu)基B的地位不變，應(yīng)有jCB B-1pj0因此，實(shí)際分析中，若某一個非基變量的系數(shù)列向量pj的改變，仍然滿足上述條件，則最優(yōu)單純形表中的最優(yōu)解仍然為最優(yōu)解；若pj的改變使上述條件不成立，則需要將對應(yīng)的變量xj作為進(jìn)基變量，用單純形法繼續(xù)迭代，求出新的最優(yōu)解。2基變量xj的系數(shù)列向量pj的改變在這種情況下，由于基B受到pj改變的影響，因而影響到單純形表的每一列，一般要重新迭代。 3增加新的變量生產(chǎn)上開發(fā)新產(chǎn)品，反映到線性規(guī)劃模型中就相當(dāng)于增加新的變量xj，并把新增加的變量所要消耗的各種資源量作為一列向量，代入原最優(yōu)單純形表中求新的最優(yōu)解。4增加新的約束條件生產(chǎn)上增加加工工序，反映在線性

40、規(guī)劃模型中即相當(dāng)于增加新的約束條件，對這種情況下的靈敏度分析，一般地可先將求出的最優(yōu)解代入新增加的約束條件，如果滿足該約束條件，則最優(yōu)解不變；否則，需將新增加的約束條件加到原先得到的最優(yōu)單純形表中，進(jìn)行調(diào)整求解。在迭代求解過程中根據(jù)需要用單純形法或?qū)ε紗渭冃畏ㄒ约耙肴斯ぷ兞康确椒ā＠?.12 在例2.11的生產(chǎn)計(jì)劃問題中：（1）若生產(chǎn)產(chǎn)品甲的工藝結(jié)構(gòu)發(fā)生了改進(jìn)，這時(shí)關(guān)于它的技術(shù)向量變?yōu)閜1=（1，2，1/2）T，試分析對原最優(yōu)計(jì)劃有什么影響；（2）若該廠除了生產(chǎn)前兩種產(chǎn)品外，擬開發(fā)新產(chǎn)品丙，已知產(chǎn)品丙每件消耗A、B、C原材料各為2、4、1kg，每件可獲利潤8千元。問該廠是否應(yīng)該生產(chǎn)該產(chǎn)品和生

41、產(chǎn)多少？解 （1）由于產(chǎn)品甲生產(chǎn)工藝的改進(jìn)，這樣原最優(yōu)單純形表中的第1列將會發(fā)生改變，具體為代入原最優(yōu)單純形表中得到 表215Cj54000bCBXBx1x2x3x4x50x35/4012-5255x15/4001-1354x2-1/210-1210將第1列化為單位向量，并用對偶單純形法迭代一次得到如表216所示的新的最優(yōu)生產(chǎn)計(jì)劃。 表216Cj54000bCBXBx1x2x3x4x50x30011-4-105x11004/5-4/5284x2010-3/58/524z000-8/5-12/5(-12/5)/-4b0x500-1/4-1/415/25x110-1/53/50304x2012/5

42、-1/5020z00-3/5-11/50-230即，工藝改進(jìn)后新的最優(yōu)生產(chǎn)計(jì)劃為甲、乙各生產(chǎn)30件和20件，利潤為230千元。（2）設(shè)新產(chǎn)品的產(chǎn)量為x3（件），其技術(shù)系數(shù)向量為p3=（2，4，1）T，由表214可求出3= c3CB B-1pj = 8（0，1，3）（2，4，1）T=1>0即安排生產(chǎn)產(chǎn)品丙是有利的。對應(yīng)x3在最優(yōu)單純形表中的列向量為代入到最優(yōu)表214中，并用單純形法迭代一次得新的最優(yōu)表217。 表217Cj540008bCBXBx1x2x3x4x5x30x30012-55255x11001-13354x2010-12210z000-1-31-2158x3001/52/5-1

43、155x110-3/5-1/520204x2012/5-1/50020z00-1/5-7/5-20-220由表217，得最優(yōu)解 X*=（20，20，5）T即該工廠生產(chǎn)產(chǎn)品甲、乙、丙分別為20，20，5件，可使工廠獲得最大利潤220千元。四、幾個系數(shù)同時(shí)變化的分析上面所述關(guān)于cj和bi的靈敏度分析，都是在其他條件不變，某一個單變量系數(shù)變化時(shí)的分析。所有以上的目標(biāo)函數(shù)系數(shù)及約束條件右端常數(shù)項(xiàng)的靈敏度計(jì)算公式只適用于單個系數(shù)變化的情況。當(dāng)兩個或更多的系數(shù)都發(fā)生變化時(shí)，采用所謂的百分之一百法則。百分之一百法則的基礎(chǔ)，是關(guān)于使最優(yōu)基不變的單個系數(shù)的變化范圍。即各單個系數(shù)的當(dāng)前值、下限值和上限值。對于給定

44、的線性規(guī)劃模型，這些計(jì)算均可借助于計(jì)算機(jī)軟件。目前，關(guān)于求解線性規(guī)劃問題的計(jì)算機(jī)軟件非常多，如芝加哥大學(xué)Linus E. Schrage開發(fā)的LINDO計(jì)算機(jī)軟件包的微機(jī)版本LINDO/PC；Microsoft Excel Solver等。利用這些軟件，很容易得到線性規(guī)劃問題的最優(yōu)解、各單個系數(shù)變化的上限值和下限值、各約束條件的對偶價(jià)格等。另外，在熟悉和掌握了線性規(guī)劃的求解方法和靈敏度分析的計(jì)算公式的基礎(chǔ)上，自己編制計(jì)算機(jī)軟件也不是件困難的事。百分之一百法則原理如下：（1）對于所有變化的目標(biāo)函數(shù)系數(shù)，當(dāng)其所有允許增加百分比和允許減少百分比之和不超過100%，則最優(yōu)解不變；（2）對于所有變化的右

45、端常數(shù)項(xiàng)，當(dāng)其所有允許增加百分比和允許減少百分比之和不超過100%，則對偶價(jià)格不變；其中：允許增加百分比=（變化值當(dāng)前值）/（上限當(dāng)前值）×100%允許減少百分比=（當(dāng)前值變化值）/（當(dāng)前值下限）×100%例2.13 計(jì)算例2.12中關(guān)于價(jià)格系數(shù)和右端常數(shù)項(xiàng)的單個系數(shù)變化的上限值與下限值以及右端常數(shù)項(xiàng)的對偶價(jià)格，并對多個系數(shù)變化進(jìn)行百分之一百分析。解 用本節(jié)所述計(jì)算公式或用有關(guān)計(jì)算機(jī)軟件計(jì)算得到例2.12的最優(yōu)解及相關(guān)指標(biāo)如下：目標(biāo)函數(shù)最優(yōu)值為：215變量 最優(yōu)解 檢驗(yàn)數(shù)  x1 35 0  x2 10 0約束 松弛/剩余變量 對偶價(jià)

46、格  1 25 0  2 0 1  3 0 3目標(biāo)函數(shù)系數(shù)范圍變量 下限 當(dāng)前值 上限  x1 4 5 8  x2 2.5  4 5右端常數(shù)項(xiàng)范圍約束 下限 當(dāng)前值 上限  1 65 90   無上限  2  67.5 80 90  3 40 45 50上述計(jì)算結(jié)果表明：在現(xiàn)有條件下，工廠生產(chǎn)甲產(chǎn)品35件，乙產(chǎn)品10件，工廠獲得最大利潤215千元；第一個約束條件的松弛變量為25，說明資源A有剩余，剩余量為25kg；第二、三個約束條件的松弛變量為零，說明資源B、C已用完。第一個約束條件的對偶價(jià)格為0，說明資源在一定的范圍內(nèi)變化，工廠的利潤不會發(fā)生變化；第二、三個約束條件的對偶價(jià)格分別為1和3，說明增加資源B或資源C，目標(biāo)函