Operations Management
Linear Programming
Duality in Linear Programming
Duality
describes that linear programming problems (LPP) exist in ‘pairs’ i.e., for
every linear programming problem, there is another linear programming problem
which is related to it and, therefore, may be derived from it.
Before writing the dual to an LPP, it is necessary to express it in standard form if it is not so. By standard form it is meant that
1) All the variables in the problem should be non-negative; and
2) All the constraints should be of ‘≤’ type if the problem is of the maximisation type and that of ‘≥’ type if it is of the minimisation type.
The
method of deriving the dual to a given primal problem, i.e. the steps and rules
for deriving the dual to a given primal problem are now discussed in details
below.
Steps and Rules for deriving the dual to
a given primal problem:
To get
the dual of a primal linear program problem (LPP) we can follow the following
steps and rules:
1)
Write the primal LPP in its standard
form.
2)
Transpose the rows and columns of the
constraint coefficients.
3)
Transpose the coefficients of the
objective function and the right side constants.
4) Change the inequalities from "≤" to "≥" sign, or from "≥" to "≤" as the case may be.
5)
If the primal is a maximization problem,
the dual will be a minimization problem, and vice versa.
6)
The dual
of a given LPP is another LPP that's derived from the original LPP. In the
dual LPP, each variable in the primal LPP becomes a constraint, and each
constraint in the primal LPP becomes a variable.
7)
Each primal constraint corresponds to a
dual variable.
8)
The number of dual variables equals the
number of primal constraints.
9)
The number of dual constraints equals
the number of primal variables.
10)
One dual
variable for each primal constraint. We usually call them y1, y2,
y3..............
11)
The coefficients of the dual variables
in the objective function are the right-hand side constants of the primal
constraints.
12)
The right-hand side constants of the
dual constraints are the coefficients of the primal variables in the objective
function.
13)
For each ‘≥’ type constraint in the
primal, there's a ‘≤’ type constraint in the dual.
14)
For each ‘=’ type constraint in the
primal, there's an unrestricted variable in the dual.
15)
For each ‘≤’ type constraint in the
primal, there's a ‘≥’ type constraint in the dual.
16)
For each unrestricted variable in the
primal, there’s a ‘=’ type constraint in the dual.
17)
If primal
problem has ‘n’ constraints, there will be ‘n’ dual variables.
18)
Transpose of the coefficient matrix of
the primal constraints is the coefficient matrix of the dual constraints as
follows:
If the coefficient matrix of the primal constraints
is:
[2
3 5]
[3 1 7]
[1 4 6]
Transposing it, we get coefficient matrix of the dual
constraints as follows:
[2 3 1]
[3 1 4]
[5 7 6]
Linear Programming
Duality in Linear Programming
Selected Problems and Solutions
Problem: 1
Find the Dual
to the following Primal Problem:
Minimize (Z) =
2x1 + x2
Subject to:
3x1
+ x2 = 3
4x1
+ 3x2 ≥ 6
x1
+ 2x2 ≤ 3
x1, x2 ≥ 0
Solution: 1
Dual Problem:
Maximise (G) =
3y1 + 6y2 – 3y3
Subject to:
3y1
+ 4y2 – y3 ≤ 2
y1 + 3y2 – 2y3
≤ 1
y2, y3 ≥ 0; y1 is
unrestricted in sign.
Problem: 2
Find the Dual
to the following Primal Problem:
Minimize Z = x1 − 3x2 − 2x3
Subject to:
3x1
− x2 + 2x3 ≤ 7
2x1
− 4x2 ≥ 12
− 4x1
+ 3x2 + 8x3 = 10
x1,
x2 ≥ 0 and x3 is unrestricted in sign.
Solution: 2
Dual Problem:
Maximise (G) =
− 7y1 + 12y2 + 10y3
Subject to:
− 3y1
+ 2y2 − 4y3 ≤ 1
y1 − 4y2 + 3y3
≤ − 3
− 2y1 + 8y3 ≤ − 2
y1,
y2 ≥ 0; y3 is unrestricted in sign.
Problem: 3
Find the Dual
to the following Primal Problem:
Minimise Z =
3x1 + 2.5x2
Subject to:
2x1
+ 4x2 ≥ 40
3x1
+ 2x2 ≥ 50
x1,
x2 ≥ 0
Solution: 3
Dual Problem:
Maximise (G) =
40y1 + 50y2
Subject to:
2y1
+ 3y2 ≤ 3
4y1
+ 2y2 ≤ 2.5
y1,
y2 ≥ 0
Problem: 4
The vitamins V
and W are found in two different foods, F1 and F2. The
amount of vitamin in each of the two foods, respective prices per unit of each
food and the daily vitamin requirements are given in the following table.
|
Vitamin |
Foods |
Daily
Requirement |
|
|
F1 |
F2 |
||
|
V |
2 |
4 |
40 |
|
W |
3 |
2 |
50 |
|
Cost
per unit of Food (in Rs) |
3 |
2.5 |
|
Formulate the
primal problem to determine optimal of Food F1 and F2 to
be purchased so that the daily requirements are met and simultaneously, the
cost of purchasing the foods is minimized. Also formulate the dual problem for
the primal problem.
Solution: 4
Primal
Problem:
Minimise, Z =
3x1 + 2.5x2
Subject to:
2x1
+ 4x2 ≥ 40
3x1
+ 2x2 ≥ 50
x1,
x2 ≥ 0
Dual Problem:
Maximise (G)
=40y1 + 50y2
Subject to:
2y1
+ 3y2 ≤ 3
4y1
+ 2y2 ≤ 2.5
y1,
y2 ≥ 0
Problem: 5
A firm makes
three products A, B and C. Each product requires production time in each of
three departments as shown below:
|
Product |
Time
taken in hours per unit |
||
|
Dept.
I |
Dept.
II |
Dept.
III |
|
|
A |
3 |
2 |
1 |
|
B |
4 |
1 |
3 |
|
C |
2 |
2 |
3 |
Total time
available is 60 hours, 40 hours and 30 hours in department I, II and III
respectively. If product A, B and C contribute Rs 2, Rs 4 and Rs 2.5 per unit
respectively formulate the primal problem to determine the optimum product mix.
Also write the dual of this primal problem.
Solution: 5
Primal
Problem:
Maximise, Z =
2x1 + 4x2 + 2.5x3
Subject to:
3x1
+ 4x2 + 2x3 ≤ 60
2x1
+ x2 + 2x3 ≤ 40
x1 + 3x2 + 3x3
≤ 30
x1,
x2, x3 ≥ 0
Dual Problem:
Minimise (G) =
60y1 + 40y2 + 30y3
Subject to:
3y1
+ 2y2 + y3 ≥ 2
4y1
+ y2 + 3y3 ≥ 4
2y1
+ 2y2 + 3y3 ≥ 2.5
y1,
y2, y3 ≥ 0
Problem: 6
Obtain the
dual problem of the following LPP.
Maximize Z = 2x1 + 5x2 +6x3
Subject to:
5x1
+ 6x2 − x3 ≤ 3
− 2x1
+ x2 + 4x3 ≤ 4
x1
− 5x2 + 3x3 ≤
1
− 3x1
− 3x2 + 7x3 ≤ 6
x1,
x2, x3 ≥ 0
Solution: 6
Dual Problem:
Minimise (G) =
3y1 + 4y2 + y3 + 6y4
Subject to:
5y1
− 2y2 + y3 − 3y4 ≥ 2
6y1
+ y2 − 5y3 − 3y4 ≥ 5
− y1
+ 4y2 + 3y3 + 7y4 ≥ 6
y1,
y2, y3, y4 ≥ 0
Problem: 7
Write the dual
of the following LPP.
Maximize Z =3x1
+ x2 + 2x3 − x4
Subject to:
2x1
− x2 + 3x3 + x4 = 1
x1
+ x2 − x3 + x4 = 3
x1,
x2 ≥ 0 and x3 and x4 are unrestricted in sign.
Solution: 7
Dual Problem:
Minimise (G) =
y1 + 3y2
Subject to:
2y1
+ y2 ≥ 3
− y1
+ y2 ≥ 1
3y1
− y2 ≥ 2
y1
+ y2 ≥ − 1
y3,
y4 ≥ 0 and y1 and y2 are unrestricted in sign.
Problem: 8
Write the dual
of the following LPP.
Maximize Z = 3x1 + x2 + x3
− x4
Subject to:
x1 + 5x2 +3x3 + 4x4
≤ 5
x1 + x2 = − 1
x3
− x4 ≤ − 5
x1, x2, x3, x4
≥ 0
Solution: 8
Dual Problem:
Minimise (G) =
5y1 − y2 − 5y3
Subject to:
y1 +
y2 ≥ 3
5y1
+ y2 ≥ 1
3y1 + y3 ≥ 1
4y1 − y3 ≥ − 1
y1,
y3 ≥ 0; y2 is unrestricted in sign.
Problem: 9
Give the dual
of the following LPP.
Minimize Z = 2x1 + 3x2 + 4 x3
Subject to:
2x1
+ 3x2 + 5x3 ≥ 2
3x1
+ x2 + 7x3 = 3
x1
+ 4x2 + 6x3 ≤ 5
x1,
x2 ≥ 0 and x3 is unrestricted in sign.
Solution: 9
Dual Problem:
Maximise (G) =
2y1 + 3y2 – 5y3
Subject to:
2y1
+ 3y2 − y3 ≤ 2
3y1
+ y2 − 4y3 ≤ 3
5y1
+ 7y2 − 6y3 ≤ 4
y1,
y3 ≥ 0; y2 is unrestricted in sign.
Problem: 10
Give the dual
of the following LPP.
Minimize Z = x1 + x2 + x3
Subject to:
x1 −
3x2 + 4x3 = 5
x1 −
2x2 ≤ 3
2x2 − x3 ≥ 4
x1,
x2 ≥ 0 and x3 is unrestricted in sign.
Solution: 10
Dual Problem:
Maximise (G) =
5y1 − 3y2 + 4y3
Subject to:
y1 − y2 ≤ 1
− 3y1
+ 2y2 + 2y3 ≤ 1
4y1 − y3 ≤ 1
y2,
y3 ≥ 0; y1 is unrestricted in sign.
No comments:
Post a Comment