\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
Solve the following linear programming problem using the simplex
method.

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


\item[(b)]
A lawnmower manufacturer produces traditional (non-powered),
electric and petrol models.  Demand for the next two months is
shown in the following table.

\begin{center}

\begin{tabular}{lcc}
\hline Model&Month 1&Month 2\\ \hline Traditional&150&200\\
Electric&600&800\\ Petrol&200&250\\ \hline
\end{tabular}

\end{center}

For each lawnmower, the production cost, the time required by the
labour force for manufacture and the time required by the labour
force for assembly are shown in the following table; the current
inventory levels (at the start of month~1) are also listed.

\begin{tabular}{lcccc}
\hline &&Time for&Time for\\
&Production&manufacture&assembly&Current\\ Model&cost
(\pounds)&(hours)&(hours)&inventory\\ \hline
Traditional&20&3&5&30\\Electric&30&5&8&50\\ Petrol&45&6&9&20\\
\hline
\end{tabular}

Last month, the company used a total of $13\,000$ hours of labour.
The company's labour relations policy will not allow the combined
total hours of labour (manufacture plus assembly) to increase or
decrease by more than 500 hours from month to month.

There are end-of-month inventory holding costs.  For each
lawnmower in stock at the end of a month, the holding cost is 3\%
of its production cost.  The company requires at least 25
lawnmowers of each model to be in stock at the end of the second
month.

Write down a linear programming formulation (but do not attempt to
solve it) for the problem of planning  production so that demand
is satisfied at minimum total cost.  You may ignore any
requirements for variables to be integer-valued.


\end{description}

ANSWER


\begin{description}

\item[(a)]

\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&8&$-3$&3&1&0&0&0&21\\ $a_1$&0&0&3&2&1&0&0&1&0&6\\
$a_2$&0&0&$-2$&4&3&0&$-1$&0&1&15\\ \hline &1&&&&&&&1&1&0\\
&1&0&$-1$&$-6$&$-4$&0&1&0&0&$-12$\\ &0&1&18&$-4$&$-5$&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&$\frac{25}{2}$&0&$\frac{9}{2}$&1&0&$\frac{3}{2}$&0&30\\
$x_2$&0&0&$\frac{3}{2}$&1&$\frac{1}{2}$&0&0&$\frac{1}{2}$&0&3\\
$a_2$&0&0&$-8$&0&1&0&$-1$&$-2$&1&3\\ \hline
&1&0&8&0&$-1$&0&1&3&0&$-3$\\ &0&1&24&0&$-3$&0&0&2&0&12
\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&$\frac{97}{2}$&0&0&1&$\frac{9}{2}$&$\frac{21}{2}$&$-\frac{9}{2}$&$\frac{33}{2}$\\
$x_2$&0&0&$\frac{11}{2}$&1&0&0&$\frac{1}{2}$&$\frac{3}{2}$&$-\frac{1}{2}$&$\frac{3}{2}$\\
$x_3$&0&0&$-8$&0&1&0*$-1$&$-2$&1&3\\ \hline &1&0&0&0&0&0&0&1&1&0\\
&0&1&0&0&0&0&$-3$&$-4$&3&21
\end{tabular}

Phase 1 end: discard $z',\ a_1,\ a_2$.

\begin{tabular}{c|cccccc|c}
Basic&$z$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$\\ \hline
$s_1$&0&$-1$&$-9$&0&1&0&3\\ $s_2$&0&11&2&0&0&1&3\\
$x_3$&0&3&2&1&0&0&6\\ &1&33&6&0&0&0&30
\end{tabular}

Thus, an optimal solution is

$$x_1=0\ x_2=0\ x_3=6\ z=30$$


\item[(b)]
Let $x_i,\ y)i,\ z_i$ be the production of traditional, electric
and petrol lawnmowers in month $i$, for $i=1,2$.

Let $s_i,\ t_i,\ u_i$ be the stocks of traditional, electric and
petrol lawnmowers in month $i$, for $u=1,2$

Let $a_i,\ b_i$ be the increase and decrease in hours of labour
from month $i-1$ to $i$, for $i=1,2$.

Let $l_i$ be the labour hours in month $i$, for $i=1,2$.

\begin{center}

\begin{tabular}{ll}
Maximize&$z=20(x_1+x_2)+30(y_1+y_2)+45(z_1+z_2)$\\
&$+0.6(s_0+s_1+s_2)+0.9(t_0+t_1+t_2)+1.35(u_0+u_1+u_2)$\\ Subject
to&$x_i\geq0,y_i\geq0,z_i\geq0,i=1,2$\\
&$s_i\geq0,t_i\geq0,u_i\geq0,i=1,2$\\
&$l_i\geq0,a_i\geq0,b_i\geq0,i=1,2$
\end{tabular}

\end{center}

\begin{eqnarray*}
s_0&=&30\\ s_0+x_1-s_1&=&150\\ s_3+x_2-s_2&=&200\\ s_2&\geq25\\
t_0&=&50\\ t_0+y_1-t_1&=&600\\ t_1+y_2-t_2&=&800\\ t_2&\geq&25\\
u_0&=&20\\ u_0+z_1-u_1&=&200\\ u_1+z_2-u_2&=&250\\ u_2&\geq&25\\
l_1&=&8x_1+13y_1+15z_1\\ l_2&=&8x_2+13y_2+15z_2\\
l_1&=&l_0+a_1-b_1\\ l_2&=&l_1+a_2-b_2\\ a_1&\leq&500\\
b_1&\leq&500\\ a_2&\leq&500\\ b_2&\leq&500\\ l_0&=&4000
\end{eqnarray*}


\end{description}





\end{document}
