Suppose that we have many towns spread across the country and we are trying to connect them with a network of roads. If we would like to do so by laying as little road as possible, how do we do it? In this blog post, we will use Calculus to tackle a special case of this optimization problem.
The case of four towns arranged in a square
Let us suppose that we have four towns arranged so that they form the four vertices of a square. Our task is then to connect them by the shortest network of roads possible so that each town is still connected to each other town. To make our problem more concrete, let us label our four towns A, B, C, and D, and assume that they are at the vertices of a square with side lengths 1 each.
Our first guess for such a road network might be to just join the four towns by a road network consisting of the four edges of the square. Four edges at length 1 each give a network of total length 4.
We then quickly notice that one of our roads is superfluous. If we remove any one of our four roads, we get a road system of length 3 that still connects our four cities.
We might assume that we are done now, but a little thinking outside of the box can get us a more efficient road system. The key insight here is that we could add extra junctions that aren’t cities. For example, something like this:
Reasoning Our Way to the Ideal Configuration of Roads
It turns out that a similar pattern of roads will be the most efficient way of connecting our four cities. To see why, we could imagine that we had an optimal configuration of roads. Clearly, this set of roads should never venture outside of our original square as that would be suboptimal. There must be a path connecting city A to city C, and a path connecting city B to city D. These paths must cross each other at least once but may do so many times. Let us call the first time that they cross point P and the last time that they cross point Q. Then, our network must have just consisted of the straight segments AP, BP, PQ, QC, and QD, as any other such network would have been longer.
We can also convince ourselves that an optimal road system should be vertically and horizontally symmetric, so our optimal network of roads must look something like this.
Most Efficient Road System Using Calculus
We suppose that the amount of inset of the center joining road from each side of the square is x. Then, our goal is to find the x that minimizes the total length of the road.
As with most calculus minimization functions, our process has three steps:
- Find the function ƒ(x) that we need to minimize.
- Find the first derivative ƒ'(x) and set it equal to zero. The minimum must occur at one of the zeroes of ƒ'(x).
- To test which zero is the minimum, we can then use the second derivative test. A local minimum occurs when ƒ"(x) > 0. Alternatively, we can check is the first derivative is negative right before our zero and positive right after our zero.
Step 1: Finding the function that we are minimizing
The middle portion PQ of our road system has length 1 - 2x and by the Pythagorean theorem, each of the other pieces AP, DP, QB, and QC has the following length:
Therefore, the function that we are trying to minimize is:
We notice that given the setup of our problem, the domain of our function is 0 ≤ x ≤ 0.5 since an x smaller than 0 would give a road system that exits the square and an x greater than 0.5 would give a negative length for one of our roads.
Step 2: Finding the zeroes of the first derivative
Now that we have our function, we have a calculus problem on our hands. To minimize the total length, we find the first derivative, set it equal to zero, and then solve for x.
Step 3: Checking if we have a minimum
We can ignore our zero at x = -1/(2√3) since this is outside the domain of our function.
We then want to check that our zero x = -1/(2√3) is a minimum to our function. We can see this by testing a point less than and greater than our zero. For example, we can see that ƒ'(0) < 0 and ƒ'(10) > 0. Since the first derivative goes from negative to positive near our zero, we know that we have a minimum. This also helps us conclude that the minimum does not occur at one of the boundary points of our domain, 0 or 0.5, since the function decreases and then increases as it traverses this domain.
Substituting x = -1/(2√3) back into ƒ(x), we get that ƒ(x) = 1 + √3, the minimum amount of road needed to connect our four cities. With a little further thought, we can even see that the optimal placement of roads occurs when the junctions at P and Q are placed very symmetrically: when each of the three angles based at P or Q has measure 120 degrees.
Voila! We have successfully used calculus to build the most efficient road network connecting our four towns.
Comments