Transcription of Chapter 4 Duality - Stanford University
{{id}} {{{paragraph}}}
Chapter 4 DualityGiven any linear program, there is another related linear program called thedual. In this Chapter , we will develop an understanding of the dual linearprogram. This understanding translates to important insights about manyoptimization problems and algorithms. We begin in the next section byexploring the main concepts of Duality through the simple graphical exampleof building cars and trucks that was introduced in Section Then, wewill develop the theory of Duality in greater generality and explore moresophisticated A Graphical ExampleRecall the linear program from Section , which determines the optimalnumbers of cars and trucks to build in light of capacity constraints.
metal stamping car assembly feasible solutions trucks produced (thousands) cars produced (thousands) optimal solution Figure 4.1: The constraints, feasible region, and optimal solution of the linear program associated with building cars and trucks. Written in matrix notation, the linear program becomes maximize cTx subject to Ax ≤ b x ≥ 0 ...
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document:
{{id}} {{{paragraph}}}