清華大學(xué)運(yùn)籌學(xué)對(duì)偶理論

1清華大學(xué)運(yùn)籌學(xué)對(duì)偶理論原來的問題：兩種產(chǎn)品各生產(chǎn)多少，利潤(rùn)總額最大？生產(chǎn)是為贏利（取得收入）。還有別的辦法贏利（取得收入）。例如，賣出或出租設(shè)備。問，三種設(shè)備賣價(jià)或租價(jià)各應(yīng)是多少，進(jìn)項(xiàng)才不低于自己生產(chǎn)時(shí)的銷售收入？2/66第1頁/共65頁用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

≥33/66和0y1

+2y2+2y3

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

+12y2+18y3是總消耗。第2頁/共65頁回答y1、y2和y3各是多少的問題，可表示如下：Min

w=4y1

+12y2+18y3s.t.

y1

+3y3

≥32y2

+2y3

≥5y1,

y2,

y3≥0該問題叫做原問題(P)的對(duì)偶問題(D)?？煽闯?，4/66Min

w=bTYMax

z=CX(P)

s.t.

AX≤bX≥0(D)

.

ATY≥CTY≥0第3頁/共65頁cj35000θicBxBB-1bx1x2x3x4x50x320011/3-1/35x260101/203x12100-1/31/3z36000-3/2-1σj5/66若要問對(duì)偶問題的解是什么，可以看解

(P)時(shí)得到的最終單純形表。最終單純形表第4頁/共65頁從該表松弛變量的檢驗(yàn)數(shù)行得到：6/66σ3

=0，

σ4

=

-3/2，σ5

=

-1，y1

=0，y2

=3/2，y3

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

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

+3×1

=32×3/2+2×1

=5y1,

y2,

y3≥0(2)(3)(4)這是對(duì)偶問題有趣的一個(gè)方面。第5頁/共65頁二、對(duì)稱的對(duì)偶問題一般形式上面的例子叫做對(duì)稱的對(duì)偶問題。三、非對(duì)稱的對(duì)偶問題請(qǐng)見教科書第三版第52頁或第四版第53頁的表。7/66第6頁/共65頁事項(xiàng)原問題（對(duì)偶問題）對(duì)偶問題（原問題）AbC目標(biāo)函數(shù)n個(gè)決策變量xj≥0xj≤0xj無約束第7頁/共65頁m個(gè)決策變量yi≥0yi≤0yi無約束8/66第二節(jié)對(duì)偶理論基本性質(zhì)一、對(duì)稱形式單純形法矩陣表達(dá)Max

z=CXs.t.

AX≤bX≥0化成標(biāo)準(zhǔn)形式Max

z=CX+0Xs.

AX+IXs=bX，Xs≥0Xs

=(xs1,xs2,…,xsm)T

是松弛變量9/66第8頁/共65頁令

X

=

XB

，(C,

0)=(CB,

CN)10/66Xs

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，即C第9頁-/共C65頁B-1N≤0N

B(2)松弛變量Xs

=(xs1,xs2,…,xsm)T的檢驗(yàn)數(shù)是0-CBB-1I

≤0，即-CBB-1≤0(4)將(2)和(3)寫在一起：或(C

，C

)-C

B-1(B，N)≤0，即11/66(CB，CN)

-

(CBB-1B，CBB-1N)≤0第10頁/共65頁再將(1)z=CBB-1b

、(5)和(4)寫在一起：z=CBB-1b(1)(5)C-

CBB-1A≤0-CBB-1≤012/66(4)令YT=CBB-1，w=YTb(1’)第1C1頁-/共Y65頁TA≤0(5’)Min

w=YTb(D)s.t.

ATY≥CTY≥0添加剩余變量后，變成Min

w=YTb+0Ys(D)

s.t.ATY-IYs=CTY,

Ys≥0剩余變量13/66Ys

=(ys1,ys2,…,ys,n-m)T

是第12頁/共65頁[例]

Max

z=3x1+5x214/66s.t.

x1≤4(P)y1y2y32x2

≤123x1+2x2

≤18x1，x2

≥0Min

w=4y1

+12y2+18y3(D)s.t.

y1

+3y3

≥3

x12y2

+2y3

≥5

x2y1,

y2,

y3≥0第13頁/共65頁Max

z=3x1+5x2

+0x3+0x4

+0x5.

x1

+

x3=4(P)=12=182x2

+

x43x1+2x2

+

x5x1，x2

，x3

，x4

，x5

≥0Min

w=4y1

23+0y4+0y5+My6+My715/107+12y第14頁+/共1685頁ybj4121800MMθibByBB-1Cy1y2y3y4y5y6y7My63103-1010-My750[2]20-1015/2w8M4-M12-2M18-2MMM00σj對(duì)偶問題初始單純形表My6310[3]-101012y25/20110-1/201/2w3M+304-M06-3MM60M-616/66σ3應(yīng)當(dāng)是18-5M，但錯(cuò)算為18-2M，所以誤選y2

為換入變量。以下將錯(cuò)就錯(cuò)算下去。3/35/2σj第15頁/共65頁bj4121800MMθibByBB-1Cy1y2y3y4y5y6y718y311/301-1/301/3012y23/2-1/3101/3-1/2-1/31/2w3620026M-2M-6σj17/66對(duì)偶問題最終單純形表第16頁/共65頁重新算一遍，對(duì)偶問題初始單純形表bj4121800MMθibByBB-1Cy1y2y3y4y5y6y7My6310[3]-10101My750220-1015/2w8M4-M12-2M18-5MMM00σj18y311/301-1/301/30-My73-2/3[2]02/3-1-2/313/2w2M/3-212-M0-2M/3+6M5M/3-60σj18/66第17頁/共65頁對(duì)偶問題最終單純形表bj4121800MMθibByBB-1Cy1y2y3y4y5y6y718y311/301-1/301/3012y23/2-1/3101/3-1/2-1/31/2w3620026M-2M-6σj19/66計(jì)算結(jié)果同上。第18頁/共65頁事項(xiàng)原問題變量原問題松弛變量xBB-1bx1x2x3x4x5x320011/3-1/3x260101/20x12100-1/31/3z36000-3/2-1變量對(duì)偶問題剩余變量對(duì)偶問題變量y4y5y1y2y320/66(P)最終單純形表第19頁/共65頁事項(xiàng)對(duì)偶問題變量對(duì)偶問題剩余變量bByBB-1Cy1y2y3y4y518y311/301-1/3012y23/2-1/3101/3-1/2w36原問題松弛變量原問題變量x3x4x5x1x221/66(D)對(duì)偶問題最終單純形表第20頁/共65頁■22/66第21頁/共65頁推論1(P)任一可行解目標(biāo)函數(shù)值

是(D)目標(biāo)函數(shù)值下界。反之，(D)任一可行解目標(biāo)函數(shù)值是(P)目標(biāo)函數(shù)值上界。推論2若(P)有可行解且目標(biāo)函數(shù)

值無界，則(D)無可行解；反之，

(D)有可行解且目標(biāo)函數(shù)無界，則

(P)無可行解。當(dāng)(D)無可行解時(shí)，第22頁/共65頁(P)無可行解或目標(biāo)函數(shù)值無界。23/66■24/66第23頁/共65頁3.對(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知25/107第24頁/共65頁道，當(dāng)(P)取得最優(yōu)解時(shí)，(D)有可行解，且有w=z，根據(jù)性質(zhì)2（最優(yōu)■26/107第25頁/共65頁■27/107第26頁/共65頁第三節(jié)影子價(jià)格一、影子價(jià)格在例子Max

z=3x1+5x2s.t.

x1≤4(P)2x2

≤123x1+2x2

≤18x1，x2

≥0bT=(4,12,18)是資源，即可利用的設(shè)備臺(tái)班量。在討論如何才能贏利最多時(shí)，沒有考慮三種設(shè)備單位臺(tái)28/66第27頁/共65頁有些經(jīng)濟(jì)學(xué)家認(rèn)為，自由的市場(chǎng)交易，商品成交價(jià)格能夠反映其真正價(jià)值。但是，資源的現(xiàn)實(shí)市場(chǎng)價(jià)格并不反映其“真正”價(jià)值。還有些經(jīng)濟(jì)學(xué)家認(rèn)為，影子價(jià)格是原本無交易的資源，在轉(zhuǎn)為其他用途時(shí)的價(jià)格，或者說，另外再增加一個(gè)單位此種資源需要付出的價(jià)格。這個(gè)問題可以利用對(duì)偶問題的解給予某種解釋。Min

w=4y1

+12y2+18y329/29(D)s.t.

y1

+3y3

≥32y2

+2y3

≥5y1,

y2,

y3≥0其解是(Y,Ys)T=(y1,y2,y3,y4,y5)=(0,3/2,1,0,0)第28頁/共65頁這就是說，三種設(shè)備每臺(tái)時(shí)的價(jià)格分別是0,3/2和1。第一種設(shè)備每臺(tái)時(shí)的價(jià)格為0，這是什么意思？請(qǐng)看原問題Max

z=3x1+5x2

+0x3+0x4

+0x530/30.

x1(P)+

x32x2

+

x4=4=123x1+2x2

+

x5

=18x1，x2

，x3

，x4

，x5

≥0其解是(X,Xs)T=(x1,x2,x3,x4,x5)=(2,6,2,0,0)第29頁/共65頁第30頁/共65頁31/3112x1x26492x2=12(2,

6)z=3x1+5x2=36z=15o32/32A

BC4

DE

x1=43x1+2x2=18FG6第31頁/共65頁12x1x26492x2=12z=3x1+5x2=36z=15o(2,

6)A

BC4

DEFGx1=4

x1=53x1+2x2=18Δz=36-36=06第32頁/共65頁33/3312x1x2649x1=43x1+2x2=18z=15oC4

DE(5/3,

6.5)FA

B2x2=132x2=12z=3x1+5x2Δz=z=3x1+5x2=36G6第33頁/共65頁34/3412x164x292x2=12z=15oC4

DEGz=3x1+5x2=37z=3x1+5x2=36x1=43x1+2x2=193x1+2x2=18FA

B35/35Δz=37-36=16第34頁/共65頁第四節(jié)對(duì)偶單純形法一、對(duì)偶單純形法思路Min

w=bTY-0Ys(D)s.t.

ATY-IYs=CTY，Ys≥036/36第35頁/共65頁二、對(duì)偶單純形法計(jì)算步驟Step1：找出初始可行基、初始單純形表和初始基解。Step2：若B-1b≥0，初始基解是最優(yōu)解，停。否則，下一步。Step3：取(B-1b)l=min{(B-1b)i|(B-1b)i<0}，第l行基變量換出。若所有的alj≥0，無可行解，停。Step4：計(jì)算σ第k3/6頁a/共l6k5頁=min{σj/alj|alj<0}，第k列非基變量換入。37/107Step5：求基的逆矩陣、新基解和z。[例1]Min

w=4x1+12x2

+18x338/66.

x1+

3x3

≥32x2

+

2x3

≥5x1，x2，x3

≥0將其改寫如下：Max

-w=

-4x1-12x2

-18x3+0x4+0x5s.t.-x1

-

3x3-2x2

-2x3+x4

=

-

3+x5

=

-5x1，x2

，x3

，x4

，x5

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

x2=10x1+

x2=11,

x1=100,

x2=

-90如果增加到，該方程解會(huì)如何變化？x1+

x2=10x1+

x2=11,

x1=1/0.011=90.91,

x2=

-Δa21/a21

=0.001/1.01=0.1%,第41頁/共65頁Δx1/x1

=(90.91-100)/100=-9%,42/66實(shí)際問題的數(shù)學(xué)模型，應(yīng)當(dāng)避免第一種情況，因?yàn)閷?shí)際中很難避免將算成。LP問題也會(huì)遇到類似情況。其中A、b和C都是從實(shí)際中收集、歸納和整理的數(shù)字，很難保證與實(shí)際情況絲毫不差。44/66如果LP問題的解因?yàn)檫@些數(shù)字與實(shí)際稍有偏差就會(huì)相差很大，那就說明利用A、b、C構(gòu)造的LP問題第43頁/共65頁模型不能用做實(shí)際問題的模型。合理的LP問題模型不應(yīng)敏感于靈敏度分析的步驟：1.先用最終單純形表中B-1變換A、b和C的增量Δb’

=B-1Δb，

ΔPj’

=B-1ΔPj

，45/66非可行解可行解

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

設(shè)備臺(tái)時(shí)/件產(chǎn)品問題1

若兩種產(chǎn)品單價(jià)分別變成5元/件和元/件，兩種產(chǎn)品最優(yōu)產(chǎn)量是否變化？問題2

使最優(yōu)產(chǎn)量不變的第二種46/66第45頁/共65頁47/66為了回答問題1，將兩種產(chǎn)品改變后的單價(jià)填入最終單純形表，并重新計(jì)算檢驗(yàn)數(shù)，得到：cj53.25000θicBxBB-1bx1x2x3x4x50x32001[1/3]-1/363.25x260101/20125x12100-1/31/3-z29.500025/600-1σj0x460031-13.25x2301-3/201/25x1410100z29.7500第46頁-0.125/共65頁0-3.25/2σj為了回答問題2，用5+Δc2表示第二種產(chǎn)品改變后的單價(jià)，并填入最終c4=-3/2-Δc2/2，若使最優(yōu)解不變，48/66單純c

形表，并重新計(jì)算檢驗(yàn)數(shù)，得j3

5+Δc2

0

0

0θic到：B-1xB

B b

x1x2

x3x4x50x320011/3-1/35+

Δc2x260101/203x12100-1/31/3z000-3/2-

Δc2/2-1σj第47頁/共65頁若回答使最優(yōu)產(chǎn)量不變的第一種產(chǎn)品單價(jià)變化范圍，則用3+Δc1表示第一c4=-3/2+Δc1/3，c5=-1-Δc1/3，若使最49/66種產(chǎn)品c

改變后的單價(jià)，并填入最終單j3+Δc15

0

0

0θi純cB形x表B

，B-1并b重x新計(jì)算檢驗(yàn)數(shù)：1

x2

x3

x4x50x320011/3-1/35x260101/203+

Δc1x12100-1/31/3z36+2

Δc10

0

0

-3/2+

Δc1/3-1-

Δc1/3σj第48頁/共65頁二、分析b的變化若Δb=(0,Δb2,0)T，問最優(yōu)解是否改變，為此，先計(jì)算Δb2/3Δb’

=B-1Δb

==

Δb2/2-Δb2/311/3-1/3001/20Δb20-1/31/30第49頁/共65頁50/66cj35000θicBxBB-1bx1x2x3x4x50x32+

Δb2/30011/3-1/35x26+

Δb2/20101/203x12-

Δb2/3100-1/31/3zσj51/66為使第二種設(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，同樣處理。第50頁/共65頁三、分析增添新變量xj的情況如果增加新產(chǎn)品x6

，單價(jià)為4元，問如何生產(chǎn)，總收入最多。設(shè)其所需三種設(shè)備臺(tái)時(shí)為25/3P6=0，變換，得P6

‘==

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

1/3

-1/3

201/2000-1/31/31第51頁/共65頁61.2

0

0

0.6

1/5

-0.2

15x260101/2003x11.610-0.2-0.40.40z39.600-1.8-2.1-0.40σj53/66cj350004cBxBB-1bx1x2x3x4x5x6θi0x320011/3-1/3[5/3]6/55x260101/200-3x12100-1/31/31/36z4

x360

0

0

-3/2

-13σj第52頁/共65頁四、分析技術(shù)系數(shù)aij變化時(shí)的情況如果aij對(duì)應(yīng)的xj是非基變量，處理辦法同“三”。如果xj是基變量，先變換Pj，Pj‘=B-1Pj[例1]第二種產(chǎn)品用設(shè)備臺(tái)時(shí)由0

改為220P2

=

23/2單價(jià)由5元增加為元/件，用x*2表示這2然后添入最終單純形表，并重新計(jì)算54/66種“新”產(chǎn)品產(chǎn)第量53頁/，共65頁先變換P

如下，21/6=

1P

‘0

=1/20

-1/31

1/3

-1/3

00

21/3

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

改為221/2P2

=

21/2單價(jià)由5元增為元，用x*2表示這種

“新”產(chǎn)品產(chǎn)量，先變換P2如下，然后添入最終單純形表，并重新計(jì)算檢驗(yàn)數(shù)：第56頁/共65頁57/6612=

11

1/3P

‘0

=1/20

-1/3-1/3

1/20

21/3

1/2cj355.500-1/20θicBxBB-1bx1x2x*2x3x4x50x3200[1]11/3-1/325x2601101/2063x1210-1/20-1/31/3-z360020-3/2-1σj第57頁/共65頁58/66需要將x2排除在外，辦法是將其視為人工變量。cj355.5000θicBxBB-1bx1x2x*2x3x4x55.5x*2200111/3-1/35x24010-11/61/33x131001/2-1/61/6z000-2-13/6-1/3σj59/66第58頁/共65頁33cj3-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/σj5.5x*260-10