This exercise comes from Bazaraa Linear Programming and Network Flows book :
Consider the problem of locating a new machine to an existing layout
consisting of four machines. These machines are located at the
following coordinates in two-dimensional space: $(3,1) ,(0,-3) ,(-2,2)$ and $(1,4)$.
Let the coordinates of the new machine be $(x_1,x_2)$ .The sum of the distances from the new machine to the four machines is
minimized. Use the street distance (also known as Manhattan distance
or rectilinear distance); for example, the distance from $(x_1,x_2)$ to the
first machine located at (3,1) is $|x_1 – 3| + |x_2 – 1|$·
the solution is definitely minimized $$|x_1 – 3| + |x_2 – 1| + |x_1 – 0| + |x_2 + 3| + |x_1 + 2| + |x_2 – 2| + |x_1 – 1| + |x_2 – 4|$$
But a solution guide I saw adds this :
$$|x_1 – 3| + |x_1 – 0| + |x_1 + 2| + |x_1 – 1| \geq 6$$
$$|x_2 – 1| + |x_2 + 3| + |x_2 – 2| + |x_2 – 4| \geq 10$$
I know those are sum of absolute values of specified points' location. But I can't figure out the whole reason of above solution.
Has anyone figured out?
Best Answer
The values of $x_1$ and $x_2$ that make the distance (street distance) a minimum are $0 \le x_1 \le 1$ and $1 \le x_2 \le 2$. Here's what I did:
Let $d_x(x_1)$ be the distance in the $x$ axis and $d_y(x_2)$ be the distance in the $y$ axis, given by:
$d_x(x_1)=|x_1 - 3|+ |x_1 - 0| + |x_1 + 2|+ |x_1 - 1|$
$d_y(x_2)= |x_2 - 1| + |x_2 + 3| + |x_2 - 2| + |x_2 - 4|$
Minimizing each function will give the coordinates $(x_1,x_2)$ that makes the total distance a minimum. The problem is the absolute value, so I got rid of it expressing $d_x(x_1)$ and $d_y(x_2)$ as piecewise functions:
$$ d_x(x_1)= \left\{ \begin{array}{1 1} -4x_1+2 & \quad x_1 \le -2 \\ -2x_1 +6 & \quad -2 < x_1 \le 0 \\ 6 & \quad 0 < x_1 \le 1 \\ 2x_1+4 & \quad 1 < x_1 \le3 \\ 4x_1-2 & \quad x_1 \ge 3 \end{array} \right.\ $$
$$ d_y(x_2)= \left\{ \begin{array}{1 1} -4x_2+4 & \quad x_1 \le -3 \\ -2x_2 +10 & \quad -3 < x_1 \le 1 \\ 8 & \quad 1 < x_2 \le 2 \\ 2x_2+4 & \quad 2 < x_2 \le 4 \\ 4x_2-4 & \quad x_2 \ge 4 \end{array} \right.\ $$
Here it is clear that the minimums are $6$ and $8$ (not $10$ as you said $|x_2 - 1| + |x_2 + 3| + |x_2 - 2| + |x_2 - 4| \ngeq 10$ )