Localización de centros públicos atractivos y /o repulsivos

Sistemas Cualitativos y Diagnosis medida que el cubrimiento de los diferentes CTs utilizados para un mismo programa se com plete, la diagnosis será más precisa. Para inves tigaciones futuras estamos trabajando en am pliar la gramática que soporta la metodología. Una investigación en curso permitirá incorporar restricciones lógicas. La extensión de todo esto a la gramática completa de Java™ se perfila como el objetivo final de esta investigación. Referencias [BinderOOJ Robert V. Binder. Testing Object Oriented Systems : Models, Patterms, and Tools. Addison Wesley. [Buchberger85J Buchberger B. Gri:ibner bases. An algorithmic method in polynomial ideal theory. Multidimensional Systems Theory, N. K. Bose, ed., D. Reidel Publishing Co., pag 184-232, 1985. [DeKleer&Williarns87] De Kleer J., and Williams, B.C. 1987. Diagnosis multi ple faults. Atificial lntelligence 32(1):pag 97-130, 1987. [GascaOl] R.M. Gasea, J.A. Ortega, M.Toro y F. De la Rosa T. Diagnosis dirigida por re stricciones simbólicas para modelos polinómi cos. Terceras Jornadas de trabajo sobre Metodologías Cualitativas Aplicadas a los Sistemas Socioeconomicos, Valladolid Julio 2001. [Helzer95] Helzer G. Griibner Bases. The Mathematica Journal Vol 5 Issue 1, 1995. [Hoffman89] Hoffman C. M. Geometric and solid modeling: An Introduction. Morgan Kaufmann, 1989. [Hollman93] Hollman J. y Langemyr. Algo rithms for Non-linear algebraic constraints. Constraint Logic Programming Selected Re search pag 113-131. [Khalil98] Khalil, M. Automated strategies for software diagnosis. The Ninth lnternation al Sympsosium on Software Reliability En gineering, Paderborn, Germany, Nov. 1998. [Khalil99] Khalil, M. An Experimental Com parason of Software Diagnosis Methods. 25th Euromicro Conference 1999. 32 [Kapur&Laksman92J Kapur D. y Lakshman Y. N., Elimination Methods: An Jntroduction. Symbolic and Numerical Computation for Artificial Intelligence, D. Kapur and Mundy (eds.), Academic Press, 1992. [Kapur95] Kapur, D. An Approach for Solv ing Systems of parametric Polynomial Equa tions. En Principies and Practice of Con straint Programming, pag 218-243,1995. [Lyle&Weiser87] Lyle J. R. and Weiser, M. Au tomatic bug location by program slicing. Sec ond lnternational Conference on Computers and Applications, Beijing, China, pag. 877883,June 1987. [Mateis99] Cristinel Mateis, Markus Stumpt ner, Dominik Wieland and Franz Wotawa .. Debugging of Java programs using a model' based approach. DX-99 Work-Shop,Loch Awe, Scotland (1999). [MateisOO] Cristinel Mateis, Markus Stumpt ner, Dominik Wieland and Franz Wotawa. Extended Abstract -Model-Based Debug ging of Java Programs. AADEBUG, August 2000,Munich. [Reiter87] Reiter R. A theory of diagnosis from first principies. Artificial Intelligence, 32(1), pag 57-96, 1987. [Weiser82] Weiser, M. Programmers Use Slices When Debugging. Communications of the ACM, Vol. 25, No. 7, pp.446-452,1982. [Weiser84] Weiser, M. Program Slicing. IEEE Transactions on Software Engineering SE-10, 4, pp. 352-357, 1984 Sistemas Cualitativos y Diagnosis Localización de centros públicos atractivos y /o repulsivos Cristobal Chamizo Guerra 1 chamiz[email protected] Francisco Velasco Morente 2 [email protected] Rafael Martínez Gasea 3 [email protected] Resumen: En este trabajo localizamos un centro de servicio en la Provincia de Sevilla en relación a unos puntos fijos atractivos o repulsivos, resolviendo el problema de Weber mediante algoritmos de ramificación y poda, de consistencia eficiente y que son algoritmos que permiten declarar fácilmente el problema mediante las restricciones y la función a optimizar, así como de configuración sencilla, en el sentido de que sirven para diferentes tipos de problemas de optimización sin restricciones, y satisfacción de restricciones en general. Localizamos el centro utilizando dos familias de funciones de distancia para las que calculamos los parámetros que mejor aproximan las distancias por carreteras existentes en la red provincial. 1.-INTRODUCCIÓN: Uno de los problemas clásicos en teoría de localización de centros de servicio es la ubicación de un determinado centro x e R' que de servicio a otro conjunto de poblaciones que se consideran fijos P, e lR2, i = l, ... ,m, minimizando la suma ponderada (por pesos asociad OS a cada punto, W; E fit2, j = 1, ... , m de las distancias de los puntos fijos al nuevo centro. Este es el Problema que Weber ya propuso en 1909 en "Über den Standort des lnd ustrien": Min f w;d(X,P¡) (1) XeIR.2 i=l donde d(X,Y) es una función de distancia preestablecida, entre los puntos X e Y. El problema, que en un principio fue puramente matemático, tuvo gran importancia práctica posteriormente y más aún con la aparición de los algoritmos que lo resolvían, favorecidos además por el auge de las computadoras. Weiszfeld (1937) se anticipó en algunos años a estas técnicas y descubrió un algoritmo natural; que en definitiva es el algoritmo del gradiente, y que partiendo de un punto inicial, lo más próximo posible a la solución busca óptimos locales, o globales, dependiendo del problema. Cuando los puntos fijos son atractivos, es decir, están interesados en utilizar dicho centro (como por ejemplo un colegio o un centro sanitario), los pesos w, son positivos; los puntos fijos son de demanda, y en este caso la función objetivo del problema de Weber es convexa, con lo que el óptimo local encontrado (mínimo) es global. Cuando los puntos fijos son repulsivos, esto es, no están interesados en tener cerca el centro de servicio (vertedero, central nuclear ... ), los pesos son negativos, y en este caso la función es cóncava. Por último, puede darse el caso de que un centro de servicio sea repulsivo para ciertos puntos y atractivo para otros, como por ejemplo un aeropuerto puede ser repulsivo para el área metropolitana de una ciudad, o grandes ciudades y sin embargo atractivo para una determinada zona, por lo que puede suponer de aportación económica para dicha zona. Para este último caso la función objetivo ya no es convexa y entonces los algoritmos clásicos de resolución tienen carácter local, como son el mencionado algoritmo de Weiszfeld, el algoritmo de Newton o bien los algoritmos genéticos 1 Titular de Escuela Universitaria. Depto. de Economía Aplicada I . U. Sevilla. Perceptor de correspondencia. 2 Titular de Universidad. Depto. de Economía Aplicada I. U. Sevilla 3 Titular de Universidad. Depto. Lenguajes y Sistemas Informáticos. U. Sevilla 33 Sistemas Cualitativos y Diagnosis Gráfico 2 5.-CONCLUSIONES FUTUROS: y TRABAJOS En este trabajo hemos pretendido, fundamentalmente mostrar un algoritmo que 38 busca y encuentra donde pueden hallarse los óptimos glogales de un problema, o más bien, descarta, usando el análisis intervalar, donde no están, podando estas zonas. Este tipo de algoritmo tiene excelentes cualidades para la Sistemas Cualitativos y Diagnosis búsqueda de óptimos globales que no ofrecen las técnicas de búsqueda locales, como son la convergencia segura no excesivamente costosa en la mayoría de los casos y la certeza del óptimo global. Este tipo de algoritmos además, son especialmente útiles cuando se tiene poca información sobre donde pueden estar los óptimos globales. También se pueden combinar con algoritmos locales, lo que permite el aprovechamiento de las mejores cualidades de ambas técnicas. En el trabajo, hemos localizado un centro de servicio en la Provincia de Sevilla, hipotéticamente repulsivo para las dos localidades de mayor población, Sevilla y Dos Hermanas, y atractivo para el resto de comunidades, 105 localidades en total, atendiendo a la población de cada sitio, y a la distancia; esto es resolviendo el Problema de Weber correspondiente. Previamente hemos calculado los parámetros óptimos para ajustar la función de distancia, a la distancia real existente por carretera entre localidades, que hemos hallado y recogido en una matriz triangular de tamaño 105, lógicamente con ceros en la diagonal, con un total de datos de: (1:5) Los algoritmos de cómputo de los parámetros vienen recogidos en el capitulo 11 del trabajo de investigación "Medición de la distancia en el Problema de Weber· (Chamizo (1996)). Hemos calculado estos parámetros para la familia de normas lp y la familia uno Infinito. Hemos comprobado que la función de distancia para la red de carreteras de la provincia de Sevilla es próxima a la nonna uno, más aún, cuando hemos calculado de nuevo los parámetros óptimos, a partir de una matriz de distancias, que hemos llamado distancias efectivas, en· la que hemos tenido en cuenta la distancia real existente y las cronas correspondientes, es decir, el tiempo de viaje estimado entre cada dos pueblos. De todas formas. aunque conocemos los parámetros óptimos para la función de distancia, se ha obtenido la solución para estos parámetros y para una variación continua en la familia lp, del parámetro p desde 1 hasta 2, con variaciones de una décima, obteniéndose que la solución es una curva 39 continua, que podemos ver en los gráficos del trabajo, y que se halla próxima a las localidades de Estepa, Gilena y Pedrera. Para trabajos futuros, pretendemos calcular funciones de distancia para circular por Sevilla capital. Primero tendremos que situar unos lugares estratégicos entre los que calcular las distancias y el tiempo de recorrido para ajustar la función. Asimismo, pretendemos que los pesos del problema de Weber recojan otros factores además del número de habitantes de un punto fijo (o de usuarios del centro a localizar que haya en dicho punto) Agradecimientos: Este trabajo ha sido soportado parcialmente por la ayuda concedida por la Junta de Andalucía (ACC265-TIC-2001) 6.-BIBLIOGRAFIA: ANO ROUTE COMPACT ESPAÑA 99. VERSIÓN 4.08. (1998). ANO Publishers. BENHAMOU, F., MAcALLESTER D. y VAN HENTENRYCK P. (1994). CLP (intervals) revisited. In Proceedings of the lntemational Logic Programming Symposium, 94. CHAMIZO, C. (1996). "Medición de la distancia en el Problema de Weber". Tesina. GIL, D. (2001). "Morón se debate entre el miedo a la crisis mundial y la posibilidad de que el uso de la base cree empleo·. El País; Andalucía, 23-9-2001: 1. HANSEN, E.(1992). Global Optimization Using lnterval Analysis. Marcel Dekker, INC. New York. LHOMME O. (1993). Consistency techniques fer numeric CSPs. In Proceedings of the 13th lntemational Joint Conference on Al. LOVE, R. F., J.G. MORRIS. (1975). "Solving Constrained Multi-Facility Location Problems lnvolving lp Distancies Using Convex Programming·. Operations Research 23, 581587. LOVE, R. F., J. G. MORRIS and G. O. WESOLOWSKY. (1988). Facilities Location: Models and Methods. Nort-Holland: New-York. MARTINEZ GASCA, R. (1998) 'Razonamiento y Simulación en Sistemas que integran Conocimiento Cualitativo y Cuantitativo·. Tesis Doctoral.