Modelos de localización continua

Bol. Soc. Esp. Mat. Apl. no29(2004), 89–132 Modelos de Localizaci´on Continua J. Puerto1y A. M. Rodr´ ıguez-Ch´ ıa2 1Departamento de Estad´ıstica e Investigaci´on Operativa. Universidad de Sevilla. 2Departamento de Estad´ıstica e Investigaci´on Operativa. Universidad de C´adiz. [email protected] [email protected] Resumen En este trabajo se revisan tres modelos de problemas de localizaci´on continua: (1) un problema general de localizaci´on con respecto a regiones de demanda; (2) el problema de la mediana ordenada y (3) un problema de localizaci´on multiobjetivo. Con ellos se pretende dar una amplia muestra de los problemas que aparecen en el ´ambito de la Teor´ıa de Localizaci´on continua, as´ı como estudiar propiedades que permitan caracterizar los conjuntos de soluciones. El trabajo incluye una larga lista de referencias que facilitar´an al lector adentrarse m´as profundamente en ´estos y otros modelos de la Teor´ıa de Localizaci´on. Palabras clave: Continuous location theory, ordered median function. Clasificaci´on por materias AMS: 90-B85,52B55,90C25 1 Introducci´on Un problema de localizaci´on consiste en determinar la posici´on de uno o m´as servidores que optimicen alguna medida de efectividad con respecto a un conjunto de ubicaciones conocidas “a priori”. Estas ubicaciones son usualmente denominadas centros de demanda. La Teor´ıa de Localizaci´on, como cualquier otra disciplina de la Investigaci´on Operativa, desarrolla modelos matem´aticos que reflejan con la m´axima fidelidad posible la situaci´on real que se est´a considerando, con soluciones adecuadas al problema real que se modela. Fecha de recepci´on: 19 de febreo de 2004 89 90 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa Aunque a veces resulta dif´ıcil realizar una clasificaci´on de los problemas considerados dentro de un campo de investigaci´on, los problemas de localizaci´on pueden agruparse en tres familias: (1) de localizaci´on continua; (2) de localizaci´on discreta y (3) de localizaci´on en redes. La localizaci´on continua considera problemas en los cuales las ubicaciones se consideran inmersas en un espacio continuo, t´ıpicamente en un espacio Eucl´ıdeo. La localizaci´on discreta impone que el conjunto de lugares candidatos para ubicar el servicio o servicios es finito. Finalmente, cuando los puntos de demanda est´an sobre un grafo y los servicios deben posicionarse sobre los nodos o aristas del mismo se denominan problemas de localizaci´on en redes. Por motivos de extensi´on, este trabajo se restringe a considerar algunos modelos de localizaci´on continua. Excelentes referencias que cubren todas las vertientes de la Teor´ıa de Localizaci´on son [9, 10, 16, 24, 32]. El origen de la Teor´ıa de Localizaci´on se puede atribuir a la Grecia antigua, donde se estudiaron por primera vez las propiedades de puntos singulares dependiendo de la configuraci´on de unos puntos dados. Se cree que, cuando la armada Sarracena en el 638 destruy´o la Biblioteca de Alejandr´ıa, ´esta conten´ıa al menos tres soluciones diferentes a lo que hoy se denomina problema de Fermat (1601–1665). ´ Este, al final de su c´elebre trabajo sobre m´aximos y m´ınimos, enuncia el siguiente problema, al que no encuentra soluci´on: “Dados tres puntos A,B y C en el plano, encontrar un cuarto punto P tal que la suma de las distancias a los otros tres sea m´ınima”. Este problema fue “resuelto” geom´etricamente por Torricelli (1608–1647). Su procedimiento consiste en trazar un tri´angulo equil´atero a partir de cada lado del tri´angulo que se obtiene al unir los puntos dados y trazar despu´es las circunferencias que circunscriben a cada uno de ellos. El punto donde intersecan estas tres circunferencias, llamado punto de Torricelli, es la soluci´on. En 1834, Heinen prob´o que la soluci´on propuesta por Torricelli no era correcta de forma general. En el caso de que uno de los ´angulos que forman los tres puntos iniciales sea igual o superior a 120o, el v´ertice correspondiente a este ´angulo es la soluci´on del problema. En su Doctrine and Application of Fluxions (1750), Simpson generaliz´o este problema para as´ı obtener el punto que minimiza la suma ponderada de las distancias a tres puntos dados. En 1857, Sylvester consider´o un problema equivalente de localizaci´on bajo el criterio minimax, donde se buscaba el menor c´ırculo que conten´ıa un conjunto de puntos. Una soluci´on geom´etrica, atribuida a Pierce, fue dada en 1860. A principios del siglo XX, A. Weber [46] propuso como criterio para la localizaci´on de las industrias la minimizaci´on de los costes de transporte o, equivalentemente, las distancias de viaje. Es por ello que el problema consistente en minimizar la suma de distancias se conoce hoy d´ıa como problema de Fermat- Weber. Debido a que estos autores no dispon´ıan de ordenador, sus m´etodos de resoluci´on no pod´ıan ser iterativos sino geom´etricos. Uno de los primeros Modelos de Localizaci´on Continua 91    ab c  Figura 1: Punto de Torricelli m´etodos anal´ıticos para resolver el problema de Fermat-Weber se debe a Weiszfeld y se encuentra en su art´ıculo “Sur le point lequel la somme des distances de npoints donn´es est minimum” en Tohoku Mathematics Journal. Se trata de un procedimiento iterativo para localizar un nuevo servicio que minimiza la suma ponderada de las distancias Eucl´ıdeas a los puntos de demanda. Este art´ıculo escrito en franc´es, enviado desde Praga y publicado en una revista japonesa en 1937, fue virtualmente desconocido hasta finales de los sesenta. Por esta raz´on, el m´etodo fue redescubierto por otros investigadores a finales de los cincuenta y principios de los sesenta. A finales de los a˜nos sesenta la Teor´ıa de Localizaci´on se diversific´o y comenz´o a interesar a arquitectos, economistas, ingenieros, ge´ografos, especialistas en ciencias de la empresa, investigadores operativos, analistas de sistemas, planificadores urbanos, etc´etera, convirti´endose as´ı en una cuesti´on multidisciplinar. Aunque el inter´es por este tema ha venido creciendo desde los a˜nos sesenta, ha sido en las dos ´ultimas d´ecadas cuando el n´umero de trabajos publicados en revistas cient´ıficas ha aumentado considerablemente. As´ı desde 1991 pueden encontrarse en el Mathematics Subject Classification los ep´ıgrafes 90B85 Localizaci´on continua y 90B80 Localizaci´on discreta entre los 19 t´ıtulos de la secci´on 90Bxx de Operations Research and Management Science. Para obtener una mejor comprensi´on de la estructura de los problemas de localizaci´on, a continuaci´on se describen brevemente los elementos comunes a todos ellos. 92 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa El espacio soluci´on: Es el espacio soporte donde se define el problema. La elecci´on de un espacio soluci´on apropiado es crucial, porque determina aspectos tan importantes como la precisi´on o la resolubilidad del modelo. Entre los espacios m´as usuales se encuentran: -Espacios discretos: Cuando existe un n´umero finito de candidatos a soluci´on. -Redes: Los candidatos a soluci´on se encuentran sobre un grafo, usualmente representando una red de comunicaci´on. Los nodos correspondientes representan elementos importantes, como ciudades o cruces. Los arcos representan conexiones entre nodos, como carreteras, calles, conexiones de luz, etc. -Espacio Eucl´ıdeo Rn:Se emplea cuando el problema presenta aspectos regionales que no pueden ser discretizados. Adem´as, puede ser utilizado para aproximar redes cuando el n´umero de nodos y arcos es muy grande. Los casos n= 2 y n= 3 tienen un claro significado f´ısico. Los casos en que n≥4 han sido usados para modelar y resolver problemas de estimaci´on estad´ıstica. -Esfera: Es ´util para aquellas situaciones reales que hacen aparecer distancias de grandes magnitudes. -Superposici´on de un grafo sobre un espacio continuo: ´ Este es un espacio soluci´on donde una red, que representa conexiones de alta velocidad, se superpone sobre un espacio Eucl´ıdeo o una esfera. Est´a motivado por el auge de las Nuevas Tecnolog´ıas en la sociedad actual y ha recibido gran atenci´on recientemente. Las ubicaciones existentes: En t´erminos de Teor´ıa de Localizaci´on, las ubicaciones existentes representan los usuarios que requieren ser servidos. Por ello, se les denomina puntos de demanda. Usualmente se modelan mediante un conjunto Ay una funci´on de intensidad asociada que es una medida de probabilidad sobre A. Existen dos formas diferentes de representar la demanda: por un conjunto finito de puntos o por regiones del espacio soluci´on. En el primer caso, se considera un conjunto de puntos A={a1,...,aM}y un conjunto de pesos {w1,...,wM}que representan la importancia (o intensidad) de la demanda generada en cada punto. En el modelo regional, la demanda se representa mediante una regi´on R(no necesariamente conexa) incluida en el espacio soluci´on y una medida de probabilidad con soporte en R.´ Esta representa la importancia de cada subconjunto medible de R. Modelos de Localizaci´on Continua 93 La nueva ubicaci´on: La localizaci´on de la nueva ubicaci´on es la inc´ognita o variable de decisi´on del problema general de localizaci´on. Esta variable est´a caracterizada por: a) El n´umero y la cualidad de los servicios que se ubican. Si es m´as de uno, ser´a necesario especificar las caracter´ısticas de cada uno de ellos. Cuando son id´enticos, como por ejemplo buzones de correo, el modelo que se considera es un modelo multiservicio. Por otro lado, como en el caso de servicios de salud (centros de emergencia, centros de salud, hospitales, etc.), se pueden considerar problemas de localizaci´on jerarquizados. b) La naturaleza del servicio. Se puede hacer una distinci´on entre servicios atractivos yrepulsivos. Un servicio es atractivo cuando todos los puntos de demanda valoran positivamente la proximidad al nuevo servidor. Se pueden considerar centros atractivos aqu´ellos que produzcan beneficios de tipo econ´omico, cultural, etc. a los puntos de demanda, como por ejemplo una biblioteca o un hospital. Sin embargo, desde la segunda mitad del siglo XX han ido apareciendo diferentes centros o lugares de almacenamiento de distintos tipos que pueden causar da˜nos o perjuicios a la salud, que deterioran el medio ambiente o que constituyen una amenaza a nuestro bienestar o estilo de vida. En definitiva, centros de actividad que se prefiere tener lo m´as lejos posible. As´ı ocurre con la ubicaci´on de centrales nucleares, cementerios de residuos radiactivos, f´abricas que producen contaminaci´on ambiental por gases, ruidos, radiaciones, plantas de tratamiento de desechos de los centros urbanos (basureros), etc. A este tipo de servicios se les denomina repulsivos o semi-repulsivos. La funci´on objetivo: Debido a que el estudio de la Teor´ıa de Localizaci´on que se lleva a cabo en este trabajo es de tipo cuantitativo, los problemas que se consideran tienen la siguiente formulaci´on com´un: opt x=(x1,...,xN)∈S F³d(a, (x1,...,xN))a∈A´ donde Fes una funci´on globalizadora (no necesariamente escalar), “opt” significa optimizar, es decir, minimizar o maximizar, Ses el espacio soluci´on, xes la nueva ubicaci´on (variable de decisi´on), 94 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa Aes el conjunto de ubicaciones existentes, aes una ubicaci´on existente, d(·,·) es una medida de la distancia de una ubicaci´on existente a una nueva ubicaci´on. La elecci´on de la funci´on objetivo a utilizar es a veces dif´ıcil. Evidentemente, la soluci´on final depende fuertemente de esta elecci´on (ver [4]), por lo que resulta esencial cuidar esta parte del proceso de modelado. La propuesta m´as aceptada para su selecci´on consiste en establecer unos principios de racionalidad (axiomas) que debe verificar la soluci´on y entonces intentar obtener funciones objetivo a trav´es de un proceso basado en esa axiom´atica. Diferentes funciones objetivo han dado lugar a los problemas cl´asicos considerados en Teor´ıa de Localizaci´on: 1. Problema de Fermat-Weber o modelo “minisum”. El problema consiste, como hemos indicado anteriormente, en la minimizaci´on de la distancia esperada a una nueva ubicaci´on x: inf x∈SZA d(x, a)dν(a), donde dν(a) es una medida de probabilidad sobre A. Cuando Aes finito, A={a1,...,aM}, el problema es inf x∈S M X i=1 µ(ai)d(x, ai), donde los µ(ai)>0 y PM i=1 µ(ai) = 1. El modelo “minisum” tiene sentido cuando intentamos hacer valer un criterio econ´omico, en el sentido de minimizar el coste promedio que soporta la localizaci´on de un nuevo servicio. 2. Problema del centro o modelo “minimax”. Es similar al problema anterior, pero ahora, minimizando la m´axima distancia ponderada por µ, es decir, inf x∈X³sup a∈A µ(a)d(x, a)´. El modelo minimax corresponde a aplicar un criterio de calidad del servicio proporcionado. 3. Problema “cent-dian”, [4, 17]. Dado λ∈(0,1), la funci´on objetivo es ahora la correspondiente combinaci´on convexa de las funciones objetivo suma y m´aximo. Es decir, el problema es inf x∈X½λZA d(x, a)dµ(a) + (1 −λ) sup a∈A µ(a)d(x, a)¾. Modelos de Localizaci´on Continua 95 El modelo “cent-dian” corresponde a un compromiso entre los modelos “minimax” y “minisum”. Est´a justificado por el hecho de que estos criterios son contrapuestos en la mayor´ıa de los casos. 4. Problema de la mediana ordenada. Dado un n´umero finito de ubicaciones existentes A={a1,...,aM}y dados unos pesos λ1,...,λM, ordenados en orden no decreciente, el problema consiste en minimizar la siguiente suma de distancias ordenadas: inf x∈X M X i=1 λid(i)(x). Aqu´ı, d(i)(x) = d(x, aσi) es el i-´esimo elemento en la lista ordenada de distancias, es decir, d(x, aσ1)≤...≤d(x, aσM), donde σes una permutaci´on de {1,...,M}. N´otese que este problema incluye como casos particulares todos los problemas mencionados anteriormente. Hablaremos de este problema en la secci´on 4. 5. Problema multiobjetivo. Los problemas anteriores establecen “a priori” el criterio bajo el cual se localizar´an los servicios. Sin embargo, existen situaciones reales donde ser´ıa razonable utilizar simult´aneamente varios criterios. Esto implica encontrar soluciones que sean ´optimas frente a varios criterios al mismo tiempo. Este tipo de problema se denomina problema de localizaci´on multiobjetivo. La soluci´on ideal rara vez existe, ya que los objetivos suelen ser contrapuestos, as´ı pues, el concepto de soluci´on ideal es poco operativo. Esto impone la necesidad de introducir soluciones de compromiso y de aceptar como soluci´on el concepto de elemento no dominado. Con las soluciones de compromiso se asegura que no existen soluciones mejores (en todos los criterios) que las que se han encontrado. Para una discusi´on detallada sobre la naturaleza multiobjetivo del problema de localizaci´on, v´ease [27, 36]. Volveremos sobre los problemas multiobjetivo en la secci´on 5. Las distancias: La ubicaci´on de un nuevo centro va a depender de la posici´on relativa de ´este, a trav´es de la noci´on de distancia, con respecto a los puntos de demanda. La distancia (o m´etrica) en un espacio m´etrico X, es una funci´on que asigna un valor real no negativo d(x, y) a cada par (x, y). Recu´erdese que debe verificar las propiedades siguientes: 1. d(x, y) = 0 si y s´olo si x=y. 2. d(x, y) = d(y, x) (simetr´ıa). 3. d(x, z)≤d(x, y) + d(y, z)∀x, y, z ∈X(desigualdad triangular). 96 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa Cuando el objetivo perseguido es resolver problemas de optimizaci´on, como es nuestro caso, Xes generalmente un espacio vectorial y se suelen exigir a d(·,·) algunas propiedades adicionales, como la convexidad, que tenga expresi´on anal´ıtica o que sea lineal a trozos. De forma que, para su resoluci´on, se puedan usar herramientas del An´alisis Convexo, del An´alisis Matem´atico o de la Programaci´on Lineal, respectivamente. Un calibrador γ(·) es una funci´on definida sobre un espacio vectorial Xque toma valores reales y que verifica las siguientes propiedades; 1. γ(x)≥0∀x∈X. 2. γ(x) = 0 si y s´olo si x= 0. 3. γ(λx) = λγ(x) cuando λ > 0. 4. γ(x+y)≤γ(x) + γ(y)∀x, y ∈X. Se dice que una distancia procede de un calibrador γ, cuando para todo x, y ∈Xse verifica que d(x, y) = γ(y−x). Dado un calibrador γ(·) sobre X, la bola unidad asociada es el conjunto Bγ={x∈X:γ(x)≤1}. Si Bγes sim´etrica (i.e. −Bγ=Bγ), entonces γ(·) es una norma en X. Dado un espacio vectorial X, toda funci´on d(·,·) definida sobre X×Xque toma valores reales y verifica las propiedades de una m´etrica (excepto quiz´a la simetr´ıa) y adem´as es convexa, procede de un calibrador. Entre las distancias m´as usuales destacan la distancia Eucl´ıdea, que procede de la norma Eucl´ıdea (γ(x) = pPn i=1 x2 i) y tiene la ventaja de tener como bola unidad el c´ırculo, que permanece invariante bajo rotaciones. En segundo lugar, destaca la distancia rectangular odistancia de Manhattan derivada de la norma rectangular (o norma l1)γ(x) = Pn i=1 |xi|. Se usa para modelar situaciones en redes ortogonales o movimientos de robots, que generalmente tienen sus desplazamientos restringidos a dos direcciones ortogonales. En estos casos, cada movimiento est´a generado por motores independientes que no pueden trabajar simult´aneamente y que tienen velocidades constantes e iguales. Tambi´en resulta interesante citar la distancia de Tchebycheff, que procede de la norma del m´aximo o norma l∞, es decir, γ(x) = maxi=1,...,n |xi|y cuya bola unidad en R2es la resultante de aplicar un giro de 45om´as una homotecia a la bola unidad de la distancia rectangular. Como es bien sabido, las distancias mencionadas anteriormente son casos particulares de las distancias lp, que proceden de la norma γp(x) = (Pn i=1 |xi|p)1 p. Finalmente, mencionamos expl´ıcitamente las distancias que proceden de calibradores poli´edricos y que fueron introducidas en [49]. Sea X=Rny sea γ(·) un calibrador en Rn. Se dice que γ(·) es poli´edrico si la correspondiente bola unidad Bγes un politopo convexo (envolvente convexa de un n´umero finito de puntos, ver figura 2). Como casos particulares de estos calibradores volvemos a encontrar las normas l1yl∞. Modelos de Localizaci´on Continua 97 e1 e2 e3 e4e5 δ1 δ2 δ3 δ4δ5 Figura 2: Ejemplo de bola unidad de calibrador poli´edrico. A continuaci´on y para finalizar esta introducci´on, se describe el esquema general del resto del art´ıculo. Los contenidos han sido divididos en seis secciones. En la segunda secci´on se recuerdan algunos resultados, principalmente de An´alisis Convexo, que se van a utilizar a lo largo del trabajo. En las secciones tercera, cuarta y quinta, se analizan tres modelos generales de localizaci´on continua, obteni´endose caracterizaciones de sus respectivos conjuntos de soluciones. La sexta secci´on est´a dedicada a conclusiones, finalizando el trabajo con una lista de referencias bibliogr´aficas que permitir´an al lector profundizar en los contenidos. 2 Preliminares Esta secci´on se dedica a preliminares matem´aticos. As´ı, se revisan una serie de definiciones y resultados que facilitar´an el entendimiento del resto del trabajo. Por simplicidad, los resultados analizados se han planteado en Rn, aunque en su mayor´ıa sigan siendo v´alidos con mucha mayor generalidad. Sea γun calibrador con bola unidad B⊂Rn, siendo Bun conjunto convexo y compacto que contiene al origen en su interior. La bola polar de B, denominada B0, viene dada por B0:= {p∈Rn:hp, xi ≤ 1∀x∈B}. Dado un calibrador poli´edrico γcuya bola unidad es B, se denota por Ext(B) := {e1,...,eG}al conjunto de puntos extremos de By se llaman direcciones fundamentales de B,δ1,...,δG, a las direcciones definidas por 0 y los e1,...,eG (v´ease figura 2). La bola polar asociada es entonces tambi´en un politopo, ver [45, 12]. El cono normal a Ben xviene dado por (v´ease figura 3) NB(x) := {p∈Rn:hp, y −xi ≤ 0∀y∈B}.(1) Sea f:Rn→Runa funci´on convexa. Un vector pes un subgradiente de f en xsi f(y)≥f(x) + hp, y −xi ∀y∈Rn. 104 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa 3.2 Aplicaci´on a dos problemas cl´asicos de localizaci´on En esta secci´on se particularizan las caracterizaciones obtenidas anteriormente al problema de Fermat-Weber y al problema minimax. Para ello, al igual que antes, se considera una familia de conjuntos A={A1,...,AM}donde cada Ai es compacto y convexo, un conjunto de pesos positivos W={w1,...,wM}y un conjunto de normas en Rn{γ1(·),...,γM(·)}, cada una con bola unidad Bi. 3.2.1 El problema de Fermat-Weber Este problema, tambi´en denominado problema de Weber, problema de Fermat- Steiner-Weber, problema de la mediana o problema minisum, tiene sus origen, como se mencion´o en la secci´on 1, en el trabajo de Pierre Fermat. El problema de Fermat-Weber con distancias ´ınfimas con respecto a AyW es el siguiente: inf x∈RnG(x) := M X i=1 widi(x, Ai),(PW(A)) donde di(x, Ai) = inf ai∈Ai γi(x−ai). Nuestro principal objetivo ser´a caracterizar el conjunto de soluciones MW(A) de PW(A). Los resultados siguientes son casos particulares del lema 3.1 y el teorema 3.1, tomando como Φ la norma rectangular en RMy tomando γ0 i=wiγipara todo i∈ {1,...,M}. Por ello, las demostraciones son omitidas. Lema 3.3 Para cualquier x∈Rnse tiene que q∈∂G(x)si y s´olo si existen ai∈projAi(x),pi∈NAi(ai)∩Bo i1≤i≤M, tales que 1. x∈ M \ i=1 (ai+NBo i(pi)), 2. q= M X i=1 wipi. Teorema 3.2 1. Si MW(A)6=∅, entonces existe una tripleta admisible (I, λ, p)con λi=wi ∀i∈Ital que MW(A) = CI(p) = Ti∈I(∂σAi(pi) + NBo i(pi)). 2. Si existe una tripleta admisible (I, λ, p)con λi=wi∀i∈Ital que CI(p)6=∅, entonces MW(A) = CI(p). Ejemplo 3.1 (Ver la figura 4) Consideremos tres conjuntos en R2, con γi=l1para cada i. Dichos conjuntos son A1:= co{(0,1),(−1,2),(1,2)}, A2:= co{(2,−005),(2,005),(3,005),(3,−005)}yA3:= co{(−2,−2),(−2,−1), (−3,−1),(−3,−2)}. Tomamos w1=w2=w3= 1. En este caso es f´acil comprobar que los g.e.c.s. CI(p), son los conjuntos delimitados por las l´ıneas dibujadas en la figura 4. As´ı por ejemplo para Modelos de Localizaci´on Continua 105 p= (p1, p2, p3) con p1= (0,−1), p2= (−1,0) y p3= (1,1), se tiene que: C{1}(p) = {(0,1−x) : x≥0},C{2}(p) = {(x1, x2) : x1≤2,−005≤x2≤005} yC{3}(p) = {(x1, x2) : x1≥ −2, x2≥ −1}. Adem´as, se tiene que el conjunto de soluciones viene dado por: MW(A) = C{1,2,3}³(p1, p2, p3)´=co{(0,−005),(0,005)}. Obs´ervese que efectivamente (I, λ, p) con I={1,2,3}, (w1, w2, w3) = (1,1,1) y p= (p1, p2, p3) es una tripleta admisible.  A1 A2 A3 MW(A)  Figura 4: Ilustraci´on del Ejemplo 3.1 El lector puede comprobar que los resultados que caracterizan el conjunto de soluciones del problema de Fermat-Weber en el caso puntual (ver [12]) pueden obtenerse como caso particular del anterior al considerar conjuntos unitarios. Corolario 3.1 El problema de Fermat-Weber con distancias m´ınimas siempre tiene una soluci´on en el conjunto de puntos extremos de los correspondientes g.e.c.s. 106 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa El siguiente resultado es similar al Teorema de la “Mayor´ıa”, bien conocido en el caso puntual. Para ello, se supone que γi=γpara todo i= 1,...,M y que d(x, y) = γ(x−y) (todas las distancias coinciden y son generadas por una ´unica norma). Teorema 3.3 Si γes una norma en Rn,MW(A)6=∅y existe Ai∈ A tal que wi≥Pi6=jwj, entonces existe una soluci´on en Ai. Demostraci´on: Sea x∗∈MW(A) y supongamos que x∗6∈ Ai. Si ˆx∈projAi(x∗), entonces se tiene que G(x∗) = M X i=1 wid(x∗, Ai)≤G(ˆx) = X j6=i wjd(ˆx, Aj). Ahora bien, por la desigualdad triangular, se tiene tambi´en que X j6=i wjd(ˆx, Aj)≤X j6=i wj(γ(ˆx−x∗) + d(x∗, Aj)) ≤wiγ(ˆx−x∗) + X j6=i wjd(x∗, Aj) =G(x∗). Por tanto, ˆxes tambi´en una soluci´on. ¤ El caso puntual En el caso particular en que los conjuntos Aison unitarios, es posible dar mejores caracterizaciones del conjunto soluci´on. En este apartado se revisan resultados de coincidencia de soluciones con puntos de demanda, adem´as del problema de Fermat-Weber con norma l1yl2, en este caso. Denotemos A={a1,...,aM}. Soluciones coincidentes con los puntos de demanda En primer lugar se estudian los casos donde alguna soluci´on del problema de Fermat-Weber puntual coincide con un punto de demanda. Por cuesti´on de simplicidad, pondremos ϕi(x) = wiγi(x−ai). Teorema 3.4 Se verifica que aj∈Aes una soluci´on de (PW(A)) si y s´olo si existe pi∈∂ϕi(aj)∀i∈ {1,...,M} \ {j}tal que γ0 j(−Pi6=jwipi)≤wj. Demostraci´on: Por el teorema 3.2, aj∈MW(A) si y s´olo si existen pi∈∂ϕi(aj) (1 ≤i≤ M), tales que PM i=1 wipi= 0 y TM i=1 ai+NB0(pi)6=∅. Modelos de Localizaci´on Continua 107 Puesto que pi∈∂ϕi(aj)∀i∈ {1,...,M}\{j}, se tiene que γ0 i(pi) = 1. Adem´as, para cada ajse cumple que pj∈∂ϕj(aj) = ∂γj(aj−aj) = ∂γj(0); lo que implica que γ0 j(pj)≤1. De esta forma, aj∈MW(A)⇔ ∃pi∈∂ϕi(aj) (1 ≤i≤M) tales que wjpj=−X i6=j wipi. Entonces, puesto que γ0 j(wjpj) = γ0 j(−Pi6=jwipi), se tiene que wj≥wjγ0 j(pj) = γ0 j −X i6=j wipi . Rec´ıprocamente, si se supone que wj≥γ0 j(−Pi6=jwipi), se tiene que −Pi6=jwipi∈wjB0 j. De esta forma, existe pj∈B0 jtal que wjpj=−Pi6=jwipi, con lo que el resultado queda probado. ¤ El teorema anterior permite reducir el problema cl´asico de Fermat a un simple ejercicio. Ejemplo 3.2 (Problema de Fermat en el plano; v´ease la figura 1). Sean a,by ctres puntos de demanda no alineados en el plano, donde las distancias vienen medidas con la norma Eucl´ıdea. El problema cl´asico de Fermat se formula as´ı: min x∈R2kx−ak2+kx−bk2+kx−ck2. En primer lugar, se establecen las condiciones necesarias y suficientes para que a,b´o csea soluci´on del problema anterior. Sin p´erdida de generalidad, se obtiene que ces ´optima si y s´olo si: °°°° c−a kc−ak2 +c−b kc−bk2°°°°2 ≤1, lo que ocurre si y s´olo si °°°° c−a kc−ak2 +c−b kc−bk2°°°° 2 2 ≤1. Se denota por utvel producto escalar de los vectores uyv. Desarrollando el lado izquierdo de la desigualdad anterior se obtiene que 2 + 2 µc−a kc−ak2¶tµc−b kc−bk2¶≤1, de donde se deduce que ces ´optimo si y s´olo si µc−a kc−ak2¶tµc−b kc−bk2¶≤ −1 2. 108 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa Esto quiere decir que el ´angulo de v´ertice casociado al tri´angulo Tde v´ertices a,byctiene m´as de 120o. En segundo lugar, se supone que ning´un ´angulo es de m´as de 120o, es decir, la soluci´on no est´a en ning´un v´ertice. Entonces la soluci´on se encuentra en un punto de diferenciabilidad de la funci´on objetivo. Adem´as, se sabe que la soluci´on est´a en el punto donde se anula el gradiente. Si se definen los vectores pa(x) = x−a kx−ak2 , pb(x) = x−b kx−bk2 , pc(x) = x−c kx−ck2 , se tiene que ˆxes ´optimo si y s´olo si pa(ˆx) + pb(ˆx) + pc(ˆx) = 0. Multiplicando por pa(ˆx), pb(ˆx) y pc(ˆx), se obtiene que:    pa(ˆx)tpb(ˆx) + pa(ˆx)tpc(ˆx) = −1 pb(ˆx)tpa(ˆx) + pb(ˆx)tpc(ˆx) = −1 pc(ˆx)tpa(ˆx) + pc(ˆx)tpb(ˆx) = −1 de donde pa(ˆx)tpb(ˆx) = pa(ˆx)tpc(ˆx) = pb(ˆx)tpc(ˆx) = −1 2. Puesto que pa(ˆx), pb(ˆx) y pc(ˆx) son vectores unitarios, la igualdad anterior implica que el punto ˆxforma ´angulos de 120ocon los v´ertices del tri´angulo T. En consecuencia, ˆxha de ser el punto de Torricelli del tri´angulo determinado por a,byc(v´ease la secci´on 1). El caso n-dimensional con norma k · k1 El problema de Fermat-Weber con distancia rectangular es un modelo con muchas aplicaciones (localizaci´on en zonas urbanas, localizaci´on de componentes trasladados por “robots”, etc.). Adem´as de su aplicabilidad, destaca su f´acil resoluci´on, ya que min x∈Rn M X i=1 wikx−aik1= n X k=1 min xk∈R M X i=1 wi|xk−aik|. Es decir, la resoluci´on del problema de Fermat-Weber con norma k · k1en Rn es equivalente a resolver nproblemas de Fermat-Weber en Rcon la norma habitual. Aunque el procedimiento anterior proporciona un m´etodo de resoluci´on eficiente, es posible desarrollar un m´etodo alternativo para resolver este problema que adem´as se puede extender a cualquier calibrador poli´edrico. En primer lugar, se observa que B1={x∈Rn:kxk1≤1}=co{(1,0),(0,1),(−1,0),(0,−1)}, Modelos de Localizaci´on Continua 109 y que su bola dual, B0 1, viene dada por: B0 1={(u1, u2) : −1≤u1≤1,−1≤u2≤1}. De esta forma, k · k1tiene como expresi´on alternativa kxk1= max{hu, xi:u∈ext(B0 1)} = max{x1+x2,−x1+x2,−x1−x2, x1−x2}. Por tanto, el problema original se puede reformular como min x∈R M X i=1 wikx−aik1= min x∈R M X i=1 wimax u∈ext(B0 1){hu, x −ai} y ´este a su vez puede ser formulado como un problema de Programaci´on Lineal. Para ello, se introducen unas variables auxiliares zitales que max{hu, x −ai: u∈ext(B0 1)} ≤ zi. Entonces el problema anterior es equivalente a: min M X i=1 wizi sujeto a h(1,1), x −aii ≤ zi∀i∈ {1,...,M} h(−1,1), x −aii ≤ zi∀i∈ {1,...,M} h(−1,−1), x −aii ≤ zi∀i∈ {1,...,M} h(1,−1), x −aii ≤ zi∀i∈ {1,...,M} x∈Rn, zi∈Rn. El lector puede comprobar que el problema de Fermat-Weber con cualquier otro calibrador poli´edrico tambi´en se transforma en un problema de Programaci´on Lineal (de forma general, con mayor n´umero de restricciones). El problema de Fermat-Weber con distancia Eucl´ıdea Sin duda la norma Eucl´ıdea es la que podr´ıa considerarse como norma natural en las aplicaciones del problema de Fermat-Weber. Por ello, esta secci´on est´a dedicada a analizar este problema con la norma Eucl´ıdea, k · k2. Es decir, min x∈RnF(x) := M X i=1 wikx−aik2. Para resolver este problema, se calcula el subdiferencial de dicha norma. Denotando ϕi(x) = wikx−aik2, se obtiene que ∂ϕi(x) =    wi x−ai kx−aik2 si x6=ai ai+B2si x=ai. 110 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa Ahora bien, utilizando el teorema 3.4, se obtiene que aj∈Aes soluci´on si y s´olo si para cada i6=jexiste pi∈∂ϕi(aj) tal que °°°°°°X i6=j wipi°°°°°°2 ≤wj, es decir si y s´olo si °°°°°°X i6=j wi aj−ai kaj−aik2°°°°°°2 ≤wj. Por otro lado, suponiendo que la soluci´on no est´a sobre ning´un punto de demanda, la condici´on necesaria de optimalidad (en este caso, debido a la convexidad, tambi´en suficiente) viene dada por M X i=1 wi x−ai kx−aik2 = 0 o, equivalentemente, x= M X i=1 wi ai kx−aik2 M X i=1 wi 1 kx−aik2 . una ecuaci´on de punto fijo. A partir de ella, queda sugerido el siguiente proceso iterativo x(l+1) = M X i=1 wi ai kx(l)−ak2 M X i=1 wi kx(l)−aik2 =x(l)− M X i=1 wi x(l)−ai kx(l)−ak2 M X i=1 wi kx(l)−aik2 . Esto es conocido en la literatura como el algoritmo de Weiszfeld. Del argumento precedente se deduce que es un algoritmo de descenso y se puede demostrar que converge a una soluci´on, supuesto que ´esta no es un punto de demanda. Este algoritmo se puede extender al caso de normas lpcon p∈[1,2] (ver [24]). 3.2.2 El problema min max con inf-distancias. El otro problema cl´asico de localizaci´on es la minimizaci´on de la distancia m´axima o problema de c´ırculo de menor radio (Sylvester 1857). La versi´on de este problema con inf-distancias consiste en hallar el m´ınimo c´ırculo que incluya las regiones de demanda y su formulaci´on es: Modelos de Localizaci´on Continua 111 min x∈RnH(x) := max 1≤i≤Mwidi(x, Ai),(9) donde di(x, Ai) = inf a∈Ai γi(x−a) para cada i. Denotamos Ml∞ W(A) el conjunto de soluciones de (9) y definimos para cada I⊆ {1,...,M}y cada α≥0 el siguiente conjunto: ASI(α) = {x∈Rn:widi(x, Ai) = α∀i∈I, widi(x, Ai)< α ∀i6∈ I}. El siguiente teorema proporciona una caracterizaci´on de Ml∞ W(A). Teorema 3.5 1. Si Ml∞ W(A)6=∅, entonces existen una tripleta admisible (I, λ, p)y un n´umero α≥0tales que Ml∞ W(A) = CI(p)∩ASI(α). 2. Para cualquier tripleta admisible (I, λ, p)y cualquier α≥0tales que CI(p)∩ASI(α)6=∅, se verifica Ml∞ W(A) = CI(p)∩ASI(α). Demostraci´on: La demostraci´on consiste en aplicar el teorema 3.1 con Φ = k · k∞en RMy γ0 i=wiγipara todo i. Puesto que Φ = k · k∞, esto implica Φo=k · k1. De este modo, γo(λ) = 1 si y s´olo si existe I⊆ {1,...,M}tal que Pi∈Iλi= 1. Por tanto, decir que α=H(x) = max1≤i≤Mwidi(x, Ai) = Pi∈Iλiwidi(x, Ai) con Pi∈Iλi= 1 es equivalente a decir que widi(x, Ai) = αpara cualquier i∈Iywidi(x, Ai)< α para cualquier i6∈ I. En otras palabras, x∈DI(λ) si y s´olo si x∈ASI(α) para α=H(x) y la demostraci´on queda concluida. ¤ Nota 3.1 El valor de αque define el conjunto soluci´on ASI(α) en el teorema anterior, es el valor ´optimo del problema (9). ¤ Ejemplo 3.3 (Ver la figura 5) Consideremos un problema en R2con: 1. Φ(x1, x2, x3) = max{|x1|,|x2|,|x3|}. 2. Conjuntos de demanda A={A1:= co{(5,1),(5,−1),(3,−1),(3,1)}, A2:= co{(1,−3),(0,−5),(−1,−3)}, A3:= co{(−3,3),(−3,5),(−5,4)}}. 3. Conjunto de pesos W={1,1,1}yγi=l∞para i= 1,2,3. 112 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa Por tanto, la formulaci´on como problema min max viene dada por: min x∈R2H(x) := max i=1,2,3di(x, Ai). Tomando I={2,3},p2= (0,1), p3= (0,−1)}, se sigue que: CI(p) = {x∈R2:x2≥ −3, x1+x2≤0, x1+x2≥ −4, x1−x2≥ −6, x1−x2≤4}. Para α= 3, se tiene que ASI(3) = {(0,0)}, que coincide con DI((0,005,005)) (obs´ervese que para λ= (0,005,005) se tiene que Φo(λ) = 1). De hecho, este conjunto se define como DI((0,005,005)) = {x: max 1≤i≤3di(x, Ai) = 1 2h(0,1), x −a2i+1 2h(0,−1), x −a3i} ={(0,0)}, donde a2= (0,−3) y a3= (−3,3). Por tanto, el conjunto de soluciones es Ml∞ W(A) = CI(p)∩ASI(α) = {(0,0)}. A3 A1 A2  Ml∞ W(A) Figura 5: Ilustraci´on del ejemplo 3.3 Modelos de Localizaci´on Continua 113 4 El problema de mediana ordenada Esta secci´on est´a dedicada al estudio de otro problema gen´erico dentro de la Teor´ıa de Localizaci´on. El modelo corresponde a una formulaci´on relativamente reciente de una familia de problemas [31, 35] cuya principal caracter´ıstica es permitir, en cierto modo, un tratamiento algebraico unificado. Por simplicidad en la exposici´on, se considera el modelo puntual en espacios de dimensi´on finita. El lector interesado puede consultar [35, 37] para un tratamiento m´as general. Sean A={a1,...,aM}un conjunto de puntos de demanda y W= {w1,...,wM}y Λ = {λ1,...,λM}dos conjuntos de escalares no negativos tales que el elemento wide Wrepresenta la importancia del punto de demanda aiy los elementos de Λ dise˜nan la funci´on objetivo. Para facilitar la comprensi´on de este modelo, se usar´a un s´olo calibrador para medir las distancias, pudi´endose extender todos los resultados obtenidos al caso de calibradores diferentes. Dada una permutaci´on σdel conjunto {1,...,M}verificando wσ1γ(x−aσ1)≤wσ2γ(x−aσ2)≤...≤wσMγ(x−aσM), se denota por d(i)(x) = wσiγ(x−aσi), el elemento i-´esimo de la lista ordenada de distancias ponderadas. Como indicamos en la secci´on 1, la formulaci´on del problema de mediana ordenada es la siguiente: min x∈RnF(x) = M X i=1 λid(i)(x),(10) donde λ1≤...≤λM. Obs´ervese que esta funci´on objetivo, dependiendo del punto evaluado, puede tener diferentes expresiones como suma ponderada de las distancias. En otras palabras, dado que σdepende de x, su forma funcional est´a definida puntualmente (hay en cierto modo dependencia “no local”). Esto significa que la manipulaci´on de Fva a tener una dificultad a˜nadida que se ve compensada por su flexibilidad, esto es, por la gran cantidad de modelos que se pueden considerar como casos particulares. Este hecho queda reflejado en la observaci´on siguiente. Nota 4.1 i) El problema de Fermat-Weber es un problema de mediana ordenada donde λ1=...=λM= 1. ii) El problema cent-dian es un problema de mediana ordenada donde λ1= ...=λM−1=λyλM= 1 −λ. iii) El problema minimax es un problema de mediana ordenada donde λ1= ...=λM−1= 0 y λM= 1. 120 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa Demostraci´on: Si x∗∈Oσse tiene que wihbo gi, x −aii=zi,para alg´un gi= 1,...,G y para todo i= 1,2,...,M lo que significa que zi=wiγ(x−ai) para todo i= 1,2,...,M, de donde se obtiene el resultado. Si x∗∈Oσ0(Oσ06=Oσ), se tiene que wihbo gi, x −aii< zipara todo gi= 1,...,G y para al menos un i. Esto significa que la funci´on objetivo del problema (Pσ) en x∗es menor que el valor objetivo de (Pσ0) en x∗.¤ A continuaci´on, usando los lemas previos y el hecho de que la funci´on objetivo es globalmente convexa, se desarrollar´a un algoritmo que resuelve el problema de la mediana ordenada. Para cada regi´on ordenada, Oσ, se resolver´a el problema de programaci´on lineal (Pσ), pudiendo darse dos casos: (1) la soluci´on est´a en el interior de la regi´on considerada (en Rn), lo que por convexidad implica que esta soluci´on es el ´optimo global; (2) la soluci´on est´a sobre la frontera o en otra regi´on ordenada; entonces se tiene que hacer una nueva b´usqueda local en alguna regi´on vecina a la que pertenece este punto. ALGORITMO 4.1 PASO 1: ELEGIR una regi´on ordenada Oσ. PASO 2: RESOLVER el problema (Pσ)y elegir una soluci´on y∗. PASO 3: - SI y∗6∈ Oσ,ENTONCES σ:= σ0donde y∗∈Oσ0e IR AL PASO 2. - SI y∗∈int(Oσ), ENTONCES x∗:= y∗e IR AL PASO 4. - SI y∗pertenece a la frontera de Oσ, ELEGIR una regi´on adyacente no visitada Oσ0tal que y∗∈Oσ0e ir al PASO 2 con σ:= σ0. SI todas las regiones adyacentes han sido visitadas, ENTONCES x∗:= y∗e IR AL PASO 4. PASO 4: SALIDA x∗. El algoritmo anterior es eficiente en el sentido de que est´a polinomialmente acotado. Una vez que se ha fijado la dimensi´on del problema, su complejidad est´a dominada por la complejidad de resolver un problema lineal en cada regi´on ordenada. El n´umero de regiones ordenadas est´a polinomialmente acotado y la resoluci´on de un problema de programaci´on lineal se puede hacer en tiempo polinomial mediante algoritmos de punto interior, ver [42]. Por tanto, el Algoritmo 4.1 es polinomial. Otros algoritmos m´as eficientes que hacen uso de t´ecnicas propias de Geometr´ıa Computacional pueden hallarse en [23]. Modelos de Localizaci´on Continua 121 Ejemplo 4.3 Para A={(3,0),(0,11),(16,8)},wi= 1, i = 1,...,M,λ1= 1, λ2= 2 y λ3= 3, el problema ordenado tiene la siguiente fomulaci´on: min x∈R2³d(1)(x) + 2d(2)(x) + 3d(3)(x)´, donde γB(·) es la norma hexagonal definida en el Ejemplo 4.1. La figura 10 muestra los convexos elementales ordenados para este problema. N´otese que las l´ıneas gruesas representan las mediatrices entre los puntos de A, mientras las l´ıneas delgadas son las direcciones fundamentales de la norma sobre cada punto de demanda. Se resuelve el problema usando el Algoritmo 4.1. Comenzando con el punto x0= (0,11) se obtiene la soluci´on en dos iteraciones. En la primera, se obtiene el punto x1= (605,8) con valor objetivo 26025. En la segunda iteraci´on, se obtiene x2= (7,8) con valor objetivo 26. Este punto no puede ser mejorado en su entorno, con lo cual es la soluci´on del problema. Las iteraciones del algoritmo para este ejemplo se muestran en la figura 11.    Figura 10: Convexos elementales generalizados 4.2 Caso no poli´edrico En los apartados anteriores se ha desarrollado una metodolog´ıa para resolver el problema de la mediana ordenada en el caso de calibradores poli´edricos. En esta secci´on, se resuelve el problema con un calibrador general, no necesariamente poli´edrico. Para ello se prueba que las soluciones de estos problemas pueden 122 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa    x0 x1 x∗ Figura 11: Soluci´on ´optima ser arbitrariamente aproximadas por una sucesi´on de soluciones de problemas con calibradores poli´edricos cuyas bolas unidad convergen, en la m´etrica de Haussdorf, ver [39], a la bola unidad del problema no poli´edrico. Sea Bla bola unidad del calibrador γB(·), {Bm}una sucesi´on creciente de pol´ıgonos convexos incluidos en By{Bm}una sucesi´on decreciente de pol´ıgonos convexos que incluyen a B: Bm⊂Bm+1 ⊂B⊂Bm+1 ⊂Bm. Sean γBm(·) y γBm(·) los calibradores cuyas bolas unidad son BmyBm, respectivamente. Proposici´on 4.3 Si Bm⊂B⊂Bmse tiene que γBm(x−y)≥γB(x−y)≥γBm(x−y)∀x, y ∈Rn. La demostraci´on se sigue directamente de la definici´on de calibrador. Proposici´on 4.4 Sea Kun conjunto compacto. Si Bmconverge a ByBm converge a Ben el sentido de la m´etrica de Haussdorf, entonces para todo ε > 0existe n0tal que, para todo m≥n0, max x∈K|Fm(x)−FB(x)|< ε, max x∈K|Fm(x)−FB(x)|< ε, siendo Fm(x) := PM i=1 λidBm (i)(x),Fm(x) := PM i=1 λidBm (i)(x)yFB(x) := PM i=1 λid(i)(x). Demostraci´on: Modelos de Localizaci´on Continua 123 S´olo se probar´a la primera desigualdad. La segunda se demuestra de forma an´aloga. Puesto que Bmconverge a B,Bm⊂Bm+1 para todo myKes un conjunto compacto, dados ε > 0 y a∈A, existe natal que, si m > nA:= maxa∈Ana, se verifica que ¯¯¯γB(x−a)−γBm(x−a)¯¯¯<ε PM i=1 wiPM i=1 λi ∀x∈K. Por continuidad se tiene que, cualesquiera iyj, y cualquier x∈K verificando que wiγB(x−ai)< wjγB(x−aj), existe no> nAtal que wiγBm(x−ai)< wjγBm(x−aj)m > no y tal que, para cualesquiera i, j yx∈Kcon wiγB(x−ai) = wjγB(x−aj), se tiene γB(x−A)(i)=wσm iγB(x−aσm i), donde wσm iγBm(x−aσm i) = dBm (i)(x) para cada m > n0. De aqu´ı se deduce que, para cualquier x∈Ky cualquier m > n0, |Fm(x)−F(x)|= M X i=1 λi|d(i)(x)−dBm (i)(x)| = M X i=1 λiwσm i|γB(x−aσm i)−γBm(x−aσm i)|< ε. ¤ Corolario 4.1 i) Si Bmconverge a Ben el sentido de la m´etrica de Haussdorf, entonces Fmconverge a FBuniformemente sobre compactos. Adem´as, la sucesi´on {Fm(x)}es decreciente. ii) Si Bmconverge a Ben el sentido de la m´etrica de Haussdorf, entonces Fmconverge a FBuniformemente sobre compactos. Adem´as, la sucesi´on {Fm(x)}es creciente. Este resultado ser´a utilizado para demostrar el siguiente teorema. Teorema 4.2 i) Sea {xm}una sucesi´on tal que xm∈arg min Fmpara cada m≥1. Entonces cualquier punto de acumulaci´on de {xm}pertenece a arg min FB. ii) Sea {xm}n∈Nuna sucesi´on tal que xm∈arg min Fm(x), para cada m≥1. Entonces cualquier punto de acumulaci´on de {xm}m∈Npertenece aarg min FB. 124 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa Demostraci´on: S´olo se probar´a la primera parte, puesto que la demostraci´on de la segunda es an´aloga. En primer lugar, debido a que la sucesi´on {Fm}es decreciente, se puede aplicar el teorema 2.46 en [1], obteni´endose que {Fm}es epi-convergente. Adem´as se obtiene por la proposici´on 2.4.8 en [1] que lim m→∞ inf x∈R2Fm(x) = inf x∈R2lim m→∞ Fm(x) = inf x∈R2FB(x).(11) Finalmente, por el teorema 2.12 de [1], deducimos que cualquier punto de acumulaci´on de la sucesi´on {xm}es una soluci´on de FB.¤ El resultado anterior prueba que la soluci´on del problema ordenado de Weber con un calibrador general puede ser arbitrariamente aproximada por las soluciones del mismo problema con calibradores poli´edricos. 5 El problema multiobjetivo En cualquier problema de localizaci´on donde el criterio para localizar un servicio sea atractivo, todos los usuarios quieren tener simult´aneamente el servicio tan cercano como sea posible. Por ello, una caracter´ıstica intr´ınseca de los problemas de localizaci´on es su naturaleza multiobjetivo. El prop´osito de los problemas multiobjetivo es el de optimizar simult´aneamente varias funciones objetivo. Sin embargo, debido a que rara vez existe un punto simult´aneamente ´optimo en todas las funciones objetivo, tratamos de caracterizar el conjunto de soluciones no dominadas o, equivalentemente, el conjunto de puntos para los que no existe otro mejor en cada funci´on objetivo considerada en el problema. En Teor´ıa de Localizaci´on, la caracterizaci´on del conjunto de soluciones no dominadas en problemas multiobjetivo ha sido ampliamente estudiada, aunque esta cuesti´on ha sido s´olo parcialmente resuelta. Una formulaci´on general del problema multiobjetivo es la que viene dada por la siguiente expresi´on: v−min(F1(x),...,Fk(x)), donde v−min representa la minimizaci´on vectorial y las F1,...,Fkson las funciones objetivo. Al problema donde cada funci´on Fies la distancia al punto fijo ai, medida con la misma norma, se le llama problema de localizaci´on punto-objetivo. Este problema fue tratado por primera vez en [47] para la norma l2. Posteriormente, Durier en [11] resolvi´o este problema para calibradores poli´edricos. Otras referencias dedicadas a estudiar diferentes versiones del problema de localizaci´on punto-objetivo son [3, 5, 7, 15, 19, 25, 29, 44, 48]. El caso en que cada Fies una suma ponderada de distancias medidas con la norma l1(el problema de Fermat-Weber con norma rectangular) fue resuelto en Modelos de Localizaci´on Continua 125 [18, 33]. El problema en que las Fison sumas ponderadas de distancias medidas con normas arbitrarias fue resuelto en [34]. Por otro lado, el caso donde existe una demanda regional y las funciones Fipara i= 1,...,k son funciones inf-distancias (es decir, la distancia al punto m´as pr´oximo de cada conjunto de demanda) fue resuelto en [40]. De esta forma, aunque el problema ha sido estudiado en numerosas ocasiones y por diferentes autores, las caracterizaciones obtenidas se aplican s´olo en casos particulares. En esta secci´on, se proporciona una soluci´on geom´etrica para esta clase de problemas, donde la ´unica condici´on que se impone a las funciones objetivo consideradas es que sean convexas e inf-compactas. A pesar de la generalidad del problema considerado, los resultados son f´aciles de comprender y en las demostraciones se usan, casi exclusivamente, herramientas del An´alisis Convexo. 5.1 El modelo Sean F1,...,Fkfunciones reales convexas e inf-compactas definidas por simplicidad en R2que reperesentan diferentes criterios o escenarios. Recu´erdese que una funci´on fes inf-compacta si los conjuntos de nivel inferior {x:f(x)≤ ρ}son compactos para cada ρ∈R. Nuestro objetivo es encontrar el conjunto de puntos x∈R2tales que no existe y∈R2que mejore el valor de Fien xpara cada i∈ {1,...,k}. De esta forma, la formulaci´on del problema viene dada por: v−min x∈R2(F1(x),...,Fk(x)).(12) El conjunto soluci´on que se va a considerar para este problema viene dado por: WE(F1,...,Fk) := {x∈R2:∀y(6=x)∈R2,∃i, 1≤i≤k, con Fi(x)≤Fi(y)}. Usualmente este conjunto es llamado conjunto de puntos d´ebilmente eficientes. Con el objetivo de facilitar el entendimiento del resto de la secci´on, se usa la siguiente notaci´on. El conjunto de nivel inferior de la funci´on Fpara un valor ρ∈Res L≤(F, ρ) := {x∈R2:F(x)≤ρ} y el conjunto de nivel estrictamente inferior L<(F, ρ) := {x∈R2:F(x)< ρ}. Para una funci´on convexa e inf-compacta Fi, se usar´a la notaci´on X∗(Fi) := arg min x∈R2Fi(x).(13) N´otese que este conjunto es convexo por la convexidad de Fi. En esta secci´on se estudia el problema (12), prob´andose que la estructura geom´etrica de WE(F1, F2, F3) viene dada por la regi´on delimitada por las cadenas de soluciones “biobjetivo” asociadas a cada par de funciones Fi 126 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa yFj, con 1 ≤i, j ≤3. Este resultado permite caracterizar el conjunto WE(F1,...,Fk) mediante la uni´on de los conjuntos soluci´on de cada problema con tres objetivos. A continuaci´on se enuncia una caracterizaci´on te´orica del conjunto WE(F1,...,Fk) que ser´a utilizada a lo largo de esta secci´on. Teorema 5.1 Se verifica que: ˆx∈WE(F1,...,Fk)⇐⇒ k \ i=1 L<(Fi, Fi(ˆx)) = ∅. La demostraci´on de este resultado puede verse en [38]. Nota 5.1 En el caso k= 2, el resultado previo establece que WE(F1, F2) coincide con el lugar geom´etrico de los puntos de tangencia de los conjuntos de nivel inferior de las funciones F1yF2uni´on con X∗(F1)∪ X ∗(F2). Para comprender bien esta afirmaci´on, v´ease el ejemplo 5.1. ¤ Ejemplo 5.1 (ver figura 12) Sean a1= (0,0), a2= (10,0), a3= (14,6), F1(x) = kx−a1k2,F2(x) = kx−a2k1yF3(x) = kx−a3k1. Por el teorema 5.1, WE(F1, F2) es el segmento definido por a1ya2. En efecto, se trata del conjunto de puntos ˆxtales que no hay ning´un otro punto que est´e m´as cerca que ´el de a1en norma k · k2y m´as cerca que ´el de a2en norma k · k1. Por otra parte, WE(F2, F3) es el rect´angulo sombreado con v´ertices opuestos a2ya3. a1a2 a3    WE(F2, F3) WE(F1, F2) Figura 12: Ilustraci´on del ejemplo 5.1. Modelos de Localizaci´on Continua 127 Usando las caracterizaciones precedentes, se obtiene una descripci´on geom´etrica del conjunto WE(F1, F2, F3). El pr´oximo resultado muestra que el conjunto soluci´on del problema 3-criterio es una especie de envolvente definida por el conjunto de soluciones biobjetivo. Sea WE(2) := [ i,j∈{1,2,3} i6=j WE(Fi, Fj) (la uni´on de todas las cadenas bicriterio para los tres criterios F1,F2yF3 considerados). Teorema 5.2 WE(F1, F2, F3) = encl(WE(2)) donde encl(WE(2)) es la regi´on acotada rodeada por WE(2) uni´on con WE(2). El lector interesado puede encontrar la demostraci´on en [38]. Nota 5.2 N´otese que encl(WE(2)) est´a bien definida porque WE(2) es conexo (ver [43]). Adem´as, esta regi´on puede ser equivalentemente definida como el conjunto de puntos tales que si x∈encl(WE(2)) \WE(2) no existe una curva continua c(t), t ∈[0,∞) con c(0) = xy limt→∞ kc(t)k= +∞, tal que c(t)/∈WE(2),∀t∈[0,∞). ¤ Como ilustraci´on de los resultados anteriores se muestra el siguiente ejemplo. Ejemplo 5.2 Sean a1= (0,0), a2= (3,−1), a3= (3,3) y las funciones F1,F2 yF3tales que, L≤(F1,1) = ½(x1, x2) : x2 1 4+x2 2 9≤1¾ L≤(F2,1) = ©(x1, x2) : (x1−3)2+ (x2+ 1)2≤1ª L≤(F3,1) = ½(x1, x2) : (x1−3)2 9+(x2−3)2 4≤1¾. Es inmediato que estas tres funciones son convexas e inf-compactas. Por consiguiente, aplicando los resultados previos se obtiene que el conjunto WE(F1, F2, F3) es la regi´on delimitada por las curvas que unen a1con a3,a1 con a2y el segmento que une a2con a3en la figura 13. Los resultados anteriores nos permiten demostrar el que sigue, que proporciona una caracterizaci´on geom´etrica del problema general con k objetivos. Teorema 5.3 WE(F1,...,Fk) = [ i,j,`∈{1,...,k} WE(Fi, Fj, F`) 128 J. Puerto y A.M. Rodr´ ıguez-Ch´ ıa PSfrag replacements a1 a2 a3 WE(F1, F3) WE(F1, F2) WE(F2, F3) WE(F1, F2, F3) Figura 13: Ilustraci´on del ejemplo 5.2. Demostraci´on: Por el teorema 5.1, ˆx∈WE(F1,...,Fk) si y s´olo si \ 1≤i≤k L<(Fi, Fi(ˆx)) = ∅. Aplicando el teorema de Helly (ver [39]), esta intersecci´on es vac´ıa si y s´olo si existen i, j, ` ∈ {1,...,k}tales que L<(Fi, Fi(ˆx)) ∩L<(Fj, Fj(ˆx)) ∩ L<(F`, F`(ˆx)) = ∅y esto es equivalente a ˆx∈WE(Fi, Fj, Fl). Esto prueba que WE(F1,...,Fk)⊆[ i,j,`∈{1,...,k} WE(Fi, Fj, F`). Puesto que en cualquier caso se tiene que [ i,j,`∈{1,...,k} WE(Fi, Fj, F`)⊆WE(F1,...,Fk), el resultado es cierto. ¤ Ejemplo 5.3 (Ver figura 14) Sean a1= (7,5), a2= (18,205), a3= (22,605), F1(x) = kx−a1k∞,F2(x) = kx−a2k1yF3(x) = kx−a3k1. Por el teorema 5.1, WE(F1, F2) es el camino en negrita que une a1ya2, WE(F1, F3) es el camino en negrita uniendo a1ya3, y WE(F2, F3) es el cuadrado sombreado con a2y a3como extremos opuestos. De esta forma, por el teorema 5.2, WE(F1, F2, F3) Modelos de Localizaci´on Continua 129 es la regi´on sombreada que encierra la uni´on de los tres conjuntos definidos previamente. N´otese que este conjunto es uni´on de convexos elementales de dimensi´on completa.    a1 a2 a3 WE(F1, F2) WE(F1, F3) WE(F2, F3) WE(F1, F2, F3) Figura 14: Ilustraci´on del ejemplo 5.3. 6 Conclusi´on En este trabajo se han revisado problemas de localizaci´on continua de tres tipos, cuya generalidad incluye como casos particulares un gran n´umero de modelos cl´asicos considerados en la literatura. En cada caso se ha presentado el modelo matem´atico y se han estudiado propiedades que permiten caracterizan su conjunto soluci´on. En la presentaci´on se ha utilizado una amplia bibliograf´ıa que permitir´a al lector interesado profundizar en el estudio de la Teor´ıa de Localizaci´on. Agradecimientos Este trabajo ha sido parcialmente financiado por los proyectos del Ministerio de Ciencia y Tecnolog´ıa BFM2001-2378 y BFM2001-4028. Referencias [1] Attouch H. Variational Convergence for Functions and Operators, Pitman Advanced Publishing Program, 1984. [2] Bauer F.L., Stoer J., and Witzgall C. Absolute and monotonic norms, Numer. Math., 3:257–264, 1961.