運籌學第2章(講課比賽)

Chapter2對偶理論

(DualityTheory)單純形法的矩陣描述對偶問題的提出線性規(guī)劃的對偶理論對偶問題的經(jīng)濟解釋－影子價格對偶單純形法靈敏度分析(選講)掌握WinQSB軟件求解對偶規(guī)劃本章主要內(nèi)容： 學習要點：

1.理解對偶理論，掌握描述一個線性規(guī)劃問題的對偶問題。

2.能夠運用對偶單純形法來求解線性規(guī)劃問題。

3.會用互補松弛條件來考慮一對對偶問題的界。

4.了解影子價格、靈敏度分析以及用WinQSB求解對偶規(guī)劃問題。2.1

單純形法的矩陣描述0.16-0.120102412x2-0.20.4001207x11.16-3.12100840x3-1.20003.41000.10010,33012x220-0.51002.5500x430.8-0.40107.82400x3000127301001033000x540010542000x490001493600x3?x5x4x3x2x1B-1bCBXB每一列的含義？每個表中的B和B-1的查找？單純形法的矩陣描述單純形法的矩陣描述單純形法的矩陣描述CBCNbXBXNbBNCBCNbXBXNB-1bIB-1N-CBB-1b0CN-CBB-1N單純形法的矩陣描述CBCNCS(0)bXBXNXSbBNI0CBCN0CBCNCS(0)bXBXNXSB-1bIB-1NB-1-CBB-1b0CN-CBB-1N-CBB-1

單純形法的矩陣描述2.3對偶問題的提出

對偶理論是線性規(guī)劃中最重要的理論之一，是深入了解線性規(guī)劃問題結(jié)構(gòu)的重要理論基礎。同時，由于問題提出本身所具有的經(jīng)濟意義，使得它成為對線性規(guī)劃問題系統(tǒng)進行經(jīng)濟分析和敏感性分析的重要工具。那么，對偶問題是怎樣提出的，為什么會產(chǎn)生這樣一種問題呢？對偶問題的提出倆家具制造商間的對話：唉!我想租您的木工和油漆工一用。咋樣？價格嘛……好說，肯定不會讓您兄弟吃虧。王老板做家具賺了大錢，可惜我老李有高科技產(chǎn)品，卻苦于沒有足夠的木工和油漆工咋辦？只有租咯。Hi：王老板，聽說近來家具生意好呀，也幫幫兄弟我哦!家具生意還真賺錢，但是現(xiàn)在的手機生意這么好，不如干脆把我的木工和油漆工租給他，又能收租金又可做生意。價格嘛……好商量，好商量。只是…...

王老板李老板引例1對偶問題的提出王老板的家具生產(chǎn)模型：x1、

x2是桌、椅生產(chǎn)量。Z是家具銷售總收入（總利潤）。maxZ=50x1+30x2s.t.4x1+3x2

≤120（木工）

2x1+x2

≤50（油漆工）

x1，x2

≥0原始線性規(guī)劃問題，記為（P）王老板的資源出租模型：y1、y2單位木、漆工出租價格。W是資源出租租金總收入。minW=120y1+50y2s.t.4y1+2y2

≥503y1+y2

≥30y1，y2

≥0對偶線性規(guī)劃問題，記為（D）所得不得低于生產(chǎn)的獲利（不吃虧原則）要使對方能夠接受（競爭性原則）兩個原則對偶問題的提出王老板按（D）的解y1、y2出租其擁有的木、漆工資源，既保證了自己不吃虧（出租資源的租金收入并不低于自己生產(chǎn)時的銷售收入），又使得出租價格對李老板有極大的吸引力（李老板所付出的總租金W最少）。按時下最流行的一個詞，叫什么來著————對偶問題的提出Max

Z=

40x1+50x2

x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標函數(shù)約束條件設三種資源的使用單價分別為y1,y2,y3y1y2y3生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利y1+3y240

2y1+2y2+2y350甲乙資源量A1230B3260C0224單位獲利4050引例2通過使用所有資源對外加工所獲得的收益W=30y1+60y2+24y3對偶問題的提出根據(jù)原則2，對方能夠接受的價格顯然是越低越好，因此此問題可歸結(jié)為以下數(shù)學模型：Min

W=30y1+60y2+24y3

y1+3y2402y1+2y2+2y350y1,y2,y3

0s.t目標函數(shù)約束條件原線性規(guī)劃問題稱為原問題，此問題為對偶問題，y1,y2,y3為對偶變量，也稱為影子價格對偶問題的提出2.4線性規(guī)劃的對偶理論Max

Z=

40x1+50x2

x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t原問題（對偶問題）對偶問題（原問題）一、原問題與對偶問題的對應關系Min

W=30y1+60y2+24y3

y1+3y2402y1+2y2+2y350y1,y2,y3

0s.t（y1）

（y2）（y3）

（x1）

13040（x2）22250306024

minωmaxz

3個約束2個變量2個約束3個變量線性規(guī)劃的對偶理論對偶問題的形式定義設原線性規(guī)劃問題為則稱下列線性規(guī)劃問題為其對偶問題，其中yi

(i=1,2,…,m)稱為對偶變量上述對偶問題稱為對稱型對偶問題原問題簡記為(P)，對偶問題簡記為(D)稱問題(P)和(D)為一對對偶問題線性規(guī)劃的對偶理論對稱型問題的對偶規(guī)則1、給每個原始約束條件定義一個非負對偶變量yi(i=1,2,…,m)；2、使原問題的目標函數(shù)系數(shù)cj

變?yōu)槠鋵ε紗栴}約束條件的右端常數(shù)；3、使原問題約束條件的右端常數(shù)bi變?yōu)槠鋵ε紗栴}目標函數(shù)的系數(shù)；4、將原問題約束條件的系數(shù)矩陣轉(zhuǎn)置，得到其對偶問題約束條件的系數(shù)矩陣；5、改變約束問題不等號的方向，即將“≤”改為“≥”；6、原問題為“max”型，對偶問題為“min”型。線性規(guī)劃的對偶理論原始問題MaxZ=CXs.t.AX≤b

X

≥0bAC≤Maxnm對偶問題MinW=Ybs.t. YA≥C Y≥0≥MinCATbnmY為行向量線性規(guī)劃的對偶理論當原問題為求極小值時，對偶問題為求極大值。原始問題中目標函數(shù)的系數(shù)變成對偶問題中約束條件的右端；原始問題中約束條件的右端變成對偶問題中目標函數(shù)的系數(shù)。原始問題約束條件系數(shù)矩陣的轉(zhuǎn)置對應對偶問題中約束條件的系數(shù)矩陣。原始問題的約束條件個數(shù)決定對偶問題變量的個數(shù)；原始問題變量個數(shù)，決定對偶問題的約束個數(shù)。原始問題的約束方程的匹配形式?jīng)Q定對偶問題變量的符號；原始問題決策變量的符號決定所對應對偶問題的約束方程的匹配形式。線性規(guī)劃的對偶理論求線性規(guī)劃問題的對偶規(guī)劃解：由原問題的結(jié)構(gòu)可知為對稱型對偶問題例1線性規(guī)劃的對偶理論求線性規(guī)劃問題的對偶規(guī)劃解：由原問題的結(jié)構(gòu)可知不是對稱型對偶問題，可先化為對稱型，再求其對偶規(guī)劃。例2線性規(guī)劃的對偶理論求線性規(guī)劃問題的對偶規(guī)劃解：由原問題的結(jié)構(gòu)可知不是對稱型對偶問題，可先化為對稱型，再求其對偶規(guī)劃。例3線性規(guī)劃的對偶理論上式已為對稱型對偶問題，故可寫出它的對偶規(guī)劃令則上式化為線性規(guī)劃的對偶理論對偶問題的非對稱形式minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≥≤=≤unr≥≤≥=≤≥x1≥0x2≤0x3:unr原始問題變量的個數(shù)(3)等于對偶問題約束條件的個數(shù)(3)；原始問題約束條件的個數(shù)(4)等于對偶問題變量的個數(shù)(4)。原始問題變量的性質(zhì)影響對偶問題約束條件的性質(zhì)，用

表示原始問題約束條件的性質(zhì)影響對偶問題變量的性質(zhì)，用表示線性規(guī)劃的對偶理論原問題（或?qū)ε紗栴}）對偶問題（或原問題）約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)約束條件右端項目標函數(shù)max目標函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=線性規(guī)劃的對偶理論MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.ty1y2y3MinW=30y1+60y2+24y3

y1+3y2+0y3

402y1+2y2+2y3

50

y1,y2,y30s.tMaxW′=-30y1-60y2-24y3

y1+3y2+0y3–y4

=402y1+2y2+2y3

–y5

=50y1,y2,y3,y4,y50s.t例4二、對偶問題的解線性規(guī)劃的對偶理論MaxW′=-30y1-60y2-24y3+0(y4+

y5)-M(y6+

y7)

y1+3y2+0y3–y4+

y6

=402y1+2y2+2y3

–y5

+

y7

=50y1,y2,y3,y4,y50s.tcj-30-60-2400-M-MB-1bθcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2σj3M-305M-602M-24-M-M00-90M線性規(guī)劃的對偶理論cj-30-60-2400-M-MB-1bθcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3σj4M/3-1002M-242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/3040/340-24y32/3011/3-1/2-1/31/235/335/2σj600-12-12-M+12-M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/21/2-3/4-1/23/435/2σj00-9-15-15/2-M+30-M-15/2-975線性規(guī)劃的對偶理論cj4050000B-1bcBxBx1x2x3x4x540x1101/2-1/20150x5003/2-1/21950x201-3/41/4015/2σj00-35/2-15/20975MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.t

x1+2x2+x3=303x1+2x2+x4=602x2+x5=24

x1–x50s.t線性規(guī)劃的對偶理論線性規(guī)劃的對偶理論原問題與其對偶問題的變量與解的對應關系： 在單純形表中，原問題的松弛變量對應對偶問題的變量，對偶問題的剩余變量對應原問題的變量。線性規(guī)劃的對偶理論XBb原問題的變量原問題的松弛變量x1x2x3x4x5x115101/2-1/20x59003/2-1/21x215/2013/4-1/4000-35/2-15/20YBb對偶問題的變量對偶問題的剩余變量y1y2y3y4y5y215/201-1/2-1/21/4y135/2103/21/2-3/400-9-15-15/2原問題最優(yōu)表對偶問題最優(yōu)表MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.tMinW=30y1+60y2+24y3

y1+3y2+0y3

402y1+2y2+2y3

50

y1,y2,y30s.t線性規(guī)劃的對偶理論性質(zhì)1對稱性定理：對偶問題的對偶是原問題

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≤bX≥0三、對偶原理線性規(guī)劃的對偶理論minz′=-

CXs.t.-AX≥-b X≥0maxw′=-Ybs.t.-YA≤-C

Y≥0minw=Ybs.t.YA≥C

Y≥0maxz=CXs.t.AX≤bX≥0對偶的定義對偶的定義簡要證明：線性規(guī)劃的對偶理論性質(zhì)2弱對偶原理(弱對偶性)：設和分別是問題(P)和(D)的可行解，則必有推論1:

原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；反之，對偶問題任意可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界。證明：(1)當X和Y為原問題和對偶問題的一個可行解有原問題目標函數(shù)值對偶問題目標函數(shù)值線性規(guī)劃的對偶理論推論2:

在一對對偶問題（P）和（D）中，若其中一個問題可行但目標函數(shù)無界，則另一個問題無可行解；反之不成立。這也是對偶問題的無界性。若（P）為無界解，則（D）無可行解；若（D）為無界解，則（P）無可行解。線性規(guī)劃的對偶理論推論3：在一對對偶問題（P）和（D）中，若一個可行（如P），而另一個不可行（如D），則該可行的問題目標函數(shù)值無界。已知原問題(LP)，試估計它的目標函數(shù)值的界,并驗證弱對偶定理.例5線性規(guī)劃的對偶理論解：問題(LP)的對偶問題(DP)為(DP)線性規(guī)劃的對偶理論由觀察可知分別是原問題和對偶問題的可行解。，弱對偶定理成立。且由推論1知，對偶問題目標函數(shù)W的下界為10，原問題目標函數(shù)Z的上界為40。且原問題的目標函數(shù)值為對偶問題的目標函數(shù)值為故線性規(guī)劃的對偶理論例：利用對偶性質(zhì)判斷下面問題有無最優(yōu)解例6解：此問題的對偶問題為不能成立，因此對偶問題不可行。故由推論3知原問題無界。為可行解線性規(guī)劃的對偶理論性質(zhì)3最優(yōu)性定理：如果是原問題的可行解，是其對偶問題的可行解，并且:則是原問題的最優(yōu)解，是其對偶問題的最優(yōu)解。線性規(guī)劃的對偶理論性質(zhì)4強(主)對偶性：若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標函數(shù)值相等。還可推出另一結(jié)論：若一對對偶問題中的任意一個有最優(yōu)解，則另一個也有最優(yōu)解，且目標函數(shù)最優(yōu)值相等；若一個問題無最優(yōu)解，則另一問題也無最優(yōu)解。一對對偶問題的關系，有且僅有下列三種：都有最優(yōu)解，且目標函數(shù)最優(yōu)值相等；兩個都無可行解；一個問題無界，則另一問題無可行解。線性規(guī)劃的對偶理論證明：當X*為原問題的一個最優(yōu)解，B為相應的最優(yōu)基，通過引入松弛變量Xs，將問題(P)轉(zhuǎn)化為標準型令CCBCN0解基系數(shù)基變量XBXNXsCBXBIB-1NB-1B-1bσ0CN-CBB-1N

-CBB-1CBB-1bCXAC-CBB-1A說明Y*可行線性規(guī)劃的對偶理論問題:（1）由性質(zhì)4可知，對偶問題最優(yōu)解的表達式Y(jié)*=?（2）求Y*是否有必要重新求解(D)?—不必?？梢詮脑瓎栴}（P）的單純形終表獲得。CCBCN0解基系數(shù)基變量XBXNXsCBXBIB-1NB-1B-1bσ0CN-CBB-1N

-CBB-1CBB-1b線性規(guī)劃的對偶理論性質(zhì)5

互補松弛性：設X0和Y0分別是P問題和D問題的可行解，則它們分別是最優(yōu)解的充要條件是：其中：Xs、Ys為松弛變量。在線性規(guī)劃問題的最優(yōu)解中，若對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；另一方面，如果約束條件取嚴格不等式，則其對應的變量一定為零。緊約束與松約束線性規(guī)劃的對偶理論證:(必要性）原問題對偶問題線性規(guī)劃的對偶理論MaxZ=CXs.t. AX+XS=b X,XS≥0MinW=Ybs.t.YA-YS=C W,WS≥0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始問題和對偶問題變量、松弛變量的維數(shù)線性規(guī)劃的對偶理論

y1

yi

ymym+1

ym+j

yn+m

x1

xj

xnxn+1

xn+i

xn+m

對偶問題的變量對偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0

yixn+i=0

(i=1,2,…,m;j=1,2,…,n)在一對變量中，其中一個大于0，另一個一定等于0線性規(guī)劃的對偶理論性質(zhì)5的應用： 該性質(zhì)給出了已知一個問題最優(yōu)解求另一個問題最優(yōu)解的方法，即已知Y＊求X＊或已知X＊求Y＊互補松弛條件由于變量都非負，要使求和式等于零，則必定每一分量為零，因而有下列關系：

若Y＊≠0，則Xs必為0；若X＊≠0，則Ys必為0利用上述關系，建立對偶問題（或原問題）的約束線性方程組，方程組的解即為最優(yōu)解。線性規(guī)劃的對偶理論已知線性規(guī)劃的最優(yōu)解是X＊=(6,2,0)T,求其對偶問題的最優(yōu)解Y＊。解：寫出原問題的對偶問題，即標準化例7線性規(guī)劃的對偶理論設對偶問題最優(yōu)解為Y＊＝(y1，y2),由互補松弛性定理可知，X＊和Y＊滿足：即：因為x1≠0，x2≠0，所以對偶問題的第一、二個約束的松弛變量等于零，即y3＝0，y4＝0，帶入方程中：解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為：Y＊=(1,1)，最優(yōu)值w=26。線性規(guī)劃的對偶理論已知線性規(guī)劃的對偶問題的最優(yōu)解為Y＊=(0,-2)，求原問題的最優(yōu)解。解:對偶問題是標準化例8線性規(guī)劃的對偶理論設原問題最優(yōu)解為X＊＝(x1，x2，x3)T,由互補松弛性定理知，X＊和Y＊滿足：將Y＊帶入由方程可知，y3＝y(tǒng)5＝0，y4＝1。∵y2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0將x2，x5分別帶入原問題約束方程中，得：解方程組得：x1=-5,x3=-1,所以原問題的最優(yōu)解為X＊=(-5,0,-1)，最優(yōu)值z=-12線性規(guī)劃的對偶理論試用對偶原理求解線性規(guī)劃問題已知其對偶規(guī)劃的最優(yōu)解為練習線性規(guī)劃的對偶理論解：該問題的對偶規(guī)劃為線性規(guī)劃的對偶理論利用松緊關系，代入對偶規(guī)劃的約束條件得下列約束是松約束，將最優(yōu)解松約束緊約束其對偶約束是緊約束線性規(guī)劃的對偶理論設原問題的最優(yōu)解為緊約束線性規(guī)劃的對偶理論對偶規(guī)劃可以用線性規(guī)劃的單純形法求解。由對偶原理可見，原問題與對偶問題之間有緊密聯(lián)系，因此我們能夠通過求解原問題來找出對偶問題的解，反之依然?；パa松弛條件就可以解決由原問題的最優(yōu)解直接求出對偶問題的最優(yōu)解。對偶問題解的求法線性規(guī)劃的對偶理論原問題與對偶問題解的對應關系小結(jié)對應關系原問題最優(yōu)解無界解無可行解對偶問題最優(yōu)解(Y,Y)(N,N)————無界解————(Y,Y)無可行解——(Y,Y)無法判斷線性規(guī)劃的對偶理論思考題判斷下列結(jié)論是否正確，如果不正確，應該怎樣改正？1）任何線性規(guī)劃都存在一個對應的對偶線性規(guī)劃.2）原問題第i個約束是“≤”約束，則對偶變量yi≥0.3）互為對偶問題，或者同時都有最優(yōu)解，或者同時都無最優(yōu)解.4）對偶問題有可行解，則原問題也有可行解.5）原問題有多重解，對偶問題也有多重解.6）對偶問題有可行解，原問題無可行解，則對偶問題具有無界解.7）原問題無最優(yōu)解，則對偶問題無可行解.8）對偶問題不可行，原問題可能無界解.9）原問題與對偶問題都可行，則都有最優(yōu)解.10）原問題具有無界解，則對偶問題不可行.11）對偶問題具有無界解，則原問題無最優(yōu)解.12）若X*、Y*是原問題與對偶問題的最優(yōu)解，則X*=Y*.線性規(guī)劃的對偶理論2.5

影子價格單位產(chǎn)品消耗的資源(噸/件))原始問題是利潤最大化的生產(chǎn)計劃問題總利潤(元)產(chǎn)品產(chǎn)量(件)單位產(chǎn)品的利潤(元/件)消耗的資源(噸)剩余的資源(噸)資源限量(噸)影子價格對偶問題——資源定價問題對偶問題是資源定價問題，對偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價格（ShadowPrice）原始和對偶問題都取得最優(yōu)解時，最大利潤Maxz=Minw總利潤(元)資源限量(噸)資源價格(元/噸)影子價格在一對P和D中，若P的某個約束條件的右端項常數(shù)bi

（第i種資源的擁有量）增加一個單位時，所引起目標函數(shù)最優(yōu)值z*的改變量稱為第

i種資源的影子價格，其值等于D問題中對偶變量yi*。由對偶問題得基本性質(zhì)可得：1.影子價格的數(shù)學分析：影子價格2.影子價格的經(jīng)濟意義1）影子價格是一種邊際價格 在其它條件不變的情況下，單位資源數(shù)量的變化所引起的目標函數(shù)最優(yōu)值的變化。即對偶變量yi

就是第

i種資源的影子價格。即：

影子價格資源影子價格的性質(zhì)影子價格越大，說明這種資源越是相對緊缺影子價格越小，說明這種資源相對不緊缺如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于0影子價格0X2X1X=(15,7.5)Z=975MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(14.5,8.25)

Z=992.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(15.5,7.25)

Z=982.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(15.5,7.25)

Z=982.5X=(14.5,8.25)

Z=992.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t2）影子價格是一種機會成本 影子價格是在資源最優(yōu)利用條件下對單位資源的估價，這種估價不是資源實際的市場價格。因此，從另一個角度說，它是一種機會成本。若第i種資源的單位市場價格為mi

，則有當yi*>mi

時，企業(yè)愿意購進這種資源，單位純利為yi*－mi

，則有利可圖；當yi*<mi

時，企業(yè)有償轉(zhuǎn)讓這種資源，可獲單位純利mi－yi

*

，否則，企業(yè)無利可圖，甚至虧損。結(jié)論：若yi*>mi

則購進資源i，可獲單位純利yi*－mi

；

若yi*<mi則轉(zhuǎn)讓資源i，可獲單位純利mi－yi

。影子價格y1y2ym產(chǎn)品的機會成本機會成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤增加單位資源可以增加的利潤減少一件產(chǎn)品可以節(jié)省的資源影子價格機會成本利潤差額成本產(chǎn)品的差額成本（ReducedCost）差額成本=機會成本-利潤影子價格3）影子價格在資源利用中的應用根據(jù)對偶理論的互補松弛性定理:Y*Xs=0,YsX*=0表明生產(chǎn)過程中如果某種資源bi未得到充分利用時，該種資源的影子價格為0；若當資源資源的影子價格不為0時，表明該種資源在生產(chǎn)中已耗費完。影子價格yixn+i=0如果yi>0，則xn+i=0如果xn+i>0，則yi=0邊際利潤大于0的資源，在最優(yōu)生產(chǎn)計劃條件下沒有剩余ym+jxj=0如果ym+j>0，則xj=0如果xj>0，則ym+j=0最優(yōu)生產(chǎn)計劃條件下有剩余的資源，其邊際利潤等于0差額成本大于0（機會成本大于利潤）的產(chǎn)品，不安排生產(chǎn)安排生產(chǎn)的產(chǎn)品，差額成本等于0（機會成本等于利潤）互補松弛關系經(jīng)濟解釋影子價格4）影子價格對單純形表計算的解釋單純形表中的檢驗數(shù)其中cj表示第j種產(chǎn)品的價格;表示生產(chǎn)該種產(chǎn)品所消耗的各項資源的影子價格的總和，即產(chǎn)品的隱含成本。當產(chǎn)值大于隱含成本時，即，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排；否則，用這些資源生產(chǎn)別的產(chǎn)品更有利，不在生產(chǎn)中安排該產(chǎn)品。影子價格2.6

對偶單純形法 對偶單純形