#9

The Simplex method

Exercise

 

Junk Jewelry Inc. makes both necklaces and bracelets from gold and platinum. The store has defined the following linear programming model for determining the number of necklaces and bracelets it needs to make in order to maximize profit.

Solve this linear programming model using the simplex method.

X1 = number of necklaces

X2 = number of bracelets

Zmax = 300X1 + 400X2 (profit, $)

Subject to:

3X1 + 2X2 <=18 (gold,oz)

2X1 + 4X2 <= 20 (platinum, oz)

X2 <= 4 (demand, bracelets)

X1,X2 >= 0

 

Transform the constraints into equations.

 

 

 

 

 

 

 

 

 

 

Simplex Tableau for this Model

1st Iteration

(Reference: Handout #8A)

 

 

 

       

 

Cj

Basic

Variables

Quantity

(RHS)

 

 

 

 

 

 

 

 

 

 

 

   

 

 

     

 

 

             

 

 

             

 

 

 

 

Zj

           

Cj - Zj

         

 

1) Enter the model variables and the basic variables for the basic feasible solution. Enter the quantities of the basic variables.

2) Record the Cj values in the 1st row and the 1st column.

3) Record the coefficients for the decision variables and the slack variables in the constraint equations.

4) Compute and record the Zj values.

 

 

 

 

 

 

 

 

5) Compute and record the Cj – Zj values.

 

 

6) Is this the optimal solution? If not, determine the pivot column (the variable that will enter the solution). Determine the pivot row (the variable that will leave the solution). Note the pivot number.

Simplex Tableau for this Model

2nd Iteration

(Reference: Handout #8B)

 

 

 

       

 

Cj

Basic

Variables

Quantity

(RHS)

 

 

 

 

 

 

 

 

 

 

 

   

 

 

     

 

 

             

 

 

             

 

 

 

 

Zj

           

Cj - Zj

         

1) Record the new basic variables and the Cj values for these variables. As you did in the first iteration, record all the decision variables and their coefficients from the objective function.

2) Compute and record the new pivot row values.

 

 

 

 

3) Compute and record the remaining rows (in this case, there are two).

 

 

 

 

 

4) Compute and record the Zj row.

 

 

 

 

5) Compute and record the Cj – Zj row.

6) Is this the optimal solution? If not, determine the pivot column (the variable that will enter the solution). Determine the pivot row (the variable that will leave the solution). Note the pivot number.

Simplex Tableau for this Model

3rd Iteration

 

 

 

       

 

Cj

Basic

Variables

Quantity

(RHS)

 

 

 

 

 

 

 

 

 

 

 

   

 

 

     

 

 

             

 

 

             

 

 

 

 

Zj

           

Cj - Zj

         

1) Record the new basic variables and the Cj values for these variables. As you did in the first iteration, record all the decision variables and their coefficients from the objective function.

2) Compute and record the new pivot row values.

 

 

 

 

3) Compute and record the remaining rows (in this case, there are two).

 

 

 

 

 

 

4) Compute and record the Zj row.

 

 

 

 

 

5) Compute and record the Cj – Zj row.

6) Is this the optimal solution? If not, determine the pivot column (the variable that will enter the solution). Determine the pivot row (the variable that will leave the solution). Note the pivot number.

Simplex Tableau for this Model

4th Iteration

 

 

 

       

 

Cj

Basic

Variables

Quantity

(RHS)

 

 

 

 

 

 

 

 

 

 

 

   

 

 

     

 

 

             

 

 

             

 

 

 

 

Zj

           

Cj - Zj

         

1) Record the new basic variables and the Cj values for these variables. As you did in the first iteration, record all the decision variables and their coefficients from the objective function.

2) Compute and record the new pivot row values.

 

 

 

 

 

3) Compute and record the remaining rows (in this case, there are two).

 

 

 

 

 

 

4) Compute and record the Zj row.

 

 

 

 

 

5) Compute and record the Cj – Zj row.

6) Is this the optimal solution?