We have seen how complex and cumbersome the iterating process in the Simplex Method can be. Every time a variable departs and new variable enters, complicated calculations requiring large space (and computer memory) have to be performed to get the new element values. Successive iteration are done by using number of row operations as has been discussed earlier. If a LPP with large number of variables and
constraints (which is in real life problem the solution will be) has to be solved by the Simplex Method, it will need a lot of time and computer space as all the tables and data will have to be stored and retrieved again and again.
However, there are methods available where the entire table does not have to be calculated during every iteration. The information required while constructing a new table is (a) C_{j} – Z_{j} value, the key column and the current basic variables and their values (or the solution value constants). This information can be directly obtained by using certain properties of the matrix. The following methods have been developed which make the computations much easier and simpler :
(a) The revised Simplex Method.
(b) The bounded variables method and
(c) The decomposition method .
The student is advised to go through the basics of matrix operation as given in the appendix of this book.
Example 4.19. Maximise Z = 5x_{1} + 2 x_{2} + 3 x_{2} – 2 x_{4} + x_{5}
Subject to 3 x_{1} + 2 x_{2} + 3 x_{3} + x_{4} = 12
x_{1} + 3x_{2} + x_{3} + x_{5} = 10
x_{1}, x_{2}, x_{3}, x_{4}, x_{5} ≥ 0
Sol. To find the basic feasible solution (nonoptimal), put x_{1} = x_{2} = x_{3} = 0.
x_{4} = 12,
x_{5} = 10.
New value of x_{5} element which is to be replaced by x_{1} variables are 5, 1,3, 1,0, 1.
New values of x_{4} element are
Solution value = 12 – [3 × 5] = – 3
element x_{1} = 3 – [3 × 1] = 0
element x_{2} = 2 – [3 × 3] = – 7
element x_{3} = 3 – [3 × 1] = 0
element x_{4} = 1 – [3 × 0] = 1
element x_{5} =0[3 × 1]=3
x_{1} = 5,
x_{2} = x_{2} = x_{5} = 0,
x_{4} = – 2,
Z_{max} = 31
The revised simplex method uses matrixvector operations to directly obtain the basic feasible solution from the original equations.
We denote the column vector P_{1}, P_{2}, P_{3}, P_{4}, P_{5} to represent x_{1}, x_{2}, x_{3}, x_{4} and x_{5} and let the column vector b represent the right hand side constraints i.e., solution values. From the original equation of constraints.
SOME MORE DUALITY PROBLEMS
Example 4.20. Solve the following LPP with the help of Duality.
Min Z = 2x_{1} + 2 x_{2}
Subject to 2 x_{1} + 4 x_{1} ≥ 1
x_{1} + 2 x_{1} ≥ 1
2 x_{1} + x_{2} ≥ 1
Sol. The dual of the given problem is
Maxirnise Z = a + b + c
Subject to 2a + b + c ≤ 2
4a + 2b + c ≤ 2
As the problem is now of maximisation, we will introduce slack variables.
Maximise Z = a + b + c + 0S_{1} + 0S_{2} + 0S_{3}
Subject to 2a + b + c + S_{1} + 0S_{2} = 2
4a + b + c + 0S_{1} + S_{2} = 2
The Simplex table can be written as follows
C_{j} → 
1 
1 
1 
0 
0 
Min Ratio 

↓ 
Basic Variables 
Solution Values 
a 
b 
c 
S_{1} 
S_{2} 

0 
S_{1} 
2 
2 
1 
2 
1 
0 

0 
S_{2} 
2 
4 
2 
1 
0 
1 

Z_{j} 
0 
0 
0 
0 
0 
0 

(C_{j}Z_{j}) 
1 
1 
1 
0 
0 
Since all the values of (C_{j} – Z_{j}) are equal i.e. 1, 1, 1 we can take anyone as the entering variable by taking it as key column. Let us take column C. S_{1} is the key row and (2) is the key element.
New value of C row (old S_{1}) will be obtained by dividing by key element i.e. 2.
So the new elements are 1, 1, ½ , 1, ½ , 0.
Sol. Multiply the objective function (Z) and the constraints by – 1 and introduce slack variables in order to convert it into equalities as there are two constraints, two slack variables will be introduced.
Maximise Z = – 4x_{1}– 6 x_{2} – 18 x_{3} + 0S_{1} + 0S_{2}
Subject to constraints
– x_{1} +0 x_{2} – 3 x_{3} + S_{1} + 0S_{2} = 3
0 x_{1} – x_{2} – 2 x_{3} + 0S_{1} + S_{2} = – 5
x_{1}, x_{2}, x_{3}, S_{1}, S_{2} ≥ 0
New elements are 5, 0, 1 , 2, 0, – 1.
New elements of row S_{1} are obtained by the relationship already known.
These are – 3 – 0 × 5 = – 3. All these elements will remain the same.
New row x_{3} (old S_{1}) will be obtained by dividing old S_{1} row by – 3 i.e. 1, 1/3, 0, 1, 1/3, 0.
New x_{1} row will be obtained by the relationship already known
There is no negative value in the solution value, the optimal solution has been obtained.
x_{1}=0,
x_{2 }=3,
x_{3 }=1,
Z_{j}=36.
Example 4.22. Solve the following LPP by Dual Simplex
Minimise Z = 6 x_{1} + 7 x_{2} + 3 x_{3} + 5 x_{4}
Subject to 5 x_{1} + 6 x_{2} – 3 x_{3} + 4 x_{4} ≥ 12
x_{1}+5 x_{3}6 x_{4} ≥ 10
2 x_{1} + 5 x_{2} + x_{3} + x_{4} ≥ 8
x_{1}, x_{2}, x_{3}, x_{4 ≥} 0
Sol. To convert it into a maximisation problem, the objective function and constraints will be multiplied by – 1.
Maximise Z = – 6 x_{1} – 7 x_{2}– 3 x_{3} – 5 x_{4}
Subject to – 5 x_{1} – 6 x_{2} + 3 x_{3} – 4 x_{4} ≤ – 12
– x_{1} – 5 x_{3} + 6 x_{4} ≤ – 10
2 x_{1}, 5 x_{2}, x_{3}, x_{4} ≤ 8
x_{1}, x_{2}, x_{3}, x_{4} ≥ 0
Introducing slack variables, the objective function and constraints can be written as
Max Z = – 6 X_{1} – 7 X_{2} – 3 X_{3} – 5 X_{4} + 0S_{1} + 0S_{2} + 0S_{3}
Subject to – 5 X_{1} – 6 X_{2} + 3 X_{3} – 4 X_{4} + S_{1} + 0S_{2} + 0S_{3} = – 12
– X_{2} – 5 X_{3} + 6 X_{4} + 0S_{1} + S_{1} + 0S_{3} = – 10
– 2 X_{1} – 5 X_{2}– X_{3} – X_{4} + 0S_{1} + 0S_{2} + S_{3} = – 8
and X_{1}, X_{2}, X_{3}, X_{4} , S_{1}, S_{2}, S_{3} ≥ 0
REVIEW
 1. Discuss in brief ‘Duality’ in linear programming.
 2. Explain the primaldual relationships.
 3. State and explain dual L.P.P.
 4. Prove that the dual of the dual of a given primal is again primal.
 5. State the fundamental properties of duality and prove anyone of them.
 6. If the kth constraint of the primal problem is an equality, then prove that the dual variable
 1. If the kth constraint of the primal problem is an equality, then prove that the dual variable w_{k is unrestricted in sign}

 1. If any variable of the primal problems is unrestricted in sign, the corresponding constraint in the dual will be a strict equality. Prove it.
 2. Slate the dual theorem and explain its implications.
 3. If either the primal or the dual problem has a finite optimal solution, then the other problem also has finite optimal solution and the values of the two objective functions are equal. Prove this.
 4. Prove that the necessary and sufficient condition for any linear programming problem and its dual to have an optimal solution is that both have feasible solutions.
 5. Prove that if the primal has an unbounded solution, the dual has either no solution or an unbounded solution.
 6. What is the essential difference between regular simplex method and dual simplex method?
 7. Develop the theory of dual simplex algorithm.
 8. Write a short note on ‘Complementary Slackness’.
 9. State and prove the complementary slackness theorem for the symmetrical dual problem
 10. What do you understand by ‘duality’ in linear programming’! State and prove the theorem of dual primal relationships.
 1. Dual Problem.
 2. Dual of a Primal.
 3. Shadow Prices in LPP.
 4. Concept of Duality in LPP.
 5. Explain primaldual relationship.
 6. Explain the role of duality in Linear Programming and discuss its uses in decisionmaking.
 7. Explain the primaldual relationship. How Dual problem can be useful in management decision making?
 1. Write the dual of the following L.P. Problem:
Maximize: 6R_{1} + 2R_{2}
Recent Comments