管理運(yùn)籌學(xué)第04章對偶線性規(guī)劃與靈敏度分析

1、管理運(yùn)籌學(xué)第4章 對偶線性規(guī)劃與靈敏度分析對偶性是線性規(guī)劃最重要的內(nèi)容之一，也是線性規(guī)劃早期研究的最重要成果之一。每一個線性規(guī)劃問題必然有與之相伴而生的另一個線性規(guī)劃問題，其中一個問題稱為原問題，另一個稱為對偶問題。這兩個問題之間存在著非常密切的關(guān)系。本章主要涉及對偶的三個問題：一是給定了原問題，如何寫出其對偶問題；二是研究原問題和對偶問題之間的關(guān)系；最后給出解線性規(guī)劃的對偶單純形方法。4.1 原問題與對偶問題在對稱形式下，原問題與對偶問題有如下關(guān)系：原問題中求目標(biāo)函數(shù)極大值，對偶問題中為求目標(biāo)函數(shù)極小值；原總是中約束條件個數(shù)等于對偶問題中變量的個數(shù)，原問題中變量的個數(shù)等于對偶總是中的約束條件

2、個數(shù)；原問題中約束條件符號為，對偶問題中約束條件符號為；原問題目標(biāo)函數(shù)的系數(shù)是其對偶問題約束條件的右端項(xiàng)，而原問題約束條件的右端項(xiàng)則是其對偶問題目標(biāo)函數(shù)的系數(shù)。4.1 原問題與對偶問題但是，并非所有線性規(guī)劃都具有上述對稱形式，對于一般情況下線性規(guī)劃問題的對偶問題，可以分以下幾種情況來討論： 1. 等號約束問題【定理4.1】如果原始問題的約束條件是等式，則對偶問題中的變量無符號限制。2. 極大化目標(biāo)函數(shù)、約束條件為的問題【定理4.2】 如果極小化原始問題中的約束條件（不包括變量非負(fù)約束）為，則對偶問題中的變量具有非正（0）約束。4.1 原問題與對偶問題于是可得到下面的推論：【推論4.1】 如果原

3、始問題中的變量無符號限制，則對偶問題中的約束條件為等式約束。【推論4.2】 如果原始問題中的變量具有非正（0）約束，則極小化對偶問題的約束條件為約束。4.1 原問題與對偶問題為了更好地理解以上結(jié)論，給出如下例子。【例4-2】 寫出以下原始問題的對偶問題： max z=2x1-x2+4x3+x4 x1+3x2-x3+5x412s.t. -2x1-2x2+3x3-2x4=25 3x1+x2-2x3+x418 x10 x20 x3:unr x404.1 原問題與對偶問題極大化問題（max）極小化問題（min）約束aijxicjyj0變量aijxi=cjyj:unraijxicjyj0變量xi0aij

4、yjbi約束xi:unraijyj=bixi0aijyjbi 通過對稱形式和一般形式的討論，可以對原始問題和對偶問題之間的關(guān)系做出如下總結(jié)： 4.2 對偶問題的基本性質(zhì)1. 對稱性：對偶問題的對偶是原問題。設(shè)原始問題為：max z=CTXs.t. AXb (P) X0根據(jù)定義，對偶問題為：min =bTYs.t. ATYC (D) Y04.2 對偶問題的基本性質(zhì)2. 弱對偶性極小化原始問題的任一可行解的目標(biāo)函數(shù)值總是大于或等于極大化對偶問題的任一可行解的目標(biāo)函數(shù)值。也就是說，若 是原問題的可行解， 是對偶問題的可行解。則恒有： 。這就是弱對偶定理，其證明如下：證明：設(shè)原始問題為max z=CT

5、Xs.t.AXb (P) X0則對偶問題為：min =bTYs.t.ATYC (D) Y04.2 對偶問題的基本性質(zhì)3.最優(yōu)性如果XF和XF分別是原始問題和對偶問題的可行解，并且它們對應(yīng)的目標(biāo)函數(shù)值相等，則XF和XF分別是原始問題和對偶問題的最優(yōu)解。即可行解是最優(yōu)解時的性質(zhì)：設(shè)是原問題的可行解，是對偶問題的可行解，當(dāng)z=CTX= bTY =w時，X，Y是最優(yōu)解。證明如下：證明：設(shè)XF 是原問題的最優(yōu)解，YF 是其對偶問題的最優(yōu)解由弱對偶性， CTXFbTYF可知CTX CTXF bTYFbTY又由已知 z=CTX= bTY =w所以CTX =CTXF=bTYF=bTY即X也是原問題的最優(yōu)解，Y

6、也是其對偶問題的最優(yōu)解。4.2 對偶問題的基本性質(zhì)4.無界性如果原始問題和對偶問題中的任一個目標(biāo)函數(shù)無界，則另一個必定無可行解。注意這個性質(zhì)的逆命題不成立，即一個問題無可行解，不能推得另一個問題目標(biāo)函數(shù)無界。事實(shí)上，一對原始對偶問題都沒有可行解的情況是存在的。 4.2 對偶問題的基本性質(zhì)5.對偶定理若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們的最優(yōu)解的目標(biāo)函數(shù)值相等。證明：由于原問題及其對偶問題均具有可行解，根據(jù)弱對偶性，可以確定原問題的目標(biāo)函數(shù)具有上界，對偶問題的目標(biāo)函數(shù)具有下界，因此兩者均具有最優(yōu)解。設(shè)原問題的最優(yōu)基為B，對應(yīng)的基礎(chǔ)最優(yōu)解為X，通過單純形法可知，原問題的最優(yōu)

7、值為z=CTX= B-1b，且CT B-1A04.2 對偶問題的基本性質(zhì)對于對偶問題，令YT= B-1，則由上式可得AYTCT又由于Y是對偶問題的可行解，其對應(yīng)的目標(biāo)函數(shù)值w =YTb= B-1 b所以有 z=CTX= bYT = w可知，當(dāng)原問題為最優(yōu)解時，其對偶問題的解為可行解，且有z =w，由最優(yōu)性，這時兩者的解均為最優(yōu)解，且它們的目標(biāo)函數(shù)值相等。4.2 對偶問題的基本性質(zhì)6.互補(bǔ)松弛關(guān)系【定理4.3】 若X=(x1，x2，xn)T和Y=(y1，y2，ym)T分別是原始問題和對偶問題的最優(yōu)解，則有或用矩陣向量表示為4.2 對偶問題的基本性質(zhì)證明：設(shè)原始問題為max z=CTXs.t.AX

8、b (P)X0則對偶問題為：min z=bTYs.t.ATYC (D)Y04.2 對偶問題的基本性質(zhì)【推論4.3】 由于Xo，Yo分別是原始對偶問題的最優(yōu)解，因此在以上兩式中，有4.2 對偶問題的基本性質(zhì)【推論4.4】 若原始問題的最優(yōu)解Xo對于某一個約束i，有 則對偶問題最優(yōu)解中該約束對應(yīng)的對偶變量 Yio=0反之，若在對偶問題的最優(yōu)解中，第i個對偶變量 Yio0則原始問題最優(yōu)解對于相應(yīng)的第i個約束是等號約束，即 也就是說，原始問題最優(yōu)解中的第i個松弛變量等于0。4.2 對偶問題的基本性質(zhì)【定理4.4】 若向量 和 分別是原始問題和對偶問題的最優(yōu)解，當(dāng)且僅當(dāng)它們滿足以下三個條件：（1）X、X

9、S是原始問題 min z=CTX s.t.AX-Xs=b(P)X，Xs0的可行解。這個條件稱為原始可行條件。4.2 對偶問題的基本性質(zhì)（2）Y、Ys是對偶問題max z=bTYs.t. ATY+Ys=C (D) Y，Ys0的可行解。這個條件稱為對偶可行條件（Dual Feasible Condition，DFC）。（3）X、Xs、Y、Ys滿足 YTXs=0 YsTX=0這個條件稱為互補(bǔ)松弛條件（Complementary Slackness Condition，CSC）。4.2 對偶問題的基本性質(zhì)綜上所述，單純形法和Kuhn-Tucker條件的關(guān)系可敘述如下：在單純形迭代過程中，如果當(dāng)前基B是

10、原始可行基而不是最優(yōu)基，則（1）原始問題相應(yīng)的解X、Xs滿足原始可行條件；（2）對偶問題相應(yīng)的解YT=CBTB-1、YsT=CT-YTA中至少有一個不滿足對偶可行條件；（3）X、Xs、Y、Ys在單純形疊代的每一步，都滿足互補(bǔ)松弛關(guān)系。當(dāng)B不僅可行，而且是最優(yōu)基時，對偶問題相應(yīng)的解YT=CBTB-1、YsT=CT-YTA才滿足對偶可行條件。因此，可以把單純形法看成在原始可行條件和互補(bǔ)松弛條件得到滿足的條件下，不斷改進(jìn)對偶可行條件的過程，一旦三個條件都得到滿足，也就得到了最優(yōu)解。4.2 對偶問題的基本性質(zhì)7. 互補(bǔ)基解線性規(guī)劃的原問題及其對偶問題之間存在一對互補(bǔ)的基解，其中原問題的松馳變量對應(yīng)對偶

11、問題的變量，對偶問題的剩余變量對應(yīng)原問題的變量；這些互相對應(yīng)的變量如果在一個問題的解中是基變量，則在另一問題的解中是非基變量； 將這對互補(bǔ)的基解分別代入原問題和對偶問題的目標(biāo)函數(shù)有z=y。證明：因?yàn)閆j -Cj =CBB-1Pj - Cj =YT Pj - Cj所以，YT Pj -（Zj -Cj）= Cj也就是 -（Zj -Cj）= Cj4.3 對偶單純形法由上一節(jié)知道，線性規(guī)劃取得最優(yōu)解的充分必要條件是原始可行、對偶可行和互補(bǔ)松弛條件同時滿足。同時，也曾指出，單純形迭代過程實(shí)際上是在滿足原始可行條件和互補(bǔ)松弛條件的基礎(chǔ)上，不斷改進(jìn)對偶可行性的過程，一旦對偶可行條件得到滿足，就得到了最優(yōu)解。對

12、偶單純形法則是從另一角度來進(jìn)行的。對偶單純形法在迭代過程中保持對偶可行條件和互補(bǔ)松弛條件滿足，并且在迭代過程中不斷改進(jìn)原始可行條件。一旦原始可行條件得到滿足，也就求得了最優(yōu)解。為了說明對偶單純形法原理，先建立有關(guān)概念和定理。4.3 對偶單純形法【定義4.1】 （對偶可行基）設(shè)B為原始問題的一個基，若XT=CBTB-1是對偶問題的可行解，則稱B為原始問題的對偶可行基?！径ɡ?. 5】 若基B既是原始問題的可行基，又是原始問題的對偶可行基，則B必定是原始問題的最優(yōu)基。證明：因?yàn)锽是原始問題的可行基，因此4.3 對偶單純形法同時因?yàn)锽是對偶可行基，根據(jù)對偶可行基的定義，XT=CBTB-1滿足對偶問題

13、的約束條件，即XTACTXT0或：CBTB-1A-CT0T-CBTB-10T以上兩個條件，就是：zjcj0,j=1, 2, , n, n+1, , n+m因此，B是原始問題的最優(yōu)基。4.3 對偶單純形法對偶單純形法的計算步驟如下：（1）確定換出基的變量：存在小于零的bi 時，令 br =min bi ，其對應(yīng)變量xr 為換出基的變量（2）確定換入基的變量：為使迭代后表中第r行基變量為正值，因而只有對應(yīng)rj 0（j=m+1，n）的非基變量才可以考慮作為換入基的變量；為使迭代后表中對偶總是的解仍為可行解，令：稱r，S 為主元素，xs 為換入基的變量。4.3 對偶單純形法（3）用換入變量替換換出變量

14、，得到一個新的基。用新的基再檢查是否所有bi（i=1，2，m，）。如果是，找到了問題的最優(yōu)解，如果否，回到第一步再重復(fù)計算。由對偶問題的基本性質(zhì)知，當(dāng)對偶問題存在可行解時，原問題可能存在可行解，也可能無可行解，對出現(xiàn)后一種情況的判別準(zhǔn)則為：對br 0，而對所有j=1，n，有rj 0。因?yàn)樵谶@種情況下，如把表中第r行的約束方程列出有因rj 0（j=m+1，n），又br 0時，有 ，這表明生產(chǎn)過程中如果某種資源bi 未得到充分利用時，該種資源的影子價格為0；又當(dāng)資源的影子價格不為0時，表明該種資源在生產(chǎn)中已消耗完畢。從影子價格的含義上再來考察單純形法的計算。4.4 線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋（4）

15、記 ，式中 代表第j種產(chǎn)品的產(chǎn)值， 是生產(chǎn)該種產(chǎn)品所消耗各種資源的影子價格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品產(chǎn)值大于隱含成本時，表明生產(chǎn)該項(xiàng)產(chǎn)品有利，可在計算中安排，否則用這些資源來生產(chǎn)別的產(chǎn)品更為有利，就不在生產(chǎn)計劃中安排。這就是單純形法中各個檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。（5）一般講，對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當(dāng)估價，這種做人直接涉及資源的最有效利用。4.4 線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋4.4.2 互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋互補(bǔ)松弛關(guān)系在經(jīng)濟(jì)學(xué)中應(yīng)用也十分廣泛，尤其是結(jié)合線性規(guī)劃問題的對偶形式，更能體現(xiàn)線性規(guī)劃模型和實(shí)際應(yīng)用之間的關(guān)系。在考慮互補(bǔ)松弛條

16、件的時候，一般會考慮以下幾種情形：（1）若在最優(yōu)生產(chǎn)計劃下，第i種設(shè)備的能力大于這種設(shè)備實(shí)際耗用，或者說第i種設(shè)備能力有剩余，這種設(shè)備的微小增加對利潤沒有影響，按邊際貢獻(xiàn)的概念，有4.4 線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋在這種情況下，原問題最優(yōu)解中會有：在這種情況下，第i種設(shè)備開工的機(jī)會成本小于實(shí)際成本，松弛變量xm+j0，對降低總成本來說，這種設(shè)備不開工更為有利，即Yi=0。于是互補(bǔ)松弛關(guān)系ixm+j=0成立。反之，如果在最優(yōu)解中，某一種設(shè)備開工，即Yi0，可以肯定，這種設(shè)備的實(shí)際成本與機(jī)會成本相等，即可以斷定這種設(shè)備能力沒有剩余, 即松弛變量xm+j=0，從而同樣滿足互補(bǔ)松弛條件Yixm+j=0

17、也成立。4.4 線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋（2） 如果在最優(yōu)設(shè)備運(yùn)行計劃下，第i種產(chǎn)品的實(shí)際生產(chǎn)量超過需求量，也就是說某種產(chǎn)品的機(jī)會成本高于這種產(chǎn)品的利潤，此時有：而松弛變量Yn+i0這時再增加一個單位需求，不會影響設(shè)備運(yùn)行計劃，即對最小成本沒有影響，在這種情況下，最優(yōu)解中這種產(chǎn)品一定不會安排生產(chǎn)，因此有即影子價格等于0。于是互補(bǔ)松弛關(guān)系Yn+ixi=0成立。4.4 線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋反之，如果某一種產(chǎn)品需求的影子價格xi0，這時產(chǎn)品需求每增加一個單位將會引起總成本zo的增加，這說明實(shí)際生產(chǎn)這種產(chǎn)品的數(shù)量恰等于需求量，即或松弛變量Yn+i=0，于是互補(bǔ)松弛關(guān)系Yn+ixi=0成立。4.

18、4 線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋4.4.3 最大利潤問題以及對偶問題的經(jīng)濟(jì)解釋各種設(shè)備能力的邊際利潤率為： 由此可知，對偶問題最優(yōu)解中對偶變量xio(i=1,2,m)的值就是相應(yīng)設(shè)備的能力對總利潤的邊際貢獻(xiàn)。xio也成為相應(yīng)設(shè)備能力約束的影子價格，xio越大，表明相應(yīng)的設(shè)備能力每增加一個單位，引起總利潤的增加越大，也就是說，相對于最優(yōu)生產(chǎn)計劃來說，這種設(shè)備能力比較緊缺；xio較小，表明設(shè)備能力相對不緊缺；xio=0，說明在最優(yōu)生產(chǎn)計劃下第I種設(shè)備能力有剩余。4.4 線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋4.4.4 關(guān)于弱對偶定理的經(jīng)濟(jì)學(xué)解釋弱對偶定理說明了這樣一個事實(shí)：極大化原始問題的任一可行解的目標(biāo)函數(shù)值

19、總是小于或等于極小化對偶問題的任一可行解的目標(biāo)函數(shù)值。對于最大利潤問題，定理2.4的形式成為CTXYTAXYTb上式種左邊的不等式，是由于某些產(chǎn)品的利潤率和機(jī)會成本不相等引起的，即CTYTA。當(dāng)取得最優(yōu)解時，由于互補(bǔ)松弛條件的作用，凡機(jī)會成本和利潤率不相等的產(chǎn)品都將不安排生產(chǎn)，因而使得不等式成為等式。4.4 線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋右邊的不等式是由于某些設(shè)備的實(shí)際耗用小于設(shè)備的實(shí)際能力引起的，即AXb同樣由于互補(bǔ)松弛條件，實(shí)際耗用和能力不等的這些設(shè)備，影子價格都等于零，從而使右邊的不等式也成為等式。這樣，當(dāng)原始和對偶問題都取得最優(yōu)解時，有CTX=YTAX=YTb4.4 線性規(guī)劃對偶問題的經(jīng)濟(jì)

20、解釋4.4.5 經(jīng)濟(jì)解釋的例子 【例4-5】 某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如表4-3所示，用線性規(guī)劃制訂使總利潤最大的生產(chǎn)計劃。4.4 線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋 【例4-6】 求解表4-4中的利潤最大問題：4.4 線性規(guī)劃對偶問題的經(jīng)濟(jì)解釋由此可以清楚地看出，資源剩余量和影子價格之間以及“機(jī)會成本利潤率”和產(chǎn)品產(chǎn)量之間的互補(bǔ)松弛關(guān)系（表中箭頭表示“一個變量大于零，導(dǎo)致另一個變量等于零”的互補(bǔ)松弛關(guān)系）?？梢钥闯鲎顑?yōu)解中產(chǎn)品不安排生產(chǎn)的原因是這種產(chǎn)品的機(jī)會成本高于利潤率。一般

21、來說，一種產(chǎn)品在最優(yōu)解中是否安排生產(chǎn)，不僅與這種產(chǎn)品的利潤率有關(guān)，還與這種產(chǎn)品對資源的消耗以及各種資源的緊缺程度有關(guān)。而線性規(guī)劃模型，正是提供了對以上諸多因素進(jìn)行系統(tǒng)分析的工具。4.5 靈敏度分析靈敏度分析是指對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。在以前討論線性規(guī)劃問題時，假定 都是常數(shù)。但實(shí)際上這些系數(shù)往往是估計值和預(yù)測值。如市場條件一變， 值就會變化； 往往是因工藝條件的改變而改變； 是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。因此提出這樣兩個問題：（1） 當(dāng)這些參數(shù)有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化； 或者這些參數(shù)在什么范圍內(nèi)變化時，線性規(guī)劃

22、問題的最優(yōu)解不變。（2）當(dāng)線性規(guī)劃問題增加一個新的變量或新的約束，如何在原來最優(yōu)解的基礎(chǔ)上獲得新的最優(yōu)解。這就是靈敏度分析所要解決的問題。4.5 靈敏度分析靈敏度分析的步驟如下：（1）將參數(shù)的改變計算反映到最終單純形表上：按下列公式計算出由參數(shù) 的變化而引起的最終單純形表上有關(guān)數(shù)字的變化：（2）檢查原問題是否仍為可行解；（3）檢查對偶問題是否仍為可行解；4.5 靈敏度分析（4）按下表所列情況得出結(jié)論和決定繼續(xù)計算的步驟原問題對偶問題結(jié)論和決定繼續(xù)計算的步驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解仍為問題最優(yōu)解用單純形法繼續(xù)迭代求最優(yōu)解用對偶單純形表繼續(xù)迭代求最優(yōu)解引進(jìn)人工變量，

23、編制新的單純形表，重新計算4.5 靈敏度分析4.5.1 目標(biāo)函數(shù)系數(shù)C的變化范圍C中元素cj的變化范圍與相應(yīng)的變量xj是基變量還是非基變量有所不同，下面分別就這兩種情況來討論。m個基變量xBr（r=1,2,m）檢驗(yàn)數(shù)為：4.5 靈敏度分析n-m個非基變量xj的檢驗(yàn)數(shù)為：設(shè)某一個基變量xB在目標(biāo)函數(shù)中的系數(shù)為cB， 當(dāng)這個基變量xB的系數(shù)cB 變化成為cB=cB+ 時，m個基變量xBr在目標(biāo)函數(shù)中的系數(shù)為：即基變量xB在目標(biāo)函數(shù)中的系數(shù)cB的變化，在最優(yōu)解中只會影響這個基變量的檢驗(yàn)數(shù)，其他基變量的檢驗(yàn)數(shù)不會變化。如果檢驗(yàn)數(shù)zB-cB-0，則原來的最優(yōu)基仍保持為最優(yōu)基，如果檢驗(yàn)數(shù)zB-cB-0，則

24、原來的最優(yōu)基不再是最優(yōu)基，新的最優(yōu)基可以通過將xB進(jìn)基，并進(jìn)行后續(xù)的單純形迭代，得到新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析設(shè)某一個非基變量xk在目標(biāo)函數(shù)中的系數(shù)為ck，當(dāng)這個非基變量xk的系數(shù)ck 變化成為ck=ck+ 時，由上式可知，對基變量的檢驗(yàn)數(shù)沒有影響，所有基變量的檢驗(yàn)數(shù)仍為0。當(dāng)這個非基變量xk的系數(shù)ck 變化成為ck=ck+ 時，n-m個非基變量xj在目標(biāo)函數(shù)中的系數(shù)為：即非基變量xk在目標(biāo)函數(shù)中的系數(shù)ck的變化，在最優(yōu)解中只會影響這個非基變量在目標(biāo)函數(shù)中的系數(shù)，其他非基變量的系數(shù)不會變化。如果檢驗(yàn)數(shù)zk-ck-0，則原來的最優(yōu)基仍保持為最優(yōu)基，如果檢驗(yàn)數(shù)zk-ck-0，則原來的最

25、優(yōu)基不再是最優(yōu)基，新的最優(yōu)基可以通過將xk進(jìn)基，并進(jìn)行后續(xù)的單純形疊代，得到新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析 【例4-7】 線性規(guī)劃問題為： max z=2x1-x2+x3 x1+x2+x36 s.t. -x1+2x24 x1,x2,x30 求c2=-1在什么范圍內(nèi)變化，原來的最優(yōu)基保持不變；當(dāng)c2=3時，最優(yōu)基是否變化，如果變化，求新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析 4.5.2 右邊常數(shù)b的靈敏度分析當(dāng)右邊常數(shù)向量b發(fā)生變化，成為b時，對變量的檢驗(yàn)數(shù)沒有影響，而單純形表中的右邊常數(shù)將變成 。即右邊常數(shù)向量的變化只會影響最優(yōu)基的原始可行性而不會影響其對偶可行性。當(dāng)變化以后的 時，原來

26、的最優(yōu)基仍為最優(yōu)基，否則，原來的基成為對偶可行基但不是原始可行基，這時要用對偶單純形法求得新的最優(yōu)基。4.5 靈敏度分析 【例4-8】 對以下線性規(guī)劃問題中第一個約束右邊常數(shù)b1=9進(jìn)行靈敏度分析。 max z=-x1-x2+4x3 x1+x2+2x39 s.t. x1+x2-x32 -x1+x2+x34 x1,x2,x304.5 靈敏度分析4.5.3 增加一個新的變量當(dāng)前最優(yōu)基是B。設(shè)新增加的變量xj在目標(biāo)函數(shù)中的系數(shù)為cj，在約束中的系數(shù)向量是aj，計算 ， 在原單純形表中增加一個新的變量以及新的一列，將以上系數(shù)置于原單純形表中，構(gòu)成新的單純形表。若新變量的檢驗(yàn)數(shù)zj-cj0，則原來的基仍

27、為最優(yōu)基，原來的基變量以及基變量的值保持不變，新的變量xj=0是非基變量。否則xj進(jìn)基，用單純形法繼續(xù)運(yùn)行，直至獲得新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析【例4-9】線性規(guī)劃問題maxz=2x1-x2+x3 x1+x2+x36s.t. -x1+2x24 x1,x2,x30中，增加一個新的變量x6，它在目標(biāo)函數(shù)中的系數(shù)c6=-1，在約束條件中的系數(shù)向量為 ，求新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析4.5.4 增加一個新的約束增加一個新的約束以后，如果原來的最優(yōu)解滿足新的約束，則原來的最優(yōu)解仍是新問題的最優(yōu)解，否則，最優(yōu)解將發(fā)生變化。 【例4-10】 設(shè)線性規(guī)劃問題為 max z=2x1-x2+x

28、3 x1+x2+x36 s.t. -x1+2x24 x1,x2,x304.5 靈敏度分析列出原問題的最優(yōu)單純形表：增加一個約束-x1+2x22，求新的最優(yōu)基和最優(yōu)解。4.5 靈敏度分析4.5.5 約束矩陣中系數(shù)的靈敏度分析1. A矩陣中非基變量系數(shù)的靈敏度分析非基變量xj對應(yīng)的非基列向量aj中元素的變化，只會影響這個非基變量在目標(biāo)函數(shù)中的系數(shù)而且，由于列向量aj不在基B中，因此aj中元素的變化不會影響 。當(dāng)aj中的第r個元素arj變成arj=arj+時，變量xj的檢驗(yàn)數(shù)為4.5 靈敏度分析當(dāng)基的對偶可行性保持不變，由此可以得到的變化范圍?！纠?-11】 在例4-4max z=-x1-x2+4x

29、3 x1+x2+2x39s.t. x1+x2-x32 -x1+x2+x34 x1,x2,x30中，對變量x2在第一個約束中的系數(shù)a12=1進(jìn)行靈敏度分析。4.5 靈敏度分析2. A矩陣中基變量系數(shù)的靈敏度分析要象非基變量在約束矩陣中的系數(shù)一樣，來確定基變量在約束條件中系數(shù)的變化范圍，是十分困難的，在這里不作討論。對于基變量在約束條件中的系數(shù)，僅考慮當(dāng)其中一個元素變化時如何求得新的最優(yōu)解?！纠?-12】 對于例4-7中的線性規(guī)劃問題:max z=2x1-x2+x3 x1+x2+x36s.t. -x1+2x24 x1,x2,x30已經(jīng)得到它的最優(yōu)單純形表。其中，x1是基變量，當(dāng)x1在約束條件中的系

30、數(shù)向量 變?yōu)?時，求新的最優(yōu)解。4.5 靈敏度分析當(dāng)約束條件右端項(xiàng)連續(xù)變化時，其參數(shù)線性規(guī)劃的形式為：式中 為原線性規(guī)劃問題的資源向量， 為變動向量， 為參數(shù)。4.5 靈敏度分析參數(shù)線性規(guī)劃問題的分析步驟為：（1）令 =0求解得最終單純形表；（2）將 或 項(xiàng)反映到最終單純形表中；（3）隨 值的增大或減小，觀察原問題或?qū)ε紗栴}，一是確定表中現(xiàn)有解（基）允許 值的變動范圍，二是當(dāng) 值的變動超出這個范圍時，用單純形法或?qū)ε紗渭冃畏ㄇ笕⌒碌慕?；?）重復(fù)第3步，一直到 繼續(xù)增大或減小時，表中的解（基）不再出現(xiàn)變化時為止。4.5 靈敏度分析【例4-13】 分析 值變化時，下述線性規(guī)劃問題最優(yōu)解的變化。4.6線性規(guī)劃問題算法簡要介紹已經(jīng)知道，解決同一種問題可以有多個算法，比較和衡量這些算法的好壞通常采納的主要標(biāo)準(zhǔn)是看這種方法解決該問題所花費(fèi)時間。但是一個算法的執(zhí)行時間與很多因素有關(guān)，首先與所使用計算機(jī)的性能有關(guān)，其次與需要求解的具體問題有關(guān)，為了使衡量算法的好壞有一個比較科學(xué)客觀的標(biāo)準(zhǔn)，