The Simplex Method and Sensitivity Analysis

CHAPTER 3

The Simplex Method and Sensitivity Analysis

Chapter Guide. This chapter details the simplex method for solving the general LP problem. It also explains how simplex-based sensitivity analysis is used to provide im-portant economic interpretations about the optimum solution, including the dual prices and the reduced cost.

The simplex method computations are particularly tedious, repetitive, and, above all, boring. As you do these computations, you should not lose track of the big picture; namely, the simplex method attempts to move from one corner point of the solution space to a better corner point until the optimum is found. To assist you in this regard, TORA's interactive user-guided module (with instant feedback) allows you to decide how the computations should proceed while relieving you of the burden of the tedious computations. In this manner, you get to understand the concepts without being over-whelmed by the computational details. Rest assured that once you have learned how the simplex method works (and it is important that you do understand the concepts), computers will carry out the tedious work and you will never again need to solve an LP manually.

Throughout my teaching experience, I have noticed that while students can easi-ly carry out the tedious simplex method computations, in the end, some cannot tell why they are doing them or what the solution is. To assist in overcoming this potential diffi-culty, the material in the chapter stresses the interpretation of each iteration in terms of the solution to the original problem.

When you complete the material in this chapter, you will be in a position to read and interpret the output reports provided by commercial software. The last section de-scribes how these reports are generated in AMPL, Excel Solver, and TORA.

This chapter includes a summary of 1 real-life application, 11 solved examples, 1 AMPL model, 1 Solver model, 1 TORA model, 107 end-of-section problems, and 3 cases. The cases are in Appendix E on the CD. The AMPLlExcel/SolverITORA pro-grams are in folder ch3Files.

Real Life Application-Optimization of Heart Valve Production

Biological heart valves in different sizes are bioprostheses manufactured from porcine hearts for human implantation. On the supply side, porcine hearts cannot be "pro-duced" to specific sizes. Moreover, the exact size of a manufactured valve cannot be de-termined until the biological component of pig heart has been processed. As a result, some sizes may be overstocked and others understocked. A linear programming model was developed to reduce overstocked sizes and increase understocked sizes. The re-sulting savings exceeded $1,476,000 in 1981, the year the study was made. The details of this study are presented in Case 2, Chapter 24 on the CD.