Consider the data in Question 2, page 472 of the text. Suppose that currently a
ID: 329171 • Letter: C
Question
Consider the data in Question 2, page 472 of the text. Suppose that currently a total of 600 calls are being sent from NY to LA via the following routing scheme: 100 calls from NY-Memphis- Dallas-LA; 500 calls from NY-Chicago, 250 from Chicago-Denver-LA and 250 from Chicago- Dallas-LA. Using this flow as a starting point, increase the total number of calls from NY-LA as much as possible via the Ford-Fulkerson algorithm and show what the optimal flows are. Verify that the final flow is optimal. 2 Telephone calls from New York to Los Angeles are transported as follows: The call is sent first to either Chicago or Memphis, then routed through either Denver or Dallas, and finally sent to Los Angeles. The number of phone lines joining each pair of cities is shown in Table 39. York to Los Angeles at any given time. York to Los Angeles at any given time. a Formulate an LP that can be used to determine the maximum number of calls that can be sent from New b Use the Ford-Fulkerson method to determine the maximum number of calls that can be sent from New TABLE 39 No. of Telephone Lines Cities N.Y-Chicago N.Y-Memphis Chicago-Denver Chicago-Dallas Memphis-Denver Memphis-Dallas Denver-L.A. DallasLA 500 400 300 250 200 150 350Explanation / Answer
Let’s use the following labelling rule:
NY(1),CH(2),ME(3),DE(4),DA(5),LA(6)
s, x12, x13, x24, x25, x34, x35, x46, x56, t
maximize x12 + x13
s.t. x12 + x13 = s
?x12 + x24 + x25 = 0
?x13 + x34 + x35 = 0
?x24 ? x34 + x46 = 0
?x25 + x35 + x56 = 0
?x46 ? x56 = ?t
s = t
s ? 0, t ? 0, 0 ? x12 ? 500, 0 ? x13 ? 400, 0 ? x24 ? 300, 0 ? x25 ? 250, 0 ? x34 ? 200, 0 ? x35 ? 150, 0 ? x46 ? 400, 0 ? x56 ? 350.