Problem #$2$

Consider the following integer$-$linear program which $is$ used $to$ decide which warehouses $to$ open

from a set $ofn$ potential warehouses, and how $to$ assign $m$ retail stores $to$ the opened warehouses

$(for$ receiving supplies$).$ Note that each retail store must $be$ assigned $to$ exactly one warehouse.

Each warehouse can serve all the retail stores. Associated with each assignment $is$ a transportation

$cost{c}_{ij},i=1,$dots,$n,j=1,$dots,$m,$ and associated with opening each warehouse $is$ a fixed cost

$f_i,i=1,$dots,$n.We$ seek $to$ minimize the total cost. This $is$ known $as$ a location$-$allocation model.

Let $I=\{1,$dots,$n\},J=\{1,$dots,$m\}$

$x_{ij}=\{\begin{array}{ccc}1,& if\text{s}\text{t}\text{o}\text{r}\text{e}\text{j}\text{i}\text{n}\text{J}is\text{a}\text{s}\text{s}\text{i}\text{g}\text{n}\text{e}\text{d}to\text{w}\text{a}\text{r}\text{e}\text{h}\text{o}\text{u}\text{s}\text{e}& \text{i}\text{i}\text{n}\text{I}\text{,}\\ 0,& \frac{\text{@}}{w},\end{array}$

and

$y_i=\{\begin{array}{ccc}1,& if\text{w}\text{a}\text{r}\text{e}\text{h}\text{o}\text{u}\text{s}\text{e}\text{i}\text{i}\text{n}\text{I}is\text{o}\text{p}\text{e}\text{n}\text{e}\text{d}\text{,}& \\ 0,& \frac{\text{@}}{w}\end{array}$

Then, the location$-$allocation model $is$:

min:,$z={\displaystyle \underset{i=1}{\overset{n}{}}}{\displaystyle \underset{j=1}{\overset{m}{}}}{c}_{ij}{x}_{ij}+{\displaystyle \underset{i=1}{\overset{n}{}}}{f}_i{y}_i$

$s.t$: ${\displaystyle \underset{i=1}{\overset{n}{}}}{x}_{ij}=1,$jinJ,

$,{\displaystyle \underset{j=1}{\overset{m}{}}}{x}_{ij}m{y}_i,$iinI,

$,x_{ij}in\{0,1\},$iinI,jinJ,

$,y_{i}in\{0,1\},$iinI.

Assume that $n=4,m=5,$ and that the fixed cost for opening a warehouse $is$ $$20,000$ for each

$of$ four warehouses. The transportation costs for all pairs $of$ warehouses and stores $(in$ thousands$)$

are provided $in$ the table below:

Questions:

For the solution $1,0,0,1$ which represents that warehouses $1$ and $4$ are open, compute the

total cost, $z(x,y)$ and describe how you did $so.$ Note that the notation for solutions that $we$

will use uses $a1to$ indicate that the corresponding warehouse $is$ open and $0$ otherwise.

Run Tabu Search for five iterations with tenure period $=2,$ and starting with the solution

$1,0,0,1.$ A neighborhood here $is$ defined $as$ a solution $in$ which the status $of$ only one

warehouse $is$ flipped, $i.e.,$ you can flip one warehouse from being open $to$ being closed $or$ vice

versa $to$ generate a neighbor $(exceptif$ that warehouse $ison$ the Tabu list$).If$ a warehouse

$is$ flipped from open $to$ closed $or$ vice versa, that warehouse $(not$ the entire solution$)$ should

then $goon$ the Tabu list. Use random$-$walk selection for