LP问题的灵敏度分析(第6章201410)

OR课件回顾前面五章内容都是围绕线性规划问题（一般形式、特殊形式）的求解（决策变量、目标等）而展开讨论的，目的旨在为规划的实施提供更多的决策依据。但在整个的讨论过程中，隐含有一个假设，即假定参数cj、bi、aij均为常数。然而：在决策的实践中，这些参数肯定是会随决策环境的变化而变化的。那么有问题：OR课件问题（1）已得的各种决策信息还有没有价值？（2）如果决策环境发生了变化，能否在已有信息的基础上，作适当的分析与计算即可？（3）能否在决策实践以前对这些参数作一些必要的分析，找出在保证原来最优方案的条件下，参数可以变动的范围，以便于实践中对它们的管理与控制？OR课件运筹帷幄之中决胜千里之外LP的灵敏度分析第六章SensitivityAnalysisofLPOR课件§2灵敏度分析的基本原理§3对Cj的灵敏度分析§4对bi的灵敏度分析§5对aij的灵敏度分析§6应用示例§1概述主要内容OR课件重点－－各种参数取值范围计算公式的计算原理及有关数据的经济含义。难点－－难点是计算公式的推导和灵敏度分析的应用。本章重点、难点OR课件灵敏度分析是线性规划中的重点内容之一。要求领会灵敏度分析的涵义及意义；掌握各种参数取值范围计算公式的原理及有关数据的经济含义；学会应用灵敏度分析为决策者提供更加准确的决策依据。本章要求OR课件问题的提出：在规划实施过程中，参数cj、bi、aij均受市场环境及生产条件等的影响而发生变化。价格系数资源系数单耗系数信息的变化：价值向量—市场变化右端向量—资源变化系数矩阵—技术进步认知的误差：背景、知识、环境等§1概述OR课件什么是灵敏度分析？就是在线性规划问题求出最优解后，当参数变化时，不必从头开始重算一次，就能知道最优解及目标函数值会发生什么变化，使决策人员经济、便利地得到比一组最优解更多的信息。分析的条件：MaxZ，；仅作单因素分析§1概述OR课件LP模型：maxZCX0AXbX标准型为max0SZCXX0,0SSAXIXbXX矩阵分块max0BBNNSZCXCXX,,0BNSBNSBXNXIXbXXX§2灵敏度分析的基本原理OR课件变换系数矩阵1111BNSBBXBNXBIXBb111BNSIXBNXBXBb111BNSXBbBNXBX111()BNBNBSZCBbCCBNXCBX变换变换目标变§2灵敏度分析的基本原理OR课件LP模型变为：111max()BNBNBSZCBbCCBNXCBX111,,0BNSBNSIXBNXBXBbXXXCBCNC0BCBXbBXNXSXBCBX1BbI1BN1BZ1BCBb01NBCCBN1BCB基变量取值基变量系数矩阵非基变量系数矩阵松弛基变量系数矩阵原（对）目标值对实变量取值对虚变量取值§2灵敏度分析的基本原理OR课件基本解为最优解的条件：10BXBb10NBCCBN10BCB灵敏度分析的任务：（1）为了保持现有的最优解或最优基不变，找出这些数据变化的范围，即所谓数据的稳定性区间。（2）当这些数据的变化超出了稳定性区间时，如何在原有最优解或最优基的基础上，作微小的调整，尽快求出新的最优解或最优基。原问题的解对偶问题的解Cj变化bi变化aij变化§2灵敏度分析的基本原理OR课件§3对灵敏度分析cj概念分析基础分析过程OR课件概念cj的灵敏度分析，就是在不改变原来最优解基变量及其取值的条件下，求出cj值的允许变动范围，即cj变动值的上、下限。§3对灵敏度分析cjOR课件分析基础不改变最优解的基变量及其取值，即保持cj–zj0单纯形表是否达到最优关键取决于：检验数和bi.§3对灵敏度分析cjOR课件分析过程niijijjjacczc1对应非基变量的系数对应基变量的系数§3对灵敏度分析cjOR课件•非基变量对应的cj:cj的上、下限01zccacccjjjniijijj常数zccjjj下限上限例§3对灵敏度分析cjOR课件例jxxxxxxxxxxxxxxxxxZj对一切）源（资）源（资）源（资,031000212001800354343452324354321432143214321maxcj1534000C’BXBbx1x2x3x4x5x6x7045x5x4x21002001000.252–0.75001-3.25-22.750101000.251-0.75-1-11ZjCj–Zj4.25-3.25505.75-2.7540000.25-0.251-1y1y2y3§3对灵敏度分析cjOR课件•例cj1534000C’BXBbx1x2x3x4x5x6x7045x5x4x21002001000.252–0.75001-3.25-22.750101000.251-0.75-1-11ZjCj–Zj4.25-3.25505.75-2.7540000.25-0.251-1非基变量对应的cj-c1-(-3.25)-c14.25-c3-(-2.75)-c35.75§3对灵敏度分析cjOR课件01aczcacccijijjniijjii针对第i行，其它行不变•基变量对应的:即的上、下限cici0min0maxaazccaazcijijjjjiijijjjj对于所有的j（非基变量）大于最大的、小于最小的例§3对灵敏度分析cjOR课件例cj1534000C’BXBbx1x2x3x4x5x6x7045x5x4x21002001000.252–0.75001-3.25-22.750101000.251-0.75-1-11ZjCj–Zj4.25-3.25505.75-2.7540000.25-0.251-1基变量对应的价格系数11,275.2min125.0,225.3max2c-0.25c413.75c45同理：-1c20.334c25.33§3对灵敏度分析cjOR课件概念分析基础分析过程求新解bi§4对灵敏度分析OR课件概念bi的灵敏度是指在最优解基变量保持不变，但基变量的取值可以变动的条件下bi的变动范围，即bi变动的上、下限。bi§4对灵敏度分析OR课件分析基础bi在允许变动范围内，新基变量的解要满足非负约束，即bi0bi§4对灵敏度分析OR课件分析过程01bBbXBXNBbBXSNB111即为最优单纯形表中，松弛变量所对应的系数矩阵aaaaaaaaaaaaaaaaBmnmknmnmnmmniknininimnknnnmnknnn,,2,1,,,2,1,,2,22,21,2,1,12,11,11bi§4对灵敏度分析OR课件•令资源k的数量变动bk，基变量新的值b`bbbbbaaaaaaaaaaaaaaaabmkkmnmknmnmnmmniknininimnknnnmnknnn21,,2,1,,,2,1,,2,22,21,2,1,12,11,10001211bBbbbbBkmkB1bi§4对灵敏度分析OR课件000,,2,1,,,2,1,,2,22,21,2,1,12,11,1baaaaaaaaaaaaaaaabkmnmknmnmnmmniknininimnknnnmnknnn0,,,2,121aaaabbbbbknmkniknknkmibi§4对灵敏度分析OR课件•取出任意第i行，得表达式：0,babkknii0min0max,,,,aabbaabknikniiikknikniii对于所有得i来说：大于最大的、小于最小的例bi§4对灵敏度分析OR课件例现分析第2种资源的变动范围：b2k=2,n=4cj1534000C’BXBbx1x2x3x4x5x6x7045x5x4x21002001000.252–0.75001-3.25-22.750101000.251-0.75-1-11ZjCj–Zj4.25-3.25505.75-2.7540000.25-0.251-175.01001200,25.0100minmax2b33.1332002b33.133310002bbi§4对灵敏度分析OR课件例•结论（1）资源2：在原来（1200单位）的基础上减少200单位，或者增加133.33单位，最优解的基变量仍然是x5、x4、x2（2）在这个范围内增加或减少任何数目的资源2，它的边际值不变，即为0.25bi§4对灵敏度分析OR课件求新解如果bi的变化在灵敏度范围以内，新解可直接求得（约束条件为型式）：abXXknkN0最优单纯形表中xn+k所对应的系数列向量？例bi§4对灵敏度分析OR课件例cj1534000C’BXBbx1x2x3x4x5x6x7045x5x4x21002001000.252–0.75001-3.25-22.750101000.251-0.75-1-11ZjCj–Zj4.25-3.25505.75-2.7540000.25-0.251-1若b2＝100：2530012575.0125.0100100200100245xxxXNNNNZ=25Z=0.25×100＝25bi§4对灵敏度分析OR课件§5对灵敏度分析aij技术系数aij的灵敏度分析增加新变量的灵敏度分析增加新的约束条件的灵敏度分析包括：OR课件概念分析基础分析过程§5对灵敏度分析aijOR课件概念aij的灵敏度分析是指不改变最优解的基变量及其取值的条件下，求aij的允许变动范围，即求aij的上、下限。§5对灵敏度分析aijOR课件分析基础aij的变化：既要保证可行，又要满足最优性检验。单耗变化，导致基变量取值的变化，要求满足bi0。单耗的变化，导致非基变量的机会成本变化，要求满足cj-zj0。§5对灵敏度分析aijOR课件•基变量对应的aij:即aij的上、下限bxxaxaiinnmjjijmjjij11（1）资源i用完：xn+i=0aij＝0非基变量等于0变化所以：例第2、3中资源全部用完（x6=0、x7=0）；而x2、x4为基变量：则a22、a24、a32、a34均不能变化。矛盾§5对灵敏度分析aijOR课件（2）资源i未用完：xn+i0bxxaxaiinnmjjijmjjij11非基变量等于0变化无限制xxainjijxxajinij综合：例第1种资源未用完，x5=100-a121-a141/2§5对灵敏度分析aijOR课件•非基变量对应的aij:即aij的上、下限miijijjjacczc110mjijiiyca110mmjijijjijijiii