15 093 Recitation 6 Michael Frankovich and Shubham Gupta October 23 2009 1 BT Exercise 7 1 Caterer Problem Solution Construct the n w as follows For each day i create two nodes as follows node ci for clean tablecloths with supply ri node di for dirty tablecloths with demand ri Create a node s for the source of new tablecloths Each node ci can receive new tablecloths from purchasing arcs s ci with arc cost p and unlimited capacity receive fast laundered tablecloths from n days ago or longer arcs di n j ci if i n j with arc cost f and unlimited capacity receive slow laundered tablecloths from m days ago or longer arcs di m j ci if i m j with arc cost g and unlimited capacity For each node di create arcs di s with zero cost and unlimited capacity representing tablecloths which are not laundered and used again 2 BT Exercise 7 3 Tournament Problem Solution We introduce nodes T1 Tn that correspond to the di erent teams These are the supply nodes and node Ti has a supply of xi the total number of games won by team i For every unordered pair i j of teams we introduce a node Gij These are demand nodes with demand k the total number of games played between these two teams Since 1 the n total number of games must be equal to the total number of wins we assume that i 1 xi n n 1 2 There are two arcs that come into a node Gij one from Ti and one from Tj The ow from Ti to Gij represents the total number of games between teams i and j that was won by team i The above constructed n w ow problem is feasible if and only if the vector x1 xn belongs to the set of possible outcome vectors 3 BT Exercise 7 23 Marriage Problem Solution A source node s a node for each man an arc connecting the source node with each man capacity of 1 unit A sink node t a node for each woman an arc connecting each woman node with the sink node capacity of 1 unit Two nodes for each broker which are connected with each other by an arc with the capacity of bi One in these two nodes is connected with man nodes that the broker knows while the other node connects to all woman nodes that the broker knows 2 MIT OpenCourseWare http ocw mit edu 15 093J 6 255J Optimization Methods Fall 2009 For information about citing these materials or our Terms of Use visit http ocw mit edu terms 1