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_{1} + 40q_{2}
subject to:
2q_{1}

+ 
q_{2}

<120 
0.8q_{1}

+ 
0q_{2}

<40 
3q_{1}

+ 
2q_{2}

<200 
4q_{1}

+ 
3q_{2}

<360 
q_{1}

> 
0, q_{2}

>0 
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:
S_{1} 
= 
slack raw material1 
S_{2} 
= 
slack raw material2 
S_{L} 
= 
slack labor 
S_{C} 
= 
slack foundry capacity 
Then the constraints will be:
2q_{1} 
+ 
q_{2} 
+S_{1} 
= 120 
0.8q_{1} 
+ 
0q_{2} 
+S_{2} 
= 40 
3q_{1} 
+ 
2q_{2 } 
+S_{L } 
= 200 
4q_{1} 
+ 
3q_{2} 
+S_{C } 
= 360 
q_{1 }> 0, q_{2} > 0, S_{1} > 0
S_{2 }> 0, S_{L} > 0, S_{C} > 0
The profit contribution of slacks is taken as 0 so that the objective function is
70q_{1} + 40q_{2} + 0S_{1} + 0S_{2} + 0S_{L} + 0S_{C}
which is to be maximized. Let us call the original variables q_{1} and q_{2} 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_{1} and q_{2}, i.e., we shall start at the point 0 in the graph. The values of slack variables will now be:
S_{1} = 120
S_{2} = 40
S_{L} = 200
S_{C} = 360
The nonflow variables are called basic variables and the others are called nonbasic variables (Basic: S_{1}, S_{2}, S_{L}, S_{C}; Nonbasic: q_{1}, q_{2}).
We shall now construct the initial tableau and update it eventually. The explanation is given at the end of each table.
Explanation

Columns (4) to (9) represent all the variables that appear in the problem, that is, q_{1}, q_{2}, S_{1}, S_{2}, S_{L} and S_{C}.

First, fill in the second row with the variables.

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.

Fill column (2) with the slack variables, S_{1}, S_{2}, S_{L}, S_{C}.

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

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

Column (4) is filled with coefficients of q_{1} in the constraints. Similarly, columns (5) to (9) are filled with the coefficients of q_{2}, S_{1}, S_{2}, S_{L} and S_{C} respectively, in the constraints.

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_{1} = 0, q_{2} = 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_{1} 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_{1}. The rule is:
Identify the least negative Z_{j}  C_{j} value. Thus the corresponding (nonbasic) variables will increase in value. In this case, q_{1} 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_{1}, 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_{1} 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_{1}. 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_{2}, that is, the resource raw material 2, gets exhausted by producing 50 units of type A castings. We cannot increase the value of q_{1} beyond 50 at this stage. As the value of S_{2} reduces to 0, we replace S_{2} by q_{1} in Column (2). We then identify the row corresponding to S_{2}.
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.