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

from a set of n 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 cij $,$ i $=1,...,$ n$,$ j $=1,...,$ m$,$ and associated with opening each warehouse is a fixed cost

fi

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

Let

xij $=$

$($

$1,$ if store j is assigned to warehouse i$,$

$0,$ o$/$w$,$

i $=1,...,$ n$,$ j $=1,...,$ m$,$ and

yi $=$

$($

$1,$ if warehouse i is opened,

$0,$ o$/$w$,$

i $=1,...,$ n$.$

Then, the location$-$allocation model is:

min z $=$

Xn

i$=1$

Xm

j$=1$

cijxij $+$

Xn

i$=1$

fiyi

s$.$t$.$ Xn

i$=1$

xij $=1,$ j $=1,...,$ m$,$

Xm

j$=1$

xij $<=$ myi i $=1,...,$ n$,$

xij in $\{0,1\},$ i $=1,...,$ n$,$ j $=1,...,$ m$,$

yi in $\{0,1\},$ i $=1,...,$ n$.$

$(5)$

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:

Stores

$12345$

$1101520940$

$21217152010$

$31814103516$

$4912332819$

Questions:

$1.$ 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 a $1$ to indicate that the corresponding warehouse is open and $0$ otherwise.