A state park has nine points of interest, such as a ranger station, cabins, picnic areas,...

 

Transcribed Image Text:

A state park has nine points of interest, such as a ranger station, cabins, picnic areas, boat docks, and scenic overlooks. To encourage people to enjoy as much of the park as possible, the state park commission wishes to introduce a network of clean-energy shuttles to transport people between the points of interest, with the goal of minimizing the total estimated travel time in the system (so that the shuttles may make as many back-and-forth trips as possible). A map of the park indicating the estimated travel times via shuttle between the points of interest (in minutes) is given below. 3 5 6 1 5 6 4 4 4 (2) 3 5 (4) Lake 3 4 8 4 7 (5) 6 4 5 (9) Let Xij = the route between points of interest i and j is used otherwise 1≤i<j≤9. (a) For the LP for the minimal spanning tree problem, write the constraint for point of interest 3. (b) For the LP for the minimal spanning tree problem, write the constraint for point of interest 8. (c) Apply the greedy minimal spanning tree algorithm (i.e., solve by hand) to determine which routes should be used by the park's shuttles. You may highlight or otherwise indicate the selected routes on the diagram itself. Which connections are used, and what is the total time? You do not need to provide the complete LP formulation. A state park has nine points of interest, such as a ranger station, cabins, picnic areas, boat docks, and scenic overlooks. To encourage people to enjoy as much of the park as possible, the state park commission wishes to introduce a network of clean-energy shuttles to transport people between the points of interest, with the goal of minimizing the total estimated travel time in the system (so that the shuttles may make as many back-and-forth trips as possible). A map of the park indicating the estimated travel times via shuttle between the points of interest (in minutes) is given below. 3 5 6 1 5 6 4 4 4 (2) 3 5 (4) Lake 3 4 8 4 7 (5) 6 4 5 (9) Let Xij = the route between points of interest i and j is used otherwise 1≤i<j≤9. (a) For the LP for the minimal spanning tree problem, write the constraint for point of interest 3. (b) For the LP for the minimal spanning tree problem, write the constraint for point of interest 8. (c) Apply the greedy minimal spanning tree algorithm (i.e., solve by hand) to determine which routes should be used by the park's shuttles. You may highlight or otherwise indicate the selected routes on the diagram itself. Which connections are used, and what is the total time? You do not need to provide the complete LP formulation.