System Engineering 3(3+0)

LESSON 4. Duality in Linear Programming

The  following table gives the amounts of two vitamins v₁ and v₂ per unit , present in two different foods f₁ and f₂ 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 f₁ and f₂ 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 f₁ and f₂ is a minimum. To formulate the problem mathematically, let x_j be the number of units of food f_j,(j = 1,2) to be purchased, then the above problem is to determine two real numbers x₁ and x₂ so as to

                         Minimize   z = 3x₁ + 2.5 x₂

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 v₁ and v₂ along with some other commodities. The local shopkeepers purchase the vitamin from him and form the two foods f₁ and f₂ ( the details are same as in the given table). The dealer knows very well that the foods f₁ and f₂ 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 v₁ and v₂, in such a way that the resulting prices of foods f₁ and f₂ do not exceed their existing market prices.

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

                           Maximize    z = 40w₁ + 50w₂

 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 x₀ be a  feasible solution to the primal problem

             

If  w₀ 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.