We have till now seen in this chapter, the type of problems where profit had to be maximised and the constraints were of the type ≤. However, there could be problems where the objective function has to be minimised (like the availability of funds, raw material or the costs of operations have to be minimised) and the constraints involved may be of the type ≥ or =. In such cases, the simplex method is somewhat different and is discussed in the form of following steps.
Step 1. Formulation of mathematical model
Now we subtract the surplus variables S_{1}, S_{2}, …. S_{n} etc to convert the inequalities into equations.
i.e., Minimise Z = C_{1} x_{1} + C_{2} x_{2} + C_{3} x_{3} + …. + C_{n} X_{n} + 0S_{1} + 0S_{2} + …. + 0S_{n}
Subject to the constraints
As in the maximisation problem, initial basic solution is obtained by putting x_{1} = x_{2} = x_{n} = 0
So –S_{1}=b_{1} or S_{1}=b_{1}
– S_{2} = b_{2} or S_{2} = – b_{2}
– S_{m} = b_{m} or S_{m} = – b_{m}
It may be seen that S_{1}, S_{2,} …. S_{m} being negative violate the nonnegativity constraint and hence is not feasible. Hence, in the system of constraints we introduce m new variables A_{1}, A_{2} …. A_{m} known as artificial variable. By introducing these variables the equations are
a_{11} x_{1} + a_{12} x_{2} + a_{13} x_{3} + …. + a_{1n} x_{n} – S_{1} + A_{1} = b_{1}
a_{21} x_{1} + a_{22} x_{2} + a_{23} x_{3} + …. + a_{2n} x_{n} – S_{2} + A_{2} = b_{2}
a_{m1} x_{1} + a_{m2} x_{2} + a_{m3} x_{3} + …. + a_{mn} x_{n} – S_{m} + A_{m} = b_{m}
where x_{j} ≥ 0 (i = 1, 2, 3, …. n)
S_{j} ≥0 (j=1,2,3, …. m)
A_{j} ≥ 0(j=1,2,3, …. m)
As we have introduced artificial variables A_{1}, A_{2} …. A_{m} this has to be taken out of the solution. For this purpose, we introduce a very large value (M) assigned to each of artificial variable and zero to each of the surplus variables as the coefficient values in the objective function. The problem now becomes
Minimise Z=C_{1}x_{1} + C_{2}x_{2} + C_{3}x_{3} + …. + C_{n}x_{n}
+ 0S_{1} + 0S_{2} + …. + 0S_{m} +
MA_{1} + M A_{2} + …. + M A_{m}
Subject to the constraints
a_{11} x_{1} + a_{12} x_{2} + a_{13} x_{3} + …. + a_{1n} x_{n} – S_{1} + A_{1} = b_{1}
a_{21} x_{1} + a_{22} x_{2} + a_{23} x_{3} + …. + a_{2n} x_{n} – S_{2} + A_{2} = b_{2}
a_{m1} x_{1} + a_{m2} x_{2} + a_{m3} x_{3} + …. + a_{mn} x_{n} – S_{m} + A_{m} = b_{m}
Step 2. Setting up of initial simplex table
Here, we allot 0 values to variables x_{1} = x_{2} = x_{3} =…. = x_{n} = 0 so that A_{1} = b_{1}, A_{2} = b_{2} …. A_{m}=b_{m}.
Table 3.15
Initial simplex table
CB 
Solution mix 
C_{j} 
C_{1}, C_{2}, C_{3}, …. C_{n}, 0 0 M … M  Minimum ratio 
Solution values 
x_{1}, x_{2}, x_{3} …. x_{n }S_{1}, S_{2}, S_{3} …. S_{n}  
CB_{1} CB_{2} CB_{n} 
A_{1} A_{2} A_{n} 
b_{1} b_{2} b_{n} 
a_{11} + a_{12} …. + a_{1n} 1 0 0 1 0 … 0
a_{21} + a_{22} …. + a_{2n} 0 1 0 0 1 … 0 a_{m1} + a_{m2} …. + a_{mn} 0 0 1 0 0 1


Z_{j} (C_{j}Z_{j}) 
0 0 0 0 0 0 0 0 … 0
C_{1} C_{2} … C_{n} 0 0 0 M M … M 

Step 3. Test for optimality
Calculate the elements of (C_{j} – Z_{j}) row
(a) If all (C_{j} – Z_{j}) ≥ 0 then the basic feasible solution is optimal.
(b) If anyone (C_{j} – Z_{j}) ≥ 0 then pick up the largest negative number in this row. This is the key column and determines the variable entering the solution,
Now the second simplex table can be constructed.
Step 4. Test for feasibility
Determine the key row and key number (element) in the same manner as is done in the maximisation problem.
Example 3.5. A special diet for a patient in the hospital must have at least 8000 units of vitamins, 100 units of minerals and 2800 units of calories. Two types of foods X and Y are available in the market at the cost of Rs. 8 and Rs. 6 respectively. One unit of X contains 400 units of vitamins, 2 units of minerals and 80 units of calories. One unit of food B contains 200 units of vitamins, 4 units of minerals and 80 units of
calories. What combination of foods X and Y be used so that the minimum requirement of vitamins, minerals and calories is maintained and the cost incurred by the hospital is minimised? Use simplex method.
Sol. Mathematical model of the problem is as follows
Minimise Z = 8x_{1} + 6x_{2}
Subject to the constraints
400x_{1} + 200x_{2} ≥ 8000 (Constraint of minimum vitamins)
2x_{1} + 4x_{2} ≥ 100 (Constraint of minimum minerals)
80x_{1} + 80x_{2} ≥ 2800 (Constraint of minimum calories)
x_{1}, x_{2} ≥ 0 (Nonnegativity constraint)
where x_{1} and x_{2} are the number of units of food X and food Y. Now the constraint inequalities can be converted into equations. Here, we take an initial solution with very high cost, as opposed to the maximisation problem where we had started with an initial solution with no profit. We subtract surplus variables S_{1}, S_{2}, and S_{3}.
400x_{1} + 200x_{2} – S_{1} = 8000
2x_{1}+4x_{2} S_{2}=100
80x_{1} + 80x_{2} – S_{3} = 2800
The surplus variables S_{1}, S_{2} and S_{3} introduced in these equations represent the extra unit of vitamins, minerals and calories over 8000 units, 100 units and 2500 units in the least cost combination.
Let x_{1}, x_{2} be zero in the initial solution.
Hence S_{1} = – 8OOO
S_{2} = 100
S_{3} =2500
This is not feasible as S_{1}, S_{2} and S_{3 ≥} 0 and cannot be negative. We have to see that S_{1}, S_{2} and S_{3} do not appear (as they are – ve) in the initial solution. So if x_{1}, x_{2} and S_{1}, S_{2}, S_{3} are all zero, new foods which can substitute food X and Y must be introduced. A_{1}, A_{2} and A_{3} are the artificial variables to be introduced. Let the artificial variables (foods) be of are very large price, M per unit
400x_{1} + 200x_{2} – S_{1} + A_{1} = 8000
2x_{I}+4x_{2}S_{2}+A_{2 }=100
80x_{1} + 80x_{2} – S_{3} + A_{3} = 2800
and Z objective function
Minimise Z = 8x_{1} + 6x_{2} + 0S_{1} + 0S_{2} + 0S_{3} + MA_{1} + MA_{2} + MA_{3}
where x_{1}, x_{2}, S_{1}, S_{2}, S_{3} ,A_{1}, A_{2}, A_{3} 0
Now, it is possible to set up initial solution by putting x_{1} = x_{2} = S_{1} = S_{2} = S_{3} = 0 in such a manner that = 8000, A_{2} = 100 and A_{3} = 2800.
Table 3.16
First simplex table

C_{j} 
8 
6 
0 
0 
0 
M 
M 
M 


C_{B} 
B Solution mix variables 
B (=x_{B}) Solution values 
x_{1} 
x_{2} 
S_{1} 
S_{2} 
S_{3} 
A_{1} 
A_{2} 
A_{3} 
Min ratio 
M 
A_{1} 
8000 
400 
200 
1 
0 
0 
1 
0 
0 
20 
M 
A_{2} 
100 
2 
4 
0 
1 
0 
0 
1 
0 
50 
M 
A_{3} 
2800 
80 
80 
0 
0 
1 
0 
0 
1 
35 
Z_{j} 
482M 
284M 
M 
M 
M 
M 
M 
M 


(C_{j}Z_{j}) 
8482M 
6284M 
M 
M 
M 
0 
0 
0 
x_{1} is the key column entering the solution, A is the departing row and 400 (circled) in the table is the key number (element).
Now apply the row operations
Table 3.17 second simplex table

C_{j} 
8 
6 
0 
0 
0 
M 
M 
M 
Minimum ratio 

C_{a} 
Solution mix variable (=B) 
Solution values (b=X_{B}) 
x_{1} 
x_{2} 
S_{1} 
S_{2} 
S_{3} 
A_{1} 
A_{2} 
A_{3} 

8 
x_{1} 
20 
1 
0 
0 

0 
0 
40 

M 
A_{2} 
60 
0 
3 
1 
0 

1 
0 
20 

M 
A_{3} 
1200 
0 
40 
0 
1 

0 
1 
30 

Z_{j} 
8 
4+43 M 
4+41 M/200 
M 
M 

M 
M 


(C_{j}Z_{j}) 
0 
243 M 
441 M/200 
M 
M 

0 
0 
Value of Z calculated as follows
Z_{j} (S_{2}) = M
Z_{j} (S_{3}) = M
Z_{j} (A_{2}) = M
Z_{j}(A_{3}) = M
It is clear from the above table, that x_{2} enters the solution and A_{2} deports, using the following row operations, we introduce x_{2} and remove A_{1}.
Table 3.18 Third simplex table

C_{j} 
8 
6 
0 
0 
0 
M 
M 
M 
Minimum ratio 

C_{B} 
Solution Mix variable (=B) 
Solution values b(=x_{B}) 
x_{1} 
x_{2} 
S_{1} 
S_{2} 
S_{3} 
A_{1} 
A_{2} 
A_{3} 

8 
x_{1} 
10 
1 
0 
0 
– 
– 
0 
60 

6 
x_{2} 
20 
0 
1 
0 
– 
– 
0 
60 

M 
A_{3} 
400 
0 
0 
1 
– 
– 
1 
30 

Z_{j} 
8 
6 
M 
– 
– 
M 


(C_{j}Z_{j}) 
0 
0 
M 
– 
– 
0 
It can be seen S_{2} has to be introduced and A_{3} has to depart. This procedure can be adopted for further improving the solution by constructing fourth simplex table and so on.
Recent Comments