对偶理论及其应用

第三章

线性规划的对偶理论及其应用书山有路勤为径，学海无涯苦作舟对偶是一种普遍现象1假设工厂考虑不进行生产而把全部可利用的资源都让给其他企业，工厂希望给这些资源定出一个合理的价格，即使别的单位愿意购买，又使本工厂能得到生产这些产品所能获得的最大收益。第一节对偶问题一、对偶问题的提出实例1（典型示例）：

3

2利润

12公斤

4

0原料B

16公斤

0

4原料A

8台时

2

1设备资源限量

II

I产品y3y2y1决策变量12168资源限量x23402IIx12041I决策变量每台收益原料B原料A设备资源产品2y3y2y1决策变量12168资源限量x23402IIx12041I决策变量每台收益原料B原料A设备资源产品3y4y3y2y1200300400600限额x330004322Cx240002314Bx120001123A每台收益丁丙乙甲材料产品假设工厂考虑不进行生产而把全部可利用的资源都让给其他企业，工厂希望给这些资源定出一个合理的价格，即使别的单位愿意购买，又使本工厂能得到生产这些产品所能获得的最大收益。实例2：4比较上述模型，可以得出两者之间的一些关系：

1.两个问题，一个是极大化，另一个是极小化；

2.一个问题的变量数等于另一问题的方程数，反之亦然；

3.一个问题的目标函数系数是另一个问题的约束方程右端常数，反之亦然；

4.两个问题的约束方程系数矩阵互为转置。称变量yi为第一个LP的第i个对偶变量，或第一个LP的第i约束相应的对偶变量5

对偶问题的提出有其理论依据，可由“单纯形法的矩阵描述”加以解释。

67二、对称LP问题1.对称形式的定义必须满足下列条件：

（1）变量为非负；（2）约束条件为不等式。对于max，约束为“£”；对于min，约束为“³”。第一类对称形式第二类对称形式82.对称LP问题的对偶问题9例3：写出下列LP问题的对偶问题对偶对偶变量y1y2y3原变量x1x210推导过程变形对偶3.对偶问题的对偶11对偶变形结论：对偶问题的对偶是原问题。12例4：写出下列LP问题的对偶问题解:上述LP问题的对偶问题为：对偶变量y1y2y3原变量x1x2x313例5：写出下列LP问题的对偶问题4.非对称LP问题的对偶问题141516对偶关系：一个问题第i个变量决定另一问题第i个约束，反之亦然。对称的对应对称的，非对称的对应非对称的17直接写出例5的LP问题的对偶问题1819已知LP问题：1)写出其对偶模型；2)如果用大M法求解原问题，请列出初始单纯形表，并用[]标出主元素。补充作业3-1

20第二节LP问题的对偶理论定理1弱对偶定理:极大化原问题目标函数值总是不大于其对偶问题的目标函数值。21结论：在双方都是可行解的情况下，极大化问题的目标函数值总不大于其对偶问题目标函数值。22推论1：

若LP问题有无界解，则其对偶问题无可行解；若LP问题无可行解，则对偶问题或无解或为无界解。推论2：

极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。

极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。推论3：23例6

考虑下面一对LP问题其对偶问题为：24证明：定理2最优性准则

当LP问题目标函数值与其对偶问题目标函数值相等时，各自的可行解即为最优解。若X(0),Y(0)分别为PP，DP的可行解,且CTX(0)＝bTY(0)

，则X(0),Y(0)分别为PP，DP的最优解。25例726补充作业3-2

27证明：定理3强对偶定理

若PP，DP均有可行解，则PP，DP均有最优解，且目标函数最优值相等。282930补充作业3-3

31证明：以PP是max为例。当PP为max，则PP的检验数与DP的解之间仅差一个负号；当PP为min，则PP的检验数与DP的解完全相同。推论：用单纯形求解LP问题时，PP的检验数对应DP的一个解（最优时为基可行解，其余为基解）。

323334当PP为max，在用单纯形法求解LP问题PP的最优单纯形表中松弛变量的检验数的相反数就是其DP的最优解；YTS10XB－YTS2CN－CBB－1

NXN－CBB－1PP的检验数－YTDP的解XSPP的变量PP检验数与DP解的对应关系表当PP为min，在用单纯形法求解LP问题PP的最优单纯形表中松弛变量的检验数就是其DP的最优解。35解：化为标准型例8求下列问题对偶问题的最优解36

X(0)＝(0,0,8,16,12)T以[1]为主元素进行旋转运算，x1为换入变量，x3为换出变量

0

qi

3

0

0

x5

x2

x3

x40

x4

x3XB

b

sj

0

x1CB

2cj

x1

cj

x2

x3

x4

x5

1

4

0

2

0

4

1

0

0

0

1

0

0

0

1

2

3

0

0

0

b816

12

XB

x3

x4

x5

CB

0

0

0以[4]为主元素进行旋转运算，x2为换入变量，x5为换出变量

sj

2

3

0

0

0

qi

8/2

—

12/4[4]

x2

3

0

0

0

1/43

1

4

0

1

016

0

0

1

1

0

-1/22X(1)＝(0,3,2,16,0)T

2

0

0

-3/4

016/4

2/1

—

[1]Y(0)＝(0,0,0,-2,-3)TY(1)＝(0,0,3/4,-2,0)T37此时达到最优解。X*=(4,2),maxZ=14。

0

qi

3

0

0

x5

x2

x3

x40

x4

x23

XB

b

sj

x1CB

2cj

0

qi

3

0

0

x5

x2

x3

x4x23

x1XB

b

sj

2

x1CB

2cj

0

0

0

1/43

10

-2

0

1/4

0

x1

2

0

1

1

0

-1/22

[2]

0-4

128

08/2

12

—

x50

0

-2

1/2

14

0

1

0

1/4

04

0

1/2

-1/8

0

02

10

-3/2

-1/8

0

0X(3)＝(4,2,0,0,4)TX(2)＝(2,3,0,8,0)T以[2]为主元素进行旋转运算，x5为换入变量，x4为换出变量Y(2)＝(2,0,-1/4,0,0)TY(3)＝(3/2,1/8,0,0,0)T38重要提示：

由上述实例可以看出：在用单纯形法求解LP问题时，PP没有得到最优解之前，每迭代一步得到一个基可行解，此时DP得到的是一个基解；而当PP得到最优解时，DP才得到一个基可行解。根据强对偶定理，DP得到的这个基可行解一定是DP的最优解。39定理4互补松弛定理在最优情况下，PP的第i个决策变量与其DP的第i个约束中的松弛变量的乘积恒为零。反之亦然。

(2)(1)(3)(4)设X(0),Y(0)分别为PP,DP的可行解，则X(0),Y(0)分别为PP,DP的最优解的充要条件为,有40例9考虑下面问题41解:则，42已知LP原问题为：已知原问题用两阶段法求得最优单纯形表如下，试用对偶理论写出其对偶问题的最优解。-230-50

0

-33

0

0

x5

x2

x3

x4-1/3001100002/3-13-214/31-15

x1

x2-33

x4

XBb0sj

030

x1CB

-15cj补充作业3-4

43第三节对偶问题的经济学解释——影子价格标准化一、对偶最优解的经济解释：资源的影子价格441、y*i的数学含义45

0

qi

3

0

0

x5

x2

x3

x40x5x23

x1XB

b

sj

2

x1CB

2cj

0

-2

1/2

14

0

1

0

1/4

04

0

1/2

-1/8

0

02

10

-3/2

-1/8

0

0标准化46

做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。Q(4,2)x1x24x1=164x2=12x1+2x2=844083Z=14Q(4.25,1.875)Z=14.125Q(4,2.5)Z=15.5Q(4,2)Z=1447

(1)对偶问题的最优解——买主的最低出价。

(2)原问题资源的影子价格——当该资源增加1单位时引起的总收入的增量——卖主的内控价格。

(3)代表在资源最优利用条件下对单位第i种资源的估价，这种估价不是资源的市场价格，而是根据资源在最优生产配置中作出的贡献而作的估价，为区别起见，称为影子价格（shadowprice)。资源影子价格≠资源市场价格资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。即：市场价格由市场确定；影子价格由生产企业确定。2、y*i的经济学含义48(4)影子价格反映了资源的稀缺性，影子价格越高，则越稀缺。(5)影子价格是一种边际价格。(6)资源的影子价格实际上又是一种机会成本。在完全市场经济条件下,当：资源的市场价格<影子价格，应买进这种资源资源的市场价格>影子价格，应卖出这种资源随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。493、影子价格在企业管理中的作用

(1)告诉管理者增加何种资源对企业更有利；

(2)告诉管理者花多大代价购买进资源或卖出资源是合适的；

(3)为新产品定价提供依据。50二、对偶约束的经济解释——产品的机会成本机会(隐含)成本：表示减少一件第j种产品生产所节省的资源量可以增加的利润或产值。51三、对偶松弛变量的经济解释——产品的差额成本机会成本差额成本=机会成本－利润或产值差额成本利润或产值52从对偶松弛变量ym+j看：

差额成本(ym+j)=机会成本－利润或产值从检验数σj看：第j种产品的相对价值系数(σj)=利润或产值－机会成本

当产品利润或产值>=机会(隐含)成本，可生产该产品；否则，不安排生产。——检验数的经济意义。53这表明在利润最大化的生产计划中，如果某种资源bi未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕，反映了资源的稀缺性。由此总结：

(1)影子价格大于0的资源没有剩余；

(2)有剩余的资源影子价格等于0；

(3)安排生产的产品机会成本等于利润；

(4)机会成本大于利润的产品不安排生产。四、互补松弛定理的经济解释54对偶典型示例分析：X*＝(4,2,0,0,4)TY*＝(3/2,1/8,0,0,0)T55第四节对偶单纯形法一、基本思想

由单纯形法的原理可知：在用单纯形法求解LP问题时，PP没有得到最优解之前，每迭代一步得到一个基可行解，此时DP得到的是一个基解；而当PP得到最优解时，DP才得到一个基可行解。根据强对偶定理，DP得到的这个基可行解一定是DP的最优解。

根据对偶问题的对称性，也可始终保持DP为基可行解，PP从基解开始迭代，当PP得到基可行解时，表明PP和DP都得到最优解。56

为了始终保持DP为基可行解，对于最大化的PP问题，其检验数必须保持非正；对于最小化的PP问题，其检验数必须保持非负。

由于PP可以从基解开始迭代，因此PP约束条件的右端常数项可以为非正。57二、步骤(以最大化为例):58建初始表

结束选出换出和换入变量进行运算YN59例11用对偶单纯形法求解下列LP问题解：原问题变形为6001021180000101-10-201000-11-1-40b-3-2-1

0

1

1

1

2

0

4

0

0

0

0

1

0

1

-1

0

-2

0

-1

0

0

0

1

-1

1

4-1

b

-3

-2

-10-1-2-3000

40-3-2-1006121130000000-10-1102-2-10-100016-1b-3-2-1

1000-5-10-3注意：对偶单纯形法不可理解成是求解对偶问题的单纯形法，而是根据对偶理论，允许原问题从初始非可行基开始迭代求解原问题的单纯形法。62三、几个问题的讨论63第五节灵敏度分析

模型中的参数A﹑b﹑C一般是预测估计的确定值，而在计划实施时，这些值一般不可能正好是事先估计的值，因此有必要在求解后，分析这些参数值在将来可能变化后对最优性的影响。灵敏度分析就是计算为保持原最优性质不变，模型中某一个参数（Cj或bi或aij）单独变化的允许范围。

一、定义64二、灵敏度分析常用的两个公式最优性(最优基)不变的条件：

1.可行条件：XB

≥02.最优条件：sj≤0（max）

灵敏度分析就是求出在上述两个最优条件仍成立的情况下，参数bi﹑cj﹑aij的变化范围。这需要将上述两式写成含有参数的表达式。65三、灵敏度分析的几种结果可行条件：XB=B-1b≥0。当bi发生变化时，只影响可行性。用XB=B-1b≥0求出bi的变化量，此时最优基不变（XB中的基变量名称没有变，但数值一般会改变）。

最优条件：sj≤0。当cj发生变化时，只影响最优性，用

sj≤0(sj=cj-∑ciaij=cj-CBPj’

)求出cj的变化量，此时只是Z值会改变，而最优解不变（最优基和基变量值均不变）。1.最优基不变，最优解保持不变，最优目标值可能改变。2.最优基不变，最优解改变，最优目标值改变。3.最优基改变，最优解改变，最优目标值改变。66最优基不变，最优解有可能变化，不需处理可行解可行解最优基改变，用单纯形法继续迭代求最优非可行解可行解非可行解可行解DP最优基改变，引进人工变量，编制新单纯形表，求最优最优基改变，用对偶单纯形法继续迭代求最优结果及处理方法非可行解非可行解PP灵敏度分析的几种结果及相应处理方法67四、常数项bi改变的灵敏度分析68其单纯形表如下所示6910.5-2004x50000x50-0.1250.5102x23-0.1250.25x40-1.500-140014x12x3x2x1bXBCB032cj0100416x40010x50004012x5000x40032

1218x30x3x2x1bXBCB032cj初始单纯形表707172730010x6000223130x60001x5012583150x7071x4700x70154648120x50x3x2x1bxBCB154

cj例

13:初始单纯形表74-52/15-13/158/15-1/15x600-1/1512/34/308x47-1/15-4/152/15x50105/313/3092x7000x4700x70-19/3-17/302/31/3114x14x3x2x1bxBcB154

cj7576771-12102x23-33x40-1-1x50-300-8

-1011x12x3x2x1bxBcB132

cj78791-12102x23-1-1x50-33x40-300-1011x12x3x2x1bXBCB132

cj例4:下面是一张LP问题的最优单纯形表,观察其基变量、非基变量目标函数系数的改变对检验数的影响五、C的改变8081即，821-12102x23-1-1x50-33x40-300-1011x12x3x2x1bXBCB132

cj83典型示例最优解及灵敏度分析目标函数最优值为:14

变量最优解相差值

x140x220

约束松弛/剩余变量对偶价格

101.520.125340

目标函数系数范围:

变量下限当前值上限

x11.52无上限

x2034

常数项数范围:

约束下限当前值上限

148102816323812无上限84要求xj=0六、A的变化85若xj

是非基变量若xj

是基变量86871-12102x23-1-1x500-33x4000-300-8

-1011x12x3x2x1bxBcB132

cj01-12102x23-1-1-1x513-200-1x60-33x400x6-300-8

-1011x12x3x2x1bxBcBx6881020101x23010x50-1-32001x50-60x40-1-1x60-100-7

1012x12x3x2x1bxBcB132

cj891-12102x23-1-1x50-3-300-8

3x4