《运筹学》 课件 第2章-线性规划的对偶理论

7/16/2024第2章线性规划的对偶理论1目录7/16/20242.1

线性规划的对偶问题2.2

对偶理论2.3

影子价格2.4

对偶单纯形法2.5

灵敏度分析CONTENTS22.1线性规划的对偶问题在第1章的例1.1中，我们讨论了如下的生产计划模型：假定现有一公司想把该工厂的生产资源收购过来，那么它至少应付出多大的代价，才能使该工厂愿意放弃生产活动，出让自己的资源？现在从另一个角度来讨论这个问题：7/16/20242.1.1对偶问题的提出例1.1

生产计划问题问产品A,B各生产多少,可获最大利润?

AB备用资源

钢材（吨）1230劳动力（工时）3260特种设备（台时）0224

利润（元/件）40504设用y1,y2,y3

分别表示钢材、劳动力和特种设备这三种资源的单位定价。因为用1个单位的钢材和3个单位的劳动力可以生产一件产品A，从而获得40元利润。那么生产每件产品A的资源出让所得应不低于生产一件产品A的利润，即y1

+3y2≥40同理，将可以生产每件产品B的资源出让的所得应不低于生产一件产品B的利润，即2y1

+2y2+2y3≥507/16/20242.1.1对偶问题的提出5要把所有的资源都收购需付出：W=30y1

+60y2+24y3当然收购公司希望用最小的代价把工厂的全部资源收买过来，故有：minW=30y1

+60y2+24y3s.t.y1

+3y2≥40

2y1

+2y2+2y3≥50y1

,y2,y3≥0对偶问题(DUAL)7/16/20242.1.1对偶问题的提出6问最经济的配食方案是什么？维生素的销售商换个角度

例1.2混合配料问题

饲料ABC

每单位成本

饲料14102饲料26125饲料31716饲料42538每天维生素12148的最低需求维生素/mg2.1.1对偶问题的提出7/16/20247“对称型”对偶问题minw=bTyATy

cy0A

矩阵y,b列向量c

列向量maxz=cTx

Ax

bx0A

矩阵x,b列向量c

列向量原问题7/16/20242.1.2线性规划原问题与对偶问题的表达形式87/16/2024原始问题maxz=cTxs.t.Ax≤b x≥0对偶问题minw=bTys.t.ATy≥

cy≥0≤maxbAcTmncATbT≥minmn2.1.2线性规划原问题与对偶问题的表达形式9minz’=-cTxs.t.-Ax≥-b x≥0maxw=-bTys.t.-ATy≤

-c y≥0minw=bTys.t.ATy≥c

y≥0maxz=cTxs.t.Ax≤b x≥0对偶的定义对偶的定义对偶问题的对偶就是原始问题！7/16/20242.1.2线性规划原问题与对偶问题的表达形式10“非对称型”2.1.2线性规划原问题与对偶问题的表达形式2.1.2线性规划原问题与对偶问题的表达形式012对偶关系对应表

（P） （D） 目标函数maxmin目标系数Cb约束右端bC系数矩阵AAT函数约束与变量约束第k个约束

第k个变量约束个数=变量个数（非）规范约束非负（正）变量等式约束自由变量7/16/20242.1.2线性规划原问题与对偶问题的表达形式13例2.1写出对偶规划：minz=4x1+2x2–3x3–x1+2x2

62x1+3x3

9x1+5x2–2x3=

4x1自由,x20,x30–y1+2y2+y3=

42y1+5y323y2–2y3

–3y10,y20,y3自由maxw=6y1+9y2+4y37/16/20242.1.2线性规划原问题与对偶问题的表达形式142.2对偶理论证明：7/16/20242.2.1弱对偶性16由弱对偶性，可得出以下的推论：原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之，对偶问题有可行解且目标函数值无界，则其原问题无可行解。（注意：逆命题不成立）若原问题有可行解而对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解而原问题无可行解，则对偶问题的目标函数值无界。7/16/20242.2.1弱对偶性17证明：再由弱对偶性：7/16/20242.2.2最优性18若原问题与其对偶问题均具有可行解，则两者均具有最优解，且它们的最优解的目标函数值相等。证明：由于两者均有可行解，根据弱对偶性推论，原问题的目标函数值具有上界，对偶问题的目标函数值具有下界。 因此，两者均具有最优解。由前面的讨论知，当原问题为最优解，即B为最优基时，YT=CBB-1是其对偶问题的可行解，且两者目标函数值相等。由最优性条件，得此Y即为最优解。7/16/20242.2.3强对偶性（对偶定理）19在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量为零。原问题：maxz=cTx

Ax

+

xs=bx,

xs0x=x1xn…xs=xs1xsm…①②7/16/20242.2.4互补松弛性（松紧定理）20证明：7/16/20242.2.4互补松弛性（松紧定理）217/16/20242.2.4互补松弛性的应用例2.2已知线性规划问题minz=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5

≥4

2x1-x2+3x3+x4+x5

≥3x1,x2,x3,x4,x5≥0其对偶问题的最优解为y1=4/5,y2=3/5，试应用对偶理论求原问题的解。222.2.4互补松弛性的应用将y1=4/5,y2=3/5的值代入，得知

为严格不等式，于是由互补松驰性，必有x2=x3=x4=0

解：写出对偶问题：Max

S=4y1+3y2y1+2y2≤2

y1-y2≤3

2y1+3y2≤5

y1+y2≤2

3y1+y2≤3

y1,y2≥0又因y1,y2>0，故原问题的两个约束条件必为紧约束，即有

x1+3x5=4

2x1+x5=3

解得

x1=x5=1即X*=(1,0,0,0,1)T,Z*=50237/16/20242.2.5对偶问题解与原问题解的关系则原问题单纯形表的检验数行对应其对偶问题的一个可行解设原问题：max

z=cTxs.t.Ax+xs=bx,xs≥0其对偶问题：min

w=bTys.t.ATy-

ys=cy,ys≥0ys1是对应原问题中基变量XB的剩余变量ys2是对应原问题中非基变量XN的剩余变量XBXNXs0CN

-CBB-1N-CBB-1-ys1-ys2-y松弛变量剩余变量检验数24项目非基变量XBXN基变量Xs0

Xs

bB

NIcj-zjCBCN

0项目基变量XB非基变量XNXsCB

XBB-1

bIB-1NB-1cj-zj0CN

-CBB-1N-CBB-1初始单纯形表：当迭代后基变量为XB时：当B

为最优基时：

0

0CB–CBB-1B=02.2.5对偶问题解与原问题解的关系025CB–CBB-1B=0CN

-CBB-1N

0C

-CBB-1A

0-CBB-1

0ATy

Cy

0令yT=CBB-1由此可见，y是对偶问题的一个可行解。将这个解代入对偶问题的目标函数，有w=bTy=yTb=CBB-1b=CBXB=z即当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值。7/16/20242.2.5对偶问题解与原问题解的关系26产品A，B产量x1，x2，Z为利润3x1+x2+x3=483x1+4x2+x4=120x1…x40MaxZ=5x1+6x23x1+x2

483x1+4x2120x1,x2

0机器台时劳动工时7/16/20242.2.5对偶问题解与原问题解的关系例：27X=(8,24)TZ=184

5600XBbx1x2x3x40x34831100x41203(4)01056000x318(9/4)01-1/46x2303/4101/41801/200-3/25x18

104/9-1/96x22401-1/31/318400-2/9-13/9B-1B0282.2.5对偶问题解与原问题解的关系3y1+3y25

y1+4y2

6y1,y20MinW=48y1+120y23y1+3y2-y3+y5=5

y1+4y2-y4+y6=

6MinW=48y1+120y2+My5+My6MaxZ=5x1+6x23x1+x2

483x1+4x2120x1,x2

0机器台时劳动工时对偶问题？0292.2.5对偶问题解与原问题解的关系

4812000M

MyBy1y2y3y4y5y6M

y5533-1010M

y661

40-10111M48-4M120-7M

M

M00My51/29/40-13/41-3/4120

y23/2

1/410-1/401/4180+1/2M18-9/4M0M30-3/4M0-30+7/4M48y12/91

0-4/91/34/9-1/3120y213/9011/9-1/3-1/91/3y=(2/9,13/9),Z=184

18400824M-8M-240302.2.5对偶问题解与原问题解的关系2.3影子价格z=CBB-1b+

(CN-CBB-1N)XN

(※)z=z(b)b为资源数对(※)求偏导：

z

b=CBB-1=YT对偶解Y——

b的单位改变量所引起的目标函数值的改变量。7/16/20242.3.1对偶解的经济意义32w=(y1…ym)b1bm…=b1y1+b2y2+…+bmymbi：第i种资源的数量；yi：对偶解；yi：反映bi的边际效益(边际成本)当bi增加bi,其它资源数量不变时,目标函数的增量Z=biyi7/16/20242.3.1对偶解的经济意义33由前面的经济解释可知，yi的大小与系统内资源对目标的贡献有关，是资源的一种估价，称为影子价格。(ShadowPrice)注：这种估价不是资源的市场价格。市场价格是已知数，相对较稳定；而影子价格则有赖于资源的利用情况，是未知数。当企业的生产任务、产品结构等等发生变化时，资源的影子价格也会随之改变，它是一种动态价格。7/16/20242.3.2影子价格34即某资源对偶解>0，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。①影子价格的大小客观地反映了资源在系统内的稀缺程度根据互补松弛定理的条件，如果某一资源在系统内供大于求，其影子价格就为零。即增加该资源的供应不会引起系统目标的任何变化。如果某一资源是稀缺资源（即相应约束条件的剩余变量为零），则影子价格必然大于零。影子价格越高，资源在系统中越稀缺。7/16/20242.3.2影子价格的应用35即直接用影子价格与市场价格相比较，进行决策，是否买入该资源。②影子价格实际上是一种机会成本在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该资源用于扩大再生产；而当某种资源的市场价格高于影子价格时，企业应卖掉已有资源。随着资源的买进卖出，其影子价格也将发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡。7/16/20242.3.2影子价格的应用362.4对偶单纯形法单纯形法的基本思路：找基

B，满足

B-1b0，但

C

-CBB-1A（即检验数）不全

0。迭代保持

B-1b0，使

C

-CBB-1A0，即

CBB-1AC对偶单纯形法的基本思路：迭代保持

C

-CBB-1A0，使

B-1b0找基

B，满足

C

-CBB-1A0，但

B-1b不全

0。对偶问题的可行基7/16/20242.4.1基本思路38(1)

作初始表，要求全部

cj-zj

0(2)

判定：B-1b全

0，停。否则，取其对应变量

xr为换出基的变量。(3)

确定换入变量①若第r行的

arj全

0，停，原问题无可行解。7/16/20242.4.2计算步骤39②若第r行的

arj有

arj<0,则求其对应变量

xs为换入基的变量(3)

确定换入变量(4)

以

ars为主元，换基迭代，得到新的单纯形表重复1-4的步骤，直到找到最优解7/16/20242.4.2计算步骤40关于①的解释：第

r个方程即<0

>0某

xj从

0↗，xr不能变

007/16/20242.4.2计算步骤步骤(3)的两个注释41关于②的解释：下一个表中的检验数为为保持可行，必须(a)对arj≥0,因cj–zj≤0(b)对arj<

0,由的选取知7/16/20242.4.2计算步骤42例2.4：MinZ=2x1+3x2+4x3

x1+2x2+x3

32x1-x2+3x34x1,x2,x30Max-Z=-2x1-3x2-4x3

-x1–2x2-x3+x4=-

3-2x1+x2–3x3+x5=-

4x1…x5

00432.4.3例子

-2-3-400XBbX1X2X3X4X50

X4-3-1-2-1100

X5-4-21-3010-2-3-4000

X4-10-5/21/21-1/2-2

X121-1/23/20-1/2-40-4-10-1-3X22/501-1/5-2/51/5-2X111/5107/5-1/5-2/5-28/500-9/5-8/5-1/5

2.4.3例子（1）初始解可以是非可行解，当检验数都是负数时，就可以进行基变换，这样避免了增加人工变量，使运算简便。（2）对变量较少时，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形求解，简化计算。（3）用于后面的灵敏度分析。7/16/20242.4.4对偶单纯形的优点与用途452.5灵敏度分析7/16/20242.5.1灵敏度分析简介灵敏度分析，是指对系统或事物因周围条件变化显示出来的敏感性程度的分析。资源向量的灵敏度分析Rangeoffeasibilityforright-hand-sidecoefficients(bi)价值向量的灵敏度分析Rangeofoptimalityforobjectivefunctioncoefficients(cj)技术系数的灵敏度分析Rangeofoptimalityformatrixcoefficients(aij)47当这些参数(

bi,cj,aij)中的一个或几个发生变化时，问题的最优解会有什么变化；或这些参数在一个多大的范围内变化时，问题的最优解不变。灵敏度分析不需要用单纯形法从头再算。只需把发生变化的个别系数，经过一定计算后直接填入最终单纯形表中，并进行检查和分析。如最优解改变，可用单纯形法或对偶单纯形法继续迭代计算，直到找到新的最优解。7/16/20242.5.1灵敏度分析简介482.5.1灵敏度分析简介项目基变量XB非基变量XNXsCB

XBB-1

bIB-1NB-1cj-zj-CBB-1b0CN

-CBB-1N-CBB-1cj,j∈N的变化cj,j∈B的变化bi的变化aij的变化B-1bB-1A-CBB-1bC

-CBB-1A2.5.1灵敏度分析简介例2.5：

经计算，得到最终单纯形表：050参数cj的变化仅仅影响到检验数

(cj–zj)

的变化，所以反映到最终单纯形表上，只可能出现两种情况：检验数仍然全部≤0，则最优解不变；出现检验数>0，需用单纯形法继续迭代求解。7/16/20242.5.2价值系数cj的灵敏度分析8-4/3-5/32/351

为使表中的解仍为最优解，应有C2在什么范围变化的时候，最优解不变？2.5.2价值系数cj的灵敏度分析

052右端项bi的变化在实际问题中为可用资源数量的变化。bi的变化反映到最终单纯形表上将引起

b

列数字的变化，可能有下面两种情况：问题的最优基不变，变化后的b列值为最优解；

（即生产产品的品种不变，但数量及最优值会变化