96 DUALITY

5.1 THE SINGLE-FACILITY EUCLIDEAN DUAL

minimize Wh(X) = 2 Wj[(x,-aj,y+(x2-aj2y + (V\ (5.2) X

which is sHghtly different from that used in problem (2.19).

There are several ways to develop a dual problem. We will use an approach based on the observation that:

wi(x-aj,Y + { 2- ,2 +

= max [(xt-aji)Uj+ix2+aj2)v-fZj]. (5.3)

[u} + vj+zjYr- = w,

To see how this equality follows, recall that the inner product of two vectors equals the product of their lengths times the cosine of the angle between them. In terms of the vectors (x, - a,,,JC2 - a,2, -«) and {Uj,Vj,Zj) this means:

[(Xt-aji)Uj + ix2-aj2)Vj-iZj]

= [(x,-aj,y + {x2-aj2y + tV[uf+vf+zJV/cos

where is the angle between the vectors. Hence the optimization on the right-hand side of equation (5.3) can be posed as:

max [(xi-aj,y + (xj-0,2) + eVWj cosd,

[uj + vj+zjyf = Wi

for which the maximum is attained when cos = \. This establishes equation (5.3) and shows that the angle between the two vectors is to be 0°; the vector (Uj,Vj,z,) is a positive multiple of ( :, - a,,,X2 - - e). The multiple is seen to be /[(Xi-a,,) + (xj-<3 ) + In particular, the values of Uj, v,, and z, that enable equation (5.3) to hold are given by:

[(X, - aj,y + (X2 - aj2y + eY"

W/X; - ,2)

V, =

z, =

[(X, - a„y + (X2 - 2 + e]"

[(X, - a,,) + (X2 - aj2y + e]

(5.4)

The transformation defined by equation (5.3) has been termed quasi-linearization. We have chosen the quasilinearization approach since it allows a relatively self-contained development of the dual problem. Since the primal problem is a minimization problem we expect that the dual will be a maximization problem.

Let / = (t/„C/2,...,<7„), where = (u„Vj), and let Z = (z„Z2,...,z„). From equation (5.3) we have:

minimize Wh{X) = min max 2 [(-i - + (Xj - ) - tz,] X X V,Z=

« n

= min max [x, Uj + X2Vj X U,Z

- (£ Uj.Uj + aj2Vj + ezj)].

subject to

{uJ + vj + zjY = wJ = l,...,n.

(5.5)

From equations (5.4) we can write the necessary and sufficient conditions for minimizers of Wh(X) as:

dWh{X)

dWh{X)

= 2 0 and

= lv, = 0.

(5.6)

(5.7)

Using conditions (5.6) and (5.7) to optimize Xout of problem (5.5), and letting Dh denote the hyperbolic dual objective function, we obtain:

minimize Wh(X) = max Dh{U,Z) X U,Z

- 2 (« ". + «y2V, + eZj)

subject to

(5.8)

1 = 0,

2 V; = 0,

iu] + V? + z]yi = w„i = 1,...,«,

which is the dual of the approximating problem (5.2). Because Wh{X) is uniformly convergent [Love and Morris (1975b)] to W{X) as « 0, the dual of problem (5.1) is the Umit of problem (5.8) as « 0. Since zj < H-j by the nonlinear equality constraints, the limiting dual problem (with

objective function denoted by D) is:

max DiU) = - S (« ". + «.2V) U,Z

subject to

(5.9)

I = 0,

I V, = 0,

(w? -I- + zj)- = WjJ = Upon omitting the Zj variables, we arrive at a standard form of the dual problem given by:

max D{U) = - X +

subject to

(5.10)

S = 0,

i V, = 0,

It is proved in the Appendix, mathematical note 5.2, that if X* a,, then (Mf+ vf )"2 = w; whereas if (Mf-b vf )/ < then = where * denotes optimality. If X* = a,, then { * * < Wj.

The dual form (5.10) is "pure" in the sense that no primal variables are present. As min W(X) has been transformed into max ) over

feasible U, a feasible solution to the dual provides a lower bound for W{X*). The inequality constraints in problem (5.10) can be equivalently posed as uj + vj =s wj to produce a differentiable problem. The dual problem can then be solved for a global optimum using a standard nonlinear programming algorithm. The optimal solution to the primal problem can be calculated from an optimal solution to the dual problem utilizing a physical interpretation of the dual variables that will be discussed. Or X* may be obtained directly as the vector of Lagrange mul-tipliersfor the two equality constraints of problem (5.10).

Let 0 denote the null vector. Then, writing = (uj + vjy, and

letting ujUj denote the scalar product ,, , + aiVj, the dual may be written conveniently in vector notation as:

max DiU) = - cijUj U

subject to

(5.11)

\\Uiw„J= \,...,n.

Property 5.1 [Solving the primal problem]. The optimal Lagrange multipliers for the equality constraints of problem (5.11) solve the primal problem (5.1).

A proof is given in the Appendix, mathematical note 5.2. There it is shown (see equation 5A.1) that for j = l,...,n, X* = aj kjU* where kj 3= 0. We conclude that each line through an with direction Uf goes through X*. This provides a simple approach to finding X*, having solved problem (5.11). If all \\UJ\\ = Wj, then four equations in four unknowns can be solved for X* using any two of the aj. Otherwise, if some < w„ we have the immediate result that X* = a,. From the same proof we have that the optimal Lagrange multiplier for the/" inequahty in problem (5.11) is given by:

2w,.

kJ2.

Examiile 5.1 The data of Example 2.2 are used to illustrate the dual structure. The associated dual problem is:

max D(U)--( , + v, -h + 4v, -b 2 - 2v, + 4 , - 5v,)

subject to

M, + W2 + + 4 = 0

V + V2 -h V3 -b V4 = 0

Mf + vf < 1

Ml + vi < 4

Mi + vi 4

ui + vl 16.

A nonlinear programming algorithm produced the following:

Mf = 0.4880, = 1.9871, ? = 0.6043, w? = -3.0794,

V* = 0.8728, vf = -0.2265, v? = 1.9065, v? = -2.529.

The optimal multipliers corresponding to the six constraints are:

xt=2.5769, ? = 3.8203, 7 ?= 1.6156,

irf = 0.3968, ir?=0.4774, 7 * = 0.2311.

Using existing facilities 1 and 2, the following vector equations can be written:

(1,1) + A:,(0.4880,0.8728) = (xt,x?) (1,4) + /t2(1.9871,-0.2265) = (x*,jc?).

Solving these equations gives xt = 2.57686, xt = 3.82026, A:, = 3.23128, and = 0.793551. Figure 5.1 illustrates the physical 1 1 1 11 of and Uf as direction vectors.

Example 5.2 The effect on an optimal dual solution of the case \\U*\\ < w, can be shown by using the data from Example 2.2 with the exception that 4-4 = 4.9. From Table 2.2 CR = 4.754 < 4-4 = 4.9. This indicates that X* = = (4,5). The nonlinear programming algorithm produced the dual solution:

u* = 0.5999, w* = 1.8967, w? = 1.1149, ? = -3.6115

V* = 0.8000, V? = 0.6343, = 1.6604, v* = -3.0948,

Figure 5.1 Interpreting the U, as Direction Vectors.

34 = (4,5)

I I-1-1-1 I

1 2 3 4 5 6

and the optimal multipliers:

x*=4.0000, xf = 5.0000, 7 *=2.5000, x? = 0.7906, 7 ?=0.9014, x* = 0.0000.

We observe that \ = 4.7561 < 4.9 = w.

5.2 THE DUAL FORM WITH LINEAR CONSTRAINTS

Whenlinear constraints augment problem (5.2), we have:

minimize Wh{X) = kix - « )" + (-2 - XjY + «]" X

subject to GX 3= 6,

(5.12)

where G is a ? X 2 matrix of real numbers whose row is (,1,,2) and Z) is a X 1 vector whose element is a real number ,. Let the linear constraint be given by gjX) = gx- + ,2X2 ,. For example, the constraint might be 4x, + > 12. This restricts the facility location to a specific half-plane. Imposition of t linear constraints restricts the location to the intersection of t half-planes and models a particular feasible region for the facility. Since location studies frequently involve some form of restrictions, linear constraints can be quite useful.

We subtract the su lus variables to convert the constraints to equalities, ie,

gkX) - sj- b, = 0, /• = \,...,t. Using the Lagrangian function, problem (5.12) can be solved as:

max min Lh(X,\) = Wh(X) + 2 4g,(X) - s}b,] \>0 X

where X = (X,,X2,...,X,). From problem (5.5) this can be written:

max min max { :, Uj + X2 Vj - (apUj + ajjVj + ez,) XO X U,Z i-

+ 2 kgkX) - sj - b,]] subject to (uj + vj + z]Y = Wj,j =