- (10 pts) Back Savers is a company that produces backpacks primarily for students. They are considering offering some combination of two different models—the Collegiate and the Mini. Both are made out of the same rip-resistant nylon fabric. Back Savers has a long-term contract with a supplier of the nylon and receives a 5000 square-foot shipment of the material each week. Each Collegiate requires 3 square feet while each Mini requires 2 square feet. The sales forecasts indicate that at most 1000 Collegiates and 1200 Minis can be sold per week. Each Collegiate requires 45 minutes of labor to produce and generates a unit profit of $32. Each Mini requires 40 minutes of labor and generates a unit profit of $24. Back Savers has 35 laborers that each provides 40 hours of labor per week. Management wishes to know what quantity of each type of backpack to produce per week to maximize the profit.
Formulate this model algebraically, that is to write out the linear programming model for this problem. Do not need to solve it.
- (10 pts) The kitchen manager for Sing Sing Prison is trying to decide what to feed its prisoners. She would like to offer some combination of milk, beans, and oranges. The goal is to minimize cost, subject to meeting the minimum nutritional requirements imposed by law. The cost and nutritional content of each food, along with the minimum nutritional requirements, are shown below. What diet should be fed to each prisoner?
| Milk (gallons) | Navy Beans (cups) | Oranges (large Calif. Valencia) | Minimum Daily Requirement | |
| Niacin (mg) | 3.2 | 4.9 | 0.8 | 13.0 |
| Thiamin (mg) | 1.12 | 1.3 | 0.19 | 1.5 |
| Vitamin C (mg) | 32.0 | 0.0 | 93.0 | 45.0 |
| Cost ($) | 2.00 | 0.20 | 0.25 |
Formulate this model algebraically. Do NOT need to solve it.
- (22 pts) Consider the following problem.
Maximize Z = 2x1 – x2 + x3,
subject to
x1 – x2 + 3x3 ≤ 4
2x1 + x2 ≤ 10
x1 – x2 – x3 ≤ 7
and x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
- (6 pts) Use Excel Solver to solve this problem.
- (4 pts) Write out the augmented form of this problem by introducing slack variables.
- (12 pts) Work through the simplex method step by step in tabular form to solve the problem.
- (10 pts) Consider the following problem.
- (5 pts) Convert this problem to a maximization problem with only three functional constraints, all constraints’ RHS are nonnegative, and all decision variables need to satisfy the nonnegativity constrain. Fill this new model in the above box.
- (5 pts) Introduce slack, surplus, and artificial variables to write this problem in augmented form. Do NOT need to solve it.
- (30 pts) Consider the following problem.
Minimize Z = 3x1 + 2x2,
subject to
2x1 + x2 ≥ 10
-3x1 + 2x2 ≤
6
x1 + x2 ≥ 6
and x1 ≥ 0, x2 ≥ 0.
- (10 pts) Solve this problem graphically.
- (10 pts) Using the Big M method, construct the complete first simplex tableau for the simplex method and identify the corresponding initial BF solution. Also identify the initial entering basic variable and the leaving basic variable.
- (10 pts) Work through the simplex method step by step to solve the problem.
- (16 pts) Consider the following problem.
Maximize
subject to
and
- (6 pts) Solve this problem graphically.
- (10 pts) Use the Big M method step by step to solve this problem.
- (21 pts) Consider the following problem:
Maximize
subject to
and
The optimal solution is
Use three different approaches to find the shadow prices.
- (10 pts) Use graphical analysis to find the shadow prices for the resources.
- (2 pts) Use the last simplex tableau (given below) to find the shadow prices for the resources.
| BV | Eq | Z | x1 | x2 | x3 | x4 | RHS |
| Z | Eq0 | 1 | 0 | 0 | 0.6 | 0.2 | 6 |
| x2 | Eq1 | 0 | 0 | 1 | 0.4 | -0.2 | 2 |
| x4 | Eq2 | 0 | 1 | 0 | -0.2 | 0.6 | 2 |
- (9 pts) Use the Excel Solver to solve the problem to find the optimal Z value, then modified each resource’s RHS by adding 1 (do the modificiation to one functional constraint at a time), use the new optimal Z value and the old optimal Z value to find the shadow price.
- (11 pts) Consider the following problem:
Maximize
Z = 2x1 + 4x2 – x3,
subject to
3x2 – x3 ≤ 30 (resource
1)
2x1 – x2 + x3 ≤ 10 (resource
2)
4x1 +2x2 – 2x3 ≤ 40 (resource 3)
and x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
The last tableau of the simplex method for this problem is given below.
| Basic Variable | Eq | Coefficient of: | |||||||
| Z | x1 | x2 | x3 | x4 | x5 | x6 | Right Side | ||
| Z | (0) | 1 | 0 | 0 | 0 | 1.5 | 0.75 | 0.125 | 57.5 |
| x2 | (1) | 0 | 0 | 1 | 0 | 0.5 | 0.25 | -0.125 | 12.5 |
| x3 | (2) | 0 | 0 | 0 | 1 | 0.5 | 0.75 | -0.375 | 7.5 |
| x1 | (3) | 0 | 1 | 0 | 0 | 0 | 0.25 | 0.125 | 7.5 |
- (3 pts) What are the shadow prices?
- (2 pts) If we can increase all resource capacity, which resource has the priority?
- (6 pts) If Z is the profit measured in million, and the cost to increase each resource by one unit is $1 million, should we increase the resource 1 by one unit? What about resource 2 and resource 3?
- (20 pts) Consider the following problem, where the values of and have not yet been ascertained.
Maximize
subject to
and
Use the graphical sensitivity analysis to determine the optimal solution(s) for for various possible values of and
When and satisfy ____________, the optimal solution is point A (.
When and satisfy ____________, the optimal solution is point B (2, 2).
When and satisfy ____________, the optimal solution is point C (4, 0).
When and satisfy ____________, the optimal solutions are all points on line segment AB.
When and satisfy ____________, the optimal solutions are all points on line segment BC.
