Problems on Linear Programming – Simplex Method – Duality Problem

8. Write the dual of the L.P. Problem given below, and find the optimal
solution of the given problem by solving its dual problem.
Minimize Z = 2x1 + 9x2 + x3
Subject to : x1 + 4x2 + 2x3≥ 5
3x1 + x2 + 2x3 ≥4, and x1 , x2 , x3 ≥ 0.
Solution :
Since the given problem is having the Objective function to be minimized,
and all the constraint equations have the ≥ Inequality sign, and all the RHS
quantities of the constraint equations are (+ve), the given problem is in the
Standard form of Type II. Therefore, we may proceed to write its dual, as
shown below.
Dual :
Maximize Zw = 5w1 + 4w2
Subject to : w1 + 3w2≤ 2
4w1 + w2≤9,
2w1+ 2w2≤1, and w1 , w2 , w3 ≥ 0.
Now, this Dual being a 2-varable problem, it can be solved by the
graphical method. But since we need to find the solution of the given
(primal) problem from the optimal solution of the dual problem, we have to
necessarily solve the Dual problem by the Simplex method only.
Solution by Simplex method :
I. Convert the inequalities in the constraint equations into equalities
by adding the Slack variables ( all the constraints have ≤ sign ).
Thus, we get : Maximize Zw = 5w1 + 4w2 + 0.S1 + 0.S2 + 0.S3

1
 Subject to : w1 + 3w2 + S1 + 0.S2 +0.S3 = 2
4w1 + w2 + 0.S1 + S2 + 0.S3 = 9
2w1+ 2w2 + 0.S1 + 0.S2 + S3 = 1,
and w1 , w2 , w3 ≥ 0.
Starting Simplex Table :
cj 5 4 0 0 0
Basic CB wB Y1 Y2 Y3 Y4 Y5 Minimum Ratio

Variable
S1 0 2 1 3 1 0 0
=2
S2 0 9 4 1 0 1 0
= 2.25
S3 0 1 2
2 0 0 1
= 0.5
Zw=[CB].[wB]T= 0 -5 -4 0 0 0 j

Since (-5) is the highest (-ve) j value, Y1 becomes the Incoming vector. To

find the out-going variable, find the Minimum ratio of . This occurs in
the 3rd row, hence S3 is the out-going variable, and the corresponding
vector Y5 becomes the out-going vector. The key element is 2. Therefore, we

now write the next simplex table, as per the usual procedure, as shown
below.
II Table :
cj 5 4 0 0 0

2
 Basic CB wB Y1 Y2 Y3 Y4 Y5
Variable Minimum Ratio

S1 0 1.5 0 2 1 0
-
S2 0 7 0 -3 0 1 -2

w1 1 1 0 0
5
Zw=[CB.wB]T= 2.5 0 1 0 0 2.5 j

Now, in the above table, all ≥ 0, hence this solution is Optimal.

j

The Optimal solution for the dual problem is :

w1 = = 0.5; w2 = 0; w3 = 0; (Z w)max = 2.5

But, we want the Optimal solution for the Primal (given) problem. That is
read from the final simplex table of the Dual problem, as given below :
x1 = ( j) = 0; x2 = ( j) = 0; x3 = ( j) = 2.5;
Max Zw = 2.5 (or) Min Z = 2.5.
9. Write the dual of the following L.P. problem, and find the optimal values
of the variables in the given problem from the optimal solution of the
dual.
Maximize Z = -40x1 + 30x2 + 60x3
Subject to : x1 – 3x2 - 4x3 ≥ -20
-2x1 + x2 + 3x3 ≤ 10
and x1 , x3 ≥ 0; x2 is Unrestricted variable.
Solution :

3
First convert the given problem into Standard form, as shown below.
Maximize Z = -40x1 + 30x2 + 60x3
Subject to : -x1 + 3x2 + 4x3 ≤ 20
-2x1 + x2 + 3x3 ≤ 10
and x1 , x3 ≥ 0; x2 is Unrestricted variable.
Now, write the dual of the problem. x2 is Unrestricted variable, the
corresponding constraint equation in the dual problem (i.e. the equation
formed by the coefficients of x2 in the given primal problem) shall have
Equality sign.
Dual :
Minimize Zw = 20w1 + 10w2
Subject to : -w1 – 2w2 ≥ -40
3w1 + w2 = 30
4w1 + 3w2 ≥ 60 and w1 , w2 , w3 ≥ 0.
Now, we find that in the R.H.S. values of the constraint equations in the
dual problem, the 1st constraint has a (-ve) value, which is not acceptable
for the simplex algorithm. Convert it into (+ve) value by multiplying the
entire equation by (-1), thereby it becomes:
w1 + 2w2 ≤ 40
Now, add the Slack / Surplus / Artificial variables, as shown below :
Minimize Zw = 20w1 + 10w2 + 0.S1 + 0.S2
Subject to : w1 + 2w2 + S1 + 0.S2 = 40
3w1 + w2 + 0.S1 + 0.S2 = 30
4w1 + 3w2+ 0.S1 – S2 = 60 and w1 , w2 , w3 ≥ 0.

4
 Now, there is only one vector of the unit matrix, i.e. [ 1 0 0 ]T in the
coefficients matrix that can be formed from the above constraint equations.
Therefore, to get the other two vectors of the unit matrix, we need to
introduce two artificial variables in the 2 nd and 3rd constraint equations, as
shown below.
Minimize Zw = 20w1 + 10w2 + 0.S1 + 0.S2 – M.A1 – M.A2
Subject to : w1 + 2w2 + S1 + 0.S2 + 0.A1 + 0.A2 = 40
3w1 + w2 + 0.S1 + 0.S2 + A1 + 0.A2 = 30
4w1 + 3w2 + 0.S1 – S2 + 0.A1 + A2 = 60, and w1, w2, w3 ≥ 0.
Now, to apply the Simplex algorithm to this problem, the Objective function
should be a Maximization function. Convert ‘Zw’ into Maximization
function, as shown below.
Maximize Zw’ = - Zw = - 20w1 - 10w2 + 0.S1 + 0.S2 – M.A1 – M.A2
Subject to : w1 + 2w2 + S1 + 0.S2 + 0.A1 + 0.A2 = 40
3w1 + w2 + 0.S1 + 0.S2 + A1 + 0.A2 = 30
4w1 + 3w2 + 0.S1 – S2 + 0.A1 + A2 = 60, and w1, w2, w3 ≥ 0.
Now, we may write the starting simplex table, as shown below.
cj -20 -10 0 0 -M -M
Basic Variable CB wB Y1 Y2 Y3 Y4 Y5 Y6 Minimum
S1 0 40 1 2 1 0 0 0 40

A1 -M 30 3 1 0 0 1 0 10

A2 -M 60 4 3 0 -1 0 1 15

Zw’=[CB].[wB]T= -7M+20 -4M+10 0 M 0 0 j

-90 M

5
We find that the highest (-ve) value of j occurs for Y1, hence that is the
Incoming vector. To find the out-going variable, we compute the minimum

ratio of . Thus, by this rule, A 1 becomes the out-going variable, and

hence Y5 is the out-going vector. The key element is 3. So, we write the
next simplex table, as shown below.
cj -20 -10 0 0 -M -M Minimum
Basic CB wB Y1 Y2 Y3 Y4 Y5 Y6
Variable Ratio
S1 0 30 0 1 0 0 18

w1 -20 10 1 0 0 0 30

A2 -M 20 0 0 -1 1 12

Zw’= [CB]. 0 0 M 0
M+ M-
[wB]T= j

(-200-20M)

Thus, the only (-ve) value of j occurs for Y2. The Incoming vector is Y2.

To find the out-going variable, we compute the minimum ratio . And

6
this occurs in the 3rd row, hence A2 is the out-going variable, and is the

key element. Now, we write the next simplex table, shown below.

cj -20 -10 0 0 -M -M Minimum

Basic CB wB Y1 Y2 Y3 Y4 Y5 Y6
Variable Ratio
S1 0 10 0 0 1 1 1 -1

w1 -20 6 1 0 0

w2 -10 12 0 1 0

Zw’ = [CB].[wB]T= 0 0 0 2 (M-4) (M-2) j

-240

All the values of j are ≥ 0, we have arrived at the Optimal solution

for the dual problem. This Optimal solution is :
w1 = 6; w2 = 12; (Zw’)max = - 240.
Now, the Optimal solution for the Primal (given) problem can be read from
the final simplex table, as shown below:

7
x1 = ( j)Y3 Y3 corresponds to the coefficients of S1
x2 = ( j)Y5 Y5 corresponds to the coefficients of A1
x3 = ( j)Y4 Y4 corresponds to the coefficients of S2

x1 = 0; x2 = - 4 (after deleting M); x3 = 2; -- and --

Zmax = (Zw )min = - (Zw’)max = - (- 240) = 240.

Important Note :

x2 is negative, yet the solution is correct as x2 is given as Unrestricted

variable in the problem.