The basic difference between the regular Simplex Method and the Dual Simplex Method is that whereas the regular Simplex Method starts with basic feasible solution, which is not optimal and it works towards optimality, the dual Simplex Method starts with an infeasible solution which is optimal and works towards feasibility. The following steps are involved in this method.
Step I. Convert the problem into a maximisation problem, if initially it is a minimisation problem.
Step II. If there are any ≥ type constraints, these must be converted into ~ type constraints by multiplying both sides by – 1.
Step III. Obtain the initial basic solution – For this, the inequality constraints have to be converted into equality by adding slack variables. Make a dual Simplex table by putting this information in the form of a table.
Step IV. Compute C_{j} – Z_{j} for each column.
a) If all C_{j} – Z_{j} are negative or zero and all solution values are nonnegative, the solution found above is the optimum basic feasible solution.
b) If all C_{j} – Z_{j} are negative and zero and at least one value of ‘solution value’ is negative then proceed to next step i.e. step V.
c) If any C_{j} – Z_{j} is positive, this method cannot be applied.
Step V. Select the row that contains the most negative ‘solution value’. This row is called the key row or the pivot row. The corresponding basic variable leaves the current solution.
Step VI. Scrutinise the elements of the key row.
a) If all elements are nonnegative, the problem does not have a feasible solution.
b) If at least one element is negative, find the ratios of corresponding elements of C_{j} _ Z_{j} row to there elements, ignoring the ratios associated with positive or zero elements of the key row. Select the smallest of these rows. The corresponding column is the key column and the associated variable is the entering variable. Mark (circle) the key element or pivot element.
Step VII. Make the key element unity (1). Carry out the row operations as is done in the regular Simplex Method and repeat until
a) An optimal feasible solution is obtained in a finite number of steps or,
b) An indication of nonexistence of feasible solution is found,
Example 4.15. Minimise Z = 50x_{1} + 250 x_{2}
Subject to 2 x_{1} + 20 x_{2} ≥ 120
5x_{1} + 10 x_{2} ≥ 70
5 x_{1}+10 x_{2 ≥} 80
x_{1, }x_{2} ≥ 0
Solve the problem by Simplex Method using primal and dual and see if the result obtained is the same. Sol. The LPP given above can be converted into the following form by introducing the surplus variables and artificial variables.
Minimise Z = 50 x_{1} + 250 x_{2} + 0S_{1} + 0S_{2} + 0S_{3} + MA_{1} + MA_{2} + MA_{3}
2x_{1} + 20 x_{2} S_{1} + 0S_{2} + 0S_{3} + A_{1} + 0A_{2} + 0A_{3} = 120
5 x_{1} + 10 x_{2} + 0S_{1} – S_{2} + 0S_{3} + 0A_{1} + A_{2} + 0A_{3} = 70
x_{1}, + 10 x_{2} + 0S_{1} + 0S_{2} – S_{3} + 0A_{1} + 0A_{2} + A_{3} = 80
x_{1},x_{2 },S_{1}, S_{2}, S_{3}, A_{1}, A_{2}, A_{3} ≥ 0
where S_{1}, S_{2}, S_{3} are the surplus variables and A_{1}, A_{2}, A_{3} are the artificial variables.
For solving this problem with Simplex Method, let us construct the initial simplex table.
Initial Simplex Table
C_{j} 
C_{j} 
50 
250 
0 
0 
0 
M 
M 
M 
M in ratio 

↓ 
Basic variables 
Solution variables 
x_{1} 
x_{2} 
S_{1} 
S_{2} 
S_{3} 
A_{1} 
A_{2} 
A_{3} 

M 
A_{1} 
120 
2 
20 
1 
0 
0 
1 
0 
0 
6 
M 
A_{2} 
70 
5 
10 
0 
1 
0 
0 
1 
0 
7 
M 
A_{3} 
80 
8 
10 
0 
0 
1 
0 
0 
1 
8 
Z_{j} 
270 M 
15M 
40M 
M 
M 
M 
M 
M 
M 

(C_{j}Z_{j}) 
5015M 
25040M 
M 
M 
M 
0 
0 
0 
Putting x_{1} = x_{2}=0, S_{1} =1. S_{2}=7. S_{3}=10 and S_{4}=3
C_{j} 
C_{j} → 
3 
2 
0 
0 
0 
0 

↓ 
Basic Variable 
Solution Value 
x_{1} 
x_{2} 
S_{1} 
S_{2} 
S_{3} 
S_{4} 
0 
S_{1} 
1 
1 
1 
1 
0 
0 
0 
0 
S_{2} 
7 
1 
1 
0 
1 
0 
0 
0 
S_{3} 
10 
1 
2 
0 
0 
1 
0 
0 
S_{4} 
3 
0 
1 
0 
0 
0 
1 
Z_{j} 
0 
0 
0 
0 
0 
0 
0 

(C_{j}Z_{j}) 
3 
2 
0 
0 
0 
0 
selecting the row with most negative solution value i.e. – 10, this is the key row. To find the key column.
Selecting the smaller of these ratios i.e. x_{2} is the key column and – 2 is the key element and – 2 is the key, element (circled). Row S_{3} is to be replaced by x_{2}. Value of x_{2} elements is obtained by dividing the row by key element i.e. – 2. Hence the row x_{2} (earlier S_{3}) is 5, ½ , 1, 0, 0, ½ , 0.
New row values of S_{1}, S_{2} and S_{4} can be determined by using the relationship.
New row element = (Element in old row) – [(Intersectional element in old row) × (Corresponding element in replacing row)
Element Solution value =  1( 1 × 5) =  1 + 5 = 4
Key element ½ is marked with a circle ½ in the table.
Row S_{4} is to be replaced by x_{1} All elements of S_{4} are divided by the key element ( ½) out these elements of new x_{1} row i.e. 4, 1,0,0,0,  1,  2.
These values can be placed in the table to determine whether it turns out to be a feasible solution or not.
C_{j} 
C_{j} 
3 
2 
0 
0 
0 
0 

↓ 
Basic Variables 
Solution Variable 
x_{1} 
x_{2} 
S_{1} 
S_{2} 
S_{3} 
S_{4} 
0 
S_{1} 
6 
0 
0 
1 
0 
1 
1 
0 
S_{2} 
0 
0 
0 
0 
1 
1 
1 
2 
x_{2} 
3 
0 
1 
0 
0 
0 
1 
3 
x_{1} 
4 
1 
0 
0 
0 
1 
2 

Z_{j} 
18 
3 
2 
0 
0 
3 
4 

(C_{j}Z_{j}) 
0 
0 
0 
0 
3 
4 
Since all the C_{j}  Z_{j} values are either zero or  ve this is the optimal feasible solution or not.
x_{1} =4, x_{2} = 3
z_{ma}_{x} =  3 × 4  2 × 3 =  18
Step III. Add slack variables S_{1}, S_{2}, S_{3} in the constraints. The problem can now be rewritten as
Maximise K =  2 x_{1}  2 x_{2}  4 x_{2} + S_{1} + 0S_{2} + 0S_{3}
Subject to the constraints
 2x_{1} 3 x_{2}  5 x_{3} + S1 =  2
3 x_{1} + x_{2} + 7 x_{3} + S_{2} = 3
x_{1} + 4 x_{2} + 6 x_{3} + S_{3} = 5
where x_{1}, x_{2}, x_{3}, S_{1}, S_{2} and S_{3} 0
Putting x_{1} = x_{2} = x_{3} = 0 the vertical basic infeasible solution is S_{1} =  2, S_{2} = 3, S_{3} = 5
This information is written in the following table.
First Infeasible Solution
C_{j} 
C_{j} 
2 
2 
4 
0 
0 
0 

↓ 
Basic Variables 
Solution Variable 
x_{1} 
x_{2} 
x_{3} 
S_{1} 
S_{2} 
S_{3} 
0 
S_{1} 
2 
2 
3 
5 
1 
0 
0 
0 
S_{2} 
3 
3 
1 
7 
0 
1 
0 
0 
S_{3} 
5 
1 
4 
6 
0 
0 
1 

Z_{j} 
0 
0 
0 
0 
0 
0 
0 

(C_{j}Z_{j}) 
2 
2 
4 
0 
0 
0 
Step IV. Since C_{j}  Z_{j} are either 0 or  ve and solution variable is _ ve the solution is optimal but infeasible. Hence we proceed to step V.
Step V. The row containing the most negative solution variable is S_{1}, hence it is the key row and S_{1} is the row to be replaced.
We have eave 1, 2/3, 4/5 ratios only since 2/3 is the smallest ratio x_{2} is the variable replacing S_{1} and key element is 3 circled in the table.
Step VII. Make the key element unity and find the new values of S_{2} and S_{3} by using the following relationship.
New element = Old row element  [(Intersectional element in old row) × (Corresponding element in replacing row)]
By making key element unity the new values of row S_{1} (to be replaced by x_{2}) are 2/3, 2/3, 1, 5/3, 1/3, 0, 0.
Step I. Convert the minimisation problem into a maximisation problem
Minimise Z = – 2y_{1} + 3 y_{2} + 5 y_{3}
or Maximise Z* = 2 y_{1} – 3 y_{2} – 5 y_{3}
Step II. Make RHS of the constraints positive
The second constraint becomes 2 y_{1} + 4 y_{2} – y_{3} ≤ 2
Step III. Make the problem as N + S coordinate problem.
Introducing slack and artificial variables
Maximise Z** = 2 y_{1} – 3 y_{2} – 5 y_{3} + 0S_{1} + 0S_{2} + 0S_{3} – MA_{1} – MA_{3}
Subject to – 2 y_{1} – 3 y_{2} – S_{1} + A_{1} = 5
2 y_{1} + 4 y_{2} – y_{3} + S_{2} = 2
y_{1} + 3 y_{3} – S_{3} + A_{3} = 3
y_{1}, y_{2}, y_{3}, S_{1}, S_{2}, S_{3}, A_{1}, A_{3} ≥ 0
S_{2} is the key row, y_{2} the key column and (4) is the key element S_{2} is the departing row and y_{2} is the entering variable.
Step V. Optimality Test. C_{j} – Z_{j} is + ve in same column, the solution is not optimal. New elements of y_{2} are obtained by dividing the whole row by 4.
New elements of A, row are obtained using the relationship.
New element = Old row element – [(intersectional element in old row) × (Corresponding element in replacing row)]
S_{3} = 0 – [ 3 × 0] = 0
A_{1} = 1 – [ 3 × 0] = 1
A_{3} = 0 – [ 3 x 0] = 0
Element y_{1} = 1, y_{2}=0, y_{3}=3, S_{1}=0, S_{2}=0, S_{3}=1, A_{1}=0, A_{3}=1.
Iterating thrice we get
Optimality Test
The above is the optimal basic feasible solution, since all values of C_{j} – Z_{j} are either 0 or – ve.
Recent Comments