In large sized linear programming problems, the solution cannot be obtained by the graphical method and hence a more systematic method has to be developed to find the optimal solution. The 'Simplex Method' developed by George B. Dantzig is an efficient algorithm to solve such problems. The simplex method is an iterative procedure for moving from an extreme point with a low profit value to another with a higher profit value until the maximum value of the objective function is achieved.

An application of the simplex method is illustrated below with the problem solved by the graphical method.

Maximization

Example 

Maximize Z: 70q₁ + 40q₂

subject to:

The first step in applying the simplex method is to convert all inequalities into equations. This conversion could be accomplished by utilizing the concept of slack or unused resources. If we define:

  Then the constraints will be:

q₁  >  0, q₂ > 0, S₁ > 0

S₂  >  0, S_L > 0, S_C > 0

The profit contribution of slacks is taken as 0 so that the objective function is

         70q₁ + 40q₂ + 0S₁ + 0S₂ + 0S_L + 0S_C

which is to be maximized. Let us call the original variables q₁ and q₂ as regular variables and the others as slack variables.

We must first form an initial solution to the constraints. This is obtained by assigning the value '0' to the regular variables q₁ and q₂, i.e., we shall start at the point 0 in the graph. The values of slack variables will now be:

                   S₁      =     120

                   S₂      =     40

                   S_L     =     200

                   S_C     =     360

The non-flow variables are called basic variables and the others are called non-basic variables (Basic: S₁, S₂, S_L, S_C; Non-basic: q₁, q₂).

We shall now construct the initial tableau and update it eventually. The explanation is given at the end of each table.

Explanation

1. Columns (4) to (9) represent all the variables that appear in the problem, that is, q₁, q₂, S₁, S₂, S_L and S_C.

2. First, fill in the second row with the variables.

3. Fill in the first row with the profit contribution of these variables. The profit contributions are the coefficients of the variables in the objective function.

4. Fill column (2) with the slack variables, S₁, S₂, S_L, S_C.

5. Fill column (1) with the profit contribution of variables that appear in column (2).

6. Fill column (3) with the solution values of the variables in column (2).

7. Column (4) is filled with coefficients of q₁ in the constraints. Similarly, columns (5) to (9) are filled with the coefficients of q₂, S₁, S₂, S_L and S_C respectively, in the constraints.

8. The value in the profit cell {column (3), last row} is obtained by multiplying the elements of column (1) with the elements of column (3), that is,

0 x 120 + 0 x 40 + 0 x 200 + 0 x 360 = 0

      This implies that, for the initial solution q₁ = 0, q₂ = 0 (that is, no production), the profit realized is 0.

9. The cells in the last row under columns (4) to (9) are called (Z_j - C_j) cells.

These values indicate the increase in the objective function per unit increase in the value of the variable currently at 0. In the initial tableau, this row is obtained by subtracting C_j from Z_j where Z_j is the summation of products of each value in columns (4) to (9) and the value in column (1).  For instance, the Z_j value for column (4) is 2 x 0 + 0.8 x 0 + 3 x 0 + 4 x 0 = 0. For column (5), Z_j is 1 x 0 + 0 x 0 + 2 x 0 + 3 x 0 = 0.

Tableau 1 is now complete. At the end of each tableau, we should decide whether to update it to obtain a better solution, or to stop. This is done by the following steps:

Step 1: Is the solution indicated in the tableau optimal?

The answer to this question is obtained by looking at the (Z_j - C_j) values in the last row. As mentioned above, these values indicate the profit that could be gained by increasing the production levels.

For example, the Z_j - C_j value corresponding to variable q₁ is -70. This indicates that, by not producing type A castings, the foundry has lost Rs.70 per unit and hence by increasing the production level of type A castings, the foundry can increase its profit at the rate of Rs.70 per unit increase in production. Similarly, the foundry can increase its profit by Rs.40 by increasing the production level of type B castings. Thus, as there is scope for improving the profit, we have not reached the optimal solution.

Thus, we can answer the initial question by looking at all the (Z_j - C_j) values. If all these values are greater than or equal to zero, it implies that we have reached the optimal solution and hence we should stop. If one of the Z_j - C_j values is negative, then we should go to the next step.

Step 2: Find the variable to 'enter solution'

This means identifying the product for which the production level has to be increased. We have seen that it is optimal to increase the production level of q₁. The rule is:

Identify the least negative Z_j - C_j value. Thus the corresponding (non-basic) variables will increase in value. In this case, q₁ has been selected to be a basic variable.

Tableau 2

Step 3: Find the variable to 'leave solution'

This is obtained by answering the following question:

In Step 2, let us decide to increase the value of q₁, that is, increase the production level of type A castings. By how much can the production of type A castings be increased?

The answer is this: Increase the production until one of the resources gets exhausted. The requirement per unit of q₁ is given in Column (4) of the tableau. If the value is positive, it means that there is a positive requirement. If the value is 0 or negative, it means that particular resources are not required for increasing the value of q₁. By applying this simple logic, it is observed that the minimum positive ratio of the elements of Column (3) with the elements of the column selected in Step 2, that is, column (4) will indicate the resource which will be the first to be exhausted.

The minimum value is 50 corresponding to the ratio 40/0.8 and the corresponding variable is S₂, that is, the resource raw material 2, gets exhausted by producing 50 units of type A castings. We cannot increase the value of q₁ beyond 50 at this stage. As the value of S₂ reduces to 0, we replace S₂ by q₁ in Column (2). We then identify the row corresponding to S₂.

Step 4: Identify the pivot element

This is the one element common to the column identified in Step 2 and the row identified in Step 3, that is, 0.8. This element is circled in the table. The column and row where the pivot element lies are called pivot column and pivot row respectively.

We are now ready to update Tableau 1 and construct Tableau 2. The format of Tableau 2 is the same as Tableau 1. The rules for updating are explained below in Tableau 2.