Step I. Formulate the problem
The problem must be put in the form of a mathematical model. The standard form of the LP model has the following properties.
a) An objective function, which has tc be maximized or minimized.
b) All the constraints can be put in the form of equations.
c) All the variables are nonnegative.
Step II. Set up the initial simplex table with slack variable or surplus variables in the solution,
Step III. Determine the decision variables which are to be brought in the solution.
Step IV. Determine which variables to replace.
Step V. Calculate new row values for entering variables.
Step VI. Revise remaining rows.
Repeat step III to VI till an optimal solution is obtained. This procedure can best be explained with the help of a suitable example,
Sol.
Step 1 Formulate the problem,
Problem is already stated in the mathematical model.
Step 2. Set up the initial simplex table with the slack variables in solution. By introducing the slack variables, the equations in step I, i.e., the mathematical model can be rewritten as follows.
3X_{1} + 2X_{2} + S_{1} = 1,200
2X_{1} + 6X_{2} + S_{2} = 1,500
X_{1} + S_{3} = 350
X_{2} + S_{4} = 200
where S_{1}, S_{2} , S_{3} and S_{4} are the slack variables. Let us rewrite the above equation in a symmetrical manner so that all the four slacks S_{1}, S_{2}, S_{3} and S_{4} appear in all the equations.
3X_{1} + 2X_{2} + 1S_{1} + 0S_{2} + 0S_{3} + 0S_{4} = 1,200
2X_{1} + 6X_{2} + 0S_{1} + 1S_{2} + 0S_{3} + 0S_{4} = 1,500
1X_{1} + 0X_{2} + 0S_{1} + 0S_{2} + 1S_{3} + 0S_{4} = 350
0X_{1} +1X_{2} + 0S_{1} + 0S_{2} + 0S_{3} + 1S_{4} = 200
Let us also write the objective function Z by introducing the slacks in it.
Z = 10X_{1} + 20X_{2} + 0S_{1} + 0S_{2} + 0S_{3} + 0S_{4}
The first simplex table can now be written as.
Table 3.1
C_{j} 
Solution Mix 
Rs. 10 
Rs. 20 
0 
0 
0 
0 
Contribution unit quantity 
X_{1} 
X_{2} 
S_{1} 
S_{2} 
S_{3} 
S_{4} 

0 
S_{1} 
3 
2 
1 
0 
0 
0 
1200 
0 
S_{2} 
2 
6 
0 
1 
0 
0 
1500 
0 
S_{3} 
1 
0 
0 
0 
1 
0 
350 
0 
S_{4} 
0 
1 Key element 
0 
0 
0 
1 
200 Key Row 
Z_{j} (C_{j}Z_{j}) 
0 
0 
0 
0 
0 
0 
0 

10 
20 Key column 
0 
0 
0 
0 
The first simplex table is shown in Table 3.1. The table is explained as below:
 Row 1 contains C_{j} or the contribution to total profit with the production of one unit of each product X_{1} and X_{2}. This row gives the coefficients of the variables in the objective function which will remain the same. Under column 1 (C_{j}) is provided profit per unit of 4 variables S_{1}, S_{2}, S_{3}, S_{4} which is zero.
 All the variables S_{1}, S_{2}, S_{3}, S_{4} are listed under Solution Mix. Their profit is zero and written under column 1 (C_{j}) as explained above.
 The constraint variables are written to the right of solution mix. These are X_{1}, X_{2}, S_{1}, S_{2} L_{3} and S_{4}.Under these are written coefficient of variables and under each are written the coefficients of particular variable as they appear in the constraint equations. For example, the coefficients X_{1}, X_{2}, S_{1}, S_{2}, S_{3} and S_{4} in first constraints equation are 3, 2, 1, 0, 0 and 0, respectively which are written under these variables in the first level. Similarly, the remaining 3 rows represent the coefficients of the variables as they appear in the other 3 constraint equations. The entries in the quantity column represent the right hand side of each constraint equation. These values are 1,200, 1,500, 350 and 200 respectively, for the given problem.
 The Z_{j} values in the second row from the bottom refer to the amount of gross profit that is given up by the introducing one unit of that variable into the solution. The subscript j refers to the specific variable being considered. The Z_{j} value under the quantity column is the total profit for their solution. In the initial column all the Z_{j} values will be zero because no real product is being manufactured and hence there is no gross profit to be lost if they are replaced.
 The bottom row of the table contains net profit per unit obtained by introducing one unit of a given variable into the solution. This row is designated as the C_{j} – Z_{j} row. The procedure for calculating Z_{j} and C_{j}– Z_{j} values is given below:
Calculation of Z_{j},
C_{j} × X_{1} 0 × 3 = 0 + 0 × 2 = 0 + 0 × 1 = 0 + 0 × 0 =0 
C_{j} × X_{2} 0 × 2 =0 + 0 × 6 = 0 + 0 × 0 = 0 + 0 × 1 = 0 
C_{j} × S_{1} 0 × 1 = 0 + 0 × 0 = 0 + 0 × 0 = 0 + 0 × 0 = 0 
Z_{X1}=0 
Z_{X2}=0 
Z_{S1}=0 
Similarly, Z_{S2}, Z_{S3} and Z_{S4} can be calculated as 0 each.
Calculation of C_{j} – Zj
C_{X1}Z_{XI} =100 =10
C_{X2} – Z_{X2} = 20 – 0 = 20
C_{S1} – Z_{S1} = 0 – 0 = 0
C_{S2} – Z_{S2} = 0 – 0 = 0
C_{S3} – Z_{S3} = 0 – 0 = 0
C_{S4} – Z_{S4} = 0 – 0 = 0
The total profit for this solution is Rs. zero.
Step 3. Determine the variable to be brought into the solution. An improved solution is possible if there is a positive value in C_{j} – Z_{j} row. The variable with the largest positive value in the C_{j} – Z_{j} row is subjected as the objective is to maximize the profit. The column associated with this variable is referred to as ‘key column’ and is designated by a small arrow beneath this column. In the given example, 20 is the largest possible value corresponding to X_{2} which is selected as the key column.
Step 4. Determine which variable is to be replaced. To make this determination, divide each amount in the contribution quantity column by the amount in the comparable row of key column, X_{2} and choose the variable associated with smallest quotient as the one to be replaced. In the given example, these values are calculated as
for the S_{1} row – 1200/2 = 600
for the S_{2} row – 1500/6 = 250
for the S_{3} row – 350/0 = ∞
for the S_{4} row – 200/1 = 200
Since the smallest quotient is 200 corresponding to S_{4}, S_{4} will be replaced, and its row is identified by the small arrow to the right of the table as shown. The quotient represents the maximum value of X which could be brought into the solution.
Step 5. Calculate the new row values for entering the variable. The introduction of X_{2} into the solution requires that the entire S_{4} row be replaced. The values of X_{2}, the replacing row, are obtained by dividing each value presently in the S_{4} row by the value in column X_{2} in the same row. This value is termed as the key or the pivotal element since it occurs at the intersection of key row and key column.
0/1 = 0; 1/1 = I ; 0/1 = 0; 0/1 = 0; 0/1 = 0; – 1/1 = 1 ; 200/1 = 200
Step 6. Update the remaining rows. The new S_{2} row values are 0, 1, 0, 0, 1 and 200 which are same as the previous table as the key element happens to be 1. The introduction of a new variable into the problem will affect the values of remaining variables and a second set of calculations need to be performed to update the initial table. These calculations are performed as given here:
Updated S_{1} row = old S_{1} row – intersectional element of old S_{1} row X corresponding element of new X_{2} row
= 3 – [2 × 0] = 3
= 2 – [2 × 1] = 0
= 1 – [2 × 0] = 1
= 0 – [2 × 0] = 0
= 0 – [2 × 0] = 0
= 0 – [2 × 1] = 2
=1200 – [2 × 200] = 800
Similarly, the updated elements of S_{2} and S_{3} rows can be calculated as follows:
Elements of updated S_{2} row 
Elements of updated S_{3} row 
2–[6×0]=2 6[6×1]=0 0[6×0]=0 1[6×0]=1 0[6×0]=0 0[6×1]=6 1500[6×200]=300 
1[0×0]=1 0[0×1]=0 0[0×0]=0 0[0×0]=0 1[0×0]=1 0[0×1]=0 350[0×200]=350 
Rewriting the second simplex table with the updated elements as shown in Table 3.2 below:
Solution Mix 
Rs.10 
Rs.20 
0 
0 
0 
0 
Contribution 
Ratio 

Cj 
X_{1} 
X_{2} 
S_{1} 
S_{2} 
S_{3} 
S_{4} 
Quantity 

0 
S_{1} 
3 
0 
1 
0 
0 
2 
800 
266.7 
0 
S_{2} 
2 
0 
0 
1 
0 
6 
300 
150 
0 
S_{3} 
1 
0 
0 
0 
1 
0 
350 
350 
20 
X_{2} 
0 
1 
0 
0 
0 
1 
200 

Z_{j} 
0 
20 
0 
0 
0 
20 
4000 

(C_{j}Z_{j}) 
10 
0 
0 
0 
0 
20 
The new variable entering the solution would be X_{1}. It will replace the S_{2} row which can be shown as follows:
For the S_{1} row 800/3 = 266·7
For the S_{2} row 300/2 = 150
For the S_{3} row 350/1 = 350
For the S_{4} row 200/0 = 00
As the quotient 150 corresponding to S_{2} row is the minimum, it will be replaced by X, in the new solution. The corresponding elements of S_{2} row can be calculated as follows:
New elements of S_{2} row to be replaced by X_{1} are
2/2 = 1; 0/2 = 0; 0/2 = 0; 1/2 = 1/2; 0/2 = 0; – 6/2 = – 3; 300/2 = 150;
The updated elements of S_{1} and S_{3} rows can be calculated as follows:
Elements of updated S_{1} row
3 – [3 × 1] = 0
0 – [3 × 0] = 0
1 – [3 × 1/2] = 1
1 – [3 × 0] = 0
0 – [3 × 3] = 7
800 – [3 × 150] = 350
Elements of updated S_{3} row
1 – [1 × 1] = 0
0 – [1 × 0] = 0
0 – [1 × 0] = 0
0 – [1 × 1/2] = 1/2
1 – [1 × 0] = 1
0 – [1 × 3] = 3
350 – [1 × 150] =200
Elements of updated X_{2} row
0[0 ×1] =0
1 [0 × 0] = 1
0 [0 × 0] = 0
0[0 × 1/2] = 0
0[0 × 0] = 0
1 [0 × – 3] = 1
200 – [0 × 150] = 200
Revised simplex table can now be written as shown in Table 3.3 below:
C_{J} 
Solution 
Rs.10 
Rs.20 
0 
0 
0 
0 
Contribution 
Min Ratio 
Mix 
X_{1} 
X_{2} 
S_{1} 
S_{2} 
S_{3} 
S_{4} 
Quantity 

0 
S_{1} 
0 
0 
1 
3/2 
0 
7 
350 
50 
10 
X_{1} 
1 
0 
0 
1/2 
0 
3 
150 
50 
0 
S_{3} 
0 
0 
0 
1/2 
1 
3 
200 
66.7 
20 
X_{2} 
0 
1 
0 
0 
0 
1 
200 
200 
Z_{j} 
10 
20 
0 
5 
10 
10 
5500 

(C_{j}Z_{j}) 
0 
0 
0 
5 
0 
10 
Now the new entering variable will be S_{4} and it will replace S_{1} as shown below:
350/7 = 50
150/ 3 = 50
200/3 = 66.7
200/1 = 200
In these figures, 50 represent the minimum quotient which corresponds to row S_{1} .
The new elements of S_{1} row to be replaced by S_{4} can be calculated as follows:
The new elements of S_{1} row would be
0/7 =0; 0/7 =0; 1/7 = 1/7; (3/2) × (1/7) =3/14; 0/7=0; 1; 7/7 = 1; 350/7=50
The updated elements of the other rows can be calculated as follows:
Elements of updated X_{1} row
1 [ 3 × 0] = 1
0 [ 3 × 0] = 0
0[3 × 1/7] =3/7
½ [ 3 × 3/14] = – 1/7
0[3 × 0] =0
– 3 – [ 3 × 1] = 0
150 – [ 3 × 50] = 300
Elements of updated S_{3} row
0[3 × 0] =0
0 [3 × 0] = 0
0 [3 × 1/7] =3/7
– ½ [3 × – 3/14] = – 1/7
1 – [3 × 0] = 1
3 – [3 × 1] = 0
200 – [3 × 50] = 50
Elements of Updated X_{2} row
0[1×0] = 0
1 [1 × 0] = 1
0 [1 × 1/7] = 1/7
0[1 ×3/14] =3/14
0[1×0]=0
1[1×1]=0
200 – [1 × 50] = 150
The new simplex table can now be written as shown in Table 3.4.
Table 3.4
Solution Mix 
Rs.10 
Rs.20 
0 
0 
0 
0 
Contribution Quantity 

C_{j} 
X_{1} 
X_{2} 
S_{1} 
S_{2} 
S_{3} 
S_{4} 

0 
S_{4} 
0 
0 
1/7 
3/14 
0 
1 
50 
10 
X_{1} 
1 
0 
3/7 
1/7 
0 
0 
300 
0 
S_{3} 
0 
0 
3/7 
1/7 
1 
0 
50 
20 
X_{2} 
0 
1 
1/7 
3/14 
0 
0 
150 
Z_{f} 
10 
20 
10/7 
40/14 
0 
0 
6,000 

(C_{j}Z_{f}) 
0 
0 
10/7 
40/14 
0 
0 
6,000 
As there is no positive value in C_{j} – Z_{j} row it represents the optimal solution, which is given as:
X_{1} = 300 units: X_{2} = 150 units
And the maximum profit Z = Rs 6,000
Recent Comments