The Happy Donut Company is trying to make and sell as many donuts as they can. They have the capacity to make 1000 donuts per day, of which at most 350 can be glazed, 350 can be chocolate, and 350 can be jelly-filled. They sell their donuts to three local cafes: Coffee Coffee Coffee, Antimocha, and The Half-N-Half Cafe. Coffee Coffee Coffee wants up to 350 donuts total, but they can only be glazed or chocolate, with at most 250 of either type. Antimocha can buy as many as 450 donuts, but only glazed or jelly-filled (they don't want chocolate), and at most 150 of them can be jelly-filled. The Half-N-Half Cafe can buy up to 150 chocolate donuts and up to 50 jelly-filled donuts, but does not want any glazed donuts.
Formulate the problem of choosing how many donuts to sell to each cafe as a maximum flow problem, whose solution is the number of donuts that can be sold. Your flow network should have a single source, a single sink, and additional vertices for The Happy Donut Company, each type of donut and each cafe, and draw the resulting flow network. (Hints: for the The Happy Donut Company, use the total capacity to label an incoming edge, and use the maximum number for each type of donut to label an outgoing edge. For the cafes, reverse this pattern, so the outgoing edge is the one with the total capacity. When there is no limit on one of the amounts, set its capacity to infinite.)
Explain why the integer flow property is important for this application.
Suppose you were trying to solve the Happy Donut Company's sales problems, but you hadn't learned about maximum flow, so you set up a brute force search that tries each combination of how many donuts of each type to sell to each cafe, from 0 up to the maximum for that type, and then checks whether that combination is within the limits of what the Happy Donut Company can produce and the total amounts that each cafe will buy. How many combinations would your program check?
As a start to solving the donut flow problem, find the most donuts of any single type that you can sell to any single cafe. (This should correspond to a widest path in your flow network.) Draw the residual graph that results from making this one sale.
How many donuts can The Happy Donut Company sell? Break it down by numbers of donuts of each type sold to each cafe (these should be the flow amounts on your network), and prove that no better solution is possible by finding a maximum cut with the same value.