運(yùn)籌學(xué)2對(duì)偶理論課件

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

B和C三種設(shè)備單位臺(tái)時(shí)賣價(jià)或租價(jià)，則，總進(jìn)項(xiàng)w可表示成w=4y1

+12y2+18y3生產(chǎn)兩種產(chǎn)品消耗的設(shè)備臺(tái)時(shí)的價(jià)值（或稱出售或出租兩種產(chǎn)品所用設(shè)備臺(tái)時(shí)的進(jìn)項(xiàng)）分別是

1y1

+0y2+3y3和0y1

+2y2+2y3兩種產(chǎn)品售價(jià)分別是3和5。出售或出租產(chǎn)品所用設(shè)備臺(tái)時(shí)的進(jìn)項(xiàng)不能低于售價(jià)。所以，應(yīng)有

1y1

+0y2+3y3

≥3和0y1

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

+12y2+18y3是總消耗。4/66用y1、y2和y3分別表示A、B和C三種設(shè)備單位5/66回答y1、y2和y3各是多少的問(wèn)題，可表示如下：Minw=4y1

+12y2+18y3

s.t.

y1

+3y3≥3

2y2

+2y3≥5y1,y2,y3≥0該問(wèn)題叫做原問(wèn)題(P)的對(duì)偶問(wèn)題(D)。可看出，Maxz=CXMinw=bTY(P)s.t.AX≤b

(D)

s.t.ATY≥CT

X≥0Y≥05/66回答y1、y2和y3各是多少的問(wèn)題，可表示如下：6/66cj35000θicBxBB-1bx1x2x3x4x50x320011/3-1/35x260101/203x12100-1/31/3z36000-3/2-1σj若要問(wèn)對(duì)偶問(wèn)題的解是什么，可以看解(P)時(shí)得到的最終單純形表。最終單純形表6/66cj35000cBxBB-1bx1x2x3x4x507/66從該表松弛變量的檢驗(yàn)數(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)這是對(duì)偶問(wèn)題有趣的一個(gè)方面。7/66從該表松弛變量的檢驗(yàn)數(shù)行得到：8/66二、對(duì)稱的對(duì)偶問(wèn)題一般形式上面的例子叫做對(duì)稱的對(duì)偶問(wèn)題。三、非對(duì)稱的對(duì)偶問(wèn)題請(qǐng)見(jiàn)教科書第三版第52頁(yè)或第四版第53頁(yè)的表。8/66二、對(duì)稱的對(duì)偶問(wèn)題一般形式9/66事項(xiàng)原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）AbC目標(biāo)函數(shù)n個(gè)決策變量xj≥0xj≤0xj無(wú)約束m個(gè)決策變量yi≥0yi≤0yi無(wú)約束9/66事項(xiàng)原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）A第二節(jié)對(duì)偶理論基本性質(zhì)一、對(duì)稱形式單純形法矩陣表達(dá)Maxz=CX

s.t.AX≤b

X≥0化成標(biāo)準(zhǔn)形式Maxz=CX+0Xs

s.t.AX+IXs=b

X，Xs≥0Xs

=(xs1,xs2,…,xsm)T是松弛變量10/66第二節(jié)對(duì)偶理論基本性質(zhì)一、對(duì)稱形式單純形法矩陣表達(dá)10/6令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的檢驗(yàn)數(shù)，令σj=cj-CBB-1Pj，若所有的σj<0，即CN-CBB-1N≤0(2)則表示目前的基可行解最優(yōu)。另外，基變量XB

的檢驗(yàn)數(shù)是CB-CBB-1B=0(3)11/66令X=XB，(C,松弛變量Xs

=(xs1,xs2,…,xsm)T的檢驗(yàn)數(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松弛變量Xs=(xs1,xs2,…,xsm)T的檢驗(yàn)數(shù)再將(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再將(1)z=CBB-1b、(5)和(4)寫在一起：13

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/66Minw=YTb14/615/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≥015/66[例]Maxz=3x1+5x2Maxz=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/107Maxz=3x1+5x2+0x17/66bj4121800MMθibByBB-1Cy1y2y3y4y5y6y7My63103-1010-My750[2]20-1015/2w8M4-M12-2M18-2MMM00σj對(duì)偶問(wèn)題初始單純形表My6310[3]-10103/312y25/20110-1/201/25/2w3M+304-M06-3MM60M-6σjσ3應(yīng)當(dāng)是18-5M，但錯(cuò)算為18-2M，所以誤選y2為換入變量。以下將錯(cuò)就錯(cuò)算下去。17/66bj4121800MMbByBB-1Cy1y2y318/66bj4121800MMθibByBB-1Cy1y2y3y4y5y6y718y311/301-1/301/3012y23/2-1/3101/3-1/2-1/31/2w3620026M-2M-6σj對(duì)偶問(wèn)題最終單純形表18/66bj4121800MMbByBB-1Cy1y2y319/66bj4121800MMθibByBB-1Cy1y2y3y4y5y6y7My6310[3]-10101My750220-1015/2w8M4-M12-2M18-5MMM00σj重新算一遍，對(duì)偶問(wèn)題初始單純形表18y311/301-1/301/30-My73-2/3[2]02/3-1-2/313/2w2M/3-212-M0-2M/3+6M5M/3-60σj19/66bj4121800MMbByBB-1Cy1y2y320/66對(duì)偶問(wèn)題最終單純形表bj4121800MMθibByBB-1Cy1y2y3y4y5y6y718y311/301-1/301/3012y23/2-1/3101/3-1/2-1/31/2w3620026M-2M-6σj計(jì)算結(jié)果同上。20/66對(duì)偶問(wèn)題最終單純形表bj4121800MMbByB21/66事項(xiàng)原問(wèn)題變量原問(wèn)題松弛變量xBB-1bx1x2x3x4x5x320011/3-1/3x260101/20x12100-1/31/3z36000-3/2-1變量對(duì)偶問(wèn)題剩余變量對(duì)偶問(wèn)題變量y4y5y1y2y3(P)最終單純形表21/66事項(xiàng)原問(wèn)題變量原問(wèn)題松弛變量xBB-1bx1x2x22/66事項(xiàng)對(duì)偶問(wèn)題變量對(duì)偶問(wèn)題剩余變量bByBB-1Cy1y2y3y4y518y311/301-1/3012y23/2-1/3101/3-1/2w36原問(wèn)題松弛變量原問(wèn)題變量x3x4x5x1x2(D)對(duì)偶問(wèn)題最終單純形表22/66事項(xiàng)對(duì)偶問(wèn)題變量對(duì)偶問(wèn)題剩余變量bByBB-1Cy

23/107

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

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

(D)無(wú)可行解時(shí)，(P)無(wú)可行解或目標(biāo)函數(shù)值無(wú)界。推論3若(P)有可行解，而(D)無(wú)可行解，則(P)目標(biāo)函數(shù)值無(wú)界；反之，(D)有可行解，而(P)無(wú)可行解，則(D)目標(biāo)函數(shù)值無(wú)界。24/66推論1(P)任一可行解目標(biāo)函數(shù)值是(D)目標(biāo)函數(shù)值下界。反

25/107

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

(D)目標(biāo)函數(shù)值有下界，因此，(P)和(D)都有最優(yōu)解。另外，根據(jù)ATY≥CT，Y≥0，w=YTb=CBB-1b=z知道，當(dāng)(P)取得最優(yōu)解時(shí)，(D)有可行解，且有w=z，根據(jù)性質(zhì)2（最優(yōu)性），(D)的可行解也是最優(yōu)解，證畢。26/1073.對(duì)偶定理。若(P)和(D)均有可行解，則均有最優(yōu)解，

27/107

27/107

28/107

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

Maxz=3x1+5x2

s.t.

x1

≤4

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

x1，x2

≥0bT=(4,12,18)是資源，即可利用的設(shè)備臺(tái)班量。在討論如何才能贏利最多時(shí)，沒(méi)有考慮三種設(shè)備單位臺(tái)班的價(jià)格。它們的價(jià)格藏在深處。29/66第三節(jié)影子價(jià)格一、影子價(jià)格29/6630/66有些經(jīng)濟(jì)學(xué)家認(rèn)為，自由的市場(chǎng)交易，商品成交價(jià)格能夠反映其真正價(jià)值。但是，資源的現(xiàn)實(shí)市場(chǎng)價(jià)格并不反映其“真正”價(jià)值。還有些經(jīng)濟(jì)學(xué)家認(rèn)為，影子價(jià)格是原本無(wú)交易的資源，在轉(zhuǎn)為其他用途時(shí)的價(jià)格，或者說(shuō)，另外再增加一個(gè)單位此種資源需要付出的價(jià)格。這個(gè)問(wèn)題可以利用對(duì)偶問(wèn)題的解給予某種解釋。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)30/66有些經(jīng)濟(jì)學(xué)家認(rèn)為，自由的市場(chǎng)交易，商品成交價(jià)格能夠31/66這就是說(shuō)，三種設(shè)備每臺(tái)時(shí)的價(jià)格分別是0,3/2和1。第一種設(shè)備每臺(tái)時(shí)的價(jià)格為0，這是什么意思？請(qǐng)看原問(wèn)題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)31/66這就是說(shuō)，三種設(shè)備每臺(tái)時(shí)的價(jià)格分別是0,3/2和32/66

32/66

33/107612x1x26449x1=42x2=123x1+2x2=18(2,6)z=3x1+5x2=36z=15oABCDEFG33/107612x1x26449x1=42x2=123x134/107612x1x26449x1=42x2=123x1+2x2=18(2,6)z=3x1+5x2=36z=15oABCDEFGx1=5Δz=36-36=034/107612x1x26449x1=42x2=123x135/107612x1x26449x1=42x2=123x1+2x2=18(5/3,6.5)z=3x1+5x2=36z=15oABCDEFG2x2=13z=3x1+5x2=37.5Δz=37.5-36=1.535/107612x1x26449x1=42x2=123x136/107612x1x26449x1=42x2=123x1+2x2=18z=3x1+5x2=36z=15oABCDEFGz=3x1+5x2=373x1+2x2=19Δz=37-36=136/107612x1x26449x1=42x2=123x1第四節(jié)對(duì)偶單純形法一、對(duì)偶單純形法思路Minw=bTY-0Ys

(D)

s.t.ATY-IYs=CT

Y，Ys≥037/66第四節(jié)對(duì)偶單純形法一、對(duì)偶單純形法思路37/66二、對(duì)偶單純形法計(jì)算步驟Step1：找出初始可行基、初始單純形表和初始基解。Step2：若B-1b≥0，初始基解是最優(yōu)解，停。否則，下一步。Step3：取(B-1b)l=min{(B-1b)i|(B-1b)i<0}，第l行基變量換出。若所有的alj≥0，無(wú)可行解，停。Step4：計(jì)算σk/alk=min{σj/alj|alj<0}，第k列非基變量換入。Step5：求基的逆矩陣、新基解和z。回Step2。38/107二、對(duì)偶單純形法計(jì)算步驟Step1：找出初始可行基、初始單純39/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≥039/66[例1]Minw=4x1+12x2+18x340/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先確定換出變量，再換入變量40/66cj-4-12-1800cBxBB-1bx1x2x41/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再確定換出變量和換入變量，41/66cj-4-12-1800cBxBB-1bx1x2x42/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)42/66cj-4-12-1800cBxBB-1bx1x2x第五節(jié)靈敏度分析問(wèn)題的由來(lái)，先看一個(gè)方程

x1+

x2=10

1.01x1+

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

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第五節(jié)靈敏度分析問(wèn)題的由來(lái)，先看一個(gè)方程43/66再看另外一個(gè)方程

x1+

x2=10

2.02x1+

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

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%,這時(shí)候，可以說(shuō)，第一個(gè)方程組的解對(duì)于Δa21敏感，而第一個(gè)方程組則否。

44/66再看另外一個(gè)方程44/66實(shí)際問(wèn)題的數(shù)學(xué)模型，應(yīng)當(dāng)避免第一種情況，因?yàn)閷?shí)際中很難避免將1.011算成1.01。

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

如果LP問(wèn)題的解因?yàn)檫@些數(shù)字與實(shí)際稍有偏差就會(huì)相差很大，那就說(shuō)明利用A、b、C構(gòu)造的LP問(wèn)題模型不能用做實(shí)際問(wèn)題的模型。

合理的

LP問(wèn)題模型不應(yīng)敏感于A、b或C的些小變化。本節(jié)課學(xué)習(xí)，當(dāng)A、b或C發(fā)生小變動(dòng)時(shí)，最優(yōu)解將如何變化，看一看對(duì)這些變化的敏感性。45/66實(shí)際問(wèn)題的數(shù)學(xué)模型，應(yīng)當(dāng)避免第一種情況，因?yàn)殪`敏度分析的步驟：1.先用最終單純形表中B-1變換A、b和C的增量

Δb’

=B-1Δb，

ΔPj’

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

若兩種產(chǎn)品單價(jià)分別變成5元/件和3.25元/件，兩種產(chǎn)品最優(yōu)產(chǎn)量是否變化？問(wèn)題2使最優(yōu)產(chǎn)量不變的第二種單價(jià)變化范圍多大？47/66[例]設(shè)備臺(tái)時(shí)/件產(chǎn)品可用臺(tái)時(shí)產(chǎn)品1產(chǎn)品2下料設(shè)備A104機(jī)48/66cj53.25000θicBxBB-1bx1x2x3x4x50x32001[1/3]-1/363.25x260101/20125x12100-1/31/3-z29.500025/600-1σj為了回答問(wèn)題1，將兩種產(chǎn)品改變后的單價(jià)填入最終單純形表，并重新計(jì)算檢驗(yàn)數(shù)，得到：0x460031-13.25x2301-3/201/25x1410100z29.7500-0.1250-3.25/2σj48/66cj53.25000cBxBB-1bx1x2x3x為了回答問(wèn)題2，用5+Δc2表示第二種產(chǎn)品改變后的單價(jià)，并填入最終單純形表，并重新計(jì)算檢驗(yà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為了回答問(wèn)題2，用5+Δc2表示第二種產(chǎn)品改變后的單價(jià)，并填若回答使最優(yōu)產(chǎn)量不變的第一種產(chǎn)品單價(jià)變化范圍，則用3+Δc1表示第一種產(chǎn)品改變后的單價(jià)，并填入最終單純形表，并重新計(jì)算檢驗(yà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若回答使最優(yōu)產(chǎn)量不變的第一種產(chǎn)品單價(jià)變化范圍，則用3+Δc1二、分析b的變化若Δb=(0,

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

Δb2/3

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

6+Δb2/2≥0，

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

25/3

P6=0，變換，得P6

‘==0

11/3

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

53/6611/3-1/3201/2000-1/31/31三、分析增添新變量xj的情況53/6611/3-1/324x61.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σj4x61.2000.61/5-0.215x260101/20四、分析技術(shù)系數(shù)aij變化時(shí)的情況如果aij對(duì)應(yīng)的xj是非基變量，處理辦法同“三”。如果xj是基變量，先變換Pj，

Pj‘=B-1Pj

[例1]第二種產(chǎn)品用設(shè)備臺(tái)時(shí)由

0改為0

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

55/66四、分析技術(shù)系數(shù)aij變化時(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

檢驗(yàn)數(shù)均已非正，說(shuō)明已經(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檢驗(yàn)數(shù)均已非正，說(shuō)明已經(jīng)得到最優(yōu)解，銷售收入增加了(42-3如果第二種產(chǎn)品用設(shè)備臺(tái)時(shí)由

0改為1/2

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

58/66如果第二種產(chǎn)品用設(shè)備臺(tái)時(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/6-1/3σj需要將x2排除在外，辦法是將其視為人工變量。60/66cj361/66cj3-M5.5000θicBxBB-1bx1x2x*2x3x4x55.5x*2200111/3-1/3--Mx24010-11/6[1/3]123x131001/2-1/61/618z000-M-7M/6-4/3M/3+4/3σj5.5x*260-101/200x5120-0-31/213x111-01-1/40z360-0-3-20σj61/66cj3-M5.5000cBxBB-1bx1x2x*可將X*=(x1,x2,x3,x4,x5)T=(1,6,0,0,12)T代入修改P2后的原問(wèn)題檢查。Maxz=3x1+5.5x2s.t.

x1

+x2/2≤4

2x2≤12

3x1+x2/2≤18

x1，x2

≥0不難發(fā)現(xiàn)，第一和第二種設(shè)備得到了充分利用，但第三種設(shè)備有12,000個(gè)臺(tái)時(shí)空閑。62/66可將X*=(x1,x2,x3,x4,x5)T=(1五、增加約束條件現(xiàn)在，為了提高產(chǎn)品性能，需利用第四種設(shè)備。兩種產(chǎn)品需要的臺(tái)時(shí)都是兩個(gè)單位，這種設(shè)備可用臺(tái)時(shí)是14,000個(gè)。于是，原問(wèn)題變成，Maxz=3x1+5x2s.t.

x1

+≤4

2x2≤12

3x1+2x2

≤18

2x1+2x2

≤14

x1，x2

≥063/66五、增加約束條件63/66先將P1,P2將變換成單位列向量。第4行-2×第2行-2×第3行

-2000-1/3-2/3164/66cj350000θicBxBB-1bx1x2x3x4x5x60x320011/3-1/305x260101/2003x12100-1/31/300x614220001zσj64/66cj350000cBxBB-1bx1x2x3x4x

σ4=-3/2-1=

σ5這是非可行解，用對(duì)偶單純形法求解，先確定換出變量，再確定換入變量。

x6換出，x5換入。65/66cj350000θicBxBB-1bx1x2x3x4x5x60x320011/3-1/305x260101/2003x12100-1/31/300x6-2000-1/3-2/31z000-1.5-10σjσj/a4j---4.51.5-65/66cj350000cBxBB-1bx1x2x3x4x66/66cj350000θicBxBB-1bx1x2x3x4x5x60x330011/20-0.55x260101/2003x11100-1/200.50x530001/21-1.5z33000-10-1.5σj這是最優(yōu)解。X*=(x1,x2,x3,x4,x5,x6)T=(1,6,3,0,3,0)T第一和第三種設(shè)備未得到充分利用。z*=33。66/66cj350000cBxBB-1bx1x2x3x4x第二章線性規(guī)劃對(duì)偶理論第一節(jié)線性規(guī)劃對(duì)偶理論第二節(jié)對(duì)偶問(wèn)題基本性質(zhì)第三節(jié)影子價(jià)格第四節(jié)對(duì)偶單純形法第五節(jié)靈敏度分析67/66第二章線性規(guī)劃對(duì)偶理論第一節(jié)線性規(guī)劃對(duì)偶理論1/66第一節(jié)線性規(guī)劃對(duì)偶理論一、對(duì)偶問(wèn)題的提出[例]68/66設(shè)備臺(tái)時(shí)/件產(chǎn)品可用臺(tái)時(shí)（千小時(shí)）產(chǎn)品1產(chǎn)品2下料設(shè)備A104機(jī)加工設(shè)備B0212焊接設(shè)備C3218產(chǎn)品單價(jià)3元/件5元/件第一節(jié)線性規(guī)劃對(duì)偶理論一、對(duì)偶問(wèn)題的提出2/66設(shè)備臺(tái)時(shí)/69/66生產(chǎn)是為贏利（取得收入）。還有別的辦法贏利（取得收入）。例如，賣出或出租設(shè)備。問(wèn)，三種設(shè)備賣價(jià)或租價(jià)各應(yīng)是多少，進(jìn)項(xiàng)才不低于自己生產(chǎn)時(shí)的銷售收入？原來(lái)的問(wèn)題：兩種產(chǎn)品各生產(chǎn)多少，利潤(rùn)總額最大？3/66生產(chǎn)是為贏利（取得收入）。還有別的辦法贏利（取得收入70/66用y1、y2和y3分別表示A、

B和C三種設(shè)備單位臺(tái)時(shí)賣價(jià)或租價(jià)，則，總進(jìn)項(xiàng)w可表示成w=4y1

+12y2+18y3生產(chǎn)兩種產(chǎn)品消耗的設(shè)備臺(tái)時(shí)的價(jià)值（或稱出售或出租兩種產(chǎn)品所用設(shè)備臺(tái)時(shí)的進(jìn)項(xiàng)）分別是

1y1

+0y2+3y3和0y1

+2y2+2y3兩種產(chǎn)品售價(jià)分別是3和5。出售或出租產(chǎn)品所用設(shè)備臺(tái)時(shí)的進(jìn)項(xiàng)不能低于售價(jià)。所以，應(yīng)有

1y1

+0y2+3y3

≥3和0y1

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

+12y2+18y3是總消耗。4/66用y1、y2和y3分別表示A、B和C三種設(shè)備單位71/66回答y1、y2和y3各是多少的問(wèn)題，可表示如下：Minw=4y1

+12y2+18y3

s.t.

y1

+3y3≥3

2y2

+2y3≥5y1,y2,y3≥0該問(wèn)題叫做原問(wèn)題(P)的對(duì)偶問(wèn)題(D)。可看出，Maxz=CXMinw=bTY(P)s.t.AX≤b

(D)

s.t.ATY≥CT

X≥0Y≥05/66回答y1、y2和y3各是多少的問(wèn)題，可表示如下：72/66cj35000θicBxBB-1bx1x2x3x4x50x320011/3-1/35x260101/203x12100-1/31/3z36000-3/2-1σj若要問(wèn)對(duì)偶問(wèn)題的解是什么，可以看解(P)時(shí)得到的最終單純形表。最終單純形表6/66cj35000cBxBB-1bx1x2x3x4x5073/66從該表松弛變量的檢驗(yàn)數(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)這是對(duì)偶問(wèn)題有趣的一個(gè)方面。7/66從該表松弛變量的檢驗(yàn)數(shù)行得到：74/66二、對(duì)稱的對(duì)偶問(wèn)題一般形式上面的例子叫做對(duì)稱的對(duì)偶問(wèn)題。三、非對(duì)稱的對(duì)偶問(wèn)題請(qǐng)見(jiàn)教科書第三版第52頁(yè)或第四版第53頁(yè)的表。8/66二、對(duì)稱的對(duì)偶問(wèn)題一般形式75/66事項(xiàng)原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）AbC目標(biāo)函數(shù)n個(gè)決策變量xj≥0xj≤0xj無(wú)約束m個(gè)決策變量yi≥0yi≤0yi無(wú)約束9/66事項(xiàng)原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）A第二節(jié)對(duì)偶理論基本性質(zhì)一、對(duì)稱形式單純形法矩陣表達(dá)Maxz=CX

s.t.AX≤b

X≥0化成標(biāo)準(zhǔn)形式Maxz=CX+0Xs

s.t.AX+IXs=b

X，Xs≥0Xs

=(xs1,xs2,…,xsm)T是松弛變量76/66第二節(jié)對(duì)偶理論基本性質(zhì)一、對(duì)稱形式單純形法矩陣表達(dá)10/6令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的檢驗(yàn)數(shù)，令σj=cj-CBB-1Pj，若所有的σj<0，即CN-CBB-1N≤0(2)則表示目前的基可行解最優(yōu)。另外，基變量XB

的檢驗(yàn)數(shù)是CB-CBB-1B=0(3)77/66令X=XB，(C,松弛變量Xs

=(xs1,xs2,…,xsm)T的檢驗(yàn)數(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)

78/66松弛變量Xs=(xs1,xs2,…,xsm)T的檢驗(yàn)數(shù)再將(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

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

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是剩余變量

80/66Minw=YTb14/681/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≥015/66[例]Maxz=3x1+5x2Maxz=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

82/107Maxz=3x1+5x2+0x83/66bj4121800MMθibByBB-1Cy1y2y3y4y5y6y7My63103-1010-My750[2]20-1015/2w8M4-M12-2M18-2MMM00σj對(duì)偶問(wèn)題初始單純形表My6310[3]-10103/312y25/20110-1/201/25/2w3M+304-M06-3MM60M-6σjσ3應(yīng)當(dāng)是18-5M，但錯(cuò)算為18-2M，所以誤選y2為換入變量。以下將錯(cuò)就錯(cuò)算下去。17/66bj41