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 different 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 total number of games must be equal to the total number of wins, we assume thatn 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 flow 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 flow 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. 2MIT OpenCourseWarehttp://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.