Ch对偶问题说课.ppt

* 【例2.13】考虑下列线性规划 求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。 （1）改变右端常数为: 2.4 灵敏度分析 Sensitivity Analysis 综合分析 * （2）改变目标函数x3的系数为c3=1; （3）改变目标函数中x2的系数为c2=2； （4）改变x2的系数为 （5）改变约束（1）为 （6）增加新约束 （7）增加新约束 2.4 灵敏度分析 Sensitivity Analysis * 【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如2－10所示。 表2－10 Cj 2 -1 4 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 4 x3 0 5/7 1 1/7 3/7 0 2 2 x1 1 2/7 0 －1/7 4/7 0 1 0 x6 0 －2 0 0 －1 1 1 λj 0 －31/7 0 －2/7 －20/7 0 ? 2.4 灵敏度分析 Sensitivity Analysis 最优解X=（1，0，2，0，0，1）T ，最优值Z=10 * 2.4 灵敏度分析 Sensitivity Analysis 最优基矩阵及其逆 （1）基变量的解为 基本解不可行，将求得的XB代替表2－10中的常数项，用对偶单纯形法求解，其结果见表2－11所示。 * 表2－11 Cj 2 －1 4 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 4 x3 0 5/7 1 1/7 3/7 0 22/7 2 x1 1 2/7 0 －1/7 4/7 0 6/7 0 x6 0 [－2] 0 0 －1 1 －2 λj 0 －31/7 0 －2/7 －20/7 0 ? 4 x3 0 0 1 1/7 1/14 5/14 17/7 2 x1 1 0 0 －1/7 3/7 1/7 4/7 －1 x2 0 1 0 0 1/2 －1/2 1 λj 0 0 0 －2/7 －9/14 －31/14 ? 2.4 灵敏度分析 Sensitivity Analysis * 最优解 （2）由表2－10容易得到基变量x3的系数c3的增量变化范围是 而c3=1在允许的变化范围之外，故表2－10的解不是最优解。非基变量的检验数 x4进基，用单纯形法计算，得到表2－12 2.4 灵敏度分析 Sensitivity Analysis * 表2－12 XB x1 x2 x3 x4 x5 x6 b x3 0 5/7 1 [1/7] 3/7 0 2 x1 1 2/7 0 －1/7 4/7 0 1 x6 0 －2 0 0 －1 1 1 λj 0 －16/7 0 1/7 －11/7 0 ? x4 0 5 7 1 3 0 14 x1 1 1 1 0 1 0 3 x6 0 －2 0 0 －1 1 1 λj 0 －3 －1 0 －2 0 ? 最优解为X=（3，0，0，14，0，1)T，最优值z=6。 2.4 灵敏度分析 Sensitivity Analysis * （3）c2是非基变量x2的系数，由表2－7知， 由 －1变为2时， 或直接求出x2的检验数 从而最优解不变，即X=(1，0，2，0，0，1)T。 2.4 灵敏度分析 Sensitivity Analysis * (4)这时目标函数的系数和约束条件的系数都变化了，同样求出λ2判别最优解是否改变。 x2进基，计算结果如表2－13所示 2.4 灵敏度分析 Sensitivity Analysis * 表2－13 Cj 2 3 4 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 4 x3 0 0 1 1/7 3/7 0 2 2 x1 1 －1 0 －1/7 4/7 0 1 0 x6 0 [3] 0 0 －1 1 1 λj 0 5 0 －2/7 －20/7 0 ? 4? x3 0 0 1 1/7 3/7 0 2 ?2 x1 1 0 0 －1/7 5/21 1/3 4/3 ?3 x2