運籌學課件-線性規(guī)劃對偶理論

第二章線性規(guī)劃對偶理論第一節(jié)線性規(guī)劃對偶理論第二節(jié)對偶問題基本性質(zhì)第三節(jié)影子價格第四節(jié)對偶單純形法第五節(jié)靈敏度分析1/66第一節(jié)線性規(guī)劃對偶理論一、對偶問題的提出[例]2/66設備臺時/件產(chǎn)品可用臺時（千小時）產(chǎn)品1產(chǎn)品2下料設備A104機加工設備B0212焊接設備C3218產(chǎn)品單價3元/件5元/件3/66生產(chǎn)是為贏利（取得收入）。還有別的辦法贏利（取得收入）。例如，賣出或出租設備。問，三種設備賣價或租價各應是多少，進項才不低于自己生產(chǎn)時的銷售收入？原來的問題：兩種產(chǎn)品各生產(chǎn)多少，利潤總額最大？4/66用y1、y2和y3分別表示A、

B和C三種設備單位臺時賣價或租價，則，總進項w可表示成w=4y1

+12y2+18y3生產(chǎn)兩種產(chǎn)品消耗的設備臺時的價值（或稱出售或出租兩種產(chǎn)品所用設備臺時的進項）分別是

1y1

+0y2+3y3和0y1

+2y2+2y3兩種產(chǎn)品售價分別是3和5。出售或出租產(chǎn)品所用設備臺時的進項不能低于售價。所以，應有

1y1

+0y2+3y3

≥3和0y1

+2y2+2y3≥5從另一個角度看，w=4y1

+12y2+18y3是總消耗。5/66回答y1、y2和y3各是多少的問題，可表示如下：Minw=4y1

+12y2+18y3

s.t.

y1

+3y3≥3

2y2

+2y3≥5y1,y2,y3≥0該問題叫做原問題(P)的對偶問題(D)?？煽闯?，Maxz=CXMinw=bTY(P)s.t.AX≤b

(D)

s.t.ATY≥CT

X≥0Y≥06/66cj35000θicBxBB-1bx1x2x3x4x50x320011/3-1/35x260101/203x12100-1/31/3z36000-3/2-1σj若要問對偶問題的解是什么，可以看解(P)時得到的最終單純形表。最終單純形表7/66從該表松弛變量的檢驗數(shù)行得到：σ3

=0，

σ4

=-3/2，σ5

=-1，y1=0，y2

=

3/2，y3

=1，將其代入(D):w=4×0

+12×3/2+18×1=36

(1)0

+3×1

=3(2)

2×3/2+2×1

=5(3)y1,y2,y3≥0(4)這是對偶問題有趣的一個方面。8/66二、對稱的對偶問題一般形式上面的例子叫做對稱的對偶問題。三、非對稱的對偶問題請見教科書第52頁的表。9/66事項原問題（對偶問題）對偶問題（原問題）AbC目標函數(shù)n個決策變量xj≥0xj≤0xj無約束m個決策變量yi≥0yi≤0yi無約束第二節(jié)對偶理論基本性質(zhì)一、對稱形式單純形法矩陣表達Maxz=CX

s.t.AX≤b

X≥0化成標準形式Maxz=CX+0Xs

s.t.AX+IXs=b

X，Xs≥0Xs

=(xs1,xs2,…,xsm)T是松弛變量10/66令X=XB，(C,0)=(CB,CN)Xs

XN(A,I)=(B,N)z=CBB-1b+(CN-CBB-1N)XN

(1)CN-CBB-1N是非基變量xm+1,xm+2,…,xn的檢驗數(shù)，令σj=cj-CBB-1Pj，若所有的σj<0，即CN-CBB-1N≤0(2)則表示目前的基可行解最優(yōu)。另外，基變量XB

的檢驗數(shù)是CB-CBB-1B=0(3)11/66松弛變量Xs

=(xs1,xs2,…,xsm)T的檢驗數(shù)是0-CBB-1I≤0，即-CBB-1≤0(4)將(2)和(3)寫在一起：(CB，CN)-

(CBB-1B，CBB-1N)≤0或(CB，CN)-CBB-1(B，N)≤0，即

C-CBB-1A≤0(5)

12/66再將(1)z=CBB-1b、(5)和(4)寫在一起：

z=CBB-1b(1)

C-CBB-1A≤0(5)-CBB-1≤0(4)令YT=CBB-1，w=YTb(1’)

C-YTA≤0(5’)

-YT≤0

(4’)或

w=YTb

ATY≥CT

Y≥0

13/66

Minw=YTb(D)s.t.

ATY≥CT

Y≥0添加剩余變量后，變成

Minw=YTb+0Ys(D)s.t.

ATY-IYs=CT

Y,Ys≥0Ys

=(ys1,ys2,…,ys,n-m)T是剩余變量

14/6615/66

[例]

Maxz=3x1+5x2

s.t.

x1

≤4

y1

(P)

2x2

≤12y2

3x1+2x2≤18

y3

x1，x2

≥0Minw=4y1

+12y2+18y3

s.t.

y1

+3y3≥3x1

(D)

2y2

+2y3≥5x2y1,y2,y3≥0Maxz=3x1+5x2+0x3+0x4+0x5

s.t.

x1

+

x3

=4

(P)2x2+

x4

=12

3x1+2x2

+

x5

=18

x1，x2，x3，x4，x5≥0Minw=4y1

+12y2+18y3+0y4+0y5+My6+My7s.t.

y1

+3y3

-y4

+y6

=3

(D)2y2+2y3

-y5

+y7

=5

y1,y2,y3,y4,y5,y6,y7

≥0

16/10717/66bj4121800MMθibByBB-1Cy1y2y3y4y5y6y7My63103-1010-My750[2]20-1015/2w8M4-M12-2M18-2MMM00σj對偶問題初始單純形表My6310[3]-10103/312y25/20110-1/201/25/2w3M+304-M06-3MM60M-6σjσ3應當是18-5M，但錯算為18-2M，所以誤選y2為換入變量。以下將錯就錯算下去。18/66bj4121800MMθibByBB-1Cy1y2y3y4y5y6y718y311/301-1/301/3012y23/2-1/3101/3-1/2-1/31/2w3620026M-2M-6σj對偶問題最終單純形表19/66bj4121800MMθibByBB-1Cy1y2y3y4y5y6y7My6310[3]-10101My750220-1015/2w8M4-M12-2M18-5MMM00σj重新算一遍，對偶問題初始單純形表18y311/301-1/301/30-My73-2/3[2]02/3-1-2/313/2w2M/3-212-M0-2M/3+6M5M/3-60σj20/66對偶問題最終單純形表bj4121800MMθibByBB-1Cy1y2y3y4y5y6y718y311/301-1/301/3012y23/2-1/3101/3-1/2-1/31/2w3620026M-2M-6σj計算結果同上。21/66事項原問題變量原問題松弛變量xBB-1bx1x2x3x4x5x320011/3-1/3x260101/20x12100-1/31/3z36000-3/2-1變量對偶問題剩余變量對偶問題變量y4y5y1y2y3(P)最終單純形表22/66事項對偶問題變量對偶問題剩余變量bByBB-1Cy1y2y3y4y518y311/301-1/3012y23/2-1/3101/3-1/2w36原問題松弛變量原問題變量x3x4x5x1x2(D)對偶問題最終單純形表

23/107推論1(P)任一可行解目標函數(shù)值是(D)目標函數(shù)值下界。反之，

(D)任一可行解目標函數(shù)值是(P)目標函數(shù)值上界。推論2若(P)有可行解且目標函數(shù)值無界，則(D)無可行解；反之，(D)有可行解且目標函數(shù)無界，則(P)無可行解。當

(D)無可行解時，(P)無可行解或目標函數(shù)值無界。推論3若(P)有可行解，而(D)無可行解，則(P)目標函數(shù)值無界；反之，(D)有可行解，而(P)無可行解，則(D)目標函數(shù)值無界。24/66

25/1073.對偶定理。若(P)和(D)均有可行解，則均有最優(yōu)解，且兩者的目標函數(shù)值相等。證明:由于(P)和(D)均有可行解，根據(jù)弱對偶性推論1，(P)目標函數(shù)值有上界，

(D)目標函數(shù)值有下界，因此，(P)和(D)都有最優(yōu)解。另外，根據(jù)ATY≥CT，Y≥0，w=YTb=CBB-1b=z知道，當(P)取得最優(yōu)解時，(D)有可行解，且有w=z，根據(jù)性質(zhì)2（最優(yōu)性），(D)的可行解也是最優(yōu)解，證畢。26/107

27/107

28/107第三節(jié)影子價格一、影子價格在例子

Maxz=3x1+5x2

s.t.

x1

≤4

(P)2x2≤123x1+2x2≤18

x1，x2

≥0bT=(4,12,18)是資源，即可利用的設備臺班量。在討論如何才能贏利最多時，沒有考慮三種設備單位臺班的價格。它們的價格藏在深處。29/6630/66有些經(jīng)濟學家認為，自由的市場交易，商品成交價格能夠反映其真正價值。但是，資源的現(xiàn)實市場價格并不反映其“真正”價值。還有些經(jīng)濟學家認為，影子價格是原本無交易的資源，在轉為其他用途時的價格，或者說，另外再增加一個單位此種資源需要付出的價格。這個問題可以利用對偶問題的解給予某種解釋。Minw=4y1

+12y2+18y3

s.t.

y1

+3y3≥3

(D)

2y2

+2y3≥5y1,y2,y3≥0其解是(Y,Ys)T=(y1,y2,

y3,y4,y5)

=(0,3/2,1,

0,0)31/66這就是說，三種設備每臺時的價格分別是0,3/2和1。第一種設備每臺時的價格為0，這是什么意思？請看原問題Maxz=3x1+5x2+0x3+0x4+0x5

s.t.

x1+

x3

=4

(P)

2x2+

x4

=12

3x1+2x2

+

x5

=18

x1，x2，x3，x4，x5≥0其解是(X,Xs)T=(x1,x2,x3,x4,x5)

=(2,6,2,

0,0)32/66

33/107612x1x26449x1=42x2=123x1+2x2=18(2,6)z=3x1+5x2=36z=15oABCDEFG34/107612x1x26449x1=42x2=123x1+2x2=18(2,6)z=3x1+5x2=36z=15oABCDEFGx1=5Δz=36-36=035/107612x1x26449x1=42x2=123x1+2x2=18(5/3,6.5)z=3x1+5x2=36z=15oABCDEFG2x2=13z=3x1+5x2=37.5Δz=37.5-36=1.536/107612x1x26449x1=42x2=123x1+2x2=18z=3x1+5x2=36z=15oABCDEFGz=3x1+5x2=373x1+2x2=19Δz=37-36=1第四節(jié)對偶單純形法一、對偶單純形法思路Minw=bTY-0Ys

(D)

s.t.ATY-IYs=CT

Y，Ys≥037/66二、對偶單純形法計算步驟Step1：找出初始可行基、初始單純形表和初始基解。Step2：若B-1b≥0，初始基解是最優(yōu)解，停。否則，下一步。Step3：取(B-1b)l=min{(B-1b)i|(B-1b)i<0}，第l行基變量換出。若所有的alj≥0，無可行解，停。Step4：計算σk/alk=min{σj/alj|alj<0}，第k列非基變量換入。Step5：求基的逆矩陣、新基解和z?；豐tep2。38/10739/66[例1]Minw=4x1+12x2+18x3

s.t.

x1+

3x3≥3

2x2+

2x3≥5x1，x2，x3

≥0將其改寫如下：Max-w=-4x1-12x2-18x3+0x4+0x5

s.t.

-x1-

3x3

+x4

=-3

-2x2

-2x3+x5=-5x1，x2，x3，x4，x5≥040/66cj-4-12-1800cBxBB-1bx1x2x3x4x50x4-3-10-3100x5-50-2-201zσj/alj初始單純形表cj-4-12-1800θicBxBB-1bx1x2x3x4x50x4-3-10-3100x5-50[-2]-201z-4/0-12/-2-18/-200σj/alj先確定換出變量，再換入變量41/66cj-4-12-1800θicBxBB-1bx1x2x3x4x50x4-3-10-310-12x25/20110-1/2zσj/alj求B-1cj-4-12-1800θicBxBB-1bx1x2x3x4x50x4-3-10[-3]10--12x25/20110-1/25/2z-4/-1--6/-3--σj/alj再確定換出變量和換入變量，42/66cj-4-12-1800θicBxBB-1bx1x2x3x4x5-18x311/301-1/30-12x23/2-1/3101/3-1/2z-36σj/alj求B-1cj-4-12-1800θicBxBB-1bx1x2x3x4x5-18x311/301-1/30-12x23/2-1/3101/3-1/2z-200-2-6σj判斷是否最優(yōu)第五節(jié)靈敏度分析問題的由來，先看一個方程

x1+

x2=10

1.01x1+

x2=11,x1=100,x2=-90如果1.01增加到1.011，該方程解會如何變化？

x1+x2=10

1.011x1+

x2=11,x1=1/0.011=90.91,x2=-80.91

Δa21/a21=0.001/1.01=0.1%,

Δx1/x1=(90.91-100)/100=-9%,

43/66再看另外一個方程

x1+

x2=10

2.02x1+

x2=11,x1=0.980,x2=9.020如果2.02增加到2.022，該方程解會如何變化？

x1+x2=10

2.022x1+

x2=11,x1=0.978,

x2=9.022

Δa21/a21=0.002/2.02=0.1%,

Δx1/x1=(0.978-0.980)/0.980=0.2%,這時候，可以說，第一個方程組的解對于Δa21敏感，而第一個方程組則否。

44/66實際問題的數(shù)學模型，應當避免第一種情況，因為實際中很難避免將1.011算成1.01。

LP問題也會遇到類似情況。其中A、b和C都是從實際中收集、歸納和整理的數(shù)字，很難保證與實際情況絲毫不差。

如果LP問題的解因為這些數(shù)字與實際稍有偏差就會相差很大，那就說明利用A、b、C構造的LP問題模型不能用做實際問題的模型。

合理的

LP問題模型不應敏感于A、b或C的些小變化。本節(jié)課學習，當A、b或C發(fā)生小變動時，最優(yōu)解將如何變化，看一看對這些變化的敏感性。45/66靈敏度分析的步驟：1.先用最終單純形表中B-1變換A、b和C的增量

Δb’

=B-1Δb，

ΔPj’

=B-1ΔPj，2.檢查(P)是否仍為可行解。3.檢查(D)是否仍為可行解。4.根據(jù)下表中各種情況決定下一步行動。46/66(P)(D)結論或繼續(xù)計算的步驟可行解可行解非可行解非可行解可行解非可行解可行解非可行解問題的最優(yōu)解或最優(yōu)解不變用單純形法繼續(xù)迭代求最優(yōu)解用對偶單純形法繼續(xù)迭代求最優(yōu)解引進人工變量，編制新單純形表重新計算[例]設備臺時/件產(chǎn)品可用臺時（千小時）產(chǎn)品1產(chǎn)品2下料設備A104機加工設備B0212焊接設備C3218產(chǎn)品單價3元/件5元/件一、分析C的變化問題1

若兩種產(chǎn)品單價分別變成5元/件和3.25元/件，兩種產(chǎn)品最優(yōu)產(chǎn)量是否變化？問題2使最優(yōu)產(chǎn)量不變的第二種單價變化范圍多大？47/6648/66cj53.25000θicBxBB-1bx1x2x3x4x50x32001[1/3]-1/363.25x260101/20125x12100-1/31/3-z29.500025/600-1σj為了回答問題1，將兩種產(chǎn)品改變后的單價填入最終單純形表，并重新計算檢驗數(shù)，得到：0x460031-13.25x2301-3/201/25x1410100z29.7500-0.1250-3.25/2σj為了回答問題2，用5+Δc2表示第二種產(chǎn)品改變后的單價，并填入最終單純形表，并重新計算檢驗數(shù)，得到：c4=-3/2-Δc2/2，若使最優(yōu)解不變，則須有c4≤0-3/2-Δc2/2≤0，Δc2≥-349/66cj35+Δc2000θicBxBB-1bx1x2x3x4x50x320011/3-1/35+Δc2x260101/203x12100-1/31/3z000-3/2-Δc2/2-1σj若回答使最優(yōu)產(chǎn)量不變的第一種產(chǎn)品單價變化范圍，則用3+Δc1表示第一種產(chǎn)品改變后的單價，并填入最終單純形表，并重新計算檢驗數(shù)：c4=-3/2+Δc1/3，

c5=-1-Δc1/3，若使最優(yōu)解不變，則須有c4≤0，c5≤0，-3/2+Δc1/3≤0，-1-Δc1/3≤0，

-3≤Δc1≤9/250/66cj3+Δc15000θicBxBB-1bx1x2x3x4x50x320011/3-1/35x260101/203+Δc1x12100-1/31/3z36+2Δc1000-3/2+Δc1/3-1-Δc1/3σj二、分析b的變化若Δb=(0,

Δb2,0)T，問最優(yōu)解是否改變，為此，先計算

Δb2/3

Δb’=B-1Δb==Δb2/2-Δb2/3將其添入最終單純形表中，得到：51/6611/3-1/3001/20Δb20-1/31/3052/66cj35000θicBxBB-1bx1x2x3x4x50x32+Δb2/30011/3-1/35x26+Δb2/20101/203x12-Δb2/3100-1/31/3zσj為使第二種設備可用臺時改變后的解仍然可行，須有：2+Δb2/3≥0，

6+Δb2/2≥0，

2-Δb2/3≥0，max{-6,-12}≤Δb2≤min{6},-6≤Δb2≤6，對于Δb1和Δb3，同樣處理。三、分析增添新變量xj的情況如果增加新產(chǎn)品x6，單價為4元，問如何生產(chǎn)，總收入最多。設其所需三種設備臺時為

25/3

P6=0，變換，得P6

‘==0

11/3

將P6’填入最終單純形表，并重新計算檢驗數(shù)：

53/6611/3-1/3201/2000-1/31/314x61.2000.61/5-0.215x260101/2003x11.610-0.2-0.40.40z39.600-1.8-2.1-0.40σj54/66cj350004θicBxBB-1bx1x2x3x4x5x60x320011/3-1/3[5/3]6/55x260101/200-3x12100-1/31/31/36z36000-3/2-13σj四、分析技術系數(shù)aij變化時的情況如果aij對應的xj是非基變量，處理辦法同“三”。如果xj是基變量，先變換Pj，

Pj‘=B-1Pj

[例1]第二種產(chǎn)品用設備臺時由

0改為0

2P2=223/2單價由5元增加為5.5元/件，用x*2表示這種“新”產(chǎn)品產(chǎn)量，先變換P2如下，然后添入最終單純形表，并重新計算檢驗數(shù)：

55/661/6

P2‘==1

-1/656/6611/3-1/3001/2020-1/31/33/2cj355.5000θicBxBB-1bx1x2x*2x3x4x50x32001/611/3-1/3125x2601101/2063x1210-1/60-1/31/3-z360010-3/2-1σj檢驗數(shù)均已非正，說明已經(jīng)得到最優(yōu)解，銷售收入增加了(42-36)/36=16.7%。57/66cj355.5000θicBxBB-1bx1x2x*2x3x4x50x310-1/6011/4-1/35.5x*2601101/203x1311/600-1/41/3z42000-2-1σj如果第二種產(chǎn)品用設備臺時由

0改為1/2

2P2=221/2單價由5元增為5.5元，用x*2表示這種“新”產(chǎn)品產(chǎn)量，先變換P2如下，然后添入最終單純形表，并重新計算檢驗數(shù)：

58/661

P2‘==1

-1/259/6611/3-1/31/201/2020-1/31/31/2cj355.5000θicBxBB-1bx1x2x*2x3x4x50x3200[1]11/3-1/325x2601101/2063x1210-1/20-1/31/3-z360020-3/2-1σj需要將x2排除在外，辦法是將其視為人工變量。60/66cj355.5000θicBxBB-1bx1x2x*2x3x4x55.5x*2200111/3-1/35x24010-11/61/33x131001/2-1/61/6z000-2-13