Probability Theory and Optimization

Probability Theory and Optimization

Module XXV

DUALITY IN LINEAR PROGRAMMING

The objectives of this module are:

To know the concept of duality in LPP
To study the principles and theorems of duality.
To practice solvingsome simple problems.

Introduction:

Associated with every linear programming problem, there is another LPP which is based on the same data and with the same value for the objective function. The original problem is called the primal problem and the associated problem is called the dual problem or vice versa.

Primal and Dual Problems:

Let a general LPP is stated as,

where ,

, ,

when we call the above problem as Primal LP Problem, its dual is defined as the following LP Problem.

; where

The correspondence between the primal in the standard form and its dual:

Primal / Dual
n 
m 


Variables 
Constraints 
Objective function  / n variable
m constraints
Cost coefficients
Constraint constants

Maximize / n constraints
m variables
constraint constants
cost coefficients

Minimize

Problem 1: Write down the dual of the following L.P.P. , Maximize

Subject to ; ; .

Solution: The given primal problem can be stated in the standard form,

Where,

and ;

the dual L P Problem is

, where

It is stated as:

Minimize

Subject to

; .

Problem 2: Write down the dual of the following primal L.P.P., Maximize

Subject to ; ;

Solution: To write the given primal problem in the standard form, we consider, the unrestricted variable as, where. The equation, is expressed as a combination of two inequalities,

and

Finally the given primal LPP can be stated as,

Maximize

Subject to

Maximize

Subject to

This is in the form,

Where,

and

Thedual L P Problem is,

where

stated as:

Minimize

Subject to

;

Consider , which is unrestricted. Then the problem becomes,

Minimize

Subject to

That is, Minimize

Subject to

24.2.Duality theorems:

Theorem:The dual of a dual is primal.

Proof: For the primal L P Problem

The dual L P Problem is,

This can be written as,

Then the dual L P Problem of this problem can be written as,

This can be expressed as,

Or, the problem is,

, which is the primal problem.

Theorem (Weak duality theorem): The value of the objective function f(X) for any feasible solution X of the problem, , is not greater than the value of the objective function (Y) for any feasible solution Y of

the dual . That is .

Proof: Consider the primal problem,

After introducing surplus variables, the problem becomes

…………………………..

In the dual of the problem,

After introducing slack variables, it becomes,

……………………………..

Let be any feasible solution of the primal and the dual respectively.

Multiply the primal constants by respectively, and the dual constraints byrespectively and add which implies two equations,

and ,

(1) – (2)

since are the set of feasible solutions,

L H S is non negative

There for it satisfies, the inequality) also. ********************************************************************************************************************************************************************************************

Simplex multipliers:

Consider the objective function

Subject to the constraint equations,

(2)

as shown in the canonical form of equations, if we assume are the basic variables, the objective function f(X) can be expressed in terms of non basic variables as follows

where

This type of expression for f(X) in terms of non-basic variable is necessary forall iterations of the simplex method.

It is possible to get the expression for objective of function in terms of non-basic

variables directly from the original equations (2) as follows:

Let us multiply each of the equations in (2) by constants and add them to (1)

Choose such that the coefficients of become zero, That is, choose such as,

The solution of m equations in given by (3) give the required values of

In matrix form (3) is written as

; , then,

The vector is called the multiplier vector and its components are the simplex multipliers. To calculate at any stage the inverse of, the matrix of basic vectors at that stage, is needed. Having calculated for any basis the value of the objective function for that basis is given by,

because the remaining terms in equation (4) contains the non basic variables which are assumed as zero.

Theorem: (Fundamental theorem of L P P)

The optimum value of f(X) of the primal, if it exists, is equal to the optimum value of (Y) of the dual.

Proof: In the primal problem,

After introducing the surplus variables, the constraints becomes,

Let be the optimal solution of the problem. Since it has to be basic feasible solution, and there are only m constraint equations, at least n of the numbers in the set of optimal solution are zero.

Let be the simplex multipliers for this solution.

Multiply the constraint equations with respectively and adding all the equations with the objective function, we get,

since are the simplex multipliers corresponding to the optimal solution,

and all of the cost coefficients in (1) are negative

and

(2) implies is the solution of the dual L P Problem

Corresponding to this solution (-1, -2, … -m) , the value of

But we have,

, satisfies only when is the minimum value of (Y)

From the proof of the above theorem, we get,

The negative of the simplex multipliers for the optimal solution of the primal are the values of the variables for the optimal solution of the dual; and in similar the simplex multipliers for the optimal solution of the dual are the values of the variables for the optimal solution of the primal.

Theorem:

If the primal problem is feasible, then it has an unbounded optimum if and only if the dual has no feasible solution, and vice versa.

Proof: Let the primal have and unbounded optimum. It means f(X) has no upper bound. That is for any number we consider, we can find a solution to the primal where the optimal value of primal is higher than the number considered. Then if possible, let the dual have a feasible solution. Then we can find a number as the value of the dual objective function, corresponding to this feasible solution. But we have for any feasible solution of the primal; the objective function f(X) isnot greater than the objective function of the dual for any of its feasible solution.

Hence in the case of unbounded optimum for primal and existence of feasible solution for the dual, is contradictory. So the dual has no feasible solution when the primal having an unbounded optimum.

In converse, let the dual is infeasible, and when primal is feasible, then to prove the primal has an unbounded maximum.

Let f(X) have a bounded minimum for feasible X:

We have over feasible values of Y.

Thus, when a bounded minimum exists for primal then the dual also should have a feasible solution which contradict the assumption that dual is infeasible.

Hence the primal has an unbounded maximum.

Theorem: (Complementary Slackness conditions)

If in the optimal solutions of the primal and the dual

(i)a primal variable is positive, then the corresponding dual slack variable is zero; and

(ii)if a primal slack is positive, then the corresponding dual variable is zero and vice versa

Proof: Let and are the set of feasible solution of the primal and the dual respectively.

Then we have,

Again on optimal solution of Dual and Primal,

We have

Then if the given feasible solutions are optimal also, then,

Since an optimal solution is feasible all . Hence to satisfy the equation (1), each term on the LHS of (1) separately should be zero.

It follows that in a term like , , and . Also in term like , and

The complementary slackness condition can play well in solving some L P Problems.

Problem: Solve the L.P.P. using complementary slackness conditions,

Maximize

Subject to

The dual LP Problem is,

Subject to; ; ;

;

The dual problem contains two variables and hence by solving graphically the solutions of the problem obtained as

Introducing slack variables to the primal constraints and the surplus variables

to dual constraints we can get the following equations

and

Since in the optimal solution of the dual,, then by using the constraint equations of the dual LP Problem, we get,

Since are primal variables and are dual variables, for optimal values of the variables, by complementary slackness property we have

Therefore, since of dual optimal are nonzero, the variables of primal optimal should be zero.

Then the primal constraint equations for optimal solution becomes,

This gives, .

Therefore the optimal solution of the primal is

Applications of duality

i)In an LP Problem numerical work increases more with the number of constraints than with the number of variables. Since the two get interchanged in the dual problem, then it is generally economical to solve the dual.

ii)It is possible under certain conditions to avoid the introduction of artificial variables to obtain an initial basic feasible solution.

24.3.Assignments:

(a)Obtain the dual of the following L.P.P: Maximize ; subject to ; ; .

(b)Obtain the dual of the L.P.P, Minimize ; subject to the constraints, ; ; .

(c)Formulate the dual of the following L.P.P: Minimize; subject to the constraints,;; ; .

24.4.Quiz

(a)If the primal problem contains n variables, then the dual have

(i) n variables (ii)n constraints(iii)m variables(iv)none of these.

(b)If p is the optimum value of the objective function of the primal problem and q be that of the dual, then

(i) p=q (ii) p>q (iii) p<q (iv)none of these

(c)Having calculated the simplex multipliers for any basis, the value of the objective function for that basis is given by,

(i) (ii) (iii) (iv) none of these

(d)If in the optimal solutions of the primal and the dual, a primal variable is positive, then the corresponding dual slack variable is

(i) positive (ii) negative (iii) zero (iv) None of these

24.5.Glossary

Primal and Dual problem: Another LPP associated with a given L.P.P. which is based on the same data and with the same value for the objective function of the given L.P.P is the dual problem of the given L.P.P. The given L.P.P is known as primal problem.
Simplex multipliers:The constants helps to express the objective function in terms of non basic variables are called the simplex multipliers. The vector is called the multiplier vector.

24.6.FAQs

What is duality in a L.P.P?
Why we use simplex multipliers?
What are the areas of application of the duality of L.P.P?

24.7.References:

Kanti Swaroop.P.K.,Gupta and Man Mohan: Operations Research (Sulthan Chand and Sons, New Delhi), 1998.
K.V. Mittal and C.Mohan:Optimization methods in Operations Research and system analysis (New Age Publications),2005.
Hamdy A Thaha: Operations Research (Prentise Hall of India Pvt.Ltd.),1997.
S.I.Gass , Linear Programming : Methods and applications (4th Edn. McGraw-Hill, New York), 1975.
G.Hadley, Linear Programming (Narosa Publishing House), 1995.

Summary:

In this module an associated problem to a L.P.P. with same solution for objective function which is called the dual problem of the original problem is considered. Method of finding the dual problem of a given problem is illustrated. Properties associated with the dual problem are discussed. Complementary slackness condition is narrated and finally some application of duality also added.

*************************

ANSWERS TO QUIZ AND FAQs

Quiz – Answers:

a. (ii) n constraints

b. (i) p=q

c. (iii)

d. (iii) zero

FAQs – Answers:

What is duality in a L.P.P?

Ans:Associated with every linear programming problem, there is another LPP which is based on the same data and with the same value for the objective function. The original problem is called the primal problem and the associated problem is called the dual problem or vice versa.

Why we use simplex multipliers?

Ans: simplex multipliers are used to express the objective function of a L.P.P in terms of non basic variables.

What are the areas of application of the duality of L.P.P?

Ans: In an LP Problem numerical work increases more with the number of constraints than with the number of variables. Since the two get interchanged in the dual problem, then it is generally economical to solve the dual. Also using duality it is possible under certain conditions to avoid the introduction of artificial variables to obtain an initial basic feasible solution.

*********************************************