Example:

Beaver Creek Pottery Company

X₁ = # of bowls to produce each day

X₂ = # of mugs to produce each day

Z_max = $40X₁ + $50X₂ + 0S₁ + 0S₂

The company needs to know how many bowls and mugs to produce each day in order to maximize profit.

Subject to the following constraints:

X₁ + 2X₂ + 1S₁ + 0S₂ = 40 labor, hr

4X₁ + 3X₂ + 0S₁ + 1S₂ = 120 clay, lb

X₁, X₂, S₁, S₂ >= 0 nonnegativity

(2^nd row) Record the model variables:

• decision variables
• slack variables

Determine the basic feasible solution. A basic feasible solution:

• satisfies the constraints
• contains as many variables with nonnegative values as there are model constraints (recall n-m)

Why is the following the basic feasible solution?

X₁ = 0 and X₂ = 0 and S1 = 40 and S2 = 120

Record the non-zero variables (basic variables) in this solution (2^nd column) and the quantity of those variables (in the 3^rd column).

Record the Cj values (the objective function coefficients, representing the per unit contribution to profit or cost):

• (1^st row) for all the decision variables
• (1^st column) for the basic variables (those in the basic feasible solution)

(4^th-7^th columns) Record the coefficients for the decision variables and the slack variables in the constraint equations.

(5^th row) Compute the Z_j values (the gross profit). To do this, multiply each C_j value in the 1^st column by each column value under Quantity, the decision variables, and the slack variables; then sum each set of values.

Example:

0 * 40 = 0

0 * 120 = 0

0 + 0 = 0

Example:

0 * 1 = 0

0 * 4 = 0

0 + 0 = 0

(6^th row) Compute the Cj – Zj values (net increase in profit associated with one additional unit of each variable). To do this, subtract the Z_j row values from the C_j (top row) values.

Example:

40 – 0 = 40

Examine the profit represented by this solution. The profit (the Z value) is found in the Z_j row under the Quantity column. Recall that the solution is to produce no bowls and no mugs. Why is this solution not optimal?

Therefore, we want to move to a solution point that will give a better solution. We want to produce some bowls or some mugs; therefore one of these nonbasic variables (variables not in the present basic feasible solution) will enter the solution and become basic.

And one of the variables must leave the solution. Why?

Which variable shall enter the solution?

Choose the highest positive value in C_j – Z_j row. It is 50, in this case, and belongs to X₂.

X₂ becomes the pivot column.

Which variable shall leave the solution?

This analysis is performed by dividing the Quantity values of the basic solution variables by the pivot column variables. The leaving variable is the one with the smallest positive quotient.

40 / 2 = 20

120 / 3 = 40

S₁ becomes the pivot row.

The value 2 at the intersection of the pivot row and the pivot column is called the pivot number.

We are now ready to the second simplex tableau and a better solution.