运筹学教程课件二 对偶理论与灵敏度分析.ppt

* * * * * * * * * * 关于影子价的一些说明 影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关 松弛变量值增加一个单位等于资源可减少一个单位 剩余变量值增加一个单位等于资源可增加一个单位 资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为 0 影子价为 0，资源并不一定有剩余 应用，邮电产品的影子价格 * 2.5.2 价值系数 cj 的灵敏度分析 cj 变动可能由于市场价格的波动，或生产成本的变动 cj 的变化会引起检验数的变化，有两种情况 非基变量对应的价值系数变化，不影响其它检验数 基变量对应的价值系数变化，影响所有非基变量检验数 1、非基变量对应的价值系数的灵敏度分析 最优解结构不变的条件 * 例2.5.1 * 2、基变量对应的价值系数的灵敏度分析 由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数 只有一个基变量的 c l发生变化，变化量为?c l（l?I） 各个非基变量的机会成本从zj变化为zj+?zj 。 * 设x4的价值系数增加?c4，对应k=2， 有一边为空集，有非基变量检验数为0如何处理 为什么akj=0不出现在任何一边的集合中 * 2.5.3 右端项 bi 的灵敏度分析 设 XB=B?1b 是最优解，则有XB=B?1b?0 b 的变化不会影响检验数 b 的变化量 ?b 可能导致原最优解变为非可行解 * 2.5.3 右端项 bi 的灵敏度分析 如果要使最优解中的基变量组成不变则要满足 其中b’i (i=1,2,…,m)为最优单纯表中的右端系数，a’i ,n+r为逆矩阵B-1中第r列各元素。 2.5.3 右端项 bi 的灵敏度分析 为了保证所有基变量的值均大于等于0，所以某一右端系数b r的变化范围应满足 当某一右端系数从b r变化变化为b r+? b r时，基变量的解值会发生变化。变化后的基变量值为 显然，由于基变量的解值发生变化，所以其目标函数也将随之发生变化。 * 以b2为例, x6是对应的松弛变量，所以有 * 2.5.4 技术系数 aij 的灵敏度分析 技术系数aij变化的影响比较复杂 对应基变量的 aij ，且资源bi已全部用完 对应基变量的 aij ，但资源bi未用完 对应非基变量的 aij ，且资源bi全用完或未用完 1、对应基变量的 aij ，且资源bi已全部用完 ?aij=0 2、对应基变量的 aij ，但资源bi未用完 ?? ? ?aij? xn+i /xj 上述两个公式不是充分必要的，为什么？ B–1发生变化，从而引起非基变量检验数 cj– zj 的变化 3、对应非基变量的 aij 只影响对应非基变量xj的检验数 cj– zj 若? aij 0，不会破坏最优解 若? aij 0，必须保证 cj– zj ? 0 * * x1, x3为非基变量， q1= 0, q2= 0.25, q3= 1, 故有 x2, x4为基变量，x5=100, b1有剩余， 故有 * 2.5.5 新增决策变量的分析 例2.4.2中，若新增产品 x8，问是否生产？ 已知 c8=9, a18=5, a28=4, a38=3 计算 x8 的检验数可知生产是否有利 结论：生产x8有利。 将B–1P8加入最优单纯型表中，以x8为入变量进行迭代 * 2.5.6 新增约束条件的分析 1、将最优解代入新的约束条件，若满足，则最优解不变 2、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型 3、利用对偶单纯型法继续迭代 为什么可以利用对偶单纯型法 例2.4.2 第2步 * * 注意：最优解的目标函数减少了25个单位 * 2.5.7 灵敏度分析举例 例2.4.3 某工厂生产三种产品 A, B, C，有五种生产组合方案。下两表给出有关数据。规定每天供应 A产品至少110 个，求收益最大的生产方案。 * 例2.13 解：设xj为已选定各种组合方案的组数(j=1,2,…,5)， x6为A产品的剩余变量， x7，x8分别为工人工时和机器工时的松弛变量。 * 例2.13 最优解的B–1是什么 产品A的影子价为多少 第II组方案的生产费用提高2元，是否要调整生产组别 若工人加班费为1元/小时，是否要采取加班措施 若通过租借机器增加工时，租费的上限应为多少 A产品的订购合同是否有利，A产品的变动范围多大 若要选用第IV组方案，该组的生产费用应降低多少 若工人加班费为0.3元/小时，最多允许加班时间多少 若机器租费低于44元/小时，问租几部机器才合适(每天8小时计) 若第III组方案使机器工时减少0.5小时，能否被选入 * 2.5.8 其他