Topic 5: Discrete Models

3 dot points, in syllabus order. Each dot point has a focused answer, with exam-style questions and worked answers where available.

How do we find the cheapest route through a network and the greatest flow it can carry?

Find shortest paths through weighted networks and determine the maximum flow using the minimum cut in a capacitated network.

How to find the shortest (least-weight) path through a network by inspection, and how to find the maximum flow from source to sink using the maximum-flow minimum-cut idea.

8 min read →

How do we assign workers to tasks for the lowest total cost or time?

Solve assignment problems using the Hungarian algorithm to allocate agents to tasks for minimum total cost.

How to set up an assignment cost matrix and use the Hungarian algorithm (row and column reduction, covering zeros) to allocate agents to tasks for the lowest total cost.

8 min read →

How do we find the shortest time to complete a project of dependent tasks?

Use forward and backward scanning on an activity network to find the critical path, the minimum project time and the float of each activity.

How to draw an activity network, use forward and backward scanning to find earliest and latest times, identify the critical path and minimum project duration, and calculate float.

8 min read →