Determine whether the problem is a standard maximization problem. In these types of problems, the following conditions must be satisfied: The function should be maximized, the constants in the inequalities must all be non-negative, the variables must all be non-negative and the inequalities must all be less than or equal to. For example, the following is a standard maximization problem:
Maximize F = 5x + 6y subject to the constraints
4x + 2y <= 10
3x + y <= 5
x + 2y <= 8
where x and y are both non-negative.
Convert each inequality into an equality by adding a slack variable to each inequality. For instance, after adding slack variables, the inequalities become:
4x + 2y + u = 10
3x + y + v = 5
x + 2y + w = 8
Ensure all of the equations, including the function, have the variables on the left side and the constants on the right. For instance, in the example all of the equations already have the right form except for the function. Rewrite the function as indicated:
-5x - 6y + F = 0
Convert the system of equations into a matrix called the initial simplex tableau. Each row of the matrix corresponds to the coefficients of the equations. Put the numbers of the function in the bottom row. For instance, the initial simplex tableau of the example is:
x y u v w F
4 2 1 0 0 0 10
3 1 0 1 0 0 5
1 2 0 0 1 0 8
-5 -6 0 0 0 -1 0
Find the most negative indicator in the initial simplex tableau. The "indicators" are the numbers in the bottom (except for the bottom-most number). In the example, the most negative indicator is -6 in the second column. This column is called the pivot column.
Find the smallest ratio in the pivot column. Form ratios by taking the right-most number in each row and dividing it by a corresponding number in the pivot column. Do this for every row except the indicator row. For instance, the ratios in the example are:
10/2 = 5
5/1 = 5
8/2 = 4
The smallest ratio in the pivot column is 4, which corresponds to the third row.
Use matrix row operations to change all the other numbers in the pivot column to 0. For instance, subtract the first row by the pivot row to form a 0 in the first row. Subtract twice the second row by the pivot row to form a 0 in the second row. The result is shown below:
x y u v w F
3 0 1 0 -1 0 2
5 0 0 2 -1 0 2
1 2 0 0 1 0 8
-8 0 0 0 -3 -1 -24
Check whether all the indicators are non-negative. If so, then you are done. Otherwise, go to Step 5.
Read off the solution from the final matrix. For instance, if the final matrix is
x y u v w F
1 0 0 3 4 0 4
0 3 0 4 4 0 6
0 0 2 4 3 0 4
0 0 0 3 3 1 5
look for the columns with a single non-zero number. This column gives you the value of that variable in the solution. To find the value, divide the right-most number by the non-zero number. In this final matrix, the solution is:
x = 4/1 or 4
y = 6/3 or 2
u = 4/2 or 2
and the maximum value of the function F is 5.