One of the fundamental ideas of linear optimization is that of duality. We saw a precursor to this idea in both Activity 2.1.6 and Activity 2.1.12. The same initial scenario produces both a maximization and a minimization problem. What does this mean, why does this occur, and what are the relations between these problems?
In this chapter, we define and explore the notion of duality in linear optimization. In Section 4.1 we give a geometric and algebraic interpretation of dual variables and the dual problem. In Section 4.2 we use geometric reasoning to guide proofs of powerful duality results connecting the primal and dual problems. Finally, in Section 4.3 we show how the simplex pivot from Chapter 2 applies geometrically and computationally to the dual problem, and show how Tucker tableaus encode the dual problem.
