and let

/ = c. (f), = minc«, for all £. Then for all and 2, let: k(K

1, for + 0 otherwise,

1, A:eA:+(f) 0 otherwise.

Ties in the min operation defining / are broken arbitrarily. The solutions (z+,y+) and (v+,w+) are feasible for problem (SRS) and problem (DSRS), respectively. They are optimal for the respective problems if they satisfy the following primal-dual complementary slackness conditions of Unear programming:

(cu + - Vp) Va, = 0 for all k,e (8.19)

( - X Wk) z* = 0 for all (8.20)

(2a - .) w,, = 0 for all k,S. (8.21)

Now yte = 1 implies {k,S) is an admissible assignment, ie, { +

wti - vt) = 0. Also zt = 1 implies +, ie, (/ - ) = 0. This

means the first two conditions are automatically satisfied due to the methods used to determine (v+,w+) and (2+, +). If the final condition is satisfied, then the integer solution (2,y) is not only optimal for problem (SRS), but also for problem (SPLP).

In the example at hand we find = {4,5). The indicated solution to problem (SRS) is z = zt = \ and yti = yti = yti = yJi = = ytt = yii = yts = 1, with all other variables at zero level. The objective value of this solution is 1235. We indeed find that condition (8.21) is satisfied, and so we have found an optimal solution to problem (SRS) and to problem (SPLP).

A violation of condition (8.21) occurs if, say, for some £ = £, more than one * has > 0, because exactly one is equal to one. In this case a so-called dual adjustment procedure is initiated to attempt to close the gap between the integer primal and the linear programming dual objective values by reducing these violations. Specifically, reducing v, creates slack in at least two binding constraints v - wJ,. c« as all positive appear in admissible assignments only.

Example 8.5b To elaborate, let = (200, 200, 200, 400, 300). The initial pass through dual ascent terminates with (vl) = (210, 190, 150, 240, 65, 285, 195, 195), (si) = (30, 0, 70, 65, 0), and = 1530. For

= {2,5) the primal objective value is 1605. However, vl > > Cje,,

so the associated primal solution violates condition (8.21). An adjustment in the value of is required. This leads to the dual-adjustment procedure. We refer the interested reader to Erlenkotter (1978) for details of the remainder of DUALOC.

Generating Trade-off Curves

Optimal solutions are often desired for a range of the number of facilities located to examine the trade-off with cost. These solutions can be generated conveniently by obtaining optimal solutions to problem (SPLP) using DUALOC for various levels of a surcharge added uniformly to the fixed charges/. This approach may not generate solutions for aU numbers of facilities, however. To see this let problem (SPLP;m) denote problem (8.13)-(8.18), with constraint (8.16) included in equality form.

Let s,„ denote a surcharge constant that, when added to each /, causes problem (SPLP) (in which constraint (8.16) is excluded) to have an optimal solution with exactly m sites chosen for facility location. Then s„ must satisfy:

v[SPLP;m] + ms,„ v[SPLP;,n+l] + (m4-1)5,,

and:

v[SPLP;m] + ms,„ < v[SPLP;m-I] + {m-\)s„.

This means every surcharge constant 5,„ satisfying:

5„, = v[SPLP;,n]-v[SPLP;m-bl] < s,„

< v[SPLP;m-l] - v[SPLP;m] = J„

wiH,;Cause problem (SPLP) to have an optimal solution with exactly m facilities located. But it is possible that s > s,„, in which case no such s,„ exists.

Cost Structures and Capacity Restrictions

The distribution model (8.13)-(8.18) enables piecewise-Unear representations of facility cost curves. Three cases are considered.

Case 1

Figure 8.4 represents the case for which c = (rf -H Vi)Dii. The annual

throughput of a facility at site is X and the annual throughput

cost is X Dks + /*.

ANNUAL THROUGHPUT COST FOR A FACILITY AT SITE

rilope = v«

ANNUAL THROUGHPUT OF THE FACILITY Figure 8.4 Linear Approximation of Facility Cost.

Case 2

The case in Figure 8.5 can be conveniently handled by associating zl and zi, respectively, with the solid segments in Figure 8.5 representing two versions of a potential facility at site k. An automatic economic consequence is that the optimal solution will have at most one of z or zl at unit value. The throughput cost will therefore be measured along the appropriate linear segment if a faciUty is located at the site.

Case 3

Case 3 emerges when capacity restrictions are included in the modej. When total throughput at site must be between an upper limit ofV,, and a lower limit of if a faciUty is located at the site, the model (omitting constraint 8.16) is generalized to:

minimize 1 ctv

(8.22)

Figure 8.5

of-Scale.

Piecewise-Linear Approximation of Facility Cost Under Economies-

ANNUAL THROUGHPUT COST FOR A FACILITY AT SITE

•"slope = < vi!

ANNUAL THROUGHPUT OF THE FACILITY

subject to

Denote this capacitated plant location problem formulation as problem (CPLP). The lower bound on throughput can be used to preclude a facility at site from operating below an acceptable level of activity. Bounds on faciUty size can also be used to restrict throughput to a range over which the cost structure is adequately modeled by a straight line, as in Figure 8.6. When fk is used in this way, traditional accounting definitions of fixed cost no longer apply directly.

Using problem (CPLP), several alternative size ranges can be considered for a facility. For example, piecewise-linear representation of the cost function for small, medium, and large operational alternatives would require three pieces, each with an associated variable and particularized fk and Vi, parameters. Size ranges would be controlled by the Kt and V/, bounds. If the entire range is characterized by economies-of-scale, at most one of the alternative versions of the facility would be chosen for operation at a given site. There may be diseconomies-of-scale, such as portrayed in Figure 8.6 for high throughput levels. Or there may be jump

Figure 8.6 Linear Approximation of the Classic S-Shaped Facility Cost Curve.

(Reprinted bj permission of Harvard Business Review. An exhibit from "Better distribution planning with computesmodels" by A.M. GeofTrion, (July-Augusl 1976), p. 92 ©1976 by the President and Fellows of Harvard College; all rights reserved.)

TOTAL ANNUAL COSTS FOR A DISTRIBUTION CENTER

"Fixed cost"

Actual

Approximation

AGGREGATE ANNUAL CWT THROUGHPUT OF THE DISTRIBUTION CENTER

discontinuities corresponding to possible expansion projects at an existing facility ( = 1 is included in the model for the existing facility). Piece-wise-linear approximation of these cost structures requires additional constraints such as z, -H -H ... -H z„ < 1 to ensure that, at most, one of the versions of the facility could be chosen for use at a given site.

Another significant modeling issue is the extent to which demand points should be aggregated in defining the demand zones. The following section presents an a priori upper bound on the degree of suboptimality induced in problem (CPLP) by any given demand point aggregation.

Demand Point Aggregation Versus Suboptimality

Let Z,, be the index set of demand points to be aggregated. The aggregation will be assumed to be pro rata by demand, which means:

for each k, the j./s must be the same for all .PeZ,,. (8.27)

An implied qualification is that:

for each £(L, the same k£ links have been included in the model.

(8.28)

The sought after benefit of condition (8.27) is that a number of variables and constraints are eliminated from the model. The model structure remains unchanged; however, there are L-1 fewer iindices in the model, where \L\ denotes the number of elements of the set Z.,. The reduced problem size is purchased at the price of model accuracy, ie, aggregation results in a possibly suboptimal solution in the full problem. The following property places an a priori bound on that price.

Property 8.1 [Customer aggregation error bound]. Let L, be any subset of demand point indices satisfying qualification (8.28). Then:

v[CPLP] v[CPLP; (8.27)] < v[CPLP] + «,

where e, = max,

(8.29)

and v[CPLP; (8.27)] denotes the optimal value of problem (CPLP) with condition (8.27) appended. Moreover, if (y,z) is feasible for problem (CPLP) augmented by condition (8.27) and is within t of v[CPLP; (8.27)], then (y,z) is feasible for problem (CPLP) and is within e + t,of v[CPLP]. That is, if (y,z) is (-optimal for the aggregated problem, then (y.z) is (t + ej-optimal for the full problem.

The appeal of Property 8.1 is that e, is calculated from problem data. Hence, no optimization problem need be solved. Potential reduction in model accuracy can therefore be determined a priori for any proposed customer aggregation defined by Z,,.

Example 8.6 The error bound is useful even if no facility location decisions are to be made. Taking all f = 0 and all ii = 0, problem (CPLP) reduces to a classical transportation problem because all zs are defined equal to I (if a facility is operated at site k) or 0 (if no facility is operated at site k). We will use this simphfied version of the problem for exposition. The company in question has facilities in Seattle (SEA), Los Angeles (LA), and Houston (HOU), with customers in Dallas (DAL), Chicago (CHI), Atlanta (ATL), Pittsburgh (PIT), New York (NY), and Boston (BOS). An aggregation of northeastern customers is proposed. Approximate transportation costs would have been determined from regression relationships of cost versus distance. Distance estimates may be obtained from empirical distance fimctions (see Chapter 10) knowing only the locational coordinates of the customers and the facilities. More accurate cost estimates would then be obtained when solving the smaller (aggregated) problem. Table 8.5 gives the full transportation problem data using the approximate transportation costs (?a/s) measured as doUars/cwt/lOOO kilometers, where cwt is gross shipping hundredweight. Supplies and demands are in units of 1000 cwt. The optimal solution, indicated parenthetically, is to be ignored initially.

If all northeastern customers are to be aggregated, the aggregated problem becomes that portrayed in Table 8.6. The unit transportation costs to PIT/NY/BOS are weighted averages, weighted pro rata by demand.

and i>p,T/Nv

/bos

i)p,T + Z>ny + £)bos = 35 (units of 1000 cwt).

For example, Wpit/ny/bos = (10/35)(2.465) + (15/35)(2.815) + (10/ 35)(2.976) = 2.761 dollars/cwt. This method of aggregation honors the requirement of condition (8.27). As self-demonstrated in Exercise 8.13, the a priori error bound is «pit/ny/bos = $500. If this is too high relative

Table 8.5 Full Transportation Problem (Optimal Solution Indicated; Optimal Value = $116,005).