East Coast Trucking provides service from Boston to Miami using regional offices located in Boston, New York, Philadelphia, Baltimore, Washington, Richmond, Raleigh, Florence, Savannah, Jacksonville, Tampa, and Miami. The number of miles between each of the regional offices and the numbers associated with each city are provided in the following table.

	New York	Philadelphia	Baltimore	Washington	Richmond	Raleigh	Florence	Savannah	Jacksonville	Tampa	Miami
Boston 1	211	320	424	459	565	713	884	1,056	1,196	1,399	1,669
New York 2		109	213	248	354	502	673	845	985	1,188	1,458
Philadelphia 3			104	139	245	393	564	736	876	1,079	1,349
Baltimore 4				35	141	289	460	632	772	975	1,245
Washington 5					106	254	425	597	737	940	1,210
Richmond 6						148	319	491	631	834	1,104
Raleigh 7							171	343	483	686	956
Florence 8								172	312	515	785
Savannah 9									140	343	613
Jacksonville 10										203	473
Tampa 11											270
Miami 12

The company's expansion plans involve constructing service facilities in some of the cities where a regional office is located, such that each regional office is within 400 miles of at least one service facility. For instance, if a service facility is constructed in Richmond, it can provide service to regional offices located in New York, Philadelphia, Baltimore, Washington, Richmond, Raleigh, and Florence. Management would like to determine the minimum number of service facilities needed and where they should be located.

(a)

Formulate an integer linear program that can be used to determine the minimum number of service facilities needed and their location. (Let

x_i

be the 0-1 variable, which is 1 if a service facility is constructed in city i, and 0 otherwise.)Min

s.t.Boston

New York

Philadelphia

Baltimore

Washington

Richmond

Raleigh

Florence

Savannah

Jacksonville

Tampa

Miami

x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀, x₁₁, x₁₂ = 0, 1

(b)

Solve the linear program formulated in part (a). How many service facilities are required?

Where should they be located? (Select all that apply.)

BostonNew YorkPhiladelphiaBaltimoreWashingtonRichmondRaleighFlorenceSavannahJacksonvilleTampaMiami

(c)

Suppose that each service facility can only provide service to regional offices within 300 miles. How many service facilities are required?

Where should they be located? (Select all that apply.)

BostonNew YorkPhiladelphiaBaltimoreWashingtonRichmondRaleighFlorenceSavannahJacksonvilleTampaMiami