Duality and Post-Optimal Analysis

CHAPTER 4

Duality and Post-Optimal Analysis

Chapter Guide. Chapter 3 dealt with the sensitivity of the optimal solution by determining the ranges for the model parameters that will keep the optimum basic solution unchanged. A natural sequel to sensitivity analysis is post-optimal analysis, where the goal is to determine the new optimum that results from making targeted changes in the model parameters. Although post-optimal analysis can be carried out using the simplex tableau computations in Section 3.6, this chapter is based entirely on the dual problem.

At a minimum, you will need to study the dual problem and its economic inter-pretation (Sections 4.1,4.2, and 4.3). The mathematical definition of the dual problem in Section 4.1 is purely abstract. Yet, when you study Section 4.3, you will see that the dual problem leads to intriguing economic interpretations of the LP model, including dual prices and reduced costs. It also provides the foundation for the development of the new dual simplex algorithm, a prerequisite for post-optimal analysis. The dual simplex algorithm is also needed for integer programming in Chapter 9.

The generalized simplex algorithm in Section 4.4.2 is intended to show that the simplex method is not rigid, in the sense that you can modify the rules to handle prob-lems that start both infeasible and nonoptimal. However, this material may be skipped without loss of continuity.

You may use TORA's interactive mode to reinforce your understanding of the computational details of the dual simplex method.

This chapter includes 14 solved examples, 56 end-of-section problems, and 2 cases. The cases are in Appendix E on the CD.