\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts,graphicx}

\begin{document}

\title{General Mathematics and ACM II}
\author{Exercise 16}
\date{April 8, 2011}
\maketitle

This exercise sheet is due Friday, April 29, 2011.  

\begin{enumerate}

\item  Find all solutions for the underdetermined linear system
$A\boldsymbol{x}=\boldsymbol{b}$, 
where
\begin{equation*}
  A =
  \begin{pmatrix}
    2 & 2 & 1 & 0 \\
    1 & 1 & 1 & 1 \\
    1 & 1 & 0 & -1 \\
    3 & 3 & 2 & 1
  \end{pmatrix}
  \qquad \text{and} \qquad
  \boldsymbol{b} =
  \begin{pmatrix}
    -1 \\ 1 \\ -2 \\ 0
  \end{pmatrix} \,.
\end{equation*}

\item Consider a linear programming problem with $n$ variables in
standard form.  Explain why a non-negative solution to $m \leq n$
equality constraints in which at least $n-m$ variables are zero
represents a vertex of the feasible region.

\emph{Hint:} Recall how the general solution to an underdetermined
system of linear equations looks like, cf.\ Question 1.  

\item Write the following linear programming problem in its standard
form.  

Maximize
\[
  z = 2 \, x_1 - x_2 + x_3
\]
subject to 
\begin{gather*}
  x_1 - x_2 \leq 1 \,, \\
  x_2 - x_3 \geq 1 \,, \\
  x_3 - x_1 \leq 3 \,, \\
  x_1 \geq -2 \,, \\
  x_2 \leq 1 \,, \\
  x_3 \leq 0 \,.
\end{gather*}

\item Solve the linear programming problem from Question 3 using the
simplex method.


\item Solve the following linear programming problem using the simplex
method.

Maximize
\[
  z = 3 \, x_1 + 4 \, x_2
\]
subject to
\begin{gather*}
  2 \, x_1 + x_2 \leq 4 \,, \\
  3 \, x_1 + 2 \, x_2 \leq 8 \,, \\
  x_i \geq 0 \text{ for } i=1,2 \,.
\end{gather*}



\end{enumerate}
\end{document}