This Location problem will determine the optimal location for a central unit in a ceiling sensor so that the maximum wire length to the central unit from three other units are minimized.
There are already three existing sensors, and if the ceiling were a coordinate system, the existing sensors are already located at (10,3), (5,15), and (20,25). Wires can only run along horizontal and vertical tracks in the ceiling, and a wire must run from each existing sensors to the central unit.
The linear programming model will determine the shortest length of total wire needed to connect each sensor to the central unit, and the desirable location of that unit.
The problem can be modeled as the following:
\[ minimize\quad max\big\{|x-5| + |y-15|, |x-10| + |y-3|, |x-20| + |y-25|\big\} \]
\[ subject\, to\; x,y\geq0 \]
However, this model is nonlinear due to the absolute values and the maximizing operation. As seen in class, we can rearrange this problem into the linear form
\[ minimize\quad f=f^{+}-f^{-} \]
\[subject\, to\quad \begin{gather*}f\geq(x_1^{+}+x_1^{-}) + (y_1^{+}+y_1^{-}) \\ f\geq(x_2^{+}+x_2^{-}) + (y_2^{+}+y_2^{-}) \\ f\geq(x_3^{+}+x_3^{-}) + (y_3^{+}+y_3^{-}) \\ x-5=x_1^{+}-x_1^{-}, y-15=y_1^{+}-y_1^{-} \\ x-10=x_2^{+}-x_2^{-}, y-3=y_2^{+}-y_2^{-} \\ x-20=x_3^{+}-x_3^{-}, y-25=y_3^{+}-y_3^{-} \\ x,y,x_1^{+},x_1^{-},y_1^{+},y_1^{-},x_2^{+},x_2^{-},y_2^{+},y_2^{-},x_3^{+},x_3^{-},y_3^{+},y_3^{-},f^{+},f^{-}\geq0 \end{gather*}\]
Below is the coding in SAGE to find the optimal solution.
|
|
|
|
The optimal objective value for the LP is (16, 0, 10, 19, 5, 0, 4, 0, 0, 0, 16, 0, 0, 10, 0, 6) The optimal objective value for the LP is (16, 0, 10, 19, 5, 0, 4, 0, 0, 0, 16, 0, 0, 10, 0, 6) |
The optimal objective solution for (x,y) is (10, 19) with an optimal value of 16 The optimal objective solution for (x,y) is (10, 19) with an optimal value of 16 |
In conclusion, we can use our optimal $x$ and $y$ values to see how what they do to the objective function. When $x=10$ and $y=19$,
\[ |x-5|+|y-15|=|10-5|+|19-15|=5+4=9 \]
\[ |x-10|+|y-3|=|10-10|+|19-3|=0+16=16 \]
\[ |x-20|+|y-25|=|10-20|+|19-25|=10+6=16 \]
Then the minimization of the maximum operation is $16$, which is our optimal objective value.
|