DUALITY IN LP PROBLEMS - Quantitative Techniques for management

Duality in linear programming is essentially a unifying theory that develops the relationships between a given linear program and another related linear program stated in terms of variables with this shadow-price interpretation. The importance of duality is twofold.

First, fully understanding the shadow-price interpretation of the optimal simplex multipliers can prove very useful in understanding the implications of a particular linear-programming model. Second, it is often possible to solve the related linear program with the shadow prices as the variables in place of, or in conjunction with, the original linear program, thereby taking advantage of some computational efficiencies.

Every minimization problem is associated with a maximization problem and vice-versa. The original linear programming problem is known as primal problem, and the derived problem is known as its dual problem. The optimal solutions for the primal and dual problems are equivalent.

Conversion of primal to dual has to be done because of many reasons. The dual form of the problem, in many cases, is simple and can be solved with ease. Moreover, the variables of the dual problem contain information useful to management for analysis.

Procedure

Step 1: Convert the objective function if maximization in the primal into minimization in the dual and vice versa. Write the equation considering the transpose of RHS of the constraints

Step 2: The number of variables in the primal will be the number of constraints in the dual and vice versa.

Step 3: The co-efficient in the objective function of the primal will be the RHS constraints in the dual and vice versa.

Step 4: In forming the constraints for the dual, consider the transpose of the body matrix of the primal problems.

Note: Constraint inequality signs are reversed

Example : Construct the dual to the primal problem

Maximize Z = 6x1 + 10x2

Subject to constraints,

2x1 + 8x2≤ 60 .......................(i)
3x1 + 5x2≤ 45 .......................(ii)
5x1 - 6x2≤ 10 .......................(iii)
x2≤ 40 .......................(iv)
where x1, x2≥0

Solution:

Minimize W = 60y1 + 45y2 + 10y3 + 40y4

Subject to constraints,

2y1+3y2+5y3+ 0y4≥ 6
8y1+ 5y2 + 6y3+ y4≥10
where y1, y2, y3, y4≥ 0

Example : Construct a dual for the following primal

Minimize Z = 6x1– 4x2+ 4x3

Subject to constraints,

6x1– 10x2 + 4x3≥14 ..................(i)
6x1+ 2x2 + 6x3≥ 10 ..................(ii)
7x1– 2x2 + 5x3≤ 20 ..................(iii)
x1– 4x2 + 5x3≥ 3 ..................(iv)
4x1+ 7x2– 4x3 20 ..................(v)
where x1, x2, x3≥ 0

Solution: Convert 'less than' constraints into 'greater than' type by multiplying by (–1) on both sides (i.e., for e.g. iii).

6x1– 10x2 + 4x3≥ 14
6x1+ 2x2 + 6x3≥10
– 7x1 + 2x2– 5x3≥ 20
x1– 4x2 + 5x3≥3
4x1 + 7x2– 4x3≥ 20

The dual for the primal problem is,

Maximize W = 14y1+10y2+20y3+3y4+20y5

Subject to constraints,

6y1+ 6y2– 7y3+ y4 + 4y5≤ 6
10y1+ 2y2 + 2y3– 4y4+7y5≤ – 4
4y1+ 6y2– 5y3+ 5y4– 4y5≤ 4
where y1, y2, y3, y4 and y5≥ 0


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Quantitative Techniques for management Topics