\documentstyle[11pt]{article}
\oddsidemargin 0.0in
\evensidemargin 0.0in
\textwidth 6.75in
\addtolength{\topmargin}{-1.25in}
\addtolength{\textheight}{2.25in}
\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}
\pagestyle{headings}

\begin{center}
C \& O 350 \hspace{1.5in} ABOUT THE FINAL \hspace{1.5in}Fall 1995
\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, 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 chapters 5 and 9). You should
have a clear idea of the relationships\footnote{The weak duality relation,  the
duality theorem, and the complementary slackness conditions.} 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.)

Sensitivity analysis incorporates most of the theoretical ideas and techniques
developed in the course. For this reason, an understanding of this topic is
important.



There will be questions asking for definitions of
concepts\footnote{Some of the important concepts are: {\bf basis, basic
solution,
feasible solution, basic feasible solution, dictionarry, primal feasibility of a
dictionary (of a basis), dual feasibility of a dictionary  (of a basis).}}. 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 calcultions
carefully, and provide a brief explanation of your work.

\vspace{.15in}
\begin{center}
{\bf Practice Problems}\footnote{Solutions will not be provided. Note that this
list does  not cover all the course material.}
\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}\geq {\bf b},~{\bf x}\geq {\bf 0}.$
\item
$\max ~{\bf cx},~~\mbox{s.t}~~\A {\bf x}\geq {\bf b}.$
\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). (This is the same question as question 3 on the
last assignment. It is a good question to test your understanding of many
important ideas, such as the matrix formulas, sensitivity analysis,economic
significance of the dual variables, etc.)

\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 linear 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: Cosider 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 run in 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}

\newpage
\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 ${\bf y}$ vector relative to the basis $B$?
\item
Write down the dual of the LP.
\item
Show that the above ${\bf 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?
\item
If the constraint
$$x_{1}+x_{2}+x_{3}+2x_{4}\leq 6$$
is added to the given LP, will the current optimal solution
${\bf x}^{\ast}=(2,0,4,1)$ remain optimal? Explain. (If it is not optimal, find
the optimal solution. Do not solve the problem from scratch.)
\end{enumerate}

\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
(b) Solve the integer linear program. (If you wish, you may rearrange terms to
obtain and a dictionary and work with the dictionary.)


\vspace{.2in}
\noindent
(15) 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
(16) Consider the LP
$$\mbox{(1)}~~~~~\max {\bf cx}~s.t. ~{\bf Ax}={\bf b},~ {\bf x}\geq{\bf 0}$$
Let ${\bf x}^{\ast}$ be an optimal solution to (1) and let ${\bf y}^{\ast}$
be an optimal solution to its dual. We obtain a second LP (2) from (1) by
multiplying both sides of the first equality constraint by 2, and leave the
remaining unchanged. Find optimal solutions to (2) and its dual.

\begin{center}
\underline{{\bf C \& O 350 \hspace{1in} Assignment 6 \hspace{1in}
Do not Hand in Solutions}}
\end{center}

\begin{enumerate}
\item[(17)] {\bf CUTTING PLANES}\\
 Consider the following pure integer programming problem.
\[  (ILP)  \begin{array}{ccccccrcl}
 \max  & 18x_1 &+& 12x_2   \\
 \mbox{subject to} &   2x_1 &-&x_2   & + x_3&& = & 5\\
                   &   2x_1 &+&3x_2   & & +x_4& = & 13\\
       &  && && x_j & \geq & 0,& \mbox{and integer}~\forall j \\
  \end{array}
\]
\begin{enumerate}
\item
Draw the feasible set of the LP relaxation in two dimensions, i.e. note
that $x_3$ and $x_4$ are slack variables.
\item
Solve the LP relaxation.
\item
Find the optimal integer solution of ILP by generating a sequence of
cutting planes.
\end{enumerate}
\item[(18)] {\bf CUTTING PLANES}\\
 Consider the following pure integer programming problem.
\[  (ILP)  \begin{array}{ccccccrcl}
 \max  & -3x_1 &+& 4x_2   \\
 \mbox{subject to} &   6x_1 &-&4x_2   & \geq  & 15\\
                   &   x_1 &+&x_2   & \geq  & 5\\
                   &  4x_1 &+&2x_2   & \leq  & 31\\
       &  && && x_j & \geq & 0,& \mbox{and integer}~\forall j \\
  \end{array}
\]
\begin{enumerate}
\item
solve the problem graphically.
\item
Solve the LP relaxation graphically. Round the optimal solution to the
LP relaxation in every possible way (i.e. round each noninteger value
either up or down.) check these points for feasibility and compute the
objective values of those that are feasible. compare these with the
soluiton found in part (a).
\item
solve this problem by the cutting plane method. Solve the LP relaxation
of each subproblem graphically.
\end{enumerate}
\end{enumerate}

{\bf Solutions to questions 17 an 18 will be placed in the library.}

\end{document}





--========================_24179756==_--


