\documentstyle[12pt,fullpage]{article}
\begin{document}

\begin{center}
{\large\bf C\&O 370}
\end{center}

\begin{center}
{\large\bf Midterm Examination}
\end{center}

\begin{center}
{\large\bf Winter 1996}
\end{center}

\vspace{.25in}
\begin{enumerate}
\item[1.]
A company consisting of three factories must produce 380 units of product
$p$ and 425 units of product
$q$.
Factory \#1 can produce 8 units of $p$ plus 5 units of $q$ per hour at a
cost of \$47.
Factory \#2 can produce 6 units of $p$ plus 10 units of $q$ per hour at a
cost of \$54, and factory \#3
can produce 4 units of $p$ plus 12 units of $q$ per hour at a cost of \$56.
\begin{itemize}
\item[(a)]
[15 marks]\\
Develop a GAMS-like model for determining the number of hours each factory
should run in order to
meet the demands and minimize total production cost.

\item[(b)]
[10 marks]\\
Verify that an optimum solution to your model of part (a) is obtained by
running factory \#1 for 25
hours, factory \#2 for 30 hours and not running factory \#3 at all.
As part of your verification argument, explicitly state the dual of your
model and the complementary
slackness equations resulting from this proposed solution.
\end{itemize}

\item[2.]
Consider the linear program:
\[ \begin{array}{clccrcrcl}
(P) & \mbox{maximize} & z & = & x_1 & + & x_2 & & \\
 & \mbox{subject to:} & & & -x_1 & + & 2x_2 & \leq & 1 \\
 & & & & 12x_1 & + & 4x_2 & \leq & 9 \\
 & & & & x_1 & , & x_2 & \geq & 0.
\end{array} \]
After introducing slack variables, a tableau for $(P)$ is:
\[ \begin{array}{rrrcrcrcl}
 & & x_2 & + & \frac{12}{28}x_3 & + & \frac{1}{28}x_4 & = & \frac{21}{28}\\
& & & & & & & & \\
 & x_1 & & - & \frac{4}{28}x_3 & + & \frac{2}{28}x_4 & = & \frac{14}{28}\\
& & & & & & & & \\
z & & & + & \frac{8}{28}x_3 & + & \frac{3}{28}x_4 & = & \frac{35}{28}.
\end{array} \]
\begin{itemize}
\item[(a)]
[5 marks]\\
Verify, as in 1.(b), that the basic solution of this tableau is $(P)$-optimum.
\item[(b)]
[5 marks]\\
Use the given tableau for $(P)$ and sensitivity techniques to solve the
linear program:
\[ \begin{array}{clccrcrcl}
(P)' & \mbox{maximize} & z & = & x_1 & + & x_2 & & \\
 & \mbox{subject to:} & & & -x_1 & + & 2x_2 & \leq & 1 \\
 & & & & 12x_1 & + & 4x_2 & \leq & 9 \\
 & & & &   x_1 & + & 2x_2 & \leq & 1 \\
 & & & & x_1 & , & x_2 & \geq & 0.
\end{array} \]
Note that $(P)'$ is $(P)$ with an added constraint.
\item[(c)]
[5 marks]\\
Use the given tableau for $(P)$ and sensitivity techniques to solve the
linear program:
\[ \begin{array}{clccrcrcrcl}
(P)'' & \mbox{maximize}    & z & = & x_1 & + & x_2 & + & x_5 & & \\
      & \mbox{subject to:} & & & -x_1 & + & 2x_2 & + & 3x_5 & \leq & 1 \\
 & & & & 12x_1 & + & 4x_2 & + & 2x_5 & \leq & 9 \\
 & & & & x_1 & , & x_2 & , & x_5 & \geq & 0.
\end{array} \]
Note that $(P)''$ is $(P)$ with an added column.
\item[(d)]
[10 marks]\\
Consider the parametric linear program:
\[ \begin{array}{clccrcrcl}
(P)''' & \mbox{maximize} & z & = & (1+ \theta)x_1 & + & (1- \theta)x_2 & & \\
 & \mbox{subject to:} & & & -x_1 & + & 2x_2 & \leq & 1 + \theta \\
 & & & & 12x_1 & + & 4x_2 & \leq & 9 - \theta \\
 & & & & x_1 & , & x_2 & \geq & 0.
\end{array} \]
Use the given tableau for $(P)$ and parametric techniques to determine all
values of $\theta$ for which
$B = (2, 1)$ is an optimum basis for $(P)'''$. \newline
Note that $(P)'''$ is $(P)$ with simultaneous parameterization of both the
$c$ and $b$ vectors.
\end{itemize}

\item[3.]
A manufacturer wants to plan his production schedule for a three month period.
The following table contains all of the relevant cost, production capacity
and end-of-month demand
data.
Note that a penalty cost is incurred for surplus (unused) production capacity.
Production levels must be at least {\bf 50 units} in each of the three
months, and inventory-holding
levels must not exceed {\bf 40 units} in each of February and March.
No inventory is to be held past the end of March.

\newpage
\begin{center}
\begin{tabular}{|c||c|c|c||c||c|} \hline
Month &
\multicolumn{3}{c|}{Costs (\$/unit)} & Production & End-of-Month \\ \cline{2-4}
 & Production & Holding & Penalty & Capacity & Demand \\ \hline
JAN & 10 & - & 2 & 100 & 50 \\
FEB & 20 & 8 & 2 & 100 & 100 \\
MAR & 30 & 8 & 2 & 100 & 75 \\ \hline
\end{tabular}
\end{center}
\begin{center}
{\bf Table: Cost \& ``Demand'' Data}
\end{center}

\vspace{.10in}
The manufacturer wants you to determine a production schedule which meets
these demands, subject to
the conditions stated, and minimizes total cost.

You recognize this as an instance of a network programming problem of the form:
$$(P) ~\mbox{minimize}~ z = cx: ~ Ax = b, ~~~ \ell \leq x \leq u,$$
where $A$ is the incidence matrix of some digraph (network) $G = (V,E)$.
\begin{itemize}
\item[(a)]
[5 marks]\\
Draw network $G=(V,E)$, labelled with the given costs, (nonzero) lower
capacities, (finite) upper
capacities and ``demands''.
\item[(b)]
[5 marks]\\
Consider a production schedule requiring production levels of 90, 85 and
50, respectively for
January, February and March.
Extend this schedule to a vector, $x^{\ast} = x^{\ast}(E)$, which is
feasible for $(P)$.
\item[(c)]
[5 marks]\\
Write down the dual, $(D)$, of $(P)$, {\bf explicitly} for the given data.
That is, do {\bf not} use a GAMS-like formulation.
In particular, for each arc, $( \alpha, \beta ) \in E$, write down the dual
constraint corresponding
to $( \alpha, \beta )$.
\item[(d)]
[10 marks]\\
Write down the complementary slackness equations corresponding to vector
$x^{\ast}$ from part (b), and
solve them.
Then, explain why vector $x^{\ast}$ is optimum for $(P)$.

Hint: When solving the complementary slackness equations, let the dual
variables indexed by the
start-of-month nodes be equal to $0$.
\end{itemize}

\newpage
\item[4.]
In digraph $G=(V,E)$ below, the node-set, $V$, represents a set of relay
stations; the arc-set, $E$,
represents a set of (one-way) communication channels, and, the number, $u(
\alpha, \beta)$, shown on
each arc, $(\alpha, \beta ) \in E$, represents the number of parallel
communication channels through
which a message can be sent directly from station $\alpha$ to station $\beta$.

\vspace{3.00in}
\begin{itemize}
\item[(a)]
[15 marks]\\
An {\bf $st$-vulnerability set}, $C$, is a subset of channels, the
destruction of which would make
communication from station $s$ to station $t$ impossible.
Find an $st$-vulnerability set, $C^{\ast}$, of minimum cardinality (size).
\item[(b)]
[10 marks]\\
Assuming the truth of any relevant theorems from lectures and/or homework
readings, prove that your
answer to part (a) is correct.
\end{itemize}

\end{enumerate}
\end{document}















