\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
Use the simplex method to find {\it all} optimal solutions of the
following linear programming problem.

\begin{tabular}{ll}
Maximize&$z = -2x_1+7x_2 + 4x_3$\\ subject to&$x_1 \geq 0$, $x_2
\geq 0$, $x_3 \geq 0$\\&$2x_1 - 5x_2  \leq 11$\\&$-x_1 + 3x_2 +x_3
= 7$\\ &$x_1 - 8x_2 + 4x_3 \geq 33.$
\end{tabular}

\item[(b)]
  A company needs to lease warehouse space over the next
five months.  The requirements for space in thousands of square
feet are shown in the following table.

\begin{tabular}{cccccc}
\hline &Month 1& Month 2& Month 3& Month 4& Month 5\\ \hline
Required space &45&30&50&20&60\\ \hline
\end{tabular}

It is possible to lease the exact space needed on a month-by-month
basis.  However, the cost per month becomes less as the period of
lease increases, so it may be more economical to lease the maximum
space needed for the entire five-month period. A variety of
intermediate strategies are also possible which may involve
starting two or more leases, each having a different leasing
period, in some months.  The cost per month of different length
leases is shown in the following table.

\begin{tabular}{lccccc}
\hline Leasing period (months)&1&2&3&4&5\\ \hline Cost (\pounds)
per 1000 square feet per month&600&480&420&380&350\\ \hline
\end{tabular}

Write down a linear programming formulation (but do not attempt to
solve it) for the problem of finding a leasing policy so that the
space requirements for the next five months are met at minimum
total leasing cost.

\end{description}

\bigskip

ANSWER


\begin{description}

\item[(a)]

Add slack variables $s_1,s_2$ and artificial variables $a_1,a_2.$

\begin{tabular}{c|ccccccccc|c}
Basic&$z'$&$z$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$&$a_1$&$a_2$\\ \hline
$s_1$&0&0&2&$-5$&0&1&0&0&0&11\\ $a_1$&0&0&$-1$&3&1&0&0&1&1&7\\
$a_2$&0&0&1&$-8$&4&0&$-1$&0&1&33\\ \hline &1&&&&&&&+1&+1&0\\
&1&0&0&5&$-5$&0&1&0&0&$-40$\\ &0&1&2&$-7$&$-4$&0&0&0&0&0
\end{tabular}

\begin{tabular}{c|ccccccccc|c}
Basic&$z'$&$z$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$&$a_1$&$a_2$\\ \hline
$s_1$&0&0&2&$-5$&0&1&0&0&0&11\\ $x_3$&0&0&$-1$&3&1&0&0&1&1&7\\
$a_2$&0&0&5&$-20$&0&0&$-1$&$-4$&1&5\\ \hline
&1&0&$-5$&20&0&0&1&5&0&$-5$\\ &0&1&$-2$&5&0&0&0&4&0&28
\end{tabular}

\begin{tabular}{c|ccccccccc|c}
Basic&$z'$&$-z$&$-x_1$&$-x_2$&$x_3$&$s_1$&$s_2$&$a_1$&$a_2$\\
\hline
$s_1$&0&0&0&3&0&1&$\frac{2}{5}$&$\frac{8}{5}$&$-\frac{2}{5}$&9\\
$x_3$&0&0&0&$-1$&1&0&$-\frac{1}{5}$&$\frac{1}{5}$&$\frac{1}{5}$&1\\
\hline &$-1$&0&0&0&0&0&0&1&1&0\\
&0&1&0&$-3$&0&0&$-\frac{2}{5}$&$\frac{12}{5}$&$\frac{2}{5}$&30
\end{tabular}

\begin{tabular}{c|cccccc|c}
Basic&$x$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$\\ \hline
$x_2$&0&0&1&0&$\frac{1}{3}$&$\frac{2}{15}$&3\\
$x_3$&0&0&0&1&$\frac{1}{3}$&$-\frac{1}{15}$&11\\
$x_1$&0&1&0&0&$\frac{4}{3}$&$\frac{1}{3}$&13\\ \hline
&1&0&0&0&1&0&39
\end{tabular}

Solution is $x_1=13,\ x_2=3,\ x_3=11,\ z=39$

Perform another iteration to find an alternative optimal solution.

\begin{tabular}{c|cccccc|c}
Basic&$x$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$\\ \hline
$s_2$&0&0&$\frac{15}{2}$&0&$\frac{5}{2}$&1&$\frac{45}{2}$\\
$x_3$&0&0&$\frac{1}{2}$&1&$\frac{1}{2}$&0&$\frac{11}{2}$\\ \hline
&1&0&0&0&1&0&39
\end{tabular}

An alternative optimal solution is $x_1=\frac{11}{2},\ x_2=0,\
x_3=\frac{25}{2},\ z=39$.

Thus
$(x_1,x_2,x_3)=\alpha(13,3,11)+(1-\alpha)\left(\frac{11}{2},0,\frac{25}{2}\right)$
for $0\leq\alpha\leq1$ is the class of all optimal solutions.

\item[(b)]
Let $x_{11},\ x_{12},\ x_{13},\ x_{14},\ x_{15}$ be the number of
square feet leased at the start of month 1 for 1, 2, 3, 4, 5
months respectively.

Variables

\begin{tabular}{ll}
$x_{21},\ x_{22},\ x_{23},\ x_{24}$&for month 2\\ $x_{31},\
x_{32},\ x_{33}$& for month 3\\ $x_{41},\ x_{42}$& for month 4\\
$x_{51}$& for month 5
\end{tabular}

are defined similarly.

Maximize
\begin{eqnarray*}
z=&&600(x_{11}+x_{21}+x_{31}+x_{41}+x_{51})\\
&&+960(x_{12}+x_{22}+x_{32}+x_{42})\\
&&+1260(x_{13}+x_{23}+x_{33})\\ &&+1520(x_{14}+x_{24})+1750x_{15}
\end{eqnarray*}

subject to $x_{ij}\geq0$ all $i,j$.
\begin{eqnarray*}
x_{11}+x_{12}+x_{13}+x_{14}+x_{15}&\geq&45\\
x_{12}+x_{13}+x_{14}+x_{15}&&\\
+x_{21}+x_{22}+x_{23}+x_{24}&\geq&30\\ x_{13}+x_{14}+x_{15}&&\\
+x_{22}+x_{23}+x_{24}&&\\ +x_{31}+x_{32}+x_{33}&\geq&50\\
x_{14}+x_{15}+x_{23}+x_{24}&&\\
+x_{32}+x_{33}+x_{41}+x_{42}&\geq&20\\
x_{15}+x_{24}+x_{33}+x_{42}+x_{51}&\geq&60
\end{eqnarray*}


\end{description}



\end{document}