廈門大學運籌學2

第二章對偶理論與靈敏度分析

在這一章中，我們將通過舉例來說明線性規(guī)劃對偶問題的提出并說明它的經(jīng)濟意義；由此來闡述它們兩者之間的關系。進一步來探討如何求一個線性規(guī)劃問題的對偶問題、以及線性規(guī)劃與它的對偶問題之間的關系、對偶單純形算法以及對線性規(guī)劃問題解的變化的進一步討論（即靈敏度分析和參數(shù)規(guī)劃等等）。第一節(jié)對偶問題的提出在第一章第一節(jié)的例1中，我們討論了工廠生產(chǎn)計劃模型及其解法，現(xiàn)從另一個角度來討論這個問題。假設該工廠的決策者決定不生產(chǎn)產(chǎn)品I、II，而將其所有資源出租或出售。這時，工廠的決策者就要考慮給每種資源進行定價的問題。設用

y1、y2、y3

分別表示出租單位設備臺時的租金和出讓單位原材料A、B

的附加費。作決策時，需要如下的比較：若一個單位設備臺時和四個單位原材料A可以生產(chǎn)一件產(chǎn)品I，可獲利2元，那么生產(chǎn)每件產(chǎn)品I的設備臺時和原材料出租和出讓的所有收入應不低于生產(chǎn)一件產(chǎn)品I的利潤。這就有：

y1+4y2

2；對于產(chǎn)品II同理有：2y2+4y3

3；把工廠所有設備臺時和資源都出租和出讓，其收入應為：w=8y1+16y2+12y3。從工廠的決策者來看，當然希望w

的值越大越好；但從接受者的角度來看，他支付的越少越好。所以工廠決策者只能在滿足所有產(chǎn)品的單位利潤條件下，使其總收入盡可能地小，才能實現(xiàn)工廠決策者的意愿。為此需要解如下的線性規(guī)劃問題：我們稱這個線性規(guī)劃問題為例1線性規(guī)劃問題（我們稱為原問題）的對偶問題。根據(jù)上述例題可見，對于形如如下形式的線性規(guī)劃問題：我們可以馬上得出它的對偶問題：其中：AT、bT

分別是原線性規(guī)劃問題中的約束條件矩陣A的轉置矩陣與約束條件中右邊列向量的轉置(即為行向量)。從以上的線性規(guī)劃問題和其對偶問題中，我們可以得出：原問題的約束條件的個數(shù)m

就是對偶問題的變量的個數(shù)；原問題的變量的個數(shù)n

就是對偶問題的約束條件的個數(shù)；若原問題的目標函數(shù)是Max型，則對偶問題的目標函數(shù)必是Min型。它們二者的最優(yōu)目標函數(shù)值相等。二、對偶問題的經(jīng)濟解釋——影子價格設B

是線性規(guī)劃問題{MaxZ=CTX|AX

b，X0}的最優(yōu)基，則該線性規(guī)劃問題的最優(yōu)解為(B-1b，0)T，其對應的目標函數(shù)最優(yōu)值則為：Z*=CTB-1b=(Y*)b，其中：Y*=CTB-1(我們稱為單純形乘子)由此可得：所以變量的經(jīng)濟義是在其它條件不變的情況下，第i種資源的變化所引起的目標函數(shù)最優(yōu)值的變化。由第一章的例1的最終計算表表1—7可見：這說明，在其它條件不變的情況下，機器臺時增加一臺時，該廠按最優(yōu)計劃安排生產(chǎn)可多獲利1.5元，原材料A

每增加一公斤，可多獲利0.125元，原材料B每增加一公斤，對獲利沒有影響。從上圖我們可以看到：設備每增加一臺時，代表約束條件的直線就由移至

，相應地最優(yōu)解由點A=(4，2)移到點B=(4，2.5)，目標函數(shù)值Z=24+32.5=15.5，即比原來的增大1.5。又若原材料A

增加一公斤，代表約束條件的直線就由

移至'，相應地最優(yōu)解由點A=(4，2)移到點B=(4.25，1.875)，目標函數(shù)值Z=24.25+31.875=14.125，即比原來的增大0.125。原材料B

增加一公斤時，該約束條件的直線由

移至

‘，這時的最優(yōu)解不變。

yi

的值代表對第i

種資源的估價。這種估價是針對具體產(chǎn)品而存在的一種特殊價格，我們稱它為“影子價格”。在該廠現(xiàn)有資源和現(xiàn)有生產(chǎn)方案的條件下，設備的每小時出租費為1.5元，一公斤原材料A

的出讓費為除成本外再附加0.125元，一公斤原材料B

可按原成本出讓，這時該廠的收入與自己組織生產(chǎn)時獲利相等。影子價格隨具體情況而異。在完全市場經(jīng)濟的條件下，當某種資源的市場價格低于影子價格時，企業(yè)應買進該資源用于擴大再生產(chǎn)；而當某種資源的市場價格高于影子價格時，則企業(yè)的決策者應把已有的資源賣出，這時企業(yè)的獲利比由自己生產(chǎn)的還高。可見，影子價格對市場有調節(jié)作用。下面再從另一個角度來討論該問題：從第一章第三節(jié)得到的檢驗數(shù)的表達式是CNT-CBTB-1N

與0–CBTB-1（松弛變量對應的檢驗數(shù)）。當滿足條件：CNT-CBTB-1N

0，–CBTB-1

0(2.1)這表示線性規(guī)劃問題已得到最優(yōu)解?？梢?2.1)式是作為得到最優(yōu)解的條件。引進記號YT=CBTB-1，稱為單純形乘子。由(2.1)式，可知對于最優(yōu)解所對應的單純形表有Y0。對應于基變量XB

的檢驗數(shù)是0，它是CBT-CBTB-1B=0。包括基變量在內(nèi)的所有檢驗數(shù)可用CT-CBTB-1A

0表示。由此可以得到CT-YTA

0即ATY

C。由于-YT=-CBTB-1，將此式兩邊同時右乘于b

得到：-YTb=-CBTB-1b即：YTb=CBTB-1b=Z綜合1、2、3的討論，我們可以得到另一個線性規(guī)劃問題：(2.2)稱此線性規(guī)劃問題為原線性規(guī)劃問題{MaxZ=CTX|AX

b，X0}的對偶線性規(guī)劃問題。從這兩個規(guī)劃問題的表達式可以看出，只要根據(jù)原線性規(guī)劃問題的系數(shù)矩陣A、C、b，就可以寫出它的對偶問題。

第二節(jié)線性規(guī)劃問題的對偶理論以上討論可以直觀地了解到原線性規(guī)劃問題與對偶問題之間的關系，這一節(jié)將從理論上進一步討論線性規(guī)劃問題的對偶問題。2.1原問題與對偶問題的關系

由第一節(jié)的討論，如下形式的線性規(guī)劃問題的對偶問題是(2.2)(2.3)我們稱(2.3)與(2.2)是原問題與對偶問題的標準形式。對其他形式的原問題的對偶問題，我們可進行如下分析：首先我們可以總結得出：

1.線性規(guī)劃原問題的約束條件的個數(shù)m，就是其對偶問題的變量的個數(shù)；原問題的變量個數(shù)n，就是其對偶問題的約束條件的個數(shù)。

在原問題目標函數(shù)為極大化（Max）的條件下有：

2.若原問題的第i個約束條件是“”，則對偶問題的第i個變量yi

0；原問題的第i個約束條件是“”，則對偶問題的第i個變量yi

0（0

i

m）。

證明：對于“”約束條件，由標準型(2.3)與(2.2)可知：

yi

0，0

i

m；對于“”約束條件，設：

ai1x1+ai2x2+···+ainxn

bi

將上式兩邊同乘以（-1）得：

（-ai1x1）+（-ai2x2）+···+（-ainxn）

-bi

利用標準型對偶關系可知原問題的對偶問題是：另–yi/=yi，則yi

0，上述問題變成：

3.若原問題的第i個約束條件是“=”，則對偶問題的第i個變量yi

無約束。

證明：對于“=”約束條件，設：ai1x1+ai2x2+···+ainxn

=bi

則此式等價于ai1x1+ai2x2+···+ainxn

bi

-ai1x1

-

ai2x2

-

···-

ainxn

-bi

利用標準型對偶關系可知原問題的對偶問題是：令yi=yi/-yi//

，則顯然yi

無非負限制，上述問題變成如下形式：

4.若原問題的第j

個變量xj

0，則對偶問題的第j

個約束條件為“”型；若原問題的第j

個變量xj

0，則對偶問題的第j

個約束條件為“”型。

證明：對于xj

0，則由標準型(2.3)與(2.2)可知對偶問題的第j

個約束條件為“”型；對于xj

0，問題，令：

xj/=-xj，則xj/

0，原問題變成：其對偶問題變?yōu)椋杭礊椋?/p>

5.若原問題的第j

個變量xj

無約束，則其對偶問題的第j

個約束條件為“=”號。

證明：假設xj

無約束，令xj=xj/-xj//

，則原問題和對偶問題分別為如下形式：原問題：對偶問題：即：綜合1、2、3、4、5點，線性規(guī)劃問題與其對偶問題的關系其變換形式可歸結為如下表2—1：

表2—1原問題對偶問題目標函數(shù)（maxZ）目標函數(shù)（minW）約束條件個數(shù)m

個對偶變量個數(shù)m

個約束條件為“”型對偶變量為“0”約束條件為“”型對偶變量為“

0”約束條件為“=”型對偶變量為無約束變量個數(shù)為n

個約束條件個數(shù)為n

個變量為“0”約束條件為“”型變量為“

0”約束條件為“”型變量為無約束約束條件為“=”型下面舉一例說明如何利用以上規(guī)則來求一個線性規(guī)劃問題的對偶問題。

例1試求如下線性規(guī)劃問題的對偶問題

解：設對應于約束條件(1)，(2)，(3)的對偶變量分別為y1y2，y3，則由表2—1中原問題與對偶問題的對應關系，可以直接寫出上面問題的對偶問題，它是：

2.2對偶問題的基本定理

1.對稱性：線性規(guī)劃問題的對偶問題的對偶是原問題。

證明：設原問題是：maxZ=CTX；AX

b；X0。它的對偶問題是：minW=bTY；ATY

C；Y0。將此對偶問題作形式上的變換，等價于：

max(-W)=-bTY；-ATY

-C；Y0；這個問題的對偶問題是：

minZ/=-CTX；-AX

-b；X0；即：max(-Z/)=CTX；AX

b；X0;也就是原問題。

2.弱對偶性：假如X*與Y*分別是原問題與對偶問題的可行解。則必有：CTX*

bTY

*。

證明：假設原問題與對偶問題分別是(2.3)與(2.2)形式，因為X*

是原問題的可行解，所以滿足約束條件，即：

AX*

b；X*0由因為Y*0，所以有：(Y*)TAX*

(Y*)Tb

=

bTY

*；又Y*是對偶問題的可行解，所以滿足約束條件，即：ATY

*

C；Y*0由因為X*0，所以有：(X*)TATY

*

(X*)TC=CTX

*

又因為：(Y*)TAX*=(X*)TATY

*

所以有：CTX

*

bTY

*。3.無界性：若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。

證明：由弱對偶性顯然便可得到。應當指出的是本性質不存在逆，即當原問題（對偶問題）無可行解時，并不能斷言對偶問題（原問題）必定具有無界解。如下問題便可說明：

例2：原問題對偶問題顯然在例2中，原問題與對偶問題都沒有可行界。

4.可行解是最優(yōu)解時的性質：設X*與Y*分別是原問題與對偶問題的可行解，當CTX

*=

bTY

*

時，

X*與Y*分別是原問題與對偶問題的最優(yōu)解解。

證明：當CTX

*=

bTY

*

時，根據(jù)弱對偶性可知，對于對偶問題的任何一個可行解Y，都有bTY

CTX

*=

bTY

*，可見Y

*

是對偶問題的最優(yōu)解。同理可證明：對于原問題的任何一個可行解X，比有CTX

*=

bTY

*

CTX，所以X

*必然是原問題的最優(yōu)解。

5.對偶定理：若原問題有最優(yōu)解，則其對偶問題也有最優(yōu)解，且它們的目標函數(shù)值相等。

證明：設X*是原問題最優(yōu)的基可行解，它對應的基矩陣為B必使得CT-CBTB-1A

0，即得到(Y*)TA

CT

也就是

ATY

*

C，其中：(Y*)T=CBTB-10這時Y*

是對偶問題的可行解，它使得：(Y*)Tb=CBTB-1b=CTX

*

由性質4可知，Y*

是對偶問題的可行解。

6.互補松弛性：若X*與Y*分別是原問題與對偶問題的可行解，那么(Y*)TXs=0和YsTX=0的充分必要條件是X*與Y*分別是原問題與對偶問題的最優(yōu)解解。這里Xs

和Ys

分別為原問題與對偶問題的松弛向量和剩余向量。

證明：設原問題和對偶問題的標準型是：原問題對偶問題將原問題目標函數(shù)中的系數(shù)向量C

用C=ATY–Ys

代替，得到：Z=(ATY–Ys)TX=YTAX–YsTX(2.4)將對偶問題目標函數(shù)中的系數(shù)向量b

用b=AX+Xs代替，得到：W=YT(AX+Xs)=YTAX+YTXs(2.5)

若(Y*)TXs=0和YsTX*=0，則

CTX

*=

bTY

*=(Y*)TAX*

由性質4可知X*與Y*分別是原問題與對偶問題的最優(yōu)解。由若X*與Y*分別是原問題與對偶問題的最優(yōu)解，由性質2可知CTX

*=(Y*)TAX*

=

bTY

*

再由(2.4)、(2.5)式知道，這時必有(Y*)TXs=0和YsTX*=0

7.設原問題是：maxZ=CTX；AX+Xs=b；X，Xs

0對偶問題是：minW=YTb；ATY–Ys=C；Y，Ys

0則原問題單純形表的檢驗數(shù)行對應其對偶問題的一個基解

，其對應關系見表2—2。

表2—2XBXNXs0CNT–CBTB-1N-CBTB-1Ys1-Ys2T-Y

這里Ys1是對應原問題中基變量XB

的剩余變量，Ys2是對應原問題中非基變量XN

的剩余變量。

證明：設B

是原問題的一個可行基，于是A=(B,N)；原問題可改寫為：相應地對偶問題可表示為：這里：，當求得原問題的一個可行解XB=B-1b時，其相應的非基變量XN、Xs

檢驗數(shù)為：CNT–CBTB-1N-CBTB-1。現(xiàn)分析這些檢驗數(shù)與對偶問題的解之間的關系：令YT=CBTB-1，將它代入(2.6)、(2.7)式得到Ys1=0，

-Ys2T=CNT–CBTB-1N。

現(xiàn)舉兩個例子說明這些性質的應用。

例3：對于如下線性規(guī)劃問題，試利用對偶理論證明該線性規(guī)劃問題無最優(yōu)解。

證明：首先我們可以知道該線性規(guī)劃問題存在可行解X=(0，0，0)；而上述問題的對偶問題是：由第一約束條件可知對偶問題無可行解，因此無最優(yōu)解。再由對偶定理可知原問題必無最優(yōu)解。

例4已知線性規(guī)劃問題：的對偶問題的最優(yōu)解為y1*=4/5，y2*=3/5，目標函數(shù)值為Z*=5，試用對偶理論找出原問題的最優(yōu)解。

解：首先寫出該線性規(guī)劃問題的對偶問題：將y1*、y2*

的值代入約束條件，得(2)、(3)、(4)為嚴格不等式；由互補松弛性（性質6）可得：x2*=x3*=x4*=0，同樣由互補松弛性，因為y1*、y2*>0，所以原問題的兩個約束條件應該取等式，故有：求解此方程組便可得到：x1*=1，x5*=1；所以原問題的最優(yōu)解為：X*=(x1*,x2*,x3*,x4*,x5*)=(1,0,0,0,1)。

最優(yōu)目標函數(shù)值為：W

*=5。

第三節(jié)對偶單純形算法

本章第二節(jié)講到原問題與對偶問題的解之間的對應關系（性質7）時指出：在單純形表進行迭代計算時，在列中得到的是原問題的基可行解，而在檢驗數(shù)行中得到的是對偶問題的基解。通過逐步迭代計算，當在檢驗數(shù)行得到對偶問題的解也是可行解時，根據(jù)性質2、4便可知道，已得到最優(yōu)解。此時原問題與對偶問題都是最優(yōu)解。根據(jù)對偶問題的對稱性，也可以這樣考慮問題：若保持對偶問題的解是基可行解，即檢驗數(shù)：

σj=cj–CBTB-1Pj

0

而原問題在非可行解的基礎上，通過逐步迭代計算達到可行，即：0，這樣也可以得到原問題的最優(yōu)解。其優(yōu)點是原問題的初始解不一定要求是基可行解，可從非基可行解開始迭代計算。這個方法可具體表述如下：設原問題是：又設B

是一個基（不一定是可行基），不失一般性，令

B=(P1,P2,···,Pm)

它對應的基變量為XB=(x1,x2,···,xm)T

。當非基變量都為0時可以得到XB=B-1b。若在B-1b

中至少有一個負分量，設(B-1b)i<0，并且在單純形表檢驗數(shù)行中的檢驗數(shù)都0，即對偶問題保持可行，它的各分量是：對應于基變量x1,x2,···,xm

的檢驗數(shù)是σj=cj–CBTB-1Pj

=0，j=1,2,···,m

對應于非基變量

xm+1,xm+2,···,xn的檢驗數(shù)是σj=cj–CBTB-1Pj

0，j=

m+1,···,n

每次迭代是將基變量中的負分量xl

取出，去替換非基變量中的xk

，并使所有檢驗數(shù)繼續(xù)保持0。在列中小于的元素個數(shù)要減少。即從原問題來看，經(jīng)過每次迭代，原問題由非可行解向可行解靠近，而當原問題得到可行解時，便得到了原問題的最優(yōu)解。

對偶單純形算法的計算步驟如下：（1）首先根據(jù)線性規(guī)劃問題，列出初始單純形表。（所給出的基要使得非基變量檢驗數(shù)全都0，也就是所給出的解是一個對偶可行解，這時也稱所給出的基為對偶可行基），檢查列的數(shù)字，若都為非負，則已得到原問題的最優(yōu)解，停止計算。（2）若列中存在某個，且所對應的該行的系數(shù)矩陣元素，則原問題無可行解，停止計算。我們對第（2）項內(nèi)容說明如下：取，這時可知

Y

T是對偶問題的可行解，對應于這個可行解的對偶問題的目標函數(shù)值是：即對偶問題的可行解使得對偶問題目標函數(shù)值無界，則由性質3（無界性）可知原問題沒有可行解。(3)若非（1）、（2）情形，則進行基變換，具體如下：首先確定換出變量：由

對應的基變量xl

為換出變量。其次確定換入變量：由

對應的非基變量xk

為換入變量（只有這樣，才能保持得到的對偶問題的解仍為可行解）。（4）以ylk

為主元素，按原單純形算法在表中進行迭代運算（即進行基變換），得到新的計算表。

重復（1）~（4）的步驟，直到的所有分量全都0。

下面舉例說明具體算法。

例5用對偶單純形算法求解如下線性規(guī)劃問題

解：先將該問題化成下面形式，以便得到原問題的一個對偶初始可行解，進而得到一個初始對偶可行基。以x4,x5

為初始基變量，建立這個問題的初始單純形表，見表2—3；然后，利用對偶單純形算法進行計算得到表2—4、表2—5，具體如下：表2—3Cj

-2-3-400CBXBx1x2x3x4x50x4-3-1-2-1100x5-4[-2]1-301

j0-2-3-400

表2—4Cj

-2-3-400CBXBx1x2x3x4x50x4-10[-5/2]1/21-1/2-2x121-1/23/20-1/2

j40-4-10-1

表2—5Cj

-2-3-400CBXBx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5

j28/500-3/5-8/5-1/5在表2—5中，，檢驗數(shù)全都0，所以原問題的最優(yōu)解為X

*=(x1*,x2*,x3*,x4*,x5*)=(11/5,2/5,0,0,0)。

原問題對應于兩個約束條件的對偶變量分別為y1,y2,則由表2—5的檢驗數(shù)行便可得出原問題的對偶問題的最優(yōu)解是Y*=(y1*,y2*)=(8/5,1/5)即對應于原問題的兩個松弛變量x4

和x5

的檢驗數(shù)的反號。從以上求解過程可以看到，對偶單純形算法有以下優(yōu)點：(1)初始解可以是非可行解，當檢驗數(shù)都0，就可以進行基變換，這時無需加人工變量，因此，可以簡化計算。(2)當變量多于約束條件時，對于這樣的線性規(guī)劃問題，用對偶單純形算法計算可以減少計算工作量。因此，對變量較少而約束條件較多的線性規(guī)劃問題，可先將它變換成對偶問題，然后利用對偶單純形算法求解。（3）在靈敏度分析中，有時需要利用對偶單純形算法，這樣可使問題的處理簡化。

當然，對偶單純形算法也有它的不足之處，其極限性主要是，對大多數(shù)線性規(guī)劃問題，很難找到一個初始對偶可行解（基），因此，這種方法在求解線性規(guī)劃問題時很少單獨使用。

第四節(jié)靈敏度分析在以前討論線性規(guī)劃問題時，都假定aij,bi

,cj

都是常數(shù)。但實際上這些系數(shù)往往是估計值或預測值。如果市場條件發(fā)生變化，cj

值就會發(fā)生變化；aij

往往是因為工藝條件的改變而改變；

bi

是根據(jù)資源投入后的經(jīng)濟效果決定的一種決策選擇。因此，我們會提出這樣的問題（1）當這些系數(shù)有一個或若干個發(fā)生變化時，原先已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化；（2）或者這些系數(shù)在什么范圍變化時，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變。前一個問題我們稱為參數(shù)規(guī)劃，將在第五節(jié)中討論；而后一個問題我們稱為靈敏度分析，將在本節(jié)中進行討論。顯然，當線性規(guī)劃問題中這些系數(shù)有一個或若干個發(fā)生變化時，原先已求得的線性規(guī)劃問題的最優(yōu)解一般是會發(fā)生變化的。當然可以用單純形算法從頭開始計算，以便得到新的最優(yōu)解。但是，這樣做很麻煩，而且也沒有必要。由于在單純形法迭代計算時，每次計算都和基變量所對應的系數(shù)矩陣B

有關，因此，可以把發(fā)生變化的個別系數(shù)，經(jīng)過一定計算后直接填入最終計算表中，并進行檢查和分析，可按表2—6中的幾種情況進行處理。下面就各種情況分別進行討論。

表2—6原問題對偶問題結論或繼續(xù)計算的步驟可行解可行解表中的解仍為最優(yōu)解可行解非可行解用單純形法繼續(xù)計算求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)計算求最優(yōu)解非可行解非可行解引進人工變量，編制新的單純形表求最優(yōu)解

4.1資源數(shù)量變化的分析資源數(shù)量變化是指系數(shù)br

發(fā)生變化，即br/=

br+Δbr

。并假定規(guī)劃問題其他系數(shù)都保持不變；這樣使最終表中原問題的解相應地變化為：XB/=B-1(b+Δb)

這里Δb=(0,···,Δbr,···,0)T

，只要XB/

0，最終表中檢驗數(shù)不變，則最優(yōu)基不變。但最優(yōu)解的值發(fā)生了變化，所以XB/

為新的最優(yōu)解。新最優(yōu)解的值可允許變化范圍用以下方法確定。這時在最終表中求得的列的所有元素：由此可得：即當約束條件中的第r

種資源變化范圍的改變量在上述范圍變化時，原問題的最優(yōu)基不發(fā)生變化。例如我們求第一章例1中第二個約束條件b2

的變化范圍Δb2

時，可計算：因此，b2

的變化范圍是：b2+Δb2=[8，32]。

例6我們知道第一章例1中，每設備臺時的影子價格為1.5元，若該廠又從別處抽出4個臺時用于生產(chǎn)產(chǎn)品I、II，求這時該廠生產(chǎn)產(chǎn)品I、II的最優(yōu)方案。

解：首先計算將上述結果反映到最終計算表中，得表2—7，并利用對偶單純形算法求得表2—8如下：

表2—7Cj

23000CBXBx1x2x3x4x52x14+01000.2500x54-800[-2]0.513x22+2010.5-0.1250

j00-1.5-0.1250表2—8Cj

23000CBXBx1x2x3x4x52x141000.2500x32001-0.25-0.53x2301000.25

j000-0.5-0.75即該廠最優(yōu)生產(chǎn)方案應改為生產(chǎn)產(chǎn)品I4件，生產(chǎn)產(chǎn)品II3件，最大獲利Z*=42+33=17（元）。從表2—8中可看出x3=2，即設備有2臺時未利用。

4.2目標函數(shù)中價值系數(shù)cj

的變化分析

可以分別就cj

對應的變量是非基變量和基變量兩種情形加以討論：（1）若cj

對應的變量xj

是非基變量，這時它在計算表中所對應的檢驗數(shù)是：σj=cj–CBTB-1Pj

當cj

變化Δcj

后，為了保證最終表中這個檢驗數(shù)仍然小于0，即：σj/=cj

+Δcj

–CBTB-1Pj

0

cj

+Δcj

YTPj(YT=CBTB-1)

Δcj

YTPj

-cj=-σj

即Δcj

的值必須小于等于YTPj

-cj

，也就是-σj

，才可以滿足原解仍然是最優(yōu)解的這一結果，這樣我們就確定了

Δcj

的取值范圍。即當Δcj(-,-σj

]時，原問題的最優(yōu)解不變。

（2）若cr對應的變量xr

是基變量，因為cr

CB，當cr

變化時，就會引起

CB

的變化，這時：(CBT+ΔCBT)B-1A=CBTB-1A+(0,···,Δcr,···,0)B-1A

=CBTB-1A+Δcr(ar1,ar2,···,arn)

其中：(ar1,ar2,···,arn)

表示B-1A矩陣的第r

行?？梢?，當

cr

變化Δcr

后，最終表中的檢驗數(shù)是：σj/=cj–CBTB-1Pj

–Δcjarj

=σj–Δcjarj

(j

IN

)若要求原最優(yōu)解不變，即必須滿足σj/

0,j

IN

，于是得到：例7：試以第一章例1的最終表為例。若基變量x2

的系數(shù)

c2

變化Δc2，在原最優(yōu)解不變的條件下，確定Δc2

的變化范圍。

解：這時由表1—7表1—7cj23000CBXBx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80-Z-1400-1.5-1/80經(jīng)修改后可得表2—9

表2—9cj23+Δc2

000CBXBx1x2x3x4x52x141001/400x5400-21/213+Δc2

x22011/2-1/80-Z-1400-1.5-Δc2/2-1/8+Δc2/80從表2—9可看出，為使表中解仍然為最優(yōu)解，就必須有：

-1.5-Δc2/20，

-1/8+Δc2/80聯(lián)立以上兩個不等式求解變得：-3Δc21即當x2

的價值系數(shù)c2

在[0，4]區(qū)間變化時，原問題的最優(yōu)解不變。

4.3技術系數(shù)aij

的變化對最優(yōu)解的影響

下面分兩種情況討論技術系數(shù)

aij

的變化，并以具體例子加以說明。

例8分析在原計劃中是否應該安排一種新產(chǎn)品。以第一章例1為例，設該廠除了生產(chǎn)產(chǎn)品I、II外，還有一種新產(chǎn)品III。已知生產(chǎn)產(chǎn)品III，每件需消耗原材料A、B各為6kg、3kg，使用設備2臺時；每件可獲利5元，問該廠是否應生產(chǎn)該產(chǎn)品和生產(chǎn)多少？

解：分析此問題的步驟是：（1）設生產(chǎn)產(chǎn)品IIIx3/

件，其技術系數(shù)向量P3/=(2,6,3)T

，然后計算表中對應于x3/

的檢驗數(shù)：

3/=c3/

-CBTB-1P3/

=5–(1.5,0.125,0)(2,6,3)T=1.25>0

說明安排生產(chǎn)產(chǎn)品III是有利的。（2）計算產(chǎn)品III在最終表中對應

x3/

的列向量：并將（1）、（2）中的計算結果填入最終表中可得表2—10

表2—10cj230005CBXBx1x2x3x4x5x3/2x141001/403/20x5400-21/21[2]3x22011/2-1/801/4-Z-1400-1.5-1/805/4

由于列的數(shù)字沒有變化，原問題的解是可行解，但檢驗數(shù)中還有正檢驗數(shù)，說明目標函數(shù)值還可以改善。（3）將x3/

作為換入變量，x5

作為換出變量，進行基變換，求出新的最優(yōu)解。這時得出新的最優(yōu)解為：x1=1，

x2=1.5，x3/=2，總利潤為16.5元，比原計劃增加了2.5元，具體見下表2—11

表2—11cj230005CBXBx1x2x3x4x5x3/2x11101.5-0.125-0.7505x3/200-10.250.513x21.5010.75-0.1875-0.1250-Z-16.500-0.25-0.4375-0.6250

例9分析原計劃生產(chǎn)產(chǎn)品的工藝結構發(fā)生變化。仍以第一章例1為例加以說明，若原來計劃生產(chǎn)產(chǎn)品I的工藝結構有了改進，這時有關它的技術向量變?yōu)镻1/=(2,5,2)T

，每件利潤為4元，試分析對原最優(yōu)計劃有什么影響？解：把改進工藝結構的產(chǎn)品I看作新產(chǎn)品I/，設x1/

為其產(chǎn)量，于是計算在最終表中對應x1/

的列向量：同時計算出x1/

的檢驗數(shù)為：

1/=c1/

-CBTB-1P1/

=4–(1.5,0.125,0)(2,5,2)T=0.375>0將以上結果填入最終表附加的x1/

列向量位置得表2—12cj230004CBXBx1x2x3x4x5x1/2x141000.250[1.25]0x5400-20.510.53x22010.5-0.12500.375-Z-1400-1.5-0.12500.375顯然在表2—12中，x1/

正好替換x1，經(jīng)基變換運算之后將x1

列去掉，以x1/

代替x1

列可得表2—13如下：

表2—13cj43000CBXBx1/x2x3x4x54x1/3.21000.200x52.400-20.413x20.8010.5-0.20-Z-15.200-1.5-0.20即這時應當生產(chǎn)產(chǎn)品I/3.2件，產(chǎn)品II0.8件，可獲利15.2元

例10：假設上例的產(chǎn)品I/

的技術向量變?yōu)镻1/=(4,5,2)T

，而每件產(chǎn)品獲利仍為4元。試問該廠如何安排最優(yōu)生產(chǎn)方案？

解：方法與上例相同，以x1/

代替x1，計算：同時計算出x1/

的檢驗數(shù)為：

1/=c1/

-CBTB-1P1/

=4–(1.5,0.125,0)(4,5,2)T=-2.625<0將以上結果填入最終表附加的x1/

列向量位置得表2—14表2—14cj230004CBXBx1x2x3x4x5x1/2x141000.250[1.25]0x5400-20.51-3.53x22010.5-0.12501.375-Z-1400-1.5-0.1250-2.625由單純形法的計算規(guī)則可知，這時原解仍為最優(yōu)解。但我們?nèi)砸詘1/

強行替換x1，將運算后的x1/

列填入x1

列位置，去掉x1

列可得表2—15如下：

表2—15

cj43000CBXBx1/x2x3x4x54x1/3.21000.200x515.200-21.213x2-2.4010.5-0.40-Z-5.600-1.50.40從該表可見原問題和對偶問題都是非可行解，于是引入人工變量x6(放入出現(xiàn)負的那一行)，用方程表示即為0x1/+x2+0.5x3

–0.4x4+0x5=-2.4

引入人工變量x6，上式就變?yōu)椋?/p>