Assignment:
Problem- Max Flow Problem
A big hockey game is to take place, and fans from RPI, Union, Cornell, and MIT all want to attend. Four cars are available to transport the fans to the picnic. The cars can carry the following number of people:
Car 1: three people
Car 2: four people
Car 3: three people
Car 4: four people
There are four people from each school and to prevent any one school to dominate the conversation, no car can carry more than two people from any one school. The goal is to transport the maximum possible number of people to the game.
a. Draw a network that represents this problem as a maximum-flow problem.
b. Provide the linear programming formulation for the problem.
c. Use Excel or the Max Flow algorithm to solve your linear programming formulation. How many people will be transported? What are the assignments of fans to cars?