\documentstyle[12pt]{article}
\oddsidemargin 0.0in
\evensidemargin 0.0in
\textwidth 7in
\addtolength{\topmargin}{-.75in}
\addtolength{\textheight}{1.5in}
\newtheorem{thm}{\mbox{}}

\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}}

\begin{document}

\begin{center}
Practice Problems\footnote{Solutions will not be provided. Note that this
list does
not cover all the course material. A description of the topics covered by the
exam is given at the end.}
\end{center}

\noindent
(1) For each of the LPs expressed in matrix notation, write down the duals
in matrix
notation.
\begin{enumerate}
\item
$\max ~{\bf cx},~~\mbox{s.t}~~\A {\bf x}\leq {\bf b},~{\bf x}\geq {\bf 0}.$
\item
$\max ~{\bf cx},~~\mbox{s.t}~~\A {\bf x}\leq {\bf b}.$
\item
$\min ~{\bf cx},~~\mbox{s.t}~~\A {\bf x}\geq {\bf b},~{\bf x}\geq {\bf 0}.$
\item
$\min ~{\bf cx},~~\mbox{s.t}~~\A {\bf x}\geq {\bf b}.$
\item
$\max ~{\bf cx},~~\mbox{s.t}~~\A {\bf x}= {\bf b},~{\bf x}\geq {\bf 0}.$
\item
$\max ~{\bf cx},~~\mbox{s.t}~~\A {\bf x}= {\bf b}.$

\end{enumerate}


\noindent
(2) State the duality theorem for general LPs (Theorem 9.1, page 141).

\vspace{.1in}
\noindent
(3) State the complementary slackness conditions for general LPs, and do
exercise
9.5, page 147.

\vspace{.1in}
\noindent
(4) Must a Phase 1 LP always have an optimal solution? Explain.

\vspace{.1in}
\noindent
(5) Prove theorem 5.5 (page 66). (Hint: If, for $i=1,...m$, $b_{i}$ is
replaced by
$b_{i}+t_{i}$, then
$${{\bf x}_{B}^{\ast}}^{\mbox{new}}={{\bf x}_{B}^{\ast}}^{\mbox{old}}+\sum
t_{i}(\mbox{column i of}~\A_{B})$$
 Thus, if ${{\bf x}_{B}^{\ast}}^{\mbox{old}}$ is
non-degenerate, and the $t_{i}$ are sufficiently small,
${{\bf x}_{B}^{\ast}}^{\mbox{new}}$ will be non-negative. See the handout on
sensitivity analysis.)


\vspace{.1in}
((6) and (7) are  easy questions. They simply test your
understanding of the definitions.)

\vspace{.1in}
\noindent
(6) If  a dual feasible dictionary for an LP is available, show that the LP
cannot be unbounded.

\vspace{.2in}
\noindent
(7) If  a primal feasible dictionary for an LP is available, show that the LP
cannot be infeasible.

\vspace{.2in}
\noindent
(8) Exercise 3.10, page 44.

\vspace{.2in}
\noindent
(9) If any LP has  more than one  feasible solution, show that it has infinitely
many feasible solutions.


\vspace{.2in}
\noindent
(10) If any LP has  more than one optimal solution, show that it has infinitely
many optimal solutions.

\vspace{.2in}
\noindent
(11) Suppose that a computer program which is capable of testing whether or
not a
given system of linear inequalities\footnote{Note that a linear equation may be
regarded as being equivalent to two liner inequalities. Thus, by a system
of linear
inequalities, we mean a system of linear inequalities and equations.} has a
feasible
solution is available. Show that such a program can be used for optimizing (i.e.
for solving LPs.) (Hint: Consider the equation $by-cx=0$, the difference
between the
dual objective function and the primal objective function equated to zero,
together
with all the primal constraints, and the dual constraints. This is a system
of linear
inequalities  in the
$m+n$ variables  $y_{1},\cdots,y_{m}$, and $x_{1},\cdots,x_{n}$. A feasible
solution to this system provides, simultaneously, an optimal solution to
the primal
and to the dual.)



\vspace{.2in}
\noindent
(12) A company has a demand to produce 380 units of product A and 425 units
of product B. It has three factories with hourly capacities:
factory 1 produces 8 units of A and 5 units of B at a cost of 47;
factory 2 produces 6 units of A and 10 units of B at a cost of 54;
factory 3 produces 4 units of A and 12 units of B at a cost of 56.
The company can also buy these two products on the open market. \\
The company must solve the following problems:
\begin{enumerate}
\item
Determine the number of hours each factory should runin order to meet
the demand and minimize cost.
\item
Determine the maximum amount that the company should pay if it chooses
to buy 380 units of A and 425 units of B and the maximum per unit prices
$p_a,p_b$ it should pay for A and B, respectively, so that the
purchasing cost of the yield of each factory does not exceed the total
cost of production.
\item
Formulate the above two problems as LP's.
\item
Show that the optimum solution to the first problem is x=(25,30,0) and
find the optimum solution to the second problem. Do not perform any
simplex operations but quote the relevant theorems to justify your
calculations.
\item
If a new factory that is being designed is expected to yield 5 units of
A and 5 units of B at a cost of 30 per hour, calculate the expected reduction
in cost per hour.
\end{enumerate}

\vspace{.2in}
\noindent
(13) Consider the LP:

$$
\vbox{{\openup1\jot\halign{
$#$&
$\hfil{}#{}$&$\hfil#$ &$\hfil{}#{}$& $\hfil#$&
$\hfil{}#{}$&$\hfil#$ &$\hfil{}#{}$& $\hfil#$&
$\hfil{}#{}$&$\hfil#$ &$\hfil{}#{}$& $\hfil#$&
$\hfil{}#{}$&$\hfil#$ &$\hfil{}#{}$& $\hfil#$&
$\hfil{}#{}$&$\hfil#$ &$\hfil{}#{}$& $\hfil#$&
$\hfil#$\cr
\max\ %
&  &27x_1 &+ &4x_2   &+ &7x_{3}    &+ &15x_4\cr
&  &2x_1 &  & x_2 &  &  &+ &7x_4 &\le &11\cr
&  & x_1 &+ &3x_{2}  &- & x_3 &+ &2x_4  &\le &0\cr
&  & 5x_{1}  &  &    &+ &2x_3 &- &2x_4 &\le &16\cr
}}
\hbox{\hskip 2.0cm$x_1,\ldots,x_4\ge0$}
}$$
The coefficients of the equality LP obtained by adding slack variables
$x_{5}$, $x_{6}$, and $x_{7}$ are as follows:
\[
\A=\left(\begin{array}{rrrrrrr}
~2~&~1~&~0~ &7~ &~1&0&0\\
~1~&~3~&-1~ &2~ &0&1&0\\
~5~&~0~&~2~&-2~&0&0&1
\end{array}\right) ~,~
\left(\begin{array}{c}
x^{\ast}_{5}\\
x^{\ast}_{6}\\
x^{\ast}_{7}
\end{array}\right)=
\left(\begin{array}{c}
11\\0\\16\end{array}\right)\]
\[~~c=\left(
\begin{array}{rrrrrrr}
~27,&4,&7,&15,&0,&0&0
\end{array}\right)\hspace{1.5in}
\]
The optimal basis for this LP is $\{4,1,3\}$. The coefficients of the final
dictionary,  are displayed in the following matrices:
\[
\overline{\A}=\left(\begin{array}{rrrrrrr}
~0~&~-\frac{1}{9}~&~0~&1~&~\frac{7}{45}&\frac{-4}{45}&\frac{-2}{45}\\
~1~&~\frac{8}{9}~&~0~&0~&\frac{-2}{45}&\frac{14}{45}&\frac{7}{45}\\
~0~&~\frac{-7}{3}~&~1~&0~&\frac{12}{45}&\frac{-39}{45}&\frac{3}{45}
\end{array}\right) ~,~
\left(\begin{array}{c}
x^{\ast}_{4}\\
x^{\ast}_{1}\\
x^{\ast}_{3}
\end{array}\right)=
\left(\begin{array}{c}
1\\2\\4\end{array}\right)\]
\[~~\overline{c}=\left(
\begin{array}{rrrrrrr}
~0,&-2,&0,&0,&-3,&-1&-4
\end{array}\right)\hspace{1.5in}
\]
\begin{enumerate}
\item
What is the basis matrix $\A_{B}$ relative to the basis $B=\{4,1,3\}$?
\item
What is the inverse of the matrix $\A_{B}$?
\item
What is the $y$ vector relative to the basis $B$?
\item
Write down the dual of the LP.
\item
Show that the above $y$ is an optimal solution to the dual.
\item
Over what range of values of the coefficient $c_{5}$ is $B=\{4,1,3\}$ an optimal
basis?
\item
Over what range of values of the coefficient $c_{4}$ is $B=\{4,1,3\}$ an optimal
basis?
\item
Over what range of values of the coefficient $b_{1}$ is $B=\{4,1,3\}$ an optimal
basis?

\end{enumerate}


\vspace{.1in}
\noindent
(14) Consider the system $Ax=b,~x\geq 0$ where
\[
A=\left(\begin{array}{rrrr}
3 & 3& -3& -1\\
-6& 3&  3&  4\\
4 &-8& -1& 4
\end{array}\right) ~~~~
b=\left(\begin{array}{r}
2\\3\\4
\end{array}\right)
\]
Either find a solution to $Ax=b,~x\geq 0$ or find a vector $y$ s.t.
$yA\geq 0,~ yb<0.$

\noindent
(15) Prove that exactly one of the following two systems has a
solution:
\begin{itemize}
\item [(i)] $Ax=0$, $x\ge0$, $x\ne0$.
\item [(ii)] $y^T A>0$.
\end{itemize}
 (Hint: Consider the primal LP
$$\max e^Tx,~\mbox{s.t}~~Ax=0, x\geq 0$$
where $e$ is the vector with each entry equal to 1. (Thus $e^{T}x$ is the same
as $\sum_{j=1}^{n}x_{j}$.) Observe that the system (i) in the statement has
a solution
if, and only if, the above LP is unbounded.)


\vspace{.1in}
\noindent
(16) Use (14) to decide if it possible to find real numbers $a$, $b$, $c$
and $d$, not all zero, such that
\begin{eqnarray*}
a^2+b^2+c^2&=&8d^2\\
8a^2+11b^2+10c^2&=&31d^2?
\end{eqnarray*}
(Hint: Write $a^{2}=x_{1}$, $b^{2}=x_{2}$, $c^{2}=x_{3}$, and  $d^{2}=x_{4}$. By
rearranging terms, you obtain a system of two homogeneous equations in four
variables. Does the system have a non-negative solution that is different from
zero?)

\vspace{.2in}
\noindent
(17) Explain the logic used in generating Gomory cuts in solving ILPs.


\vspace{.2in}
\noindent
(18) For each of the following statements, decide whether or not the
statement is
true.  If a statement is true, provide a proof of the statement, and if it
is false,
give a counter-example\footnote{Thinking about questions of this type is a
good way
of understanding the material. As you study the subject, pose  such questions
for yourself.}:

\begin{enumerate}
\item
Every optimal solution to an LP in standard form is a basic feasible solution.

\item
If an LP in standard form has a unique optimal solution $x^{\ast}$, then
$x^{\ast}$
is a basic feasible solution.

\item
The dual of an unbounded LP is unbounded.

\item
An optimal solution to an ILP (integer LP) can always be obtained by rounding
(up or down) the entries of an optimal solution to the LP relaxation of the ILP?


\end{enumerate}

\noindent
----------------------------------------------------------------------------
----------------------------------------------

\vspace{.25in}
\begin{center}
ABOUT THE FINAL
\end{center}

The topics covered by the exam will include chapters 1, 2, 3, and 5, plus the
material on the revised simplex method, methods for solving general LPs,
duals of general LPs (including complementary slackness conditions),
theorems of the
Farkas lemma type, sensitivity  analysis, and integer programming as covered in
lectures.

You should know the matrix formulas, and should be able to use them. They
feature
in the revised simplex method, and sensitivity analysis.

A good understanding of duality is important (read chapter 5). You should
have a clear
idea of the relationship between an LP and its dual. (You can often draw
inferences
concerning an LP from the properties of its dual. For example, if an LP is
unbounded,
then its dual is infeasible.)



There will be questions asking for definitions of
concepts. You will be required to know the statements of all the theorems,
and have
an intuitive understanding of their proofs. You should be able to use them to
derive simple consequences. (Definitions of concepts, and statements of theorems
should be stated in clear and precise language; intuitive explanations are not
acceptable. There will be some questions in which you would be required to
prove
simple propositions. Your answers to such questions should be clear and logical.
There will be no questions which require lengthy proofs.)

Computational questions will be selected so as not to involve ``horrible
fractions". (In some questions, you will only be required to do one
iteration, so
that you do not compound numerical errors.) You should display your calculations
carefully, and provide a brief explanation of your work.


\end{document}

You should know all the definitions concerning LPs,  dictionaries,  bases,
and basic
solutions. You should know the correspondence between bases, dictionaries, and
basic solutions.

You should know the matrix formulas and how to use them.

You should know the statements of all the theorems, and have an intuitive
understanding of their proofs. You will be expected to use them to derive simple
consequences.

\end{document}
