ROADMIN BRIEF ABSTRACT Here's a nice minimization problem to get your students thinking: Pave the smallest amount of connecting roads as possible between four homes located at the vertices of a one square mile field. Differential calculus of a single variable and an open-mind are prerequisites. GENERAL INFORMATION FileName: ROADMIN Full title: The Road Less Paved Last Update: 6/4/96 Developer: Kimberly Foltz, Mathematics and Computer Science Division, Indiana Academy for Science, Mathematics, & Humanities, Muncie IN 47306 USA Contact: Aaron Klebanoff, Department of Mathematics, Rose-Hulman Institute of Technology, Terre Haute, IN 47803 USA. Phone: 812-877-8151. Email: Klebanoff@rose-hulman.edu.FAX: 812-877-3198. Support: The production of this material is supported by the National Science Foundation under Division of Undergraduate Education grant DUE-9352849: Development Site for Complex, Technology-Based Problems in Calculus with Applications in Science and Engineering and the Arvin Foundation of Columbus IN. STATEMENT OF PROBLEM Four houses are located so that they form the vertices of a square which has sides of length 1 mile. These neighbors desire to connect their houses with roads in a manner that is as inexpensive as possible. The cost of building one unit of road is constant in the entire region. Construct this system of roads in the most cost-effective way possible. (It may not be as obvious as you first may think!) Determine the total length of this system of roads. Describe the path that is formed by the roads. KEYWORDS Graph theory, Steiner points, optimization TEACHER NOTES ISSUES RELATED TO THE PROBLEM As a teacher in class you might want to discuss some of the obvious possibilities which we list below and hint at the combination which we offer in the solution. Further there should be a good discussion of whether or not we really have the optimal case. After all, we may not have considered ALL the possibilities. Students should come away from this problem with some confidence, but with some small element of question about whether or not they really have the absolute minimum and the just right layout. Since the paving costs are uniform throughout this neighborhood, it is reasonable to approach the problem of minimizing the cost by minimizing the total length of the road system used to connect the houses. Thus, the question becomes what is the minimum length of road that will be necessary to provide a path from one house to any of the other houses. HORIZONTAL AND VERTICAL ROADS An obvious way to connect the houses would be to build the road so that it traces the path of the square . This would produce a system of roads of length 4 miles. (The code follows for this figure.) In[2]:= houses=Graphics[ { PointSize[.03], Point[{0,0}], Point[{1,0}], Point[{0,1}], Point[{1,1}] } ]; In[3]:= road4=Graphics[ { Line[ { {0,0},{0,1} } ], Line[ { {0,0},{1,0} } ], Line[ { {0,1},{1,1} } ], Line[ { {1,0},{1,1} } ] }]; In[4]:= Show[road4, houses, AspectRatio->Automatic, PlotLabel->"length=4 miles"] Out[4]= -Graphics- Certainly we can do better than this! The length is improved by omitting any one of the sides of this square, decreasing the total distance by 1 mile. (The code follows for this figure.) In[5]:= road3=Graphics[ { Line[ { {0,0},{0,1} } ], Line[ { {0,0},{1,0} } ], Line[ { {0,1},{1,1} } ] }]; In[6]:= Show[road3, houses, AspectRatio->Automatic, PlotLabel->"length=3 miles"] Out[6]= -Graphics- OBLIQUE ROADS Rather than traveling around the perimeter, what if we attempt to move within the square to build the roads. The same result from above can be achieved by relocating the endpoints of the vertical road to some arbitrary position in between the houses. (The code follows for this figure.) In[7]:= road3arb=Graphics[ { Line[ { {.35,0},{.35,1} } ], Line[ { {0,0},{1,0} } ], Line[ { {0,1},{1,1} } ] }]; road3mid=Graphics[ { Line[ { {3,0},{3,1} } ], Line[ { {2.5,0},{3.5,0} } ], Line[ { {2.5,1},{3.5,1} } ] }]; houses2=Graphics[ { PointSize[.02], Point[{2.5,0}], Point[{3.5,0}], Point[{2.5,1}], Point[{3.5,1}] } ]; In[10]:= Show[road3arb,road3mid,houses,houses2, AspectRatio->Automatic, PlotLabel->"length=3 miles"] Out[10]= -Graphics- Is it possible to do any better than a distance of 3 miles? We know the shortest distance between two points is a straight line. Thus, intuition might suggest that the diagonals of the square are a more efficient path. (The code follows for this figure.) In[11]:= roaddiag=Graphics[ { Line[ { {0,0},{1,1} } ], Line[ { {0,1},{1,0} } ] }]; In[12]:= Show[roaddiag, houses, AspectRatio->Automatic, PlotLabel->"2 Sqrt[2] miles (approx 2.828)"] Out[12]= -Graphics- With this arrangement, notice that the path between any two given houses is equidistant to the path between any other pair of houses This is a "fair" arrangement in the sense of convenience, but is it the ideal arrangement from an economic viewpoint? At least one more configuration exists which will beat this total. Experiment with sketches that will combine the features of both the horizontal and vertical roads and the oblique roads. A particular type of path should then reduce to an optimization problem which will follow the usual routine for such problems. Prerequisites Max/min problems in differential calculus of a single variable. Time allotment - time management Expectations Future payoffs Extensions As an extension, consider: What changes would be necessary if a circular pond of radius 1/8 mile is centered in the square? How big must the radius of the pond be before it effects the optimal configuration? NOTE: The addition of the pond increases the total path length, but it does not change the given optimal configuration until the point where the radius is greater than the optimal length for the middle road. A three-dimensional version of this problem can be modeled by dipping a cubical wire frame in a soap bubble solution. The soap film's tendency to seek a state of lowest energy causes it minimize the surface area in a manner that looks surprisingly similar to the optimal road configuration shown here. References and Sources Source: Idea from a problem in Problems for Mathematicians, Young and Old, by Paul R. Halmos. Washington DC: MAA. 1991. POSSIBLE SOLUTION(S) Let's think a little first Consider a configuration which incorporates the advantages of a diagonal access to the interior while still making a straight shot down the middle. (The code follows for this figure.) In[13]:= roadsym=Graphics[ { Line[ { {0,0},{.5,.2} } ], Line[ { {0,1},{.5,.8} } ], Line[ { {1,0},{.5,.2} } ], Line[ { {1,1},{.5,.8} } ], Line[ { {.5,.2},{.5,.8} } ], }]; Show[roadsym, houses, AspectRatio->Automatic, PlotLabel->"Hybrid Model for Optimization"] Out[15]= -Graphics- This arrangement may seem counterintuitive since it takes the horizontal/vertical "I" formation and pulls it somewhere short of the diagonal formation. Thus, at first glance, it may seem that this total distance should be somewhere between 3 miles and 2Sqrt[2] miles. Approach the problem of minimizing the length of this configuration in the standard way. Label the diagram and express the quantity to be optimized as a function of one variable. (The code follows for this figure.) In[16]:= labels=Graphics[{ Text["z",{.25,.85}], Text["x",{.45,.5}], Text["y",{.45,.9}] }]; auxil=Graphics[ { Dashing[ {.01,.02} ], Line[{ {.5,.8},{.5,1} } ], Line[{ {0,1},{1,1} } ] } ]; In[19]:= Show[roadsym, houses, labels, auxil, AspectRatio->Automatic, PlotLabel->"Hybrid Model for Optimization"] Out[19]= -Graphics- Now, here's our answer. Utilizing the symmetry of the configuration, the total length of the system of roads is 4z + x. Relationships between the variables can be established by using the symmetry, the right triangle, and the side length of 1. Minimize: length = 4z + x subject to: y^2 + (.5)^2 = z^2 and 2y + x = 1 Using these constraints, the function to be minimized can be written as length below. In[20]:= x[z_] := 1 - 2 Sqrt[z^2-1/4] In[22]:= length[z_] := 4 z + x[z]; To determine the critical points, compute the derivative . . . In[24]:= length'[z] Out[24]= 2 z 4 - --------------- 1 2 Sqrt[-(-) + z ] 4 and find the values of z for which the derivative is zero (the undefined case will be considered later). cps1 = Solve[ length'[z]==0, z] Out[25]= 1 {{z -> -------}} Sqrt[3] In[26]:= inroad = z /. cps1[[1]] //N Out[26]= 0.57735 Verify that this critical point minimizes the function by use of a graph. In[27]:= Plot[length[z], {z ,1/2, 1}, PlotRange -> {{0,1},{0, 3.3}}] Out[27]= -Graphics- What does this minimal value of inroad do to the total length of the system? In[28]:= N[length[inroad]] Out[28]= 2.73205 Notice that this does beat the 2Sqrt[2] length given by the diagonals, which occurs in this configuration when z=Sqrt[2] / 2 . . . one-half of a diagonal. In[29]:= N[length[ Sqrt[2]/2 ]] Out[29]= 2.82843 Other critical points can be found by determining when the derivative is undefined. In[30]:= cps2 = Solve[ Denominator[Together[ length'[z] ]]==0, z] Out[30]= 1 1 {{z -> -(-)}, {z -> -}} 2 2 The critical value here of z = 1/2 is interesting to note because it forces this configuration into the "I" formation. Thus, the maximum length for this configuration is 3, which occurs at this critical point. In[31]:= length[1/2] Out[31]= 3 Because of the geometric constraints of the problem, we could actually specify that z must be on the closed interval [1/2, Sqrt[2] / 2 ] . These endpoints also provide locations for relative extrema. The left endpoint has already been considered since it also was a critical point. The right endpoint, which is the value for z which creates the diagonal path, actually turns out to give a local MAXIMUM!!! Notice this behavior in the graph of the length function. In[32]:= Plot[length[z],{z, .5, Sqrt[2] / 2}] Out[32]= -Graphics- Finally, we should be convinced that for this configuration the minimum length of roads necessary is 2.73205 miles. This is achieved by building a symmetric system with access roads of length z = .5773 miles connecting to a middle road of length In[33]:= N[x[inroad]] Out[33]= 0.42265 Does this establish that this configuration is the best of all possible configurations? Or have we only found the best value for this configuration? What if the middle road was "off center"? It seems reasonable that this symmetric approach will be be best, but we have not proven it. Experiment with other configurations to see if you can do any better. We offer one experiment with a nonsymmetric configuration where the mid-road divides the horizontal road in a ratio of 2 to 1. (The code follows for this part.) In[34]:= roadnon=Graphics[ { Line[ { {0,0},{2/3,.2} } ], Line[ { {0,1},{2/3,.8} } ], Line[ { {1,0},{2/3,.2} } ], Line[ { {1,1},{2/3,.8} } ], Line[ { {2/3,.2},{2/3,.8} } ], }]; labelsnon=Graphics[{ Text["z",{.25,.85}], Text["x",{.62,.5}], Text["y",{.62,.92}] }]; auxilnon=Graphics[ { Dashing[ {.01,.02} ], Line[{ {2/3,.8},{2/3,1} } ], Line[{ {0,1},{1,1} } ] } ]; In[37]:= Show[roadnon, houses, labelsnon, auxilnon, AspectRatio->Automatic, PlotLabel->"Nonsymmetric Configuration"]; Through the optimization process as used above, the minimal total road length is 2.75645 miles which is more than the symmetric case of minimal total road length of 2.73205. In[38]:= length2[z_]:=2z+2Sqrt[z^2-1/3] + 1-2Sqrt[z^2-4/9] critpt = NSolve[length2'[z]==0,z]; inleft = z/.critpt[[3]] Out[40]= 0.718578 In[41]:= length2[inleft] Out[41]= 2.75645 And again the endpoints as critical points yields nothing better. In[53]:= critptundef = Solve[Denominator[Together[ length2'[z] ]]==0,z] Out[53]= 2 2 1 {{z -> -(-)}, {z -> -}, {z -> -(-------)}, 3 3 Sqrt[3] 1 {z -> -------}} Sqrt[3] In[54]:= inleftundef = z /. critptundef[[2]] Out[54]= 2 - 3 In[55]:= length2[inleftundef] Out[55]= 3 ISSUES IN SOLUTION Using techniques from graph theory and/or optimization, one could show that the path given is the optimum. However, for the purposes of this problem, students should see if they can convince themselves by considering various configurations.