运筹学 05.pptx

Chapter 5Sensitivity Analysis: An Applied Approach
to pany
Operations Research: Applications and Algorithms
4th edition
by Wayne L. Winston
Copyright (c) 2004 Brooks/Cole, a division of Thomson Learning, Inc.
– A Graphical Introduction to Sensitivity Analysis
Sensitivity analysis is concerned with how changes in an LP’s parameters affect the optimal solution.
Reconsider the Giapetto problem from Chapter 3.
Where:
x1 = number of soldiers produced each week
x2 = number of trains produced each week.
max z = 3x1 + 2x2
2 x1 + x2 ≤ 100 (finishing constraint)
x1 + x2 ≤ 80 (carpentry constraint)
x1 ≤ 40 (demand constraint)
x1,x2 ≥ 0 (sign restriction)
The optimal solution for this LP was z = 180, x1=20, x2= 60 (point B) and it has x1, x2, and s3 (the slack variable for the demand constraint) as basic variables.
How would changes in the problem’s objective function coefficients or right-hand side values change this optimal solution?
Graphical analysis of the effect of a change in an objective function value for the Giapetto LP shows:
By inspection, we can see that making the slope of the isoprofit line more negative than the finishing constraint (slope = -2) will cause the optimal point to switch from point B to point C.
Likewise, making the slope of the isoprofit line less negative than the carpentry constraint (slope = -1) will cause the optimal point to switch from point B to point A.
Clearly, the slope of the isoprofit line must be between -2 and -1 for the current basis to remain optimal.
A graphical analysis can also be used to determine whether a change in the rhs of a constraint will make the current basis no longer optimal. For example, let b1 = number of available finishing hours.
The current optimal solution (point B) is where the carpentry and finishing constraints are binding.
If the value of b1 is changed, then as long as where the carpentry and finishing constraints are binding, the optimal solution will still occur where the carpentry