\documentstyle[12pt,fullpage]{article}
\newcommand{\A}{\mbox{\bf A}}
\newcommand{\B}{\mbox{\bf B}}
\newcommand{\C}{\mbox{\bf C}}
\newcommand{\Q}{\mbox{\bf Q}}
\newcommand{\R}{\mbox{\bf R}}
\newcommand{\Z}{\mbox{\bf Z}}
\newcommand{\qed}{\hfill\rule{2.5mm}{2.5mm}}
%\addtolength{\topmargin}{0in}
\setlength{\textheight}{14in}
%\newcounter{temp}
\reversemarginpar
\pagestyle{myheadings}

\markright{C\&O 350 \hspace{10mm} NAME: \underline {\hspace{60mm}}}
\markright{\bf Name: \protect\rule{2.5in}{.01in}}
\begin{document}
\begin{titlepage}
\begin{flushright}
\hfill {\bf Name: \protect\rule{3in}{.01in}}
\\ \hspace{1.50in}
\\
{\bf I.D. \#: \protect\rule{3in}{.01in}}
\\ \hspace{1.50in}
\\
{\bf Section: \protect\rule{3in}{.01in}}
\end{flushright}

\vspace{.50in}

\begin{center}
{\Large\bf C\&O 350 Linear Programming \\ Mid-Term Examination \\
Winter 1996 \\ Thursday, 15 Feb., 1996 \\
7:00 - 9:00 p.m. (2 hours)\\}
\end{center}

\vspace{.50in}
\begin{enumerate}
\item[1.]
Print your name and i.d.  and section number in the space provided above.
\item[2.]
This examination consists of 6 questions and 10 pages plus the cover page.
Make sure you have a complete paper.
\item[3.]
No calculators are allowed.
\item[4.]
Write answers in space provided.  If you need more space, use back of
previous page.
\end{enumerate}

\vspace{.50in}
\begin{center}
\begin{tabular}{llll}
\large Section 1 & \large $\Box$ Wolkowicz & \large TR & \large 1:00-2:30
\\
\large Section 2 & \large $\Box$ Cunningham & \large TR & \large  10:00-11:30\\
\end{tabular}
\end{center}

\vspace{.50in}
\begin{minipage}[t]{2.25in}
\begin{center}
\begin{tabular}{|c|c|c|}\hline
& & \\
Question & Mark Value & Student Mark\\ \hline
& & \\
1 & 24 & \\ \hline
& & \\
2 & 16 & \\ \hline
& & \\
3 & 17 & \\ \hline
& & \\
4 & 19 & \\ \hline
& & \\
5 & 14 & \\ \hline
& & \\
6 & 10  & \\ \hline
& & \\
Total & 100 & \\
& & \\ \hline
\end{tabular}
\end{center}
\end{minipage}
\end{titlepage}

\begin{enumerate}
\item[1.]
Consider the following linear programming problem (LP):
\[ \begin{array}{rrcrcrcr}
\mbox{maximize} & 2x_{1} & + & x_{2}  & & \\
\mbox{subject to} & x_{1} & - & 2x_{2}  & \leq & 1 \\
&  &   & x_{2}  &\leq  & 2 \\
 & x_{1} &   &  &  \leq & 5 \\
 & -x_{1} & + & x_{2}  & \leq & 1 \\
 & x_{1} & , & x_{2} &  \geq & 0
\end{array} \]
\begin{itemize}
\item[(a)]
Solve the LP by
  \marginpar{~~~[12]}
applying the simplex method. \newline
( Use the largest coefficient rule for choosing the entering variable and
the smallest subscript rule for choosing the leaving variable.)\\
\end{itemize}

\newpage
\item[1.] continued,
\begin{itemize}
\item[(b)] For the final basis in (a)  \marginpar{~~~[4]} give the
the basic solution, the basis $B$, the basis matrix $A_B$
and inverse $A_B^{-1}$.

\vspace{3.00in}
\item[(c)]
Is the \marginpar{~~~[4]} optimal basic solution degenerate? If so, find
another basis determining it.

\vspace{2.00in}
\item[(d)] Draw the \marginpar{~~~[4]}set of feasible solutions of $(LP)$
and indicate the basic feasible solutions.
\end{itemize}

\newpage
\item[2.]
Consider the linear programming problem $(P)$ below:
$$\begin{array}{rrrrrrr}
\mbox{maximize }z&=&&+x_2&x_3&&\\
\mbox{subject to }&&&&&\\
&&-x_1&+x_2&-2x_3&=&4\\
&&2x_1&-x_2&+x_3&=&-1\\
&&x_1,&x_2,&x_3&\geq& 0.
\end{array}
$$
\begin{itemize}
\item[(a)]
Formulate \marginpar{~~~[4]}a phase I linear programming problem $(P')$
 for finding
a feasible solution to $(P)$, and find a feasible tableau (or dictionary)
for $(P')$.

\vspace{6.00in}
\item[(b)]
Solve \marginpar{~~~[8]}$(P')$ by the simplex method.
\end{itemize}

\newpage
\item[2.]
\begin{itemize}
\item[(b)] continued,

\vspace{6.00in}
\item[(c)] From \marginpar{~~~[4]}your solution to (b), find a feasible
tableau (or dictionary)
for $(P)$. {\bf Do not solve } $(P)$.
\end{itemize}

\newpage
\item[3.]
\begin{itemize}
\item[(a)]
Define \marginpar{~~~[3]}the term ``basic solution'' of $Ax = b$.
(You may assume that $A$ is $m \times n$ with rank $m$.) Your definition
should not use other terms from linear programming, but it may use
terms from linear algebra.

\vspace{1.50in}
\item[(b)]
Let $x^*$ be \marginpar{~~~[3]} a feasible solution of a linear programming
problem $(LP)$. Define what it means for $x^*$ to be an {\bf extreme point}
of the set of feasible solutions.

\vspace{1.50in}
\item[(c)] Suppose \marginpar{~~~[3]}that the constraints of problem $(LP)$
of part (c)
are $Ax=b,\ x\geq 0$, where $A$ has $m$ rows and rank $m$. State a theorem
giving a condition for $x^*$ to be an extreme point of the set of feasible
solutions.

\vspace{1.50in}
\item[(d)]
For each of the following statements, tell whether the statement is true or
false.  You do not need to give a reason for your answer.
\begin{itemize}
\item[(i)]
If the simplex method \marginpar{~~~[2]} applied to a linear programming
problem fails to terminate, then the problem must be degenerate.

\vspace{.50in}
\item[(ii)]
If a linear programming problem is unbounded, then it has \marginpar{~~~[2]}
infinitely many optimal solutions.

\vspace{1.00in}
\item[(iii)]
If \marginpar{~~~[2]}a linear programming problem has more than one
optimal solution, then it has infinitely many optimal solutions.

\vspace{.50in}
\item[(iv)]
If \marginpar{~~~[2]}in an iteration of the simplex method, $x_{k}$ is
chosen as the entering variable,
and there is more than one choice for the leaving variable, then the new
basic solution
will be degenerate.
\end{itemize}
\end{itemize}


\newpage
\item[4.]
\begin{itemize}
\item[(a)]
Consider the tableau
\[      (T') ~~~~~ \begin{array}{rrrrrrrrr}
&& 2x_{2} & +  x_{3} && - x_{5}&+x_{6} & = & 4  \\
&&   x_{2} & -  x_{3} &+x_{4}& +  x_{5}&& = & 2  \\
&x_{1}& +  2x_{2} & +  2x_{3} && +  3x_{5}& & = & 6 \\
z&& -  2x_{2} & +  2x_{3} && -  3x_{5}& & = & 5
\end{array} \]
Notice that the bottom row could also be written
$$-z+  2x_{2}  -  2x_{3} +  3x_{5} = 5.$$
\begin{itemize}
\item[(i)]
List \marginpar{~~~[2]}all the pairs $(x_{k}, x_{r})$ such that $x_{k}$
could be the entering
variable and $x_{r}$
could be the leaving variable on a simplex iteration beginning from $(T')$.

\vspace{1.00in}
\item[(ii)]
List all \marginpar{~~~[2]}the pairs if the largest-coefficient rule for
choosing the
entering variable is being used.

\vspace{1.00in}
\item[(iii)]
List \marginpar{~~~[2]}all the pairs, if the smallest subscript rules for
choosing the
entering and leaving variables are being used.

\vspace{1.00in}
\item[(iv)]
List \marginpar{~~~[4]}all the pairs if the lexicographic rule for choosing
the leaving
variable is used. (Here you should use the fact that the initial feasible
basis was $(4,5,6)$.)
\end{itemize}
\end{itemize}

\newpage
\item[4.] continued,
\begin{itemize}
\item[(b)]
Consider the tableau
\[ (T) ~~~~~ \begin{array}{lclll}
x_{i}& +&\displaystyle \sum_{j \in N} \bar{a}_{ij} x_{j} &
 = & \bar{b}_{i} \ \ (i\in B)\\
z & - &\displaystyle \sum_{j \in N} \bar{c}_{j} x_{j}&= & \bar{v} .
\end{array} \]
Notice that another way to write the last row is
$$-z  + \displaystyle \sum_{j \in N} \bar{c}_{j} x_{j}=  -\bar{v} .$$
\begin{itemize}
\item[(i)]
Give \marginpar{~~~[3]}the basic solution associated with $(T)$.

\vspace{3.00in}
\item[(ii)]
Suppose \marginpar{~~~[3]}that $x_{k}$ is chosen as the entering variable,
and $x_{r}$ as the
leaving variable.
Give a formula for the value of $x_k$ in the new basic solution.

\vspace{3.00in}
\item[(iii)]
What does \marginpar{~~~[3]}it mean for an iteration or pivot of the
simplex method beginning from $(T)$ to be ``degenerate''?
\end{itemize}
\end{itemize}


\newpage
\item[5.]
Consider the problem
\[ (P) ~~~~~ \begin{array}{rrrcll}
\mbox{Maximize} & \displaystyle \sum^{n}_{j = 1} c_{j} x_{j} & & & \\
\mbox{subject to} & \displaystyle \sum^{n}_{j = 1} a_{ij} x_{j} & \leq &
b_{i} & ( i = 1, 2, \ldots , m) \\
 & x_{j} & \geq & 0 & (j = 1, 2, \ldots , n).
\end{array} \]
\begin{itemize}
\item[(a)]
Write \marginpar{~~~[2]}the dual, $(D)$, of $(P)$.

\vspace{2.50in}
\item[(b)]
State \marginpar{~~~[3]}the Weak Duality relation (or property) for $(P)$, $(D)$
.

\vspace{2.00in}
\item[(c)]
Prove  \marginpar{~~~[4]}the Weak Duality relation for $(P)$, $(D)$.
\end{itemize}

\newpage
\item[5.] continued,
\begin{itemize}
\item[(d)]
Consider \marginpar{~~~[2]}the linear programming problem
\[ (P) ~~~~~ \begin{array}{cccccccc}
\mbox{maximize} & 6x_1&+&3x_2&+&4x_3 \\
\mbox{subject to} & x_1&+&2x_2&+&x_3&\leq&8 \\
  &+5x_1&+&4x_2&+&3x_3&\leq&25 \\
 x_{j}  \geq  0,~\forall~j&  &
\end{array} \]
Write the dual $(D')$ of $(P')$.

\vspace{4.00in}
\item[(e)]
Notice that \marginpar{~~~[3]}the point $x=(1/2,0,15/2)^t,$
is feasible for $(P')$. Is it optimal? Justify your answer.
(Hint: Consider the point $y=(1,1).$)
\end{itemize}

\newpage
\item[6.]
\begin{itemize}
\item[(a)]
Suppose that $x^*$ \marginpar{~~~[5]} is the unique optimal solution of a
linear programming problem maximize $cx$ subject to $Ax=b,\ x\geq 0$,
where $A$ has $m$ rows and rank $m$. Must $x^*$ be  a basic solution?
Justify your answer.

\vspace{5.00in}
\item[(b)]
Consider \marginpar{~~~[5]}the linear constraints $Ax\leq b,\ x\geq 0$.
We want to determine whether the set of feasible solutions will change if
we drop the first constraint. Show how this can be determined by solving
one linear programming problem.
\end{itemize}
\end{enumerate}
\end{document}






