Classroom Activities In Optimization

Here are a few examples of hands on activities to help students gain an intuitive idea of the problem of optimization.

Traveling Salesman
Sweaty Elevators

The Traveling Salesman Problem

Tell the students to imagine that each of, say, nine randomly chosen spots in the room has a piece of rotting food leftover from a recent class party. Suppose a pregnant fly wanted to pick one of these sites as a starting point and fly to each location in turn, laying a few hundred eggs at each site.

However, this fly is on its last wings, and wants to visit each site and, finally, return to the starting point in the shortest distance possible. Draw a sample of nine points on the board, and show how an inefficiently chosen path will be much longer than another path.
Explain that the class is going to try to help the fly out by attempting to find an efficient flight plan.

Select the nine (or however many you wish to use) locations, preferably in some random fashion, since regularly spaced locations can make the problem too easy. There should be some fairly heavy object at each location (a desk or chair will do) that a fishing line can be tied to. Using a fishing reel, demonstrate a possible path by starting at one of the locations, and traveling to all locations, looping the line around a chair leg or thumbtack at each location. When you have arrived at the starting point, have a student gather the line, and measure it by (for example) wrapping around a meter stick (since it is hard to say how much the diameter of the roll of line inside the reel changes, counting revolutions of the reel might not be the way to go here). Have the students see if they can beat this distance. They can use simple trial and error, or diagrams, or whatever.

When they have had some time to play with it, you can discuss what would happen if there were a hundred seperate locations to visit. Show them (ask them to guess first) how many flight patterns there are with nine locations (about 9!/2, which is 181,440), and then give them an idea of how many possibilites there would be with a hundred cities.

Finally, show the students a program such as RealSim Salesman that performs this type of optimization. For information on an alpha version of this program, send mail to info@shodor.org.

The Sweaty Elevator

Have the students imagine ten hot, sweating people in one elevator. Where would we expect the people to stand? What happens when a bunch of people in a small place try to stay as far from each other as possible?

Mark off a 10x15 foot section of the floor with masking tape. Select ten kids to be the people in the "elevator". Have them walk in to the tape rectangle and stand as far away from each other as possible while staying within the "elevator"'s boundaries. What do they notice about the outcome?

Explain that some things in nature "don't like" to be around each other. Use like magnet poles to demonstrate this phenomenon visually.

Many of the materials we use in our everyday life "arrange themselves" in this sort of way. The tiny pieces that make up a solid generally don't want to be too close to each other. The way they arrange themselves in response to these forces can be extremely important--one rearrangement might make the material transparent, while another would only let a little light through. One type of object in which arrangement of molecules is particularly important is a crystal.

Scientists want to know how the molecules of an object will arrange themselves in particular situations. The molecules of many materials, when the material is being cooled slowly from its liquid state, become arranged in evenly spaced positions called a lattice, or crystal lattice.

A companion website is located here, which was developed to teach people about crystal formation and how scientists study it using computers.