TRABAJOS DE INVESTIGACION
OPERATIVA
Vol. $.
n lm,
1. 1991. pp. 61 a
69
EL CON JUNTO EFICIENTE EN PROBLEMAS
DE LOCALIZACION CON NORMAS MIXTAS (Lp)
CARRIZOSA PRIEGO, E. J.
FERNANDEZ GARCIA, F. R.
Dp o. de Es adis ica e I.O.
Uni e sidad de Se illa
RESUMEN
En el p esen e abajo es ablecemos una nue a ap oximaci6n a la soluci6n
del p oblema de iocalizaci6n con no mas mix as a a 6s de las di ecciones de
p oyecci6n.
P obamos que el cie e oc ogonal de los pun os de demanda es una buena
ap oximaci6n pa a el conjun o de pun os e icien es cuando el p oblema es ~i
o mulado como un p oblema mul iobje i o con no mas mix as ipo I~. Demos-
amos que es a co a es alcanzable, dando condiciones pa a que ello ocu a, 1o
que es de g an impo ancia pa a el caso de que los pa ones de dis ancia es 6n
dis ibuidos ai aza .
Palab as cla e: Localizaci6n, No mas Mix as, Pun os e icien es.
Clasi icaci6n AMS : 90B99.
SUMMARY
In his pape we gi e a new app oach o he e icien se o mul iobjec i e
loca ion p oblems wi h mixed no ms h ough p ojec ion di ec ions.
We show ha he oc ogonal hull o he demand poin s is a good app oxi-
ma ion o he e icien se when he no ms belong o he amily o lp no ms.
We also show ha his bound may be eached, and gi e condi ions o ha .
This o g ea in e es i dis ance pa ons a e andomly dis ibu ed.
Key wo ds: Loca ion, Mixed No ms, E icien Poin s.
Classi ica ion AMS: 90B99.
Recibido: "Feb e o 1990.
Re isado: Oc ub e 1990.
61
TRASAJOS DE INVESTIGACION 0PERAT1VA. Vol. 6. Nlim. 1, 1991
1. INTRODUCCION
La mayo pa e de los modelos de localizaci6n de un se icio
pueden o mula se del siguien e modo:
Min~( (x),i= 1,2 .... ,m, 9(x)) s.a. xeX (1)
donde X es el conjun o de posibles localizaciones del se icio, ,(.) la
unci6n que alo a la dis ancia del clien e i al se icio, 9(') una unci6n
de cos o po la ubicaci6n del se icio en x, y q~(.) una unci6n de u ilidad
que nos da una alo aci6n global de la localizaci6n del se icio en x.
En muchos modelos los clien es se conside an pun os d~, d2, ..., dm de
R 2 y la dis ancia medida po unciones no ma i(x) =
N,~x - dl).
Cl isicamen e la unci6n 9 es la unci6n suma, 1o que conduce a
p oblemas de la
mediana, o
bien la unci6n miximo, 1o que nos lle a a
los p oblemas del
cen o,
con 1o que seg in la o ma de la unci6n 9 se
de e mina la localizaci6n 6p ima del se icio. No obs an e pa a no
impone un c i e io a p io i, se puede es udia el p oblema de modo
independien e de la unci6n O, es ableciendo el p oblema como un
p oblema mul iobje i o, ya que cada clien e i desea el se icio lo mhs
ce ca posible de d, y de e minando las soluciones e icien es de es e
p oblema se end hn odas las soluciones del p oblema o iginal bajo
cie as condiciones pa a la unci6n globalizado a.
Es o hace que el siguien e p oblema mul ic i e io sea muy impo an-
een Teo ia de Localizaci6n:
(P) <<Min>>
(Nl(x -- dl), N2(x -
d2)
.... , Nm(x - din)) x ~ X ~ R 2
Es e p oblema ha sido es udiado en la li e a u a, donde se han
es ablecido p opiedades y ca ac e izaciones de los pun os e icien es,
Wendell y Hu e (1973), Hansen y o os (1980), Du ie y Michelo
(1985). Peleg in y Fe nilndez (1988) han dado algo i mos pa a encon a
el conjun o de pun os e icien es pa a es e p oblema en el caso de se
X = R 2, y se N i = N pa a odo i, cualquie a que sea la no ma N.
En el caso de no mas di e en es en cada pun o, el p oblema se
p esen a mils complejo. Exis en en la li e a u a algunos esul ados que
de e minan un
quasin~cleo d~bil
(Whi e, 1982) pa a (P): un conjun o
K c •2 al que, pa a odo xe R 2 exis e un cie o ye K al que
N,(x - di) > Ni(y - di)
pa a odo i.
En es e sen ido, es clilsico el esul ado (Hansen y o os, 1980) que
62
CARRIZOSA PRIEGO. E. J.. y FERNANDEZ GARCIA. F. R.
EL CON JUNTO EFICIENTE EN PROBLEMAS...
es ablece que el
cie e oc ogonal
es un quasinOcleo d6bil pa a (P) si
odas las no mas en (P) son I
En el p esen e abajo p oponemos una nue a me odologia de
cons ucci6n de quasin6cleos d6biles pa a (P). Como co ola io, ob ene-
mos el ci ado esul ado sob e el cie e oc ogonal, y es ablecemos
condiciones pa a que es a co a del conjun o e icien e sea alcanzable.
2. RESULTADOS BASICOS
Sea 9 La ec a = {2 :29 R} = {(x,y): 2x
- ~y
= 0}
di ide a R 2 en dos semiplanos F~ = {(x,y): 2x
- ly >>,
0} y F~- =
{(x, y): - 0}.
Po comodidad, deno a emos po ( ) a la ec a , po n,(x) a la
p oyecci6n o ogonal de x sob e ( ), y po • al ec o ( 2,- ~). El
cambio de di ecci6n del ec o cambia ia F~ y F~-.
De inicibn 2.1
gene a una
di ecci6n de
Vx9 +, Vy9
N(x - y) >1 N(n,(x) - y)
p oyecci6n
pa a la no ma N sii
y N(y - x) >1 N(~(y) - x)).
De inicibn 2.1
Sea N una no ma en R 2, 9 R2 {0}, y xeR 2.
Po ~. N y g~. N deno amos las unciones de R § en 1~ + de inidas po
las igualdades
~. s(2) =
N( ~(x) +
2 • g~. s(2) =
N(l ~(x) --
2 •
Teo ema 1
E •2 {0} gene a una di ecci6n de p oyecci6n pa a la no ma N sii
~,.N(') es no dec ecien e V x ~ F~, y g~. N(') es no dec ecien e V y e F~-.
Demos aci6n
Sea x e F~ +, 21 y 229 ales que 0 ~< 2 ~< 22 . En onces
~,N(22) =
N(n (x) +
22 • =
N(n (x) +
(22 -- ~.l)V -L -- (--,~.l -l-)) >
63
TRABAJOS DE INVESTIGACION OPERATIVA. Vol.
6. NO a.
1. 1991
N( ~ Oz (x) + (42 -
41) • - (-21 • =
N( c*2(x) +
21 • = ~,s(20.
g~,,N(22) = N(x*2(y) - 22 'I') = N( *2(y) -- (22 - 21) "L - 21 a') i>
N( ( c*2(y) --
(22 - 41) • - 41 • =
N( c (y) -
41 I) = 9;.N(4 0 9
Teo ema 2
Sea N una no ma en ~2; sean e [~2 {0}, x e F~ +, y e F~.
a) ~, ~(.) es no dec ecien e sii ~. N(2) >/ ~,, ~(0) V 2 >i 0.
.2 .2 4 '2
b) 9 . ~ es no dec ecien e sii 9 , N( ) >I 9y. N(0) V 2 >I 0.
Demos aci6n
La implicaci6n hacia la de echa es ob ia an o en a) como en b).
Pa a el ecip oco, sean 22 > 41 > 0. De a con exidad de N y la hip6-
esis, se deduce que ~. N(21) = N(n*2(x) + 21 • = N((21/22)( ~*2(x) + 22 l) +
((42 -- 41)/42)~Z (X)) ~< (41/42)N(Tz*2(x) + 42 • + ((42 -- 4~)/42)N(Tz*2(x)) <~
N(n*2(x) + 22 • - ~,, N(22). Un azonamien o an~dogo p ueba la impli-
caci6n pa a b). 9
Como consecuencia de los eo emas an e io es, se iene
Co ola io 1
Sea N una no ma en [R 2. e R2 {0} gene a una di ecci6n de p o-
yecci6n pa a N sii N(n*2(x) + 2 • >~ N(n*2(x)) V x ~ R 2.
Co ola io 2
Sea N una no ma en [R2" ~ ~2 {0} gene a una di ecci6n de p o-
yecci6n pa a N si y s61o si
N(n*2(z)+ 2 I)>I 1 Vz~2 al que N( c*2(z))= 1.
Demos aci6n
Es inmedia a a pa i del co ola io 1 y del hecho de que N~x)=
l~N(x) V/~ ~> 0, V x e 1~ 2. 9
64
CARRIZOSA PRIEGO. E. J.. y FERNANDEZ GARCIA. F.R.
EL CONJUNTO EFICIENTE EN PROBLEMAS...
Comen a io
E1 hecho de que
N(z) >i 1 u z
al que
N(n (z))
= 1 quie e deci que
la ec a {n (z)+ ). • R} no co a al in e io de la bola unidad
BN(1) pa a la no ma N.
Sea A c I~ z un conjun o ce ado y con exo. De inimos la p oyecci6n
o ogonal sob e A como la aplicaci6n nA : l iZ~ A al que ha(x)= z e A
equi ale a que IIx - zl12 = min {llx --
wllE:w~A}.
Teo ema 3
Sea N una no ma, D = {d 1,d E ..... dn} c R E, y una di ecci6n de
p oyecci6n pa a N. Si A es la minima banda de lados pa alelos a
que con iene a D. En onces,
N(z-di) l> N(na(z)-di) VzeR 2, i= 1 ..... n
Demos aci6n
Las desigualdades son i iales si z e A. Po o a pa e, se iene que
exis en
~.1,).2, 21
~<
2 2
ales que
A = {zeR2:ze[# + 21 l, la +
22 • pa a alg in /~eR}.
Es udiemos el caso 2 > 22. Es e iden e que z- 22 • F~, y que
di - 22 • E F~- (u i = 1 ..... n); adem is, po se di ecci6n de p oyecci6n,
pa a i = 1 ..... n,
N(z - di) = N((z -
22 • - (di - 22 • >/N(n,(z
- ).2 •
- (d i -
)~2) 'l'))
= N( : (z -
22 • + 22 • -
di) = N(na(Z) --
di).
Razonando an~ilogamen e pa a el caso 2<21, se iene el esul ado.lll
En el caso de que la no ma N sea poli6d ica, podemos ca ac e iza
geom& icamen e el conjun o de di ecciones de p oyecci6n asociadas.
De inici6n 2.3
Una no ma N en ~" se dice poli6d ica si y s61o si su bola unidad
BN(1 ) = {z"
N(z)=
I} es un polied o.
65

TRABAJOS DE INVESTIGACION 0PERATIVA Vol 6. N im. I. 1991
Es e iden e que si N es poli6d ica, en onces cualquie bola es un
polied o.
De inici6n 2.4
Sea N una poli6d ica en E2, y z ~2 {0}. Se dice que < > es una
di ecci6n de iaje pa a N si y s61o si odos los pun os de BN(1)c~ < )
son pun os ex emos del polied o BN(1).
Teo ema 3. (Ca ac e izaci6n de las di ecciones de p oyecci6n en
no mas poli6d icas).
Sea N una no ma poli6d ica en ~2.
E1 ec o no-nulo gene a una di ecci6n de p oyecci6n sii cumple
alguna de las dos condiciones siguien es:
a) ( > es di ecci6n de iaje pa a N, y si N(), ) = 1, en onces N(2
+ l~V • > 1.
b) < > es o ogonal a una ca a C de Bu(1), dim(C) = 1, y adem~ s,
< ) ~ C c~ BN(I ) #
Demos aci6n
La implicaci6n hacia la de echa es una consecuencia de los co ola-
ios 1 y 2. Recip ocamen e, sea < ) una di ecci6n de p oyecci6n; si ( )
es di ecci6n de iaje, en onces, po el co ola io 2, debe sa is ace a); si no
es di ecci6n de iaje, en onces exis e una ca a C no degene ada de Bu(1)
al que < ) c~ C c~ Bu(1 ) # 4'.
Si ( ) no ue a o ogonal a C, exis i ian 2, p ~ R ales que l~ e C~Bu(1),
y N(# + 2 l) < 1, lo que, po el co ola io 2, con adice que < ) sea
una di ecci6n de p oyecci6n. Po lo an o, se cumple b). 9
3. APLICACION A NORMAS L e
De inici6n 3.1
Sea B c ~2. Se llama cie e oc ogonal de B y se deno a C.O.(B) al
meno polied o que con iene a B y cuyas ca as son pa alelas a los ejes
coo denados o o man gngulos de n/4 con ellos.
66
CARRIZOSA PRIEGO, E. J., y FERNANQEZ GARCIA, F R.
EL CONJUNTO EFICIENTE EN PROBLEMAS...
Como aplicaci6n de los eo emas an e io es, se iene que el cie e
oc ogonal del conjun o D de pun os de demanda es un quasin icleo
d6bil pa a (P) cuando ias no mas son
lp.
Teo ema 5
Las di ecciones de p oyecci6n an o pa a la no ma
11"111
como pa a
la no ma II'll| son las gene adas po los ec o es l = (1,0), 2 = (0, 1),
V 3 = (1, 1), V 4 = (1, --1).
Teo ema 6
Si
x, ye
R E son ales que Hxl[l ~< IlYlll, [Ix[[oo ~< ILYlloo, en onces
Ilxllp ~< [lYpll Vp~[1, +oo].
Demos aci6n
Sean
y [~2,
pe(1, +~).
Sea = m~ix {llxll~,: [Ixlll <~ IlYlll, IIx[Ioo ~< IlYlloo}. Veamos que, en
e ec o, o = Yl{~. Pa a ello, no emos en p ime luga que, en la solu-
ci6n 6p ima x* del p oblema an e io , la p ime a es icci6n debe cum-
pli se con igualdad: de 1o con a io, Ix*l + Ix~l < IlY[I, ~< 2. IlYlI~, po
Io que exis i ia x* (sin p~ dida de gene alidad podemos supone que es
x*) al que Ix*l < IlYll~o.
Pe o es o implica que el pun o ((1 + a)x*, x*) es ac ible pa a cie o
> 0, y con mayo alo en la unci6n obje i o que x*, 1o que con adi-
ce que x* es 6p imo po hip6 esis.
Po consiguien e,
= m/ x {Ixll p + ( lylll - Ixll)P: Ilylll - I]yll~o ~< Ixll ~< Ilyll~}.
De la con exidad de la unci6n obje i o en la egi6n ac ible se iene
que el 6p imo debe alcanza se en la on e a, es o es:
= m/~x {(llyll~ - IJylI~)P + Ilyll~ , IlyLI~ + (llyll~ - [lyll o~) p} =
IlylLg
c.q.d. 9
67
TP-,ABA, IOS DE INVESTIC~CION OPERATIVA. Vol. 8. N~n. 1. 991
Teo ema 7
Supongamos que, en el pun o de demanda dl, se u iliza la no ma
Ni =
I 'lip,,
con pie[l, +oo] Vi = 1 .... ,n. En onces,
VxeR 2 3yeC.O.({d~ .... ,d,,}) alque
N,~x-dl)>lN,~y-d~) Vi.
Demos aci6n
Pa a i= 1, ..., 4, sea A i la minima banda que con iene a D = {dl, ..., d,}
y de lados pa alelos a i, donde los ~ son los de inidos en el eo e-
ma 5.
Sea
y
=
7~A47[A37~A27~AI(X)E
C.O.(D). Po el eo ema 3,
IIx - dill x /> IlY - dill~ , IIx - d, ll~o >/ IlY - dill oo (i = 1 .... ,n)
Po el eo ema 6, pa a i = 1,..., n,
[IX -- di lpi >/
IIY
-
dillp,
y es o p ueba el eo ema. 9
Bajo cie as condiciones, el cie e oc ogonal es de pun os e icien es;
el siguien e eo ema da condiciones pa a que es o ocu a.
Teo ema 8
Supongamos que se sa is acen las condiciones siguien es:
C1) Sob e cada ace a de C.O. pa alela a alguno de los ejes
ca esianos de e e encia, exis e un pun o de demanda con no ma
II-IIx,
Y
sob e cada ace a o mando 5.ngulo de ~ /4 con los ejes, exis e un pun o
de demanda con no ma
II'II~-
C2) Sob e cada 6 ice de C.O. in e secci6n de dos ace as de C.O.
pa alelas a los ejes ca esianos de e e encia, exis e un pun o de deman-
da con no ma
I1"11~,
Y sob e cada 6 ice in e secci6n de dos ace as
o mando ~ingulo de e/4 con los ejes, exis e un pun o de demanda con
no ma I1"11~.
En onces, odos los pun os de 3(C.O. {dl, ...,din}) son e icien es.
68
CARRIZOSA
PRIEGO. E. J.. y FERNANDEZ GARCIA. F. R.
EL CONJUNTO EF/C/ENTE EN PROBLEMAS...
Demos aci6n
Sea x o e d(C.O. {d 1 .... ,dm}). Six o e {dl ..... din}, i ialmen e es e icien-
e, luego podemos supone que x o ~ {dl ..... din}. Sea C una ace a al
que x o E C y sea c la ec a o ogonal a C. Po hip6 esis se iene que
exi e un pun o de demanda di e C n {dl ..... din}, con no ma II "111 si C es
pa alela a los ejes coo denados, y
I1"11
~ si C o ma un ingulo de e/4
con 6s os. Po con enio, di emos que di pe enece al semiplano nega-
i o de c.
Adem is, es ob io que exis e un pun o de demanda d k pe enecien e
al semiplano posi i o de c, y al que
{z : N,(z -
d,)
N,(xo -
d,)} n {z: N (z
- N (xo -
-- {x0},
1o que implica que x o es e icien e. 9
REFERENCIAS
[1] DURIER, R., y MICHELOT, Ch. (1985): <<Geome ical p ope ies o
Webe -Fe ma p oblem>>, Eu opean Jou nal o Ope a ional Resea ch, 20,
332-343.
[2] HANSEN. P.; PERRER, J., y THISSE, J. F. (1980): <<Loca ion Theo y,
Dominance and Con exi y: Some u he esul s>>, Ope a ions Rese a ch,
28, 1241-1250.
[3"1 PELEGRIN, B., y FERNANDEZ, F. R. (1988): <<De e mina ion o e ici-
en poin in mul iple-objec i e loca ion p oblems>~, Na al Resea ch Logis-
ic, 35, 693-705.
I-4] PLASTRIA, F. (1984): ~Localiza ion in single acili y loca ion>>, Eu opean
Jou nal o Ope a ional Resea ch, 18, 215-219.
[5"1 THISSE, J. F.; WARD, J. E., y WENDELL, R. E. (1984): <~Some p ope -
ies o loca ion p oblems wi h block and ound no ms>>, Ope a ions
Resea ch, 32, 1309-1327.
[6"1 WARD, J. E., y WENDELL, R. E. (1980): ~A new no m o measu ing
dis ance wich yields linea loca ion p oblems>~, Ope a ions Resea ch, 28,
836-843.
[7"1 WENDELL, R. E., y HURTER, A. P. (1973): <~Loca ion Theo y, Domi-
nance and Con exi y>>, Ope a ions Resea ch, 21, 314-320.
1"8"1 WHITE, D. J. (1982): Op imali y and E iciency, Wiley, 1982.
69