运筹学对偶理论与灵敏度分析.ppt

《运筹学对偶理论与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学对偶理论与灵敏度分析.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 线性规划的对偶理论与灵敏度分析一、对偶问题的提出一、对偶问题的提出在同一企业的资源状况和生产条件下产生的，且是同在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相一个问题从不同角度考虑所产生的，因此两者密切相关关-两个两个LP问题是互为对偶问题是互为对偶即任何一个求即任何一个求maxZ的的LP都有一个求都有一个求minW的的LP。“原问题原问题”-“LP”，“对偶问题对偶问题”-“DP”。1、原问题与对偶问题、原问题与对偶问题-对称形式对称形式(1)原问题中的约束条件个数等于它的对偶问题中的变量数；原问题中的约束条件个数等于它的对偶问题中的变量

2、数；(2)原问题中目标函数的系数是其对偶问题中约束条件的右端项；原问题中目标函数的系数是其对偶问题中约束条件的右端项；(3)约束条件在原问题中为约束条件在原问题中为“”，则在其对偶问题中为，则在其对偶问题中为“”；(4)目标函数在原问题中为求最大值，在其对偶问题中则为求最小值。目标函数在原问题中为求最大值，在其对偶问题中则为求最小值。二、对偶理论例例2.2 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题解：按照上述规则，该问题的对偶线性规划为解：按照上述规则，该问题的对偶线性规划为:非对称形式非对称形式-例如：当原问题约束条件为等式例如：当原问题约束条件为等式对偶问题对偶问题:特

3、点：对偶变量符号不限特点：对偶变量符号不限 对于一般情况下线性规划问题如何写出对偶问题。对于等对于一般情况下线性规划问题如何写出对偶问题。对于等式约束可以把它写成两个不等式约束，对于式约束可以把它写成两个不等式约束，对于“”的不等式，的不等式，可以两边同乘可以两边同乘“1”，再根据对称形式的对偶关系写出对偶问，再根据对称形式的对偶关系写出对偶问题，然后进行适当的整理，使式中出现的所有系数与原问题中题，然后进行适当的整理，使式中出现的所有系数与原问题中的系数相对应。的系数相对应。归纳归纳-表表2.2MaxMin约束条件数=m 变量个数=m 第i个约束条件“”“”“=”第i个变量00无限制 变量数

4、=n 约束条件数=n 第i个变量00无限制 第i个约束条件为“”为“”为“=”第i个约束条件的右端项目标函第i个变量的系数 目标函数第i个变量的系数第i个约束条件的右端项 表2.2例2.3 写出下述线性规划问题的对偶问题例2.4 写出下述线性规划问题的对偶问题2、对偶问题的基本定理对偶问题的基本定理 （1）（对称性）对偶问题的对偶是原问题。）（对称性）对偶问题的对偶是原问题。（2）（弱对偶定理）若）（弱对偶定理）若X(0)是原问题的可行解，是原问题的可行解，Y(0)是对偶问题的可行解，是对偶问题的可行解，则有则有C X(0)Y(0)b。(3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题

5、（原问题）无）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。可行解。（4）（最优性定理），若）（最优性定理），若X(0)、Y(0)分别是互为对偶问题的可行解，且分别是互为对偶问题的可行解，且C X(0)=Y(0)b，则，则X(0)、Y(0)分别是它们的最优解。分别是它们的最优解。（5）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。且它们的目标函数值相等。（6）（互补松驰性）若）（互补松驰性）若X*、Y*分别是原问题和对偶问题的可行解，则分别是原问题和对偶问题的可

6、行解，则X*、Y*是最优解的充要条件是：是最优解的充要条件是：Y*XS=0,YSX*=0(其中其中XS，YS分别是原问题和对偶问题的松驰变量向量分别是原问题和对偶问题的松驰变量向量)。证：设原问题是max Z=C X；AXb；X 0其对偶问题为min W=Y b；YA C；Y 0又因为可得对称变换，上式的对偶问题是max（-W）=-Y b；-YA -C，Y 0两边取负号，因min W max（-W），得到（1）（对称性）对偶问题的对偶是原问题。）（对称性）对偶问题的对偶是原问题。证：设原问题是 若若X(0)是原问题的可行解，是原问题的可行解，Y(0)是对偶问题的可行解，是对偶问题的可行解，则有

7、则有C X(0)Y(0)b。将 右乘上式，得到因为 是LD的可行解，所以满足对偶问题是是LD的可行解，将 左乘上式，得到是LP可行解，满足约束,即（2）（弱对偶定理）（弱对偶定理）注意：不存在逆。注意：不存在逆。当原问题（对偶问题）无可行解时，其对偶问题（原当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或无可行解。问题）或具有无界解或无可行解。若原问题（对偶问题）为无界解，若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。则其对偶问题（原问题）无可行解。证：由弱对偶性C X(0)Y(0)b，显然得。（3）（无界性）（无界性）证：若所以 是最优解。同样证明：对于LP

8、所有可行解X，存在可见 使目标函数取值最小的可行解，既最优解。因为 ，所以 根据性质2，LD的所有可行解Y都存在 若若X(0)、Y(0)分别是互为对偶问题的可行解，分别是互为对偶问题的可行解，且且C X(0)=Y(0)b，则，则X(0)、Y(0)分别是它们的最优解。分别是它们的最优解。（4）（最优性定理），）（最优性定理），若互为对偶问题之一有最优解，则若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。另一问题必有最优解，且它们的目标函数值相等。是原问题的最优解，对应基阵B必存在 即得到 ，其中若是对偶问题的可行解，它使因原问题的最优解是，使目标函数取值由此，得到 是对

9、偶问题的最优解。（5）（强对偶定理）（强对偶定理）从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一：原问题与对偶问题都有最优解，且CX=Yb；一个问题具有无界解，则它的对偶问题无可行解；两个问题均无可行解。若若X*、Y*分别是原问题和对偶问题的可行解，则分别是原问题和对偶问题的可行解，则X*、Y*是最优是最优解的充要条件是：解的充要条件是：Y*XS=0,YSX*=0(其中其中XS，YS分别是原问题和对偶问题的松驰变量向量分别是原问题和对偶问题的松驰变量向量)。证明：设原问题和对偶问题的标准型是 原问题 对偶问题（6）（互补松驰性）（互补松驰性）将原问题目标函数中的系数向量C用 代

10、替后，得到 必有又若 分别是原问题和对偶问题的最优解，则若 ；则 故 是最优解。将对偶问题的目标函数中的系数向量，用 代替后，得到松约束松约束:某一可行点（如某一可行点（如X*和和Y*）处的严格不等式约束（包）处的严格不等式约束（包 括对变量的非负约束）括对变量的非负约束）紧约束紧约束:严格等式约束严格等式约束 已知已知试通过求试通过求LD的最优解来求解的最优解来求解LP的最优解。的最优解。例例2.5化简为又由于又由于y1*=1，y2*=3 ,原问题的约束必为等式，即原问题的约束必为等式，即将代入约束条件，（将代入约束条件，（1），（），（2），（），（5）-紧约束紧约束 （3），（），（4）

11、-松约束。松约束。解：对偶问题为解：对偶问题为令原问题的最优解为令原问题的最优解为X*=（x1，x2，x3，x4，x5），则根据互补松弛条件，必有则根据互补松弛条件，必有x3=x4=0图解图解-Y*=（1，3），），W=11。无穷多解无穷多解令令x5=0,得到得到x1=1，x2=2，即即X*1=（1，2，0，0，0）Z=11。再令再令 x5=2/3，得到，得到x1=5/3，x2=0，即即X*2（5/3，0，0，0，2/3）Z=11。1、影子价格、影子价格-边际价格若LP的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量-第i个约束条件的影子价格设：设：B是问题是问

12、题LP的最优基，由前式可知，的最优基，由前式可知，Z*=CB B-1b=Y*b=y*1b1+y*2b2+y*ibi+y*mbm当当bi变为变为bi+1时（其余右端项不变，也不影响时（其余右端项不变，也不影响B），则目标函数），则目标函数最优值变为：最优值变为：Z*=y*1b1+y*2b2+y*i(bi+1)+y*mbm所以有所以有 Z*=Z*Z*=y*i 三、对偶问题的经济解释三、对偶问题的经济解释影子价格影子价格目标函数最优值对资源的一阶偏导数目标函数最优值对资源的一阶偏导数（问题中所有其它数据都保持不变）（问题中所有其它数据都保持不变）-Z*对对bi的变化率的变化率经济意义是：在其它条件不

13、变的情况下，单位资源经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。变化所引起的目标函数的最优值的变化。即对偶变量即对偶变量yi就是第就是第 i 个约束条件的影子价格。个约束条件的影子价格。Z*=y*1b1+y*2b2+y*ibi+y*mbm 问该公司如何安排生产才能使销售利润最大？表23生产消耗参数及产品售价甲甲产产品品乙乙产产品品每天可供量每天可供量资资源源单单位成本位成本A2325单单位位5（万元（万元/单单位）位）B1215单单位位10（万元（万元/单单位）位）产产品售价（万元）品售价（万元）2340模型一：决策变量：甲、乙两种产品的数量两种原材料A、B

14、的使用量 模型二：决策变量：甲、乙两种产品的数量 例2.6在最优决策下对资源的一种估价，没有最优决策就没有影子价在最优决策下对资源的一种估价，没有最优决策就没有影子价格，格，-又称又称“最优计划价格最优计划价格”，“预测价格预测价格”等。等。定量的反映了单位资源在最优生产方案中为总收益所做出的贡定量的反映了单位资源在最优生产方案中为总收益所做出的贡献，献，-可称为在最优方案中投入生产的机会成本。可称为在最优方案中投入生产的机会成本。若第若第i 种资源的单位市场价格为种资源的单位市场价格为mi当当yi mi时，企业愿意购进这种资源，单位纯利为时，企业愿意购进这种资源，单位纯利为yimi，则有，则

15、有利可图；利可图；yi 0，说明该资源已耗尽，成为短线资源。，说明该资源已耗尽，成为短线资源。影子价格影子价格=0，说明该资源有剩余，成为长线资源。，说明该资源有剩余，成为长线资源。（2）对市场资源的最优配置起着推进作用）对市场资源的最优配置起着推进作用即在配置资源时，对于影子价格大的企业，资源优即在配置资源时，对于影子价格大的企业，资源优先供给先供给（3）可以预测产品的价格）可以预测产品的价格产品的机会成本为产品的机会成本为CBB-1A-C，只有当产品价格定在，只有当产品价格定在机会成本之上，企业才有利可图。机会成本之上，企业才有利可图。2、影子价格的作用、影子价格的作用（4）可作为同类企业

16、经济效益评估指标之一。）可作为同类企业经济效益评估指标之一。对于资源影子价格越大的企业，资源的利用所带来对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。的收益就越大，经济效益就越好。通过以上讨论可知：通过以上讨论可知：只有某资源对偶解大于只有某资源对偶解大于0，该资源才有利可图，该资源才有利可图，可增加此种资源量；若某资源对偶解为可增加此种资源量；若某资源对偶解为0，则不增加，则不增加此种资源量。此种资源量。直接用影子价格与市场价格相比较，进行决策，直接用影子价格与市场价格相比较，进行决策，是否买入该资源。是否买入该资源。单纯形法单纯形法在保证在保证 的前提下，使的前

17、提下，使 迭代到迭代到对偶单纯形法对偶单纯形法:根据对偶问题的对称性，保持对偶可行下，经根据对偶问题的对称性，保持对偶可行下，经过迭代，逐步实现原问题可行，以求得最优解。过迭代，逐步实现原问题可行，以求得最优解。对偶单纯形是先保证现行解对应的对偶问题可行，即对偶单纯形是先保证现行解对应的对偶问题可行，即 ，然后从，然后从 迭代到迭代到 。1.单纯形法的重新解释设X*是最大化LP问题最优解的充要条件是第二节、对偶单纯形法第二节、对偶单纯形法（1）初始单纯形表。检查）初始单纯形表。检查b列，若都为非负，且检验数都为非正，列，若都为非负，且检验数都为非正，得到最优解，停算。若得到最优解，停算。若b列

18、至少还有一个负分量，检验数保持非列至少还有一个负分量，检验数保持非正，转（正，转（2）；）；（2）确定换出变量）确定换出变量 对应基变量为换出变量；对应基变量为换出变量；（3）确定换入变量）确定换入变量在单纯形表中检查所在的行的系数在单纯形表中检查所在的行的系数 ，若所若所有的有的 ，则无可行解，停止计算。若存在，则无可行解，停止计算。若存在 ，计算，计算按按规则，所对应的列变量的非基变量为换入变量；规则，所对应的列变量的非基变量为换入变量；（4）以）以 为主元素，按单纯形法进行换基迭代，得到新为主元素，按单纯形法进行换基迭代，得到新的单纯形表；的单纯形表；重复（重复（1）（）（4）的步骤进行

19、计算。）的步骤进行计算。对偶单纯形的计算步骤：对偶单纯形的计算步骤：例例2.7 用对偶单纯形法求解用对偶单纯形法求解表2.4cj-9-12-15000CBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001-z0-9-12-15000表2.4cj-9-12-15000CBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001-z0-9-12-15000CBxBbx1x2x3x4x5x60 x4-7.2-1.8-1.8010-0.20 x5-9.2-1

20、.8-2.8001-0.2-15x32.80.20.2100-0.2表2.5 -z42-6-9000-3cj-9-12-15000CBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14-15x315/71/140101/14-3/14表2.6 -z501/7-3/14000-45/14-33/14cj-9-12-15000CBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9表2.7 -z72000-1/3-3-7/3（1）初始解非可行解，

21、检验数都是负数时，）初始解非可行解，检验数都是负数时，-进行基变进行基变换，避免增加人工变量，运算简便。换，避免增加人工变量，运算简便。（2）变量较少，约束条件很多的线性规划问题，可先将其）变量较少，约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形求解，简化计算。变为对偶问题，再用对偶单纯形求解，简化计算。（3）灵敏度分析。）灵敏度分析。优点与用途：优点与用途：如市场条件发生变化，价值系数就会发生变化；如市场条件发生变化，价值系数就会发生变化；当资源投入量发生改变时，也随着发生变化；当资源投入量发生改变时，也随着发生变化；当工艺条件发生改变时，也随着工艺的变化而变化。当工艺条件

22、发生改变时，也随着工艺的变化而变化。灵敏度分析灵敏度分析1）系数在什么范围内变化时，最优解（基）不变；）系数在什么范围内变化时，最优解（基）不变；2）若系数的变化使最优解发生变化，如何最简便地）若系数的变化使最优解发生变化，如何最简便地求得新的最优解求得新的最优解(值，结构）。值，结构）。bXB XNXsXBB-1 bI B-1 NB-1-Z-CB B-1b 0CN-CB B-1 N-CB B-1 第三节、灵敏度分析第三节、灵敏度分析ABC资源量甲11112乙12220利润586解：设三种产品的产量分别为解：设三种产品的产量分别为x1、x2、x3，标准型为标准型为 max Z=5x1+8x2+

23、6x3x1+x2+x3+x4=12x1+2x2+2x3+x5=20 x1,x2,x3,x4,x50 已知某企业计划生产已知某企业计划生产3种产品种产品A、B、C，其资源消耗，其资源消耗与利润如表与利润如表2.12所示所示问：如何安排产品产量，可获最大利润？问：如何安排产品产量，可获最大利润？例例2.9表表2.1558600CBXBbx1x2x3x4x55x141002-18x28011-11最优表最优表Z8400-2-2-3表表2.1458600CBXBbx1x2x3x4x50 x412111100 x52012201初始表初始表058600最优方案为 X=(4,8,0)T,目标值为84。Cj

24、的灵敏度分析的灵敏度分析 最优表最优表 -表表2.16若若C3=10时，时，j=20，这时原方案已不是最优方案。，这时原方案已不是最优方案。原最优方案不发生改变。原最优方案不发生改变。j0，这时对最优解方案没有影响。，这时对最优解方案没有影响。在例在例2.9中，如果改变中，如果改变 C3 ，使，使 j=cj CBB-1 Pj1、目标函数中的价值系数、目标函数中的价值系数（1）非基变量的价值系数）非基变量的价值系数表表2.16581000XBbx1x2x3x4x55x141002-18x28011-11Z84002-2-3表表2.17581000XBbx1x2x3x4x55x141002-110

25、 x38011-11Z1000-200-5则最优方案调整为则最优方案调整为 X=(4,0,8)T,目标值为目标值为100。全部全部 仍仍0，最优解方案不变，最优值变。，最优解方案不变，最优值变。在例在例2.9中，如果中，如果 改变，使改变，使即单位产品即单位产品A的利润在的利润在4,8之间变化时之间变化时,最优方案不变，最优方案不变，但最优值为但最优值为 。（2）、基变量的价值系数）、基变量的价值系数为10时，原方案已不是最优方案表表2.18108600CBXBbx1x2x3x4x510 x141002-18x28011-11Z10400-2-122表表2.19108600XBbx1x2x3x

26、4x510 x112111100 x58011-11Z1200-2-4-100则最优方案调整为 X=(12,0,0)T,目标值为120。bXXBB-1bB-1AZ-C BB-1bC-C BB-1A 对偶单纯形法对偶单纯形法-新的最优方案。新的最优方案。最优基不变最优基不变-即生产产品的品种不变，但最优值会变化。即生产产品的品种不变，但最优值会变化。影响最优解和最优值影响最优解和最优值2、资源、资源b的灵敏度分析的灵敏度分析即原料甲的供应量在即原料甲的供应量在10，20之间时并不影响最优方案。之间时并不影响最优方案。当 时，时，最优方案调整为 X=(16,2,0)T,目标值为96。表表2.205

27、8600XBbx1x2x3x4x55x1401002-18x210011-11Z12000-2-2-3表表2.2158600XBbx1x2x3x4x55x120122010 x41001111Z10002-40-5最优方案为最优方案为 X=(20,0,0)T,目标值为目标值为100。新产品新产品D，单位产品消耗原材料甲，单位产品消耗原材料甲-3个单位，乙个单位，乙-2个单位，利润个单位，利润10。问：投产。问：投产D是否有利？是否有利？（1）D利润为多少利润为多少-投产产品投产产品D有利？有利？最优方案不变。投产产品最优方案不变。投产产品D无利。无利。3、添加新变量的灵敏度分析、添加新变量的灵

28、敏度分析（2）、当）、当 时，时，表表2.225860015XBbx1x2x3x4x5x65x141002-148x28011-11-1Z8400-2-2-33表表2.235860015XBbx1x2x3x4x5x615x611/400-1/2-1/418x291/411-1/23/40Z87-3/40-2-7/2-9/40生产B产品9件，生产D产品1件。目标值为87。假设电力供应紧张假设电力供应紧张-13单位单位产品产品A、B、C每单位需电力每单位需电力-2、1、3个单位个单位问该公司生产方案是否需要改变？问该公司生产方案是否需要改变？加入松弛变量得加入松弛变量得 2x1+x2+3x3x61

29、3解：原最优解解：原最优解（4，8，0）T原解已不是新约束条件下的最优解原解已不是新约束条件下的最优解以以x6为基变量，将上式反映到最终单纯形表中为基变量，将上式反映到最终单纯形表中表表2.24586000XBbx1x2x3x4x5x65x141002-108x28011-1100 x613213001Z 84 00-2-2-30 化化 BI 得表得表2.25代入电力约束条件代入电力约束条件 2x1+x2+3x3 134、添加新约束、添加新约束表表2.25586000XBbx1x2x3x4x5x65x141002-108x28011-1100 x63002311Z8400-2-2-30对偶单纯

30、形法对偶单纯形法表表2.26586000XBbx1x2x3x4x5x65x12104/30-1/32/38x29011/302/3-1/30 x4100-2/31-1/3-1/3Z8200-10/30-11/3-2/3生产A产品1件，生产B产品9件。目标值为82。（1）、非基变量的工艺发生改变）、非基变量的工艺发生改变影响影响 列，看检验数是大于零还是小于零。列，看检验数是大于零还是小于零。(小于零小于零-单纯形法）单纯形法）2、基变量的工艺发生改变、基变量的工艺发生改变当当 是基变量是基变量 的系数时，它的变化会使发生改变的系数时，它的变化会使发生改变 ，所以最终单纯形表，所以最终单纯形表

31、也要发生变化也要发生变化.改变改变(计划生产的产品工艺结构发生改变计划生产的产品工艺结构发生改变)5、技术系数、技术系数表表2.27558600XBbx1x1 x2x3x4x55x1412002-18x280011-11Z84050-2-2-3若产品若产品A的工艺改变为对甲、乙原材料需求为的工艺改变为对甲、乙原材料需求为-2，2，利润不变利润不变，问最优方案如何变化？问最优方案如何变化？表表2.2858600XBb x1 x2x3x4x55x1 21001-1/28x28011-11Z7400-23-11/2表表2.2958600XBbx1 x2x3x4x50 x421001-1/28x210

32、11101/2Z80-50-20-4最优方案发生改变，这时只生产B产品10件。目标值为80。当当 是基变量是基变量 的系数时，它的变化会使的系数时，它的变化会使 出现出现负数或检验数和基变量均不满足最优解要求。负数或检验数和基变量均不满足最优解要求。若产品若产品A工艺改变为对甲、乙原材料的需求分别为工艺改变为对甲、乙原材料的需求分别为1，3，单单位产品的利润为位产品的利润为5，问最优方案如何变化？问最优方案如何变化？表表2.3058600XBbx1x2x3x4x55x141002-18x28211-11Z8460-2-2-3表表2.3158600XBBx1x2x3x4x55x14100218x21601131Z10800-2-143 x1-2 x4+x5=-4 乘以（乘以（1）表表2.3258600MXBBx1x2x3x4x5x6Mx64-1002-118x216011310-Z4M-1285-M0-22M-24-M+80加加-人工变量人工变量x6 -x1+2 x4x5 +x6 =4表表2.3358600MXBbx1x2x3x4x5x60 x42-1/2001-1/21/28x2103/21101/2-3/2-Z-80-70-20-412-M生产B产品10件。目标值为80。