A computer service company needs to establish communications between five cities. An analysis of various media...

  

Transcribed Image Text:

A computer service company needs to establish communications between five cities. An analysis of various media has determined that the monthly cost of connecting a pair of cities i and / with a link is c as shown in the accompanying matrix. The connection allows communications in both directions. There is a cost of establishing interconnection facilities at each city that depends on the number of links incident to the city. Note that these are node costs rather than are costs. • If one link touches the city the cost is d. . The second link touching the city adds the cost d . The third link touching the city adds the cost d.. These costs are related as: d₁>d;> d. Formulate a 0-1 integer linear programming model that incorporates the following information. (i) The objective is to minimize monthly cost. (ii) Each city must be touched by at least one connection. (iii) The links selected must form a tree. (iv) No more than three links can touch a city. (v) d.-5, d. 3, d=1 Hint: A variable must be defined for each potential link between city pairs. The constraints will assure that at least one link touches each city. Variables must be included for the second and third link *) If you solve the problem after formulating it, you will receive 5 extra credits. A computer service company needs to establish communications between five cities. An analysis of various media has determined that the monthly cost of connecting a pair of cities i and / with a link is c as shown in the accompanying matrix. The connection allows communications in both directions. There is a cost of establishing interconnection facilities at each city that depends on the number of links incident to the city. Note that these are node costs rather than are costs. • If one link touches the city the cost is d. . The second link touching the city adds the cost d . The third link touching the city adds the cost d.. These costs are related as: d₁>d;> d. Formulate a 0-1 integer linear programming model that incorporates the following information. (i) The objective is to minimize monthly cost. (ii) Each city must be touched by at least one connection. (iii) The links selected must form a tree. (iv) No more than three links can touch a city. (v) d.-5, d. 3, d=1 Hint: A variable must be defined for each potential link between city pairs. The constraints will assure that at least one link touches each city. Variables must be included for the second and third link *) If you solve the problem after formulating it, you will receive 5 extra credits.

Answer rating: 100% (QA)

To formulate the 01 integer linear programming model for establishing communi... View the full answer