\documentclass[11pt]{article}
\input{../../preamble}
\usepackage{amsmath, latexsym}
\begin{document}
\problemset{5}{September 26, 2014}{5}{October 3, 2014}
\begin{enumerate}
\item (Strict Complementary Slackness) Consider the standard form linear programs, with primal LP $(\min c^Tx: Ax = b, x \geq 0)$ and dual LP $(\max b^Ty: A^Ty \leq c)$. Suppose the value of the two LPs is $\gamma$.
\begin{enumerate}
\item (3 points) Show that the set of optimal solutions to the primal is a convex set; argue the same for the dual.
\item (10 points) Show that either there exists an optimal solution $x$ to the primal such that $x_j > 0$ or there exists an optimal solution $y$ to the dual such that the $j$th inequality is strict; that is, $\sum_{i=1}^na_{ij}y_i < c_j.$ (Hint: Consider the linear program $(\min -e_j^Tx: Ax = b, -c^Tx \geq -\gamma, x \geq 0)$, where $e^j$ is a vector that has a 1 in the $j$th component, and 0 everywhere else).
\item (5 points) Show that there exist a primal optimal solution $x^*$ and a dual optimal solution $y^*$ such that $x^*_j > 0$ if and only if the $j$th inequality of the dual is met with equality.
\end{enumerate}
\item (12 points) Prove that if an index leaves the basis during an iteration of the simplex method, then that index cannot reenter the basis during the very next iteration.
\item (10 points) The indication for unboundedness in the simplex method shows the existence of feasible solutions to the primal problem with objective function values unbounded below. This implies via weak or strong duality that the dual problem is infeasible. Show how to obtain a short certification of the infeasibility of the dual from the quantities already computed.
\end{enumerate}
\end{document}