% $Header: /home/rdv/quantum/genetic-paper/RCS/eaqc-paper.tex,v 1.12 2005/05/29 21:34:00 rdv Exp rdv $
% now how do I set the paper size?
% \documentclass[twocolumn]{article}

\documentclass[onecolumn,doublespace]{article}
%\documentclass{acm_proc_article-sp-no-copyright}
% \usepackage{usenix,times}
\usepackage{times}
%\usepackage{times}
\usepackage{graphics}
\usepackage{lscape}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath,amsfonts,amssymb}
%\setlength{\textwidth}{6in}
%\setlength{\textheight}{9in}
%\setlength{\oddsidemargin}{0.25in}

\pagestyle{plain}

\bibliographystyle{unsrt}

% \input{psfig}
\input{epsf}
% \epsfverbosetrue

\newcommand{\icol}[1]{% inline column vector
  \left(\begin{smallmatrix}#1\end{smallmatrix}\right)%
}

\newcommand{\irow}[1]{% inline row vector
  \begin{smallmatrix}(#1)\end{smallmatrix}%
}

\begin{document}
\title{Optimization Theory (DS2) HW\#4\\
    Simplex in the Morning, Simplex in the Evening!}
\maketitle
\begin{abstract}
  Last homework on the simplex algorithm.  \emph{This homework counts
    for two homework sets!}
\end{abstract}

Problems and page numbers from the paperback edition of \emph{A Gentle
  Introduction to Optimization}, by B. Guenin \emph{et al.}


\begin{enumerate}
\item I am in Williamson, West Virginia, for an extended stay, and you are
coming from Japan to visit me.  ``Rice!  I need rice!'' I tell you.  I
offer to pay you \$3 above cost for each kilogram of Thai rice, \$2/kg
above cost for Chiba-ken mochigome, and \$1/kg for plain old
Nagano-ken koshihikari.  You visit the grocery store, where they have
15kg of Thaimai on the shelf, 5kg of mochigome, and 12kg of
koshihikari.  You can buy any combination, including fractional
kilograms.  However, the weight of your suitcase cannot exceed 22kg.
\begin{enumerate}
\item Write this as a linear program (inequalities okay).
\item Solve this in R.
\end{enumerate}

\item Take our favorite LP:
\begin{equation}
  \operatorname{max} z(\vec{x}) = (2,3,0,0,0)(x_1,x_2,x_3,x_4,x_5)^\intercal
\end{equation}
subject to
\begin{align}
  \left(
    \begin{array}{ccccc}
      1 & 1 & 1 & 0 & 0 \\
      2 & 1 & 0 & 1 & 0 \\
      -1 & 1 & 0 & 0 & 1 
    \end{array}
  \right)
  \vec{x} & =
  \left(
    \begin{array}{c}
      6 \\
      10 \\
      4
    \end{array}
  \right) \\
  x_1, x_2, x_3, x_4, x_5 & \ge 0.
\end{align}
and show that you can solve it in R using the {\tt simplex()} function.

\item Let's finish off the problem by hand (last time you'll have to
  do such grungy stuff by hand for the simplex algorithm, I promise).
  You will need to refer to both the lecture notes for Lec. 5 and the
  pseudocode for the simplex algorithm.

  The problem has already been carried through the first full
  iteration for you, and through the process of creating the next
  canonical form, in detail, ending in Lec. 5, Eqs. 26-29.  So here we
  will pick up the work at line 2 of the pseudocode, finding a basic
  solution.
\begin{enumerate}
\item Find a new basic solution, $\vec{x_a'}$.  (This involves picking
  an element $x_i$ to optimize for, using our temporary variable $t$,
  and applying the ratio test to maximize $t$ and therefore $x_i$.)
  Report both $\vec{x_a'}$ and the corresponding objective function
  value, $z_a' = z(\vec{x_a'})$.
\item Check to see if $\vec{x_a'}$ is optimal.  (If so, you are done!)
\item Pick a new element $k$ to add to the basis.
\item Test $A_k$ for unboundedness.
\item Conduct a new ratio test to pick the element you are going to
  remove from the basis.  (Careful with the indices $r$ and $\iota$
  here, it's a little bit tricky.)
\item Write down the new basis $B$.
\par At this point, you have completed the loop, up through step 9 in
  the lecture notes or the end of the pseudocode.
\item The next step (back at the top of the pseudocode) is to create a
  new version of the problem in canonical form for the new basis we
  just picked.
\end{enumerate}
At this point, you've been all the way around once.  I suppose that's
far enough... otsukaresama deshita on the simplex algorithm!  (And
let's all be grateful for computers that do the work for us!)
\end{enumerate}

\end{document}
