第二章 对偶理论

对偶理论(DualityTheory)线性规划的对偶问题对偶问题的基本性质对偶问题的经济解释----影子价格

对偶单纯形法灵敏度分析

对偶性是线性规划问题的最重要的内容之一。每一个线性规划（LP

）必然有与之相伴而生的另一个线性规划问题，即任何一个求maxZ

的LP都有一个求minZ的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。一、线性规划的对偶问题（一）对偶问题的提出

例一、资源的合理利用问题1810单件利润150（设备）51C100（煤炭）32B170（钢材）25A资源限制乙甲单件产消耗品资源

已知资料如表所示，问应如何安排生产计划使得既能充分利用现有资源又使总利润最大？下面从另一个角度来讨论这个问题：假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费标准（合理的）？分析问题：

1、每种资源收回的费用不能低于自己生产时的可获利润；

2、定价又不能太高，要使对方能够接受。生产产品甲需资源5(A),2(B),1(C),盈利10元；生产产品乙需资源2(A),3(B),5(C),盈利18元；租赁公司又希望用最小的费用将三种资源全部买过来

一般而言，W越小越好，但因需双方满意，故为最好。该问题的数学模型为：模型对比：例二、合理配料问题，其数学模型为：假设工厂想把这m

种营养成分分别制成一种营养丸销售，问如何定价（以保证总收入为最多）？原问题对偶问题目标函数maxmin约束条件≤≥变量数量约束条件个数约束条件个数变量数量例三、23x1

x2

原问题12y1

22≤128y2

12≤816y340≤1612y404≤12对偶问题23（原问题）（对偶问题）模型对比：已知P，写出D。

（二）对称形式下对偶问题的一般形式例一：写出线性规划问题的对偶问题解：首先将原式变形

注意：以后不强调等式右段项b≥0，原因在对偶单纯型表中只保证而不保证，故b可以是负数。（三）非对称形式的原-对偶问题关系例二：原问题混合型对偶问题例三：原问题对偶问题综上所述，其变换形式归纳如下：原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=b约束条件右端项目标函数变量的系数C目标函数变量的系数约束条件右端项例四、线性规划问题如下：练习：235317146224Maxw=2y1+3y2+5y3y10y20y30≥≤≤≤≤≤y3y3y3y2+y2+y2+y1+y1+y1+正反无约束1-23401342-3-7-432-34Min

W=0y1-5y2+2y3y1

y3

y2

反正≥0≤0无约束≥0≤0=0=0单纯形法计算的矩阵描述项目非基变量基变量XBXN

XS0XBb

BN

I

cj

-zj

CBCN

0项目基变量非基变量XBXN

XSCB

XB

B-1bI（B-1B）B-1NB-1

cj

-zj0CN-CBB-1N-CBB-1二、对偶问题的基本性质CBB-1：单纯形乘子单纯形法计算的矩阵描述原问题检验数与对偶问题解的关系

设原问题是maxz=CX;AX+IXS=b;X,XS≥0它的对偶问题是minω=Yb;YA-IYS=C;Y,YS≥0则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如表所示。YS1是对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量

‖‖YS=(YS1,YS2)T

证:设B是原问题的一个可行基，于是A=(B,N)；原问题可以改写为

maxz=CBXB+CNXNBXB+NXN+XS=bXB，XN，XS≥0相应地对偶问题可表示为

minω=YbYB-YS1=CB(1)YN-YS2=CN(2)Y，YS1,YS2≥0这里YS=(YS1，YS2)T。当求得原问题的一个解：XB=B-1b其相应的检验数为CN-CBB-1N与-CBB-1现分析这些检验数与对偶问题的解之间的关系：令Y=CBB-1，将它代入(1)式，(2)式得YS1=0,-YS2=CN-CBB-1NminZ’=-CXs.t.-AX≤-b X≥01、对称性定理：对偶问题的对偶是原问题。

minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥b X≥0对偶的定义对偶的定义maxW’=-Ybs.t.YA≥CY≤0对偶问题的基本性质弱对偶定理定理对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值

为了便于讨论，下面不妨总是假设

推论⑴

若和分别是问题（P）和（D）的可行解，则是（D）的目标函数最小值的一个下界；是（P）的目标函数最大值的一个上界。2、弱对偶性（弱对偶原理）：设和分别是问题（P）和（D）的可行解，则必有

推论⑵.在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。关于无界性有如下结论：问题无界无可行解无可行解问题无界对偶问题原问题无界如：（P）无可行解（D）

推论⑶.在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该可行的问题无界。例1、试估计它们目标函数的界，并验证弱对偶性原理。（P）解：（D）由观察可知：=（1,1,1,1）T，=（1,1），分别是（P）和（D）的可行解。Z=10，W=40，故有，弱对偶定理成立。由推论⑴可知，W

的最小值不能小于10，Z

的最大值不能超过40。＜例2、已知试用对偶理论证明原问题无界。解：=(0,0,0)T是P的一个可行解，而D的第一个约束条件不能成立（因为y1,

y2≥0)。因此，对偶问题不可行，由推论⑶可知，原问题无界。

3、最优性

若X*

和Y*分别是P和D

的可行解且CX*=Y*b，则X*.Y*分别是问题P和D

的最优解。例如，在例1中，可找到X*=(0,0,4,4)T，

Y*=(1.2，0.2),则Z=28，W=28.故X*

、Y*分别是P和D的最优解。

4、强对偶性（对偶定理）：若一对对偶问题P和D

都有可行解，则它们都有最优解，且目标函数的最优值必相等。推论⑷若P和D的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。

综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：①都有最优解，分别设为X*

和Y*，则必有CX*=Y*b；②一个问题无界，则另一个问题无可行解；③两个都无可行解。

5、互补松弛定理：设X*和Y*分别是问题P和D的可行解，则它们分别是最优解的充要条件是同时成立一般而言，我们把某一可行点（如X*和Y*

）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。例3、已知试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为用图解法求出：Y*=（1,3），W=11。将y*1=1，y*2=3代入对偶约束条件，（1）（2）（5）式为紧约束，（3）（4）为松约束。令原问题的最优解为X*=(x1,x2,x3,x4,x5)T，则根据互补松弛条件，必有x3=x4=0(1,3)（1）（2）（3）（4）（5）又由于y*1＞0，y*2

＞0，原问题的约束必为等式，即此方程组为无穷多解令x5=0,得到x1=1，x2=2

即X*1=(1,2,0,0,0)T为原问题的一个最优解

Z*=11再令x5=2/3，得到x1=5/3，x2=0即X*2=(5/3,0,0,0,2/3)T也是原问题的一个最优解

Z*=11例4、已知原问题的最优解为X*=（0，0，4）T，Z=12。试求对偶问题的最优解。解：（1）（2）（3）将X*=（0，0，4）T代入原问题中，有下式：所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=3。因此，对偶问题的最优解为

Y*=（0，0，3），W=12。6、对偶问题的解利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解。⑴.设原问题为：maxZ=CXAX≤

bX≥0引入xs

，构建初始基变量，然后，用单纯形法求解。当检验数满足σj≤0，则求得最优解。此时，xs对应的σjs

为-Y*

，故求对偶Y*

，只要将最优单纯形表上xs

对应的检验数反号即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CN－CBB-1N－CBB-1例1、cj1018000cBxBbx1x2x3x4x50x317052100170/20x410023010100/30x515015001150/5Z01018000cj1018000cBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7Z4100/7000-32/7-6/7初始表最终表由上表可知：X*=（50/7,200/7），Z=4100/7对偶问题的最优解：Y*=（0,32/7,6/7），W=4100/7也就是外加工时的收费标准。⑵.设原问题：maxZ=CXAX=bX≥0此时，矩阵A中没有现成的矩阵I，必须通过加入人工变量来凑一个单位矩阵，再用大M法或两阶段法求解。如何求Y*，经分析得出如下结论：

σB=0最优基变量检验数向量

σI=CI

－CBB-1

初始基变量检验数向量

σD=CD

－CBB-1D非基变量检验数向量所以，Y*=CI

－σI

例2、cj3-1-100-M-McBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/31/3-M2/3-Mcj3-1-100-M-McBxBbx1x2x3x4x5x6x70x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z3-6M-1+M-1+3M0-M00初始表最终表所以，X*=（4,1,9），Z=2∴y*1=(0－σ4)=1/3y*2=(－M－σ6)=－M－(1/3－M)=－1/3y*3=(－M－σ7)=－M－(2/3－M)=－2/3Y*=（1/3,－1/3,－2/3）W=2初始基变量的检验数σ4=－1/3，σ6=1/3－M,σ7=2/3－M定义：在一对P和D中，若P的某个约束条件的右端项常数bi

增加一个单位时，所引起的目标函数最优值Z*

的改变量y*i

称为第i

个约束条件的影子价格，又称为边际价格。三、对偶问题的经济解释—影子价格

设：B是问题P的最优基，由前式可知，

Z*=CBB-1b=Y*b=y*1b1+y*2b2+…+y*Ibi+…+y*mbm

当bi

变为bi+1时（其余右端项不变，也不影响B），CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CN－CBB-1N－CBB-1目标函数最优值变为：

Z′*=y*1b1+y*2b2+…+y*i（

bi+1）+…+y*mbm

∴△Z*=Z′*－Z*=y*i

也可以写成：

经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi

就是第i

个约束条件的影子价格。

也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。即y*i

表示Z*对bi的变化率。影子价格在管理决策中的作用：

（2）影子价格反映了资源的稀缺性，影子价格越高，则越稀缺。影子价格＞市场价格，影子价格＜市场价格，则应买进该资源则应卖出该资源（1）影子价格≠市场价格01020304050601020304050x2

x1123(50/7.200/7)①②③01020304050601020304050x2

x1123(50/7.200/7)Y1=0①②③多了32/7x101020304050601020304050x2

123(55/7.199/7)Y2=

32/7①②③01020304050601020304050x2

x1123(47/7.202/7)多了6/7Y3=

6/7①②③

5.由最优单纯形表求对偶问题最优解

标准形式：

Max

z=50x1+100x2

s.t.x1+x2+x3=300

2x1+x2+x4=400

x2+x5=250

x1,x2,x3,x4,x5

≥0cBB-1B=(p1,p2,p4)B-1最优解

x1=50x2=250x4=50(松弛变量，表示原料A有50个单位的剩余）影子价格y1=50y2=0y3=50,B-1对应的检验数cBB-1

。‖‖

对偶单纯形法是求解线性规划的另一基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。四、对偶单纯形法

对偶单纯形法的基本思想对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正σj≤0），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。4.对偶单纯形法对偶单纯形法在什么情况下使用：

应用前提：有一个基，其对应的基满足:

①单纯形表的检验数行全部非正（对偶可行）；

②变量取值可有负数（非可行解）。

注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯性表。4.对偶单纯形法1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若b′≥0,则得到最优解,停止;否则,令bk=min{bi<0}

则选k行的基变量为出基变量,转33.若所有akj’≥0(j=1,2,…,n)，则原问题无可行解,停止;否则,若有akj′<0

则选

=min{j’/

akj’┃akj’<0}=r’/akr’那么xr为进基变量,转4；4.以akr’为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。

对偶单纯形法求解线性规划问题过程：例一、用对偶单纯形法求解：解：将模型转化为cj-9-12-15000cBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1-5001Z′

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/5Z′

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

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

-72000-1/3-3-7/3(-3/-9,-45/-9,-33/-1)

所以，

X*=（2,2,2,0,0,0），

Z′*=－72，

原问题Z*=72

其对偶问题的最优解为：

Y*=(1/3,3,7/3)，W*=72对偶单纯形法的优点

1．初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。

2．当变量多于约束条件，对这样的线性规划问题，用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将变换成对偶问题，然后用对偶单纯形法求解。

3．在灵敏度分析中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这方法在求解线性规划问题时很少单独应用练习：cj-2-3-400cBxBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301Z

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

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

28/500-3/5-8/5-1/5Y=（8/5,1/5）X=（11/5,2/5,0）Z=28/5单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法

对偶单纯形法的适用范围对偶单纯形法适合于解如下形式的线性规划问题4.对偶单纯形法在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。

五、灵敏度分析

以前讨论线性规划问题时，假定aij，bi，cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；aij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；(2)或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。后一个问题将在第6节参数线性规划中讨论。线性规划问题中某一个或几个系数发生变化?显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按下表中的几种情况进行处理。灵敏度分析步骤：

1.将参数的改变通过计算反映到

最终单纯形表上2.检查原问题是否仍为可行解。3.检查对偶问题是否仍为可行解。表2-94.按表2-9所列情况得出结论或决定继续计算的步骤。一、目标函数中价值系数cj的变化分析

可以分别就cj是对应的非基变量和基变量两种情况来讨论。(1)若cj是非基变量xj的系数，这时它在计算表中所对应的检验数是

σj=cj-CBB-1Pj

或当cj变化Δcj后，要保证最终表中这个检验数仍小于或等于零，即σj’=c’j-CBB-1Pj≤0那么cj+Δcj≤YPj，即Δcj的值必须小于或等于YPj-cj，才可以满足原最优解条件。这就可以确定Δcj的范围了。

例3：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划已知最优表如下。（1）确定x2的系数c2的变化范围，使原最优解保持最优；（2）若c2=6，求新的最优计划。一、价值系数cj的变化分析cj5000CBXBbx1x2x3x4x50x3250012-55x1351001-14x2

10010-12000-1-3最优单纯形表4c2最优解不变？σ4=c2－5≤0σ5=5－2c2

≤05/2≤c2≤5cj5c2

000CBXBbx1x2x3x4x50x3250012-55x1351001-1c2

x2

10010-12000c2-55-2c2最优解X*=（35，10，25，0，0）保持不变。（1）Cj56000CBXBbx1x2x3x4x50x325001[2]-55x1351001-16x2

10010-12σj

0001-70x425/2001/21-5/25x145/210-1/203/26x2

45/2011/20-1/2σj00-1/20-9/2x1*=45/2，x2*=45/2，x4*=25/2，x3*=x5*=0，z*=495/2（2）二、资源数量变化的分析(b)

资源数量变化是指资源中某系数br发生变化，即br′=br+Δbr。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为XB′=B-1(b+Δb)这里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB′为新的最优解。新的最优解的值可允许变化范围用以下方法确定。B-1

是最终计算表中的最优基的逆例1：求下列LP问题Cj0-130-20CBXBbx1x2x3x4x5x60x1713-10200x4120-2[4]1000x6

100-43081σj

0-130-200x1101[5/2]01/4203x330-1/211/4000x6

10-5/20-3/481σj01/20-3/4-20-1x242/5101/104/503x351/5013/102/500x6

11100-1/2101σj-1/500-4/5-12/50B3=（P2，P3，P6）=B3－1=例4：对于上例中的线性规划作下列分析：（1）b3在什么范围内变化，原最优基不变？（2）若b3=55，求出新的最优解。

二、右端常数bi的变化分析cj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14x2

10010-12000-1-3最优基：B=（P3，P1，P2）B－1=（1）B－1==≥0解得40≤b3≤50，即当b3∈[40，50]时，最优基B不变z*=5×（80－b3）+4×（－80+2b3）=80+3b3=（2）当b3=55时

=x2

x1x50-11/5-3/500σj0-1/52/51020403/5-1/5013051-2/5-1/50050-32-1[-5]x50-1000σj

-101030x2

4100125x152100-25x30x4x3x2x1bXBCB0045Cj对偶单纯形三、增加一个变量的分析例5：（续例3）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示P6=。问它的价值系数c6符合什么条件才必须安排它的生产？设c6=3，新的最优生产计划是什么？σ6=c6－CBB－1P6=c6－（0，5，4）=c6－5/2=B－1P6==Cj540003CBXBbx1x2x3x4x5x60x3250012-5[1]5x1351001-11/26x2

10010-120σj

000-1-31/23x6250012-515x145/210-1/203/204x2

10010-120σj00-1/2-2-1/20四、增加新的约束条件的分析4x1+2x2+x6=150X*=（35，10，25，0，0）T例6:

假设在例3中，还要考虑一个新的资源约束：

4x1+2x2≤1504x1+2x2+x6=150cj540000CBXBbx1x2x3x4x5x60x3250012-505x1351001-104x2

10010-1200x6150420001000-1-30变化：基变量x1、x2、x3所对应的矩阵不再是单位矩阵。Cj540000CBXBbx1x