\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 = 28x_1+36x_2 + 4x_3$\\ subject to&$x_1 \geq 0$, $x_2
\geq 0$, $x_3 \geq 0$\\&$4x_1 + 5x_2 + x_3 \leq 25$\\ &$2x_1 +
3x_2 +x_3 = 12$\\ &$6x_1 + 6x_2 - 2x_3 \geq 30.$
\end{tabular}

\item[(b)]
A company produces hand-made rugs. The expected demand for rugs
over the next six months is as follows.

\begin{center}

\begin{tabular}{lcccccc}
\hline Month&1&2&3&4&5&6\\ Demand&120&130&150&200&120&150\\ \hline
\end{tabular}

\end{center}

At the start of month 1, there are no rugs in stock. A worker
takes 20 hours to make a rug. There are 20 workers, and each works
for 140 hours per month, plus up to 40 hours per month of
overtime.  A worker is paid a fixed monthly wage for normal
working, plus \pounds30 per hour of overtime.  At the end of each
month, a holding cost of \pounds10 is incurred for each rug in
stock.

Write down a linear programming formulation (but do not attempt to
solve it) for the problem of planning rug production and overtime
working over the next six months so that demand is met at minimum
total cost.

\end{description}


ANSWER


\begin{description}

\item[(a)]
Introduce slack variables $s_1\geq0,s_2\geq0$ and artificial
variables $a_1,a_2\geq0$.

\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&4&5&1&1&0&0&0&25\\ $a_1$&0&0&2&3&1&0&0&1&0&12\\
$a_2$&0&0&6&6&$-2$&0&$-1$&0&1&30\\ \hline &1&&&&&&1&1&0\\
&1&0&$-8$&$-9$&1&0&1&0&0&$-42$\\ &&1&$-28$&$-36$&$-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&$\frac{2}{3}$&0&$-\frac{2}{3}$&1&0&$-\frac{5}{3}$&0&5\\
$a_1$&0&0&$\frac{2}{3}$&1&$\frac{1}{3}$&0&0&$\frac{1}{3}$&0&4\\
$x_2$&0&0&2&0&$-4$&0&$-1$&$-2$&1&6\\ \hline
&1&0&$-2$&0&4&0&1&3&1&$-6$\\ &0&1&$-4$&0&8&0&0&12&0&144
\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&0&$\frac{2}{3}$&1&$\frac{1}{3}$&$-1$&$-\frac{1}{3}$&3\\
$x_1$0&0&0&1&$\frac{5}{3}$&0&$\frac{1}{3}$&1&$-\frac{1}{3}$&2\\
$x_2$&0&0&1&0&$-2$&0&$-\frac{1}{2}$&$-1$&$\frac{1}{2}$&3\\ \hline
&1&0&0&0&0&0&0&1&1&0\\ &0&1&0&0&0&0&$-2$&8&2&156
\end{tabular}

\begin{tabular}{c|cccccc|c}
Basic&$z$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$\\ \hline
$s_1$&0&0&$-1$&$-1$&1&0&1\\ $x_1$&0&0&3&5&0&1&6\\
$s_2$&0&1&$\frac{3}{2}$&$\frac{1}{2}$&0&0&6\\ \hline
&1&0&6&10&0&0&168
\end{tabular}

Solution is $x_1=6,\ x_2=0,\ x_3=0,\ z=168$

\item[(b)]
For each month $j$, let

$x_j$ be the number of rugs produced

$I_j$ be the end of month inventory

$O_j$ be the number of hours overtime

Minimize $z=10(I_1+\ldots+I_6)+30(O_1+\ldots+O_6)$ subject to
$x_j\geq0, I_j\geq0,\ O_j\geq0\ j=1,\ldots,6$

\begin{eqnarray*}
x_1-I_1&=&120\\ I_1+x_2-I_2&=&130\\ I_2+x_3-I_3&=&150\\
I_3+x_4-I_4&=&200\\ I_4+x_5-I_5&=&120\\ I_5+x_6-I_6&=&150\\
20x_j&\leq&2800+O_j\ j=1,\ldots,6\\ O_j&\leq&800\ j=1,\ldots,6
\end{eqnarray*}

\end{description}




\end{document}