运筹学3对偶 1

1、第三章线性规划的对偶理论,内容提要 3.1 线性规划的对偶问题 3.2 线性规划的对偶理论 3.3 对偶解的经济解释 3.4 对偶单纯形方法 3.5 灵敏度分析,3.1 线性规划的对偶问题,1. 对偶问题的提出 2. 如何将原问题转化为对偶问题 3. 原问题与对偶问题的对应关系,对偶问题的提出 例 3.1,某工厂拥有A、B、C三种类型的原料，生产甲、乙两种产品。每件产品在生产中消耗的原料数量，每件产品的价格以及三种原料可利用的数量如下表所示：,问题：工厂应如何安排生产可获得最大的总收益？ 解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。则有 目标函数 Max z = 50 x1 +

2、 100 x2 s.t. x1 + x2 300 2x1 + x2 400 x2 250 x1 ,x2 ,x3 ,x4 ,x5 0,现在考虑若三种原料都用于转让，试问：三种原料各如何收费才能即保证本厂的利益，有能最有竞争力？ 设 y1 ，y2 ，y3 分别为每设备工时（或原料）每单位的收取费用，则有,Min f = 300y1+ 400y2 + 250y3 s.t.y1+2y2 50（不少于甲产品的利润） y1+ y2+y3 100（不少于乙产品的利润） y1,y2 ,y3 0,Min f = 300y1+ 400y2 + 250y3 s.t. y1+2y2 50 y1+ y2+ y3 100

3、 y1, y2 , y3 0,Max z = 50 x1 + 100 x2 s.t. x1 + x2 300 2x1 + x2 400 x2 250 x1 , x2 0,对偶问题 租赁者模型,原问题 管理者模型,一对互为对偶的模型,对偶问题的定义： （对称形式）,（LP ） max Z=c1 x1 + c2 x2 + . + cn xn s.t. a11x1 + a12 x2 + . + a1nxn b1 . . . . . . am1x1 + am2x2 + .+ amn xn bm x1 , x2 , . , xn 0 （DP） min W=b1 y1+ b2 y2+ . + bm ym

4、s.t. a11y1+ a21 y2+ . + am1 ym c1 . . . . . . a1ny1+ a2n y2+ . + amnym cn y1 , y2 , . , ym 0,(LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 则（DP）称为（LP）的对称形式对偶问题,设：,例32 写出下面线性规划的对偶规划模型,解：按照对称形式的对偶关系，其对偶模型为,2. 如何将一般问题转化为对偶问题,原问题和对偶问题有很多内在联系，它们之间存在严格的对应关系： 目标函数类型之间的对应关系； 目标函数系数与右边项的对

5、应关系； 约束系数矩阵之间的对应关系； 约束类型与变量类型之间的对应关系；,非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面 的对应关系直接给出其对偶规划。 （1）将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；,（3）若原规划的某个变量的值没有非负限 制，则在对偶问题中与此变量对应的那个 约束为等式。 下面对关系（2）做一说明。对于关系（3） 可以给出类似的解释。 设原规划中第1

6、个约束为等式： a11x1 +a12+ a1nxn = b1 那么，这个等式与下面两个不等式等价,这样，原规划模型可以写成,此时已转化为对称形式，直接写出对偶规划,令 y1 = y1 - y1，于是有,一般情况，我们总结如下：,例 3. 3 写出下列问题的对偶问题：,解 ：先将约束条件变形为“”形式,再根据非对称形式的对应关系，直接写出对偶规划,3.2 线性规划的对偶理论,考虑下面一对对偶问题： P max z = CT X D min w = bTY s.t. AX b s.t. ATY c X 0 Y 0,A为mn阶矩阵，A的秩为m。引入松弛变量Xs，得到原规划（P）的标准型为（P1）,其

7、中01和I分别为m维的零向量和m维的单位矩阵。,记,则上面的标准型可记为（P2）,设B为一可行基，并记,得到模型（P2）的另一表示形式,对偶定理,定理 3.1 (对称性定理) 对偶问题的对偶就是原问题。 定理 3.2（弱对偶定理）设 X, Y分别是 P 和 D 的可行解，则 CTX bTY。 证：由 P 和 D 的约束条件 AXb, ATYC, X0, y0 可直接推得 CTX YT AX YTb =bTY，证毕。,推论1 （对偶定理）若X*, Y*分别是（P）和（D）的可行解，则它们分别是（P）和（D）的最优解的充要条件是： CTX*= bTY*。 证 由定理3.1可知，对于规划（D）的任一

8、可行解Y，都有bTY CTX*= bTY* ，因此Y*是规划（D）的最优解，类似地可证明， X*是规划（P）的最优解。,推论2 若规划（P）有可行解，则（P）有最优解的充分必要条件是规划（D）有可行解。 推论3 若规划（D）有可行解，则（D）有最优解的充分必要条件是规划（P）有可行解。,例3.4 试用对偶理论判断下面线性规划是否有最优解,解: 此规划存在可行解 ，其对偶规划为,显然，对偶规划没有可行解，因此，原规划没有最优解。,例3.5 用对偶理论判断下面线性规划是否存在最优解,解: 此规划存在可行解，其对偶规划为,对偶规划也存在可行解,因此原规划存在最优解。,定理 3.3 若原规划（P）有最

9、优解，则对偶规划（D）也有最优解，反之亦然。并且两者的目标函数值相等。,证： 考虑原规划（P）的标准型（P2）,设B为模型（P2）的最优基，现在证明对偶规划（D）也有最优解。由单纯形法可知，此时,为对偶规划（D）的可行解。另一方面有,因此,其中,为原规划的最优解。由推论1可知，为对偶规划（D）的最优解。,类似地，可以证明，若规划（D）有最优解，则规划（P）也有最优解。,从定理3.2的证明可以看到，对偶规划（D）的最优解为：,例3.6 求解下面线性规划问题，并根据最优单纯形表中的检验数，给出其对偶问题的最优解。,解 引入松弛变量、将模型化为标准型，经求解后得到其最优单纯形表,对偶规划的最优解为

10、:,3 .3 对偶解的经济解释,1. 对偶解与影子价格 2. 互补松弛定理,1. 对偶解与影子价格,对偶解的数学意义：当得到最优解后，目标函数值 z =CTX* = bT Y*,z = y1b1+y2b2+.+ymbm 将b1,b2,bm看作变量，对右边项求偏导 z bi = yi 对偶解的意义是：当取得最优解的前提下，右边资源项 bi 的单位改变量（其他参数不变）所引起目标函数 z 的改变量。,如果把线性规划约束看成广义资源约束，右边项代表资源的可用量，其经济含义是资源对经济目标的边际贡献。 目标函数值通常用价值量衡量，对偶解也具有价值内涵，被称为影子价格。 影子价格是对偶解十分形象的名称，

11、它既表明对偶解是对资源的一种客观估价，又表明它是虚拟而不是真实的价格。,对偶解的经济意义：,影子价格有以下几个特点： （1）系统资源的最优估价 影子价格是综合考虑系统内所有因素和相互之间影响之后对资源在系统内的真实价值的估价。只有系统达到最优状态时才可能赋予该资源这种价值。因此，也有人称之为最优计划价格。,（2） 影子价格与系统价值取向和状态有关 影子价格 (y = CBT B-1) 的取值与系统的价值取向有关 (反映在CB上)； 影子价格受系统状态影响 (反映在B-1 上) ; 系统内部资源数量和价格的任何变化都会引起影子价格的变化，从这种意义上讲，它是一种动态的价格体系 。,（3） 影子价

12、格是一种边际值 它与经济学中边际成本的概念相同，在管理中有十分重要的应有价值，管理者可以根据资源在本企业内影子价格的大小决定企业的经营策略。,（4）反映资源在系统内的稀缺程度 如果资源在系统内供大于求，其影子价格为零。增加该资源的供应不会给系统目标带来任何变化。 如果是稀缺资源，其影子价格大于零价格越高，资源的稀缺程度越高。,例: 某企业生产 A , B 两种产品。A 产品需消耗 2个单位的原料和 1 小时人工；B 产品需消耗 3 个单位的原料和 2 小时人工。A 产品售价 23 元，B 产品售价 40 元。该企业每天可用于生产的原料为 25 个单位和 15 小时人工。每单位原料的采购成本为

13、5 元，每小时人工的工资为 10 元。问该企业如何组织生产才能使销售利润最大。,成本数据不直接反映在模型中。 max z = 3x1 + 5x2 s.t. 2x1 + 3x2 25 x1 + 2x2 15 x1 0 , x2 0 最优解： x = (5 , 5)T ，z = 40， 对偶解：y = (1 , 1) 。,构模方法一,构模方法二,成本数据直接反映在模型中 max z = 23x1 + 40 x2 - 5x3 - 10 x4 s.t. 2x1 + 3x2 - x3 0 x1 + 2x2 - x4 0 x3 25 x4 15 x10 , x20 , x30 , x4 0 最优解： x

14、= (5 , 5 , 25 , 15) , z = 40, 对偶解：y = ( 6 , 11 , 1 , 1 ),计算影子价格时要注意资源成本是如何反映在目标函数中的, 若资源成本显性地反映在目标中 影子价格 = 对偶解 若资源成本隐性地反映在目标中 影子价格 = 对偶解 + 资源成本,按以下原则考虑经营策略： 影子价格高于市场价格（或0）表明资源有获利能力，购入该资源。 影子价格低于市场价格（或0）表明该资源无获利能力，出让该资源。 影子价格等于市场价格（或=0）表明该资源处于平衡状态，既不用买入, 也不必卖出。,2. 互补松弛定理,互补松弛定理(又称松紧定理)描述了线性规划达到最优时，原问

15、题(或对偶问题)变量取值和对偶问题(或原问题)约束松紧之间的对应关系。,定理3.4（互补松弛定理）如果 X, Y分别是 P 和 D 的可行解, 它们是 P 和 D 的最优解的充要条件是： (C - ATY)T X = 0 (b - AX)T Y= 0 互补松弛定理中还可等价表示为： yi(bi - ai x) = 0 i=1 , 2 , . , m (cjypj )xj = 0 j=1 , 2 , . , n,互补松弛定理证明了最优线性规划的下列对应关系： 原问题约束为紧 对偶变量 0； 原问题约束为松 对偶变量=0； 对偶约束为紧 原问题变量 0； 对偶约束为松 原问题变量=0； 原问题变量

16、0 对偶约束为紧约束； 原问题变量=0 对偶约束可紧可松。,互补松弛性的经济意义,若资源的影子价格大于零(yi0)，必为紧缺资源，约束为紧约束(bi-aix=0)；否则，若该资源仍有剩余，系统还未达到最优状态，利用该资源可使目标进一步得到改善。 若资源有剩余，约束为松(bi-aix0)，其对偶解必为零(yi=0)，否则，若对偶解大于零，增加该资源的使用还可使目标得到改善。,互补松弛性的经济意义,在最优状态下，当变量的检验数小于零时（cj-ypj0），说明生产该产品的边际贡献是负的，在最优计划中不该生产它，因此，该变量必为零（xj=0）。 当变量大于零时（xj0），该变量的检验数（边际贡献）必为

17、零（cj-ypj=0），否则，无论边际贡献取正值或负值，相应地增加或降低该产品的产量都可使目标得到改善。,例.7 已知线性规划 min z = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 s.t. x1 + x2 + 2x3 + x4 + 3x5 4 2x1 - x2 + 3x3 + x4 + x5 3 x1 , x2 , x3 , x4 , x5 0 其对偶问题的最优解为：y1* = 0.8, y2* = 0.6。试用对偶理论求出它的原问题的最优解,对偶问题： Max w= 4y1 + 3y2 s.t. y1 + 2y2 2 y1 - y2 3 2y1+ 3y2 5 y1+ y2

18、 2 3y1+ y2 3 y1 0, y2 0,代入y1*=0.8, y2*=0.6,松约束 x2 = 0,紧约束 x1 0,松约束 x3 = 0,松约束 x4 = 0,紧约束 x5 0,原问题的约束为紧约束, 故有: x1 + 3x5 = 4 2x1 + x5 = 3 解得：x1* = 1， x5* = 1 原问题的最优解为： X = (1 , 0 , 0 , 0 , 1) , z* = 5,3.4 对偶单纯形方法,单纯形方法始终保持原问题的解可行，检验数不一定小于等于零（即对偶解不可行）。一旦检验数小于等于零（即对偶解变为可行解），则问题达到最优。,对偶单纯形方法的基本思想：从对偶规划的一

19、个可行基出发，即保证满足 = C - CBB-1A 0；一旦原问题可行，即：XB = B-1b 0，则找到最优解。,最优检验存在以下几种情况： (1)如果B-1b0，该问题已最优，停止； (2) 如果B-1b存在至少一个负分量, 且 i 0 , i = (i1, i2, . in)，ij =(B-1pj)i ，由线性规划的典则方程： 再由条件(B-1b)i 0和 i 0，(xB)i 不可能变为正，因此原问题无可行解。,(3) 如果B-1b中存在至少一个负分量，且每个负分量对应的行向量i存在小于零的元素，此时原问题解不可行，仍需继续迭代。保持对偶可行的条件可表示为：,因此可得入基变量的检验条件为

20、：,对偶单纯形算法：,1.找初始对偶可行解； 2.最优检验：(B-1b)r=min(B-1b)i iJB 如果(B-1b)r0，已找到最优解，停止。 如果(B-1b)r0 且 r0, 问题不可行, 停止计算。 否则选变量 xr 出基，转到3。,3.确定入基变量，令j=cj-cBB-1pj, 计算： 令 xk 入基。 4.以 rk 为转轴进行旋转迭代得到一个新的单纯形表，转到2。,原始与对偶单纯形法的对比,例3.8 用对偶单纯形方法求解：,解: （1）引入松弛变量 x3 , x4 , x5 化为标准形，并在约束等式两侧同乘-1，得到,取x3 , x4 , x5为基变量，此式即为典式形式，并且检验

21、数皆非正，因此可构初始对偶单纯形表,例3.9 用对偶单纯形法求解下面线性规划,解: 构造对偶单纯形表进行迭代，,从最后的表可以看到，B-1b列元素中有-20，并且，-2所在行各元素皆非负，因此，原规划没有可行解。,对偶单纯形法适合于解如下形式的线性规划问题:,在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便 。,2.5 灵敏度分析,使用LP求解管理问题时，管理者需要了解当环境和数据发生变化时，线性规划得出的结论还是否有效； 资源供应发生变化会有什么影响? 成本变化后利润会发生什么变化? 如果模型使用的数

22、据不精确会有什么影响，数据允许在什么范围内变化?,灵敏度分析主要内容,1. 目标函数系数变化的灵敏度分析 2. 右边项变化的灵敏度分析 3.约束条件中的系数变化的灵敏度分析 4. 增加新变量的灵敏度分析 5. 增加约束条件的灵敏度分析 6.灵敏度分析的几何意义,1. 目标函数系数变化的灵敏度分析,假定只有一个 cj 变化，假定 cj 从 cj 变到cj*=cj+ cj，当 cj在什么范围内变化时，不会影响最优解。,(1) 分析什么？,(2) 怎么分析？,最优解不变的充要条件是：,假定只有一个cj变化，分两种情况讨论： 1）cj 是非基变量的系数 设cj 变化量为cj，若希望cj 变化后最优基不

23、变，检验数应满足以下条件： j = (cj + cj ) - cBB-1pj = cj - cBB-1pj + cj = j + cj 0 得到:cj -j,由cj -j 及最优条件j 0，cj只在增加方向受限制，在下降方向不受限制： cj增加时，变量对目标函数的贡献增加，增加足够大时，检验数会大于零，使该变量入基而引起最优基改变; cj下降时，变量对目标函数的贡献下降，检验数变得更负，最优基不会变化。 非基变量目标系数允许变化范围为: - cj - j jJN 满足以上条件，解和目标值不会改变。,2) cj 是基变量的系数 基变量的 cj 变化会引起cBB-1变化, 从而引起所有检验数变化。

24、若要使所有检验数满足最优条件, 有以下条件: k = ck - (cB + cB)B-1pk 0 kJN 假定cj 是当前基的第 r 个基变量，即： cj = (cB)r cB = (0,., (cB)r,., 0) = (0,., cj,., 0),从而有： k = ck - (cB + cB)B-1pk = ck- cBB-1pk - (0,.,(cB)r,.,0)B-1pk = k - cj (B-1pk)r 0 kJN 令rk = (B-1pk)r 得： k = k - cjrk 0 kJN,在上述变化范围内： 目标函数值的改变量： z = cj xj 对偶解的改变量： y = cBB

25、-1 原问题的最优基和最优解不会改变。,解不等式组 k = k - cjrk 0 kJN 得,cj 的变化范围： maxk -, k /rkrk0 cj mink +, k /rkrk0,例: 对例1.1的目标函数系数进行敏感性分析。 解：家具厂问题的最优单纯形表：,c1: x1在基的第二行(r=2), 非基变量下标k=3和4, 23= -1/2, 24=3/2,可得: max -, -15/1.5 c1 min+, -5/(-0.5) -10 c1 10,c2 ：x2 在基的第一行，r1，131， 14-2，可得： max-,(-5)/(1)c2min+,(-15)/(-2) -5 c2 7

26、.5,2. 右边项发生变化的灵敏度分析,(1) 分析什么？,假定只有一个 br 变化，假定 br 从 br 变到br*=br+ br，当 br在什么范围内变化时，不会影响最优基。（不改变产品种类，只调整数量）,(2) 怎么分析？,最优基不变的充要条件是：,为了保持最优基不变，应使 ，即,解不等式组，得,例: 对例1.1的右边项进行敏感性分析。,1)对b1进行分析：i=1对应基的第一列，11=13=1，21= 23 = -0.5 max-,-20/1 b1 min+, -15/(-0.5) 20 b1 30,2)对 b2 进行分析：i = 2 对应基的第二列，12 = 14 = -2，22 =

27、24 = 1.5 max-, -15/1.5 b2 min+, -20/(-2) 10 b2 10,灵敏度分析一览表,3、约束条件中的系数变化,假设只有一个 aij 变化。其他数据不变，并且只讨论 aij 为非基变量的系数的情况。因此， aij的变化只影响一个检验数 。当 aij在什么范围内变化时，不会影响最优解,(1) 分析什么？,(2) 怎么分析？,最优解不变的充要条件是：,其中Y为对偶最优解，yi为Y的第i个分量。,为使最优解不变，要使 ，即,4. 增加新变量的灵敏度分析,在管理中经常遇到的问题：已知一种新产品的技术经济指标，在原有最优生产计划的基础上，怎样最方便地决定该产品是否值得投入

28、生产，可在原线性规划中引入新的变量 ； 无论增加什么样的新变量，新问题的目标函数只能向好的方向变化。,例: 家具厂设计了一种新柜子，市场售价为100元，生产一个柜子需9个木工工时，3.5个油漆工工时。问柜子是否应投产？ 解：令 x5 代表柜子产量，新模型为： max z = 50 x1+30 x2 + 100 x5 s.t. 4x1 + 3x2+ x3 + 9 x5 = 120 2x1 + x2 + x4+3.5x5 = 50 x1 , x2 , x3 , x4 , x5 0,B-1p5 =,新变量及其系数放在原单纯形表的最后一列，新向量需经过左乘基的逆矩阵后才能写入最优单纯形表：,计算新产品

29、影子(机会)成本：由y1= 5，y2= 15，影子成本 y pj 为 ： 95 + 3.515 = 97.5 100,5. 增加一个新约束的分析,当出现新的资源限制时，模型要加入新约束，可在原最优解的基础上进行分析： 最优解满足新约束，最优解不变； 最优解不满足新约束，应继续寻找新的最优解； 无论加入什么类型约束，目标函数值都不会改善。,例: 如果家具厂每月可用的木材只有10立方米，生产一个桌子需木材0.4立方米，椅子需0.3立方米。问应该如何生产？ 解：加入新约束为： 4x1 + 3x2 100， 引入松弛变量 x5 并令其入基，加入原最优表后得到的不是标准单纯形表，需要通过矩阵的初等变换将

30、其化为标准表，再进一步用对偶单纯形法求解。,例: 设某厂使用甲、乙、丙三种原料生产A、B、C三种产品。每种产品的原料消耗和销售价格见下表： 已求得最优单纯形表见下表,该厂需要做以下敏感性分析： 1. 至少生产A产品 30件，会有什么变化？,2. 要留下300公斤原料丙，对生产会有什么样的影响？ 3. C 产品已滞销，不能再生产，会有什么变化？ 4. 新产品 D 消耗原料甲3公斤、乙2公斤、丙1公斤，问如何定价工厂才能获利? 如果单价定为55元，是否应进行生产？,1.强制生产30件A x1 必须等于30 目标值下降; 下降程度可用 x1 的检验数进行计算： z= x1检验数变化数量= -1530 = -450 x2= 400 -130 = 370 生产B产品370件 x3=50 - 1/330 = 40 生产C产品40件 x4=350 - 5/330=300 甲剩余300公斤 新方案生产30件A，370件B，40件C，甲原料剩余300公斤。,2.丙原料剩余300 资源减少300，目标改变量=影子价格资源改变数量： z = yb = 25(-300) = -7500。 还