chapter3 linear programming computer solutionand（chapter 3 linear programming computer solutionand）.doc

Chapter 3 Linear Programming: Computer Solution and Sensitivity Analysis Computer Solution Early linear programming used lengthy manual mathematical solution procedure called the Simplex Method (See CD-ROM Module A). Steps of the Simplex Method have been programmed in software packages designed for linear programming problems. Many such packages available currently. Used extensively in business and government. Text focuses on Excel Spreadsheets and QM for Windows. Linear Programming Problem: Standard Form Standard form requires all variables in the constraint equations to appear on the left of the inequality (or equality) and all numeric values to be on the right-hand side. Examples: x3 ( x1 + x2 must be converted to x3 - x1 - x2 ( 0 x1/(x2 + x3) ( 2 becomes x1 ( 2 (x2 + x3) and then x1 - 2x2 - 2x3 ( 0 Sensitivity analysis (or post-optimality analysis) is used to determine how the optimal solution is affected by changes, within specified ranges, in: the objective function coefficients the right-hand side (RHS) values Sensitivity analysis is important to the manager who must operate in a dynamic environment with imprecise estimates of the coefficients. Sensitivity analysis allows him to ask certain what-if questions about the problem. Objective Function Coefficients Let us consider how changes in the objective function coefficients might affect the optimal solution. The range of optimality for each coefficient provides the range of values over which the current solution will remain optimal. Managers should focus on those objective coefficients that have a narrow range of optimality and coefficients near the endpoints of the range. Range of Optimality Graphically, the limits of a range of optimality are found by changing the slope of the objective function line within the limits of the slopes of the binding constraint lines. The slope of an objective function line, Max c1x1 + c2x2, is -c1/c2, and the slope of a constraint, a1x1 + a2x2 = b, is