《管理运筹学之灵敏度分析与对偶理论》由会员分享，可在线阅读，更多相关《管理运筹学之灵敏度分析与对偶理论（18页珍藏版）》请在金锄头文库上搜索。
1、单纯形法的灵敏度分析灵敏度分析是研究线性规划模型原始数据的变化对最优解 的影响。研究内容：1.目标系数Cj的灵敏度分析2.约束常数bi灵敏度分析3.技术系数aij的灵敏度分析4.新增变量xt的灵敏度分析5.新增变量约束条件的灵敏度分析1、目标系数CK的灵敏度分析(1)、非基变量系数CK非基变量的检验数 CK+CK-ZK= +CK 0即： CK- 其中： ZKCB*PK基变量的检验数没有变化，要求非基变量检验数仍 小于等于零。(2)、基变量系数CK当基变量系数由 变为 时CB=(CB1, CB2, CK, CBm)变为CB=(CB1, CB2, CK+ CK, CBm)最优解不变的情况下CK的变
2、化范围：例： X1 X2 X3 X4 X5CB XB b 50 100 0 0 050 X1 50 1 0 1 0 -10 X4 50 0 0 -2 1 1 100 X2 250 0 1 0 0 1Cj -Zj -27500 0 0 -50 0 -50 非基变量目标系数灵敏度：C350, C550基变量目标系数灵敏度：-50 C150 -50 C2-50 C425 2、约束右端常数b的灵敏度分析若第k个约束条件约束常量的变化为bk,即b=(b1,bk+ bk,bm)例：X1 X2 X3 X4 X5CB XB b 50 100 0 0 050 X1 50 1 0 1 0 -10 X4 50 0
3、0 -2 1 1 100 X2 250 0 1 0 0 1Cj -Zj -27500 0 0 -50 0 -50右端常数项的灵敏度：-50b125-50 b2-50 b3503、技术系数aij的灵敏度分析（1）非基变量xj的系数aij的灵敏度分析对应的检验数变为 ，若 ，最优解不变；若 ，则继续进行迭待求出新的最优解。 （2）基变量xj的系数aij的灵敏度分析（不讨论）X1 X2 X3 X4 X5 X6CB XB b 50 100 0 0 0 16050 X1 50 1 0 1 0 -1 (0.5)0 X4 50 0 0 -2 1 1 0100 X2 250 0 1 0 0 1 1Cj -Zj
4、 -27500 0 0 -50 0 -50 35160 X3 100 2 0 2 0 -2 10 X4 50 0 0 -2 1 (1 ) 0100 X2 150 -2 1 -2 0 3 0Cj -Zj -31000 -70 0 -120 0 20 0例：X1 X2 X3 X4 X5 X6CB XB b 50 100 0 0 0 160 160 X3 200 2 0 -2 2 0 10 X5 50 0 0 -2 1 1 0100 X2 150 -2 1 4 -3 0 0 Cj -Zj -32000 -70 0 -80 -20 0 0线性规划的对偶问题 引例：问题1例1（原问题） 问题2（对偶问题
5、）现在假设工厂准备把设 备A,B,C用于出租，确定 合理的租金？工厂计划期内安排， 两种产品生产，需要设备 A,B,C台时及产品利润如表 所示资源限制 设备A11300 设备B21400 设备C01250 利润50100设y1, y2, y3分别为三种 设备的租金。原问题：求目标函数 值最大值问题 对偶问题：求目标函数 值最小值问题 互为对偶问题1、求目标函数最大值问题的线性规划问题有n各变量和m各 约束条件，约束条件均为小于等于的不等式。则其对偶问题则 是求目标函数值为最小值的线性规划问题，有m各变量和n各约 束条件, 约束条件均为大于等于的不等式。2、原问题的目标函数中的变量系数为对偶问题
6、中约束条件 的右端常数项，原问题有多少各变量，则对偶问题就有多少约 束条件。3、原问题的约束条件的右端常数项为对偶问题的目标函数 的变量系数。4、对偶问题的约束条件系数矩阵是原问题的约束条件的AT。 原问题 对偶问题 目标函数max 目标函数min 约束 条件 个个无符号限制 变量 变量 个无符号限制 个约束 条件 目标函数的系数 约束条件右端常数 约束条件系数矩阵A 约束条件右端常数 目标函数的系数 约束条件系数矩阵AT 例：写出下面线性规划问题的对偶问题对偶规划的基本性质1对称性：对偶问题的对偶是原问题。 2弱对偶性。 （1）原问题任一可行解的目标函数值是其对偶问题目标函 数值的下界；反之
7、对偶问题任一可行解的目标函数值是其原 问题目标函数值的上界。 （2）如原问题具有无界解，则其对偶问题无可行解；反之 对偶问题有可行解且目标函数值无界，则其原问题无可行解 （注意：本点性质的逆不成立，当对偶问题无可行解时，其 原问题或具有无界解或无可行解，反之亦然）。 （3）若原问题有可行解而其对偶问题无可行解，则原问题 目标函数值无界；反之对偶问题有可行解而其原问题无可行 解，则对偶问题的目标函数值无界。3最优性。如果 是原问题()的可行解， 是对偶问题 ()的可行解，并且 C = bT ，则 和 分别为原问 题()和对偶问题()的最优解。4强对偶性。即若原问题()及其对偶问题()都有可行解 ，则两者都有最优解；且它们的最优解的目标函数都相等。5互补松弛性。在线性规划问题的最优解中，如果对应某一 约束条件的对偶变量值为非零，则该约束条件取严格等式； 反之，如果约束条件取严格不等式，则其对应的对偶变量一 定为零。
