where

a, =

demand to be served at RNf, I if an engine company is located in station

0 otherwise,

1 if a truck company is located in station £

0 otherwise,

1 if RNf is covered by engine and truck companies 0 otherwise,

number of engine companies to be located, number of truck companies to be located,

{k\d,, < Si, {k\d,, < S!,

distance (time) from station to RNf, service standard for engine companies, service standard for truck companies.

a. Explain the model.

b. Let the c data in Table 8.4 correspond to du (in tenths of minutes) here. Let a = (71, 62, 56, 39, 35, 21, 20, 19), 5< = S = 15 minutes, n" = 3, and n = 2. Formulate the associated problem.

c. Explain how the model might be solved. Then use your suggested technique to solve the case developed in Exercise 8.4b. Comment on the result.

d. Criticize the model and suggest ways to overcome your criticisms.

e. Suppose the objective was changed to 2 tX, + afx where w Ss

0, and ai, ai are population and property value weights, respectively. Explain how the new model could be used.

8.5 Consider the shortest distance matrix given in Table 8.2. Assume the table entries correspond to tenths of minutes of helicopter travel time between nodes. A hospital is located at node 8.

a. Use the Kolesar-Walker heuristic to find a minimum number of nodes to use as helicopter bases so that the response time to each node from the nearest base plus the trip time to the nearest hospital is less than 12 minutes. Indicate which sites are chosen as bases.

b. Use the cutting plane procedure to solve the problem in Exercise 8.5a.

c. Provide criticisms of the "solution." Rank the criticisms in importance, and then suggest means to overcome the criticisms.

8.6 Consider the shortest distance matrix given by Table 8.2. Let the entries correspond to round-trip time (for the route k-*e-*k) in minutes. Use linear programming to find a minimum number of sites to use as polling places for an upcoming election. Each node corresponds to a community, and it is required that residents of each community travel no more than 42 minutes round-trip to the nearest polling place. Indicate which sites are chosen and discuss criticisms as in Exercise 8.5c.

8.7 Use the context of Exercise 8.6, but apply the maximal covering model given by problem (8.7)-(8.11) with m = 3, T = 30, T, = 42, $ = 1,...,12.

Let all be equal. Solve the problem. Indicate which sites are chosen and discuss criticisms as in Exercise 8.5c.

8.8 Use the reduction rules Rl, R2, and R3 of Section 8.1 to solve the covering problem with coefficients given in Table 8.3.

8.9 Cornuejols, Fisher, and Nemhauser (1977) It is economically advantageous for large organizations to maintain accounts in geographically dispersed banks so they can achieve lengthy check-clearing times. Let be the fixed cost of maintaining a bank account in city k\ 7„ the average number of days to clear a check drawn on an account in city when it is cashed in city It, and Vf the dollar volume of checks to be cashed in city 2. Add any additional necessary information. Then formulate as problem (8.13)-(8.18) the problem of locating, at most, m bank accounts to take greatest economic advantage of check-clearing times. Describe the meaning of the objective function (including the units of measurement) and the constraints.

8.10 Nauss and Markland (1981) It is economically advantageous for large organizations to locate lock-boxes so that they will clear checks for funds due as quickly as possible. Lock-boxes are post office boxes operated by banks for corporations. They function as check-collection centers. Revise the terminology used in Exercise 8.9 to formulate the appropriate lock-box location problem as problem (8.13)-(8.18). Find a place in your model for y„ the average number of days to clear a check cashed at the main corporate office that is drawn on a bank in city £ Explain the objective function and the constraints.

8.11 a. Fill in the supporting detail for the use of DUALOC in Example 8.5a.

b. Fill in the supporting detail for the use of DUALOC in Example 8.5b.

c. Use DUALOC to solve Example 8.5a upon omitting site 4.

8.12-rlenkotter (1977) Let c„ = -[J?/Z)if)-?jAJ in the objective function (8.13). Here is the demand quantity in demand zone i if supplied from a facility at site k; RjD) is the total revenue corresponding to demand D; and tie > 0 is the production and distribution cost per unit demand in demand zone H if supplied from a facility at site k. The revenue function Rl-\\s assumed to be concave, differentiable, and bounded above, with RiQ) = 0. The values for £),f are determined from the optimality conditions:

if dRM/dD < t,„ then D,, = 0; and

ifdRAOydD > r„, then dRDJ/dD = / ,.

Add a site for which = 0, P = 1,-,L, and = 0. For reference, let RD) = pID)-D, where plD) is price associated with demand D. Explain and justify the implied model.

8.13 Use Property 8.1 to show that ep,T/Nv/Bos in Example 8.6 is indeed $500. Disaggregate the optimal flows indicated in Table 8.6. Then show that the

disaggregated solution is feasible for the full problem and has the same cost as the optimal value of the aggregated problem.

8.14 Use Property 8.2 to find the a priori error bound for H = 1, using = DAL,CHI,ATL) and = PIT,NY,BOS). Solve the associated transportation problem. Disaggregate the flows and verify that the solution obtained is feasible for the full problem and has the same cost as v[L„L2 aggregation]. Verify that the suboptimality of v[L„l2 aggregation] satisfies the a priori bound.

8.15 a. Show that problem (CPLP) reduces to the classical transportation prob-

lem if the model doesnt involve facility location and all » = 0. b. Explain why the method of aggregation used in Example 8.6 will honor the requirement of condition (8.27).

8.16 Geoffrion, Graves and Lee (1978) The following exercises pertain to the distribution design problem (DD).

a. Suppose a certain demand zone is to obtain some commodities directly from the plants, and others through a DC. Explain how this provision may be accommodated without changing the form of the model.

b. Replace D,j by D,„. This allows demand in demand zone j? for commodity / to depend on the particular DC from which service is to be provided. Give the negative term that must be appended to the objective function (8.31) to ensure net revenue maximization when considering this feature of service elasticity of demand.

c. Revise the design problem to include selection among alternative plant sites and plant expansion projects.

d. Revise the design problem to include seasonal effects by letting plant capacities and customer demands be given on a monthly basis, thus requiring decisions concerning seasonal inventories.

e. As demand zones are single-sourced [by constraints (8.34)], the annual flow on each outbound link liS is known. The associated unit transportation rate is therefore determined primarily by the individual demand zones and is not significantly affected by the annual throughput at the DC. However, the larger the throughput of a DC, the lower the unit inbound transportation rates should be. Explain Row to include economies-of-scale in inbound transportation costs that depend on each alternative size range for a DC from among "small," "medium," and "large."

f. Consider an application characterized by diseconomies-of-scale in producing a given commodity at a given plant. In particular, marginal costs increase appreciably with volume over the relevant range of output. Give a detailed account of how to accommodate this feature within the model and explain your logic.

g. Show the form of constraints (8.36) to accommodate: precedence relations relating to open DCs (eg, do not open DC A unless DC is open); mandatory service constraints (eg, if DC A is open, it must serve demand zone B); and specification of a subset of DCs among which at least one is required to be opened.

h. More detailed capacity constraints than constraints (8.35) may be needed. First show how to weight the capacity consumption with a suhable weighting factor for each commodity and indicate how this affects units of measurement in the constraint. Then describe separate constraints for certain commodities.

i. Suppose the capacity limits are not absolute, but may be augmented at a cost. The penalty (perhaps related to costs of leasing additional warehouse space) per unh overflow of is P. Show how to generalize the model to accommodate this feature.

8.17 a. Read Geoffrion (1976b) and Mairs et al. (1978) for perspective on dis-

tribution design modeling.

b. Read Geoffrion and Powers (1980, 1981) for perspective on facility location in the context of management support systems.

c. Read Economides and Fok (1984), Gelb and Khumawala (1984), and Davis, Kleindorfer, Kochenberger, Reutzel, and Brown (1986) for examples of actual applications of variants of models in this chapter. .

8.18 Let S = S,2 = 400 in Example 8.7. Solve the revised problem with t = 0, letting all other data remain unaltered. Present the step-by-step results as was done in the example.

8.19 Dutton, Hinman and Millham (1974) It is required to find the optimal location of power plants in the Pacific Northwest with respect to capital-construction C/a), operating (Oa), and transmission ( ) costs of providing peak ( <?) and energy (x,,) power. The following model is used:

1 8 13 18 13

minimize X X + X * X te + X fxA

a = i p= 1

x,y,z

k= 1 p= 1

subject to

X (0.85 p)z,

X Xu < (6130p,)ZA

X

a= 1 13

X Xu ~> eg

for all i for all for all e for all i

ay =e Xu < by! for all k,B

Xii, > , Zl = or 1 for all

a. Give an account of how the Benders decomposition approach might be used here.

b. Schrage (1975) Add the slack variable Ste to ayi =s Xj, to obtain ay.s + Sie = Xai- Explain how this can be used to eliminate from the problem as well as the constraint. Reformulate the problem after eliminating as many variables and constraints as possible. What was the reduction in the size of the problem?

8.20 After reading Fitzsimmons and Allen (1983), answer the following:

a. Explain how the model can be cast in the form of the simple plant location problem (SPLP) given by problem (8.13)-(8.18), omitting constraint (8.16). Interpret the variables and parameters of problem (SPLP) in the context of the application.

b. Is the model given by problem (8.22)-(8.26) appropriate for the case where there is a minimum and maximum number of auditors that can be assigned to any site? Explain.

8.21 Columbia Express, Inc.,* is a specialty forwarder whose business consists primarily of next-day delivery of perishable or urgent freight ranging from 10 to 50 pounds per item. Long-haul transportation is by the companys fleet of jet aircraft, with local pickup and delivery made through local contractors. Most of the freight is carried under long-term contracts with manufacturers who need fast service between dispersed manufacturing sites. Thus, the pickup and delivery sites are relatively small in number compared with, for example, mail forwarders or small-package operations.

Since its establishment five years ago, Columbia has used a single-hub dispatching system, under which all packages picked up are routed to the main Columbia base at Kansas City, and are forwarded from there to their eventual destinations. The continental U.S. is divided into districts, which arc aggregated for supervisory purposes into multistate regions. Aircraft are assigned to make pickup rounds in each district, and the material picked up is then flown to Kansas City, where it is unloaded and sorted. Aircraft then return from Kansas City carrying the packages for unloading and delivery in the districts.

At first the number of districts was small, but it has expanded rapidly, along with the growth of Columbias total shipping. However, this growth has not been without problems. The company has encountered control difficulties causing shipment delays. Since package forwarding is a highly competitive business, the market restrains the prices that can be charged, and Columbia has been only marginally profitable for the last year and a half. This marginal profitability has attracted attention in the business community. Recently, National Enterprises, a large holding company, announced its intent to make a hostile tender offer for Columbia.

You are director of the management science group on the corporate staff of US Communications, a company whose main business has been in pro-

*The Columbia Express, Inc., case was authored by Stephen M. Robinson, Department of Industrial Engineering, University of Wisconsin-Madison, and is used here with his permission.

viding telecommunications service to contracting businesses nationwide You report to James Neesvig, Corporate Vice President and chief financial officer, who in turn reports to Harold Jensen, President and CEO. This morning, Neesvig stopped by your office and told you he had an urgent project for you to work on.

As you know. National Enterprises is tendering for Columbia Express. Were seriously considering fighting them with a competitive tender offer, and Harry Jensen has asked the board to be prepared for a special meeting if it looks as though we should go ahead. Columbia wants nothing to do with us, so itll have to be a hostile offer.

We clearly dont want Columbia if it continues the way its been going for the last year or so. Our interest is based on a gut feeling that we ought to be able to run it better than their current management is doing. Theyve been OK on day-to-day operations, but we dont think theyve been doing the right kind of overall planning. The key question is whether doing things dilTerenUy would get their profitability up enough to make the acquisition worthwhile.

Weve asked Morgan Stanley lo do an analysis of the acquisition, but they can only work with the figures wc have on Columbia. I think we should try a parallel analysis based on how wed operate Columbia if we had it. If we did that, we might be able to come up with a very different valuation of Columbia than would be made based on their current results. Thats where your group comes in.

I think we have to focus on the way Columbia is running their shipments. We know they use a single-hub system because thats what Federal Express does. But Columbia is really a very different operation from Federal Express, and Im not convinced that a single-hub system is the best way to go. I want you and your people to tell me what is the best way to operate, given the information we have . . . and thats pretty sketchy at the moment.

Weve had our liaison people dig out some information at the FAA that gives traffic averages for their regions, based on flights and weights reported. They also got some basic information about costs for the kind of aircraft Columbia is using. You may be able to get better information, and if you can, by - all means do. But thats all we have at the moment.

What I need to know is the best way to run the Columbia operation, and how much we could get in cost savings if we did that instead of what theyre doing. Once we have that, well work with Morgan Stanley to build a valuation based on the new operational concept, and well present that to the board along with the other valuation based on current operations. My guess is that therell be quite a difference in the two.

The overriding need now is speed. Weve got to decide what to do and, if we go ahead, organize the tender before National gets this thing wrapped up. I want you to give this top priority. Let me know daily how things are going on it. Any questions at this point?

Based on this narrative and the supporting information in Tables 8E.1 and 8E.2, and Exhibit 8E. 1 below, prepare a report for presentation to Mr. Jensen. The report should be in the following format, with each section clearly headed and beginning on a separate sheet.