对外经济贸易大学研究生院：《运筹学研究》课程教学资源（讲稿）第2章对偶理论与灵敏度分析 Duality Theory and Sensitivity Analysis.pdf_大学文库

2019/6/20 1 第2章对偶理论与灵敏度分析 Duality Theory and Sensitivity Analysis 目录 2.1 对偶问题的提出 2.2 线性规划的对偶理论 2.3对偶问题的经济解释----影子价格 2.4 灵敏度分析 2.1 对偶问题的提出产品I 产品II 供应量设备原材料A 原材料B 1 4 0 2 0 4 8 16 12 利润 2 3 现工厂决策者决定不生产产品，而将其所有资源出租或出售，应如何给每种资源定价？设y1，y2和y3分别表示出租单位设备台时的租金和出让单位原材料A，B的价格，那么出让相对于生产一单位第 j 种产品的资源消耗的价值应不低于第 j 种产品的单位利润价值，但同时买方会把价格压到最低。则有（左式） 1 2 y y +  4 2 1 3 2 4 3 y y +  min 8 16 12 1 2 3  = + + y y y 1 2 3 y y y , , 0  1 2 x x +  2 8 1 4 16 x  2 4 12 x  1 2 max z x x = + 2 3 1 2 x x, 0  st.. 1 1 0 0 N B B C C B N C B − − −  −  1 Y C BB − = Y  0 YA C Yb z = max 0 z CX AX b X =   min 0 Yb YA C Y  =   对偶模型的一般式      = 0 . . X AX b s t max z CX （P)      = 0 . . min Y YA C st  Yb 上对偶模型称为对称式对偶模型。二者间有对称的对应关系：原问题（P）对偶问题（D）目标max型目标min型有n个变量（非负）有n个约束（大于等于）有m个约束（小于等于）有m个变量（非负）价格系数资源向量资源向量价格系数技术系数矩阵技术系数矩阵第j个变量为自由变量第j个约束为等式约束第i个约束为等式约束第i个变量为自由变量 • 原模型P和对偶模型D既有联系又有区别。联系在于，它们都是关于家具厂生产经营的模型，并且使用相同的数据；区别在于，它们所反映的实质内容是完全不同的：P是站在家具厂经营者的立场上追求家具厂的销售收入最大;而D 则是站在家具厂谈判对手的立场上寻求应付家具厂租金最少的策略。 • 任何线性规划问题都有对偶问题，而且都有相应的经济意义。 • 由以上不难得到，所谓对偶规划，就是与线性规划原问题相对应并使用同一组数据按照特定方法形成的另一种反映不同性质问题的线性规划模型

2019/6/20 2 2.1 对偶问题的提出—关系原问题（或对偶问题）对偶问题（或原问题）目标函数目标函数变量(n个) ≥ 0 ≤ 0 无约束 ≥ ≤ = 约束条件 (n个) 约束条件 (m个) ≤ ≥ = ≥ 0 ≤ 0 无约束变量(m个) 约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项 max z min 2.2 线性规划的对偶理论线性规划的对偶理论包括四个基本定理。定理1 对称性定理：对偶问题的对偶是原问题。 min Z’= - CX s.t. - AX≤- b X ≥0 min W= Y b s.t. YA ≥ C Y ≤ 0 max Z=C X s.t. AX≥b X ≥0 对偶的定义对偶的定义 max W’ = -Yb s.t. YA≥ C Y ≤ 0 定理2 弱对偶原理（弱对偶性）：设和分别是问题（P）和（D）的可行解，则必有 __ X __ Y   = =   n j m i j j ibi C X Y b c x y 1 1 __ __ ,即推论⑴ 若和分别是问题（P）和（D）的可行解，则是（D）的目标函数最小值的一个下界；是（P）的目标函数最大值的一个上界。 __ C X Y b __ __ X __ Y 这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。推论⑵ 在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。关于无界性有如下结论：问题无界无可行解无可行解问题无界原问题对偶问题        −  −  = + 0, 0 2 4 max 2 1 2 1 2 1 2 1 2 x x x x x x Z x x 无界如：（原）        − −  +  = + 0, 0 1 2 min 4 2 1 2 1 2 1 2 1 2 y y y y y y W y y 无可行解（对）推论⑶ 在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该可行的问题无界。例       + + +  + + +  = + + + − 0 2 3 2 20 2 2 3 20 max 2 3 4 1 4 1 2 3 4 1 2 3 4 1 2 3 4 x x x x x x x x x Z x x x x 试估计它们目标函数的界，并验证弱对偶性原理。（P）定理3 最优性判别定理：若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = Y* b，则X* 、Y*分别是问题 P和D 的最优解。 4、对偶定理（强对偶性）：若一对对偶问题 P 和 D 都有可行解，则它们都有最优解，且目标函数的最优值必相等

2019/6/20 3 推论⑷ 若 P 和 D 的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。综上所述，一对对偶问题的关系，只能有下面三种情况之一出现： ① 都有最优解，分别设为X* 和 Y*，则必有CX* =Y*b； ② 一个问题无界，则另一个问题无可行解； ③ 两个都无可行解。 5、互补松弛定理：设X*和Y*分别是问题 P 和 D 的可行解，则它们分别是最优解的充要条件是剩余变量或或 s s s s X Y Y A C X Y X Y b AX Y X . ( ) 0 0 ( ) 0 0     − = = − = =       同时成立一般而言，我们把某一可行点（如X*和Y* ）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。原问题与对偶问题解的对应关系问题与解的对偶问题状态有最优解无界无可行解有最优解一定不可能不可能无界不可能不可能可能原问题无可行解不可能可能可能定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi 增加一个单位时，所引起的目标函数最优值Z* 的改变量y * i 称为第 i 个约束条件的影子价格，又称为边际价格。           = = 0 D 0 max min Y YA C X AX b P Z CX W Yb 2.3 对偶问题的经济解释——影子价格 2.3 对偶问题的经济解释——影子价格影子价格 —— 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。若x *,y * 分别为（LP）和（DP）的最优解，那么， c T x * = b T y * 。根据 f = b Ty *=b1y1 *+b2y2 *++bmym * 可知 f / bi = yi * yi * 表示 bi 变化1个单位对目标 f 产生的影响，称 yi * 为 bi的影子价格。注意：若 B 是最优基， y * 为影子价格向量。 2.3 对偶问题的经济解释——影子价格影子价格的经济含义 (1)影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进

2019/6/20 4 19 （2）影子价格表明资源增加对总效益产生的影响。根据推论“设x 0和y 0分别为原规划（P）和对偶规划（D）的可行解，当cx 0=b Ty 0时，x 0、y 0 分别是两个问题的最优解”可知，在最优解的情况下，有关系因此，可以将z *看作是bi ,i=1,2，… ,m的函数，对bi求偏导数可得到这说明，如果右端常数增加一个单位，则目标函数值的增量将是 • 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。 • 需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围” 时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。 2.3 灵敏度分析(Sensitivity or what-if) • 灵敏度分析，是指对系统或事物因周围条件变化所表现出的敏感性程度的分析。 • 在前面讲的线性规划问题中，通常都是假定问题中的 aij,bi,cj系数是已知的常数，但实际上这些参数都是一些估计或预测的数字。在现实中，如果市场条件变化，cj值就会发生变化；如果工艺技术条件改变，则aij就会变化；如果资源的可用量发生变化，则bi也会发生变化。因此就必然会提出这样的问题，即当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者说，当这参数在一个多大的范围内变化时问题的最优解才会保持不变。这就是灵敏度分析所要研究解决的问题。 • 当然，如果线性规划问题中的一个或几个参数变化时，完全可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。因为由单纯形的迭代过程我们知道，线性规划的求解是从一组基向最变换为另一组基向量，其中每步迭代得到的数字只随着基向量的不同选择而有所改变，因此完全有可能把个别参数的变化直接在获得最优解的最终单纯形表上反映出来。这样就不需要从头计算，而只需对获得最优解的单纯形表进行审查，看一些数字变化后是否仍满足最优解的条件，如果不满足的话，再从这个表开始进行迭代计算，求得最优解即可。这也就是灵敏度分析。 • 在这里，仅介绍目标函数系数和资源约束的灵敏度分析。 ▪ 单个系数发生变化 ▪ 多个系数同时发生变化目标系数代表对未来收益情况（不可控环境因素）的预期，相应的灵敏度分析是考察环境的不确定性或变化对最优解有什么影响。目标函数系数的灵敏度分析例 Wyndor 玻璃制品公司产品组合问题改变目标系数（单位利润）会怎样？门的单位利润PD =$300降到PD =$200，而最优解保持不变！（只是目标函数值相应地发生了变化） 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $200 $500 Hours Hours Used Available Plant 1 1 0 2 <= 4 Plant 2 0 2 12 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 2 6 $3,400 Hours Used Per Unit Produced

2019/6/20 5 例 Wyndor 玻璃制品公司产品组合问题改变目标系数（单位利润）会怎样？门的单位利润PD =$300升到 PD =$500，而最优解保持不变！ 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $500 $500 Hours Hours Used Available Plant 1 1 0 2 <= 4 Plant 2 0 2 12 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 2 6 $4,000 Hours Used Per Unit Produced 例1 Wyndor 玻璃制品公司产品组合问题门的单位利润PD =$300升到 PD =$1000时，最优解发生变化！ 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $1,000 $500 Hours Hours Used Available Plant 1 1 0 4 <= 4 Plant 2 0 2 6 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 4 3 $5,500 Hours Used Per Unit Produced 改变目标系数（利润）会怎样？例 Wyndor 玻璃制品公司产品组合问题目标系数（单位利润）变化对最优解的影响案例1：Wyndor 玻璃制品公司产品组合问题利用Excel Solver进行灵敏度分析 Doors Windows Unit Profit $300 $500 Hours Hours Used Available Plant 1 1 0 2 <= 4 Plant 2 0 2 12 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 2 6 $3,600 Hours Used Per Unit Produced 例 Wyndor 玻璃制品公司产品组合问题灵敏度分析结果 Adjustable Cells Final Reduced Objective Allowable Allowable Cell Name Value Cost Coefficient Increase Decrease $C$12 Units Produced Doors 2 0 300 450 300 $D$12 Units Produced Windows 6 0 500 1E+30 300 最后三栏表示了门窗单位利润的最优域（可增加/减少量）当前最优解例 Wyndor 玻璃制品公司产品组合问题两个目标系数（利润）同时变化又会怎样？门的单位利润PD =$300升到 PD =$450，窗的单位利润PW=$500降到 PW=$400，而最优解保持不变！ 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $450 $400 Hours Hours Used Available Plant 1 1 0 2 <= 4 Plant 2 0 2 12 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 2 6 $3,300 Hours Used Per Unit Produced

2019/6/20 6 例 Wyndor 玻璃制品公司产品组合问题两个目标系数（利润）同时变化对最优解的影响 24 25 26 27 28 29 B C D E F G H Units Produced (Doors, Windows) Unit Profit for Windows (2, 6) $100 $200 $300 $400 $500 $300 (4, 3) (4, 3) (2, 6) (2, 6) (2, 6) Unit Profit $400 (4, 3) (4, 3) (2, 6) (2, 6) (2, 6) for Doors $500 (4, 3) (4, 3) (4, 3) (2, 6) (2, 6) $600 (4, 3) (4, 3) (4, 3) (4, 3) (2, 6) 多个目标函数系数同时变化时最优性分析目标函数系数同时变动的百分之百法则(The 100 percent rule for simultaneous changes in objective function coefficients)：如果目标函数的系数同时变动，计算出每一系数变动量占该系数最优域允许变动量(增加或减少)的百分比，而后，将各个系数的变动百分比相加，如果所得的和不超过百分之一百，最优解不会改变，如果超过百分之一百，则不能确定最优解是否改变。百分之百法则的重要作用 ▪可用于确定在保持最优解不变的条件下，目标函数系数的变动范围； ▪百分百法则通过将允许的增加或减少值在各个系数之间分摊，从而可以直接显示出每个系数的允许变动值； ▪线性规划研究结束以后，如果将来条件变化，致使目标函数中一部分或所有系数都发生变动，百分百法则可以直接表明最初最优解是否保持不变。约束资源的灵敏度分析/右端项的影子价格分析 ▪分析函数约束右端值变动的原因也是不能得到模型的参数的精确值，只能对其作大略的估计。因此要知道万一这些估计不准确产生的后果。 ▪更主要的理由是因为这些常数往往不是由外界决定的而是管理层的政策决策。在建模并求解后，管理者想要知道如果改变这些决策是否会提高最终收益。 •影子价格分析就是为管理者提供这方面的信息。例 Wyndor 玻璃制品公司产品组合问题改变工厂的可用生产时间（约束右端值）会怎样？工厂2的可用生产时间从每周 12小时增加至13小时，每周利润将增加$150！ 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $300 $500 Hours Hours Used Available Plant 1 1 0 1.667 <= 4 Plant 2 0 2 13 <= 13 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 1.667 6.5 $3,750 Hours Used Per Unit Produced 例 Wyndor 玻璃制品公司产品组合问题改变工厂的可用生产时间（约束右端值）会怎样？工厂2的可用生产时间进一步从每周13小时增加至18小时，每周利润将增加$750！每增加1小时，利润增加$150！ 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $300 $500 Hours Hours Used Available Plant 1 1 0 0 <= 4 Plant 2 0 2 18 <= 18 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 0 9 $4,500 Hours Used Per Unit Produced

2019/6/20 7 例 Wyndor 玻璃制品公司产品组合问题改变工厂的可用生产时间（约束右端值）会怎样？更加完整的结果 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 B C D E F G Doors Windows Unit Profit $300 $500 Hours Hours Used Available Plant 1 1 0 2 <= 4 Plant 2 0 2 12 <= 12 Plant 3 3 2 18 <= 18 Doors Windows Total Profit Units Produced 2 6 $3,600 Time Available Total Incremental in Plant 2 (hours) Doors Windows Profit Profit 2 6 $3,600 4 4 2 $2,200 5 4 2.5 $2,450 $250 6 4 3 $2,700 $250 7 3.667 3.5 $2,850 $150 8 3.333 4 $3,000 $150 9 3 4.5 $3,150 $150 10 2.667 5 $3,300 $150 11 2.333 5.5 $3,450 $150 12 2 6 $3,600 $150 13 1.667 6.5 $3,750 $150 14 1.333 7 $3,900 $150 15 1 7.5 $4,050 $150 16 0.667 8 $4,200 $150 17 0.333 8.5 $4,350 $150 18 0 9 $4,500 $150 19 0 9 $4,500 $0 20 0 9 $4,500 $0 Hours Used Per Unit Produced Optimal Units Produced Select these cells (B18:E35), before choosing the Solver Table. 例 Wyndor 玻璃制品公司产品组合问题灵敏度分析结果 Adjustable Cells Final Reduced Objective Allowable Allowable Cell Name Value Cost Coefficient Increase Decrease $C$12 Units Produced Doors 2 0 300 450 300 $D$12 Units Produced Windows 6 0 500 1E+30 300 Constraints Final Shadow Constraint Allowable Allowable Cell Name Value Price R.H. Side Increase Decrease $E$7 Plant 1 Used 2 0 4 1E+30 2 $E$8 Plant 2 Used 12 150 12 6 6 $E$9 Plant 3 Used 18 100 18 6 6 在此范围内，目标函数值的变化率保持不变影子价格：约束右端值的单位增量引起的目标函数值的增加当前约束右端值例 Wyndor 玻璃制品公司产品组合问题多个约束的右端值同时变化又会怎样？工厂3的可用工作时间转移1个小时给工厂2，利润将增加$50！ 3 4 5 6 7 8 9 10 11 12 B C D E F G Doors Windows Unit Profit $300 $500 Hours Hours Used Available Plant 1 1 0 1.333 <= 4 Plant 2 0 2 13 <= 13 Plant 3 3 2 17 <= 17 Doors Windows Total Profit Units Produced 1.333 6.5 $3,650 Hours Used Per Unit Produced 可以理解为：当将部分产品的生产从一个工厂转移到另一个工厂时，利润的改变情况例 Wyndor 玻璃制品公司产品组合问题多个约束的右端值同时变化又会怎样？不断将工厂3的工作时间转移到工厂2，利润变化情况多个约束同时变化时影子价格分析约束右端值同时变动的百分之百法则(The 100 percent rule for simultaneous changes in right-hand side)：同时改变几个或所有函数约束的右端值，如果这些变动的幅度不大，那么可以用影子价格预测变动产生的影响。为了判别这些变动的幅度是否允许，计算每一变动占可行域所允许的增加值或减少值的百分比，如果所有的百分比之和不超过100%，那么影子价格还是有效的，如果所有的百分比之和超过100% ，那就无法确定影子价格是否有效。百分之百法则 • 设参数a变化的最优范围的上下限分别为[a’,a’’]，若参数a变化增加到a*，则可行增加的百分比＝(a*-a)/(a’’-a)；若参数a变化减少到a*，则可行减少的百分比＝(a -a*)/(a-a’)。注意：不是(a - a*)/(a”-a’)。 • 对所有变化的目标函数系数，求其占可行增加和可行减少的百分比的绝对值之和。若绝对值之和不超过100%，则最优解不变； • 对所有变化的约束条件右侧的值系数，求其占可行增加和可行减少的百分比的绝对值之和。若绝对值之和不超过100%，则影子价格起作用； • 注意： • 当允许增加（减少）的量为无穷大时，则对任意增加（减少）的量，其允许增减（减少）的百分比均看做0； • 百分百法则是充分条件，非必要条件； • 该法则不能应用于目标函数系数和约束条件右边常数值同时变化的情况，此时需要重新计算

对外经济贸易大学研究生院：《运筹学研究》课程教学资源（讲稿）第2章 对偶理论与灵敏度分析 Duality Theory and Sensitivity Analysis

对外经济贸易大学研究生院：《运筹学研究》课程教学资源（讲稿）第2章对偶理论与灵敏度分析 Duality Theory and Sensitivity Analysis