\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\usepackage{etex}
\usepackage[all]{xypic}
\setlength{\parindent}{0em}

\def\vx{\mathbf{x}}
\def\vc{\mathbf{c}}
\def\vb{\mathbf{b}}
\def\vy{\mathbf{y}}

\begin{document}

\thispagestyle{empty}



\begin{center}
	\Large\bf MATH 482, Spring 2013 - Homework 1
	
	\large (Will be) Assigned Wednesday, 09/04.
	
	\large Due Friday, 09/06.
\end{center}


\textbf{1.} (\emph{Assigned!}, 5pts)  Convert the following (general form) linear program into standard and canonical form:

\[\begin{array}{rccccccccl}
	\max & 3x_1 & - & 2x_2 & & & + & x_4 & \\
	\text{subject to} & x_1 & + & x_2 & - & x_3 & & & \geq & 1\\
	& & & 2x_2 & && + & x_4 &= & 0\\
	& && && x_3&-&3x_4& \leq & 6\\
	& x_1, & & x_2 &&&&&\geq& 0\\
&	&& && x_3 &&&\leq & 0\\
&	&& && && x_4 & & \text{free}
\end{array}\]


\vspace{1em}
\textbf{2.} Consider the linear programming formulation of the shortest paths problem. (\emph{The statements below are adjusted versions of the questions asked in class.})

\quad\textbf{a.} Produce a digraph whose shortest paths linear program has a feasible point with $x_{i,j} > 1$ for some edge $ij$.

\quad\textbf{b.} (\emph{Assigned!}, 5pts) Prove that for every digraph, every \emph{optimal} solution to the shortest paths linear program has $x_{i,j} \leq 1$ for all edges $ij$.

\quad\textbf{c.}  (\emph{Assigned!}, 5pts) Produce a digraph whose shortest paths linear program has an optimal point where at least one variable $x_{i,j}$ has $0 < x_{i,j} < 1$. (\emph{Hint: Consider what happens when there are multiple optimal solutions to the shortest paths problem.})

\quad\textbf{d.} Prove that for every digraph there exists an optimal solution to the shortest paths linear program where every variable $x_{i,j}$ has value in $\{0,1\}$. (\emph{Hint: Use duality, and look in the example implementation report 0.})


\vspace{1em}
\textbf{3.} Consider the following linear program:

\[
\begin{array}{rrcrcl}
\min & 2x_1 & + & 5x_2 & & \\
\text{subject to} & 3x_1 & + & x_2 & \geq & 6\\
& x_1 & & \geq & \frac{1}{2} \\
& x_1 & + & x_2 & \geq &1 \\
& 2x_1 & + & 5x_2 & \geq & 10 \\
& -x_1 & + & x_2 & \geq & -3\\
& -x_1 & - & x_2 & \geq & -100\\
& x_1, & & x_2 & \geq & 0
\end{array}
\]

\quad\textbf{a.} Plot the constraints and solve the problem graphically.

\quad\textbf{b.} List all of the basic feasible solutions.

\quad\textbf{c.} Characterize the optimal solutions in terms of optimal basic feasible solutions. 


\vspace{1em}
\textbf{4.} ((\emph{Assigned!}, 5pts)  Consider a standard-form linear program P
\begin{align*}
	\min \vc^\top \vx &\\
	\text{subject to } A\vx &= \vb\\
	\vx &\geq {\mathbf{0}} 
\end{align*}
Let D be the dual of P.
Prove that the dual of the dual of P is equivalent to P by forming the dual D, converting D into a standard form problem D', then forming the dual of D' (call it P') and converting P' into standard form.
Here is an outline:
\[
\xymatrix{
	\text{Standard Form problem P} \ar[rr]^{\text{take the dual}} & \qquad & \text{General problem D}\ar[dll]^<{\text{\qquad \qquad \qquad convert to standard form}}\\
	\text{Standard Form problem D'} \ar[rr]_{\text{take the dual}} & \qquad & \text{General problem P'}\ar[ull]_<{\text{\qquad \qquad \qquad convert to standard form}}
}\]

\end{document} 