CSU Mathematics & Science Day Page

Hello Students

Some of you may not have had time to complete all of the survey and network exercises at the CSU mathematics & science day. Here is one of the data sets collected on the day. You may wish to use this data to work through the complete set of exercises with you mathematics teacher.

The solutions to the problems are available Click Here.  Don't worry about the Maple code, simply scan down through the output to find the answers to the problems in the output.  Maple is simply a nice programming environment tat we use at CSU for solving mathematical problems.

You may also want to have a look at some of the photographs of the activities on the day - Click Here

Mathematics & Spatial Measurement

Project 1 - Remote Measurement of Distances

Project 2 – Measure the area of the car park

Note: The Global Positioning System (GPS) coordinates are in meters.

Hint: Split the area into two triangles
 
 







Mathematics & Optimal Networks

Activity 8

While working through the network solutions you may like to try the following shortest route algorithm to find the shortest route from the car park entrance (103) to the Library (88). This would be more efficient than the trial and error approach for larger networks.

Don’t forget to use PRIN’s algorithm for finding the optimal fibre optic path in activity 9.

The shortest route problem

Another common application of networks is the shortest route problem. It is concerned with finding the shortest path in a network (graph) from one node to another node.

Example 6

Finemore trucking company operates a special fast service pickup and delivery service between Wagga and 7 other towns. When Finemore receives a request for service, it dispatches a truck from Wagga to the town requesting service as soon as possible. Since both fast service and minimum travel costs are objectives of Finemore, it is important that the dispatched truck takes the shortest route from Wagga to the specified town. Assume that the following network, with distances given in hours, represents the highway network for this network.

a. Find the shortest times (route distances) from Wagga to all 7 towns.

b. What is the shortest time (route) to town 7? town 8?

We will use the following algorithmic procedure (given in Reading 3) to solve the shortest route problems.

Step 1. Assign node 1 the permanent label [0,S]: the S indicates that node 1 is the starting node, and the 0 indicates that the distance from node 1 to itself is zero.

Step 2. Compute tentative labels for the nodes that can be reached directly from node 1. The first number in each label is the direct distance from node 1 to the node in question; we refer to this portion of the label as the distance value. The second number in each label, which we refer to as the preceding node value, indicates the preceding node value is 1 since we are only considering nodes that can be directly reached from node 1.

Step 3. Identify the tentatively labelled node with the smallest distance value, and declare that node permanently labelled. If all nodes are permanently labelled, go to step 5.

Step 4. Consider all nodes that are not permanently labelled and can be reached directly from the new permanently labelled node identified in step 3. Compute tentative labels for these nodes as follows:

a. If the non permanently labelled node in question has a tentative label, compute the sum of the distance value at the new permanently labelled node and the direct distance from the new permanently labelled node to the node in question. If this sum is less than the distance value for the node in question, set the distance value for this node equal to this sum; in addition, set the preceding node value equal to the new permanently labelled node that provided the smaller distance. Go to step 3.

b. If the non permanently labelled node in question does not have a tentative label, a tentative label is created with a distance value equal to the sum of the distance value at the new permanently labelled node and the direct distance from the new permanently labelled node to the node in question. The preceding node value is set equal to the new permanently labelled node. Go to step 3.

 Step 5. The permanent labels identify the shortest distance from node 1 to each node and the preceding node on the shortest route. The shortest route to a given node can be found by starting at the given node and moving to its preceding node. Continuing this backward movement through the network will provide the shortest route from node 1 to the node in question. Node 1 permanently labelled, nodes 2, 3 and 4 temporarily labelled.

 Node 2 permanently labelled, node 5 temporarily labelled.

Node 4 permanently labelled, temporary label at node 5 revised

Node 3 permanently labelled, node 6 is temporarily labelled

Node 5 permanently labelled, temporary label at node 6 is revised, node 8 is temporarily labelled

Node 6 permanently labelled, temporary label at node 8 is revised, node 7 is temporarily labelled.

Node 8 permanently labelled, no temporary labels are revised

Node 7 permanently labelled, shortest route from node 1 to all other nodes on labels.


a. Which denotes the shortest distances from Wagga to all other towns (e.g. the shortest distance from Wagga to town 5 is 6 hours). b. The shortest time to town 7 is 11 hours and to town 8 is 10 hours.