Problema de localización con barreras

UNIVERSIDAD DE SEVILLA MÁSTER UNIVERSITARIO EN MATEMÁTICAS TRABAJO FIN DE MÁSTER: PROBLEMA DE LOCALIZACIÓN CON BARRERAS DEPARTAMENTO DE ESTADÍSTICA E INVESTIGACIÓN OPERATIVA, FACULTAD DE MATEMÁTICAS Presentado por: MOISÉS RODRÍGUEZ MADRENA Dirigido por: JUSTO PUERTO ALBANDOZ Sevilla Junio 2017 Abstract In location problems, the distance functions that model the travel distance between the elements of the problem play a fundamental role in the adequacy or fidelity of the theoretical problem to the real problem considered. Think, for example, of problems in the design of connective networks (to this type of problems belongs, to mention some realworld problem, the routing of pipelines on ships), often the sections of these networks must obey a particular structure or pattern, the distance functions are then convenient for calculating the distance between the nodes of the network. Another real feature of location problems, which is of great importance in achieving good modeling, is the constraint of the feasible solution space. This restriction is due to the presence in the environment where the problem is considered of bodies or obstacles, called barriers in the literature, that do not allow travelling or passing through them. The barrier distance functions are, in this case, the way to obtain the adequacy of the theoretical problem to the real problem. The object of study of the present End of Master Project are the mentioned barrier distance functions and their application to the location problems. The first chapter gives a brief summary of the elementary distance measures used in the modeling of location and transport problems, as well as their basic properties. The barriers distances, central concept of this End of Master Project, appear in the second chapter, where special attention is paid to the case of polyhedral barriers and where the main known results in the art are shown. More precisely, these distances are introduced in the chapter to address the problem of the minimum rectangular path in the presence of hyperparallelepiped complexes that perform as barriers in any real space of finite size. Extensions of the known results for the treatment of this problem in the planar case and new original methods for their exact resolution are the main contribution of this chapter and of the work in general. In the third chapter a particular case of the location problem with barriers is treated: the median problem in rectangular metric and in the context of hyperparallelepipeds that act as barriers in any real space of finite size. The methods developed in the second chapter are the basis for the construction of the new algorithms that solve such problem, which are presented in this chapter. The computational performance tests of the algorithms of the second and third chapters are collected in the fourth and final chapter. I Extracto En los problemas de localización, las funciones de distancia que modelan la distancia de viaje entre los elementos del problema juegan un papel fundamental en la adecuación o fidelidad del problema teórico al problema real considerado. Piénsese, por ejemplo, en los problemas de diseño de redes conectivas (a este tipo de problemas pertenece, por citar algún problema del ámbito real, el enrutamiento de tuberías en barcos), a menudo los tramos de estas redes deben de obedecer a una determinada estructura o patrón, las funciones de distancia son entonces convenientes para el cálculo de la distancia entre los nodos de la red. Otra característica real de los problemas de localización, de gran importancia a la hora de conseguir un buen modelado de los mismos, es la restricción del espacio de soluciones factibles. Dicha restricción se debe a la presencia en el entorno donde está considerado el problema de cuerpos u obstáculos, denominados barreras en la literatura, que no permiten el viaje o paso a través de ellos. Las funciones de distancia con barrera son, en este caso, la forma de conseguir la adecuación del problema teórico al problema real. El objeto de estudio del presente Trabajo de Fin de Máster son las mencionadas funciones de distancia con barreras y su aplicación a los problemas de localización. En el primer capítulo se ofrece un resumen suscinto de las medidas de distancia elementales usadas en el modelado de los problemas de localización y transporte, así como de sus propiedades básicas. Las funciones de distancia con barreras, concepto central del Trabajo de Fin de Máster, aparecen en el capítulo segundo, donde se presta especial atención al caso de barreras poliédricas y se muestran los principales resultados conocidos en la materia. Más concretamente, estas distancias son introducidas en el capítulo para abordar el problema del camino rectangular mínimo en presencia de complejos de hiperparalelepípedos barrera en cualquier espacio real de dimensión finita. Extensiones de resultados conocidos para el tratamiento de este problema en el caso plano y nuevos métodos originales para su resolución exacta son la principal contribución de este capítulo y del trabajo en general. En el capítulos tercero se trata un caso particular del problema de localización con barreras: el problema de la mediana en métrica rectangular y en el contexto de hiperparalelepípedos que actúan como barreras en cualquier espacio real de dimensión finita. Los métodos desarrollados en el segundo capítulo son la base para construir los nuevos algoritmos que resuelven dicho problema y que se presentan en este capítulo. III IV Extracto Las pruebas de rendimiento computacional de los algoritmos de los capítulos segundo y tercero se recogen en el cuarto y último capítulo. Índice general Abstract I Extracto III 1. Funciones de distancia 1 1.1. Normasymétricas ........................... 1 1.2. Normasbloque ............................. 3 1.3. Relación entre las normas bloque y la norma de Manhattan . . . . . . 9 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 11 2.1. Caminos mínimos y el concepto de visibilidad . . . . . . . . . . . . . 11 2.2. Barreras poliédricas y la propiedad de contacto con barreras . . . . . 16 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera . 18 2.3.1. Formulación como un problema de camino mínimo en grafos 19 2.3.2. Formulaciones de programación lineal y entera mixta . . . . . 35 2.4. Camino bloque mínimo en presencia de romboides barrera . . . . . . 73 3. Problema de la mediana rectangular en presencia de paralelepípedos barrera 77 3.1. Problema de localización con barreras . . . . . . . . . . . . . . . . . 77 3.2. Problema de la mediana rectangular en presencia de paralelepípedos barrera.................................. 79 3.2.1. Existencia de conjunto dominante finito . . . . . . . . . . . . 80 3.2.2. Una formulación de programación lineal y entera mixta . . . . 84 3.3. Problema de la mediana bloque en presencia de romboides barrera . . 87 4. Pruebas computacionales 89 4.1. Rendimiento de los modelos de programación lineal y entera mixta . . 89 Conclusiones 93 Bibliografía 95 1 Funciones de distancia La elección de una función de distancia adecuada juega un papel fundamental a la hora de proporcionar una buena estimación de las distancias de viaje en entornos reales. Dependiendo del modo de viaje y del tipo de problema considerado, podemos usar, por ejemplo, la distancia euclídea para modelar los desplazamientos por vía aérea o la métrica de Manhattan para problemas de transporte urbano en Nueva York. Esto significa que diferentes modos de transporte requieren diferentes formas de estimación de la distancia. Consecuentemente, el aumento de la heterogeneidad en los problemas relativos al sector del transporte ha llevado aparejado una creciente preocupación por estimar con una mayor precisión las distancias de viaje. En lo que sigue se ofrece un resumen sintético de las normas y medidas de distancia usadas en el modelado de los problemas de localización y transporte, así como de sus propiedades básicas. 1.1. Normas y métricas Definición 1.1. Sea Sun conjunto compacto y convexo en Rnconteniendo al origen en su interior. Además, sea Ssimétrico con respecto al origen y sea X∈Rn. La norma γ:Rn→Rnde Xcon respecto a Sviene dada por γ(X) := ´ınf{λ > 0 : X∈λS}.(1.1) A menudo nos referiremos a γ(X)como kXkγ. Toda norma γdefinida de acuerdo a la Definición 1.1 satisface las propiedades de la norma en Rn. Lema 1.1. (Minkowski, 1911) Sea γdefinida de acuerdo a la Definición 1.1. Entonces, para todo X, Y ∈Rny para todo λ∈R, γ(X)≥0yγ(X)=0⇔X= 0,(1.2) γ(λX) = |λ|γ(X),(1.3) γ(X+Y)≤γ(X) + γ(Y).(1.4) 1 8 1.2. Normas bloque Figura 1.5: Bola unidad de la norma `1y bola unidad de la norma ponderada `w 1en R2. Ejemplo 1.3. La norma ponderada uno-ifinito `α,β 1,∞se define como la suma de las normas ponderadas `α 1y`β ∞: kXk`α,β 1,∞=kXk`α 1+kXk`β ∞=X i=1,2 αi|xi|+ m´ax i=1,2βi|xi|, donde α1, α2, β1, β2>0(ver Figura 1.6). Los vectores fundamentales de la norma ponderada uno-infinito en R2son de la siguiente forma: v1=0 1 α2+β2, v2=  1 α1+β1+β1 β2α2 1 α2+β2+β2 β1α1 , v3=1 α1+β1 0, v4=  1 α1+β1+β1 β2α2 −1 α2+β2+β2 β1α1 , v5=0 −1 α2+β2, v6=  −1 α1+β1+β1 β2α2 −1 α2+β2+β2 β1α1 , v7=−1 α1+β1 0, v8=  −1 α1+β1+β1 β2α2 1 α2+β2+β2 β1α1 . 1. Funciones de distancia 9 Figura 1.6: Bola unidad de la norma ponderada uno-infinito en R2. 1.3. Relación entre las normas bloque y la norma de Manhattan En esta sección vamos a seguir tratando el caso del espacio bidimensional real R2, concretamente, nos vamos a centrar en las normas bloque con exactamente cuatro vectores fundamentales (ver Figura 1.7) y a discutir su relación con la norma de Manhattan `1 (ver Figura 1.5). Para distinguir estas funciones de distancia más generales de la norma de Manhattan con los vectores fundamentales v1, ..., v4etiquetados como aparecen en el Ejemplo 1.2, en adelante vamos a denotar a los vectores fundamentales de cualquier otra norma bloque con cuatro vectores fundamentales por u1, ..., u4. Figura 1.7: Bola unidad de una norma bloque con cuatro vectores fundamentales u1, ..., u4. Sea γuna norma bloque con vectores fundamentales (ordenados en el sentido de las agujas del reloj) u1=u1 1, u1 2t, u2=u2 1, u2 2t, u3=u3 1, u3 2t, u4=u4 1, u4 2t, cumpliendo u3=−u1yu4=−u2. Si Tes la transformación lineal tal que T(u1) = Tu1=v1yT(u2) = Tu2=v2, entonces T=t11 t12 t21 t22=1 u1 2u2 1−u1 1u2 2u1 2−u1 1 −u2 2u2 1.(1.21) 10 1.3. Relación entre las normas bloque y la norma de Manhattan Obsérvese que la correspondiente transformación inversa viene dada por T−1=u2 2u1 1 u2 2u1 2. Si consideramos, por ejemplo, la norma `∞con los vectores fundamentales etiquetados como en el Ejemplo 1.1, entonces tenemos T=1 21−1 1 1 yT−1=1 1 −1 1. Estableciendo T(X) := TX para todo X∈R2, podemos probar el siguiente resultado que relaciona las distancias en norma bloque con la métrica `1. Lema 1.5. Sea γuna norma bloque con cuatro vectores fundamentales y sea Tla transformación lineal definida por (1.21). Entonces γ(X, Y ) = `1(T(X), T(Y)) para todo X, Y ∈R2. Demostración. Consideremos en primer lugar el caso especial en el que Y= 0. Si además X= 0, entonces el resultado se obtiene trivialmente. Sea X∈C(ui, ui+1) para algún i∈ {1, ..., 4}y sea X=λiui+λi+1ui+1 la única representación de Xen términos de uiyui+1 (recordemos que C(ui, ui+1)es un cono convexo). Dado que γtiene sólamente cuatro direcciones fundamentales podemos suponer sin pérdida de generalidad que ui∈ {u1,−u1}yui+1 ∈ {u2,−u2}. Usando (1.19) y el Lema 1.3 se sigue que `1(T(X),0) = |t11x1+t12x2|+|t21x1+t22x2| = u2 1x1−u1 1x2 u1 2u2 1−u1 1u2 2 + u2 1x2−u2 2x1 u1 2u2 1−u1 1u2 2 =λi+1 +λi =γ(X, 0). Ahora consideremos el caso general en el que X, Y ∈R2son ambos diferentes de 0. Dado que Tes una transformación lineal, inmediatamente obtenemos `1(T(X), T(Y)) = `1(T(X)−T(Y),0) = `1(T(X−Y),0) =γ(X−Y, 0) = γ(X, Y ). Nótese que la definición de Tpara una norma bloque γdada depende de la asignación T(u1) = v1y cambia si fijamos T(u1) = −v1,T(u1) = v2oT(u1) = −v2. 2 Camino rectangular mínimo en presencia de paralelepípedos barrera El problema de hallar caminos mínimos en entornos reales tiene un gran interés en el contexto de la localización, así como en otros ámbitos más allá de éste. Los problemas de camino mínimo en presencia de barreras físicas aparecen, por ejemplo, en la planificación de rutas marítimas de mínima longitud entre diferentes puertos o en la determinación del camino óptimo de un robot en una planta industrial. En este capítulo nos vamos a centrar en los caminos mínimos entre dos puntos con respecto a la métrica de Manhattan cuando existen paralelepípedos que actúan como barreras. Consideraremos que dichos paralelepípedos pueden intersecar, dando lugar a obstáculos complejos. Diferentes algoritmos son presentados para resolver el problema de camino mínimo en métrica rectangular: por un lado, un método basado en la extensión al caso n-dimensional de resultados conocidos para la versión plana del problema; por otro lado, nuevos modelos de programación lineal y entera mixta. El capítulo comienza introduciendo las conceptos básicos empleados en el estudio de los caminos mínimos en presencia de barreras, sigue mostrando algunos resultados que se tienen cuando las barreras presentan formas poliédricas para finalmente dedicarse al problema particular en norma rectangular y barreras en forma de paralelepípedos descrito antes. 2.1. Caminos mínimos y el concepto de visibilidad Sea duna métrica fijada en el espacio n-dimensional Rn(n≥2) que se quiere utilizar para medir distancias de viaje entre pares de puntos de Rn. Asumimos que la métrica destá inducida por una norma k•kd:Rn→Rny que es por tanto simétrica (1.8) y satisface la desigualdad triangular (1.9). Como sabemos, dpuede calcularse a partir de k•kdcomo d(X, Y ) = kY−Xkd∀X, Y ∈Rn. 11 12 2.1. Caminos mínimos y el concepto de visibilidad Además, sea {B1, ..., BN}un conjunto finito de conjuntos cerrados y disjuntos dos a dos de Rncon interior no vacío. Cada conjunto Bi,i= 1, ..., N, es llamado barrera (u obstáculo), y la unión de todas las barreras se denota por B, i.e., B=SN i=1 Bi. Nótese que no se está suponiendo que las barreras tengan que ser acotadas. Asumimos que moverse por el interior de las barreras está prohibido. Sin embargo, está permitido moverse por la frontera ∂(Bi)de cada región barrera Bi,i= 1, ..., N. Sea F:= Rn\int(B)la región factible (o espacio libre) en Rn. Para evitar la infactibilidad, vamos a suponer que Fes un subconjunto conexo de Rn. La función de distancia con barreras (también llamada métrica de camino mínimo odistancia geodésica)dB:F × F → Rmide la longitud del camino más corto (o los caminos más cortos) entre dos puntos XeYen la región factible F=Rn\int(B)que no interseca el interior de ninguna barrera. Definición 2.1. Un X-Ycamino es una curva continua Pdada por la parametrización p= (p1, ..., pn)t: [0,1] →Rncon p(0) = Xyp(1) = Yque es continuamente diferenciable en [0,1] salvo quizá en un número finito de puntos, donde la derivada p0= (p0 1, ..., p0 n)ttiene límite finito por la izquierda y por la derecha. La longitud l(P)del X-Ycamino Pcon respecto a la métrica fijada dviene dada por l(P) := Z1 0 kp0(t)kddt. Si Pno interseca el interior de ninguna barrera, i.e., si p([0,1]) ∩int(B) = ∅, el X-Y camino Pes un X-Ycamino permitido. Usando la noción de X-Ycamino permitido, la distancia con barreras dBentre dos puntos XeYen la región factible Fpuede definirse de la siguiente forma. Definición 2.2. Para X, Y ∈ F, la distancia con barreras dB(X, Y )es el ínfimo de las longitudes de todos los X-Ycaminos permitidos, i.e., dB(X, Y ) := ´ınf{l(P) : Pes un X-Ycamino permitido}.(2.1) Un X-Ycamino permitido con longitud dB(X, Y )es un X-Ycamino permitido dmínimo (o X-Ycamino óptimo, camino geodésico). Nótese que la existencia de un X-Ycamino permitido d-mínimo, que es una curva diferenciable salvo quizá en un número finito de puntos, no puede ser garantizada siempre. En particular, pueden existir casos donde el ínfimo en (2.1) se alcance para un camino que no satisfaga la condición de diferenciabilidad de la Definición 2.1. Un ejemplo de esta situación en el caso bidimensional se muestra en la Figura 2.1. 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 13 Figura 2.1: Un ejemplo en R2donde no existe ningún X-Ycamino `2-mínimo. La frontera superior del conjunto barrera Btiene un número infinito de puntos extremos en (1/i, 1−1/i2)ty(−1/i, 1−1/i2)t,i∈ {2,4,8,16, ...}, es por ello que ningún camino sobre esta frontera es un X-Ycamino permitido de acuerdo a la Definición 2.1. En adelante nos vamos a centrar en los problemas y conjuntos de barreras para los que existe un X-Ycamino permitido d-mínimo para toda elección de X, Y ∈ F. Este es el caso, por ejemplo, de los conjuntos de barreras poliédricos en Rn. En estos casos, el ínfimo en (2.1) puede ser reemplazado por un mínimo. La distancia con barreras dBno es, en general, positivamente homogénea, lo cual implica que no existe una norma induciendo la métrica dB. Más aún, la distancia con barreras dBtampoco es, en general, convexa. Sin embargo, dBdefine una métrica en la región factible F. Lema 2.1. Sea duna métrica inducida por una norma y sea B=SN i=1 Bila unión de los conjuntos barrera. Entonces, dBdefine una métrica en F, i.e., para todo X, Y, Z ∈ F, dB(X, Y )≥0ydB(X, Y )=0⇔X=Y, (2.2) dB(X, Y ) = dB(Y, X),(2.3) dB(X, Y )≤dB(X, Z) + dB(Z, Y ).(2.4) Por consiguiente, (F, dB)es un espacio métrico n-dimensional. Demostración. Las desigualdades e igualdades de (2.2) y (2.3) se tienen de forma trivial. Para probar la desigualdad triangular (2.4) consideremos tres puntos X, Y, Z ∈ 14 2.1. Caminos mínimos y el concepto de visibilidad F. Es fácil ver que para todo X-Zcamino permitido PX,Z y para todo Z-Ycamino permitido PZ,Y existe un X-Ycamino permitido PX,Y =PX,Z ∪PZ,Y de longitud l(PX,Y ) = l(PX,Z ) + l(PZ,Y )pasando por Z. Por tanto, dB(X, Y ) = ´ınf{l(PX,Y ) : PX,Y es un X-Ycamino permitido} = ´ınf{l(PX,Z ) + l(PZ,Y ) : PX,Z es un X-Zcamino permitido y PZ,Y es un Z-Ycamino permitido} =dB(X, Z) + dB(Z, Y ). Nos referiremos a dBcomo métrica de camino mínimo odistancia geodésica. El siguiente colorario es una consecuencia inmediata de la definición de dB. Corolario 2.1. Sea duna métrica inducida por una norma y sea B=SN i=1 Bila unión de los conjuntos barrera. Entonces dB(X, Y )≥d(X, Y )∀X, Y ∈ F. Considerando la distancia desde un punto dado X∈ F podemos distinguir, por un lado, las partes de Fen las que dB(X, Y )es equivalente a la métrica d(X, Y )y, por otro lado, las partes de Fdonde dB(X, Y )> d(X, Y ). Definición 2.3. Dos puntos X, Y ∈ F son d-visibles si dB(X, Y ) = d(X, Y ), esto es, si la distancia entre XeYno se ve incrementada por la presencia de las regiones barrera. El conjunto de puntos que son d-visibles desde un punto X∈ F es, por tanto, visiblesd(X) := {Y∈ F :dB(X, Y ) = d(X, Y )}. De forma similar, llamaremos d-sombra de un punto X∈ F al conjunto de puntos Y∈ F que no son d-visibles desde X, i.e., sombrad(X) := {Y∈ F :dB(X, Y )> d(X, Y )}. Definición 2.4. La frontera de la clausura de la d-sombra de un punto X∈ F (o, para abreviar, la frontera de sombrad(X)) es ∂(sombrad(X)) := {Y∈ F :Nε(Y)∩sombrad(Y)6=∅y Nε(Y)*sombrad(Y)∀ε > 0}, donde Nε(Y) := {Z∈Rn:`2(Z, Y )< ε}. 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 15 En la Figuara 2.2 se muestran dos ejemplos de posibles formas de la d-sombra de un punto dado X∈R2con respecto a dos métricas ddiferentes. Figura 2.2: La `2-sombra y la `1-sombra de un punto X∈R2. Obsérvese que para algunas elecciones de la métrica dun punto que es d-visible puede no ser `2-visible, esto es, no visible en el sentido usual de visibilidad en línea recta. Por otra parte, todo par de puntos `2-visibles son también d-visibles si des una métrica inducida por una norma, como muestra el siguiente lema. Lema 2.2. Sea duna métrica inducida por una norma. Entonces sombrad(X)⊆sombra`2(X), X ∈ F. Además, si X, Y ∈ F son `2-visibles, X6=Y, entonces el segmento de recta que conecta XeYes un X-Ycamino permitido d-mínimo con longitud d(X, Y ). Demostración. Sin pérdida de generalidad, sea X= 0 el origen (siempre puede hacerse una traslación que lleve Xal origen) y sea Y∈ F un punto `2-visible desde X. Entonces, el segmento de recta que conecta XeYes un X-Ycamino permitido Pdado por la parametrización p: [0,1] →Rn,p(t) = t·Y,t∈[0,1]. Usando la definición de distancia con barreras dB, Definición 2.2, la longitud de Ppuede calcularse como dB(X, Y )≤l(P) = Z1 0 kp0(t)kddt =Z1 0    d dt(tY )   d dt =Z1 0 kYkddt =kYkd=d(0, Y ). Por tanto, el segmento de recta que conecta XeYes un X-Ycamino permitido dmínimo con longitud d(X, Y ). Por consiguiente, la subregión de Fque es `2-visible desde un punto X∈ F es también d-visible desde X, y sombrad(X)⊆sombra`2(X) para todo X∈ F. 16 2.2. Barreras poliédricas y la propiedad de contacto con barreras 2.2. Barreras poliédricas y la propiedad de contacto con barreras Un conjunto poliédrico en R2es un conjunto cerrado cuya frontera es un polígono. En Rncon n≥3, llamaremos conjunto poliédrico a todo conjunto cerrado cuyas caras de dimensión n−1son conjuntos poliédricos en Rn−1. Conviene hacer notar aquí la diferencia entre poliedro y conjunto poliédrico, mientras que el primero es siempre convexo por ser la intersección de un número finito de semiespacios, el segundo no tiene por qué serlo necesariamente. En esta sección nos vamos a centrar en el caso particular en el que el conjunto de barreras {B1, ..., BN}está constituido por conjuntos disjuntos dos a dos, cerrados, poliédricos, pero no necesariamente convexos, en Rn. Además, asumimos que el número de caras de las barreras de B=SN i=1 Bies finito para evitar casos degenerados como el que se ilustró en la Figura 2.1. Los resultados que se muestran a continuación garantizan la existencia de caminos permitidos mínimos para este tipo de barreras. Para poder abordar el caso general n-dimensional será necesario fijar antes la atención en el caso bidimensional, al conjunto finito de puntos extremos de Blo vamos a denotar por P(B). Lema 2.3. Sea {B1, ..., BN}un conjunto finito de conjutos barrera en R2disjuntos dos a dos, cerrados, poliédricos y con un conjunto finito de puntos extremos P(B). Sea duna métrica inducida por una norma y sean X, Y ∈ F. Entonces existe un X-Y camino permitido d-mínimo SP con la propiedad que apararece a continuación. Propiedad de contacto con barreras: SP es un camino lineal a trozos con puntos críticos solamente en los puntos extremos de las barreras. Demostración. Sean X, Y ∈ F y sea SP un X-Ycamino permitido d-mínimo en Fque no satisface la propiedad de contacto con barreras. Nótese que, dado que el conjunto de barreas y también el conjunto de puntos extremos de las barreras P(B) son finitos, SP puede subdividirse en un conjunto finito de puntos verificando que dos puntos consecutivos en SP son `2-visibles. El Lema 2.2 implica que el segmento de recta que conecta dos puntos consecutivos en SP es un camino permitido d-mínimo uniendo estos dos puntos. Por tanto, podemos construir un camino lineal a trozos SP0 uniendo XeYcon un conjunto finito de puntos críticos y cuya longitud es menor o igual a la de SP. Ahora puede construirse un X-Ycamino permitido d-mínimo SP00 con la propiedad de contacto con barreras a partir SP0. Sean [Ti−1, Ti]y[Ti, Ti+1]dos segmentos rectilíneos consecutivos de SP0. Asumamos que Ti−1yTi+1 son `2-visibles. Entonces, la desigualdad triangular implica que los dos segmentos rectilíneos [Ti−1, Ti] y[Ti, Ti+1]pueden ser reemplazados por el segmento rectilíneo [Ti−1, Ti+1]sin incrementar la longitud de SP0. Supongamos ahora que Ti−1yTi+1 no son `2-visibles, usando de nuevo la desigualdad triangular, el punto crítico Tipuede moverse a lo largo de [Ti−1, Ti]o a lo largo de [Ti, Ti+1]hacia Ti−1oTi+1, respectivamente, sin incrementar la longitud de SP0, hasta que uno de estos segmentos rectilíneos sea tangente a una 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 17 barrera. Durante la iteración de ambas operaciones todo punto extremo de una barrera que pertenezca a SP0lo interpretamos como un punto crítico Ti, incluso cuando el segmento rectilíneo [Ti−1, Ti+1]es parte de SP0. De esta forma, con la iteración de ambas operaciones se consigue un camino SP00 con la propiedad deseada después de un número finito de pasos, ya que todo punto crítico de SP0que no es aún un punto extremo de una barrera puede moverse hacia X,Y, o un punto extremo de una barrera. La existencia de X-Ycamino permitido d-mínimo está garantizada, pues si suponemos que dB(X, Y )se alcanza únicamente para caminos en Fque no satisfacen las condiciones de la Definición 2.1, repitiendo el proceso de construcción de SP00 a partir de cualquiera de estos caminos, conseguimos un X-Ycamino con la propiedad de contacto con barreras, y por tanto permitido, con longitud menor o igual que dB(X, Y ), lo cual es una contradicción. Nótese que la propiedad de contacto con barreras no se satisface en general para los problemas en Rncon n≥3. En la Figura 2.3 se muestra un ejemplo de situación en R3en la que no existe ningún X-Ycamino permitido `2-mínimo con puntos críticos sólo en los puntos extremos de las barreras presentes. Sin embargo, el Lema 2.3 puede generalizarse al caso n-dimensional como muestra el Lema 2.4 a continuación. Figura 2.3: Un X-Ycamino permitido `2-mínimo en un entorno con dos barreras poliédricas en R3. Lema 2.4. Sea {B1, ..., BN}un conjunto finito de conjutos barrera en Rn,n≥3, disjuntos dos a dos, cerrados, poliédricos y con un número finito de caras. Sea duna métrica inducida por una norma y sean X, Y ∈ F. Entonces existe un X-Ycamino permitido d-mínimo SP con la propiedad que apararece a continuación. Propiedad de contacto con barreras generalizada: SP es un camino lineal a trozos con puntos críticos solamente en las caras de las barreras de dimensión n−2o menos. 24 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera [Ti, Ti+1]∩int(B) = ∅y a que los complejos son disjuntos. De esta forma, podemos sustituir cada segmento [Ti, Ti+1]de SP00 por un Ti-Ti+1 camino rectangular permitido de su misma longitud, siendo el resultado de esta sustitución un X-Ycamino rectangular permitido de la misma longitud que SP00 y, por tanto, que SP. Figura 2.9: El Ti-Ti+1 camino rectangular permitido Q0es una amalgamación del Ti- Ti+1 camino rectangular no permitido Q. Si Qes un X-Ycamino rectangular mínimo permitido, el propio Qes un X-Y camino en el sentido de la Definición 2.1: puede parametrizarse en el intervalo [0,1], siendo continuamente diferenciable salvo en un número finito de puntos, estos son, los codos. Que el camino parametrizado es permitido es evidente pues el camino rectangular Qsin parametrizar lo es. Por último, seleccionada una parametrización pde Q(cualquier parametrización estándar para caminos lineales a trozos), puede comprabarse, usando la propiedad de aditividad con respecto al intervalo de integración de la integral, que l(Q) = Z1 0 kp0(t)k`1dt. Si el Lema 2.4 (o el Lema 2.3 según el caso) simplificaba la búsqueda de X-Ycaminos permitidos `1-mínimos para obtener dB(X, Y )al asegurarnos la existencia de uno de estos caminos con la particularidad de ser lineal a trozos y con puntos críticos solamente en partes concretas de las barreras, la noción de X-Ycamino rectangular y el Lema 2.5 facilitan aún más la tarea del cálculo de dB(X, Y )dada la sencillez de estos últimos caminos, pues no son más que una sucesión finita de segmentos paralelos a los ejes coordenados que nos llevan de un punto al otro. Este es el momento de formalizar el problema al que queremos dar solución. 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 25 Problema 2.1. Dado el conjunto {B1, ..., BN}de complejos de paralelepípedos isotéticos en Rndisjuntos dos a dos y dados dos puntos XeYen la región factible F, siendo F=Rn\ B yB=SN i=1 Bi, calcular dB(X, Y )así como un X-Ycamino rectangular permitido Qde esa longitud, es decir, mínimo. Lo primero que debemos plantearnos es si es posible restringir la región de Fdonde podemos encontrar un camino rectangular mínimo permitido. Dicha restricción va a ser posible y para ello se empleará el siguiente concepto. Definición 2.6. Sea Bla unión de un conjunto finito de complejos de paralelepípedos isotéticos en Rndisjuntos a dos a dos y sea F=Rn\ B. La envolvente rectangular iterativa RBde X, Y ∈ F y de Bes el paralelepípedo isotético en Rnmás pequeño tal que X, Y ∈ RBy∂RB∩int(B) = ∅. La envolvente rectangular iterativa de la Definición 2.6 puede obtenerse mediante el siguiente algoritmo. Algoritmo 2.1. (Costrucción de la envolvente rectangular iterativa) Input: Los puntos X= (x1, ..., xn)teY= (y1, ..., yn)ten Fy el conjunto {B1, ..., BN} de complejos de paralelepípedos barrera en Rn, cada uno de ellos descrito por el conjunto de paralelpípedos {B1 i, ..., Bmi i}que lo forman, i= 1, ..., N. Paso 1: Hacer Rigual al paralelepípedo de centro κ:= ((x1+y1)/2, ..., (xn+yn)/2)t y mitad de la anchura en cada coordenada OXk,ξk:= |κk−xk|=|κk−yk|, k= 1, ..., n. Paso 2: Mientras exista un paralelepípedo Bj i∈Bi,j= 1, ..., mi,i= 1, ..., N, tal que ∂R ∩ int(Bj i)6=∅, hacer Rigual al paralelepípedo dado por: el centro de coordenadas κk:= (m´ax{κ0 k+ξ0 k, κ00 k+ξ00 k} − m´ın{κ0 k−ξ0 k, κ00 k−ξ00 k})/2, siendo κ0 k, κ00 kyξ0 k, ξ00 klas coordenadas de los centros y las mitades de las anchuras en la coordenada OXkdel paralelepípedo Rconstruido en la etapa anterior y el paralelepípedo Bj irespectivamente, k= 1, ..., n; y mitad de la anchura en cada coordenada OXk,k= 1, ..., n, ξk:= |κk−m´ax{κ0 k+ξ0 k, κ00 k+ξ00 k}| =|κk−m´ın{κ0 k−ξ0 k, κ00 k−ξ00 k}|. Output: RB:= R. El Algoritmo 2.1 sigue la idea elemental de ir englobando sucesivamente mediante un paralelepípedo contenedor mínimo los paralelepípedos que forman los complejos de B 26 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera hasta obtener RB. La Figura 2.10 ilustra la aplicación del Algoritmo 2.1 en un ejemplo con cinco complejos de paralelepípedos barrera en el plano. Figura 2.10: Construcción de RBusando el Algoritmo 2.1. Lema 2.6. El Algoritmo 2.1 halla la envolvente rectangular iterativa de X, Y ∈ F y Ben un número finito de pasos. 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 27 Demostración. El Algoritmo 2.1 termina en un número finito de pasos, pues estamos asumiendo que el número de complejos barrera así como el número de paralelepípedos por los que están formados cada uno de ellos son finitos, luego el Paso 2 del algoritmo se ejecutará a lo sumo PN i=1 miveces, siendo Nel número de complejos barerra y mi el número de paralelepípedos que constituyen el complejo Bi,i= 1, ..., N. Para probar la corrección del Algoritmo 2.1 vamos a denotar por Rl,l= 1, ..., L, al paralelepípedo obtenido tras la l-ésima iteración del algoritmo, de esta forma, R1es el paralelepípedo contenedor mínimo de XeY, y RLes el paralelepípedo obtenido al finalizar el algoritmo. Entonces, el Algoritmo 2.1 construirá correctamente la envolvente rectangular iterativa RBsi RL=RB. Claramente, Rl⊆ Rl+1 se tiene para todo l= 1, ..., L. Por tanto, X, Y ∈ RL. Probemos ahora que ∂RL∩int(Bi)6=∅,i= 1, ..., N. Si esto no se da, entonces existe un punto Z∈∂RL∩int(Bi). Sea Bj i,j∈ {1, ..., mi}, un paralelepípedo del complejo Bital que Z∈Bj i. Si Z∈int(Bj i)entonces llegamos a un absurdo puesto que por el Paso 2 del algoritmo el paralelepípedo Bj ihabría sido añadiendo a RLen algún momento de la ejecución, no dando lugar a que z∈∂RL. Si Zpertenece a la frontera de Bj i, entonces, por las suposiciones que estamos haciendo sobre la descripción de los complejos de paralelepípedos barrera, existirá otro paralelepípedo Bk idel complejo Bi distinto de Bj ital que Z∈int(Bk i), con lo que, de nuevo por el Paso 2, se llegaría a una contradicción, teniéndose por tanto ∂RL∩int(B) = ∅. Puesto que X, Y ∈ RLy ∂RL∩int(B) = ∅, se tiene la contención RB⊆ RL, por ser RBel menor paralelepípedo isotético que verifica estas condiciones. Por otro lado, R1⊆ RBse tiene por el Paso 1 del algoritmo. Supongamos ahora que RL*RB. Entonces existe un índice r∈ {2, ..., L}tal que Rl⊆ RBpara todo l∈ {1, ..., r −1}, pero Rr*RB. Sea Br Rel paralelepípedo añadido en la iteración r, el cual es parte del complejo BR. Por consiguiente, Br R*RB, y dado que ∂RB∩int(BR) = ∅, se tiene también ∂RB∩int(Br R) = ∅ya que int(Br R)⊆int(BR). Usando que Rr−1⊆ RBllegamos a que int(Br R)∩ Rr−1=∅, lo que contradice la construcción del paralelepípedo Rren la iteración r. Denotemos por Wal número total de paralelepípedos que forman los complejos barrera, es decir, con la notación que venimos utilizando, W=PN i=1 mi. El Paso 1 del Algoritmo 2.1 tiene un coste O(n), siendo nla dimensión del espacio Rnen el que estemos trabajando. Como se ha dicho en la demostración del Lema 2.6, el Paso 2 se realiza a lo sumo Wveces. Las comprobaciones ∂R ∩ int(Bj i)6=∅del Paso 2 para los paralepípedos Bj i∈Bi,j= 1, ..., mi,i= 1, ..., N, tienen un coste O(n), pues para llevarlas a cabo sólo tenemos que comparar los intervalos [κk−ξk, κk+ξk]de ambos paralelepípedos en cada coordenada k= 1, ..., n, además, estas comprobaciones se realizarán cada vez que llegamos al Paso 2 un número de veces acotado por W(una vez por cada uno de los paralelepípedos que forman los complejos barrera). Es fácil observar que la actualización de Rque se lleva a cabo en el Paso 2 tiene un coste O(n). Por tanto, una cota superior asintótica para la ejecución del Algoritmo 2.1 es O(W2n). 28 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera Lema 2.7. Sea Bla unión de un conjunto finito de complejos de paralelepípedos isotéticos en Rndisjuntos a dos a dos y sean X, Y ∈ F con F=Rn\B. Entonces, siempre existe un X-Ycamino rectangular mínimo permitido contenido en la envolvente rectangular iterativa RBde X,YyB. Demostración. Obsérvese que podemos asumir que no hay barreras en Rn\ RBpues- to que esta asunción sólo podría decrementar la longitud de los caminos rectangulares que no están contenidos en RBmientras que no tiene efecto sobre los caminos rectangulares que sí lo están. Asumimos pues que no hay barreras en Rn\ RB. Como sabemos, el Lema 2.3, el Lema 2.4 y el Lema 2.5 implican la existencia de un X-Y camino rectangular mínimo permitido Q. Supongamos que Qes tal que Q*RB. Sean (αi, ωi)los pares de puntos de la frontera de RB, tales que, cuando considaramos Q orientado desde Xhasta Y,Qabandona RBpor αiy vuelve a entrar en la envolvente rectangular iterativa por ωi. La parte del camino Qαi,ωide Qque va desde αiaωise encuentra por tanto completamente contenida en el exterior de RB, salvo αiyωique están en la frontera. Lo que vamos a demostar es que cada porción Qαi,ωide Qpuede ser sustituida por un αi-ωicamino rectangular de la misma longitud contenido en la frontera de RB, con lo que obtendríamos un X-Ycamino rectangular mínimo permitido Q0contenido en RB. Sean αyωcualquiera de los pares de puntos mencionados antes y sea Qα,ω la porción de Qque los une. El camino Qα,ω es un α-ωcamino rectangular mínimo permitido, pues de lo contrario, Qtampoco sería un camino rectangular mínimo permitido. Obsérvese que, puesto que Qα,ω ∩int(RB) = ∅, si consideramos a RBcomo una barrera, Qα,ω sigue siendo un α-ωcamino rectangular mínimo permitido. Los puntos αyωson los únicos puntos de Qα,ω que pertenecen a la frontera de RB, si seguimos considerando a la envolvente rectangular iterativa RBcomo una barrera (la cual contendrá a Bpor la asunción hecha al comienzo de la demostración), por el Lema 2.4 (asumimos en adelante que Rnes tal que n≥3, la demostración en R2es análoga utilizando el Lema 2.3), existe un α-ωcamino permitido `1-mínimo Plineal a trozos con puntos críticos solamente en las caras de dimensión menor o igual que n−2de RB. Por el Lema 2.5, l(P) = l(Q). Sea [Ti, Ti+1]cualquiera de los segmentos que forman P. Como Ti, Ti+1 ∈ RByRBes convexo por ser un poliedro, en concreto un hiperparalelepípedo de dimensión n, el segmento [Ti, Ti+1]⊆ RB. Pero [Ti, Ti+1]es un Ti-Ti+1 camino permitido, luego debe estar contenido en la frontera de RB. Lo que vamos a probar a continuación es que existe una cara de dimensión n−1de RBque contiene a [Ti, Ti+1]. Es sabido, que las caras de dimensión kde RBson hiperparalelepípedos de dimensión k,k= 1, ..., n −1. Como Tiestá en la frontera de RB, entonces alguna de las coordenadas (Ti)jde Tidebe ser igual a uno de los valores extremos κj−ξj, κj+ξjdel paralelepípedo RBen esa coordenada, siendo κjla j-ésima coordenada del centro de RByξjla mitad de la anchura en esa misma coordenada OXjde RB,j∈ {1, ..., n}. De lo contrario siempre podría encontrarse una bola B(Ti, δ)⊆int(RB),δ > 0, lo cual es una constradicción con que Tipertenezaca a la frontera de RB. Lo mismo ocurre 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 29 con Ti+1. Si (Ti)j= (Ti+1)j=κj+sξjcon s∈ {−1,1}para alguna coordenada OXj, j∈ {1, ..., n}, entonces TiyTi+1 están contenidos en la cara de dimensión n−1de RB constiuida por el hiperparalalepípedo de dimensión n−1contenido en el hiperplano Xj=κj+sξj. Si (Ti)j= (Ti+1)j6=κj+sξjpara todo s∈ {−1,1}y toda coordenada OXj,j= 1, ..., n, entonces puede comprobarse que κj−ξj<(Ti+Ti+1)j/2< κj+ξj para todo j= 1, ..., n, es decir, el punto medio de TiyTi+1, que está contenido en [Ti, Ti+1], pertenece al interior de RB, lo cual es una contradicción pues [Ti, Ti+1]es un camino permitido por serlo P. Como TiyTi+1 están contenidos en un hiperparalelepípedo de dimensión n−1, cualquier camino rectangular que va de TiaTi+1 de forma que en cada codo no trivial de la sucesión se iguala una de las coordenadas de Tia la coordenada correspondiente de Ti+1 (ver Figura 2.8), está contenido en dicho paralelepípedo que a su vez está contenido en la frontera de RB. Dichos Ti-Ti+1 caminos rectangulares tienen longitud `1(Ti, Ti+1), es decir, la misma que [Ti, Ti+1](Lema 2.2). De esta forma, podemos sustituir cada segmento [Ti, Ti+1]de Ppor un Ti-Ti+1 camino rectangular permitido de su misma longitud, siendo el resultado de esta sustitución un α-ωcamino rectangular permitido de la misma longitud que Qα,ω contendio en la frontera de RB. El Lema 2.7 nos dice que, a la hora de encontrar un X-Ycamino rectangular mínino permitido, podemos restringir la búsqueda a F ∩ RBen lugar de considerar todo F. Esto implica que, en el Problema 2.1, podemos obviar todos los complejos de hiperparalelepípedos barrera que no estén contenidos en RB, pues no son necesarios en el cálculo de dB(X, Y ). A continuación, vamos a realizar un mallado sobre RB, de forma que buscar X-Y caminos rectangulares mínimos permitidos sea equivalente a resolver un problema de camino mínimo en el grafo que constituye esta malla. La construcción de esta malla va a requerir un tratamiento distinto según estemos en el caso plano o en Rncon n≥3. Consideremos primero el caso bidimensional. Para cada punto Z∈ {X, Y }∪P(B), siendo P(B)el conjunto finito de puntos extremos de B, y para cada vector fundamental vide la norma rectangular, etiquetados como en el Ejemplo 1.2, y la correspondiente dirección fundamental di,i= 1, ..., 4, sea (Z+di)B:= {Z+λdi:λ∈R+,(Z+µdi)∩int(B)∩(R2\ RB) = ∅ ∀0≤µ≤λ} el conjunto de puntos del plano que son `2-visibles desde Zen la dirección fundamental didentro de la envolvente rectangular iterartiva RBde X,YyB. Diremos que (Z+di)B es una línea de construcción rectangular. Definición 2.7. En R2, la red N`1:=  [ Z∈{X,Y }∪P(B) 4 [ i=1 (Z+di)B ∪ S(B)∪∂RB, donde S(B)es el conjunto de las caras de dimensión 1 de todos los complejos de paralelepípedos Bi,i= 1, ..., N, es la red de construcción rectangular de X,YyB. 30 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera Los puntos de intersección de los segmentos en N`1(los cuales pueden ser caras de dimensión 1 de un complejo de paralelepípedos barrera o caras de dimensión 1 de RB o líneas de construcción rectangular) definen el conjunto P(N`1)de nodos de la red, yC(N`1)es el conjunto de celdas resultantes en RB\int(B), i.e., el conjunto de poliedros con puntos extremos en P(B). Nótese que estos poliedros que constituyen las celdas son de hecho hiperparalelepípedos isotéticos, pues los segmentos en N`1son siempre paralelos a los ejes de coordenadas. Consideraremos que C(N`1)está compuesto por los hiperparalelepípedos isotéticos de dimensión 2 resultantes del mallado que N`1produce en RB, así como por los hiperparalelepípedos isotéticos de dimensión 1 (segmentos) resultantes de dicho mallado que no están contenidos en los hiperparalelepípedos de dimensión 2 anteriores, de forma que SC∈C(N`1)=RB\int(B). En la Figura 2.11 se muestra un ejemplo de una red de construcción rectangular N`1en R2. Figura 2.11: Red de construcción rectangular N`1de X,YyB=B1∪B2en R2. Los hiperparalelepípedos de dimensión 2 de C(N`1)se aprecian claramente, mientras que los de dimenión 1 se han señalado como líneas de mayor grosor (hay tres). Vamos a ver ahora cómo podemos realizar un mallado de RBen Rncon n≥3. Sea Bun paralelepípedo cualquiera en Rnde centro κ= (κ1, ..., κn)ty mitad de la anchura en cada coordenada OXkigual a ξk,k= 1, ..., n. Las caras de dimensión n−1de B son los hiperparalelepípedos de dimensión n−1dados por {(z1, ..., κj+sξj, ..., zn)t∈ Rn:κi−ξi≤zi≤κi+ξi, i = 1, ..., n, i 6=j}con j∈ {1, ..., n}ys∈ {−1,1}, y su número es, por tanto, 2n. Consideremos los hiperplanos Hparalelos a los hiperplanos OX1· · · Xj−1Xj+1 · · · Xn,j= 1, ..., n, y que cortan a Búnicamente en su frontera. Cada uno de estos hiperplanos contiene una cara de dimensión n−1de B, el hiperplano Hdado por Xj=κj+sξjcon s∈ {−1,1}contiene al hiperparalelepípedo {(z1, ..., κj+sξj, ..., zn)t∈Rn:κi−ξi≤zi≤κi+ξi, i = 1, ..., n, i 6=j}de dimensión n−1,j= 1, ..., n, luego su número es también 2n. En cuanto a lo planos Πparaleleos a los planos OXiXj,i, j = 1, ..., n,i<j, y que cortan a Búnicamente 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 31 en su frontera, su número es n(n−1)2n−3: el número de planos OXiXj,i, j = 1, ..., n, i < j, es n 2, o lo que es los mismo, n(n−1)/2; para cada plano OXiXj, las posibilidades de colocarlo en la frontera de Bson 2n−2, esto es, el número de posibilidades de combinar los valores extremos κk+sξk,s∈ {−1,1}, en las coordenadas restantes OXk,k= 1, ..., n,k6=i, j. Así, n 22n−2=n(n−1)2n−3es también el número de caras (paralelepípedos) de dimensión 2 de B. Volvamos a nuestro conjunto de complejos barreras {B1, ..., BN}y tomemos dos paralelepípedos Bj i,Bh kcualesquiera (que pueden pertenecer al mismo complejo o incluso ser iguales), i, k ∈ {1, ..., N},j∈ {1, ..., mi},h∈ {1, ..., mk}. Sea Hun hiperplano de los anteriores para Bj ital que la cara de dimensión n−1que contiene de Bj ino está completamente contenida en el interior de Bi, y sea Πun plano de los descritos antes para Bh kque cumple también que la cara de dimensión 2que contiene de Bh kno está completamente contenida en el interior de Bk. Utilizando la fórmula de la dimensión sabemos que la intersección de HyΠpuede ser, o bien, una recta, o bien, el propio Π. Nos interesa sólo las intersecciones de HyΠque dan lugar a rectas r. Tomada la recta r, que es necesariamente paralela a uno de los ejes de coordenadas, nos quedamos con los segmentos {S1, ..., SK}de rque se obtienen al realizar el siguiente procedimiento: en primer lugar, nos quedamos con el segmento S=r∩ RBde r; y, en segundo lugar, tomamos los segmentos maximales {S1, ..., SK}de Stales SK i=1 Si=S\int(B). El número de estos segmentos es finito pues el número de paralelepípedos de cada complejo es finito así como el númeor de caras que poseen. Los segmentos {S1, ..., SK}son las líneas de construcción rectangular producidas por el hiperplano Hy el plano Π. De la misma forma, podemos construir estas líneas considerando también como hiperplanos Hy planos Πa los hiperplanos paralelos a OX1· · · Xj−1Xj+1 · · · Xn,j= 1, ..., n, y a los planos paralelos a OXiXj,i, j = 1, ..., n,i<j, que pasan por los puntos XeY entre los que queremos caluclar dB(X, Y ), así como a las caras de dimensión n−1y 2 de RB. Los segmentos resultantes del proceso al considerar estos planos e hiperplanos son también líneas de construcción rectangular en Rncon n≥3. Obsérvese que, puesto que la cara de dimensión n−1de Bj ique contiene el hiperplano Hno está completamente contenida en el interior de Biy la cara de dimensión 2 de Bh kque contiene el plano Πno está completamente contenida en el interior de Bk, HyΠcontienen, respectivamente, una cara de dimensión n−1de Biy una cara de dimesnión 2de Bk. De hecho, en lo que estamos interesados realmente es en intersecar hiperplanos que contienen caras de dimensión n−1de un complejo con planos que contienen caras de dimensión 2de otro o el mismo complejo. Sin embargo, el procedimiento anterior constituye una forma sencilla de obtener las líneas de construcción rectangular a partir de los paralelepípedos que constituyen los complejos, y no a partir de estos últimos directamente. Definición 2.8. En Rncon n≥3, la red de construcción rectangular N`1de X,YyB es la formada por la unión de las líneas de construcción rectangular descritas en los párrafos anteriores formadas entre todos los pares posibles de hiperplanos Hy planos Πen las condiciones del mismo párrafo. 32 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera Al igual que en R2, los puntos de intersección de los segmentos en N`1definen el conjunto P(N`1)de nodos de la red, y C(N`1)es el conjunto de celdas resultantes en RB\int(B). Los poliedros que constituyen las celdas de C(N`1)son ahora hiperparalelepípedos isotéticos de dimensión non−1. Para ver esta última afirmación tenemos que mostrar que dado un punto Z∈ P(N`1)existe un segmento que parte de Zen todas las direcciones fundamentales visibles desde Z(esto es, si Zpertece a la cara de dimensión n−1de un paralepípedo que hace de barrera o de RB, no tiene sentido considerar la dirección fundamental que al partir de Zse introduce inmediatamente después de Zen el interior del paralelepípedo o de RB). El punto Zpuede ser un punto extremo de un segmento de N`1o el resultado de la intersección de dos segmentos de N`1. Supongamos que Zes un punto extremo de un segmento de N`1. Sea rla recta a la que pertenece dicho segmento y a partir de la cual se obtienene el mismo. Sean Hy Π, respectivamente, el hiperplano y el plano cuya intersección da lugar a r. Por tanto, Z∈r, H,Π. Supongamos, sin pérdida de generalidad, que OX1es la dirección en la que varía r, que Hes paralelo al hiperplano X2= 0 y que Πes paralelo al plano que varía en las direcciones OX1yOX2siendo constante en el resto. Por la construcción descrita de N`1, el que Zsea un punto extremo de un segmento Sde N`1significa que existe una cara de dimensión n−1de un paralelepípedo de los complejos barreras o de RBque impide que el segmento Sse prolongue por Zen la dirección OX1. Sea H0 el hiperplano que contiene a dicha cara, el cual será paralelo al hiperplano X1= 0. Se tiene, por tanto, Z∈ H0. Por último consideremos una cara de dimensión n−1que contiene a la cara de dimensión 2del paralelepípedo o de RBque da lugar al plano Π, en caso de que Πtenga algunos de estos orígenes. Sea H00 el hiperplano que la contiene, el cual es paralelo al hiperplano Xj= 0 con j6= 1,2. Si Πes un plano que pasa por XoY, entonces igualmente tomamos un hiperplano H00 que pase por XoYy que contenga a Π. También en este caso H00 es paralelo al hiperplano Xj= 0 con j6= 1,2. Como Z∈Πse tiene Z∈ H00. Por último, observemos que H,H0yH00 son todos hiperplanos que intervienen en la construcción de N`1(contienen a caras de dimensión n−1de paralelepípedos no contenidas completamente en el interior del complejo correspondiente, o de RB, o pasan por XoY), por tanto, dado cualquier sentido para una dirección OXk, nótese que siempre puede tomarse uno de estos hiperplanos y un plano contenido en otro de los hiperplanos que pase por Z(plano que interviene también en la construcción de N`1) cuya intersección dé lugar a un segmento de N`1que pasa por Zy continúa en el sentido dado de OXksi esto es posible. Si Zes el resultado de la intersección de dos segmentos de N`1se razona de la misma forma. Las celdas de dimensión n−1de C(N`1)son las contenidas en las caras de dimensión n−1de RBy se deben, en el caso de que ocurran, a las intersecciones de las fronteras de los complejos con la frontera de RB. Analicemos cuál es el coste computacional de la construcción de N`1. La red de construcción rectangular N`1es una red geométrica determinada por sus nodos P(N`1) y los segmentos (con su longitud correspondiente) que los unen, por tanto, determinados estos tenemos aquella. Comencemos por el caso bidimensional. Sea Σel número 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 33 de puntos en {X, Y }∪P(B), siendo P(B)el conjunto finito de puntos extremos de B, y sea W=PN i=1 miel número total de paralelepípedos que forman los complejos barrera de B. En primer lugar tenemos que obtener RBcon un coste de O(W2). Dado un punto de {X, Y }∪P(B)tenemos que considerar las cuatro líneas de construcción rectangular que parten de él. Para saber hasta dónde se extienden dichas líneas debemos detectar si intersecan el interior de los paralelepípedos que constituyen los complejos barrera, así como si intersecan alguna de las caras de dimensión 1 de RB. Las comprobación de intersección con el interior de un paralelepípedo así como con una cara de dimensión 1 de RBse realiza en tiempo constante. Las líneas de construcción se obtienen, por tanto, en un tiempo de O(4Σ)O(W+ 4) = O(ΣW). El número de líneas de construcción está acotado por O(Σ). Para obtener los puntos P(N`1)y dividir las líneas de construcción en segmentos debemos comprobar las intersecciones entre líneas de construcción, lo que tiene un coste O(Σ2). Para obtener la longitud de los segmentos, tomamos cada línea de construcción y la recorremos calculando la distancia entre nodos adyacentes en dicha línea, como el número de nodos en una línea de construcción es a lo sumo O(Σ), las longitudes de los segmentos se hallan en un tiempo O(Σ2). Luego N`1se obtiene en O(m´ax{W2,Σ2}). Puesto que si los complejos están adecuademente descritos por sus paralelepípedos W < Σ,N`1se tiene en un tiempo O(Σ2). En Rncon n≥3, el paso inicial del cálculo de RBconlleva un tiempo O(W2n). La interseccion de todos los hiperplanos Hcon los planos Πpara obtener las rectas rtiene un coste O(W2n42n−3)(véase la discusión sobre el número de caras de dimensión n−1 y2de un paralelepípedo en Rnen los párrafos precedentes, y considérese que la intersección de un hiperplano y un plano en Rnrequiere un número O(n)de operaciones). La división en segmentos de cada recta rrequiere comprobar la intersección de ésta con el interior de todos los paralelepípedos que constituyen los complejos, cada una de estas comprobaciones se realiza en O(n), luego la división de todas las rectas ren segmento tiene un coste O(W3n52n−3). Por ese mismo coste calculamos las longitudes de los segmentos. Para obtener los puntos P(N`1)debemos comprobar las intersecciones (cada comprobación de intersección requiere O(n)operaciones) entre los segmentos anteriores, lo que tiene un coste O(W6n1122n−6). Si dos segmentos intersecan en un punto estos deben dividirse en nuevos segmentos cuyas longitudes deben ser calculadas (para que esto se entienda, al intersecar [(1,0)t,(1,2)t]con [(0,1)t,(2,1)t], debemos calcular la longitud de los segmentos [(1,0)t,(1,1)t],[(1,1)t,(1,2)t],[(0,1)t,(1,1)t] y[(1,1)t,(2,1)t], pues (1,1)tes un nuevo nodo), pero este cálculo puede realizarse en tiempo constante en el mismo momento en el que se obtiene los puntos P(N`1). Por tanto, la obtención de N`1en Rncon n≥3tiene un coste O(W6n1122n−6). Teorema 2.1. El Problema 2.1 es equivalente al problema de hallar el camino mínimo entre XeYen la red geométrica N`1. Demostración. En primer lugar, obsérvese que efectivamente Xes es un nodo de N`1, el cual se obtiene por la intersección sucesiva entre los hiperplanos Hparalelos a los 40 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera j= 1, ..., n, es equivalente al problema de programación lineal y entera mixta m´ın d(2.6) s.a: d≥d0−(1 −ω0)M2,(2.7) d≥dkrs −(1 −ωkrs)M2,∀k= 1, ..., n, r = 1, ..., n, r 6=k, s =−1,1,(2.8) ω0+X k= 1, ..., n, r = 1, ..., n, r6=k, s =−1,1 ωkrs = 1,(2.9) u+ jk −u− jk =xj k−κk,∀j= 1,2, k = 1, ..., n, (2.10) u+ jk ≤Mδjk,∀j= 1,2, k = 1, ..., n, (2.11) u− jk ≤M(1 −δjk),∀j= 1,2, k = 1, ..., n, (2.12) dc jk =u+ jk +u− jk,∀j= 1,2, k = 1, ..., n, (2.13) d0 k≥x1 k−x2 k,∀k= 1, ..., n, (2.14) d0 k≥x2 k−x1 k,∀k= 1, ..., n, (2.15) dζ jks ≥xj k−(κk+sξk),∀j= 1,2, k = 1, ..., n, s =−1,1,(2.16) dζ jks ≥(κk+sξk)−xj k,∀j= 1,2, k = 1, ..., n, s =−1,1,(2.17) dc jk ≥ξk−ξkλ1 jk,∀j= 1,2, k = 1, ..., n, (2.18) X h=1,...,n,h6=k λ1 jh ≤(n−2) + λ2 jk,∀j= 1,2, k = 1, ..., n, (2.19) λ2 1k+λ2 2k≤1+Λk,∀k= 1, ..., n, (2.20) −∆k≤δ1k−δ2k≤∆k,∀k= 1, ..., n, (2.21) Λk+ ∆k≤1+Ωk,∀k= 1, ..., n, (2.22) d0=X k=1,...,n d0 k+MX h=1,...,n Ωh,(2.23) dkrs =dζ 1rs +dζ 2rs +X h=1,...,n,h6=r d0 h+MX t=1,...,n,t6=k Ωt, ∀k= 1, ..., n, r= 1, ..., n, r6=k, s=−1,1, (2.24) d, d0≥0,(2.25) d0 k≥0,∀k= 1, ..., n, (2.26) dkrs ≥0, ωkrs ∈ {0,1},∀k= 1, ..., n, r = 1, ..., n, r 6=k, s =−1,1,(2.27) u+ jk, u− jk, dc jk ≥0, λ1 jk, λ2 jk, δjk ∈ {0,1},∀j= 1,2, k = 1, ..., n, (2.28) dζ jks ≥0,∀j= 1,2, k = 1, ..., n, s =−1,1,(2.29) Λk,∆k,Ωk∈ {0,1},∀k= 1, ..., n, (2.30) siendo M > 0una constante lo suficientemente grande. Demostración. En (2.25)-(2.30) se define la naturaleza de las variables de decisión: d es una variable positiva que en el óptimo tomará el valor dB(X1, X2);d0 1, ..., d0 nson 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 41 también variables positivas que en el óptimo tomarán los valores |x1 1−x2 1|, ..., |x1 n−x2 n|, respectivamente, si estos valores son necesarios para el cálculo de dB(X1, X2); la variable dkrs representa el valor de la distancia dB(X1, X2)en el caso de que X1 yX2no sean `1-visibles debido a que Proyˆ k(X1),Proyˆ k(X2)∈int(Proyˆ k(B)) y m´ın{x1 k, x2 k}< κk<m´ax{x1 k, x2 k}, y el menor X1-X2camino rectangular permitido sea el de longitud Pi=1,...,n,i6=r|x1 i−x2 i|+|x1 r−(κr+sξr)|+|x2 r−(κr+sξr)|, mientras que ωkrs es una variable binaria que tomará el valor 1si efectivamente X1y X2se encuentran en ese caso y 0en caso contrario; u+ jk,u− jk ydc jk tomarán, respectivamente, los valores |xj k−κk|si xj k≥κko0en caso contario, |xj k−κk|si xj k≤κko0 en caso contario, y |xj k−κk|; las variables dζ jks son variables positivas que representan los valores |xj k−(κk+sξk)|necesarios para el cálculo de dB(X1, X2)en los diferentes casos; λ1 jk,λ2 jk yΛkson variables binarias que determinarán la posición relativa de las coordenadas de X1yX2con respecto a las proyecciones en Proyˆ k(·)de B;δjk y∆k son variables binarias que determinarán la posición relativa de x1 kyx2 kcon respecto al centro de B; las variables binarias Ωkdetectan si X1yX2son `1-visibles o no. Las restricciones (2.10), (2.11) y (2.12) hacen que u+ jk tome el valor |xj k−κk|si xj k> κk, en cuyo caso δjk = 1, y que u− jk tome el valor |xj k−κk|si xj k< κk, en cuyo caso δjk = 0. Por tanto, con (2.13) se consigue que dc jk tome el valor |xj k−κk|. En (2.14)-(2.15) se impone que d0 k≥ |x1 k−x2 k|. Las restricciones (2.16) y (2.17) obligan a dζ jks a tomar valores mayores o iguales que |xj k−(κk+sξk)|. La restricción (2.18) hace que la variable binaria λ1 jk tome el valor 1si dc jk < ξj, pudiendo tomar el valor 0o1en caso contrario. Por la tanto, la restricción (2.19) hace que la variable binaria λ2 jk tome el valor 1si Proyˆ k(Xj)∈int(Proyˆ k(B)), pudiendo tomar el valor 0o1en caso contrario. La restricción (2.20) fuerza a que Λktoma el valor 1 si tanto Proyˆ k(X1)como Proyˆ k(X2)pertenecen a int(Proyˆ k(B)), pudiendo tomar el valor 0o1en caso contrario. Obsérvese que si m´ın{x1 k, x2 k}< κk<m´ax{x1 k, x2 k}, entonces δ1k−δ2kes 1o−1, en caso contrario δ1k−δ2k= 0 (pudiendo ser 1si se da alguna de las igualdades en m´ın{x1 k, x2 k} ≤ κk≤m´ax{x1 k, x2 k}), luego (2.21) obliga a que ∆k= 1 si m´ın{x1 k, x2 k}< κk<m´ax{x1 k, x2 k}, pudiendo tomar el valor 0o1en caso contario. Teniendo en cuenta lo anterior, por (2.22), Ωk= 1 si Proyˆ k(X1),Proyˆ k(X2)∈int(Proyˆ k(B)) ym´ın{x1 k, x2 k}< κk<m´ax{x1 k, x2 k}, cosa que sabemos sólo puede darse en todo caso para un k∈ {1, ..., n}, en caso contrario Ωkpuede tomar el valor 1o0. En (2.23)-(2.24) se calcula dB(X1, X2) según la situación en la que X1yX2se encuentren de acuerdo al Lema 2.9. En 2.23, a d0(que representa la distancia `1(X1, X2)) se le aplica una penalización si X1yX2no son `1-visibles (esto es, si Ωk= 1 para algún k∈ {1, ..., n}). Las distancias dkrs también son penalizadas si Ωj= 1 para algún j∈ {1, ..., n}con j6=k(es decir, si Proyˆ j(X1),Proyˆ j(X2)∈int(Proyˆ j(B)) ym´ın{x1 j, x2 j}< κj< m´ax{x1 j, x2 j}). El problema de programación matemática tiene estructura de problema minimín debido a (2.6)-(2.9), que hacen que se calcule dB(X1, X2)de la forma adecuada según el caso: si X1yX2son `1-visibles entonces d0es la menor de las dis- 42 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera tancias que se puede seleccionar; si se da Proyˆ k(X1),Proyˆ k(X2)∈int(Proyˆ k(B)) ym´ın{x1 k, x2 k}< κk<m´ax{x1 k, x2 k}, entonces d0ydjrs con j6=kson penalizadas, se escogerá entonces entre las distancias dkrs, cumpliéndose en el óptimo d= m´ınr=1,....,n,r6=k,s=−1,1{dkrs}=dB(X1, X2). Es necesario en (2.7) y (2.8) que Mesté elevada al cuadrado para que no pueda anularse con las penalizaciones que se aplican a d0y a cada dkrs en (2.23) y (2.24). Como se ha dicho, en (2.14)-(2.15) se impone que d0 k≥ |x1 k−x2 k|y en (2.16)-(2.17) que dζ jks ≥ |xj k−(κk+sξk)|, dado que en (2.6) se está minimizando d, en la solución óptima del problema se da la igualdad para las variables que representen distancias necesarias para el cálculo de la longitud del camino rectangular permitido óptimo. Todas las variables binarias cuyo valor no quedaba fijado en determinadas situaciones, pudiendo tomar los valores 0o1, tomarán el valor 0en dichas circustancias, de lo contrario se aplicarían penalizaciones en (2.23)-(2.24) que aumentarían el valor de la función objetivo innecesariamente. En el Teorema 2.2, una elección válida para Mes nm´axi=1,...,n{2ξ0 i}+ε, siendo ξ0 ila mitad de la anchura en la coordenada OXide la envolvente rectangular iterativa RB de X,YyB, y εcualquier constante estrictamente positiva. Muchas de las variables de (2.6)-(2.30) (d0,d0 k,dc jk,dζ jks,...) representan valores que, de hecho, podemos obtener antes de plantear el problema de programación matemática, puesto que estamos suponiendo que X1yX2son fijos, de esta forma se reduciría el número de variables binarias usadas en la formulación (δjk, los valores λ1 jk yλ2 jk se podrían saber de antemano,...), sin embargo, la formulación (2.6)-(2.30) es una formulación general para cualquier par de puntos X1yX2de la región factible, que pueden suponerse no fijos, lo que permite integrarla en formulaciones para problemas más generales que requieran resolver el problema al que (2.6)-(2.30) da solución como subproblema. Las formulaciones que aparecerán en el resto del capítulo están dadas de forma que pueda suponerse que los puntos X1yX2no son fijos, lo que permitirá usarlas para resolver los problemas que se plantearán en los siguientes capítulos. Aún así, el número de variables binarias empleadas en la formulación (2.6)-(2.30) puede reducirse como muestra el siguiente lema. Lema 2.10. El problema de programación matemática (2.6)-(2.30) es equivalente al problema resultante de hacer en éste los siguientes cambios: considerar las variables de decisión ∆k,k= 1, ..., n, en (2.30) como variables positivas en lugar de variables binarias y sustituir la restricción (2.21) por las restricciones: ∆k≤1,∀k= 1,2,(2.31) ∆k≥δ1k−δ2k,∀k= 1, ..., n, (2.32) ∆k≥δ2k−δ1k,∀k= 1, ..., n. (2.33) Demostración. La variable ∆kse comporte de la siguiente forma: si m´ın{x1 k, x2 k}< κk<m´ax{x1 k, x2 k}, entonces δ1k−δ2kes 1o−1, obligando a ∆ka tomar el valor 1 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 43 por las restricciones (2.31)-(2.33); si δ1k−δ2k= 0 yΛk= 1,∆kpuede tomar todos los valores del intervalo [0,1], sin embargo, si ∆ktomase un valor estrictamente mayor que cero, la restricción (2.22) activaría la variable binaria Ωk, con lo que se produciría un aumento del valor de la función objetivo (2.6) debido a penalizaciones innecesarias producidas por las restricciones (2.23)-(2.24), luego en este caso ∆ktomará el valor 0; por último, si δ1k−δ2k= 0 yΛk= 0, el valor que tome ∆kno influye en el valor de la función objetivo (2.6). Por tanto, este cambio no afecta a la solución óptima que proporciona el problema de programación matemática (2.6)-(2.30). Conseguida una formulación para el Problema 2.1 cuando B=Bes un único paralelepípedo en Rn, pasemos a estudiar el caso en el que B=B1∪B2, siendo B1yB2dos hiperparalelepípedos de dimensión ndisjuntos de centros (κ2 1, ..., κ1 n)ty(κ2 1, ..., κ2 n)t, y mitad de la anchura en cada coordenada ξ1 jyξ2 j,j= 1, ..., n, respectivamente. Bajo las condiciones que indica el siguiente lema, la formulación (2.6)-(2.30) es suficiente para resolver este caso particular del Problema 2.1. Lema 2.11. Si Proyˆ k(B1)∩Proyˆ k(B2) = ∅,∀k= 1, ..., n, entonces dB(X, Y ) = m´ax{dB1(X, Y ), dB2(X, Y )}. Demostración. Dado que la reducción de la región factible sólo puede provocar un aumento de la distancia con barreras y no al contrario, es evidente que dB(X, Y )≥ dB1(X, Y ), dB2(X, Y ). Si XeYson `1-visibles entonces el resultado se tiene de forma trivial ya que dB(X, Y ) = dB1(X, Y ) = dB2(X, Y ) = `1(X, Y ). Supongamos que XeYno son `1-visibles. Entonces, debe darse para algún j∈ {1, ..., n}, o bien, Proyˆ j(X),Proyˆ j(Y)∈int(Proyˆ j(B1)) ym´ın{xj, yj}< κ1 j<m´ax{xj, yj}, o bien, Proyˆ j(X),Proyˆ j(Y)∈int(Proyˆ j(B2)) ym´ın{xj, yj}< κ2 j<m´ax{xj, yj}, o ambas situaciones, ya que de lo contrario, razonando como en la demostración del Lema 2.9, podríamos construir un X-Ycamino rectangular permitido de longitud `1(X, Y ), lo que contradice la suposición de que XeYno son `1-visibles. Supongamos que se tiene Proyˆ j(X),Proyˆ j(Y)∈int(Proyˆ j(B1)) ym´ın{xj, yj}< κ1 j<m´ax{xj, yj}. Consideremos el X-Ycamino rectangular Q1de la forma (2.5) y de longitud mínima cuando sólo se considera a B1como barrera obviando B2. Como Proyˆ k(B1)∩ Proyˆ k(B2) = ∅,∀k= 1, ..., n, obsérvese que ninguno de los segmentos que constituyen Q1puede ser intersecados por el interior de B2, luego Q1es un X-Yca- mino rectangular permitido de longitud dB1(X, Y ). Si se tiene Proyˆ k(X),Proyˆ k(Y)∈ int(Proyˆ j(B2)) ym´ın{xj, yj}< κ2 j<m´ax{xj, yj}para algún k∈ {1, ..., n}, siguiendo el razonamiento que acabamos de hacer para el paralelepípedo B1, obtendríamos un X-Ycamino rectangular permitido Q2de longitud dB2(X, Y ). En caso contrario dB1(X, Y )≥dB2(X, Y ) = `1(X, Y ). Concluimos así que dB(X, Y ) = m´ax{dB1(X, Y ), dB2(X, Y )}. En las condiciones del Lema 2.11, la estrategia de resolución del problema que nos ocupa es sencillamente la seguiente: calcular dB1(X, Y )ydB2(X, Y )independientemente resolviendo sendos problemas de programación matemática (2.6)-(2.30), y 44 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera tomar el X-Ycamino rectangular solución de estos problemas de mayor longitud. La comprobación de si Proyˆ k(B1)∩Proyˆ k(B2) = ∅para algún k∈ {1, ..., n}puede hacerse en tiempo O(n)comparando los pares de intervalos [κ1 j−ξ1 j, κ1 j+ξ1 j], [κ2 j−ξ2 j, κ2 j+ξ2 j],j= 1, ..., n. Nótese, que si B=SN i=1 Bi, siendo {B1, ..., BN} un conjunto de hiperparalelepípedos de dimensión ndisjuntos dos a dos tales que Proyˆ k(Bi)∩Proyˆ k(Bj) = ∅,∀k= 1, ..., n,∀i, j = 1, ..., N con i6=j, el Lema 2.11 puede extenderse a este caso y la estrategia anterior de calcular todos las distancias dBi(X, Y ),i= 1, ..., N, y quedarnos con la mayor, seguiría siendo válida. Si no se da Proyˆ k(B1)∩Proyˆ k(B2) = ∅,∀k= 1, ..., n, entonces Proyˆ j(B1)∩ Proyˆ j(B2)6=∅, para un único j∈ {1, ..., n}, pues los paralelepípedos son isotéticos. Sean V1=κ1 j+hξ1 jyV2=κ2 j+iξ2 jcon h, i ∈ {−1,1}tales que |V1−V2|es mínimo, es decir, las coordenadas en OXjde las caras de dimensión n−1de B1yB2, respectivamente, más cercanas entre sí. La coordenada j-ésima tal que Proyˆ j(B1)∩ Proyˆ j(B2)6=∅así como los valores V1yV2pueden obtenerse en tiempo O(n), pues- to que la primera se obtiene en O(n)y los segundos mediante un número constante de comparaciones una vez obtenida la anterior. Supongamos sin pérdida de generalidad que V1< V 2. Obsérvese que la región R(V1, V 2) := {Z∈Rn:V1≤zj≤V2} separa a los paralelepípedos B1yB2en el siguiente sentido: la cara de dimensión n−1 de B1en la que la coordenada OXjes constante e igual a V1pertenece a la frontera de R(V1, V 2), así como la cara de dimensión n−1de B2en la que coordenada OXj es constante e igual a V2, no existiendo puntos de B1ni B2en int(R(V1, V 2)). Entonces, no es difícil ver (para ello basta considerar argumentos simples basados en la envolvente rectangular iterativa como los utilizados en pruebas anteriores) que se tiene la siguiente casuística (utilizamos de nuevo la notación X1=XyX2=Y): (a) Si V1≤x1 j, x2 j≤V2entonces dB1∪B2(X1, X2) = `1(X1, X2). (b) Si x1 j, x2 j≤V2entonces dB1∪B2(X1, X2) = dB1(X1, X2). (c) Si x1 j, x2 j≥V1entonces dB1∪B2(X1, X2) = dB2(X1, X2). (d) Si x1 j≤V1yx2 j≥V2entonces existe ρ∈Rncon V1≤ρk≤V2tal que dB1∪B2(X1, X2) = dB1(X1, ρ) + dB2(ρ, X2). (e) Si x2 j≤V1yx1 j≥V2entonces existe ρ∈Rncon V1≤ρk≤V2tal que dB1∪B2(X1, X2) = dB1(X2, ρ) + dB2(ρ, X1). Las Figuras 2.12, 2.13, 2.14 y 2.15 ilustran esta casuística en R2cuando Proyˆ 1(B1)∩ Proyˆ 1(B2)6=∅. 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 45 Figura 2.12: Caso (a). Figura 2.13: Caso (b). Figura 2.14: Caso (c). 46 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera Figura 2.15: Caso (d) (el caso (e) es similar). Si w1 1es una variable de decisión binaria, la restricción V1−M(1 −w1 1)≤x1 j≤V1+Mw1 1, siendo M > 0una constante los suficientemente grande, hace que w1 1= 0 si x1 j< V 1, w1 1= 1 si x1 j> V 1, mientras que si x1 j=V1entonces w1 1puede tomar el valor 0o 1. Por tanto, las posiciones relativas de la coordenada j-ésima de los puntos X1yX2 con respecto a V1yV2, las cuales nos permiten detectar en que caso de la casuística anterior se encuentran los puntos X1yX2, pueden determinarse mediante el conjunto de restricciones: V1−M(1 −wi 1)≤xi j≤V1+Mwi 1,∀i= 1,2,(2.34) V2−M(1 −wi 2)≤xi j≤V2+Mwi 2,∀i= 1,2,(2.35) wi h∈ {0,1},∀i= 1,2, h = 1,2.(2.36) En la casuística (a)-(e), podemos considerar sólamente los casos (b), (c), (d) y (e), pues el caso (a) está contemplado tanto en (b) como en (c). Es decir, si se da (a), entonces: (a) ⇒(b) ⇒dB1∪B2(X1, X2) = dB1(X1, X2) = `1(X1, X2), (a) ⇒(c) ⇒dB1∪B2(X1, X2) = dB2(X1, X2) = `1(X1, X2). Además, obsérvese que los casos (d) y (e) son excluyentes pues estamos suponiendo V1< V 2. Si φ1,φ2,φ3yφ4son variables binarias que representan, respectivamente, la ocurrencia de los casos (b), (c), (d) y (e), cuando toman el valor el 1, entonces, a partir de las posiciones relativas de x1 jyx2 jcon respecto a V1yV2detectadas por las variables binarias wi h,i= 1,2, h = 1,2, podemos determinar en cuál de los casos nos 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 47 encontramos mediante las restricciones: 4 X k=1 φk= 1,(2.37) φ1≤(1 −w1 2) + (1 −w2 2),(2.38) φ2≤w1 1+w2 1,(2.39) φ3≥w2 2−w1 1,(2.40) φ4≥w1 2−w2 1,(2.41) φk∈ {0,1},∀k= 1, ..., 4.(2.42) La restricción (2.37) fuerza a que se seleccione uno y sólo uno de los casos. La restricción (2.38) indica que si x1 j, x2 j> V 2entonces no puede darse el caso (b), de la misma forma, la restricción (2.39) indica que si x1 j, x2 j< V 1entonces no puede darse el caso (c). Si x1 j< V 1yx2 j> V 2entonces necesariamente φ3= 1 (restricción (2.40)) y si x2 j< V 1yx1 j> V 2entonces necesariamente φ4= 1 (restricción (2.41)). Cuando estas restricciones se integren al modelo correspondiente, el cuál estará minimizando dB1∪B2(X1, X2)en la función objetivo, siempre se intentará que φ1= 1 oφ2= 1, pues dB1∪B2(X1, X2)es menor en los casos (b) y (c) que en los casos (d) y (e). Si se da el caso (d) o (e) (sólo puede darse uno de ellos) entonces necesariamente φ3= 1 o φ4= 1, no pudiendo hacerse φ1= 1 oφ2= 1. Luego, las restricciones (2.37)-(2.42) detectan adecuadamente el caso en el que se encuentran los puntos X1yX2. Puede comprobarse que, en los casos extremos en los que los wi hpueden tomar los valores 0o1, las restricciones (2.37)-(2.42) siguen detectando adecuadamente el caso de la casuística (b)-(e) en el que se encuentran los puntos X1yX2, pues en dichos casos extremos podemos encontrarnos en diferentes casos de la casuística (b)-(e) a la vez. Sean %1, %2, %3∈Rn. La distancia dB1(%1, %2)puede calcularse adaptando la formulación (2.6)-(2.30) a los puntos %1,%2y a la barrera B1. Para ello, basta sustituir en (2.6)-(2.30) los papeles de X1yX2por los de %1y%2, y el de Bpor B1. Llamemos d12 a la variable positiva que habría que minimizar en la función objetivo del problema de programación matemática resultante (la que en (2.6)-(2.30) era simplemente d). De la misma forma, la distancia dB2(%2, %3)puede calcularse adaptando la formulación (2.6)-(2.30) a los puntos %2,%3y a la barrera B2. Llamemos ahora d23 a la variable positiva que habría que minimizar en la función objetivo del nuevo problema de programación matemática resultante. Consideremos el siguiente problema de programación matemática: m´ın d12 +d23 s.a: (2.6)-(2.30), adaptadas para el cálculo de dB1(%1, %2),(2.43) (2.6)-(2.30), adaptadas para el cálculo de dB2(%2, %3).(2.44) Por lo dicho antes está claro que este problema de programación matemática calcula dB1(%1, %2) + dB2(%2, %3). Vamos a aclarar en qué sentido podemos apoyarnos en 48 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera esta formulación para resolver nuestro problema. Obsérvese que si estamos en el caso (b) de nuestra casuística entonces dB1(%1, %2) + dB2(%2, %3)es dB1∪B2(X1, X2) = dB1(X1, X2)si %1=X1,%2=X2y%3=X2. Si estamos en el caso (c) entonces dB1(%1, %2) + dB2(%2, %3)es dB1∪B2(X1, X2) = dB2(X2, X2)si %1=X1,%2=X1 y%3=X2. En el caso de encontrarnos en el caso (d), dB1(%1, %2) + dB2(%2, %3)es dB1∪B2(X1, X2) = dB1(X1, ρ) + dB2(ρ, X2)si %1=X1,%2=ρy%3=X2, siendo ρ∈R(V1, V 2). Por último, en el caso de encontrarnos en el caso (e), dB1(%1, %2) + dB2(%2, %3)es dB1∪B2(X1, X2) = dB1(X2, ρ) + dB2(ρ, X1)si %1=X2,%2=ρy %3=X1, siendo ρ∈R(V1, V 2). Luego, si conseguimos fijar adecuadamente los valores de %1,%2y%3según el caso, tendríamos la formulación de un problema de programación matemática que equivaldría a nuestro problema. Si ρ∈R(V1, V 2), utilizando las variables de decisión binarias φk,k= 1, ..., 4, que indicaban el caso en el que nos encontrábamos (y de las cuales sólo una podía tomar el valor 1), los valores de %1,%2y%3pueden fijarse mediante las restricciones x1 k−M(1 −φ1)≤%1k≤x1 k+M(1 −φ1), k = 1, ..., n, (2.45) x2 k−M(1 −φ1)≤%2k≤x2 k+M(1 −φ1), k = 1, ..., n, (2.46) x2 k−M(1 −φ1)≤%3k≤x2 k+M(1 −φ1), k = 1, ..., n, (2.47) x1 k−M(1 −φ2)≤%1k≤x1 k+M(1 −φ2), k = 1, ..., n, (2.48) x1 k−M(1 −φ2)≤%2k≤x1 k+M(1 −φ2), k = 1, ..., n, (2.49) x2 k−M(1 −φ2)≤%3k≤x2 k+M(1 −φ2), k = 1, ..., n, (2.50) x1 k−M(1 −φ3)≤%1k≤x1 k+M(1 −φ3), k = 1, ..., n, (2.51) ρk−M(1 −φ3)≤%2k≤ρk+M(1 −φ3), k = 1, ..., n, (2.52) x2 k−M(1 −φ3)≤%3k≤x2 k+M(1 −φ3), k = 1, ..., n, (2.53) x2 k−M(1 −φ4)≤%1k≤x2 k+M(1 −φ4), k = 1, ..., n, (2.54) ρk−M(1 −φ4)≤%2k≤ρk+M(1 −φ4), k = 1, ..., n, (2.55) x1 k−M(1 −φ4)≤%3k≤x1 k+M(1 −φ4), k = 1, ..., n, (2.56) donde %ik representa la k-ésima coordenada de %iyρkla k-ésima coordenada de ρ. Teniendo en cuenta la discusión anterior, una formulación para resolver el problema del camino rectangular mínimo entre X1yX2en presencia de dos paralelepípedos barrera disjuntos cuyas proyecciones Proyˆ j(·)intersecan para algún j∈ {1, ..., n}, es la que recoge el siguiente teorema. Teorema 2.3. El Problema 2.1 cuando B=B1∪B2, siendo B1yB2dos hiperparalelepípedos de dimensión ndisjuntos tales que Proyˆ j(B1)∩Proyˆ j(B2)6=∅con j∈ {1, ..., n}, y etiquetados de forma que V1< V 2siendo V1=κ1 j+hξ1 jy V2=κ2 j+iξ2 jcon h, i ∈ {−1,1}tales que |V1−V2|es mínimo, es equivalente 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 49 al problema de programación lineal y entera mixta m´ın d12 +d23 (2.57) s.a: (2.34)-(2.56),(2.58) V1≤ρj≤V2,(2.59) ρk∈R,∀k= 1, ..., n, (2.60) %ik ∈R,∀i= 1,2,3, k = 1, ..., n. (2.61) Demostración. La corrección de esta formulación se sigue de la discusión mantenida en los párrafos precedentes. La constante Mpuede tomarse nuevamente nm´axi=1,...,n{2ξ0 i}+ε, siendo ξ0 ila mitad de la anchura en la coordenada OXide la envolvente rectangular iterativa RBde X,Y yB=B1∪B2, y εcualquier constante estrictamente positiva. Nótese que la separación de B1yB2realizada mediante R(V1, V 2)puede hacerse también en el caso en el que Proyˆ k(B1)∩Proyˆ k(B2) = ∅,∀k= 1, ..., n, para ello tomamos cualquier k∈ {1, ..., n} para el que se cumpla V1=κ1 k+ξ1 k≤V2=κ2 k−ξ2 koV2=κ2 k+ξ2 k≤V1=κ1 k−ξ1 k. Este kexiste, de lo contrario B1yB2no serían disjuntos, y puede obtenerse en tiempo O(n). Por lo tanto, la formulación (2.57)-(2.61) es válida para resolver el problema del camino rectangular mínimo entre dos puntos en presencia de dos paralelepípedos barrera disjuntos en cualquier tesitura. El Lema 2.10 también puede usarse en esta formulación para dismuir el número de variables binarias, pues la formulación (2.57)- (2.61) contiene (por duplicado) a la formulación (2.6)-(2.30). Como último caso particular del Problema 2.1 antes de abordar el mismo, nos planteamos el problema en el que B=SN i=1 Bisiendo los Bihiperparalelepípedos de dimensión ndisjuntos dos a dos, es decir, consideramos el caso particular del Problema 2.1 cuando cada complejo barrera está formado por un único paralelepípedo. Como ya hemos comentado, si Proyˆ k(Bi)∩Proyˆ k(Bj) = ∅,∀k= 1, ..., n,∀i, j = 1, ..., N con i6=j, el Lema 2.11 puede extenderse a este caso y la estrategia de calcular todas las distancias dBi(X, Y ),i= 1, ..., N, y quedarnos con la mayor, es válida también en este caso. Puesto que la comprobación de la condición Proyˆ k(Bi)∩Proyˆ k(Bj) = ∅, ∀k= 1, ..., n,i6=j, tendría que llevarse a cabo para todos los pares posibles de paralelepípedos, dicha comprobación puede ralizarse en un tiempo O(N2n). No obstante, nuestro objetivo es resolver el problema en cualquier circunstancia, es decir, se cumpla o no la condición anterior. Como se ha podido comprobar al abordar el problema para el caso N= 2, la estrategia de detectar la posición relativa de los puntos XeYcon respecto a los paralelepípedos barrera B1yB2complica considerablemente la formulación del problema de programación matemática que se tenía para el caso N= 1, y hace bastante difícil la adaptación de dicha formulación cuando N≥3. Es por ello que un cambio de estrategia es necesario. En adelante, κi kdenota a la coordenada k-ésima del centro del paralelepípedo Biyξi ka la mitad de la anchura de ese mismo paralelepípedo en la coordenada OXk,i= 1, ..., N,k= 1, ..., n. 56 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera consecuencia pues las variables ωimk sólo aparecen en esta restricción y en las anteriores ((2.81) y (2.83)). Supongamos que (ai)j< κm j<(ai+1)jo(ai+1)j< κm j<(ai)j para algún j∈ {1, ..., n}(de hecho esto sólo puede ocurrir en una coordenada pues la restricción (2.75) fuerza a que aiyai+1 se diferencian a lo sumo en una coordenada), en cuyo caso θimj = 1, y supongamos además que θimk = 0,∀k6=j. En este caso, debe asegurarse, o bien, (ai)r,(ai+1)r≤κm r−ξm r, o bien, (ai)r,(ai+1)r≥κm r+ξm r, para cierto r6=j, o dicho de otra forma, debe asegurarse que dac imr ≥ξm rpara algún r6=j, pues dado que aiyai+1 se diferencian a lo sumo en una coordenada, siendo esta entonces necesariamente la j-ésima ya que (ai)j< κm j<(ai+1)jo(ai+1)j< κm j<(ai)j, dac (i+1)mr ≥ξm rse tendrá por tenerse dac imr ≥ξm r. En esta situación dado que la restricción (2.81) quedaría dac imk ≥ξm kωimk y alguno de los ωimk tomará el valor 1por la restricción (2.82), se tendrá que dac imr ≥ξm rpara algún r, faltaría comprobar que este r es distinto de j, pero esto se tiene por la restricción (2.83) que fuerza a que ωimj = 0, cumpliéndose así la condición 3 del Lema 2.13 para garantizar que los codos a1, ..., a¯ S forman un X1-X2camino rectangular permitido. Como sabemos, las variables θimk toman el valor 1necesariamente si (ai)k< κm k<(ai+1)ko(ai+1)k< κm k<(ai)k, pudiendo tomar valores en el intervalo [0,1] en caso contario, aún así, obsérvese que las restricciones (2.81)-(2.83) funcionan correctamente en el resto de casos no desarrollados, pues valores de las variables θimk que, pudiendo tomar cualquier valor en el intervalo [0,1], hagan demasiado pequeña la cantidad M(1 −Pn h=1 θimh)de la restricción (2.81), producirán un incremento innecesario del valor de la función objetivo. Dado que en la función objetivo (2.62) se está minimizando la suma de las longitudes de los segmentos que constituyen el camino rectangular permitido que une X1yX2, en el óptimo, el camino que determinan los segmentos [a1, a2], ..., [a¯ S−1, a¯ S]es un X1- X2camino rectangular mínimo permitido y la función objetivo (2.62) toma el valor dB(X1, X2). De nuevo, Mpuede tomarse nm´axi=1,...,n{2ξ0 i}+ε, siendo ξ0 ila mitad de la anchura en la coordenada OXide la envolvente rectangular iterativa RBde X,YyB=SN i=1 Bi, yεcualquier constante estrictamente positiva, siempre y cuando en (2.62)-(2.88) no se consideren los paralelepípedos barrera que no estén contenidos en RB. Esto último lo podemos hacer por el Lema 2.7, y además supone una disminución del número de variables binarias que emplea (2.62)-(2.88). Puesto que el número de variables binarias usadas en la formulación (2.62)-(2.88) depende directamente de la cota superior para el número de codos ¯ S, es inmediato ver que cuanto más ajustada sea esta cota, menor será en general el tiempo que necesite el solver que estemos utilizando para encontrar la solución óptima del problema. Si en (2.62)-(2.88) tomamos ¯ Smenor que el número mínimo de codos necesario para formar un X1-X2camino rectangular mínimo permitido, entonces (2.62)-(2.88) devuelve como solución el X1-X2camino rectangular permitido de menor longitud que puede formarse con ese número de codos. Si consideramos el Problema 2.1 general, no el caso particular del Teorema 2.4, y formulamos (2.62)-(2.88) con las paralelepípedos que contituyen los diferentes complejos barrera, 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 57 las condiciones del Lema 2.13 que cumple (2.62)-(2.88), son suficientes para garantizar que la formulación (2.62)-(2.88) resuelve el Problema 2.1. Corolario 2.2. El Problema 2.1 es equivalente al problema de programación matemática (2.62)-(2.88) tomando como paralelepípedos en la formulación los que forman los complejos barreras. Demostración. Basta observar que, puesto que venimos suponiendo que los paralelepípedos {B1 i, ..., Bmi i}que componen un complejo Bi, lo describen correctamente si, para cualquier punto de un paralelepípedo Bj i,j= 1, ..., mi, que pertenezca a la frontera de Bj iy, al mismo tiempo, al interior del complejo Bi, entonces, existe otro paralelepípedo distinto Bh idel mismo complejo tal que dicho punto pertenece a su interior, o lo que es lo mismo, que Smi k=1 int(Bk i) = int(Bi), las condiciones del Lema 2.13 que cumple (2.62)-(2.88) son equivalentes a decir que el X1-X2camino rectangular formado sea un camino rectangular permitido. La formulación (2.62)-(2.88) como método para resolver el Problema 2.1 presenta un inconveniente: la obtención de una cota superior ¯ Spara el número de codos de un X1-X2camino rectangular mínimo permitido no es inmediata. La asunción hecha en el Lema 2.12 de que siempre puede encontrase un X1-X2camino rectangular mínimo permitido tal que una vez que pasa por la frontera de un paralelepípedo barrera, no vuelve a pasar por ella, no es cierta en el caso de los complejos de paralelepípedos. En la Figura 2.16 se muestra un ejemplo en el caso plano dónde todo X1-X2camino rectangular mínimo permitido pasa necesariamente dos veces por la frontera de un complejo barrera y dos veces por la frontera de un mismo paralelepípedo constituyente de dicho complejo. Del Teorema 2.1 se desprende que una cota superior ¯ Spara el número de codos de un X1-X2camino rectangular mínimo permitido necesaria en la formulación (2.62)-(2.88) cuando ésta se utiliza para resolver el Problema 2.1, es el número de nodos del grafo correspondiente a N`1. Sin embargo, la obtención de ese número requiere la construcción de N`1, cuya complejidad sólo hemos podido acotar por O(W6n1122n−6). Es necesario pues explorar una nueva estrategia para resolver el Problema 2.1 en su versión general. 58 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera Figura 2.16: Todo X1-X2camino rectangular mínimo permitido pasa necesariamente dos veces por la frontera de B1y dos veces por la frontera de B1 1. El método para resolver el Problema 2.1 que se va a desarrollar a continuación se basa fundamentealmente en el siguiente resultado. Lema 2.14. Sean C1yC2dos hiperparalelepípedos isotéticos de dimensiones n1, n2∈ {n−1, n}, respectivamente, que intersecan en sus fronteras pero no en sus interiores. Entonces, para todo X∈C1y para todo Y∈C2, existe un X-Ycamino rectangular de longitud `1(X, Y )completamente contenido en C1∪C2. Demostración. Durante toda la prueba supondremos sin pérdida de generalidad n1≥ n2. Denotemos por ˆ ξ1 jyˆ ξ2 j,j= 1, ..., n, a la mitad de la anchura en cada coordenada de C1yC2, y por (ˆκ1 1, ..., ˆκ1 n)ty(ˆκ2 1, ..., ˆκ2 n)ta sus centros, respectivamente. La intersección de C1yC2,C1∩C2, se encuentra necesariamente en una cara ζ1 de C1de dimensión n1−1en la que es constante la coordenada, digamos, OXj, j∈ {1, ..., n}, y en una cara ζ2de C2de dimensión n2−1en la que es constante esa misma coordenada OXj. Esto se tiene porque los paralelepípedos son isotéticos e intersecan en su frontera pero no en su interior. Más aún, C1∩C2es un hiperparalelepípedo de dimensión n2−1, el cual se extiende en OXken el intervalo [fk, gk] = [ˆκ1 k−ˆ ξ1 k,ˆκ1 k+ˆ ξ1 k]∩[ˆκ2 k−ˆ ξ2 k,ˆκ2 k+ˆ ξ2 k},k= 1, ..., n. Es decir, [fk, gk]puede ser [ˆκ1 k−ˆ ξ1 k,ˆκ2 k+ˆ ξ2 k],[ˆκ2 k−ˆ ξ2 k,ˆκ1 k+ˆ ξ1 k],[ˆκ1 k−ˆ ξ1 k,ˆκ1 k+ˆ ξ1 k]o[ˆκ2 k−ˆ ξ2 k,ˆκ2 k+ˆ ξ2 k], k= 1, ..., n. En adelante supondremos ˆκ1 j<ˆκ2 j, por tanto, todos los puntos de C1∩C2 tienen la j-ésima coordenada igual a fj= ˆκ1 j+ˆ ξ1 j= ˆκ2 j−ˆ ξ2 j=gj. Sean X∈C1eY∈C2. Es evidente que para todo punto Z1de C1siem- pre existe un X-Z1camino rectangular de longitud `1(X, Z1)contenido completamente en C1(el camino rectangular en el que en cada codo no trivial se iguala una de las coordenadas de Xa la de Z1correspondiente). Lo mismo ocurre con C2e Y. Supongamos en primer lugar que ζ2⊆ζ1. Entonces consideramos el segmento s= [(y1, ..., yj, ..., yn)t,(y1, ..., fj, ..., yn)t], el cual está contenido en C2, y denotamos Z2= (y1, ..., fj, ..., yn)t. El punto Z2pertenece a C1∩C2, en particular a C1, luego existe un X-Z2camino rectangular QX,Z2de longitud `1(X, Z2)contenido en C1. El 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 59 X-Ycamino rectangular QX,Z2∪ses un X-Ycamino rectangular contenido en C1∪C2 de longitud l(QX,Z3∪s) = l(QX,Z3) + l(s) = n X i=1,i6=j |xi−yi|+|xj−fj|+|fj−yj|, pero xj≤fj≤yj, luego |xj−fj|+|fj−yj|=|xj−yj|, por lo que QX,Z2∪stiene longitud `1(X, Y ). Si ζ1⊆ζ2se razona de la misma forma. Consideremos ahora el caso general en el que no necesariamente ζ2⊆ζ1ni ζ1⊆ζ2. Tomemos C1∩C2y consideremos el paralelepípedo isotético C3dado por el conjunto de puntos {Z2+τej:Z2∈C1∩C2,0≤τ≤2ξ2 j}, siendo ej∈Rn el vector cuya única componente no nula es la j-ésima, siendo ésta igual a 1, es decir, C3es la región barrida cuando se desplaza C1∩C2desde fjhasta ˆκ2 j+ˆ ξ2 j(ver Figura 2.17). Figura 2.17: Paralelepípedos C1,C2yC3en R2. Claramente C3⊆C2. Consideremos que Y /∈C3, pues si Y∈C3el resultado se tiene construyendo el mismo X-Ycamino rectangular que el construido en el caso en el que ζ2⊆ζ1. El punto Ypertenece a C3si y sólo si fi≤yi≤gipara todo i= 1, ..., n con i6=j. Como Y /∈C3, sean i1, ..., imlos índices para los que, o bien, yik< fik, o bien, yik> gik. Sea Qel camino rectangular compuesto por msegmentos que parte de Yy tal que en cada codo se iguala la coordenada yikde yafiksi yik< fiko a giksi yik> gik. Sea Zel punto al que llega este camino. El punto Zpertenece a C3yQes un Y-Zcamino rectangular contenido en C2(y por tanto en C1∪C2) de longitud `1(Y, Z). Como Z∈C3, por el párrafo anterior sabemos que existe un Z-Xcamino rectangular Q0contenido en C1∪C3(y por tanto en C1∪C2) de longitud `1(Z, X), pues C1y C3son dos paralelepípedos isotéticos que intersecan en sus fronteras pero no en sus interiores, y si ζ3es la cara de C3en la que está contenido C1∩C3=C1∩C2, entonces ζ3⊆ζ1. El camino rectangular Q∪Q0es así un Y-Xcamino rectangular contenido completamente en C1∪C2. Veamos que su longitud es `1(Y, X). Si i /∈ {i1, ..., im}, 60 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera entonces el aporte a la longitud de Q∪Q0del desplazamiento en la i-ésima coordenada es |yi−zi|+|zi−xi|, pero en este caso yi=zi, luego es |yi−xi|. Por otro lado, si i∈ {i1, ..., im}, entonces el aporte a la longitud de Q∪Q0del desplazamiento en la i-ésima coordenada es |yi−zi|+|zi−xi|, donde zies fisi yi< fiogisi yi> gi. Si zi=fi, entonces yi< ziyzi≤xi, pues como yi< zinecesariamente fi= ˆκ1 i−ˆ ξ1 i, ya que si fi= ˆκ2 i−ˆ ξ2 ino se podría tener yi< zi, luego |yi−zi|+|zi−xi|=|yi−xi|. Si zi=gi, entonces yi> ziyzi≥xi, pues como yi> zinecesariamente gi= ˆκ1 i+ˆ ξ1 i, ya que si gi= ˆκ2 i+ˆ ξ2 ino se podría tener yi> zi, luego |yi−zi|+|zi−xi|=|yi−xi|. Concluimos así que la longitud de Q∪Q0es `1(X, Y )quedando probado el lema. Volvamos a pensar en la red de construcción rectangular N`1de X,YyB. Esta red nos permitía dar un método de cálculo de un X-Ycamino rectangular mínimo permitido basado en el Teorema 2.1, el cual consistía básicamente en aplicar cualquier algoritmo de cálculo de camino mínimo en el grafo que constituye N`1. Hablamos entonces de la complejidad asíntotica de utilizar el algoritmo de Dijkstra para hallar dicho camino. No se comentó en ese momento, pero evidentemente, una vez construido el grafo que describe N`1, puede utilizarse también para resolver el Problema 2.1, la formulación lineal clásica de programación matemática para resolver el problema del camino mínimo en grafos como un problema de flujo. El Lema 2.14 nos va a permitir además resolver el Problema 2.1 como un problema de camino mínimo en grafos de nodos no fijos. La idea es descomponer RB\int(B)en regiones entre las cuales los caminos rectangulares se comportan de una forma deseable que los hace, en algún sentido, manejables. Estas regiones, como se puede intuir y deducir del Lema 2.14, son los hiperparalelepípedos isotéticos. Este es el caso de la descomposición en paralelepípedos C(N`1)de RB\int(B)que da la red de construcción rectangular. Los paralelepípedos de C(N`1)sólo intersecan con otros en su frontera, más aún, por la construcción hecha de N`1, estas intersecciones son caras comunes de los paralelepípedos que intersecan. El Lema 2.14 puede aplicarse entonces en cualquier par de puntos de sendos paralelepípedos adyacentes (es decir, que intersecan en sus fronteras) de C(N`1). El siguiente lema proporciona un método para resolver el Problema 2.1 basado en el Lema 2.14, el objeto del lema es simplemente mostrar como puede ser utilizado el Lema 2.14 para dar solución al Problema 2.1, si bien este método se seguirá refinando en lo que resta de capítulo. Lema 2.15. Sean X1, X2∈ F y sea N`1la red de construcción rectangular de X1, X2yB. Sea G= (V, E)el grafo dirigido que posee un nodo νi∈Vpor cada paralelepípedo Cide C(N`1), y tal que el arco (i, j)∈E(y, por tanto, el arco (j, i)∈E) si y sólo si los paralelepípedos CiyCjde C(N`1)son adyacentes, esto es, intersecan. Denotemos por i0al índice tal que X1∈Ci0∈ C(N`1)(si hay más de uno i0será cualquiera de ellos), por ifal índice tal que X2∈Cif∈ C(N`1)(si hay más de uno if será cualquiera de ellos), i06=if, y notemos ˜ N=|C(N`1)|. Sea ˜κi kla coordenada késima del centro de Ciy˜ ξi kla mitad de su anchura en la coordenada OXk,i= 1, ..., ˜ N, k= 1, ..., n. Entonces, el Problema 2.1 es equivalente al problema de programación 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 61 lineal y entera mixta m´ın X (i,j)∈E Dij (2.89) s.a: X (i0,j)∈E ηi0j= 1,(2.90) X (h,if)∈E ηhif= 1,(2.91) X (i,j)∈E ηij −X (h,i)∈E ηhi = 0,∀j= 1, ..., ˜ N, i 6=i0, if,(2.92) dijk ≥ci k−cj k,∀(i, j)∈E, k = 1, ..., n, (2.93) dijk ≥ −ci k+cj k,∀(i, j)∈E, k = 1, ..., n, (2.94) Dij ≥ n X k=1 dijk −M(1 −ηij),∀(i, j)∈E, (2.95) ˜κi k−˜ ξi k≤ci k≤˜κi k+˜ ξi k,∀i= 1, ..., ˜ N, k = 1, ..., n, (2.96) ci0 k=x1 k,∀k= 1, ..., n, (2.97) cif k=x2 k,∀k= 1, ..., n, (2.98) Dij ≥0, ηij ∈ {0,1},∀(i, j)∈E, (2.99) dijk ≥0,∀(i, j)∈E, k = 1, ..., n, (2.100) ci k∈R,∀i= 1, ..., ˜ N, k = 1, ..., n, (2.101) siendo M > 0una constante lo suficientemente grande. Demostración. En (2.99)-(2.101) se define la naturaleza de las variables de decisión: ci krepresenta la k-ésima coordenada de un punto en el i-ésimo paralelepípedo Ci∈ C(N`1);dijk es una variable positiva que en el óptimo tomará, al menos, el valor absoluto de la diferencia en la k-ésima coordenada |ci k−cj k|de los puntos (ci 1, ..., ci n)t∈Ci y(cj 1, ..., cj n)t∈Cj;Dij es una variable positiva que en el óptimo tomará el valor `1((ci 1, ..., ci n)t,(cj 1, ..., cj n)t)si los puntos (ci 1, ..., ci n)ty(cj 1, ..., cj n)tpertenecen al X1- X2camino rectangular mínimo permitido que se encuentra en el óptimo y el punto (ci 1, ..., ci n)tse visita antes que el punto (cj 1, ..., cj n)tcuando el X1-X2camino óptimo se recorre desde X1hasta X2, en cuyo caso la variable binaria ηij tomará el valor 1, en caso contrario Dij = 0 yηij tomará también el valor 0. Las restricciones (2.90)-(2.92) son las restricciones clásicas de conservación de flujo utilizadas en los problemas de programación matemática para hallar caminos mínimos en grafos. Estas restricciones imponen que del nodo inicial νi0debe de salir un arco (restricción (2.90)), que al nodo final νifdebe de llegar otro (restricción (2.91)), y que en cualquier otro nodo debe conservarse el flujo (restricción (2.92)), esto es, que al nodo llegue un arco y de él salga otro, o que al nodo no llegue ni de él salga ningún arco. 62 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera De esta forma, se construye un camino de νi0aνifen G. Cada nodo νiestá representando a un punto en el paralelepípedo Ci∈ C(N`1)(restricción 2.96), la longitud Dij del arco (i, j)viene dada por, al menos, la distancia `1((ci 1, ..., ci n)t,(cj 1, ..., cj n)t)entre los puntos de CiyCjque se seleccionen en el óptimo (restricciones (2.93) y (2.94)). Como en (2.89) se está minimizando P(i,j)∈EDij, en el óptimo el camino encontrado será de longitud mínima siempre y cuando Dij = 0 si el arco (i, j)no se selecciona en el camino, es decir, si ηij = 0, pero esto se consigue con (2.95), pues si esto ocurre entonces (2.95) impone Dij ≥Pn k=1 dijk −M < 0, desigualdad que no está exigiendo nada pues Dij ≥0por definición en (2.99), haciéndose Dij = 0 por la minimización que se está haciendo en (2.89), si por el contario el arco (i, j)se selecciona en el camino, esto es, si ηij = 1, (2.95) impone Dij ≥Pn k=1 dijk, así por la minimización que se está haciendo en (2.89),Dij =Pn k=1 dijk =`1((ci 1, ..., ci n)t,(cj 1, ..., cj n)t)en el óptimo. En resumen, dado que (2.97) y (2.98) imponen que el punto de partida sea X1y el de llegada X2, el problema (2.89)-(2.101) halla en el óptimo una secuencia de puntos X1, ..., (ci 1, ..., ci n)t, ..., X2en SCi∈C(N`1)Cicumpliendo: que un punto y su sucesor pertenecen a paralelepípedos adyacentes de C(N`1); y que la suma de distancias en métrica `1entre puntos consecutivos de la secuencia es mínima. Vamos a ver que esa suma de distancias que se obtiene en el valor óptimo de (2.89)-(2.101) es la longitud de un X1-X2camino rectangular mínimo permitido y cómo se obtiene este camino a partir de la solución óptima del problema. Como SCi∈C(N`1)Ci=RB\int(B), los puntos (ci 1, ..., ci n)tseleccionados en el óptimo pertenecen a la región factible F. Por el Lema 2.14, existe un camino rectangular Qij completamente contenido en Ci∪Cj⊆ RB\int(B)de longitud la distancia en métrica `1uniendo al punto (ci 1, ..., ci n)ty su sucesor (cj 1, ..., cj n)ten la secuencia óptima, pues estos puntos pertenecen a sendos paralelepípedos CiyCjque intersecan en su frontera. De esto se deduce que efectivamente el valor óptimo de (2.89)-(2.101) es la longitud de un X1-X2camino rectangular mínimo permitido, pues la unión de los caminos rectangulares Qij es un X1-X2camino rectangular permitido (está contenido en SCi∈C(N`1)Ci=RB\int(B)) y mínimo, ya que se está minimizando su longitud en (2.89) y la región factible de (2.89)-(2.101) es SCi∈C(N`1)Ci=RB\int(B), donde es suficiente buscar un camino rectangular mínimo permitido por el Lema (2.7). Dicho camino rectangular puede construirse uniendo los puntos (ci 1, ..., ci n)tconsecutivos seleccionados en la secuencia óptima mediante el camino descrito en la demostración constructiva del Lema 2.14. El método que da el Lema 2.15 para resolver el Problema 2.1 requiere la obtención del conjunto de celdas (paralelepípedos) C(N`1)(si X1yX2están en la misma celda de C(N`1), entonces X1yX2son `1-visibles y dB(X1, X2) = `1(X1, X2)trivialmente, es por ello que en el lema se supone i06=if). Esto puede hacerse a partir de N`1, aunque como razonamos en su momento, sólo habíamos podido acotar el coste de construcción de N`1por O(W6n1122n−6)(exponencial) cuando n≥3, con W=PN i=1 miy siendo miel número de paralelepípedos que describen al complejo barrera Bi,i= 1, ..., N. 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 63 Además, el número de variables binarias de (2.89)-(2.101) depende directamente del número de paralelepípedos de C(N`1), el cual, cabe esperar que sea elevado dado el número de segmentos (O(W3n32n−3)) y nodos (O(W6n622n−6)) de N`1cuando n≥3. Más aún, los paralelepípedos CiyCjde C(N`1)que intersecan lo hacen en una cara común, lo cual contituye un caso particular de las condiciones de aplicación del Lema 2.14, es decir, el Lema 2.14 no se está explotando todo lo que se podría explotar con la descomposición de RB\int(B)en los paralelepípedos C(N`1). El método que da el Lema 2.15 puede pulirse tratando de corregir esta serie de inconvenientes. Este refinamiento pasa necesariamente por una descomposición en paralelepípedos de RB\int(B) que, en algún sentido, aproveche mejor que C(N`1)el Lema 2.14. El número de variables binarias empleadas por el modelo de programación matemática lineal y entera mixta final basado en el Lema 2.14 que se presentará en el término de la sección, es igual al número de paralelepípedos en las condiciones del Lema 2.14 en el que se descomponga RB\int(B), por ello, trataremos de realizar una descomposición C0de RB\int(B)en un número reducido de paralelepípedos. Es importante también que podamos asegurar una buena cota superior asíntotica para la complejidad de realizar dicha descomposición, pues si la complejidad de llevar a cabo la descomposición en paralelepípedos C0de RB\int(B)es muy elevada, de nada nos serviría el ahorro computacional conseguido al disminuir el número de variables binarias del modelo de programación matemática. Comenzaremos dando una descomposición de RB\int(B)de estas características en el plano y la extenderemos a dimensiones superiores de forma recursiva. Algoritmo 2.2. (Costrucción de C0en R2) Input: Los puntos X= (x1, x2)teY= (y1, y2)ten Fy el conjunto {B1, ..., BN} de complejos de paralelepípedos barrera en R2, cada uno de ellos descrito por el conjunto de paralelpípedos {B1 i, ..., Bmi i}que lo forman, i= 1, ..., N, y estos a su vez descritos por su centro (κi,j 1, κi,j 2)ty la mitad de su anchura ξi,j ken cada coordenada OXk,i= 1, ..., N,j= 1, ..., mi,k= 1,2. Paso 1: Obtener RBmediante el Algoritmo 2.1. Descartar todos los complejos barrera que no estén contenidos en RB. Si ninguno de los complejos barrera está contenido en RB, hacer L3:= RBe ir a Output. Paso 2: Ordenar de menor a mayor, los valores (se entiende, de los paralelepípedos no descartados en el paso anterior) κi,j 1+sξi,j 1,i= 1, ..., N,j= 1, ..., mi,s∈ {−1,1}, así como el valor máximo y mínimo en la coordenada OX1de RB, en una lista L1, y los valores κi,j 2+sξi,j 2,i= 1, ..., N,j= 1, ..., mi,s∈ {−1,1}, así como el valor máximo y mínimo en la coordenada OX2de RB, en una lista L2, no incluyendo las posibles repeticiones de elementos en ninguna de las listas. Seleccionar la coordenada OX1o la coordenda OX2. En adelante suponemos seleccionada la coordenada OX1, el algoritmo seleccionada la coordenada OX2es análogo. 64 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera Paso 3: Crear una lista vacía L3. Añadir a L3las caras de dimenisón 1 (hiperparalelepípedos de dimensión 1, segmentos paralelos a los ejes coordenados) de los paralelepípedos Bj icontenidas en la frontera de RB,k= 1,2. Para cada i= 1, ..., |L1| − 1hacer lo siguiente: si zies el i-ésimo elemento de L1,zi+1 el (i+ 1)-ésimo, z− 2yz+ 2los valores extremos de RBen OX2, y Ri,i+1 el paralelepípedo de vértices (zi, z− 2)t,(zi+1, z− 2)t,(zi, z+ 2)ty(zi+1, z+ 2)t, entonces añadir a L3las componentes conexas (hiperparalelepípedos de dimensión 2) de la clausura de Ri,i+1 \ B. Paso 4: Encontrar los segmentos maximales que pueden formarse mediante la unión de los segmentos de L3obtenidos en la primera parte del paso anterior, añadir estos segmentos maximales a L3y eliminar los segmentos que los constituyen. Para cada i= 1, ..., |L1|−2hacer los siguiente: para cada paralelepípedo C0 obtenido de Ri,i+1 (es decir, para cada componente conexa de la clausura de Ri,i+1 \ B) y para cada paralelepípedo C00 obtenido de Ri+1,i+2, comprobar si C0∪C00 es también un paralelepípedo, en cuyo caso eliminar C0yC00 de L3y añadir C0∪C00 aL3(en la iteración i+ 1,C0∪C00 se considera un paralelepípedo obtenido de Ri+1,i+2). Output: C0:= L3. Lema 2.16. En R2, el Algoritmo 2.2 descompone RB\int(B)en un número O(W)de paralelepípedos isotéticos, siendo W=PN i=1 miel número de paralelepípedos que describen los complejos barrera B1, ..., BN. Demostración. Los segmentos añadidos a L3en el Paso 3 del Algoritmo 2.2 son hiperparalelepípedos isotéticos de dimensión 1, y sus posibles uniones en el Paso 4 también lo son. Veamos que efectivamente las componentes conexas de la clausura de Ri,i+1 \B son hiperparalelepípedos isotéticos de dimensión 2. Para i= 1, ..., |L1|−1, puesto que en Ri,i+1 no puede estar contenida ninguna cara de ningún paralelepípedo Bj hde la forma [(κh,j 1+sξh,j 1, κh,j 2−ξh,j 2)t,(κh,j 1+sξh,j 1, κh,j 2+ξh,j 2)t]con s∈ {−1,1}a menos que κh,j 1+sξh,j 1sea el i-ésimo o el (i+ 1)-ésimo elemento de L3,Ri,i+1 \ B consiste en varios hiperparalelepípedos isotéticos de dimensión 2 disjuntos unos con otros en los que faltan algunas de sus caras, entonces, la clausura de Ri,i+1 \ B añade a estos paralepípedos isotéticos las caras faltantes. Las posibles uniones en el Paso 4 de los hiperparalelepípedos isotéticos de dimensión 2 obtenidos en el Paso 3 del Algoritmo 2.2, son claramente hiperparalelepípedos isotéticos de dimensión 2 también. Sea Z∈ RB\int(B). No es difícil ver, que si Zpertenece a la frontera de RBy al mismo tiempo a la frontera de uno de los complejos barrera, entonces Zestá contenido en alguno de los hiperparalelepípedos de dimensión 1 de C0, en cualquier otro caso, Z pertenece a alguno de los hiperparalelepípedos de dimensión 2 de C0. Luego C0es una descomposición en paralelepípedos de RB\int(B), es decir, SC0∈C0C0=RB\int(B). Probemos ahora que el número de paralelepípedos de C0es O(W). Evidentemente, 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 65 el número de hiperparalelepípedos de dimensión 1 de C0es a lo sumo O(W). En cuan- to al número de hiperparalelepípedos de dimensión 2 de C0, vamos a probar que es a lo sumo 3Σ, siendo Σel número de puntos extremos P(B)de los complejos barrera B1, ..., BN. Para ello basta probar que todo hiperparalelepípedo de dimensión 2 de C0 contiene un punto de P(B)en su frontera, como cada punto Zde P(B)puede pertenecer a lo sumo a tres hiperparalelepípedos isotéticos de dimensión 2 de C0(cuando Zes un vértice común de los tres paralelepípedos de C0), el número de hiperparalelepípedos de dimensión 2 de C0será a lo sumo 3Σ. Supongamos que el paralelepípedo C0obtenido en el Paso 3 o en el Paso 4 del Algoritmo 2.2 no posee ningún punto de P(B)en sus caras de dimensión 1 dónde la coordenada OX1es constante. Como C0no posee ningún punto de P(B)en sus caras de dimensión 1 en las que la coordenada OX1es constante, necesariamente al menos una de sus caras de dimensión 1 en las que la coordenada OX2es constante está contenida en una de las caras de dimensión 1 en la que la coordenada OX2es constante de un paralelepípedo Bj i, de lo contrario, C0se extendería en OX2desde el mínimo valor en OX2de RB(denotado z− 2en el Paso 3) hasta el máximo valor en OX2de RB(denotado z+ 2en el Paso 3), y como no habría puntos zi, zi+1 ∈ L1, con 1< i, i + 1 <|L1|, tales que zisea el mínimo valor que alcanza en OX1el paralelepípedo C0yzi+1 el máximo valor que alcanza C0en esa misma coordenada, pues en este caso C0contendría al menos un punto de P(B)en sus caras de dimensión 1 en las que la coordenada OX1 es constante, necesariamente C0=RB. Pero C0=RBsignifica que ninguno de los complejos barrera está contenido en RB, lo cual es una contradicción pues en el Paso 1 del algoritmo se hubiese saltado directamente a Output sin pasar por el Paso 3 ni el Paso 4. Por lo tanto, si C0no posee ningún punto de P(B)en sus caras de dimensión 1 en las que la coordenada OX1es constante, necesariamente al menos una de sus caras de dimensión 1 en las que la coordenada OX2es constante está contenida en una de las caras de dimensión 1 en la que la coordenada OX2es constante de un paralelepípedo Bj i. La otra cara de C0en la que la coordenada OX2es constante estará contenida en una de las caras de dimensión 1 en la que la coordenada OX2es constante de otro paralelepípedo Bl ho en la frontera de RB. Supongamos que nos encontramos en el último caso (ver Figura 2.18 (a)), para el otro caso se razona de forma análoga. Veamos que en el Paso 4 del algoritmo se descarta C0en L3para sustituirlo por un paralelepípedo que lo contiene. Sea gkel máximo valor que alcanza en OX1el paralelepípedo C0. Entonces existe en L3un paralelepípedo C00 de la misma altura que C0, compartiendo una cara de dimensión 1 con él, que en OX1se extiende desde gkhasta z0= m´ın{zq∈ L1:zq> gk}(ver Figura 2.18 (b)). Además, z0≤κi,j 1+ξi,j 1, κh,l 1+ξh,l 1. En el Paso 4 del algoritmo se realiza entonces la unión C0∪C00, que se añade a L3, y se eliminan C0yC00 de L3, o dicho de otro modo, se extiende C0por la derecha hasta z0. Más aún, C0se extenderá por la derecha en el Paso 4 hasta m´ın{κi,j 1+ξi,j 1, κh,l 1+ξh,l 1}. El paralelepípedo C000 resultante, comparte vértice con Bj ioBl h(ver Figura 2.18 (c)). Si dicho vértice no es un punto extremo del complejo correspondiente es porque las 72 2.3. Camino rectangular mínimo en presencia de paralelepípedos barrera notemos ¯ N=|C0|. Sea ¯κi kla coordenada k-ésima del centro de C0 iy¯ ξi kla mitad de su anchura en la coordenada OXk,i= 1, ..., ¯ N,k= 1, ..., n. Entonces, el Problema 2.1 es equivalente al problema de programación lineal y entera mixta m´ın X (i,j)∈E0 Dij (2.102) s.a: µi0= 1,(2.103) µif= 1,(2.104) X (h,i0)∈E0 ηhi0+X (i0,j)∈E0 ηi0j= 1,(2.105) X (h,if)∈E0 ηhif+X (if,j)∈E0 ηifj= 1,(2.106) X (h,i)∈E0 ηhi +X (i,j)∈E0 ηij = 2µi,∀i= 1, ..., ¯ N, i 6=i0, if,(2.107) ηij ≤1,∀(i, j)∈E0,(2.108) µi+µj≤1 + ηij,∀(i, j)∈E0,(2.109) ηij ≤µi,∀(i, j)∈E0,(2.110) ηij ≤µj,∀(i, j)∈E0,(2.111) dijk ≥ci k−cj k,∀(i, j)∈E0, k = 1, ..., n, (2.112) dijk ≥ −ci k+cj k,∀(i, j)∈E0, k = 1, ..., n, (2.113) Dij ≥ n X k=1 dijk −M(1 −ηij),∀(i, j)∈E0,(2.114) ¯κi k−¯ ξi k≤ci k≤¯κi k+¯ ξi k,∀i= 1, ..., ¯ N, k = 1, ..., n, (2.115) ci0 k=x1 k,∀k= 1, ..., n, (2.116) cif k=x2 k,∀k= 1, ..., n, (2.117) Dij, ηij ≥0,∀(i, j)∈E0,(2.118) µi∈ {0,1},∀i= 1, ..., ¯ N, (2.119) dijk ≥0,∀(i, j)∈E0, k = 1, ..., n, (2.120) ci k∈R,∀i= 1, ..., ¯ N, k = 1, ..., n, (2.121) siendo M > 0una constante lo suficientemente grande. Demostración. La formulación (2.102)-(2.121) es igual a la formulación (2.89)-(2.101) salvo por las restricciones (2.103)-(2.111) que sustituyen a (2.90)-(2.92), las variables ηij que ahora son variables positivas y no binarias, y las nuevas variables µidefinidas en (2.119). Los paralelepípedos de C0están en las condiciones del Lema 2.14 al igual que lo estaban los de C(N`1). Obsérvese, que por las restricciones (2.108)-(2.111), a pesar de que ηij esté definida como variable positiva en (2.118), en la práctica se va 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 73 a comportar como una variable binaria pues sólo se le va a permitir tomar el valor 0 o el valor 1. Por tanto, si demostramos que las restricciones (2.103)-(2.111) realizan la misma tarea que (2.90)-(2.92), estos es, encontar un camino en G0desde ν0 i0hasta ν0 if, los problemas de programación matemática (2.102)-(2.121) y (2.89)-(2.101) serán equivalentes, y por consiguiente, (2.102)-(2.121) será equivalente al Problema 2.1. La variable binaria µitomará el valor 1 si el nodo ν0 ies seleccionado en el camino en G0de ν0 i0aν0 ifóptimo. Con esta interpretación de las variables µi, las restricciones (2.108)-(2.111) indican que una arista ηij es seleccionada si y sólo si se han seleccionado los puntos relativos a los paralelepípedos adyacentes C0 iyC0 j(es decir, si se han seleccionado los nodos ν0 iyν0 j). Las restricciones (2.103) y (2.104) imponen que los nodos que representan los paralelepípedos en los que se encuentran X1yX2sean seleccionados. Las restricciones (2.105) y (2.106) fuerzan a que sólo se seleccione una arista inicidente en ν0 i0yν0 ifrespectivamente. Y la restricción (2.107) impone, salvo para ν0 i0yν0 if, que si ν0 ies seleccionado, entonces en él inciden dos aristas, en caso contrario, ninguna. Puesto que en (2.102) se está minimizandpo P(i,j)∈E0Dij, las restricciones (2.103)-(2.111) tienen el mismo efecto que (2.90)-(2.92), y (2.102)-(2.121) es equivalente al Problema 2.1. El número de variables binarias de la formulación (2.102)-(2.121) es igual al número de paralelepípedos de C0(O(Wn−1)). En lugar de considerar las variables ηij como binarias, la formulación (2.102)-(2.121) las considera como variables positivas, evitando así un número de variables binarias O(W2n−2), con lo que se espera un mejor rendimiento del modelo. Que las variables ηij se comporten como binarias sin serlo se consigue con un número O(W2n−2)de restricciones. La constante Mpuede tomarse nm´axi=1,...,n{2ξ0 i}+ε, siendo ξ0 ila mitad de la anchura en la coordenada OXide la envolvente rectangular iterativa RBde X,YyB=SN i=1 Bi, y εcualquier constante estrictamente positiva. El X1-X2camino rectangular mínimo permitido obtenido por el modelo puede construirse uniendo los puntos (c1 i, ..., ci n)tseleccionados en el óptimo mediante el camino descrito en la demostración constructiva del Lema 2.14. 2.4. Camino bloque mínimo en presencia de romboides barrera El Lema 1.5 del capítulo anterior ponía de manifiesto la relación existente en R2entre la norma de Manhattan y cualquier norma bloque con cuatro vectores fundamentales. En esta última sección se aprovecha dicho resultado para dar un método de resolución de un problema plano que generaliza al Problema 2.1 en R2. Consideremos fijada la norma bloque γcon vectores fundamentales (ordenados en el sentido de las agujas del reloj) u1=u1 1, u1 2t, u2=u2 1, u2 2t, u3=u3 1, u3 2t, u4=u4 1, u4 2t, 74 2.4. Camino bloque mínimo en presencia de romboides barrera cumpliendo u3=−u1yu4=−u2. Un γ-romboide centrado será un romboide con vértices de la forma 1= u2 1 w1+u1 1 w2 u2 2 w1+u1 2 w2!, 2= u2 1 w1−u1 1 w2 u2 2 w1−u1 2 w2!, 3= −u2 1 w1−u1 1 w2 −u2 2 w1−u1 2 w2!, 4= −u2 1 w1+u1 1 w2 −u2 2 w1+u1 2 w2!, donde w1, w2>0, mientras que un γ-romboide será un romboide con vértices de la forma w+i,i= 1, ..., 4, siendo w∈R2un vector cualquiera. Llamaremos complejo de γ-romboides a la unión de un número finito de γ-romboides siempre y cuando el conjunto resultante de la unión sea conexo, sin puntos de corte, sin huecos (en el sentido que venimos utilizando este término) y tal que para cualquier punto en la frontera de un γ-romboide constituyente del complejo que, al mismo tiempo, pertenezca al interior del complejo, entonces, exista otro γ-romboide del complejo distinto tal que dicho punto pertenece a su interior. Obsérvese que los complejos de γ-romboides son conjuntos poliédricos en R2. El siguiente problema es una generalización del Problema 2.1 en R2. Problema 2.2. Dado el conjunto {B1, ..., BN}de complejos de γ-romboides en R2 disjuntos dos a dos y dados dos puntos XeYen la región factible F, siendo F= R2\int(B)yB=SN i=1 Bi, calcular dB(X, Y ). Pero el Problema 2.2 puede reducirse al Problema 2.1 en R2(para el que conocemos diferentes métodos de resolución) como muestra el lema que aparece a continuación. Lema 2.18. Para la norma bloque con cuatro vectores fundamentales γfijada, sea T la transformación lineal definida en (1.21). Entonces, para todo X, Y ∈ F, γB(X, Y ) = `1,T (B)(T(X), T(Y)). Demostración. Sean X, Y ∈ F dos puntos factibles y sea SP un X-Ycamino permitido γ-mínimo con la propiedad de contacto con barreras del Lema 2.3. Entonces, SP es un camino lineal a trozos con un número finito de puntos críticos I1, ..., Ik∈ F. Como Tes lineal y biyectiva, la imagen T(SP)de SP es factible en T(F), i.e., T(SP)⊆T(F). Además, los segmentos en SP son trasformados en segmentos en T(SP), por lo que T(SP)es también un camino lineal a trozos con puntos críticos T(Ii),i= 1, ..., k. Fijando I0:= X,Ik+1 := Yy usando el Lema 1.5, obtenemos γB(X, Y ) = k X i=0 γ(Ii, Ii+1) = k X i=0 `1(T(Ii), T(Ii+1)) ≥`1,T (B)(T(X), T(Y)). Análogamente, sea SP0un T(X)-T(Y)camino permitido `1-mínimo con la propiedad de contacto con barreras en T(F). Sean I0 1, ..., I0 k0∈T(F)el conjunto finito de puntos extremos en SP0y sean I0 0:= T(X)yI0 k0+1 := T(Y). Entonces `1,T (B)(T(X), T(Y)) = k0 X i=0 `1(I0 i, I0 i+1) = k0 X i=0 γ(T−1(I0 i), T−1(I0 i+1)) ≥γB(X, Y ), 2. Camino rectangular mínimo en presencia de paralelepípedos barrera 75 con lo que se completa la prueba. Análogamente, puede probarse que bajo los supuestos del Lema 1.5, `1,B(X, Y ) = γT−1(B)(T−1(X), T−1(Y)). Para ver que el Problema 2.2 puede reducirse al Problema 2.1 en R2basta recordar que la longitud de un X-Ycamino rectangular mínimo permitido es dB(X, Y )(Lema 2.5), notar que si Bj ies un γ-romboide entonces T(Bj i)es un paralelepípedo isotético en R2 y observar que, por la linealidad de T, si {B1, ..., BN}es un conjunto de complejos de γ-romboides disjuntos dos a dos, entonces {T(B1), ..., T(BN)}es un conjunto de complejos de paralelepípedos isotéticos en R2disjuntos dos a dos. 3 Problema de la mediana rectangular en presencia de paralelepípedos barrera La presencia de barreras en los problemas de localización continua modifica las características geométricas y analíticas de estos. La no convexidad de las funciones de distancia con barrera da lugar a problemas de optimización no convexos. La mayoría de métodos clásicos empleados para los problemas de localización continua se basan fundamentalmente en la convexidad de la función objetivo y por ello fallan en este contexto. Por otro lado, los métodos generales de optimización global capaces de tratar con problemas no convexos ignoran la geometría característica de los problemas específicos que estamos considerando. La forma de lidiar con estos problemas es, por tanto, desarrollando nuevos estudios teóricos y enfoques algorítmicos que permitan superar las dificultades mencionadas y poder resolverlos eficientemente. Este capítulo se dedica al tratamiento del problema, clásico en teoría de la localización, de la mediana, cuando las distancias son medidas con respecto a la métrica de Manhattan y existen complejos de hiperparalelepípedos isotéticos en la región factible que actúan como barreras. Se proponen nuevos métodos para su resolución basados en los resultados obtenidos en el capítulo anterior para el problema del camino mínimo rectangular en presencia de praralelepípedos barrera. 3.1. Problema de localización con barreras Muchas decisiones en materia de gestión, economía, planificación de la producción, etc., presentan facetas relacionadas con la “localización de servicios”. La determinación de la ubicación de un nuevo almacén con respecto a las de un grupo determinado de clientes, teniendo en cuenta los costes de transporte y los tiempos de entrega, es sólo un ejemplo dentro de una vasta gama de aplicaciones de la localización. Por otro lado, 77 78 3.1. Problema de localización con barreras la teoría de la localización es en sí misma una parte de interés dentro las matemáticas, con un conjunto cada vez mayor de problemas y desafíos que no necesariamente tienen un transfondo real. Los problemas de localización continua se plantean a partir de un conjunto finito de puntos de demanda, los cuales son puntos en el espacio n-dimensional Rn, y que representan, por ejemplo, la ubicación espacial de clientes. Claramente n= 2 on= 3 en los problemas del ámbito real, sobre todo estos problemas se dan en R2, ya que en las aplicaciones prácticas a menudo se trata con decisiones de localización en el plano. Vamos a denotar al conjunto de puntos de demanda por Ex:= {Ex1, ..., ExM}con el conjunto de índices M:= {1, ..., M}, donde Exm∈Rnpara todo m∈ M. En un problema de localización continua debe darse además una medida de distancia d:Rn×Rn→R, que modela, por ejemplo, el coste de transporte o el tiempo de viaje entre dos puntos X, Y ∈Rn. Asumimos que des una métrica inducida por una norma k•kden Rn, es decir, dsatisface (1.7), (1.8) y (1.9). Entonces, el problema de localización continua consiste en localizar un nuevo servicio X∈Rnde tal manera que se minimice alguna función de las distancias entre el nuevo servicio Xy los puntos de demanda en Ex: m´ın f(X) = f(d(X, Ex1), ..., d(X, ExM)) s.a :X∈Rn.(3.1) Normalmente fes una función convexa y no decreciente de las distancias d(X, Exm), m∈ M. Un problema clásico de localización continua es el problema de la mediana, también conocido como el problema de Weber: m´ın f(X) = PM m=1 wmd(X, Exm) s.a :X∈Rn,(3.2) donde el peso no negativo wm=w(Exm)especifica la demanda del punto de demanda Exm,m∈ M. Por tanto, el objetivo en el problema de la mediana es minimizar el coste total de viaje entre el nuevo servicio XyEx. Este problema es el que modela, por ejemplo, el problema de decidir la localización de un almacén con respecto a las de un conjunto de clientes. Los pesos wmpueden ser también interpretados como una ponderación de la importancia o prioridad del punto de demanda Exm, si PM m=1 = 1 entonces wmpuede considerarse como la probabilidad de que una demanda aleatoria ocurra en el punto Exm,m∈ M, en este caso, en (3.2) se estaría minimizando el valor esperado del coste de viaje entre el nuevo servicio Xy el punto de demanda de Ex cuya demanda necesite ser satisfecha en un momento dado. Obsérvese que los puntos de demanda con wm= 0 pueden omitirse del modelo sin cambiar la función objetivo. Por lo tanto, asumiremos sin pérdida de generalidad que todos los pesos wm,m∈ M, son estrictamente positivos. El desarrollo de modelos de localización realistas es fundamental en los procesos 3. Problema de la mediana rectangular en presencia de paralelepípedos barrera 79 de decisión donde se tienen que localizar servicios. Especialmente en el caso de los modelos de localización plana debe considerarse la representación geométrica del problema, y la realidad geográfica tiene que ser incorporada en esta representación. Esto se traduce en restricciones en el problema de localización. Dichas restricciones se corresponden con regiones tales que viajar a través de ellas está completamente prohibido o es imposible. Estas regiones son las barreras, que en el plano pueden ser, por ejemplo, áreas militares, cordilleras, o lagos, y en el espacio tridimensional, objetos físicos. Las aplicaciones de la localización con barreras se encuentran, entre otros, en los ejemplos que hemos venido dando a lo largo de la memoria: diseño de circuitos, planificación de rutas en ciudades, enrutamiento de tuberías en barcos, etc. Consideremos el conjunto de barreras {B1, ..., BN}, el cual no es más que un conjunto finito de conjuntos cerrados y disjuntos dos a dos en Rn, y sea B=SN i=1 Bi. Como en el capítulo anterior, el viaje a través de int(B)no está permitido, lo que inmediatamente implica que el nuevo servicio no pueda localizarse en int(B). Así, la región factible F ⊆ Rnpara la ubicación del nuevo servicio y para moverse viene dada por F=Rn\int(B). Para evitar casos infactibles suponemos, como en el capítulo anterior, que Fes un subconjunto conexo de Rn. Además, debe asumirse Exm∈ F para todo m∈ M. La distancia ddel problema de localización continua pasa a ser ahora una distancia con barreras dB(Definición 2.2), que, como sabemos, verifica la desigualdad triangular (2.4) pero no es, en general, positivamente homogénea. Hechas las suposiciones anteriores, el problema de localización continua con barreras es: m´ın fB(X) = f(dB(X, Ex1), ..., dB(X, ExM)) s.a :X∈ F,(3.3) donde fB(X) = f(dB(X, Ex1), ..., dB(X, ExM)) es una función de las distancias entre el nuevo servicio Xy los puntos de demanda en Ex. Nuevamente, en la mayoría de casos, fes una función convexa y no decreciente de las distancias dB(X, Exm),m∈ M. El problema de la mediana con barreras será entonces: m´ın fB(X) = PM m=1 wmdB(X, Exm) s.a :X∈ F,(3.4) siendo los pesos wm,m∈ M, estrictamente positivos Descrito el problema de localización con barreras, pasamos a plantear el caso especial de éste sobre el que versa el capítulo. 3.2. Problema de la mediana rectangular en presencia de paralelepípedos barrera Diferentes extensiones y variaciones del problema de la mediana han sido ampliamente estudiadas en la literatura. Como se adelantaba al comienzo del capítulo, nos vamos 80 3.2. Problema de la mediana rectangular en presencia de paralelepípedos barrera a centrar aquí en el problema de la mediana cuando las distancias son medidas con respecto a la métrica de Manhattan y existen barreras en forma de complejos de hiperparalelepípedos isotéticos en la región factible. Problema 3.1. Dado el conjunto {B1, ..., BN}de complejos de paralelepípedos isotéticos en Rndisjuntos dos a dos y dado el conjunto de puntos de demanda Ex= {Ex1, ..., ExM}en la región factible F, siendo F=Rn\int(B)yB=SN i=1 Bi, es el problema 3.4 cuando d=`1. Dos métodos se proponen para resolver el Problema 3.1: el primero consiste en la obtención de un conjunto dominante finito y es una extensión a Rncon n≥2cual- quiera del método conocido para el caso plano de este problema; el segundo es una formulación de programación lineal y entera mixta. Ambos métodos se apoyan en los resultados obtenidos en el capítulo anterior. 3.2.1. Existencia de conjunto dominante finito Nos planteamos en primer lugar, como hicimos con el Problema 2.1, si es posible restringir la región de Fdonde podemos encontrar la solución óptima del Problema 3.1. Obsérvese que el concepto de envolvente rectangular iterativa RBde dos puntos X, Y ∈ F y de Bde la Definición 2.6, puede extenderse a Mpuntos Ex1, ..., ExMde F, para ello basta exigir en la Definición 2.6 que, en lugar de X, Y ∈ RB,Exm∈ RB para todo m∈ M. Utilizaremos la misma notación RBpara la envolvente rectangular iterativa de dos puntos que de M, pues la última no es más que una extensión de la primera. No es difícil ver la corrección del Algoritmo 2.1 para hallar la envolvente rectangular iterativa de los puntos de ExyBcuando sólo se cambia en éste el Paso 1, haciendo Rigual al paralelepípedo de centro κ:= ((z+ 1+z− 1)/2, ..., (z+ n+z− n)/2)ty mitad de la anchura en cada coordenada OXk,ξk:= |κk−z+ k|=|κk−z− k|, siendo z+ k= m´axm∈M{(Exm)k}yz− k= m´ınm∈M{(Exm)k},k= 1, ..., n. Lema 3.1. Sean el conjunto de puntos de demanda Ex={Ex1, ..., ExM}y la unión de los conjuntos barrera B=SN i=1 Bidel Problema 3.1, entonces, la solución óptima X∗del Problema 3.1 está contenida en la envolvente rectangular iterativa RBde los puntos de ExyB. Demostración. Si X∗∈ RB, entonces, por el Lema 2.5 y por el Lema 2.7, existe un X∗-Exmcamino rectangular mínimo permitido de longitud dB(X∗, Exm)completamente contenido en RB, para todo m∈ M. Por tanto, para razonar por reducción al absurdo, podemos asumir que no hay barreras en Rn\ RB, puesto que esta asunción sólo podría decrementar el valor en la función objetivo del Problema 3.1 de los puntos que no están contenidos en RB, mientras que no tiene efecto sobre el valor en la función objetivo del Problema 3.1 de los puntos que sí lo están. Supongamos que X∗/∈ RB. Sea QExmel X∗-Exmcamino rectangular mínimo permitido de longitud dB(X∗, Exm)que da el Lema 2.5, m∈ M. Sea Zmel último punto de QExmen la 3. Problema de la mediana rectangular en presencia de paralelepípedos barrera 81 frontera de RBcuando QExmse recorre desde X∗hasta Exm,m∈ M. Vamos a distinguir dos casos. Supongamos en primer lugar que Proyˆ j(X∗)∈int(Proyˆ j(RB)) para cierto j∈ {1, ..., n}. El índice jes único, de lo contrario se tendría que X∗∈ RB. Además, si denotamos por (κ1, ..., κn)tal centro de RBy a la mitad de su anchura en cada coordenada por ξi,i= 1, ..., n, entonces, x∗ j< κj−ξjox∗ j> κj+ξj, pues en caso contrario nuevamente se tendría X∗∈ RB. Sea XJel punto de Rncon todas sus componentes iguales a las de X∗salvo la j-ésima, que es κj+sξj, siendo s∈ {−1,1}tal que |x∗ j−(κj+sξj)|es mínimo. El punto XJpertenece a la frontera de X∗∈ RB, y por tanto, a F. Como Zmes el último punto de QExmen la frontera de RBcuando QExmse recorre desde X∗hasta Exm, considerar a RBcomo una barrera, única pues contiene a las demás, no afecta al valor de dB(X∗, Zm), es decir, dB(X∗, Zm) = dRB(X∗, Zm), m∈ M. A partir del Lema 2.9 se deduce que, si X∗yZmson `1-visibles, entonces XJyZmtambién lo son, y si X∗yZmno son `1-visibles, entonces XJyZmtampoco lo son, para todo m∈ M. En cualquier caso, los sumandos de d`1(X∗, Zm)y d`1(XJ, Zm), si X∗yZmson `1-visibles, o los de las expresiones de dRB(X∗, Zm)y dRB(XJ, Zm)que da el Lema 2.9, si X∗yZmno son `1-visibles, son los mismos salvo |x∗ j−(Zm)j|y|xJ j−(Zm)j|,m∈ M. Pero |xJ j−(Zm)j|<|x∗ j−(Zm)j|para todo m∈ M, lo que significa que XJproporciona un menor valor objetivo que X∗en el Problema 3.1, ya que por la desigualdad triangular se tiene que dB(XJ, Exm)≤dB(XJ, Zm)+l(QExm Zm,Exm)< dB(X∗, Zm)+l(QExm Zm,Exm) = dB(X∗), siendo el camino rectangular QExm Zm,Exmla porción del camino rectangular QExmque va de ZmaExm,m∈ M. Que XJproporcione un menor valor objetivo que X∗en el Problema 3.1 contradice que X∗sea la solución óptima del Problema 3.1. Supongamos ahora que Proyˆ j(X∗)∈int(Proyˆ j(RB)) no se da para ningún j∈ {1, ..., n}. Nuevamente vamos a usar que, como Zmes el último punto de QExmen la frontera de RBcuando QExmse recorre desde X∗hasta Exm, podemos considerar a RBcomo única barrera a la hora de calcular dB(X∗, Zm),m∈ M. Como Proyˆ j(X∗)∈ int(Proyˆ j(RB)) no se da para ningún j∈ {1, ..., n}, entonces, utilizando el Lema 2.9, se deduce que X∗yExmson `1-visibles para todo m∈ M. Además, al menos uno de las desigualdades x∗ j< κj−ξjox∗ j> κj+ξjse da para algún j∈ {1, ..., n}, de lo contrario X∗pertenecería a RB. Tomemos k∈ {1, ..., n}donde se dé alguna de las desigualdades anteriores. Sea XKel punto de Rncon todas sus componentes iguales a las de X∗salvo la k-ésima, que es κk+sξk, siendo s∈ {−1,1}tal que |x∗ k−(κk+sξk)| es mínimo. Del Lema 2.9 se deduce que, como X∗yZmson `1-visibles, entonces XK yZmson también `1-visibles, para todo m∈ M. Los sumandos de d`1(X∗, Zm)y d`1(XK, Zm)son los mismos, salvo |x∗ k−(Zm)k|y|xK k−(Zm)k|,m∈ M. Pero obsérvese que |xK k−(Zm)k|<|x∗ k−(Zm)k|para todo m∈ M, lo que significa que XKproporciona un menor valor objetivo que X∗en el Problema 3.1, ya que por la 88 3.3. Problema de la mediana bloque en presencia de romboides barrera Teorema 3.3. Sean el conjunto de puntos de demanda Ex={Ex1, ..., ExM}y el conjunto de barreras {B1, ..., BN}del Problema 3.2, y sea Tla transformación lineal definida en (1.21). El punto X∗∈R2es una solución óptima del Problema 3.2 si y sólo si T(X∗)es una solución óptima del Problema 3.1 con puntos de demanda T(Ex) = {T(Ex1), ..., T(ExM)}y barreras {T(B1), ..., T(BN)}. Demostración. Notando que si Bes un γ-romboide entonces T(B)es un paralelepípedo isotético en R2y que, por la linealidad de T, si {B1, ..., BN}es un conjunto de complejos de γ-romboides disjuntos dos a dos, entonces {T(B1), ..., T(BN)}es un conjunto de complejos de paralelepípedos isotéticos en R2disjuntos dos a dos, el resultado se sigue directamente del Lema 2.18. Por tanto, de acuerdo al Teorema 3.3, para resolver el Problema 3.2 podemos transformarlo mediante Ten un problema del tipo del Problema 3.1, y aplicar a éste último cualquiera de los dos métodos dados en el capítulo para su resolución, la solución óptima del problema sin transformar es la transformada inversa T−1de la solución óptima del problema transformado. 4 Pruebas computacionales En este capítulo se recogen algunos resultados de rendimiento computacional obtenidos con los modelos de programación lineal y entera mixta para resolver el problema del camino mínimo rectangular y el problema de la mediana rectangular en presencia de paralelepípedos barrera presentados en los capítulos segundo y tercero, respectivamente. 4.1. Rendimiento de los modelos de programación lineal y entera mixta En primer lugar se van a comparar el rendimiento de los modelos (2.6)-(2.30), (2.62)- (2.88) y (2.102)-(2.121) a la hora de resolver el problema del camino mínimo rectangular en presencia de un paralelepípedo isotético barrera en Rn. Los resultados que se muestran en la Tabla 4.1 son la media del tiempo en segundos obtenido para diez instancias del problema. Los puntos XeYa unir se han tomado de forma que Proyˆ 1(X),Proyˆ 1(Y)∈int(Proyˆ 1(B)) ym´ın{x1, y1}< κ1<m´ax{x1, y1}, siendo B el paralelepípedo isotético barrera y κ1la primera coordenada de su centro. Es decir, se han tomado puntos que no son `1-visibles, de acuerdo al Lema 2.9. Como cota superior para el número de codos utilizados del modelo (2.62)-(2.88) se ha tomado la que da el Lema 2.12. En cuanto al modelo (2.102)-(2.121), se ha tomado una descomponsición en 2nparalelepípedos isotéticos de RB\int(B)(número de caras de dimensión n−1 de B), siendo RBla envolventte rectangular iterartiva de X,YyB. Ni en la Tabla 4.1, ni en ninguna de las posteriores, se añaden los tiempos de la descomposición en paralelepípedos isotéticos de RB\int(B)necesaria para el modelo (2.102)-(2.121), sólamente el tiempo necesario para obtener la solución óptima del modelo. 89 90 4.1. Rendimiento de los modelos de programación lineal y entera mixta Modelo n 2 3 4 5 8 27 (2.6)-(2.30) 0 0 0.0016 0.003 0.0047 38.1341 (2.62)-(2.88) 0.0889 0.2016 2.8079 19.173 (*) - (2.102)-(2.121) 0.0015 0.0076 0.0111 0.0169 0.0234 48.6149 Tabla 4.1: Tiempo medio en segundos para diez instancias obtenidos por los modelos (2.6)-(2.30), (2.62)-(2.88) y (2.102)-(2.121) para resolver el Problema 2.1 en Rn cuando B=B. Con (*) notamos que para al menos tres instancias se ha obtendio un tiempo superior a 600 segundos. La resolución del problema con cualquiera de los tres modelos es prácticamente inmediata hasta R3. El modelo (2.62)-(2.88) es el que presenta peores resultados. Esto se debe a que el número de variables binarias que utiliza es un múltiplo de la dimensión y del número de barreras, en particular de la dimensión, es por ello que al aumentar la dimensión se obtienen peores resultados. En ocasiones, el óptimo de (2.62)-(2.88) se alcanza para un número de codos inferior al que da la cota del Lema 2.12, en estos casos, disminuir el número de codos mejora el rendimiento del modelo. Sin embargo, una reducción de la cota del número de codos que da el Lema 2.12 a priori sin que esto afecte a la solución óptima del problema no es posible. Los modelos (2.6)-(2.30) y (2.102)-(2.121) resuelven el problema de forma prácticamentte inmediata hasta dimensiones elevadas. Se ha tomado R27 para ilustrar hasta donde pueden los modelos anteriores resolver el problema en un tiempo razonable. Para los mismos modelos anteriores, se considera el Problema 2.1 cuando B= B1∪B2, siendo B1yB2dos paralelepípedos isotéticos disjuntos. Los puntos XeY a unir se han tomado de forma que Proyˆ 1(X)∈int(Proyˆ 1(B1)),x1< κ1 1, Proyˆ 1(Y)∈ int(Proyˆ 1(B2)) yκ2 1< y1, con κ1 1< κ2 1, denotando κ1 1yκ2 1la primera coordenada del centro de B1yB2respectivamente. Los resultados se muestran en la Tabla 4.2. Para el modelo (2.102)-(2.121), se ha tomado una descomponsición en 4nparalelepípedos isotéticos de RB\ B, con B=B1∪B2. Modelo n 2 3 4 5 7 (2.6)-(2.30) 0.0702 0.2528 0.7303 4.4195 53.416 (2.62)-(2.88) 1.10955 46.3977 (*) - - (2.102)-(2.121) 0.0173 0.0593 0.1271 0.2103 0.5259 Tabla 4.2: Tiempo medio en segundos para diez instancias obtenidos por los modelos (2.6)-(2.30), (2.62)-(2.88) y (2.102)-(2.121) para resolver el Problema 2.1 en Rn cuando B=B1∪B2, con B1∩B2=∅. Nuevamente el modelo (2.62)-(2.88) es el que presenta peores resultados, pues como hemos dicho, el número de variables binarias que emplea es un factor, además de 4. Pruebas computacionales 91 la dimensión, del número de obstáculos. Esta vez el modelo (2.102)-(2.121) parece presentar mejores resultados que el modelo (2.6)-(2.30) específico para el problema. Esto puede deberse a que el número de variables binarias empleadas por el modelo (2.6)-(2.30) es cuadrático respecto a la dimensión, mientras que el de (2.102)-(2.121) es cuatro veces la de esta (recuérdese que el número de variables binarias empleadas por el modelo (2.102)-(2.121) es igual al número de paralelepípedos en las que se descompone RB\int(B)). A esto hay que sumar que el número de variables positivas y restricciones del modelo (2.102)-(2.121), las cuales dependen de las conexiones (aristas) entre los paralelepípedos en los que se descompone RB\int(B), no es muy elevado para las dimensiones consideradas y la descomposición hecha de RB\int(B), de lo contrario el tiempo de resolución podría verse incrementado. Por último, se van a mostrar los resultados en R2yR3obtenidos con el modelo (3.7)-(3.31) para resolver el problema de la mediana rectangular en presencia de paralelepípedos barrera. En la Tabla 4.3 se indica el número de paralelepípedos Wconsiderados en R2así como el número de complejos de paralelepípedos Na los que dan lugar las intersecciones de estos. La descomposición en paralelepípedos de RB\int(B) en R2se ha hecho utilizando el Algoritmo 2.2. En R3se han tomado paralelepípedos barrera disjuntos y una descomposición en paralelepípedos de RB\int(B)consistente en 6Wparalelepípedos. Los resultados en R3se recogen en la Tabla 4.4. Modelo (3.7)-(3.31) W= 5 pdd: 5 N= 2 N= 3 N= 5 Tiempo 0.7739 0.7941 3.11545 |C0|11.3 11.9 15.1 Modelo (3.7)-(3.31) W= 10 pdd: 10 N= 3 N= 4 N= 5 N= 6 Tiempo 14.3964 88.1551 88.3272 133.2273 |C0|16.7 20.2 20.1 22.3 Modelo (3.7)-(3.31) W= 4 pdd: 15 N= 2 N= 3 N= 4 Tiempo 2.779 9.6394 93.0912 |C0|10 10.4 12 Tabla 4.3: Tiempo medio en segundos y número medio de paralelepípedos en los que se descompone RB\int(B)para diez instancias obtenidos por el modelo (2.102)-(2.121) en R2. El número de puntos de demanda lo notamos por pdd. 92 4.1. Rendimiento de los modelos de programación lineal y entera mixta Modelo (3.7)-(3.31) pdd/N 3/4 5/3 10/2 Tiempo 56.5247 121.3554 32.7707 Tabla 4.4: Tiempo medio en segundos para diez instancias obtenidos por el modelo (2.102)-(2.121) en R3. El número de puntos de demanda lo notamos por pdd. El tiempo de resolución del modelo aumenta con el número de complejos, aunque el número de paralelepípedos constituyentes sea el mismo. Esto se debe como puede verse a que el número de paralelepípedos en los que se descompone RB\int(B)aumenta con el número de complejos y, en consecuencia, aumenta el número de variables binarias de (3.7)-(3.31). Los resultados obtenidos con el modelo (3.7)-(3.31) pueden calificarse de modesto. Es posible que esto se deba a que la estrategia de reducir el número de variables binarias del modelo a costa de aumentar el número de restricciones no esté proporcionando los resultados deseados. Esta estrategia se traduce en un mayor tiempo de resolución del problema relajado en cada nodo del árbol que da el método de ramificación y acotación, pero reduciendo la dimensión de dicho árbol. Sería conveniente comparar estos resultados con los obtenidos al modificar el modelo (3.7)-(3.31) de forma que las variables que representan aristas sean binarias, descartándose así las restricciones necesarias para la estrategia antes descrita. Conclusiones En este Trabajo de Fin de Máster se han estudiado las funciones de distancia con barreras y su aplicación a los problemas de camino mínimo y localización. La presencia de barreras en estos problemas modifica las características geométricas y analíticas de los mismos. La no convexidad de las funciones de distancia con barreras da lugar a problemas de optimización no convexos. La mayoría de métodos clásicos empleados para los problemas de camino mínimo y localización continua se basan fundamentalmente en la convexidad de la función objetivo y por ello fallan en este contexto. Por otro lado, los métodos generales de optimización global capaces de tratar con problemas no convexos ignoran la geometría característica de estos problemas. La forma de lidiar con estos problemas es, por tanto, desarrollando nuevos estudios teóricos y enfoques algorítmicos que permitan superar las dificultades mencionadas y poder resolverlos eficientemente. En esta memoria se han propuesto diferentes y novedosos métodos para resolver el problema del camíno mínimo rectangular y el problema de la mediana rectangular en presencia de complejos de hiperparalelepípedos que actúan como barreras en cualquier espacio real de dimensión finita. Estos métodos se apoyan en resultados teóricos y algorítmicos que explotan la geometría de los caminos mínimos rectangulares en regiones factibles restringidas por paralelepípedos barrera. Dichos métodos son fundamentalmente problemas de programación lineal y entera mixta que pueden apoyarse en descomposiciones en paralelepípedos de la región factible. Una extensión al caso n-dimensional del método basado en la obtención de un conjunto dominante para el problema de la mediana con barreras conocido en el plano es otra de las aportaciones del trabajo. Las pruebas computacionales obtenidas indican que el rendimiento de los modelos propuestos debe mejorarse. Dicha mejora, así como la evaluación del rendimiento de la extensión al caso n-dimensional del método basado en un conjunto dominante antes mencionado, se realizará en una colaboración más amplia con el director del trabajo. En caso de no poder mejorarse los resultados obtenidos con los modelos de programación matemática, los resultados desarrollados para su construcción podrían utilizarse para construir metaheurísticos que combinen, por ejemplo, algoritmos genéticos y búsqueda tabú. La posible extensión del problema al uso de otras normas es otro tema que se tendrá en cuenta. 93 Bibliografía [1] BISCHOFF, M., AND KLAMROTH, K. An efficient solution method for weber problems with barriers based on genetic algorithms. European Journal of Operational Research 177, 1 (2007), 22–41. [2] BUTT, S. E., AND CAVALIER, T. M. An efficient algorithm for facility location in the presence of forbidden regions. European Journal of Operational Research 90, 1 (1996), 56–70. [3] DEREZENDE, P. J., LEE, D.-T., AND WU, Y.-F. Rectilinear shortest paths with rectangular barriers. In Proceedings of the first annual symposium on Computational geometry (1985), ACM, pp. 204–213. [4] DEARING, P., HAMACHER, H., AND KLAMROTH, K. Dominating sets for rectilinear center location problems with polyhedral barriers. Naval Research Logistics (NRL) 49, 7 (2002), 647–665. [5] HAMACHER, H. W., AND KLAMROTH, K. Planar location problems with barriers under polyhedral gauges. [6] ICKING, C., KLEIN, R., MA, L., NICKEL, S., AND WEISSLER, A. On bisectors for different distance functions. Discrete applied mathematics 109, 1 (2001), 139–161. [7] KLAMROTH, K. A reduction result for location problems with polyhedral barriers. European Journal of Operational Research 130, 3 (2001), 486–497. [8] KLAMROTH, K. Single-facility location problems with barriers. Springer Science & Business Media, 2006. [9] LARSON, R. C., AND SADIQ, G. Facility locations with the manhattan metric in the presence of barriers to travel. Operations Research 31, 4 (1983), 652–669. [10] LOVE, R. F., AND MORRIS, J. G. A computation procedure for the exact solution of location-allocation problems with rectangular distances. Naval Research Logistics (NRL) 22, 3 (1975), 441–453. 95 96 Bibliografía [11] MINKOWSKI, H. Gesammelte abhandlungen, zweiter band. sl]: Nabu Press.- 2010-468 S (1967). [12] NICKEL, S. Discretization of planar location problems. Verlag Shaker, 1995. [13] WARD, J. E., AND WENDELL, R. E. Using block norms for location modeling. Operations Research 33, 5 (1985), 1074–1090.