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

\def\d{{\mathrm d}}

\begin{document}

\title{General Mathematics and CPS II}
\author{Exercise 16}
\date{April 4, 2014}
\maketitle

\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.  You may begin
by visualizing the feasible region in two and three dimensions first.

\emph{Remark:} These $n-m$ nonzero variables are the \emph{basic
variables} in the description of the simplex method.

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

\end{enumerate}

\end{document}
