ISE 302-12 (Fall '17)
Lesson: Maximal Flow / Shortest Path / Minimal Spanning Tree Problems
Objectives:
1. Define the following terms:
a. Source
b. Sink
c. Directed arc
d. Undirected arc
e. Flow
f. Capacity
g. Forward arc
h. Backward arc
i. Cycle
2. Give examples of maximal flow problems.
3. Formulate, solve, and interpret a maximal flow problem using LINGO.
4. Define and solve a shortest route problem
5. Define and solve a minimal spanning tree problem
Assignment:
1. Read pages 99-102, maximal flow.
2. Read pages 102-107 to see examples of a shortest route problem.
3. Study pages 107-109 to use a hand algorithm to solve for a minimal spanning tree.
Homework:
1. Solve problem 16, page 129, find the maximal flow using Excel.
2. Solve problem 17, page 129, using Excel.
3. Problem 20, page 130 using Dijkstra's algorithm.
4. Problem 21, page 130 using EXCEL.
5. Problem 23, page 130, as written (hand solution).