清华大学运筹学对偶理论

1清华大学运筹学对偶理论原来的问题：两种产品各生产多少，利润总额最大？生产是为赢利（取得收入）。还有别的办法赢利（取得收入）。例如，卖出或出租设备。问，三种设备卖价或租价各应是多少，进项才不低于自己生产时的销售收入？2/66第1页/共65页用y1、y2和y3分别表示A、B和C三种设备单位台时卖价或租价，则，总进项w可表示成w=4y1

+12y2+18y3生产两种产品消耗的设备台时的价值（或称出售或出租两种产品所用设备台时的进项）分别是1y1

+0y2+3y3

和0y1

+2y2+2y3两种产品售价分别是3和5。出售或出租产品所用设备台时的进项不能低于售价。所以，应有1y1

+0y2+3y3

≥33/66和0y1

+2y2+2y3

≥5从另一个角度看，w=4y1

+12y2+18y3是总消耗。第2页/共65页回答y1、y2和y3各是多少的问题，可表示如下：Min

w=4y1

+12y2+18y3s.t.

y1

+3y3

≥32y2

+2y3

≥5y1,

y2,

y3≥0该问题叫做原问题(P)的对偶问题(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若要问对偶问题的解是什么，可以看解

(P)时得到的最终单纯形表。最终单纯形表第4页/共65页从该表松弛变量的检验数行得到：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)这是对偶问题有趣的一个方面。第5页/共65页二、对称的对偶问题一般形式上面的例子叫做对称的对偶问题。三、非对称的对偶问题请见教科书第三版第52页或第四版第53页的表。7/66第6页/共65页事项原问题（对偶问题）对偶问题（原问题）AbC目标函数n个决策变量xj≥0xj≤0xj无约束第7页/共65页m个决策变量yi≥0yi≤0yi无约束8/66第二节对偶理论基本性质一、对称形式单纯形法矩阵表达Max

z=CXs.t.

AX≤bX≥0化成标准形式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的检验数，令σj

=cj

-CBB-1Pj，若所有的σj

<0，即C第9页-/共C65页B-1N≤0N

B(2)松弛变量Xs

=(xs1,xs2,…,xsm)T的检验数是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对偶问题初始单纯形表My6310[3]-101012y25/20110-1/201/2w3M+304-M06-3MM60M-616/66σ3应当是18-5M，但错算为18-2M，所以误选y2

为换入变量。以下将错就错算下去。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对偶问题最终单纯形表第16页/共65页重新算一遍，对偶问题初始单纯形表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页对偶问题最终单纯形表bj4121800MMθibByBB-1Cy1y2y3y4y5y6y718y311/301-1/301/3012y23/2-1/3101/3-1/2-1/31/2w3620026M-2M-6σj19/66计算结果同上。第18页/共65页事项原问题变量原问题松弛变量xBB-1bx1x2x3x4x5x320011/3-1/3x260101/20x12100-1/31/3z36000-3/2-1变量对偶问题剩余变量对偶问题变量y4y5y1y2y320/66(P)最终单纯形表第19页/共65页事项对偶问题变量对偶问题剩余变量bByBB-1Cy1y2y3y4y518y311/301-1/3012y23/2-1/3101/3-1/2w36原问题松弛变量原问题变量x3x4x5x1x221/66(D)对偶问题最终单纯形表第20页/共65页■22/66第21页/共65页推论1(P)任一可行解目标函数值

是(D)目标函数值下界。反之，(D)任一可行解目标函数值是(P)目标函数值上界。推论2若(P)有可行解且目标函数

值无界，则(D)无可行解；反之，

(D)有可行解且目标函数无界，则

(P)无可行解。当(D)无可行解时，第22页/共65页(P)无可行解或目标函数值无界。23/66■24/66第23页/共65页3.对偶定理。若(P)和(D)均有可行解，则均有最优解，且两者的目标函数值相等。证明:由于(P)和(D)均有可行解，根据弱对偶性推论1，(P)目标函数值有上界，(D)目标函数值有下界，因此，

(P)和(D)都有最优解。另外，根据ATY≥CT，Y≥0，w=YTb=CBB-1b=z知25/107第24页/共65页道，当(P)取得最优解时，(D)有可行解，且有w=z，根据性质2（最优■26/107第25页/共65页■27/107第26页/共65页第三节影子价格一、影子价格在例子Max

z=3x1+5x2s.t.

x1≤4(P)2x2

≤123x1+2x2

≤18x1，x2

≥0bT=(4,12,18)是资源，即可利用的设备台班量。在讨论如何才能赢利最多时，没有考虑三种设备单位台28/66第27页/共65页有些经济学家认为，自由的市场交易，商品成交价格能够反映其真正价值。但是，资源的现实市场价格并不反映其“真正”价值。还有些经济学家认为，影子价格是原本无交易的资源，在转为其他用途时的价格，或者说，另外再增加一个单位此种资源需要付出的价格。这个问题可以利用对偶问题的解给予某种解释。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页这就是说，三种设备每台时的价格分别是0,3/2和1。第一种设备每台时的价格为0，这是什么意思？请看原问题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页第四节对偶单纯形法一、对偶单纯形法思路Min

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

ATY-IYs=CTY，Ys≥036/36第35页/共65页二、对偶单纯形法计算步骤Step1：找出初始可行基、初始单纯形表和初始基解。Step2：若B-1b≥0，初始基解是最优解，停。否则，下一步。Step3：取(B-1b)l=min{(B-1b)i|(B-1b)i<0}，第l行基变量换出。若所有的alj≥0，无可行解，停。Step4：计算σ第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判断是否最优cj-4-12-1800cBxBB-1bx1x2x3x4x5-18x311/301-1/30-12x23/2-1/3101/3-1/2z-2第400页0/共65页0-2-6第五节灵敏度分析问题的由来，先看一个方程x1+

x2=10x1+

x2=11,

x1=100,

x2=

-90如果增加到，该方程解会如何变化？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实际问题的数学模型，应当避免第一种情况，因为实际中很难避免将算成。LP问题也会遇到类似情况。其中A、b和C都是从实际中收集、归纳和整理的数字，很难保证与实际情况丝毫不差。44/66如果LP问题的解因为这些数字与实际稍有偏差就会相差很大，那就说明利用A、b、C构造的LP问题第43页/共65页模型不能用做实际问题的模型。合理的LP问题模型不应敏感于灵敏度分析的步骤：1.先用最终单纯形表中B-1变换A、b和C的增量Δb’

=B-1Δb，

ΔPj’

=B-1ΔPj

，45/66非可行解可行解

非可行解非可行行动解。可行解非可行解2.检查(P)是否仍为可行解。(3P.)检查((DD))是否仍结论为或可继行续计解算。的步骤可行4.解根据可行下解表中问各题的种最情优解况或决最优定解下不变一步用单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解引进人工变量，编制新单纯形表重新计算第44页/共65页可用台时产品1产品2（千小时）下料设备A104机加工设备B0212焊接设备C产品单价33元/件25元/件18一、分析C的变化[例]

设备台时/件产品问题1

若两种产品单价分别变成5元/件和元/件，两种产品最优产量是否变化？问题2

使最优产量不变的第二种46/66第45页/共65页47/66为了回答问题1，将两种产品改变后的单价填入最终单纯形表，并重新计算检验数，得到：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表示第二种产品改变后的单价，并填入最终c4=-3/2-Δc2/2，若使最优解不变，48/66单纯c

形表，并重新计算检验数，得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页若回答使最优产量不变的第一种产品单价变化范围，则用3+Δc1表示第一c4=-3/2+Δc1/3，c5=-1-Δc1/3，若使最49/66种产品c

改变后的单价，并填入最终单j3+Δc15

0

0

0θi纯cB形x表B

，B-1并b重x新计算检验数：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，问最优解是否改变，为此，先计算Δ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为使第二种设备可用台时改变后的解仍然可行，须有：2+Δb2/3≥0，

6+Δb2/2≥0，

2-Δb2/3≥0，max{-6,

-12}≤Δb2≤min{6},

-6≤Δb2≤6，对于Δb1和Δb3，同样处理。第50页/共65页三、分析增添新变量xj的情况如果增加新产品x6

，单价为4元，问如何生产，总收入最多。设其所需三种设备台时为25/3P6=0，变换，得P6

‘==

011/3将P6’填入最终单纯形表，并重新计算检验数：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页四、分析技术系数aij变化时的情况如果aij对应的xj是非基变量，处理办法同“三”。如果xj是基变量，先变换Pj，Pj‘=B-1Pj[例1]第二种产品用设备台时由0

改为220P2

=

23/2单价由5元增加为元/件，用x*2表示这2然后添入最终单纯形表，并重新计算54/66种“新”产品产第量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检验数均已非正，说明已经得到最优解，销售收入增加了(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页如果第二种产品用设备台时由0

改为221/2P2

=

21/2单价由5元增为元，用x*2表示这种

“新”产品产量，先变换P2如下，然后添入最终单纯形表，并重新计算检验数：第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