CCSS Edition Parent Resource Core-Plus Mathematics
Mathematical Content
  Curriculum Overview
Sequence of Units
CCSS Alignment
CPMP Classrooms
Helping Your Student
  Helping with Homework
Preparing for Tests
Preparing for College
Research Base
  Design Principles
Research on Learning
Research on Communication
Evidence of Success
  Key Evaluation Findings

 


Course 2, Unit 6 - Modeling and Optimization

Overview
In the Modeling and 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 Problem 8 on page 404 for Kruskal's algorithm, and Problem 10 on page 404 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 page 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 page 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 page 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 pages 435-442 and CPMP-Tools Vertex-Edge Graph software.)

  • Earliest finish time: the total task time for all tasks on the critical path for the project. (See page 438.)

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

Copyright 2017 Core-Plus Mathematics Project. All rights reserved.