Setting dLh{X,\)ldx, = dLh{,X,\)ldSi = aLh(X,X)/8X, = 0 yields the extremal conditions:

X + S X,5„ = 0

J-t 1-1

S V, + X X,ga = 0

= 0, / = 1,...,?, g,(X) - sj - b, = 0, / = \,...,t. (5.14)

The extremal conditions (5.14) imply:

It n I I

= - I X,giX) = - X X,{sj + Z),) = - S . (5.15)

1-1 1-1 /=1

Applying conditions (5.14) and (5.15) to problem (5.13) we have the limiting case of the dual to problem (5.12) as ˆ 0 given by:

max D{U,X) = bX - a,U, U,X

subject to

XG + i f/, = 0,

(5.16)

0.

5.3 THE MULTI-FACILITY EUCLIDEAN DUAL

The approximation in problem (5.2) extended to the multi-facility Euclidean primal problem is:

n /«-1 m

WMh{X) = 2 S - al + I S W2,\\x, - xl (5.17)

1-1 j-i 1-1 1-/+1

where:

1--1 = [(x„ - a,,) + (Xa - a,,Y + and IX~XI = [(x„ - x,yf + {Xa - x.Y + 6>0.

We use the triple-bar notation to indicate that this is not a distance function (since \X, - 0). Defining = (M,y,v„j) and IJ.r = (M2,„V2,y), and following equation (5.3), the quasilinearization of terms of WMh is given by:

w, JX, - a. = max \{X, - „ - ez„,]

subject to [C/„f -h z],r = -The equality holds for:

Wuji.Xn - aj,) w„j{x,2 - uji)

Similarly:

- 1 = max [iX-X,)U2.-e22.r]

subject to [\U2,\ + zUP = W2,>. In this case the equality holds for:

2, - 1 - Xh) W2,XX,2 - Xr

2 - III v- xlll

2 , =

llli - x\l

\\x, - XI

Problem (5.17) can now be stated as:

m n

min lVMh(X) = min max S " -

m-\ m

+ S S [(-1 - X,)U2,r - eZ2,J

/ n

(5.18)

(5.19)

(5.20)

(5.21)

= min max { ,( ,, - Xc/j- + E t/jiv) X [/,Z --+1

- S 2 (.f. + « ,/;) - 2 I «2,J 1-1 y-l 1-1 -/+1

subject to

[f/„f + zy/ = w„„ z = l,...,w;> =

[f/2,f + zW" = W2i„ i = 1,...,OT-1; r = /+l,...,m.

(5.22)

From equations (5.19) and (5.21) we can write the necessary and sufficient conditions for minimizers of WMhiX) as:

- = -S., + i U.,. + iu,, = -0,i= U...,m. (5.23) Using conditions (5.23) in problem (5.22), we arrive at:

m n

min WMh(X) = max DMh{U,Z)-- Z {ajUuj+ez„j)

X U,Z -=

111- 1 m

-X E 2,r (5.24)

subject to

- 2 t2„ + 2 f2,. + E = 0, / = l,...,m,

[f/„Jp + zf,,]/ = w,,„ = \,...,m-j =

+ zy/ = W2,„ / = l,...,m-l; r = i+l,...,m.

Now z,J =s w,„ and z2„ < iv,,,, so the limit of problem (5.24) as « -. 0 (and Z is omitted thereafter) is:

ni n

max DM{U) = Z «.

subject to (5.25)

- S U,-. + X t2,. + E C.o = 0, / = l,...,w,

r=l ,=/+1 J-\

W,i,\\ Wuj, i = l,...,m;j = 1,..., ,

\ Wz/., = l,...,w-l; r = /+l,...,m. The corresponding dual form when Unear constraints are present in the primal problem is a special case of the dual model derived in the following section.

5.4 THE MULTI-FACILITY £ DUAL

From problem (4.1), the multi-facility £p distance primal problem is:

m fi

minimize WM{X) = S X wik-i " « + 1-.2 " jilV"

X (5.26)

The methods used to derive the Euclidean dual in the preceding sections are now applied to the £p problem for p > 1. (When p = I, problem (5.26) can be posed as the linear programming problem (4.5), for which duality results are well known.) Let Y = ( „ 2)- Here we use the notation lYl to denote [[ ,!" + "". In this notation Ui,Xr) becomes \\X, - Xl, The approximation in equation (5.17) extended to distances is:

1-1 c-/+

(5.27)

where:

fx, - ag,, = [\xn - a„p + \xa ajjf + V", and

;, - xji,, = [x„ - + \x.2 - x,jf + y, a>o.

Let g = p/(p - 1). Then using the construction in the Appendix, mathematical note 5.1, quasilinearization of terms of WMh is given by:

W2,iX. - Xl = max [(X, - X.W,, - ez,,]

subject to [(llf/z/J,) + "]/" = W2,>.

(5.28)

The values of Uj.r and Z2„ that make the equality hold in this case are given by:

U2,r = W2,{ignix.-x,,)(\xn-x,,\/\\X-X\l,y-\

sign(x,2-x,2)i\x,2-x,2\l\\X-Xl ,y-] (5.29a) and Z2f, = - H2,>e-7(iX, - Xl,,y-K (5.29b)

Similarly:

uiX, - ag , = max [{X, - a)Uuj - ez,J

subject to [QU.ly + z„J]/ = w„„

with values for and z,,, given by the analog of equations (5.29).

Carrying through the same development as that from problem (5.22) to problem (5.24), we have:

min WMh{X) = max DMh{U,Z) X U,Z

m n m-1 m

= max - X E (« . + z.j) - S 2 «22,

i-l y-l 1-1 1-1+ I

DUALITY

(5.30)

subject to

- 2 U,,, + Y U,., + 2 = 0,i= l,...,m,

i~l j=l

" + z„t]/. = w,„, / = l,...,mj = l,...,n,

[(Wbl) + " = 2.r, i = r = i+l,...,m.

Because the primal approximating objective WMh(X) in equation (5.27) is uniformly convergent to WM(X) in problem (5.26) as «-.0, we seek the dual problem in the limiting case as «0. Since \zuj\ and z2,J =e W2,„ the limiting form of problem (5.30) as «-0 (and Z is omitted thereafter) is:

m n

maxDMiU) = - 2 S a,Uu, -y=i

subject to (5.31)

- S + 2 U„, + 2 [/,, = 0, / = l,...,m,

r-\ r-i+l J-l

Wuji < H-iy, / = l,...,m;J = l,...,n,

2,1 < W2,n i = l,...,w-l; r = i+l,...,m.

The multi-facility dual problem (p > I) can be solved using a standard nonlinear programming algorithm upon raising both sides of the inequality constraints to the power q to produce a differentiable problem. The m optimal facility locations will be the m optimal Lagrange multiplier vectors corresponding to the equality constraints.

When linear constraints GX > b augment the primal problem (5.26), an analysis entirely analogous to that of Section 5.2 can be used to derive the augmented multi-facility P„ dual form. Let G be a / X 2w matrix and let X = (X„...,X,) be the vector of associated Lagrange multipliers. Let the

constraint be given by g;(X) = g„Xn + gaXn + g.iXi, +...+ g„2nPC2 > bi. The constrained primal problem can be solved as:

max min LMh{X,\) = WMh{X) + X,[,( - 5f - (5.32)

XO X =

Let the/ column of G be given by ,,] = 1,2,...,2m. Applying conditions analogous to equations (5.14) and (5.15) to the analog of problem (5.13)

EXERCISES

and letting e 0, we arrive at the following limiting case of the dual of problem (5.26) in the presence of linear constraints:

max DM{U,\) = - X S juj subject to

(5.33)

X(GV„G2,) - 2 U2.i + 2 U2,. + S Uu, = 0,i= l,...,m,

\\Uuji < w„„ i = l,...,mj = \,...,n, \\U2,l < W2,n = l,...,w-l; r = i+l,...,m, X > 0

5.5 SOLUTION METHODS FOR THE DUAL FORM

The multi-facility primal problem (with or without linear constraints) can be solved by solving the dual problem using a standard nonlinear programming algorithm. (For p = 1 both the primal and dual problems can be posed as linear programming problems, following the discussion in Section 4.1.) However, computational experience seems to indicate that using nonlinear programming algorithms, and one of the differentiable approximating objective functions, the primal problem may be solved faster than the dual. Yet the dual problem has a much simpler functional form in the objective function and constraints (after raising each nonlinear constraint to the g" power). The ease of setting up the dual problem for solution by a nonlinear programming algorithm may outweigh any extra computing time.

Decomposition procedures have also been developed to solve the dual problem. They require special computer programs to be written and are computationally efficient only when large numbers of constraints are present in the primal problem. Sources for the methods are given in Reference Note 5.3.

EXERCISES

5.1 Kuhn (1967,1976) Consider problem (5.1) with = 3 and w, = iVj = = 1. Figure 5E.1 depicts the geometry of the situation described by Mr. Tho. Moss in Section 1.3. The locations a„ , and a, are the locations of the three trees mentioned there. Equilateral triangles have been constructed on the sides of the triangle . ,. The point X* is the Toricelli point described in