运筹学2对偶问题运筹学教程运筹学Operations Research Chapter 2 对偶问题Dual Problem1. 线性规划的对偶模型Dual Model of LP2.对偶性质对偶性质3.对偶单纯形法对偶单纯形法4.灵敏度分析灵敏度分析Dual property Dual Simplex Method Sensitivity Analysis 运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 2 of 19在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。
【例2.1】某企业用四种资源生产三种产品，工艺系数、例资源限量及价值系数如下表：产品资源Ⅰ Ⅱ Ⅲ Ⅳ 每件产品利润9 5 8 7 100 8 4 3 6 80 6 7 2 4 70 500 450 300 550 A B C 资源限量建立总收益最大的数学模型。
运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dualmodel of LPCh2 Dual Problem2022年11月26日星期五Page 3 of 19 设x1,x2,x3分别为产品A,B,C的产量，则线性规划数学模解型为：m Z = 100x + 80x + 70x ax1 2 39x1 + 8x2 + 6x3 ≤ 500 5x + 4x + 7x ≤ 450 2 3 1 8x1 + 3x2 + 2x3 ≤ 300 7x + 6x + 4x ≤ 550 2 3 1 x1, x2, x3 ≥ 0 现在从另一个角度来考虑企业的决策问题。
假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？价格太高对方不愿意接受，价格太低本单位收益又太少。
合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。
这一决策问题可用下列线性规划数学模型来表示。
运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 4 of 19 设y1,y2,y3及y4分别表示四种资源的单位增殖价格(售价=成本+增殖),总增殖最低可用min w=500y1+450y2+300y3+550y4 表示。
企业生产一件产品A用了四种资源的数量分别是9, 5,8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100,即9y1 + 5y2 + 8y3 + 7y4 ≥ 100同理，对产品B和C有8y1 + 4y2 + 3y3 + 6y4 ≥ 80 6y1 + 7y2 + 2y3 + 4y4 ≥ 70价格不可能小于零，即有yi≥0,i=1, 。
,4.从而企业的资源价格模型为运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 5 of 19m w = 500y1 + 450y2 + 300y3 + 550y4 in 9y1 + 5y2 +8y3 + 7y4 ≥100 8y + 4y + 3y + 6y ≥ 80 1 2 3 4 6y1 + 7y2 + 2y3 + 4y4 ≥ 70 yi ≥ 0, i =1, ,4 这是一个线性规划数学模型，称这一线性规划问题是前面生产计划问题的对偶线性规划问题或对偶问题。
生产计划的线性规划问题称为原始线性规划问题或原问题。
运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 6 of 19【例2.2】某人根据医嘱，每天需补充A、B、C三种营养，例A不少于80单位，B不少于150 单位，C不少于180单位。
此人准备每天从六种食物中摄取这三种营养成分。
已知六种食物每百克的营养成分含量及食物价格如下表，试建立此人在满足健康需要的基础上花费最少的数学模型。
含量营养成分食物A B C食物单价(元/100g)一13 24 18 0.5二25 9 7 0.4三14 30 21 0.8四40 25 34 0.9五8 12 10 0.3六11 15 0 0.2需要量≥80 ≥150 ≥180运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 7 of 19 设xj为每天第j种食物的用量，数学模型为解13 x1 + 25x2 +14x3 + 40x4 + 8x5 +11x6 ≥ 80 24x + 9x + 30x + 25x +12x +15x ≥ 150 1 2 3 4 5 6 18 x1 + 7x2 + 21x3 + 34x4 +10x5 ≥ 180 x1、2、x3、x4、5、x6 ≥ 0 x xm Z = 0.5x1 + 0.4x2 + 0.8x3 + 0.9x4 + 0.3x5 + 0.2x6 in现有一制药厂要生产一种包含A、B、C三种营养成分的合成药，如何制定价格，使得此药既要畅销又要产值最大。
设yi(i=1,2,3)为第i种营养成分的单价，则运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 8 of 19 m w = 80y1 +150y2 +180y3 ax 13 y1 + 24y2 +18y3 ≤ 0.5 25y + 9y + 7y ≤ 0.4 2 3 1 y1 + 30y2 + 21y3 ≤ 0.8 14 40y1 + 25y2 + 34y3 ≤ 0.9 8y +12y +10y ≤ 0.3 2 3 1 y1 +15y2 ≤ 0.2 11 y1、y2、y3 ≥ 0影子价格( 影子价格Shadow price): 上面两个线性规划有着重要的经济含义。
原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格影子价格，影子价格即对偶问题中的决策变量yi的值。
运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 9 of 19 由后面的对偶性质可知：原问题和对偶问题的最优值相等，故有Z = CB X B = CB B 1b = Yb = ∑bi yii=1 mZ = yi i = 1, , m bi 即yi是第i种资源的变化率，说明当其它资源供应量bk(k≠i) 不变时，bi增加一个单位时目标值Z增加yi个单位。
运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 10 of 19 例如，第一种资源的影子价格为y1=2,第二种资源的影子价格为y2=2,即当第一种资源增加一个单位时，Z增加2个单位,当第二种资源增加一个单位时，Z增加2个单位。
企业可利用影子价格调节生产规模。
例如，目标函数Z表示利润(或产值),当第i种资源的影子价格大于零(或高于市场价格)时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零(或低于市场价格), 企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模。
应当注意，Z 是在最优基B不变的条件下有上述yi= bi 经济含义，当某种资源增加或减少后，最优基B 可能发生了变化，这时yi的值也随之变化。
运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 11 of 19 在例2.1中，原问题的最优解X=(24.24,0,46.96) 对偶问题的最优解Y=(10.6,0.91,0,0) 最优值z=w=5712.12 分析：分析1. y1=10.6说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来10.6元的利润；如果要出售该资源，其价格至少在成本价上加10.6元。
2. y3=0说明增加第三种资源不会增加利润，因为第三种资源还有没有用完。
问题：1.第三、四种资源的售价是多少，是否不值钱？问题 2. 如果要增加利润，企业应增加哪几种资源，各增加多少后再进行调整？运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 12 of 19 以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。
原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。
上面两种形式的线性规划称为对称形式。
对称形式的定义是：目标函数求极大值时，所有约束条件对称形式为≤号，变量非负；目标函数求极小值时，所有约束条件为≥号，变量非负。
对称形式的线性规划的对偶问题亦是对称形式。
运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 13 of 19 【例2.3】写出下列线性规划的对偶问题例m Z = 5x1 2x2 + 3x3 in 4x1 + x2 x3 ≥ 4 x1 7x2 + 5x3 ≥ 1 x , x , x ≥ 0 1 2 3这是一个对称形式的线性规划，设Y=(y1,y2), 解则有4 m w = Yb = ( y1, y2 ) = 4y1 + y2 ax 1 1 4 1 - YA = ( y1, y2 ) 1 - 5 7 = (4y1 + y2 , y1 7y2, y1 + 5y2 ) ≤ (5, 2,3)运筹学教程§2.1线性规划的对偶模型线性规划的对偶模型Dual model of LPCh2 Dual Problem2022年11月26日星期五Page 14 of 19 从而对偶问题为m Z = 4y1 + 3y2 ax 4y1 + y2 ≤ 5 y1 7y2 ≤ 2 y1 + 5y2 ≤ 3 y1 ≥ 0, y2 ≥ 0对偶变量yi也可写成xi的形式。