对偶问题与灵敏度分析

运筹学

——第3章对偶问题与灵敏度分析湖南大学工商管理学院本讲内容什么是对偶问题单纯形法的矩阵描述对偶问题的性质线性规划的灵敏度分析什么是对偶问题？例1（生产计划问题）：某工厂在计划期内要安排A、B两种产品的生产，已知生产单位产品的利润与所需的劳力、设备台时及原材料消耗，如下：产品A产品B资源限额劳动力设备原材料9434510360工时200台时300公斤单位产品利润70120问：如何安排生产使该厂获利最大？maxz=70x1+120x2s.t.9x1＋4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0对偶问题的提出考虑上一讲的生产计划问题，若设备和原料都用于对外加工，工厂收取加工费。试问：该厂设备工时、劳动力和原料该如何定价？显然，工厂给这些生产要素定价，既要保证自己的利益，又要使自己的价格具有竞争力价格越高越好价格越低越好一个合理的定价是：收取的加工费不能低于自己生产所得收益，在此前提下使总加工费尽量小。即：Minw=360y1+200y2+300y3s.t.9y1+4y2+3y3≥704y1+5y2+10y3≥120y1,y2≥0该线性规划问题与原问题互为对偶问题对偶的定义

(LP)Maxz=CX

(DP)Minw=Ybs.t.AX≤bs.t.YA≥CX≥0Y≥0若一个问题的某约束为等式，那么对应的对偶问题的相应变量无非负限制；反之，若一个问题的某变量无非负限制，那么对应的对偶问题的相应约束为等式。原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项建立对偶问题的规则约束条件变量右端项价值系数对于上表，特别把握以下要点：maxmin求max的对偶问题时，变量反号求min的对偶问题时，约束反号＝无限制例1：写出下列规划问题的对偶问题Maxz=2x1+2x2-4x3

s.t.X1+3x2+3x3≤304x1+2x2+4x3≤80X1,x2,x3≥0解：minw=30y1+80y2

s.t.y1+4y2≥23y1+2y2≥23y1+4y2≥-4y1,y2≥0例2：写出下列规划问题的对偶问题minz=2x1+8x2-4x3

s.t.X1+3x2-3x3≥30-x1+5x2+4x3=804x1+2x2-4x3≤50X1≤0,x2≥0,x3无限制解：maxw=30y1+80y2＋50y3

s.t.y1-y2+4y3≥23y1+5y2+2y3≤8

－3y1+4y2－4y3＝-4y1≥0,y2无限制,y3≤0单纯形法的矩阵描述单纯形法的矩阵描述设有线性规划问题Maxz=CXAX≤bX≥0加上松弛变量XS=(xn+1,xn+2,…,xn+m),化为标准型Maxz=CX＋0XsAX+IXS=bX≥0,XS≥0单纯形法的矩阵描述设A中存在一可行基B，相应的变量可分为基变量XB和非基变量XN，价值系数也分为CB,CN，即A=(B,N)X=(XB,XN)TC=(CB,CN)Maxz=CX＋0XsAX+IXS=bX≥0,XS≥0因而于是Maxz=CX＋0XsAX+IXS=bX≥0,XS≥0代入XB,目标值检验数令XN=0,XS=0,得基可行解目标值0zIb0C矩阵形式描述的单纯形表关于对偶问题的基本定理定理1（弱对偶定理）若X(0),Y(0)

分别为（LP）和（DP）的可行解，那么CX(0)≤Y(0)b。(证明)该定理说明：如果原问题是最大化问题，则它的任意可行解对应的目标函数值都会小于等于其对偶问题(极小化)的任一可行解对应的目标函数值证明：由X(0),Y(0)

分别为原问题和对偶问题的可行解则,AX(0)≤b,X(0)≥0Y(0)A≥C,Y(0)≥0因此，Y(0)AX(0)≤Y(0)b于是，CX(0)≤Y(0)bMaxz=2x1+2x2-4x3

s.t.X1+3x2+3x3≤304x1+2x2+4x3≤80X1,x2,x3≥0minw=30y1+80y2

s.t.y1+4y2≥23y1+2y2≥23y1+4y2≥-4y1,y2≥0例如任意取一些可行解试试看？定理2（无界性）若一个问题无界，则另一个问题不可行maxz=x1+x2

s.t.-2x1+x2

≤40x1-x2

≤20x1,x2≥0可行域Minw=40y1+20y2s.t.-2y1+y2

≥

1y1-y2≥1y1,y2

≥0对偶问题显然无可行解！例如定理3（最优性定理）若X(0),Y(0)

分别为（LP）和（DP）的可行解，且CX(0)=Y(0)b，那么X(0),Y(0)分别为（LP）和（DP）的最优解证明设X*是LP问题的任一可行解，由弱对偶性CX*≤Y(0)b=CX(0)从而X(0)是最优解同理Y(0)是最优解定理4（对偶定理）若其中一个问题有最优解，则另一个问题也有最优解，且两者最优值相等证明证明：设X*是LP问题的最优解，相应的最优基为B，则检验数必定满足令则有因而Y*是对偶问题的可行解又因而Y*是对偶问题的最优解0zIb0C定理5（互补松弛定理）原问题及其对偶问题的可行解X(0)和Y(0)是最优解的充要条件是：

Y(0)XS=0，YSX(0)=0XS,YS分别为原问题松弛向量和对偶问题剩余向量该定理说明：一对对偶问题达到最优，当且仅当松约束对应的对偶变量必定是紧的利用互补松驰定理，可以在知道一个问题的最优解时，求解其对偶问题的最优解例：Minz=2x1+3x2+5x3+2x4+3x5s.t.X1+x2+2x3+x4+3x5≥42x1-2x2+3x3+x4+x5≥3

xj≥0,j=1,…,5Maxw=4y1+3y2s.t.y1+2y2≤2y1-2y2≤32y1+3y2≤5y1+y2≤23y1+y2≤3y1,y2≥0对偶问题y1*=4/5,y2*=3/5对偶问题的最优解4/5-2*3/5=-2/5<3约束条件是松的也即ys>0,由互补松弛定理知X(0)ys=0所以x2=0同理，x3=0,x4=0又y1*>0,而Y(0)xs=0,知xs＝0，即原问题第一个约束取等式同理，第2个约束也取等式定理6若原问题最优解存在，则原问题最优单纯形表的检验数行中，松弛变量的检验数和剩余变量的检验数的相反数即为对偶问题最优解对偶最优解的经济含义——影子价格由对偶定理求z*对bi的偏导数所以对偶最优解为原问题各资源的影子价格影子价格非资源的市场价格，而是指系统达到最优状态时，资源的单位变化引起目标最优值的变化对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。什么是对偶单纯形法？也就是说，求解原问题（LP）时，可以从（LP）的一个基本解（并不一定是基可行解）开始，逐步迭代，使目标函数值（Z=Yb=CBB-1b=CX）减少，当迭代到XB=B-1b≥0时，即找到了（LP）的最优解，这就是对偶单纯形法。同原始单纯形求法一样，求解对偶问题（DP），也可以从（DP）的一个基本可行解开始，从一个基本可行解（迭代）到另一个基本可行解，使目标函数值减少。例一、用对偶单纯形法求解：解：将模型转化为cj-9-12-15000cBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1-5001(-9/-1.-12/-1.

-15/-5)-Z′

0-9-12-15000cj-9-12-15000cBxBbx1x2x3x4x5x60x4-36/5-9/5-9/5010-1/50x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5(-30/-9.-45/-14.-15/-1)-Z′

42-6-9000-3cj-9-12-15000cBxBbx1x2x3x4x5x60x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9.-45/-9.-33/-1)-15x315/71/140101/14-3/14-Z′

501/7-3/14000-45/14-33/14cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9-Z′

72000-1/3-3-7/3

所以，

X*=（2.2.2.0.0.0），

Z′*=－72，

原问题Z*=72

其对偶问题的最优解为：

Y*=(1/3.3.7/3)，W*=72练习：cj-2-3-400cBxBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301-Z

-2-3-400cj-2-3-400cBxBbx1x2x3x4x50x4-10-5/21/21-1/2-2x121-1/23/20-1/2-Z

0-4-10-1cj-2-3-400cBxBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5-Z

28/500-3/5-8/5-1/5Y=（8/5.1/5）X=（2/5.11/5.0）Z=28/5灵敏度分析为什么要进行灵敏度分析？前面对线性规划的讨论，价值系数c，资源系数b和技术系数矩阵A都是已知常数。但现实中，这些系数可能只是估计量，存在误差或随着时间的推移可能有些许变化糟糕！这个月产品市场价格与原计划时发生变化了。年初安排的生产计划还是最优的么？价值系数变化的灵敏度分析设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围内变化而最优解不变呢？例(生产计划问题)maxz=70x1+120x2s.t.9x1＋4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0模型价值系数变化的灵敏度分析设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围内变化而最优解不变呢？例(生产计划问题)最优单纯形表cj70120000CBXBbX1X2X3X4X5

070120X3X1X2842024001-3.121.161000.4-0.2010-0.120.164280000-13.6-5.2考虑C2发生变化价值系数变化的灵敏度分析设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围内变化而最优解不变呢？例(生产计划问题)最优单纯形表cj70c2

000CBXBbX1X2X3X4X5

070c2X3X1X2842024001-3.121.161000.4-0.2010-0.120.164280000-28+0.12c2

14-0.16c2

显然只要-28+0.12c2≤014-0.16c2≤0

成立，则最优解不变！

即

87.5≤c2≤233.33右端项变化的灵敏度分析考察单纯形表0zIb0Cb变化只影响因此，只要B-1b≥0,则最优基不变从而对偶最优解不变，也即影子价格不变例如生产计划问题,考虑b3变化的灵敏度分析最优单纯形表由此可见，(p3,p1,p2)是最优基，即B-1b≥0解得227.586≤b3≤400计算机灵敏度分析的例子生产计划问题Excel生产计划问题DM多个参数变化的灵敏度分析百分之百法则：(1)对