Duality in linear programming

Corresponding to every linear programming problem, there is another linear programming problem. The given problem is called the primal and the other its dual. Although the idea of duality is essentially mathematical, it has important interpretations. This can help managers in answering questions about alternative courses of action and their effect on values of the objective function.

When the primal problem is of the maximisation type the dual is of the minimisation type and vice versa. It is an interesting feature of the simplex method that we can use it to solve either the original problem – the primal – or the dual. Whichever problem we start out to solve, it will also give us the solution to the other problem. Consider the following general linear programming problem.

Maximise Z = c1x1 + c2x2, Subject to

a11x1 + a12x2 <or = b1

a21x1 + b22x2 <or = b2

x1,x2 > or = 0

We can write this problem in a short form as

Maximise Z = cx, Subject to       ax < or = b

x> or = 0

The dual corresponding to this problem is

Minimise   Z* = b’y

Subject to a’y > or = c’

y> or = 0

where

b’ =transpose of matrix b

a’ = transpose of matrix a

c’ = column matrix of coefficients of objective function.

Y’ = matrix of dual variables.

Or

Minimise   Z* = b1y1 +b2y2, Subject to

a11y1 +a21y2 < or = c1

a12y1 +a22y2 < or = c2

y1,y2> or = 0

The dual problem is constructed from the primal as follows:

  • Each constraint in primal problem will have a corresponding variable (dual variable y) in dual problem.
  • The elements of the right hand side of the constraints in the primal are equal to the respective co efficient of the variables in objective function in the dual [i.e. y1 will have a coefficient b1 in the objective function etc.].
  • If the primal problem is that of maximisation the dual problem is of minimisation.
  • The maximisation problem has (< or =) type constraints and the minimisation problem has (> or =) type constraints. If the constraints in the primal are mixed type, they are converted into constraints of the same type before formulating the dual.
  • The coefficient matrix of the dual is the transpose of the coefficient matrix of the primal.
  • The variables in both the problems are non-negative.

Leave a Reply

Your email address will not be published. Required fields are marked *