运筹学第2章(讲课比赛)

Chapter2对偶理论

(DualityTheory)单纯形法的矩阵描述对偶问题的提出线性规划的对偶理论对偶问题的经济解释－影子价格对偶单纯形法灵敏度分析(选讲)掌握WinQSB软件求解对偶规划本章主要内容： 学习要点：

1.理解对偶理论，掌握描述一个线性规划问题的对偶问题。

2.能够运用对偶单纯形法来求解线性规划问题。

3.会用互补松弛条件来考虑一对对偶问题的界。

4.了解影子价格、灵敏度分析以及用WinQSB求解对偶规划问题。2.1

单纯形法的矩阵描述0.16-0.120102412x2-0.20.4001207x11.16-3.12100840x3-1.20003.41000.10010,33012x220-0.51002.5500x430.8-0.40107.82400x3000127301001033000x540010542000x490001493600x3ɵx5x4x3x2x1B-1bCBXB每一列的含义？每个表中的B和B-1的查找？单纯形法的矩阵描述单纯形法的矩阵描述单纯形法的矩阵描述CBCNbXBXNbBNCBCNbXBXNB-1bIB-1N-CBB-1b0CN-CBB-1N单纯形法的矩阵描述CBCNCS(0)bXBXNXSbBNI0CBCN0CBCNCS(0)bXBXNXSB-1bIB-1NB-1-CBB-1b0CN-CBB-1N-CBB-1

单纯形法的矩阵描述2.3对偶问题的提出

对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？对偶问题的提出俩家具制造商间的对话：唉!我想租您的木工和油漆工一用。咋样？价格嘛……好说，肯定不会让您兄弟吃亏。王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。Hi：王老板，听说近来家具生意好呀，也帮帮兄弟我哦!家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。价格嘛……好商量，好商量。只是…...

王老板李老板引例1对偶问题的提出王老板的家具生产模型：x1、

x2是桌、椅生产量。Z是家具销售总收入（总利润）。maxZ=50x1+30x2s.t.4x1+3x2

≤120（木工）

2x1+x2

≤50（油漆工）

x1，x2

≥0原始线性规划问题，记为（P）王老板的资源出租模型：y1、y2单位木、漆工出租价格。W是资源出租租金总收入。minW=120y1+50y2s.t.4y1+2y2

≥503y1+y2

≥30y1，y2

≥0对偶线性规划问题，记为（D）所得不得低于生产的获利（不吃亏原则）要使对方能够接受（竞争性原则）两个原则对偶问题的提出王老板按（D）的解y1、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。按时下最流行的一个词，叫什么来着————对偶问题的提出Max

Z=

40x1+50x2

x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目标函数约束条件设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品A的资源消耗所得不少于单位产品A的获利生产单位产品B的资源消耗所得不少于单位产品B的获利y1+3y240

2y1+2y2+2y350甲乙资源量A1230B3260C0224单位获利4050引例2通过使用所有资源对外加工所获得的收益W=30y1+60y2+24y3对偶问题的提出根据原则2，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：Min

W=30y1+60y2+24y3

y1+3y2402y1+2y2+2y350y1,y2,y3

0s.t目标函数约束条件原线性规划问题称为原问题，此问题为对偶问题，y1,y2,y3为对偶变量，也称为影子价格对偶问题的提出2.4线性规划的对偶理论Max

Z=

40x1+50x2

x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t原问题（对偶问题）对偶问题（原问题）一、原问题与对偶问题的对应关系Min

W=30y1+60y2+24y3

y1+3y2402y1+2y2+2y350y1,y2,y3

0s.t（y1）

（y2）（y3）

（x1）

13040（x2）22250306024

minωmaxz

3个约束2个变量2个约束3个变量线性规划的对偶理论对偶问题的形式定义设原线性规划问题为则称下列线性规划问题为其对偶问题，其中yi

(i=1,2,…,m)称为对偶变量上述对偶问题称为对称型对偶问题原问题简记为(P)，对偶问题简记为(D)称问题(P)和(D)为一对对偶问题线性规划的对偶理论对称型问题的对偶规则1、给每个原始约束条件定义一个非负对偶变量yi(i=1,2,…,m)；2、使原问题的目标函数系数cj

变为其对偶问题约束条件的右端常数；3、使原问题约束条件的右端常数bi变为其对偶问题目标函数的系数；4、将原问题约束条件的系数矩阵转置，得到其对偶问题约束条件的系数矩阵；5、改变约束问题不等号的方向，即将“≤”改为“≥”；6、原问题为“max”型，对偶问题为“min”型。线性规划的对偶理论原始问题MaxZ=CXs.t.AX≤b

X

≥0bAC≤Maxnm对偶问题MinW=Ybs.t. YA≥C Y≥0≥MinCATbnmY为行向量线性规划的对偶理论当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。线性规划的对偶理论求线性规划问题的对偶规划解：由原问题的结构可知为对称型对偶问题例1线性规划的对偶理论求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。例2线性规划的对偶理论求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。例3线性规划的对偶理论上式已为对称型对偶问题，故可写出它的对偶规划令则上式化为线性规划的对偶理论对偶问题的非对称形式minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≥≤=≤unr≥≤≥=≤≥x1≥0x2≤0x3:unr原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质，用

表示原始问题约束条件的性质影响对偶问题变量的性质，用表示线性规划的对偶理论原问题（或对偶问题）对偶问题（或原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=线性规划的对偶理论MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.ty1y2y3MinW=30y1+60y2+24y3

y1+3y2+0y3

402y1+2y2+2y3

50

y1,y2,y30s.tMaxW′=-30y1-60y2-24y3

y1+3y2+0y3–y4

=402y1+2y2+2y3

–y5

=50y1,y2,y3,y4,y50s.t例4二、对偶问题的解线性规划的对偶理论MaxW′=-30y1-60y2-24y3+0(y4+

y5)-M(y6+

y7)

y1+3y2+0y3–y4+

y6

=402y1+2y2+2y3

–y5

+

y7

=50y1,y2,y3,y4,y50s.tcj-30-60-2400-M-MB-1bθcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2σj3M-305M-602M-24-M-M00-90M线性规划的对偶理论cj-30-60-2400-M-MB-1bθcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3σj4M/3-1002M-242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/3040/340-24y32/3011/3-1/2-1/31/235/335/2σj600-12-12-M+12-M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/21/2-3/4-1/23/435/2σj00-9-15-15/2-M+30-M-15/2-975线性规划的对偶理论cj4050000B-1bcBxBx1x2x3x4x540x1101/2-1/20150x5003/2-1/21950x201-3/41/4015/2σj00-35/2-15/20975MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.t

x1+2x2+x3=303x1+2x2+x4=602x2+x5=24

x1–x50s.t线性规划的对偶理论线性规划的对偶理论原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。线性规划的对偶理论XBb原问题的变量原问题的松弛变量x1x2x3x4x5x115101/2-1/20x59003/2-1/21x215/2013/4-1/4000-35/2-15/20YBb对偶问题的变量对偶问题的剩余变量y1y2y3y4y5y215/201-1/2-1/21/4y135/2103/21/2-3/400-9-15-15/2原问题最优表对偶问题最优表MaxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x20s.tMinW=30y1+60y2+24y3

y1+3y2+0y3

402y1+2y2+2y3

50

y1,y2,y30s.t线性规划的对偶理论性质1对称性定理：对偶问题的对偶是原问题

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≤bX≥0三、对偶原理线性规划的对偶理论minz′=-

CXs.t.-AX≥-b X≥0maxw′=-Ybs.t.-YA≤-C

Y≥0minw=Ybs.t.YA≥C

Y≥0maxz=CXs.t.AX≤bX≥0对偶的定义对偶的定义简要证明：线性规划的对偶理论性质2弱对偶原理(弱对偶性)：设和分别是问题(P)和(D)的可行解，则必有推论1:

原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。证明：(1)当X和Y为原问题和对偶问题的一个可行解有原问题目标函数值对偶问题目标函数值线性规划的对偶理论推论2:

在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。若（P）为无界解，则（D）无可行解；若（D）为无界解，则（P）无可行解。线性规划的对偶理论推论3：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题目标函数值无界。已知原问题(LP)，试估计它的目标函数值的界,并验证弱对偶定理.例5线性规划的对偶理论解：问题(LP)的对偶问题(DP)为(DP)线性规划的对偶理论由观察可知分别是原问题和对偶问题的可行解。，弱对偶定理成立。且由推论1知，对偶问题目标函数W的下界为10，原问题目标函数Z的上界为40。且原问题的目标函数值为对偶问题的目标函数值为故线性规划的对偶理论例：利用对偶性质判断下面问题有无最优解例6解：此问题的对偶问题为不能成立，因此对偶问题不可行。故由推论3知原问题无界。为可行解线性规划的对偶理论性质3最优性定理：如果是原问题的可行解，是其对偶问题的可行解，并且:则是原问题的最优解，是其对偶问题的最优解。线性规划的对偶理论性质4强(主)对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。还可推出另一结论：若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等；若一个问题无最优解，则另一问题也无最优解。一对对偶问题的关系，有且仅有下列三种：都有最优解，且目标函数最优值相等；两个都无可行解；一个问题无界，则另一问题无可行解。线性规划的对偶理论证明：当X*为原问题的一个最优解，B为相应的最优基，通过引入松弛变量Xs，将问题(P)转化为标准型令CCBCN0解基系数基变量XBXNXsCBXBIB-1NB-1B-1bσ0CN-CBB-1N

-CBB-1CBB-1bCXAC-CBB-1A说明Y*可行线性规划的对偶理论问题:（1）由性质4可知，对偶问题最优解的表达式Y*=?（2）求Y*是否有必要重新求解(D)?—不必。可以从原问题（P）的单纯形终表获得。CCBCN0解基系数基变量XBXNXsCBXBIB-1NB-1B-1bσ0CN-CBB-1N

-CBB-1CBB-1b线性规划的对偶理论性质5

互补松弛性：设X0和Y0分别是P问题和D问题的可行解，则它们分别是最优解的充要条件是：其中：Xs、Ys为松弛变量。在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；另一方面，如果约束条件取严格不等式，则其对应的变量一定为零。紧约束与松约束线性规划的对偶理论证:(必要性）原问题对偶问题线性规划的对偶理论MaxZ=CXs.t. AX+XS=b X,XS≥0MinW=Ybs.t.YA-YS=C W,WS≥0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数线性规划的对偶理论

y1

yi

ymym+1

ym+j

yn+m

x1

xj

xnxn+1

xn+i

xn+m

对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0

yixn+i=0

(i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0线性规划的对偶理论性质5的应用： 该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y＊求X＊或已知X＊求Y＊互补松弛条件由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：

若Y＊≠0，则Xs必为0；若X＊≠0，则Ys必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。线性规划的对偶理论已知线性规划的最优解是X＊=(6,2,0)T,求其对偶问题的最优解Y＊。解：写出原问题的对偶问题，即标准化例7线性规划的对偶理论设对偶问题最优解为Y＊＝(y1，y2),由互补松弛性定理可知，X＊和Y＊满足：即：因为x1≠0，x2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即y3＝0，y4＝0，带入方程中：解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：Y＊=(1,1)，最优值w=26。线性规划的对偶理论已知线性规划的对偶问题的最优解为Y＊=(0,-2)，求原问题的最优解。解:对偶问题是标准化例8线性规划的对偶理论设原问题最优解为X＊＝(x1，x2，x3)T,由互补松弛性定理知，X＊和Y＊满足：将Y＊带入由方程可知，y3＝y5＝0，y4＝1。∵y2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0将x2，x5分别带入原问题约束方程中，得：解方程组得：x1=-5,x3=-1,所以原问题的最优解为X＊=(-5,0,-1)，最优值z=-12线性规划的对偶理论试用对偶原理求解线性规划问题已知其对偶规划的最优解为练习线性规划的对偶理论解：该问题的对偶规划为线性规划的对偶理论利用松紧关系，代入对偶规划的约束条件得下列约束是松约束，将最优解松约束紧约束其对偶约束是紧约束线性规划的对偶理论设原问题的最优解为紧约束线性规划的对偶理论对偶规划可以用线性规划的单纯形法求解。由对偶原理可见，原问题与对偶问题之间有紧密联系，因此我们能够通过求解原问题来找出对偶问题的解，反之依然。互补松弛条件就可以解决由原问题的最优解直接求出对偶问题的最优解。对偶问题解的求法线性规划的对偶理论原问题与对偶问题解的对应关系小结对应关系原问题最优解无界解无可行解对偶问题最优解(Y,Y)(N,N)————无界解————(Y,Y)无可行解——(Y,Y)无法判断线性规划的对偶理论思考题判断下列结论是否正确，如果不正确，应该怎样改正？1）任何线性规划都存在一个对应的对偶线性规划.2）原问题第i个约束是“≤”约束，则对偶变量yi≥0.3）互为对偶问题，或者同时都有最优解，或者同时都无最优解.4）对偶问题有可行解，则原问题也有可行解.5）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7）原问题无最优解，则对偶问题无可行解.8）对偶问题不可行，原问题可能无界解.9）原问题与对偶问题都可行，则都有最优解.10）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最优解.12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.线性规划的对偶理论2.5

影子价格单位产品消耗的资源(吨/件))原始问题是利润最大化的生产计划问题总利润(元)产品产量(件)单位产品的利润(元/件)消耗的资源(吨)剩余的资源(吨)资源限量(吨)影子价格对偶问题——资源定价问题对偶问题是资源定价问题，对偶问题的最优解y1、y2、...、ym称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润Maxz=Minw总利润(元)资源限量(吨)资源价格(元/吨)影子价格在一对P和D中，若P的某个约束条件的右端项常数bi

（第i种资源的拥有量）增加一个单位时，所引起目标函数最优值z*的改变量称为第

i种资源的影子价格，其值等于D问题中对偶变量yi*。由对偶问题得基本性质可得：1.影子价格的数学分析：影子价格2.影子价格的经济意义1）影子价格是一种边际价格 在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量yi

就是第

i种资源的影子价格。即：

影子价格资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0影子价格0X2X1X=(15,7.5)Z=975MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(14.5,8.25)

Z=992.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(15.5,7.25)

Z=982.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t0X2X1X=(15,7.5)Z=975X=(15.5,7.25)

Z=982.5X=(14.5,8.25)

Z=992.5MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t2）影子价格是一种机会成本 影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。若第i种资源的单位市场价格为mi

，则有当yi*>mi

时，企业愿意购进这种资源，单位纯利为yi*－mi

，则有利可图；当yi*<mi

时，企业有偿转让这种资源，可获单位纯利mi－yi

*

，否则，企业无利可图，甚至亏损。结论：若yi*>mi

则购进资源i，可获单位纯利yi*－mi

；

若yi*<mi则转让资源i，可获单位纯利mi－yi

。影子价格y1y2ym产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源影子价格机会成本利润差额成本产品的差额成本（ReducedCost）差额成本=机会成本-利润影子价格3）影子价格在资源利用中的应用根据对偶理论的互补松弛性定理:Y*Xs=0,YsX*=0表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为0；若当资源资源的影子价格不为0时，表明该种资源在生产中已耗费完。影子价格yixn+i=0如果yi>0，则xn+i=0如果xn+i>0，则yi=0边际利润大于0的资源，在最优生产计划条件下没有剩余ym+jxj=0如果ym+j>0，则xj=0如果xj>0，则ym+j=0最优生产计划条件下有剩余的资源，其边际利润等于0差额成本大于0（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于0（机会成本等于利润）互补松弛关系经济解释影子价格4）影子价格对单纯形表计算的解释单纯形表中的检验数其中cj表示第j种产品的价格;表示生产该种产品所消耗的各项资源的影子价格的总和，即产品的隐含成本。当产值大于隐含成本时，即，表明生产该项产品有利，可在计划中安排；否则，用这些资源生产别的产品更有利，不在生产中安排该产品。影子价格2.6

对偶单纯形法 对偶单纯形