\documentstyle[fullpage,12pt]{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 \\
Fall 1995 \\ Thursday, 26 October, 1995 \\
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 12 pages.
Make sure you have a complete paper.
\item[3.]
No calculating aids 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  10:00-11:30\\
\\
\large Section 2 & \large $\Box$ Murty & \large TR & \large 11:30-1:00\\
\\
\large Section 3 & \large $\Box$ Cunningham & \large TR & \large 1:00-2: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 & 20 & \\ \hline
& & \\
2 & 19 & \\ \hline
& & \\
3 & 18 & \\ \hline
& & \\
4 & 20 & \\ \hline
& & \\
5 & 18 & \\ \hline
& & \\
6 & 5  & \\ \hline
& & \\
Total & 100 & \\
& & \\ \hline
\end{tabular}
\end{center}
\end{minipage}
\end{titlepage}
$~~~~~~~~~$
\newpage
\begin{enumerate}
\item[1.]
\begin{itemize}
\item[(a)]
Solve \marginpar{~~~[12]}the following linear programming problem by
applying the simplex method. \newline
(Hint:  Use the largest coefficient rule.)
\[ \begin{array}{rrcrcrcr}
\mbox{maximize} & 6x_{1} & + & 2x_{2} & + & 2x_{3} & & \\
\mbox{subject to} & 2x_{1} & - & 2x_{2} & + & x_{3} & \leq & 4 \\
 & 4x_{1} & - & 4x_{2} & & & \leq & 9 \\
 & -2x_{1} & + & 3x_{2} & + & x_{3} & \leq & 2 \\
 & x_{1} & , & x_{2} & , & x_{3} & \geq & 0
\end{array} \]
\end{itemize}

\newpage
\item[1.] continued,
\begin{itemize}
\item[(b)]
Write \marginpar{~~~[6]}the dual of the problem of (a) and give an optimal
solution to the dual problem.

\vspace{5.00in}
\item[(c)]
Suppose \marginpar{~~~[2]}that in the problem of part (a), the right-hand
side of the third constraint is changed
from $2$ to $2 + \epsilon$, where $| \epsilon |$ is very small.
Give the optimal value (not an optimal solution) of the new problem.
\end{itemize}

\newpage
\item[2.]
\begin{itemize}
\item[(a)]
For \marginpar{~~~[3]}the linear programming problem
\[ (P) ~~~~~ \begin{array}{rrcll}
\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} \]
write the auxiliary problem (A) for finding an initial feasible solution.

\vspace{3.50in}
\item[(b)]
Prove \marginpar{~~~[6]}that (A) always has an optimal solution.
You may use the fundamental theorem of linear programming.
\end{itemize}

\newpage
\item[2.] continued,
\begin{itemize}
\item[(c)]
For \marginpar{~~~[10]}the following problem (P), construct the auxiliary
problem and solve it.
Hence give a feasible dictionary for (P).
{\bf (Do not solve (P).)}
\[ (P) ~~~~~ \begin{array}{rrcrcrcl}
\mbox{Maximize} & -3x_{1} & - & x_{2} & - & 4x_{3} & & \\
\mbox{subject to} & -x_{1} & - & x_{2} & - & x_{3} & \leq & -12 \\
 & -x_{1} & - & 2x_{2} & - & x_{3} & \leq & -6 \\
 & x_{1} & , & x_{2} & , & x_{3} & \geq & 0
\end{array} \]
\end{itemize}

\newpage
\item[3.]
\begin{itemize}
\item[(a)]
Define \marginpar{~~~[2]}the term ``basic solution'' of $Ax = b$.
(You may assume that $A$ is $m \times n$ with rank $m$.)

\vspace{2.00in}
\item[(b)]
Define \marginpar{~~~[2]}``degenerate basic solution'' of $Ax = b$.

\vspace{2.00in}
\item[(c)]
Consider \marginpar{~~~[6]}the dictionary
\[ (Dict) ~~~~~ \begin{array}{lclll}
x_{i} & = & \bar{b}_{i} - \displaystyle \sum_{j \in N} \bar{a}_{ij} x_{j} &
(i \in B) \\
z & = & \bar{v} + \displaystyle \sum_{j \in N} \bar{c}_{j} x_{j}. &
\end{array} \]
\begin{itemize}
\item[(i)]
Give the basic solution associated with (Dict).

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

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

\newpage
\item[3.] continued,
\begin{itemize}
\item[(d)]
Consider \marginpar{~~~[8]}the dictionary
\[  (Dict) ~~~~~ \begin{array}{rcrcrcrcr}
x_{6} & = & 4 & - & 2x_{2} & - & x_{3} & + & x_{5} \\
x_{4} & = & 2 & - & x_{2} & + & x_{3} & - & 2x_{5} \\
x_{1} & = & 6 & - & 2x_{2} & - & 2x_{3} & - & 3x_{5} \\
z & = & 5 & + & 2x_{2} & - & 2x_{3} & + & 3x_{5}
\end{array} \]
\begin{itemize}
\item[(i)]
List 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 (Dict).

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

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

\vspace{1.00in}
\item[(iv)]
List all the pairs if the lexicographic rule for choosing the leaving
variable is used,
and the constant terms of the first three equations of the dictionary are
changed as
follows:

\[  \begin{array}{rcrclcrcrcr}
x_{6} & = & 4 & + & 2 \epsilon_{1} - 2 \epsilon_{2} & - & 2x_{2} & - &
x_{3} & + & x_{5} \\
x_{4} & = & 2 & + & \epsilon_{1} + \epsilon_{2} + 3 \epsilon_{3} & - &
x_{2} & + & x_{3} & - & 2x_{5} \\
x_{1} & = & 6 & + & 2 \epsilon_{1} & - & 2x_{2} & - & 2x_{3} & - & 3x_{5} \\
z     & = & 5 &   &                & + & 2x_{2} & - & 2x_{3} & + & 3x_{5}
\end{array} \]
\end{itemize}
\end{itemize}

\newpage
\item[4.]
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.00in}
\item[(b)]
State \marginpar{~~~[2]}the Weak Duality relation (or property) for (P), (D).

\vspace{2.00in}
\item[(c)]
State \marginpar{~~~[3]}the Duality Theorem for (P), (D).

\vspace{2.00in}
\item[(d)]
State \marginpar{~~~[3]}the Complementary Slackness Conditions for (P), (D).
\end{itemize}

\newpage
\item[4.] continued,
\begin{itemize}
\item[(e)]
For \marginpar{~~~[10]}the problem
\[ \begin{array}{rrcrcrcrcr}
\mbox{Maximize} & 7x_{1} & & & & & + & 9x_{4} & & \\
\mbox{subject to} & 2x_{1} & - & x_{2} & + & x_{3} & - & 2x_{4} & \leq & 5 \\
 & 3x_{1} & + & x_{2} &  &  & + & 3x_{4} & \leq & 3 \\
 & x_{1} & , & x_{2} & , & x_{3} & , & x_{4} & \geq & 0
\end{array} \]
use the Complementary Slackness Theorem to check whether each of the
following are
optimal solutions.
\begin{itemize}
\item[(i)]
$x^{\ast} = (1, 0, 3, 0)^{T}$
\item[(ii)]
$x^{\ast} = (0, 0, 7, 1)^{T}$
\end{itemize}
\end{itemize}

\newpage
\item[5.]
For each of the following statements, tell whether the statement is true or
false, and give
a brief reason for your answer.
\begin{itemize}
\item[(a)]
If \marginpar{~~~[3]}a linear programming problem has an optimal solution,
then its dual has a feasible solution.

\vspace{2.00in}
\item[(b)]
If \marginpar{~~~[3]}a linear programming problem is unbounded, then its
dual is infeasible.

\vspace{2.00in}
\item[(c)]
If \marginpar{~~~[3]}a linear programming problem is infeasible, then its
dual is unbounded.

\vspace{2.00in}
\item[(d)]
If \marginpar{~~~[3]}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}

\newpage
\item[5.] continued,
\begin{itemize}
\item[(e)]
If \marginpar{~~~[3]}in an iteration of the simplex method, $x_{k}$ is
chosen as the entering variable and
there is a unique choice for the leaving variable, then the new basic
solution is not
degenerate.

\vspace{2.00in}
\item[(f)]
If \marginpar{~~~[3]}a dictionary satisfies $\bar{b}_{i} \geq 0$ for all $i
\in B$, and no simplex iteration starting
from it gives a better objective value, then the basic solution associated
with the dictionary is optimal.
\end{itemize}

\newpage
\item[6.]
Prove \marginpar{~~~[5]}that if $x=0$ is not an optimal solution of the problem
\[ (P) ~~ \begin{array}{rrcr}
\mbox{maximize} & cx & \\
\mbox{subject to} & Ax & \leq & 0 \\
 & x \geq & 0
\end{array} \]
then (P) is unbounded.

\end{enumerate}
\end{document}






