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

\newcommand{\x}{\boldsymbol{x}}
\newcommand{\y}{\boldsymbol{y}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}

\newcommand{\R}{\mathbb{R}}

\begin{document}

\title{General Mathematics and Computational Science II}
\author{Exercise 16}
\date{April 19, 2007}
\maketitle

\begin{enumerate}

\item Show that the leaving variable in one iteration of the simplex
method can never be the entering variable in the next iteration.

\item The \emph{primal} form of a linear programming problem is
\begin{equation*}
  \begin{gathered}
    \text{minimize } \c^T \x \\
    \text{subject to } A\x = \b, \x \geq 0 \,.
  \end{gathered}
  \tag{P}
\end{equation*}
The corresponding dual problem reads
\begin{equation*}
  \begin{gathered}
    \text{maximize } \y^T \b \\
    \text{subject to } \y^T A \leq \c^T \,.
  \end{gathered}
  \tag{D}
\end{equation*}
There $A$ is an $m\times n$ matrix, $\x, \c \in \R^n$, and $\y, \b \in
\R^m$. 

Show that if $\x$ solves (P) and $\y$ solves (D), then
\[
  \y^T\b \leq \c^T \x \,.
\]

\item In the notation of the previous question, show that if $\x$ is
feasible for problem (P) and $\y$ is feasible for problem (D), and if
furthermore
\[
  \y^T \b = \c^T \x \,,
\]
then $\x$ solves (P) and $\y$ solves (D).


\end{enumerate}
\end{document}
