The Griffins, Browns, Swansons, and Quagmires are going on their annual family picnic. Four cars are available to transport the families to the picnic. The cars can carry the following number of people:
Car Maximum number of people
1 3
2 5
3 3
4 4
There are four people in each family, and no car should carry more than two people from any one family. Formulate the problem of transporting the maximum possible number of people to the picnic as a minimum cost network flow problem. You should write down the LP (can use summation notation if elsewhere specify all constants) and draw a picture. Do not solve it.
Hint: Create an extra node to balance supply and demand.