Example 2.  Consider the region in the plane defined by the inequalities:  

           

2 (a).  Find the maximum of      over the region .  

Solution 2 (b).

Graph the domain defined by the constraints.

Enter the objective function.

Use the Mathematica subroutine LinearProgramming to find the solution (note carefully the "-" signs in front of the matrix and vector in the second and third arguments).

Use the simplex algorithm to find this solution.  

Enter the coefficients of the decision variables and right side of the tableau.  

Mathematica will fill in the columns for the slack variables and append a column of zeros which will be use to calculate the ratios for determining the pivot rows.

Aside.  The bottom line of the tableau corresponds to the augmented objective function

The first step in the simplex method is to determine an exchange variable.

There is a tie for choosing the first exchange variable is chosen since the current coefficients    are negative and is smaller any of the other coefficients  .  
This time, let us eliminate the exchange variable    and use  .

To determine the pivot row we need to consider the ratios  .  The pivot row    is chosen to be the row where the minimum ratio occurs.  Since    is smallest, use simplex Gaussian elimination to eliminate using the pivot row   .

From column 1 we see that .  The new point    in a feasible solution.  The simplex method has moved from its previous point   along the edge    to the point .

The second step in the simplex method is to determine the next exchange variable.

The second exchange variable is chosen since the current coefficient    is negative and is smaller any of the other coefficients  .  
Eliminate the exchange variable    and use  .  

To determine the pivot row we need to consider the ratios  .  The pivot row    is chosen to be the row where the minimum ratio occurs.  Since    is smallest, use simplex Gaussian elimination to eliminate using the pivot row   .

There are no negative coefficients in the bottom row, so we are done.

From column 1 and row 1 we see that .  From column 2 and row 3 we see that .  The new point    is the optimal feasible solution.  The simplex method has moved from its previous point   along the edge    to the point .  The value of the objective function at the solution point is located in the bottom row of the column "",  i.e.  .

We are done!

Aside.  The slack variables could be computed from (4) using the initial coefficients of the tableau:

       for rows    in the tableau.    

The bottom line of the tableau corresponds to the augmented objective function.

Graph the domain defined by the constraints and the level curves of the objective function.

(c) John H. Mathews 2005