Week 5 - Shortest path problem, Network problems

Question 1

Network flow problems

Answer 1

1. Total supply = Total demand
2. All variables are nonnegative
3. All the constraints at the SUPPLY, DEMAND & INTERMEDIATE VERTICES are equalities since total S = total D

Question 2

Flow Integrality Theorem

Answer 2

If all demands and supplies are INTEGER numbers in a network flow problem, then all extreme points are integer vectors
(special property for a network flow problem, not always the case in other problems)

Question 3

Transportation problem (special case of a network flow problem)
What to do if total supply > total demand?

Answer 3

1. NO intermediate vertices in Transportation problems, b/c sources are directly connected to destinations
2. If total S > total D, send excess to a DUMMY NODE at Cost 0

Question 4

Transportation problem - eg. of Application of a maximisation problem (see slides for more elaboration)

Answer 4

Maximise summation(p_ij x_ij)
- each CLUSTER i corresponds to a SUPPLY VERTEX, with available supply ai
- each AD j corresponds to a DEMAND vertex, with demand bj