1.   (25 pts total) Consider what happens when you apply the simplex method to the following linear problem. Maximize         Z = x1 + 2x2 + x3, subject to

5x1 + 2x2 + 3x3 ≤ 15

x1 + 4x2 + 2x3 ≤ 12

2x1                  +  x3 ≤   8             And            x1 ≥ 0,    x2 ≥ 0,    x3 ≥ 0.

We will break this problem into parts a – c below:

a)    (5 pts) Introduce appropriate slack variables and write down the system in augmented form (don’t forget to include equation zero):

b)   (10 pts) Obtain the initial BF solution and describe optimality test.

c)    (10 pts) Identify entering and leaving basic variables of the 1st  iteration and perform this iteration to identify the next BF solution.  Describe the optimality test again. If this solution is not optimal, you  don’t need to go any further than that.

2.   (25 pts total) Label each statement as True of False and brieflyjustify your answer:

a)   (5 pts) In a particular iteration of the simplex method, if there is a tie for which variable should be the leaving basic variable, then the next BF solution must have at least one basic variable equal to zero.

b)   (5 pts) If there is no leaving basic variable at some iteration the problem has nofeasible solutions.

c)   (5 pts) If there is no leaving basic variable at some iteration the problem has no optimal solutions.

d)   (5 pts) If at least one of the basic variables has a coefficient of zero in row 0 of the final Tableau, then the problem has multiple optimal solutions.

e)   (5 pts) If at least one of the non-basic variables has a coefficient of zero in row 0 of the final Tableau, then the problem has multiple optimal solutions.

3.     (35 pts) Problem. In this problem you are asked to consider changes that happen to Wyndor Problem if hours available for Plant 1, or Plant 2, or Plant 3 change. (All changes will be considered one at a time. Assume that    none of the other assumptions associated with the original example change.)

a.    (5 pts) Suppose that Plant 3 goes off line and can’t contribute to making products. Write down the    modified LP problem formulation. Identify the new feasible region.  Find an optimal solution and the new profit value.

b.    (5 pts) Suppose that Plant 1 and Plant 2 are able to provide unlimited number of hours.  Write down the modified LP problem formulation. Identify the new feasible region.  Find an optimal solution and the      new profit value.

c.    (10 pts) Write down a LP Problem associated with having Plant 2 and Plant 3 provide unlimited number of hours. Draw the feasible region. Work through a simplex method iteration associated with this           problem. Show and explain what happens as you start performing a simplex method iteration.

     (Note: In problem 3c, you must justify your answer using a simplex method formulation, do not

use a drawing offeasible region as a justification of your answer.)

d.    (20 pts) Suppose that the number of hours available to plant 3 changes.  How many hours would need to be available to Plant 3 in order to create a tie for a leaving basic variables in one of the Simplex Method  iterations (i.e. create a degeneracy)?

i.   Indicate the number of hours. (Explain your answer).

ii.   Indicate the resulting CPF solutions where degeneracies occur.

iii.   Indicate the entering basic variables that cause this to happen

iv.   Indicate which basic variable form a tie for a leaving basic variable.

Note for part (d): You do not need to solve anything via Simplex Method.  All you need to do is indicate the number of hours available to Plant 3, the CPF solution where degeneracy occurs, and the   appropriate basic and non-basic variables. There are multiple possible answers here.   Getting any one  will give you full credit.  For each additional correct answer you will earn extra 5 bonus points.