1、管 理 运 筹 学第六章 单纯形法的灵敏度分析与对偶 1 单纯形表的灵敏度分析 2 线性规划的对偶问题 3 对偶规划的基本性质 4 对偶单纯形法1管 理 运 筹 学1 单纯形表的灵敏度分析一、目标函数中变量 Ck系数灵敏度分析1.在最终的单纯形表里， X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与 Ck没有任何关系，所以当 Ck变成 Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为 Xk是非基变量，所以基变量的目标函数的系数不变，即 CB不变，可知 Zk也不变，只是 Ck变成了 Ck+ Ck。 这时 K= Ck-Zk就变成了 Ck+ Ck- Zk= K
2、+ Ck。 要使原来的最优解仍为最优解，只要 K+ Ck 0即可，也就是 Ck的增量 Ck - K。2.在最终的单纯形表中， X k是基变量 当 Ck变成 Ck+ Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数 CB变了，则 ZJ(J=1,2,.,N) 一般也变了，不妨设 CB=(CB1, CB2。 , Ck, ， CBm),当 CB变成 =(CB1, CB2。 ,Ck+ Ck, CBm),则：ZJ=(CB1, CB2。 , Ck, ， CBm)(a1j , a2j , aKj , amj)ZJ=(CB1, CB2。 , Ck+ Ck, ， CBm)(a1j , a2
3、j , aKj , amj) = ZJ + Ck aKj 2管 理 运 筹 学1 单纯形表的灵敏度分析根据上式可知检验数 J (J=1,2,.,M) 变成了 J,有 J=CJ-ZJ= J+ CK aKj 。 要使最优解不变，只要当 J K时， J =03管 理 运 筹 学1 单纯形表的灵敏度分析例：目标函数： Max z=50X1+100X2约束条件： X1+X2 3002X1+X2 400X2 250X1， X2 0最优单纯形表如下迭代次数 基 变 量 CB X1 X2 S1 S2 S3 b50 100 0 0 02 X1 50 1 0 1 0 -1 50S2 0 0 0 -2 1 1 50
4、X2 100 0 1 0 0 1 250ZJ 50 100 50 0 50 27500CJ -ZJ 0 0 -50 0 -504管 理 运 筹 学1 单纯形表的灵敏度分析我们先对非基变量 S1的目标函数的系数 C3进行灵敏度分析。这里 3=-50，所以当 c3的增量 c350 ，最 优 解不 变 。再 对 基 变 量 x1的目 标 函数的系数 c1进 行灵敏度分析。在 a11 ,a12 ,a13 ,a14 ,a15 中，除了知道 a11 和 a13 大于0， a15 小于 0，可知 ，有 。同 样 有。 这样可以知道当 -50 c150 时，也就是 x1的目标函数 c1 在 0c 1100 时
5、最优解不变。在最终的单纯形表中，用 C1代替原来的 C1=50,计算得表5管 理 运 筹 学1 单纯形表的灵敏度分析迭代次数 基 变 量 CB X1 X2 S1 S2 S3 b50 100 0 0 02 X1 C1 1 0 1 0 -1 50S2 0 0 0 -2 1 1 50X2 100 0 1 0 0 1 250ZJ C1 100 C1 0 -C1+100CJ -ZJ 0 0 - C1 0 C1-100从 3 0，得到 -c10, 即 c10 ，并且从 50 ，得到 c1100 。那么如果 c1 取值超出这个范围，必然存在一个检验数大于 0，我们可以通过迭代来得到新的最优解。6管 理 运
6、筹 学1 单纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中 S2 =50是基变量，即为，原料 A有 50千克没用完，再增加 A原料是不会增加利润的， A的对偶价格为 0。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为 0。迭代次数 基 变 量 CB X1 X2 S1 S2 S3 b50 100 0 0 02 X1 50 1 0 1 0 -1 50S2 0 0 0 -2 1 1 50X2 100 0 1 0 0 1 250ZJ 50 100 50 0 50 27500CJ -ZJ 0 0 -50 0 -507管
7、 理 运 筹 学1 单纯形表的灵敏度分析可以看出，上题中对于设备台时数约束来说，当其松弛变量 在目标函数中从 0变到 Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利50元时，譬如有人愿意出 50元买一个设备时，我们就不必为生产 、 产 品而使用完所有的 设备 台 时 了， 这说 明了 设备 台 时 数的 对 偶价格就是 Z3=50元。对 于含有大于等于号的 约 束条件，添加剩余 变 量化 为标 准型。 这时这 个 约 束条件的 对 偶价格就和 这 个剩余 变 量的 有关了。 这 将使得最 优 目标值 特 别 “恶 化 ”而不是改 进 ，故 这时约 束条件的 对 偶价格 应 取
8、值 的相反数 - 。对 于含有等于号的 约 束条件，其 约 束条件的 对 偶价格就和 该约 束方程的人工 变 量有关了。其 约 束条件的 对 偶价格就等于此 约 束方程的人工 变量的 值 。8管 理 运 筹 学下表 给 出了一个由最 终单纯 形表 对 于不同 约 束 类 型的 对 偶价格的取 值 。从 对 偶价格的定 义 ,可以知道当 对 偶价格 为 正 时 它将改 进 目 标 函数的 值 ，当对偶价格 为负时 它将使得目 标 函数朝着与最 优 化相反的方向前 进 。下面我 们 研究当右端 项 bj发 生 变 化 时 ，在什么范 围 内其 对 偶价格不 变 。 由于bj的 变 化并不影响系数矩
9、 阵 的迭代，故其最 终单纯 形表中的系数矩 阵 没有 变 化。由此可 见 当 bj变 化 时 ，要使原来的基不 变 得到的基本可行解仍然是可行解，也就是所求的基 变 量的 值 一定要大于 0。所 谓 使其 对 偶价格不 变 的 bj的 变 化范 围 ，也就是使其最 优 解的所有基 变 量不 变 ，且所得的最 优 解仍然是可行的 bj的 变 化范 围 。约 束条件 影子价格的取 值 等于 这 个 约 束条件 对应 的松弛 变 量的 值 ,即 为 的相反数 等于 这 个 约 束条件 对应 的剩余 变 量的 值 ,即 为 的相反数 = 等于 这 个 约 束条件 对应 的人工 变 量的 值 ,即 为 的相反数 1 单纯形表的灵敏度分析9管 理 运 筹 学1 单纯形表的灵敏度分析当 bj中的第 k项 bK 变 成 时 ，也就是原来的初始单纯 形表中的 b向量 变 成了 b向量10
