运筹学第一章-对偶理论南京大学课件

对偶理论例1.某工厂在计划期内要生产甲乙两种产品。这些产品分别需要在A,B,C,D四种不同的设备上加工。具体工况如下：设备产品ABCD利润（元/件）甲21402乙22043台时1281612如何获取最大利润？解:问题的数学模型为:Maxf=2x1+3x2s.t.2x1+2x212x1+2x284x1164x212xj

0,j=1,2假如设备的有效工时也可以用来承接对外加工，应如何对每种设备的工时定价？设A,B,C,D四种设备的工时价格分别定为y1,y2,y3,y4.生产一件甲产品所用A,B,C,D四种设备的工时分别为2,1,4,0,得到2元利润。工时的价格应保证相应工时用于对外加工时获利不低于2元。即有

2y1+y2+4y3

2.同样，对于乙产品应有2y1+2y2+4y43.相应的总利润为12y1+8y2+16y3+12y4为了能够得到对外加工订单，工时的价格只能尽量的低，这就导致利润要尽可能的小。Ming=12y1+8y2+16y3+12y4s.t.2y1+y2+4y3

22y1+2y2+4y43y1,y2,y3,y40这样我们就有如下的规划模型Maxf=2x1+3x2s.t.2x1+2x212x1+2x284x1164x212xj

0,j=1,2Ming=12y1+8y2+16y3+12y4s.t.2y1+y2+4y3

22y1+2y2+4y43y1,y2,y3,y40例2.市场上有6种食物都含有维生素A

和C，具体数据如下：一二三四五六最少需要量A1022129C01313219价格353060502722问题：消费者应如何选购食物，既花费最少又能满足人体每日9个单位维生素A、19个单位维生素

C的需要？解.设6种食物的选购量分别为x1,x2,x3,x4,x5,x6,

则

若有一家药厂计划生产两种药丸，分别含一个单位的维生素A

和C.假定市场上含维生素A

和C

的食品价格如例1所示。问这两种药丸应如何定价才能既与市场上的食品价格竞争又使合要求的饮食费用最大（赚钱最多）？(LP1)s.t.Minf=35x1+30x2+60x3+50x4+27x5+22x6x1+2x3+2x4+x5+2x69x2+3x3+x4+3x5+2x6

19xi

0,i=1,…,6.

(LP2)设维生素A丸和C丸的价格分别定为y1和y2,

则有Maxg=9y1＋19y2s.t.y135y2

302y1+3y2602y1+y250y1+3y2272y1+2y222y10,y20

(LP1)s.t.x1+2x3+2x4+x5+2x69x2+3x3+x4+3x5+2x619

xi

0,i=1,…,6.Minf=35x1+30x2+60x3+50x4+27x5+22x6

Maxg=9y1+19y2s.t.y1

35

y2302y1+3y2602y1+y250

y1+3y2272y1+2y222

y10,y20(LP2)极大极小(LP2)(LP1)目标系数右端向量目标系数右端向量系数矩阵转置n

个变量m

个变量m

个约束n

个约束定义：给定一个一般形式的(LP),称它为原始(LP),那么它的对偶定义如下：原始Minf=cxs.t.aix＝bi

i

Maix

bi

i

M’xj

0j

Nxj

0j

N’对偶Maxg=bTys.t.yi

0i

Myi

0

i

M’AjT

y

cj

j

NAjTy

cj

j

N’其中，ai

表示A

的第

i

个行向量,Aj

表示A

的第j

个列向量,

M

和M’分别表示对应于等式和不等式约束的行指标集合,N

和N’表示x

Rn

中对应于限制和非限制变量的列指标集合。注意：当目标函数求极小值时

(Min),

不等式约束均为,

当目标函数求极大值时

(Max),

不等式约束均为.xTycb如何写出一个(LP)问题的对偶？1.若原问题的第i

个约束为等式，则对偶问题的第i

个变量为自由变量；2.若原问题的第j

个变量为自由变量，则对偶问题的第j

个约束为等式。例3.写出下面(LP)问题的对偶。Maxf=x1+2x2−3x3+4x4s.t.−x1+x2−x3−3x4

56x1+7x2−3x3−5x4812x1−9x2+9x3+9x420xi0,i=1,2,3;x40.解.原问题等价于：Maxf=x1+2x2−3x3+4x4s.t.−x1+x2−x3−

3x4

5−6x1−

7x2+3x3+

5x4−812x1−9x2+9x3+9x420xi0,i=1,2,3;x40.由定义，原问题的对偶为：Ming=5y1−8y2+20y3s.t.−y1−6y2+12y31y1−

7y2−9y32−y1+

3y2+

9y3

−3−

3y1+

5y2+9y3

4y10,

yj

0,j=2,3.对偶问题的基本性质定理1.

对偶问题的对偶是原问题

原问题Minf=cxs.t.Aix=bi

i

Maix

bi

i

M’xj

0j

Nxj

0j

N’

对偶问题Maxg=bTys.t.yi

0

i

Myi

0

i

M’AjTy

cj

j

NAjTy

=cj

j

N’证.原始问题对偶的一般形式为：Min(bT)ys.t.(AjT)

y

cj

j

N(AjT)

y

cj

j

N’yi

0

i

M’yi

0

i

M把它看作原始(LP),按定义其对偶为：Max(c)xs.t.xj

0

j

Nxj0

j

N’aix

bi

i

M’aix

bi

i

M定理2.(弱对偶定理)设x0,y0分别是(LP)问题及其对偶问题的可行解，则cx0bTy0.证.由题设可知Ax0b,x00;ATy0cT,y00.由(2)式得ATy0

cT

0.由(1)式和(4)式得bTy0(x0)TATy0cx0.(1)(2)(3)式两边同乘以(x0)T得(x0)T(ATy0

cT)

0.(3)(4)定理3.(无界性定理)若原问题与其对偶问题中有一个有无界解，则另一个必无可行解。证.由定理1我们不妨假设原(LP)问题有无界解。若其对偶有可行解，令y0为其任一可行解，于是有

ATy0cT.设x

是原(LP)问题任一可行解，则

xTATy0cx.由于

xTATy0(Ax)Ty0bTy0故有

cxbTy0,这表明原问题目标函数值有下界，矛盾。定理4.(最优性定理)设x0,y0分别是(LP)问题及其对偶问题的可行解且cx0bTy0.则x0,y0分别是原问题与其对偶问题的最优解。定理5.(强对偶定理)若原问题存在最优解，则其对偶问题也有最优解，且两者的最优目标函数值相同。证.设原(LP)问题的标准型为：Mincx+0x’s.t.

AxImx’=b

x0,x’0.设x*是用单纯形法求出的原(LP)问题的最优bfs,其对应的基为B,所有非基列记为N.于是有N

cN

cBB1N0.由于基变量的检验数为0，我们有(c,

0)

cBB1(A,Im)0.

(1)令y*(cBB1)T,则由(1)式可得ATy*cT,

y*0.这说明y*是对偶问题的可行解。由于

cx*

cBxB*

cBB1bbTy*,根据定理

4,y*是对偶问题的最优解。注意上下衔接的过程，我们把整个C=(c,0)拿出来了，用得是前面得到的B,这个B不是初始基，而是最终的可行基！互为对偶的两个(LP)的解之间的关系：1.两个均有最优解；2.两个都没有可行解；3.

一个有无界可行解，另一个没有可行解。对偶原始最优值有界最优值无界无可行解最优值有界1最优值无界3无可行解32定理6.

(互补松弛性定理)设x,y

分别是(LP)问题及其对偶问题的可行解，则它们是最优解的充要条件是,对一切i和j有：

(1)uiyi(aixbi)0;

(2)vj(cj

yTAj)xj0.证.由对偶关系知，对一切i

和j

有ui

0,vj

0.令易见，u0当且仅当(1)成立；v0当且仅当(2)成立。对一切i和j,将(1)式和(2)式相加，则可消去既含x又含y

的项，从而有

u+v=cxyTb.因此，(1)和(2)成立当且仅当u+v=0,或者

cx=yTb.由定理2,cx=yTb

是x

和y分别是最优解的充要条件。定理6结论表明：若原问题最优解的某分量xi>0,则其对偶问题中第i个约束在最优解处必呈等式；若对偶问题第i个约束在最优解处呈严格不等式，则原问题最优解中第i个分量必为0.互补松弛性定理的应用:设x,y

分别是(LP)问题及其对偶问题的可行解，则它们是最优解的充要条件是:对一切i和j有：(1)yi(aixbi)0;

(2)(cj

yTAj)xj0.例4.已知线性规划问题其对偶最优解为y*=(4/5,3/5)T,试求原问题的最优解。Minf=2x1+3x2+5x3+2x4+3x5s.t.x1+x2+2x3+x4+3x542x1−x2+3x3+x4+x5

3xj0,j=1,…,5解.

其对偶为:

Maxg=4y1＋3y2s.t.y1+2y22y1

y2

32y1+3y2

5y1+y2

23y1+y2

3yj0,j=1,2设x*=(x1,x2,x3,x4,x5)T

是原问题的最优解。[在对偶问题中，一共7个约束(含2个非负约束)。找出对偶最优解y*=(4/5,3/5)T的等式约束，即约束1和约束5,其余约束皆为严格不等式约束。]由互补松弛性可知：

x2x3

x40且由此可得x*=(1,0,0,0,1)T.x1+3x5=42x1+

x5=3影子价格当(LP)原问题求得最优解x*时，其对偶问题也求得最优解y*,且有

f*cx*bTy*g*.在实际的经济活动中，bi

代表资源的拥有量；对偶变量yi*代表在资源最优利用的条件下对单位第i

种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价。为区别市场价格，称其为影子价格。如果资源i

增加一个单位，而其它资源都保持不变，那么由此引起的目标函数最优值的增量称为该资源的影子价格。(1)如何计划可使周收益最大？(2)若每周多工作一小时，最多可增加多少收入？例1.某生产果汁杯和酒杯的个体经营者，每周工作60小时，拥有150立方米的储藏室。这两种产品的生产工况如下：杯型工效(小时/百箱)储藏量(立方米/百箱)最大需求(百箱)收益(元/箱)果汁杯61085酒杯5204.5解.(1)设每周生产果汁杯x1百箱,酒杯x2百箱。则

基x1x2x3x4x5bx36510060x41020010150x51000185004500000该问题化为标准型后的单纯形初表为Maxf=500x1＋450x2s.t.6x1＋5x26010x1＋20x2150x18xi0,i=1,2基x1x2x3x4x5bx2011/73/35030/7x5002/71/14111/7x1102/71/14045/700550/720/7036000/7上述问题的单纯形终表为故每周应生产果汁杯45/7百箱,酒杯30/7百箱。(2)这时，b’=(61,150,8)T.于是

B1b’=(29/7,9/7,47/7)T.又cB=(450,0,500),可算得

cB

B1b’=36550/7.对原问题而言，其目标值为36550/7,实际增加=550/7,即每周多工作1小时可增加收入550/7元。影子价格的计算

Max

z=cx

s.t.

Ax

b

x0考虑问题化为标准型

Min

f=cx

s.t.

Ax+Imx’

=b

x

0

x’

0(D)若最优基为B,且A=(B

N),则其单纯形表为:基变量xBxNx’x’BNImbccBcN00基变量xBxNx’解xBImB1NB1B1b0cN+cBB1NcBB1cBB1b上表说明资源i

的影子价格在数值上就等于其对偶问题最优解的第

i

个分量。这也就是说，对于形如(D)的线性规划问题，其资源的影子价格可从原问题的单纯形终表中读出。现在C’=--C,例2.求下列线性规划问题中诸资源的影子价格。

Maxf=80x1+100x2

s.t.8x1+4x22205x1+5x21703x1+4x2120

xi0,i=1,2解.该问题的初始单纯形表为基x1x2x3x4x5解x384100220x455010170x53400112080100000单纯形终表为：基x1x2x3x4x5解x30014420x11004/5116x20103/5118000420对应于松弛变量的检验数可直接读出资源的影子价格为

(0,4,20)T.另一方面，由影子价格公式w=(B1)TcBT

也可算得14404/5103/51例3.若在例1中增加一个问题：今有客户欲订购一种香槟杯，其工况如下表。这位个体经营者是否应该接下此活？杯型

工效(小时/百箱)

储藏量(立方米/百箱)最大需求(百箱)

收益(元/箱)果汁杯61085酒杯5204.5香槟杯8106解.设每周生产果汁杯x1百箱,酒杯x2百箱，香槟杯x3百箱。则

Maxf=500x1+450x2+600x3

s.t.6x1+5x2+8x36010x1+20x2+10x3

150

x18

xi0,i=1,2,3从例1的单纯形终表中可知三种资源的影子价格为

w=(550/7,20/7,0)T.若生产香槟杯,则所需的隐含费用为8×550/7+10×20/7+0=4600/7元。由于4600/7＞600,即隐含费用＞收益，故此活不能接。考虑(LP)问题若最优基为B,且A=(B

N),则其单纯形终表为基变量xBxN解BNbxBImB1NB1b0

cNcBB1NcBB1b灵敏度分析其中，cN

cBB1N

0;

B1b

0.Minf=cx

s.t.Ax=bx0由上表可知

1.bi

的变化分析设bi有改变量bi

,要保证B

的最优基不变，只须使得变化后的基变量依然可行，即B1(b+b)0,由此可以确定bi

的变化范围，其中B1可由问题的单纯形终表读出，b=(0,..,0,bi,0,..,0)T.改变影响不影响bi(1)可行性(2)目标值最优性(可行情况下)cB(1)最优性(2)目标值可行性cN最优性(1)可行性aij

(jN)最优性(1)可行性(2)目标值(2)目标值例1.已知一个(LP)问题的单纯形初表终表如下，试求

b1

的变化范围。基x1x2x3x4x5bx36510060x41020010150x51000185004500000基x1x2x3x4x5bx2011/73/35030/7x5002/71/14111/7x1102/71/14045/700550/720/7036000/71/73/3502/71/1412/71/140解.由终表可得则由B1(b+b)

0可得–45/2

b1

11/2,即75/2

b1131/2.令2.cj

的变化分析情形1.

cj

,Pj

N设A=(P1,P2,…,Pn

)设cj’

cj+cj,Pj

N,则

cj

–

j

欲保持B

的最优性，只需j’

0,即

j+cj

0即可。故cj

,Pj

N的变化准则是：例2.已知某(LP)问题的单纯形初、终表如下。若目标系数

c4有改变量c4,求使原问题最优解保持不变的c4变化范围。基x1x2x3x4x5bx31310090x42101080x51100145540000基x1x2x3x4x5bx30012525x11001135x20101210

00013215解.由cj

–j

可得，c4

1.

情形2.ci,Pi

B设ci’

ci+ci,Pi

B,则对于一切Pj

N,有欲保持B

的最优性，只需对于一切Pj

N,有j’

0,即

j

–cBB1Pj0即可。故ci

,Pi

B

的变化准则是：

Pj

N,cBB1Pj

j

其中cB’

=cB

+cB.例3.已知某(LP)问题的单纯形初、终表如下。若基变量x2的目标系数c2有改变量c2,求使原问题最优解保持不变的c2变化范围。基x1x2x3x4x5bx31310090x42101080x51100145540000基x1x2x3x4x5bx30012525x11001135x20101210

00013215125011012解.cB=(0,5,4),

N={P4,P5},4=1,5=3.

1

c23/2,

5

c2

5/2.

B1P4=(2,1,1)T,

B1P5=(5,1,2)T,

cB

=(0,0,c2).由cBB1Pj

j

可得即

Pj

N,cBB1Pj

j

3.aij

的变化分析分三种情形：情形1.aij

,

Pj

N设Pj’

Pj+Pj,Pj

N,则欲保持B

的最优性，只需j’

0,即

j

–cBB1Pj

0即可。故aij

,Pj

N

的变化准则是：

cBB1Pj

j

情形2.aij

,

Pj

B此时情况比较复杂。一般来说要用单纯形法重新求解。若变化仅限于B

的某一列，那么新问题的求解可在原单纯形终表基础上变换一些数据进行。情形3.增加新变量增加新变量相当于原约束矩阵增加一列。类似于情形2,一般来说要用单纯形法重新求解。新问题的求解可在原单纯形终表基础上，增加一列数据进行。

新产品开发问题在约束矩阵中增加一列计算诸资源的影子价格；2.计算开发新品所需的隐含费用，决定是否开发；若开发，令新产品的技术参数向量为P*,计算B1P*

和相应的检验数*=c*–cBB1P*,并将其加到原问题的单纯形表中；4.运用单纯形法直至求得最优解。例4.某厂生产两种产品，其工况如下：原料产品A1产品A2资源(公斤)D1390E2180F1145利润(千元/件)54

(1)应如何安排生产可获利最多？(2)若新品A3每件耗D、E、F分别为2、4、1公斤，且每件新品可获利8000元，该厂是否应当开发？应生产多少为好？基x1x2x3x4x5bx30012525x11001135x2010121000013215生产方案是：A1:35件，A2:10件；获利21.5万元。解.(1)本题的单纯形终表是

(2)从单纯形终表中可知三种资源的影子价格为：

w=(0,1,3)T.

若生产新品,则所需的隐含费用为：

2×0+4×1+1×3=7000.

由于8000＞7000,即收益＞隐含费用，故应当开发。125011012B1P*=(5,3,2)T,由终表得由于P*=(2,4,1)T,cB=(0,–5,–4)T,故*=c*–cBB1P*=–1.将B1P*

和*

加入原单纯形终表中得基x1x2x3x4x5x*

bx300125525x110011335x201012210000131215基x1x2x3x4x5x*bx*001/52/5115x1103/51/52020x2012/51/50020

001/57/520220生产方案：A1:20件，A2:20件，A3:5件；获利22万元。基x1x2x3x4x5x*

bx300125525x110011335x201012210000131215例5.某厂生产两种产品，其工况如下：产品I产品II资源设备128台时材料A4016公斤材料B0412公斤利润(千元/单位)23应如何安排生产可获利最多？若该厂又增调4台时用于这两种产品的生产，求最优方案。确定产品II

价格系数的变化范围。新品III的技术参数为：设备2台时；材料A6公斤；材料B

3公斤；利润为5千元/单位。是否值得开发？应生产多少？(5)工艺改进后，产品I

技术参数为：设备2台时；材料A5公斤；材料B2公斤；利润为4千元/单位。试分析它对原最优计划有何影响？基x1X2x3x4x5bx3121008x44001016x50400112230000解.(1)设生产产品I

x1

单位，产品II

x2单位。则Maxf=2x1+3x2

s.t.

x1+2x284x1164x212

xi

0,i=1,2.Minz=2x1

3x2

s.t.

x1+

2x2+

x3=84x1+

x4=16

4x2+

x5=12

xi0,i=1,…,5.其单纯形初表为：其单纯形终表为：基x1x2x3x4x5bx11001/404x50021/214x2011/21/802

003/21/8014最优解为：

x*=(4,2)T;f*=14.即生产产品I4单位，产品II2单位；获利1.4万元。(2)由单纯形终表得：

cB=(2,0,3)T;cN

=(0,0)T;

B=(P1,P5,P2);b=(4,0,0)T.

B1(b+b)=(4,4,4)T.这样，我们有在终表中以B1(b+b)

替代B1b,以cBB1(b+b)

替代cBB1b

有：基x1x2X3X4x5bx1100¼04x5002½14x201½1/804

003/21/8020如何在上表的基础上求新问题的最优解？对偶单纯形法此时，(b1,…,bm,0,…,0)T

是基解而非基可行解。但是b0!基x1x2xmxm+1xm+2xn

bx1100b1x2010b2xm001bm000m+1m+2n

1.确定出基变量:若bk=minbi|bi＜0,则选取

xk

为出基变量；2.确定入基变量:若所有λkj

0,则该问题无解。若

=maxjλkj

λkj＜0=lλkl,则选取

xl

为入基变量。3.进行换基迭代：若得最优解，中止；否则，重复上述过程。

基x1x2x3x4x5bx11001/404x50021/214x2011/21/804

003/21/8020基x1x2x3x4x5bx11001/404x50021/214x2011/21/804

003/21/8020基x1x2x3x4x5bx11001/404x30011/41/22x201001/43

0001/23/417经过一次换基迭代有：最优解为x*=(4,3)T,f*=17,即生产4单位产品I,3单位产品II,获利1.7万元。

1

c23,4

c20.

B1P4=(1/4,1/2,1/8)T

B1P3=(0,2,1/2)T

N={P3,P4},

3=3/2,4=1/8,

令

cB

=(0,0,c2)T,由cBB1Pj

j,jN,得即(3)

由(1)中单纯形终表得(4)由(1)中单纯形终表得影子价格为wP*=3/2×2+1/8×6+0×3=15/4(千元)，由于15/4＜5,即隐含费用＜收益，故可以开发。将B1P*和*

代入(1)中单纯形终表得：cB

=(2,0,3)TB1P*=(3/2,2,1/4)T*=c*

cBB1P*=5/4w=(3/2,1/8,0).令P*=(2,6,3)T,则新品III

的隐含费用为：基x1x2x3x4x5x*bx11001/403/24x50021/2124x2011/21/801/42

003/21/805/414

x*=(1,3/2,2)T;f*=33/2分别生产产品I,II

和III1,3/2,2单位；获利1.65万。基x1x2x3x4x5x*bx1103/21/83/401x*0011/41/212x2013/43/161/803/2

001/47/165/8033/2(5)计算B1P1’

和1

基x1x2x3x4x5bx15/4001/404x51/20–21/214x23/811/2–1/802–3/803/21/8014用B1P1’

和1

替换(1)中单纯形终表中x1所在列得B1P1’

=(5/4,1/2,3/8)T1=c1’–cBB1P1=–3/8

换基迭代有：基x1x2x3x4x5bx11001/5016/5x500–22/5112/5x2011/2–1/504/5003/21/5076/5x*=(16/5,4/5)T即，工艺改进后，应生产3.2单位的产品I,0.8单位的产品II;可获利1.52万元。最优解为f*=76/5新资源限制考虑问题

Max

f=cx

s.t.

Ax

b

x0在原模型中增加一个资源限制

Max

f=cx

s.t.

Ax

b

x

x0问题:如何求出变化后的最优解？设A=(B

N),其中B

是最优基，且=(B,N).将增加约束后的模型化为标准型得：

Min

z=cx

s.t.

Ax+Imx’=b

x+xs=

x,x’,xs

0xBxNx’

xsxBBNIm

0bxsBN01

cB

cN

000列出其单纯形表：此时，矩阵构成了新问题的一个基，并且xBxNx’

xsxBBNIm

0bxsαBN01

cB

cN

000BB01于是xBxNx’xsxBI

B1NB1

0B1bxs0NBB1N

BB1

1

BB1b

0

cBB1N

cNcBB1

0cBB1b

由于B

是最优基，故

0,B1b

0.

准则1.

若BB1b

0,则B’

是新最优基。2.若BB1b

＜0,且NBB1N

0,BB1

0,则新问题无解；否则，可由对偶单纯形法求解。xs0NBB1N

BB1

1

αBB1b

例6.

某厂用三种原料生产两种产品，其工况如下：原料产品A产品B资源甲84220乙55170丙34120单价(元)80100应如何安排生产可获利最多？若甲原料不允许有剩余，求最优方案。增加限制4x1+6x2

164，求最优方案。解(1)设产品A

生产x1

单位，产品B

生产x2单位。则

Max

f=80x1＋100x2

s.t.8x1＋4x22205x1＋5x21703x1＋4x2120

xi0,i=1,2.

Minz=80x1100x2

s.t.8x1﹢4x2﹢x3=2205x1+5x2﹢x4=170

3x1+4x2x5=120

xi0,i=1,…,5.化为标准型得：基x1x2x3x4x5x384100220x455010170x534001120801000000基x1x2x3x4x5x30014420x11004/5116x20103/51180004203080

x*=(16,18)T;f*=3080.生产A:16,B:18,获利3080元。14404/5103/51若甲原料不允许有剩余，可将甲资源约束改为等式，用二阶段法重新计算。基x1x2x3x4x5x384100220x455010170x534001120*001000801000000基x1x2x3x4x5x384100220x455010170x534001120*84000220801000000基x1x2x3x4x5x384100220x455010170x534001120*84000220801000000基x1x2x3x4x5x111/21/80055/2x405/25/81065/2x505/23/8

0175/2*00100006010002200基x1x2x4x5x111/20055/2x405/21065/2x505/20175/2060002200基x1x2x4x5x1101/5021x2012/5013x500115002402980第二阶段基x1x2x3x4x5x5001/4115x1101/4