Question

Consider the single-facility rectilinear minimax location problem. Four existing facilities are located at (15,5),(3,8),(6,20),(6,13). The weights are 20,40,30,50, respectively.

Write a mathematical formulation which can be used to solve this problem. If necessary, linearize the model

Answer 1

The single-facility rectilinear minimax location problem is solved by finding the location that minimizes the maximum weighted rectilinear distance to existing facilities. A mathematical formulation is provided, and the linearization of the non-linear model with additional variables and constraints is explained for easier solution using linear programming techniques.

Step-by-step explanation:

The single-facility rectilinear minimax location problem aims to find the location of a new facility that minimizes the maximum weighted rectilinear distance to existing facilities. Given four existing facilities with coordinates (15,5), (3,8), (6,20), (6,13) and weights 20, 40, 30, 50 respectively, the objective is to minimize the maximum weighted distance to these facilities. Assuming the new facility's coordinates are (x,y), the mathematical formulation for this problem is:

• Minimize: Z = maxx-15

To linearize the model and make it solvable by linear programming techniques, additional variables and constraints are introduced to handle the absolute values:

1. Let D1, D2, D3, D4 be the distances from the new facility to each existing facility.
2. Introduce non-negative auxiliary variables to replace the absolute value expressions, for example, U1, U2, V1, V2 for the x and y coordinates respectively.
3. The new linear programming formulation becomes:
   1. Minimize: Z = max{20∙(D1), 40∙(D2), 30∙(D3), 50∙(D4)}
   2. Subject to:
   3. D1 ≥ U1 + V1, x-15 ≤ U1, 15-x ≤ U1, y-5 ≤ V1, 5-y ≤ V1
   4. D2 ≥ U2 + V2, x-3 ≤ U2, 3-x ≤ U2, y-8 ≤ V2, 8-y ≤ V2
   5. D3 ≥ U3 + V3, x-6 ≤ U3, 6-x ≤ U3, y-20 ≤ V3, 20-y ≤ V3
   6. D4 ≥ U4 + V4, x-6 ≤ U4, 6-x ≤ U4, y-13 ≤ V4, 13-y ≤ V4
   7. And all variables non-negative.