Problem:
During the month of July, Pittsburgh resident Bill Fly must make 4 round-trip flights between Pittsburgh and Chicago. These are the dates of the meetings Bill must attend:
Trip 1: Leave Pitt on Monday July. 1, Leave Chicago on Friday July 5
Trip 2: Leave Pitt on Tuesday July 9, Leave Chicago on Thursday July 11
Trip 3: Leave Pitt on Monday July 15, Leave Chicago on Friday July 19
Trip 4: Leave Pitt on Wednesday July 24, Leave Chicago on Thursday July 25
Bill must purchase 4 round trip tickets. Without a discounted fare, a round trip ticket between Pittsburgh and Chicago costs $500. If Bill's stay in a city includes a weekend, he gets a 20% discount on the round-trip fare. If his stay is more than 10 days, he receives a 30% discount, and if his stay in a city is at least 21 days, he receives a 35% discount. However, at most one discount can be applied toward the purchase of any ticket. Determine how to minimize the total cost of purchasing the 4 round-trip tickets. (hint: it might be beneficial to pair one half of one round-trip ticket number with half of another round-trip ticket).
This can be developed as an assignment problem where the supply nodes are the flights leaving Pittsburgh and the demand nodes are the flights leaving Chicago. Any assignment is feasible. For example, if he could purchase a roundtrip ticket to leave Pittsburgh 8/1 and leave Chicago 8/11. He could then purchase a roundtrip ticket to leave Chicago 8/5 and leave Pittsburgh 8/24. That would get him leaving Pittsburgh on 8/1 and leaving Chicago on 8/5 by using half of each roundtrip ticket. The key is that four round-trip tickets give him eight one-way tickets that he can use any way he wants.
Chi 7/5 Chi 7/11 Chi 7/19 Chi 7/25
Pitt 7/1 $500 $400 $350 $325
Pitt 7/9 $400 $500 $400 $350
Pitt 7/15 $400 $400 $500 $400
Pitt 7/24 $350 $350 $400 $500