\documentclass[11pt]{article}
\input{../../preamble}
\usepackage{amsmath, latexsym}
\begin{document}
\problemset{7}{October 10, 2014}{7}{October 17, 2014}
\begin{enumerate}
\item (10 points) In class, we started to describe the capacitated simplex method for solving linear programs of the form $\min c^Tx: Ax = b, \ell \leq x \leq u$. We noted that its dual is $\max b^Ty - u^Tv + \ell^T w: A^Ty -v + w = c$, and that for any $y$, we can have a dual feasible solution by setting $v = \max(0,A^Ty - c)$ and $w = \max(0, c-A^Ty)$. We stated that the main idea is now to maintain three sets of indices of the primal variables: $B$ the basic variables, $L$ the variables set to their lower bounds, and $U$ the variables set to the upper bounds, so that associated with these sets, we have a solution $x$ in which we set $x_j = \ell_j$ for all $j \in L$, $x_j = u_j$ for all $j \in U$, and $x_B = A^{-1}_B(b - A_Uu_U - A_L\ell_L)$; we assume the primal is feasible, which is true if $\ell_B \leq x_B \leq u_B$.
Given the dual solution $y = (A_B^T)^{-1}c_B$, and the normal reduced costs $\bar c = c - A^Ty$, we argued in class that the current primal and dual are optimal if $\bar c_j \geq 0$ for all $j \in L$ and $\bar c_j \leq 0$ for all $j \in U$. Finish the description of the simplex method by describing what should happen from this point on: if the solutions are not optimal, how should $x$, $B$, $L$, and $U$ be altered so that $x$ remains feasible and so that we make progress if the current solution is not degenerate? How do we know that the updated $B$ is a basis?
\end{enumerate}
\end{document}