Page 91 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research Neha Tikoo, Lovely Professional University

Notes Unit 4: Linear Programming – Duality

CONTENTS
Objectives
Introduction

4.1 Concept of Duality
4.2 Dual Formulation
4.3 Advantages of Duality

4.4 Summary
4.5 Keywords
4.6 Review Questions
4.7 Further Readings

Objectives

After studying this unit, you will be able to:

 Analyze the importance of duality in linear programming
 Understand dual formation and solution

 Learn the significance and advantages of duality in LPP
Introduction

For every linear programming problem, there is an associated linear programming problem.
The former problem is called primal and the latter is called its dual and vice versa. The two
problems may appear to have superficial relationship between each other but they possess very
intimately related properties and useful one, so that the optimal solution of one problem gives
complete information about the optimal solution to the other. In other words, the optimal
solutions for both the problems are same.
The concept of duality is very much useful to obtain additional information about the variations
in the optimal solutions when certain changes are effected in the constraint coefficients, resource
availabilities and objective function coefficients. This is termed as post-optimality or sensitivity
analysis.

4.1 Concept of Duality

One part of a Linear Programming Problem (LPP) is called the Primal and the other part is called
the Dual. In other words, each maximization problem in LP has its corresponding problem,
called the dual, which is a minimization problem. Similarly, each minimization problem has its
corresponding dual, a maximization problem. For example, if the primal is concerned with
maximizing the contribution from the three products A, B, and C and from the three departments
X, Y, and Z, then the dual will be concerned with minimizing the costs associated with the time
used in the three departments to produce those three products. An optimal solution from the
primal and the dual problem would be same as they both originate from the same set of data.

86 LOVELY PROFESSIONAL UNIVERSITY