The Simplex Algorithm

The Simplex Algorithm
Insert the slack variables, and find the slack equations.
Rewrite the objective function to match the format of the slack equations.
Write the initial simplex tableau.
Determine the pivot element.
Rules for Selection.
i. The most negative indicator in the last row of the tableau determines the pivot column.
ii. The pivot row is selected from among the slack equations by using the smallest-quotient rule.

Example:
Maximize P=3 x+4 y+z
Subject to:
x+2y+z?6
2x+2z?4
3x+y+z?9
x,y,z?0
The slack equations are:
x+2y+z+s_1=6
2x+2z+s_2 =4
3x+y +z+s_3 =9
x,y,z,s_1,s_2,s_3?0
Rewrite the objective function:
-3 x-4 y –z+P=0
The initial simplex tableau:
x y z s_1 s_2 s_3 P
s_1 1 2 1 1 0 0 0 6
s_2 2 0 2 0 1 0 0 4
s_3 3 1 1 0 0 1 0 9
-3 -4 -1 0 0 0 1 0
The most negative indicator in the last row is - 4 and so the pivot column is the y-column:
x y z s_1 s_2 s_3 P
y 1/2 1 1/2 1/2 0 0 0 3
s_1 2 0 2 0 1 0 0 4
s_1 5/2 0 1/2 -1/2 0 1 0 6
-1 0 -1 0 0 0 1 12

The next pivot column is the x-column and the smallest quotient is 2 (from the second row):
x y z s_1 s_2 s_3 P
y 0 1 0 1/2 -1/4 0 0 2
x 1 0 1 0 1/2 0 0 2
s_1 0 0 1/10 -1/2 -1/5 1 0 26/5
0 0 2 2 1/2 0 1 14

Pivoting on that element gives:
No negative indicators exist and so the maximum has been reached. The solution is:
y=2 ,x=2 ,z=0,s_1=26/5 ,? s?_2=0,s_3=0,P=14