下载文档原格式
第二章线性规划的对偶理论与灵敏度分析一、学习目的与要求 1、掌握对偶理论及其性质 2、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法 二、课时 6学时第一节 线性规划的对偶问题一、对偶问题的提出定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。
应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。
例：某家具厂木器车间生产木门与木窗；两种产品。
加工木门收入为56元/扇，加工木窗收入为30元/扇。
生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。
问：(1)该车间应如何安排生产才能使每日收入最大？(2)假若有一个个体经营者，手中有一批木器家具生产订单。
他想利用该木器车间的木工与油漆工来加工完成他的订单。
他就要考虑付给该车间每个工时的价格。
他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。
解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为⎪⎩⎪⎨⎧≥≤+≤++=-0502120343056max 21212121x x x x x x x zX*=(15,20)’ Z*=1440元解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格⎪⎩⎪⎨⎧≥≥+≥++=-0303562450120min 21212121y y y y y y y wY*=(2,24)’ W*=1440元将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的联系与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。
习题二2.1 写出下列线性规划问题的对偶问题(1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤54x1＋x2＋x3≤20 2x1－x2＋3x3＝－4x j≥0 （j＝1,2,3）x1－x3＋x4≥1x1，x3≥0，x2，x4无约束(3) min z ＝3x1＋2 x2－3x3＋4x4(4) min z ＝－5 x1－6x2－7x3st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤202x1－3x2－7x3 －4x4＝2＝x1－x2－x3＝－5 x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束2.2 已知线性规划问题max z＝CX，AX=b，X≥0。
分别说明发生下列情况时，其对偶问题的解的变化：（1）问题的第k个约束条件乘上常数λ（λ≠0）；（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为max z＝λCX（λ≠0）；'x代换。
（4）模型中全部x1用312.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4st. x1＋2x2＋x4≥33x1＋x2＋x3＋x4≥6x3 ＋x4＝2x1 ＋x3 ≥2x j≥0（j＝1,2,3,4）(1) 写出其对偶问题；(2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。
2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量st. 2x1 ＋x3＋x4≤8 y12x1＋2x2＋x3＋2x4≤12 y2x j≥0（j＝1,2,3,4）对偶问题的最优解y1*=4；y2*=1，试对偶问题的性质，求出原问题的最优解。
2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3st. 3x1＋4 x2＋2x3≤602x1＋x2＋2x3≤40x1＋3x2＋2x3≤80x j≥0 （j＝1,2,3）４７４８（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。
运筹学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的形式。
