C

Name:

Math Models of Operations Research, MATP 4700/ DSES 4770.

First Exam, Tuesday, October 4, 2005.

You may use any result from your notes or a homework that is clearly stated. You may use one sheet of handwritten notes, but no other sources. The exam consists of five questions, and lasts one hundred and ten minutes.

1. (25 points; each part is worth 5 points.)

   Consider the linear constraints
   

   $$\begin{array}{rcrcr} -y_1 & + & y_2 & \leq & 2 \\ 5y_1 &&& \leq & 10 \\ \multicolumn{3}{r}{y_1, y_2} & \geq & 0 \end{array}$$
   
   
   1. Sketch the feasible set in a 2-dimensional plot.
   2. Add slacks $y_3$ and $y_4$ to place the constraints in standard form.
   3. Determine whether columns of the standard form corresponding to each of the following sets of variables form a basis: $\{ y_1, y_2 \}$, $\{y_2, y_3 \}$, $\{y_3,y_4\}$, $\{y_1,y_4\}$.
   4. For each set that does form a basis in part 1c, determine the corresponding basic solutions and classify it as feasible or infeasible.
   5. Identify each solution of part 1d on your plot of part 1a.

2. (15 points.)

   The following tableau represents a linear program in standard form:
   

   $$\begin{array}{\vert r\vert rrrrr\vert} \hline 3 & 4 & 0 & -3... ... & -5 & 0 & 0 \\ 4 & 6 & 0 & 2 & 1 & 0 \\ \hline \end{array}$$
   
   
   1. (10 points) Perform one simplex pivot on this tableau.
   2. (5 points) What would you do next?

3. (20 points)

   Consider the following tableau for a standard form linear program:
   

   $$M = \begin{array}{\vert r\vert rrrr\vert} \multicolumn{1}{... ...& b & e & 1 & 0 \\ 12 & c & f & 0 & 1 \\ \hline \end{array}$$
   
   
   On the next pivot $x_2$ enters the basis. The corresponding pivot matrix is
   
   $$P = \left[ \begin{array}{rrr} 1 & 3 & 0 \\ 0 & 2 & 0 \\ 0 & -4 & 1 \end{array} \right]$$
   
   
   1. (6 points) What is the basic feasible solution obtained as a result of this pivot?
   2. (7 points) Give a linear constraint that must be satisfied by $a$, $b$, and $c$ for the new solution to be optimal.
   3. (7 points) What three linear constraints must $a$, $b$, and $c$ satisfy for the next tableau to be in unbounded form?

4. (20 points)

   The variables in the following linear programming problem have upper bounds:
   

   $$\begin{array}{lrcrcrcrcrcr} \min & 5x_1 & - & 3x_2 \\ \m... ...\leq & 10 \\ &&&&&&& 0 & \leq & x_5 & \leq & 25 \end{array}$$
   
   
   The current basic feasible solution has $x_1$ and $x_2$ both nonbasic at their upper bounds.
   1. (3 points) What are the values of the basic variables at the current BFS?
   2. (3 points) Which variable should enter the basis?
   3. (3 points) What is the corresponding simplex direction?
   4. (3 points) Which variable should leave the basis?
   5. (3 points) What steplength should be chosen in the simplex direction?
   6. (5 points) Plot the feasible region, and hence show that this move along the simplex direction leads to the optimal solution.

5. (20 points)

   A coal-fired electric plant burns three types of coal to drive steam turbines in order to produce electricity. Federal standards require that emissions from the furnace contain no more than 2500 parts per million (ppm) of sulfur oxide and that no more than 40 kilograms per hour (kg/hr) of particulate matter (smoke) be emitted from the stack. The following table gives the amounts of both pollutants that result from burning the three types of coal.

                   

   	Sulfur Oxide in	Particulates Emitted
   Coal	Stack Emissions	per Ton of Coal Burned
   Type	(ppm)	(kg/hr)
   A	1200	1
   B	3300	2
   C	2100	5

   Burning one ton of coal A results in 22,000 lb of steam, whereas burning one ton of coal B or coal C, respectively, produces 27,000 or 34,000 lb. The furnace has a capacity for burning 25 tons per hour of any mixture of the three coals. Also, the sulfur oxide emissions that result from burning a mixture of coals is equal to a weighted average of the parts-per-million emissions of the individual coals, where each weight is equal to the proportion of that coal used in the mixture.

   Formulate a linear programming model for operating the electric plant so as to maximize the amount of steam generated per hour.