Linear Programming

CHAPTER 4

Duality of Linear Programming

4.1 INTRODUCTION One of the interesting features of linear programming is duality. For every linear programming problem, there is a twin linear programming problem that has a special and unique relationship to the first one. These two problems stand as pairs, or duals of each other. Not only is duality a rather nice theoretical relationship; it has also proved to be of immense value in devising other operations research techniques. Furthermore, duality has a useful economic interpretation and is widely used in economic theory. Besides being of theoretical interest, duality is at the core of sensitivity analysis in linear programming. That, however, is the topic of Chapter 5. Chapter 4 assumes that you have a thorough grasp of Chapter 3. This programme can be rewritten by transposing (reversing) the rows and columns of the algebraic statement of the problem. Inverting the programme in this way results in dual (D) programme. A solution to the dual programme may be found in a manner similar to that used for the primal(P). The two programmes have very closely related properties so that optimal solution of the dual problem gives complete information about the optimal solution of the primal problem and vice versa. Duality is an extremely important and interesting feature of linear programming. The various useful aspects of this property are (i) If the primal problem contains a large number of rows (constraints) and a smaller number of columns (variables), the computational procedure can be considerably reduced by converting it into dual and then solving it. Hence it offers an advantage in many applications. (ii) It gives additional information as to how the optimal solution changes as a result of the changes in the coefficients and the formulation of the problem. This forms the basis of post optimality or sensitivity analysis. (iii) Duality in linear programming has certain far reaching consequences of economic nature. This can...