\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)] Four projects are being considered for execution over the
next three years. The expected returns for each project, yearly
expenditures and the maximum fund available each year (in millions
of pounds) are given in the following table.

\begin{tabular}{ccccc}
\hline &&Expenditure for year\\ Projects&Year 1&Year 2&Year
3&Returns\\ \hline 1&3&4&2&20\\ 2&4&3&2&20\\ 3&4&3&3&30\\
4&3&2&5&30\\ \hline Maximum funds&10&11&12\\ \hline
\end{tabular}

Assume that each approved project will be executed over the 3-year
period. The objective is to select projects that maximize the
total return. Give an integer programming formulation for this
problem.



\item[(b)]
A company supplies $10$ retail outlets, with Outlet $j$
requiring $d_j$ units monthly. The company can rent storage
facilities in up to $5$ warehouses, with Warehouse $i$ having a
storage capacity of $s_i$ units and a monthly rent fee of $r_i$.
There is a cost of $c_{ij}$ to ship one unit from Warehouse $i$ to
Outlet $j$. Let $x_{ij}$ be the number of units shipped monthly
from Warehouse $i$ to Outlet $j$, and $y_i=1$ if Warehouse $i$ is
used and $y_i=0$ otherwise. Give a mixed integer programming
formulation for the minimization of the total cost.

\item[(c)]
Solve the following integer programming problem by a branch and
bound algorithm.

\begin{tabular}{ll}
Maximize&$z = 3x_1 + x_2 + 4x_3$\\subject to&$6x_1 + 3x_2 +5x_3
\leq  25$\\&$3x_1 + 4x_2 +5x_3 \leq 20$\\&$x_i \geq 0$ and
integer, for $i=1,2,3$.
\end{tabular}

\end{description}


ANSWER

\begin{description}

\item[(a)]
The integer programming formulation is given by

\begin{tabular}{ll}
maximize&$z=20x_1+20x_2+30x_3+30x_4$\\ subject
to&$3x_1+4x_2+4x_3+3x_4\leq10$\\ &$4x_1+3x_2+3x_3+2x_4\leq11$\\
&$2x_1+2x_2+3x_3+5x_4\leq12$\\ &$0\leq x_i\leq1$ and integer
\end{tabular}

\item[(b)]
We have the following constraints:

\begin{enumerate}

\item
For the capacity of warehouse $i$

$$\sum_{j=1}^{10}x_{ij}\leq s_i\ i=1,2,\ldots,5$$

\item
For the demand at outlet $j$:

$$\sum_{i=1}^5x_{ij}=d_j\ j=1,2,\ldots,10$$

\item
For variable $y_i$:

$y_i=1$ if Warehouse $i$ is used or any one of $x_{ij}$ is
positive. Therefore we may set

$$y_i\geq\frac{\sum_{j=1}^{10}x_{ij}}{s_i}.$$

\end{enumerate}

The integer programming formulation is given by

\begin{tabular}{ll}
minimmize&$z=\sum_{i=1}^5\sum_{j=1}^{10}c_{ij}x_{ij}+\sum_{i=1}^5r_iy_i$\\
subject to&$\sum_{j=1}^{10}x_{ij}\leq s_i\ i=1,2,\ldots,5$\\
&$\sum_{i=1}^5x_{ij}=d_j\ j=1,2,\ldots,10$\\
&$y_i\geq\frac{\sum_{j=1}^{10}x_{ij}}{s_i},\ i=1,2,\ldots,5$\\
&$x_{ij}\geq0,\ (0\leq y_i\leq1\textrm{ and integer}).$
\end{tabular}


\item[(c)]

\setlength{\unitlength}{1cm}

\begin{picture}(10,10)

\put(4.5,8.7){\begin{tabular}{cc}$x_1=\frac{5}{3}$,&$x_2=0$\\
$x_3=3,$&$z=17$\end{tabular}}

\put(2.5,4.7){\begin{tabular}{cc}$x_1=1,$&$x_2=0$\\
$x_3=\frac{17}{5}$,&$z=16\frac{3}{5}$ \end{tabular}}

\put(6.5,4.7){\begin{tabular}{cc}$x_1=2,$&$x_2=0$\\
$x_3=\frac{13}{5},$&$z=16\frac{2}{5}$ \end{tabular}}

\put(.5,.7){\begin{tabular}{cc}$x_1=0,$&$x_2=0$\\
$x_3=4,$&$z=16$\\(optimal)\end{tabular}}

\put(4.5,1){\begin{tabular}{cc}$x_1=1,$&$x_2=\frac{1}{2}$\\
$x_3=3,$&$z=15\frac{1}{2}$\end{tabular}}

\put(6,8){\line(-1,-1){2}}\put(6,8){\line(1,-1){2}}
\put(4,4){\line(-1,-1){2}}\put(4,4){\line(1,-1){2}}

\put(3.8,7){$x_1\leq1$}\put(7.2,7){$x_1\geq2$}
\put(1.8,3){$x_3\geq4$}\put(5.2,3){$x_3\leq3$}

\end{picture}

\end{description}




\end{document}