\documentstyle[12pt]{article}
%
\def\baselinestretch {1.2}
\oddsidemargin 0.5cm
\textwidth 6in
\topmargin -0.5cm
\textheight 8.5in
\pagestyle{empty}
%
\pagestyle{empty}
\newtheorem{prop}{Proposition}[section]
\newtheorem{theorem}[prop]{Theorem}
\newtheorem{cor}[prop]{Corollary}
\newtheorem{lemma}[prop]{Lemma}
\newcommand{\myline}{\noindent \rule{\textwidth}{.02in} \medskip}
\newcommand{\matchings}{\noindent {\bf Matching Polyhedra} \medskip}
%
\newcommand\blackslug{\hbox{\hskip 1pt \vrule width 4pt height 8pt depth 1.5pt
        \hskip 1pt}}
  
\newenvironment{proof}{{\bf Proof:\ }}{{\quad\blackslug\medbreak}}
\newcommand{\oofx}{{\quad\blackslug\medbreak}}
\newcounter{ex}[section]
\newcommand{\ex}[1]{\refstepcounter{ex}\item[\thesection.\theex.]\label{#1}}
%
\def\eps{\varepsilon}
\def\minimize{\rm minimize}
\def\maximize{\rm maximize}
\def\R{{\bf R}}
\def\Z{{\bf Z}}
\def\bs{\backslash}
\newcommand{\ssp}{\renewcommand{\baselinestretch}{1}\large\normalsize}
\newcommand{\dsp}{\renewcommand{\baselinestretch}{1.5}\large\normalsize}
\begin{document}
                                                           
\centerline{\bf C\&O 350 Assignment 5, Due Thursday March 21, 1996}
\bigskip
\begin{enumerate}
\item Prove that $Ax\leq b$ has a solution if and only if there does not
exist $y$ such that $yA= 0$, $y\geq 0$ and $yb<0$. 
(Hint: Just imitate the proof of
the Farkas Lemma. First, show that not both $x$ and $y$ can exist (this is
easy). Then suppose that $x$ does not exist, and use duality to prove that
$y$ must exist.)

\item
\begin{enumerate}
\item Solve by the (two-phase) revised simplex method:
\[
\begin{array}{clcc}
\mbox{maximize} & 5x_1-x_2+x_3-10x_4+7x_5&&\\
\mbox{subject to}&&&\\
&3x_1-x_2-x_3& = &4\\
&x_1-x_2+x_3+x_4& = &1\\
&2x_1+x_2+2x_3~~~+x_5& = &9\\
&x_j\geq 0,~\forall j
\end{array}
\]
\item Solve by the revised simplex method, beginning with $B=
(1,2,6)$.
\[
\begin{array}{clcc}
\mbox{minimize} & 14x_1-19x_2~~~+21x_4+52x_5&&\\
\mbox{subject to}&&&\\
&x_1~~~~~~~~~~~-x_4+x_5+x_6& = &3\\
&x_1+x_2~~~~~-x_4+3x_5& = &4\\
&x_1+x_2+x_3-3x_4~~~+x_6& = &6\\
&x_j\geq 0,~\forall j
\end{array}
\]
\end{enumerate}

\item
Consider the (family) diet problem minimize($cx$ subject to $Ax\geq b,\ x\geq 0$),
where  the costs (in cents per kg) of 6 foods are given by
$c=(35,30,60,50,27,22)$; the minimum nutrient requirement for two nutrients,
vitamins A and C, are $b =( 9,19)^t$; and the nutrient contents of the foods
 are given in the matrix
\[ A =
\left[
\begin{array}{ccccccc}
1&0&2&2&1&2 \\
0&1&3&1&3&2 \\
\end{array}
\right]
\]
The basis $B=\{5,6\}$ is optimal for this problem.  (Found after adding
surplus variables $x_7,x_8.$)

\begin{enumerate}
\item
Suppose a new primary food, food 7, is available in the market at 88
cents/kg. One kilogram of this food contains two units of vitamin A and
four units of vitamin C. Should the family include this new food in its
diet? If not, how much should the cost of this food decrease before the
family can consider including it in its diet?
%At this breakeven cost, show that there is an optimum diet that
%includes food 7 and another that does not.
What is the optimum diet if food 7 is actually available at 32
cents/kg?
\item
For what range of cost per kilogram of primary food 4 does the
basis $B$ remain optimal to the original family's diet problem? If the
cost is  slightly too small to be in this range, find the new primal
solution after one revised simplex pivot.
\item
For what range of cost per kilogram of primary food 5 does the
basis $B$ remain optimal to the original family's diet problem? If the
cost is  slightly too large to be in this range, find the new primal
solution after one revised simplex pivot.
\item
What is the marginal effect of increasing the minimum requirement of
vitamin C on the cost of the optimal diet in the original family's diet
problem? How much can the minimal requirement of vitamin C increase
before the basis $B$ becomes nonoptimal to the problem?
%What is an optimal diet when this requirement is 39 units?
\end{enumerate}
\item
Consider the LP
\[
\begin{array}{clcc}
\mbox{maximize} & 2x_1+4x_2+x_3+x_4&&\\
\mbox{subject to}&&&\\
&x_1+3x_2~~~~+x_4& \leq &8\\
&2x_1+x_2              & \leq &6\\
&~~~~x_2+4x_3+x_4& \leq &6\\
&x_j\geq 0,~\forall j
\end{array}
\]
This problem represents the production plan of a company with 4
products, represented by the variables $x_j$, and utilizing 3 resources,
with availability given by the right-hand side of the constraints. The
slack variables $x_5,x_6,x_7$ correspond to the three constraints. The
basis $B=\{1,3,5\}$ is optimal.

\begin{enumerate}
\item
Compute the inverse of the basis matrix, $A_B^{-1}$, and optimal primal
and dual solutions.
\item
If the availability of only one of the resources can be marginally
increased, which one should be picked? Why?
\item
For what range of values of $b_1$ (resource material 1) does the basis
$B$ remain optimal?
%What is an optimal solution to the problem if
%$b_1=20?$
%\item
%If seven more units of resource 1 can be made available (over the
%present 8 units), what is the maximum you can afford to pay for it? Why?

\end{enumerate}

\end{enumerate}
\end{document}





