SOLVING A  MAXIMIZATION  PROBLEM WITH THE SIMPLEX METHOD

Maximize E = 4x + 3y + 7z,

subject to x + 3y + 2z <= 120 and 2x + y + 3z <= 120,

with x, y, z >= 0.

We introduce two slack variables, s1 and s2, so that the constraints become

x + 3y + 2z + s1 = 120 and 2x + y + 3z + s2 = 120,

and we require x, y, z, s1, s2 >= 0.

>

restart:

>	with( linalg ):

We start with the tableau for corner 1, characterized by x=y=z=0.

>	mat := matrix(3,6, [1,3,2,1,0,120,2,1,3,0,1,120,4,3,7,0,0,E] );

The largest positive coefficient in the objective (bottom) row is 7, so the pivot column is column 3.

That is, z will lose status as corner variable.

Determine the ratios ...

>	evalf( 120/2 ); evalf( 120/3 );

The smallest positive ratio is 40, so the pivot row is row 2.

That is, s2 will gain status as corner variable.

Proceed with row operationsthat turn column 3 into an elementary column:

>	mat1 := mulrow( mat, 2, 1/3 );

>	mat2 := pivot( mat1, 2, 3 );

The above matrix is the tableau for corner 2, characterized by x=y=s2=0.

Look for the largest positive coefficient in the objective row, which is 2/3, in column 2.

So the pivot column is column 2.

That is, y will lose status as corner variable.

Determine the ratios ...

>	evalf( mat2[1,6]/mat2[1,2] ); evalf( mat2[2,6]/mat2[2,2] );

The smallest positive ratio occurs in row 1.  

So the pivot row is row 1.

That is, s1 will gain status as corner variable.

Proceed with row ops that turn column 2 into an elementary column ...

>	mat3 := mulrow( mat2, 1, 3/7 );

>	mat4 := pivot( mat3, 1, 2 );

The above tableau is for corner 3, characterized by x=s1=s2=0.

Look for the largest positive coefficient in the objective row.

Since there are none, we're done, and we can read off the optimal solution

from the tableau.  It says that the optimal solution occurs at x=0, y=120/7, z=240/7,

and the maximum value of E obtained there is 2040/7.