Description
1. In Table 1, the locations of eight existing facility units and their weights are given.
a. (15 pts) Solve the minisum location problem to determine the
location of a new repair show to serve all these existing facilities.
b. (15 pts) Solve the minimax location problem to determine the
location of a fire department to serve all existing facilities and the
new repair shop considered in part a.
c. (20 pts) Now assume two fire stations will be placed, but the
coordinates should be an integer (indicating the central locations
in a grid partition). Formulate a linear programming model that
can be used to find the locations of the new fire stations.
2. (50 pts) Consider the layout planning problem over a three-by-four grid (shown in Figure 1) where the
facility units each require a single cell in the grid.
A B C D
E F G H
I J K L
Figure 1: grid layout
The flow between the five facility units we need to place is given in Table 2.
D1 D2 D3 D4 D5
D1 – 100 50 0 0
D2 75 – 50 50 25
D3 100 25 – 0 0
D4 0 0 50 – 50
D5 50 0 50 25 –
Table 2: Flow amounts between facility units
a. (20 pts) Consider the following limitations and write a quadratic assignment formulation to solve the
layout planning problem.
– D1 and D4 cannot share an edge
– D1, D2, and D5 cannot be placed in grids A,D,L, or I.
– D3 cannot be placed in grid locations other than A,D,L, and I.
b. (30 pts) Solve the model you produced in part a with your favorite math solver (10 pts bonus for the
solution with the minimum solution value).
Facility 𝑎! 𝑏! W
D1 2 3 5
D2 4 4 10
D3 3 5 8
D4 1 3 7
D5 2 6 6
D6 4 6 10
D7 1 5 6
D8 5 5 5
Table:1 Existing facility units
