LESSON 4. Duality in Linear Programming

3.1 Concept of Duality

Associated with every L.P.P is always a corresponding L.P.P called the Dual problem of the given L.P.P. The original (given) L.P.P is called the Primal problem. However if we state the dual problem as the primal one, then the other can be considered to be the dual of this primal. The two problems can thus be said to constitute a pair of dual problems. Moreover as will be seen very soon, the two problems can be derived from each other and there is a unique dual (primal) problem associated with the primal(dual) problem. It will turn out that while solving a L.P.P. by simplex method, we shall simultaneously be solving its associated dual problem as well.

The  following table gives the amounts of two vitamins v1 and v2 per unit , present in two different foods f1 and f2 respectively.

Vitamin

Food

Daily requirements

f1  

f2

v1

2

4

40

v2

3

2

50

cost

3

2.5

 

 

The last column of this table represents the number of units of the minimum daily requirements for the two vitamins; whereas the last row represents the cost per for the two foods. The problem is to determine the minimum quantities of the two foods f1 and f2 so that the minimum daily requirements of the two vitamins are met and that at the same time, the cost of purchasing these quantities of f1 and f2 is a minimum. To formulate the problem mathematically, let xj be the number of units of food fj,(j = 1,2) to be purchased, then the above problem is to determine two real numbers x1 and x2 so as to

                         Minimize   z = 3x1 + 2.5 x2

Subject to the constraints :

                        

Here, of course, in the construction of constraints, we have assumed that any intake of more than the minimum requirements is not harmful and that negative purchase levels are prohibited. We shall consider this L.P.P. as the primal problem.

Now, let us consider a different problem, which is associated with above problem. Suppose there is a whole sale dealer who sells the two vitamins v1 and v2 along with some other commodities. The local shopkeepers purchase the vitamin from him and form the two foods f1 and f2 ( the details are same as in the given table). The dealer knows very well that the foods f1 and f2 have their market values only because of their vitamin contents. The problem of the dealer is to fix the maximum per unit selling prices, for the two vitamins v1 and v2, in such a way that the resulting prices of foods f1 and f2 do not exceed their existing market prices.

To formulate the problem mathematically, let the dealer decide to fix up the two prices at w1 and w2 per unit, respectively. Then, the dealer’s problem can be started mathematically has to determine to real numbers w1 and w2 so as to     

                           Maximize    z = 40w1 + 50w2

 Subject to the constraints:

                                             

Since negative price levels are prohibited.

Let us place the matrix formulation of this L.P.P. side by with that of the primal one :

  

These two problems remarkably symmetric

  • The cost vector associated with the objective function of one is just the right hand side vector in the other’s set of constraints.

  • The constraint coefficient matrix associated with one problem is simply the transpose of the constraint matrix associated with the other.

However the two problems differ in one respect, that  one of the problem is a maximization problem while the other is a minimization problem.

3.2 Duality theorems:

Theorem 1:

The dual of the dual is the primal.

Theorem 2: (Weak Duality Theorem)

        Let x0 be a  feasible solution to the primal problem

             

If  w0 be a feasible solution to the dual of the primal, namely

  

Theorem 3: (Fundamental theorem of Duality)

If the primal or the dual has the finite optimum solution, then the other problem also possesses a finite optimum solution and the optimum values of the objective functions of the two problems are equal.

Theorem 4: (Existence theorem)

If either the primal or the dual problem has an unbounded objective function value, then the other problem has no feasible solution.

3.3 Relationship between primal and dual:

The symmetrical relationship between the primal and dual problem is summarized below (assume primal to be a minimization problem)

Primal

Dual

Minimization

Maximization

Number of variables

Number of constraints

Number of constraints

Number of variables

Less than or equal to type constraint

Non negative variable

Equal to type constraint

Unrestricted variable

Unrestricted variable

Equal to type constraint

R.H.S constant for the ith constraint

Objective function coefficient for ith variable

Objective function coefficient for jth variable

R.H.S constant for the jth constarint

Coefficient (aij) for ith variable in jth constraint

Coefficient (aij) for jth variable in ith constraint

 

Rules for Constructing the Dual from the Primal (or primal from the dual) are:

  1. If the objective of one problem is to be maximized, the objective of the other is to be minimized.

  2. The Maximization problem should have all constraints and the minimization problem has all constraints

  3. All primal and dual variables must be non-negative (0)

  4. The elements of right hand side of the constraints in one problem are the respective coefficients of the objective function in the other problem.

  5. The matrix of constraints coefficients for one problem is the transpose of the matrix of constraint coefficient for the other problem.

Last modified: Saturday, 3 May 2014, 6:18 AM