\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 = 3x_1-10x_2 + 2x_3+3x_4$\\subject to&$x_1 \geq 0$,
$x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$\\&$2x_1 -5x_2 + 4x_3
+3x_4 = 32$\\&$3x_1 +x_2 +2x_3+ x_4 \ge 12$
\end{tabular}

\item[(b)]
An engineering company manufactures industrial machines for
overseas export.  Demand for the next six months, which must be
satisfied, is shown in the following table.

\begin{center}
\begin{tabular}{lcccccc}
\hline Month&July&Aug&Sept&Oct&Nov&Dec\\
Demand&150&180&240&170&190&220\\ \hline
\end{tabular}
\end{center}



Capacity restrictions limit the production of machines to a
maximum of 200 per month.  However, it is possible to manufacture
machines before they are required.  In this case, there is a cost
of \pounds200 per machine in storage at the end of each month. At
the start of July, there are no machines in storage, and no stock
is required at the end of December.

The machines can be distributed to customers by aeroplane or by
ship.  Air transportation costs \pounds1000 per machine; sea
transportation costs \pounds750 per machine. Machines to be
transported by air are dispatched in the month that they are
required. On the other hand, machines to be transported by ship
must be dispatched one month in advance.

Write down a linear programming formulation (but do not attempt to
solve it) for the problem of planning production and distribution
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)]
Introduce a slack variable $s\geq0$, and artificial variables
$a_1\geq0,\ a_2\geq0$

\begin{tabular}{c|ccccccccc|c}
Basic&$z'$&$z$&$x_1$&$x_2$&$x_3$&$x_4$&$s$&$a_1$&$a_2$\\ \hline
$a_1$&0&0&2&$-5$&4&3&0&1&0&32\\ $a_2$&0&0&3&1&2&1&$-1$&0&1&12\\
\hline &1&0&&&&&&1&1&0\\ &1&0&$-5$&4&$-6$&$-4$&1&0&0&$-44$\\
0&1&$-3$&10&$-2$&$-3$&0&0&0&0
\end{tabular}

\begin{tabular}{c|ccccccccc|c}
Basic&$z'$&$z$&$x_1$&$x_2$&$x_3$&$x_4$&$s$&$a_1$&$a_2$\\ \hline
$a_1$&0&0&$-4$&$-7$&0&1&2&1&$-2$&8\\
$x_3$&0&0&$\frac{3}{2}$&$\frac{1}{2}$&1&$\frac{1}{2}$&$-\frac{1}{2}$&0&$\frac{1}{2}$&6\\
\hline &1&0&4&7&0&$-1$&$-2$&0&3&$-8$\\
&0&1&0&11&0&$-2$&$-1$&0&1&12
\end{tabular}


\begin{tabular}{c|ccccccccc|c}
Basic&$z'$&$z$&$x_1$&$x_2$&$x_3$&$x_4$&$s$&$a_1$&$a_2$\\ \hline
$s$&0&0&$-2$&$-\frac{7}{2}$&0&$\frac{1}{2}$&1&$\frac{1}{2}$&$-1$&4\\
$x_3$&0&0&$\frac{1}{2}$&$-\frac{5}{4}$&1&$\frac{3}{4}$&0&$\frac{1}{4}$&0&8\\
&1&0&0&0&0&0&0&1&1&0\\
0&1&$-2$&$\frac{15}{2}$&0&$-\frac{3}{2}$&0&$\frac{1}{2}$&0&16
\end{tabular}

Phase 1 ends, so discard $z',\ a_1,\ a_2$

\begin{tabular}{c|cccccc|c}
Basic&$z$&$x_1$&$x_2$&$x_3$&$x_4$&$s$\\ \hline
$s$&0&0&$-\frac{17}{2}$&4&$\frac{7}{2}$&1&36\\
$x_1$&0&1&$-\frac{5}{2}$&2&$\frac{3}{2}$&0&16\\
&1&0&$\frac{5}{2}$&4&$\frac{3}{2}$&0&48
\end{tabular}

Thus, we have an optimal solution

$$x_1=16\ x_2=0\ x_3=0\ z=48$$


\item[(b)]
Let the months be labeled $1,2,\ldots,6$. For month $t$ let

$x_t$=production

$y_t$=quantity sent by air

$z_t$= quantity sent by ship

$s_t$=end of month stock

\begin{tabular}{ll}
Minimize&$1000(y_1+\ldots+y_6)+750(z_1+\ldots+z_6)+200(s_1+\ldots+s_6)$\\
subject to&$x_t,y_t,z_t,s_t\geq0\ t=1,\ldots,6$\\ &$x_t\leq200\
t=1,\ldots,6$\\ &$s_{t-1}+x_t-y_t-z_t=s_t\ t=1,\ldots,6$
\end{tabular}

\begin{eqnarray*}
y_1&=&150\\ z_1+y_2&=&180\\ z_2+y_3&=&240\\ z_3+y_4&=&170\\
z_4+y_5&=&190\\ z_5+y_6&=&220\\ s_0&=*0\\ s_6&=&0
\end{eqnarray*}

\end{description}




\end{document}