Instructions

Please show all your work in the blue book provided and box off your answers.

. Partial credit will be given when you show your work.

.  If you get stuck on one problem – I recommend moving on to the next one and coming back to the one that gave you trouble later. Good luck!

Problem 1. True or False?  :  (25 points)

Label each statement as True of False and briefly justify 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 no feasible 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.

Problem 2. BIG M method :  (60 points)

Consider the following LP problem (a modification on Wyndor Glass problem).

Maximize Z = 3x1  + 5x2 , subject to

x1  = 4 (updated constraint)

2x2  ≤ 12

3x1 + 2x2  ≤ 18;  And

x1  ≥ 0, x2  ≥ 0

(a)  (10 pts) Write down the complete artificial problem (in augmented form) to be used by the Big M method. Don’t forget about the function to be optimized.

(b)  (10 pts) Draw the feasible region for artificial problem.  Also identify feasible region for true problem.

(c)  (15 pts)  Put the system in the proper form for Gaussian elimination in the initial iteration.  Identify entering and leaving basic variable.  You don’t need to go beyond this point.

(d)  (10 pts.) Using any method you want, identify the optimal solution.

(e)  (10 pts) Suppose that you forgot to modify the objective function to account for arti- ficial variables. Explain what would happen to the optimal solution in this case.

(f)  ( 10 pts) What happens to our feasible region and optimal solution if we remove con- straint 2 and 3! DRAW A GRAPH TO DEMONSTRATE YOUR ANSWER!

Problem 3. Change in the constraint ?  (30 points)

Suppose that objective function in the problem above changed to minimize Z = 3x1 + 5x2 , subject to the same boundary constraints as above.

(a)  (10 pts) Write down the complete artificial problem (in augmented form) to be used by the Big M method. Don’t forget about the function to be optimized.

(b)  (10 pts.) Using any method you want, identify the optimal solution to this problem.

(c)  (10 pts) Suppose that you forgot to modify the objective function to account for arti- ficial variables in part d.

Problem 4. Formulate linear programming problem (45 points)

Formulate a linear programming model for the problem described below.

A Company makes three types of gloves – Men’s, Women’s, and Children’s.  Below is the information regarding the labor costs and the profits to the Company from making this product (gloves).

.  The company labor force consists of full-time employees who work a 40-hour week and part-time workers who work 20 hours per week. The Company labor force is governed by the following rules:

–  The number of full-time employees can never drop below 20.

–  There must be at least 2 full-time employees for each part-time employee.

–  Each full-time employee earns 13 dollars per hour, while each part-time employee earns 10 do per hour.

. All three types of gloves are made out of the same material  (leather).   Only  5,000 square feet of the material is available each week.

Table 1: Glove Production Details

Management wishes to know what mix of each of the three types of gloves to produce per week, as well as how many full-time and how many part-time workers to employ. They would like to maximize their net profit — their gross profit from sales minus their labor costs.

. We will break this problem into parts a – f below:

(a)  (10 pts) Write down the decision variables needed for this problem and explain what each one represents.

(b)  (5 pts) Write down the objective function in terms of your decision variables.

(c)  (5 pts) Write down the boundary constraints associated with limitations on the amount of leather material.

(d)  (10  pts) Write down the boundary constraints associated with the amount of labor required to produce specified number of product types (hint:  your right- hand side bound should be a function that depends on the number of full and part-time workers).

(e)  (5 pts) Write down boundary constraints associated with the numbers of full-time and part-time workers.

(f)  (10 pts) Write down boundary constraints associated with non-negativity;  and state whether the origin is a feasible solution (justify your answer).

Score Table