第二章 对偶问题与灵敏度分析w重点与难点： 1、对偶问题的定义，对偶定理，对偶问题最优解的经济含义，由最优单纯形表求对偶问题最优解； 2、对偶单纯形法的特点，对偶单纯形法求解； 3、灵敏度分析：价值系数cj发生变化，右端常数bi发生变化，增加一个变量，增加一个约束，A中对应非基变量的一列元素发生变化OR11运筹学——对偶问题与灵敏度分析课件 第二章 对偶问题与灵敏度分析w要求： 了解LP对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析 OR12运筹学——对偶问题与灵敏度分析课件 2.1 对偶问题w2.1.1 对偶问题的提出 回顾例题1： 现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的（资源的）价格底线是多少？产品A产品B资源限制劳动力设备原材料 9 4 3 4 5 10 360 200 300单位利润 70 120OR13运筹学——对偶问题与灵敏度分析课件 对偶模型w设每个工时收费Y1元，每设备台时费用Y2元，每单位原材料收费Y3元。
出租收入不低于生产收入： 9y1+4y2+3y3 ≥70 4y1+5y2+10y3 ≥120目标：ω=360y1+200y2+300y3出租收入越多越好？还是至少不低于某数？OR14运筹学——对偶问题与灵敏度分析课件 原问题与对偶问题之比较原问题： 对偶问题：maxZ=70X1+120X2 minω=360y1+200y2+300y3 9X1+4X2≤360 9y1+4y2+3y3 ≥70 4X1+5X2 ≤200 4y1+5y2+10y3 ≥120 3X1+10X2 ≤300 y1 ≥0, y2 ≥0, y3 ≥0X1≥0 X2≥0OR15运筹学——对偶问题与灵敏度分析课件 2.1.2对偶规则原问题一般模型： 对偶问题一般模型：maxZ=CX min ω=Yb AX ≤b YA ≥C X ≥0 Y ≥0OR16运筹学——对偶问题与灵敏度分析课件 对偶规则P57.原问题（或对偶问题）对偶问题（或原问题）目标函数maxz目标函数min⍵n个n个变量约束条件≥ 0≥≤0≤无约束＝约束条件变量≤≥m个m个≥ 0≤0＝无约束约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项OR17运筹学——对偶问题与灵敏度分析课件 例题2：写出下列原问题的对偶问题OR18运筹学——对偶问题与灵敏度分析课件 例题3：写出以下模型的对偶问题w例题3 max ω=7y1+4y2-2y3minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3 2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2 x1+ 2x3 -x4 ≤ 4 -4y1+ 2y2 ≤-6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0 x1，x2，x3 ≥0; 3y1 +y3=1 x4 ≤ 0;x5无限制 y1 ≥ 0y2 ≤ 0y3 无约束 OR19运筹学——对偶问题与灵敏度分析课件 例题4：写出以下模型的对偶问题OR110运筹学——对偶问题与灵敏度分析课件 例4的解法OR111运筹学——对偶问题与灵敏度分析课件 2.1.3对偶问题的基本性质w1.对称性：对偶问题的对偶问题是原问题。
w2.弱对偶性：若 是最大化原问题的可行解， 是对偶问题的可行解，则存 w3.无界性：若原问题为无界解，则对偶问题无可行解注：该性质的逆不存在当原问题无可行解时，其对偶问题可能为无界解，也可能无可行解w4.最优解定理：若两互为对偶的问题均有可行解，且可行解对应的目标函数值相等，则该可行解分别为他们的最优解OR112运筹学——对偶问题与灵敏度分析课件 性质3的应用P60w已知LP问题：试用对偶理论证明上述LP问题无最优解OR113运筹学——对偶问题与灵敏度分析课件 w5.对偶定理：若原问题有最优解，则对偶问题也有最优解，且目标函数值相等若原问题最优基为B，则其对偶问题最优解Y*=CBB-1w6 .互补松弛性：在LP的最优解中，若对应某一约束条件的对偶变量值不为零，则该约束条件取严格等式；反之，若约束条件取严格等式，则其对应的对偶变量一定为零另一解释：在互为对偶的两个问题中，①若原问题的某个变量取正数，则对偶问题相应的约束条件必取“＝”式；②若原问题的某个约束条件取不等式，则对偶问题相应的变量为零OR114运筹学——对偶问题与灵敏度分析课件 性质6的应用P60w已知线性规划问题：w已知其对偶问题的最优解为：w试用对偶理论找出原问题的最优解。
OR115运筹学——对偶问题与灵敏度分析课件 w7.设原问题是maxz=CX,AX+Xs=b; X, Xs≥0,其对偶问题是min⍵=Yb,YA-Ys=C, Y, Ys ≥0,则原问题单纯形表的检验数行对应其对偶问题的一个基解CBB-1 （符号相反），其对应关系如下：OR116运筹学——对偶问题与灵敏度分析课件 非基变量基变量XBXNXS0XSbBNICBCN0CBCN初始单纯形表XNXBXSI=B-1BB-1NB-1CBXBB-1bCBCN00CN-CBB-1N_-CBB-1互为对偶问题在单纯形表间关系：1、原问题的基解对应于对偶问题的检验数2、原问题的松弛变量对应对偶问题的决策变量3、原问题的基变量对应对偶问题的非基变量OR117运筹学——对偶问题与灵敏度分析课件 w某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？回顾例题1： 现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的（资源的）价格底线是多少？产品A产品B资源限制劳动力设备原材料 9 4 3 4 5 10 360 200 300单位利润 70 120OR118运筹学——对偶问题与灵敏度分析课件 CjC1 C2 … CnCBXBbX1 X2 X3 X4 X5θj 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030σj0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.130.7620100σj3600 34 0 0 0 -12701200X3X1X2842024 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16σj4280 0 0 0 -13.6 -5.2y1y2y3OR119运筹学——对偶问题与灵敏度分析课件 2.1.4对偶最优解的经济解释—影子价格Z*= CBB-1b =Y* b= b1y1*+ b2y2* +…+ bm ym* (*) Z= Z(b) b为资源为资源求偏导：求偏导： Z* b=CBB-1= Y*=(y1* ,y2*, …ym* ) 对偶解对偶解yi* 的经济意义的经济意义：其它条件不变的情：其它条件不变的情况下，第况下，第i i种资源改变一个单位所引起的目标种资源改变一个单位所引起的目标函数最优解的变化。
函数最优解的变化OR120运筹学——对偶问题与灵敏度分析课件 另一种直观的解释W=yb=(y1 … ym )b1bm…= b1 y1 + b2 y2 + … + bm ymbi ：： 第第 i 种资源的数量种资源的数量yi ：对偶解：对偶解bi增加增加 bi , ,其它资源数量不变时其它资源数量不变时, ,目标函数目标函数的增量的增量 Z=bi yiyi ：反映：反映bi 的边际效益的边际效益( (边际成本边际成本) )OR121运筹学——对偶问题与灵敏度分析课件 影子价格的应用情况情况① ① 某资源对偶解某资源对偶解>0>0，该资源有利可图，，该资源有利可图，可增加此种资源量；某资源对偶解为可增加此种资源量；某资源对偶解为0 0，，则不增加此种资源量则不增加此种资源量情况情况② ② 直接用影子价格与市场价格相比较，直接用影子价格与市场价格相比较，进行决策，决定是否买入该资源进行决策，决定是否买入该资源即：即：影子价格所含有的信息：影子价格所含有的信息：1 1、资源紧缺、资源紧缺状况；状况；2 2、确定资源转让基价；、确定资源转让基价；3 3、取得紧、取得紧缺资源的代价。
缺资源的代价OR122运筹学——对偶问题与灵敏度分析课件 对偶单纯形法w设有问题maxZ=CX ，w AX ＝b ，w X ≥0 w又设B是其一个基，当非基变量都为0时，可以得到XB=B-1b若在B-1b中至少有一个负分量，设第i个为负分量，并且在单纯形表的检验数行中的检验数都为非正，这种情况就可以用对偶单纯形法来进行求解OR123运筹学——对偶问题与灵敏度分析课件 对偶单纯形法的计算步骤P62w（1）根据LP问题，列出初始单纯形表检查b列的数字，若都为非负，检验数都为非正，则已得到最优解，停止计算若检查b列的数字时，至少还有一个负分量，检验数保持非正，则进行以下计算w（2）确定换出变量：将B-1b中最小的负分量所对应的变量确定为换出变量w（3）确定换入变量：检查换出变量所在行（第L行）的各系数aLj若所有的aLj ≥0，则无可行解 ，停止计算若存在aLj <0，则计算 ，将其最小值所对应的变量作为换入变量w（4）进行迭代计算w重复1－4步，直至得到最优解为止。
OR124运筹学——对偶问题与灵敏度分析课件 对偶单纯形法举例w利用对偶单纯形法求解以下线性规划问题：OR125运筹学——对偶问题与灵敏度分析课件 cjCBXBbx1x2x3x4x5-1-3000-2-3-1-1-2-2100010解法001-3-4-1x3x4x5000-1-3000cj-zj1/33/2x3x1x50101/32/3-4/3100-2/3-1/3-1/3001cj-zj-1/34/31/30-7/30-1/301/20-10x4x1x5½3/21/2010-1/2½-3/2-3/2-1/2-1/21000010-10cj-zj0-5/2-1/200-3/2此时所有的B-1b均≥0 ，且所有的cj-zj均≤0，此时已得到最优解为：X*=(3/2,0,0,1/2,1/2)TZ*=-3/2OR126运筹学——对偶问题与灵敏度分析课件 总结：对偶单纯形法与单纯形法的比较单纯形法对偶单纯形法保持B-1b≥0所有的cj-zj≤0最优解时要求所有的cj-zj≤0B-1b≥0OR127运筹学——对偶问题与灵敏度分析课件 对偶单纯形法的应用时机w要求最大化时，在单纯形表中：如果检验数均非正，而 列中有负值，此时用对偶单纯形法求解。
若所有 ，中有正值，则用单纯形法求解；若 列中有负值，且 中有正值，则必须引入人工变量，建立新的单纯形表，重新计算B-1bB-1b≥0cj-zjB-1bcj-zjOR128运筹学——对偶问题与灵敏度分析课件 对偶单纯形法的优点P64w（1）初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以直接计算w（2）当变量多于约束条件，对这样的LP问题，用对偶单纯形法计算可以减少计算工作量因此，对变量较少，而约束条件很多的LP问题，可以先将它变换成对偶问题，然后用对偶单纯形法求解w（3）在灵敏度分析中，有时需要用对偶单纯形法，这样可使问题的处理简化OR129运筹学——对偶问题与灵敏度分析课件 2.2灵敏度分析（考研时常考的知识点）灵敏度分析通常有两类问题：①是当C,A,b中某一部分数据发生给定的变化时，讨论最优解与最优值怎么变化；②是研究C,A,b中数据在多大范围内波动时，使原有最优基仍为最优基，同时讨论此时最优解如何变动？灵敏度分析的两把尺子： σj =Cj-CBB-1pj≤ 0； XB= B-1b ≥0OR130运筹学——对偶问题与灵敏度分析课件 2.2.1右端项bi变化的灵敏度分析bi变化到什么程度可以保持最优基不变？用尺度xB= B-1b ≥0。
问题：为什么不用尺度σj =Cj-CBB-1pj≤ 0？OR131运筹学——对偶问题与灵敏度分析课件 例题：求以下模型中第二个约束条件右端项b2的变化范围maxZ=70X1+120X29X1+4X2≤3604X1+5X2 ≤200 3X1+10X2 ≤300 X1≥0 X2≥0OR132运筹学——对偶问题与灵敏度分析课件 Cj70 120 0 0 0CBXBbX1 X2 X3 X4 X5θi 0 0 0X3X4X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030σj0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.130.7620100σj3600 34 0 0 0 -12701200X3X1X2842024 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16σj4280 0 0 0 -13.6 -5.2OR133运筹学——对偶问题与灵敏度分析课件 w解：从最优单纯形表得出：XB=(20,24,84)Tw最优基为：w注意：应为初始数据。
为什么？w还可以从单纯形表中找出B-1.OR134运筹学——对偶问题与灵敏度分析课件 w设b2由200变为200＋∆ b2，则b由w w由此得到迭代后的单纯形表： cj70120000CBXBbx1x2x3x4x5θi010001100-3.120.4-0.121.16-0.20.1684-3.12 ∆b220+0.4 ∆ b224-0,12 ∆ b2x3x1x2070120zjσj4280+13.6 ∆ b270120013.65.2000-13.6-5.2OR135运筹学——对偶问题与灵敏度分析课件 w上述解是最优解，必须是可行解：w即：w解得：－50 ≤ ∆ b2 ≤ 26.9w可知右端项系数b2的变化范围是: （200－50） ～（200＋26.9)OR136运筹学——对偶问题与灵敏度分析课件 w在此范围内σj ≤0， B-1b ≥0，最优解仍有效，即最优解的基变量不变，最优解为：w最优值为：Z*=4280+13.6 ∆ b2 OR137运筹学——对偶问题与灵敏度分析课件 2.2.2目标函数中价值系数cj的灵敏度分析w分cj是非基变量的系数还是基变量的系数两种情况来讨论。
w①若cj是非基变量xj的系数，此时，当cj变化∆ cj后，要保证最终表中这个检验数仍小于或等于零即可②若cj是基变量xj的系数，则引起的变化较大OR138运筹学——对偶问题与灵敏度分析课件 w例题：在模型例1中，求基变量x2的系数变化范围w解：本例的最优单纯形表如下：070120cjCBXBbx3x1x2842024x1x2x3x4x5θi70120000010001100-3.120.4-0.121.16-0.20.16σj4280000-13.6 -5.2OR139运筹学——对偶问题与灵敏度分析课件 w基变量系数c2由120变为120＋ ∆ c2后，可以得到迭代后的单纯形表cjCBXBbx3x1x2842024x1x2x3x4x5θi70120＋ ∆ c2000010001100-3.120.4-0.121.16-0.20.16σj4280＋24∆ c2000-13.6 +0.12∆ c2-5.2-0.16 ∆ c2070120+ ∆ c2OR140运筹学——对偶问题与灵敏度分析课件 w要保持最优解，必须使σj ≤0， 即：w－13.6+0.12 ∆ c2 ≤0w -5.2-0.16 ∆ c2 ≤0w解得－32.5 ≤ ∆ c2 ≤113.3w由此可知， c2 的变化范围为：w（120－32.5)~(120+113.3)，即87.5 ≤ c2 ≤233.3。
OR141运筹学——对偶问题与灵敏度分析课件 2.2.3技术系数aij的灵敏度分析一般地，发生变化的系数大多是非基变量的系数它的改变不会影响到现行最优解的可行性，如果要有影响的话，那将是对现行解是否还是保持最优的问题分两种情况进行讨论(1)非基列向量的改变；（2）某一元素的改变OR142运筹学——对偶问题与灵敏度分析课件 例：讨论线性规划w的系数列向量 的情况OR143运筹学——对偶问题与灵敏度分析课件 w解：首先利用单纯形法得出初始单纯形表及最优单纯形表如下CBXBbx1x2x3x4x52-1-10000x4x5641-112101001σj 2-1-10020x1x56101013111101σj0-3-1-20OR144运筹学——对偶问题与灵敏度分析课件 w由于 .所以CBXBbx1x2x3x4x52-1-10000x4x5641-112101001σj 2-1-10020x1x56101013111101σj0-3-1-2027-5由此可知，当前解仍为最优解OR145运筹学——对偶问题与灵敏度分析课件 本章知识点总结1、建立线性规划数学模型2、非标准型线性规划模型转变为标准型。
3、线性规划问题的解法：图解法，单纯形法4、单纯形法的进一步讨论：大M法，两阶段法5、线性规划问题的对偶问题，对偶规则对偶最优解的经济解释，对偶问题的基本性质6、对偶单纯形法7、灵敏度分析OR146运筹学——对偶问题与灵敏度分析课件 。