\documentstyle[12pt,fullpage]{article}
\begin{document}

\begin{center}
{\large\bf C\&O 350 \\ 
Assignment 5 
}
\end{center}

\begin{flushleft}
{\large  Due: Friday March 31 (\S 2, \S 3),
          Thursday March 30 (\S 1 )
}
\end{flushleft}

\begin{enumerate}
\item
Consider the LP problem
\[ (P)~ \max cx ~\mbox{s.t.}~Ax=b,~x \geq 0,
\]
where
\[
A = \left[ \begin{array}{ccccc}
  1&1&\frac 12&1&0 \\
  2&1&1&2&-1 \\
2&1&2&2&1   \end{array}  \right],~~
b = \left[ \begin{array}{c}
  2 \\
  2 \\
8   \end{array}  \right],~~
c = \left[ \begin{array}{ccccc}
  2&1&1&-7&1 
   \end{array}  \right].
\]
Consider the basis $B=\{1,3,5\}.$

You are given the basic solution $x^*$ corresponding to $B$, the
solution $y$ of $yA_B = c_B,$ and the inverse of $A_B$:

\[
A_B^{-1} = \left[ \begin{array}{ccc}
  3&-\frac 12&-\frac 12 \\
  -4&1&1 \\
2&-1&0       \end{array}  \right],~~
y = \left[ \begin{array}{ccc}
   4&-1&0
   \end{array}  \right],~~
x^* = \left[ \begin{array}{ccccc}
  1&0&2&0&2
   \end{array}  \right].
\]
You are also given that $x^*$ is optimal for (P).
\begin{enumerate}
\item
Suppose that the value of $c_2$ in (P) changes from 1 to 4. How would
you proceed to solve the new problem? Go as far as finding the entering
and leaving variables on the first pivot.
\item
Suppose that the value of $c_1$ in (P) is changed from 2 to $\theta.$
For what values of $\theta$ is $x^*$ optimal for the new LP?
\item
Suppose that a new variable $x_6$ is added to (P) with $c_6= \theta$ and
$A_6 = (-1,-4,17).$ For what values of $\theta$ does $B$ remain an
optimal basis?
\item
Using the matrix description of dictionaries, write down the dictionary
corresponding to the basis $B$.
\item
Suppose that the value of $b_3$ in (P) changes from 8 to 12. Solve the
resulting LP.
\end{enumerate}

\item
A dairy wishes to produce milk containing exactly $4\%$ butterfat, at
least $5\%$ protein, and at most $6\%$ lactose. It can buy milk from
three farms. Relevant information is tabulated below.

\begin{center}
\begin{tabular}{|c|ccc|c|}
\hline
Farm & Fat($\%$) &Protein ($\%$) &Lactose($\%$) &Cost/100lb \\
\hline
1 & 3 &5 &8 &\$6.80 \\
2 & 4 &4 &5 &\$7.50 \\
3 & 5 &7 &7 &\$8.30 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}
\item
Formulate an appropriate LP.
\item
Explain why there is no feasible solution composed only of milk from the
three farms.
\item
Suppose that we can add water. What is the minimum percent of water that
we can use to make an acceptable mix?
\item
Suppose that we can use all the water we wish. Formulate an appropriate
LP.
\item
What is the minimal cost of 100 pounds of acceptable milk that can be
mixed using the minimum possible amount of water?
\end{enumerate}

\item
Solve the following integer program using Gomory cuts.
\[
\begin{array}{lrcrcrcl}
\mbox{maximize}   & 2x_1 &-& 4x_2 &+&  x_3 &    &           \\
\mbox{subject to} &      & & 2x_2 &+& 3x_3 &\leq& 28,       \\
                  &  x_1 &-&  x_2 & &      &\leq& 12,       \\
                  &  x_1 &,&  x_2 &,&  x_3 &\geq&  0,~~\mbox{integers}. 
\end{array}
\]

\item
The following is a primal-feasible dictionary for a standard form
linear program:
\[
(D)~~~~~~\begin{array}{rclcl}
x_r &=& \bar{b}_r &-& \sum_{s \not\in B} \bar{a}_{rs}x_s~~~(r \in B)  \\
    & &           & &                                                 \\
  z &=& \bar{d}   &+& \sum_{s \not\in B} \bar{c}_s x_s
         \end{array}
\]
For each of the following statements, say whether the statement is
true or false, and justify your claim with a proof or a counterexample.
\begin{enumerate}
\item[(a)]
If $\bar{c}_s \leq 0$ for all $s \not\in B$ then the basic feasible solution
associated with $(D)$ must be optimal for the primal problem.
\item[(b)]
If $\bar{c}_s > 0$ for some $s \not\in B$ then the basic feasible solution
associated with $(D)$ cannot be optimal for the primal problem.
\item[(c)]
If $\bar{c}_s < 0$ for all $s \not\in B$ then the primal linear program
must have a unique optimal solution.
\item[(d)]
If $\bar{c}_s \leq 0$ for all $s \not\in B$
and $\bar{c}_s = 0$ for some $s \not\in B$
then the primal linear program must have more than one optimal solution.
\item[(e)]
If $(D)$ is nondegenerate and $\bar{c}_s \leq 0$ for all $s \not\in B$
then the dual problem must have a unique optimal solution.
\item[(f)]
If $(D)$ is nondegenerate and $\bar{c}_s > 0$ for some $s \not\in B$
then the basic feasible solution associated with $(D)$ cannot be optimal
for the primal problem.
\end{enumerate}

\end{enumerate}
\end{document}





