运筹学课件灵敏度分析与参数规划ppt课件.ppt

28 03 2020 灵敏度分析与参数规划 5 1 5灵敏度分析与参数规划 灵敏度分析参数规划 矿山系统工程电子教案 28 03 2020 灵敏度分析与参数规划 5 2 概述 在定义线性规划问题的数学模型时 假定aij bi cj都是常数 但实际上这些数据往往是估计值和预测值 如市场条件一变 cj值就会变化 aij往往因为工艺条件的改变而改变 bi是根据资源投入后的经济效果决定的一种决策选择 对数据资料可能的波动作进一步的研究和分析一般称之为灵敏度分析 sensitivityanalysis 当有关数据的变化被看作是某个参数的函数时 这样的分析就是参数分析 parametricanalysis 28 03 2020 灵敏度分析与参数规划 5 3 5 1灵敏度分析 线性规划灵敏度分析的方法与一般经济计量模型采用的方法有所不同 它的特点是在建立数学模型和求得最优解之后 再考察解对数据变化的敏感程度 因此这种分析方法又称为优化后分析 postoptimalanalysis 线性规划问题中涉及的数据很多 决策者既希望知道个别数据变化的影响 还希望了解若干数据同时发生变化所产生的后果 本节仅讨论前一种情形 28 03 2020 灵敏度分析与参数规划 5 4 生产计划问题 maxz 2x1 3x2s t x1 2x2 84x1 164x2 12x1 x2 0maxz 2x1 3x2s t x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x5 0 28 03 2020 灵敏度分析与参数规划 5 5 灵敏度分析的意义 在生产计划问题的一般形式中 A代表企业的技术状况 b代表企业的资源状况 而C代表企业产品的市场状况 在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定 在实际生产过程中 上述三类因素均是在不断变化的 如果按照初始的状况制订了最佳的生产计划 而在计划实施前或实施中上述状况发生了改变 则决策者所关心的是目前所执行的计划还是不是最优 如果不是应该如何修订原来的最优计划 更进一步 为了防止在各类状况发生时 来不及随时对其变化作出反应 即所谓 计划不如变化快 企业应当预先了解 当各项因素变化时 应当作出什么样的反应 28 03 2020 灵敏度分析与参数规划 5 6 灵敏度分析的内容 本节将分析下列模型要素变化所产生的影响 模型数据发生变化目标函数系数 价值系数 cj右端常数 限定系数 bi组成系数 工艺系数 aij模型规模参数发生变化阶数m 即约束条件有增减维数n 即决策变量有增减 28 03 2020 灵敏度分析与参数规划 5 7 灵敏度分析的基础与依据 灵敏度分析是在线性规划问题求解后进行的 因此必有一个最优基B及其最优解作为分析的基础 所以灵敏度分析就是检验一下要素改变后 当前解是否仍然满足下述两个条件 i 可行性条件B 1b 0 ii 最优性条件CN CBB 1N 0 28 03 2020 灵敏度分析与参数规划 5 8 灵敏度分析的任务 线性规划的灵敏度分析要解决两个问题 一个或几个系数或要素变化后 当前的最优解或最优基是否有变 这些系数在什么范围内变动时 当前的最优解或最优基不变 另外 一旦当前解受影响就要运用适当方法对其进行调整 以便得到新的最优解 28 03 2020 灵敏度分析与参数规划 5 9 灵敏度分析的结果 通过灵敏度分析可以发现 系数或要素变化后会对线性规划问题产生下列程度不同的影响 当前最优解不变 当前最优基不变 当前最优解变为可行解 可行性不变 当前最优解变为正则解 最优性不变 当前最优解变为非可行非正则解 28 03 2020 灵敏度分析与参数规划 5 10 分析结果的处理方法 针对上述五种不同的分析结果 可按下列相应的调整方法进行处理 分析结果处理方法最优解不变计算CN CBB 1N最优基不变计算XB B 1b变为可行解原始解法求最优解变为正则解对偶解法求最优解变为普通解混合解法求最优解 28 03 2020 灵敏度分析与参数规划 5 11 灵敏度分析的算例 例5 1生产计划问题maxz 2x1 3x2s t x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x5 0其中 x1 x2分别为产品P1 P2的产量 x3 x4 x5分别为原料M1 M2 M3的非生产用量 问题的初始表和求解后的最终表如下 以此为例作有关的灵敏度分析 表5 1初始表和最终表 28 03 2020 灵敏度分析与参数规划 5 12 5 1 1价值系数cj的变化分析 价值系数变化是指目标函数系数cs发生变化 即cj cj cj 价值系数cj变化时 会使求解问题的最终表里的相关检验数改变 解的性质也可能因此改变 下面分别就cj是非基变量还是基变量的系数两种情况来讨论 28 03 2020 灵敏度分析与参数规划 5 13 1 非基变量系数cs的变化分析 若cs是非基变量xs的系数 这时它在计算表中所对应的检验数是 s cs CBB 1Ps当cs增加 cs后 要保证这个检验数仍小于或等于零 即 s cs cs CBB 1Ps 0那么 cs cs CBB 1Ps 即 cs cs CBB 1Ps s 综上所述 可以得出结论 若 cs s 则 s 0 当前解仍是最优解 若 cs s 则 s 0 当前解只是可行解 28 03 2020 灵敏度分析与参数规划 5 14 非基变量系数cs变化的分析算例 由上述讨论可知 生产计划问题中变量x3和x4的系数c3和c4分别不大于1 5和0 125时 问题的最优解不变 经营问题 假若生产计划问题中 原料M1既可用于生产又可按单位利润为2的价格直接出售 原料M2的单位储存费用为0 125 那么问题的目标函数变为z 2x1 3x2 2x3 0 125x4问题的最优解也随之改变 28 03 2020 灵敏度分析与参数规划 5 15 2 基变量系数cr的变化分析 当基变量xr的系数cr CB 变化 cr时 就会引起CB的变化 从而影响到各非基变量xj对应的 j 设 CB 0 cr 0 若要求原最优解不变 则新的检验数必须满足 j cj CB CB B 1Pj cj CBB 1Pj CBB 1Pj j 0 cr 0 b1j brj bmj T j crbrj 0于是得到 cr j brj brj0 cr的变化范围为是max j brj brj 0 cr min j brj brj 0 j 1 2 n 28 03 2020 灵敏度分析与参数规划 5 16 基变量系数cr变化的分析算例 试以表5 1为例 当基变量x2的系数c2变化 c2时 在原最优解不变的条件下确定其变化范围 从右表可见 若 3 1 5 c2 2 0 4 c2 8 1 8 0则有 c2 3和 c2 1 由此可得 c2的变化范围为 3 c2 1即x2的系数c2可以在 0 4 之间变化而原最优解不变 28 03 2020 灵敏度分析与参数规划 5 17 5 1 2资源数量变化的分析 资源数量br发生变化时 即br br br 最终表的解相应变为XB B 1 b b 这里 b 0 br 0 若XB 0 因为检验数不会随b变化 则最优基不变 只是最优解在中基变量的值变为XB 要保持最优基不变 br的取值范围可按下述可行性条件确定 B 1 b b 0由此可得max bi0 bir bir 0 cr min bi0 bir bir 0 28 03 2020 灵敏度分析与参数规划 5 18 资源数量变化范围确定的算例 B 1b B 1 b B 1b B 1 b1 0 0 T 例如求例5 1中第一个约束条件b1的增量 b1的取值范围时 按可行性条件确定如右 由此可得 b1 4 2 2 b1 2 0 5 4所以 b1的取值范围是 4 2 相应地 b1的变化范围是 4 10 若取 b1 2B 1 b b 4 0 3 Tz 17 28 03 2020 灵敏度分析与参数规划 5 19 资源数量变化的分析算例 在生产问题中 若该企业增加4个单位的原料M1 求这时的最优生产方案 计算将计算结果反映到最终表中 见右表 由于表中b列有负数 用对偶解法求新的最优解 从表中看出x3 2 即有2个单位的M1未被利用 28 03 2020 灵敏度分析与参数规划 5 20 5 1 3工艺系数的变化分析 关于工艺系数的变化分析可分为两种情况来讨论 一是单个系数aij的变化 一是某个系数列向量Pj a1j a2j amj T的改变 另一方面 根据变化的aij或改变的Pj是否处在基B中又需分别考虑 aij或Pj不在基B中时 它的改变不会影响到当前解XB B 1b 0的可行性 只可能影响到当前解的最优性 反之 当前解的可行性和最优性都可能受到影响 鉴于两个方面的前一种情况都比较简单 本节不予讨论 对于后一种情况也不作一般性讨论 仅以具体例子来说明 28 03 2020 灵敏度分析与参数规划 5 21 工艺系数列向量变化的分析算例 在生产问题中产品P2的工艺系数向量由P2 2 0 4 T变为P2 1 5 0 5 T 试分析对原最优计划的影响 设改进后的产品产量为x2 计算x2 在最终表中对应的列向量和检验数 2 c2 CBB 1P2 3 1 5 0 125 0 1 5 0 5 T 3 2 25 0 75 28 03 2020 灵敏度分析与参数规划 5 22 工艺系数和价值系数变化的分析算例 若工艺系数列向量和相应的价值系数P1 1 4 0 T c1 2变化为P1 2 5 2 T c1 4计算 1 c1 CBB 1P1 4 1 5 0 125 0 2 5 2 T 4 3 625 0 375 28 03 2020 灵敏度分析与参数规划 5 23 运用混合算法调整当前解 若工艺系数列向量和相应的价值系数P1 1 4 0 T c1 2变化为P1 4 5 2 T c1 4计算 1 c1 CBB 1P1 2 625 28 03 2020 灵敏度分析与参数规划 5 24 5 1 4决策变量增减的分析 若企业在计划期内 有新的产品可以生产 则在知道新产品的单位利润 单件资源消耗量时 可以在最优表中补充一列 其中的前m行可以由基矩阵的逆矩阵得到 而检验数行也可以由与其它列相同的方法计算得到 若检验数非正 则原最优解仍为最优 原生产计划不变 不生产这种新产品 否则 当检验数为正时 则应以该变量进基 作单纯形迭代 从而找出新的最优解 28 03 2020 灵敏度分析与参数规划 5 25 5 1 5约束条件增减的分析 在企业的生产过程中 经常有一些突发事件产生 造成原本不紧缺的