Click here for the schedule and sample problems page.

The material to be covered on the Final Exam is cumulative and includes all previous Summary and Objectives items as well as Chapter 8: Objectives 1, 5, 6. Also proficiency with LINDO will be tested on the Final Exam.

No solutions for the sample problems will be provided. (But you can ask during office hours.) The exam will have 6-9 problems.

1. Consider LINDO output for a maximization problem. Describe the role of the entries in the "REDUCED COST" column in terms of the final Simplex tableau.

2. p. 432, #5.

3. pp. 447-8, #3.

4. p. 448, #4.

The material to be covered on Test 3 is largely described by the following objectives from the Summary and Objectives sections concluding the respective chapters: Chapter 4: Objectives 5 - 7; Chapter 7: Objectives 4, 6 (except, NO LINDO), 7.

No solutions for the sample problems will be provided. (But you can ask during office hours.) The exam will have 4-6 problems.

1. p. 229, #7.

2. p. 231, #9.

3. p. 368, #3. Do 3b using a (very slight) modification of the branch-and-bound algorithm for knapsack problems.

4. We want to pack a cooler to tailgate at a CMU football game, but we bought too much food. Here are the volumes (in cm^{3}) and prices (in dollars) of the items that we bought:

Price | Volume | |

Hamburgers | 20 | 10 |

Frankfurters | 8 | 5 |

Potato Salad | 18 | 12 |

Cole Slaw | 14 | 7 |

Ice Cream | 21 | 12 |

Sushi | 15 | 9 |

If an item does not get placed in the small cooler (capacity 28 cm^{3}) it will spoil. Use a branch-and-bound method to find the minimum cost of the spoiled food. To simulate exam conditions, only carry out the first three branchings. That is, there are only 6 nontrivial *B _{i}* computations to be made.

5. p. 407, #9.

6. p. 420, #1.

7. p. 420, #5.

The material to be covered on Test 2 is largely described by the following objectives from the Summary and Objectives sections concluding the respective chapters: Chapter 3: Objectives 8 - 18; Chapter 4: Objectives 1, 3 - 5.

No solutions for the sample problems will be provided. (But you can ask during office hours.) The exam will have 5-7 problems. You will be able to do all of the problems except for #9 right away.

1. p. 156, #3.

2. Consider the following linear program:

(a) Determine its dual.

(b) Without utilizing the Simplex
algorithm, can you determine which dual constraint must have slack or
surplus?

(c) Using part (b), which variable of the original problem
must have value 0 in the optimal solution?

3. We are given that a maximizing linear program has solution
*z=100*. Suppose the dual minimizing linear program has
objective function

*w=10y _{1}+5y_{2}+y_{3}+2y_{4}*.

A student claims that

*y _{1}=0*,

is an optimal solution to the dual linear program.

(a) Is the student's dual solution an optimal solution? Why or why not?

(b) Can you tell if it is a feasible solution? Why or why not?

4. p. 172 #6.

5. The following tableau is optimal. The variable
*s _{i}* is a slack or surplus variable in constraint

(a) What is the maximum increase and the maximum decrease in the right hand side of the first constraint if the set of basic variables will not change.

(b) If the resource in the first constraint is increased by the maximum amount from part (a) above, what will be the new value of *x _{2}*?

(c) If the objective function of the dual problem is

*w=4y _{1}+y_{2}+2y_{3}+Ay_{4}*

(d) Which variable in the dual problem is unrestricted, and why?

6. State the complimentary slackness theorem.

7. Determine an initial basic feasible solution for the following transportation problem and the next solution:

(a) What is the difference between the value of the objective function for your first solution and for your second solution?

(b) Is your *second* solution optimal? Why or why not?

8. p. 205, #4

9. Consider p. 227 #2. Draw the critical path network for this model.

(a) Determine the slack for every event.

(b) Determine the float for every edge.

The material to be covered on Test 1 is described by the following objectives from the Summary and Objectives sections concluding the respective chapters: Chapter 1: Objectives 1 - 7; Chapter 3: Objectives 1 - 3, 5 - 9.

No solutions for the sample problems will be provided. (But you can ask during office hours.) The exam will only have 5 problems. You will be able to do all of the problems except for #7 right away. Even #7 will be old material by 2/7/01.

1. Consider the following linear program:

(a) Draw the set of feasible solutions and label the feasible
corners.

(b) Determine the solution.

(c) Draw two level curves of the objective function, one corresponding
to the optimal value, and one corresponding to a value smaller than
the optimal value.

2. Consider the following linear program:

Give the values of *a* for which the feasible region is the
empty set.

3. (a) Define what it means for a set to be convex.

(b) Define what it means for a point in a convex set to be an extreme
point.

(c) Sketch a convex region that has an infinite number of extreme
points but also has boundary points that are not extreme points.

4. Consider the following simplex tableau:

(a) In the *given* tableau, what is the basic solution?

(b) In the *given* tableau, which variable would produce the
larger increase in the objective function if made basic, and how much
would that increase be?

(c) Determine the next tableau if *x*_{1} becomes
basic.

(d) In the tableau that you calculated above, is the solution optimal?
Why or why not?

5. p. 99, #7

6. Consider the simplex tableau below:

There are several variables which are candidates to become basic in
the next solution. Which variable should become basic, and briefly
why, if the goal is

(a) To increase the value of the objective function by 64?

(b) The third constraint is to be tight?

(c) To have the value of the new basic variable to be 15?

(d) To achieve the greatest increase in the value of the objective
function?

7. **Set up** the initial simplex tableau for the following
linear program. Include an artificial objective function if necessary:

8. **Set up** the linear program to solve the following problem.
Provide all needed constraints and clearly identify each variable.

Generic Motors makes three kinds of cars: pick-up trucks, minivans and coupes. It is looking at its production for the next two weeks (before the next round of layoffs). One key to production is the use of transmogrifiers. The pick-ups use 2 transmogrifiers whereas the other vehicles use only one. A strike at a supply company left only 300 transmogrifiers in stock.

Some of GM's cars are exported. In order to get favorable US tariff treatment, the average domestic content of their production must be at least 75%. The domestic content of the pick-ups, minivans and coupes are 65%, 70% and 85%, respectively.

A pickup sells for $32500, a minivan sells for $30000 and a coupe sells for $39000. Unfortunately for GM, the coupe is a convertable and sells for one-third less in the colder markets and GM expects to sell half of the coupes in cold markets. Finally, because of marketing considerations, the minivans must be at least one-fifth of all the cars made.

Determine a linear program to decide the number of each model to
produce to maximize sales revenue. **DO NOT SOLVE** the linear
program.

9. Consider the following linear program and the nonbasic solution
**x**^{T}=[2,4,4,0,1] to the following problem:

Determine a basic feasible solution with objective value at least
as large as that of * x* by adding a solution to the
homogeneous system of equations to the given solution.

Ryan Martin's CMU MATH 257 Exam Page / Revised 8/19/04.