I just started a class on Mathematical Modeling, and I am having trouble with this linear programming problem (translated from another language):
The mayor of a 6 city neighborhood has to determine where to build firehouses (all of the same cost) with the minimum budget. The mayoralty wants to make sure that there is at least one firehouse less than 16 minutes away from any of the 6 neighborhoods. Write a linear optimization problem to determine how many firehouses have to be built and where. Get the answer in Matlab. The following time table tells us how long it takes to go from one neighborhood to another:
$$\begin{array}{c|c|c|} & \text{N1} & \text{N2} & \text{N3} & \text{N4} & \text{N5} & \text{N6} \\ \hline \text{N1} & 0 & 10 & 20 & 30 & 30 & 20 \\ \hline \text{N2} & 10 & 0 & 25 & 35 & 20 & 10 \\ \hline \text{N3} & 20 & 25 & 0 & 15 & 30 & 20 \\ \hline \text{N4} & 30 & 35 & 15 & 0 & 15 & 25 \\ \hline \text{N5} & 30 & 20 & 30 & 15 & 0 & 14 \\ \hline \text{N6} & 20 & 10 & 20 & 25 & 14 & 0 \\ \hline \end{array}$$
I am not really sure how to define the variable(s), and the only "constraint ideas" I can come up with are that there can either be $0$ or $1$ firehouses per neighborhood, and that there can't be any numbers greater than 16 in the "answer matrix".
P.S.: this is my first post so apologies for the newbie formatting and the mistakes I might have made in any way or form during the post. Any help would be very much appreciated, thanks!
The first step is to define the decision variables. Let binary decision variable $x_i$ indicate whether a firehouse is built in neighborhood $i$. The objective is to minimize $\sum_{i=1}^6 x_i$. Now you need a constraint that each neighborhood must be covered by some firehouse that is at most $16$ minutes away. For example, neighborhood $1$ is covered only if a firehouse is built in neighborhood $1$ or $2$ (the other neighborhoods are more than $16$ minutes away), so impose linear constraint $x_1 + x_2 \ge 1$. Now do something similar for each of the other $5$ neighborhoods.