Mathematical Content CPMP Classrooms Helping Your Student Helping with Homework Preparing for Tests Preparing for College Research Base Evidence of Success

# Course 2, Unit 6 - Network Optimization

Overview
In the Network Optimization unit, students use minimum spanning trees and Hamilton circuits to help find optimum networks that span (reach) all the vertices in a vertex-edge graph. They also use critical path analysis to optimally schedule large projects. In business, industry, and government, this type of mathematical management technique is very widely used. Two slightly different versions of this management technique are the Critical Path Method (CPM) and the Program Evaluation and Review Technique (PERT).

Key Ideas from Course 2, Unit 6

• Optimization: the process of looking for the best solution, whether this is a shortest path, a minimum spanning tree, or a minimum circuit.

• Tree: A vertex-edge graph which has no circuits. (See Course 1 Unit 4 for introductory work with vertex-edge graphs.) For example:

 EXAMPLE NONEXAMPLE
• Minimum spanning tree: a subset of a vertex-edge graph which connects all vertices, without making any circuits and by minimizing total edge lengths. (Lengths might represent actual distances, cost, or time, etc.) There are algorithms for producing a minimum spanning tree. (See p. 404 Problem 8 for Kruskal's algorithm, and p. 404 Problem 10 for the nearest-neighbor algorithm.) For example:

• Traveling Salesperson Problem: a particular problem represented by a vertex-edge graph, in which the goal is to create a circuit from the start point to every vertex, without repeating any vertex, minimizing the total edge lengths. There is no algorithm for producing an optimum solution. Brute force methods are impractical if more than a few vertices are involved.

• Hamilton circuit: As with other circuits, the goal is to start at one vertex, and return to the same vertex, without repeating an edge, but with the additional condition that each vertex can only be visited once. (See p. 408.)

• Best-edge algorithm: One best-edge algorithm is to start with just vertices then add the shortest edge that will not create a circuit, and repeat this process until it is not possible to add an edge without creating a circuit. A new edge added does not have to be connected to previously-added edges. The result is a minimal spanning tree. (See p. 409.)

• Brute force method: This is another algorithm for solving optimizing problems. Basically, all solutions are found and then the best is chosen. This is not practical in many situations. (See p. 409.)

• Scheduling large projects: Critical path analysis is used to optimally schedule large projects comprised of smaller tasks, such as a building construction project. The vertices represent tasks, and the edges represent times, a note is added to the edge to indicate these times. The vertices (tasks) are arranged in a parallel format, sequentially according to the prerequisites in the context. (See pp. 435-442 and CPMP-Tools Vertex-Edge Graph software.)

• Critical path: the path through the graph that gives enough time for all tasks of the project to be completed.

• Earliest finish time: the total task time for all tasks on the critical path for the project.