El conjunto eficiente en problemas de localización con normas mixtas (L p)

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