An Introduction to Optimization, 4th Edition

CHAPTER 17

DUALITY

17.1 Dual Linear Programs

Associated with every linear programming problem is a corresponding dual linear programming problem. The dual problem is constructed from the cost and constraints of the original, or primal, problem. Being an LP problem, the dual can be solved using the simplex method. However, as we shall see, the solution to the dual can also be obtained from the solution of the primal problem, and vice versa. Solving an LP problem via its dual may be simpler in certain cases, and also often provides further insight into the nature of the problem. In this chapter we study basic properties of duality and provide an interpretive example of duality. Duality can be used to improve the performance of the simplex algorithm (leading to the primal-dual algorithm), as well as to develop nonsimplex algorithms for solving LP problems (such as Khachiyan’s algorithm and Karmarkar’s algorithm). We do not discuss this aspect of duality further in this chapter. For an in-depth discussion of the primal-dual method, as well as other aspects of duality, see, for example, [88]. For a description of Khachiyan’s algorithm and Karmarkar’s algorithm, see Chapter 18.

Suppose that we are given a linear programming problem of the form

We refer to the above as the primal problem. We define the corresponding dual problem as

We refer to the variable λ ^m as the dual vector. Note ...