Models and Methods of Optimization (CMU MATH 257) Exam Page

Click here for the archive.
Click here for the schedule and sample problems page.


Objectives for Final Exam and sample problems.

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.



Objectives for Test 3 and sample problems.

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 cm3) and prices (in dollars) of the items that we bought:

PriceVolume
Hamburgers2010
Frankfurters85
Potato Salad1812
Cole Slaw147
Ice Cream2112
Sushi159

If an item does not get placed in the small cooler (capacity 28 cm3) 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 Bi computations to be made.

5. p. 407, #9.

6. p. 420, #1.

7. p. 420, #5.



Objectives for Test 2 and sample problems.

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:

\begin{displaymath}\begin{array}{lrcrcrcr}
\mbox{Maximize:} & 3x1 & + & 4x_2 & ...
...{x_1\geq 0,
x_2\mbox{ unrestricted,} x_3\geq 0}
\end{array} \end{displaymath}

(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=10y1+5y2+y3+2y4.

A student claims that

y1=0, y2=5, y3=10, y4=15

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 si is a slack or surplus variable in constraint i and ai is an artificial variable in constraint i.

\begin{displaymath}\begin{array}{rrrrrrrrr\vert r}
x_1 & x_2 & x_3 & x_4 & s_1 ...
... \hline
0 & 0 & 3 & 0 & 5 & -5 & 0 & 5 & 2 & 450
\end{array} \end{displaymath}

(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 x2?
(c) If the objective function of the dual problem is

w=4y1+y2+2y3+Ay4

what is the value of A?
(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:

\begin{displaymath}\begin{array}{r\vert r\vert r\vert r\vert r\vert r\vert
r\ver...
...}{c}{} & & \multicolumn{2}{c}{} & \\ \cline{2-10}
\end{array} \end{displaymath}

\begin{displaymath}\begin{array}{r\vert r\vert r\vert r\vert r\vert r\vert
r\ver...
...}{c}{} & & \multicolumn{2}{c}{} & \\ \cline{2-10}
\end{array} \end{displaymath}

(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.



Objectives for Test 1 and sample problems.

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:

\begin{displaymath}\begin{array}{lrcrcr}
{\rm Maximize:} & 3x_1 &+& 2x_2 \\
{\r...
...
& \multicolumn{5}{c}{x_1 \geq 0, \; \; x_2 \geq 0}
\end{array}\end{displaymath}

(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:

\begin{displaymath}\begin{array}{lrcrcr}
{\rm Maximize:} & 80x_1 & + & 60x_2 \\ ...
... & \multicolumn{5}{c}{x_1 \geq 0, \; \; x_2 \geq 0}
\end{array}\end{displaymath}

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:

\begin{displaymath}\begin{array}{cccccc\vert r}
x_1& x_2& x_3& s_1 & s_2 & s_3 &...
... 1 & 9\\
\hline
-1 & 0 & -2 & 0 & \frac12 & 0 & 40
\end{array}\end{displaymath}

(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 x1 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:

\begin{displaymath}\begin{array}{rcccrcr\vert r}
x_1 & x_2 &x_3 & s_1 & s_2 & s_...
... & 60 \\
\hline
-5 & 0 & -8 & 0 & -2 & 0 & 0 & 700
\end{array}\end{displaymath}

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:

\begin{displaymath}\begin{array}{lrcrcrcr}
{\rm Maximize:} & 4x_1 &+& 5x_2 &+& 3...
...\; \; x_2 \geq 0,
\; \; x_3 \; {\rm unrestricted}}
\end{array}\end{displaymath}

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 xT=[2,4,4,0,1] to the following problem:

\begin{displaymath}\begin{array}{lrcrcrcrcrcl}
\mbox{Maximize:} & 12x_1 & + & 4...
... 0, x_2\geq 0,
x_3\geq 0, x_4\geq 0, x_5\geq 0}
\end{array} \end{displaymath}

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.