Algoritmo Weiszfeld

El algoritmo de Weiszfeld para la resoluci´n del o problema econ´mico de Weber o
Ca˜ avate Bernal, Roberto J. n Departamento de M´todos Cuantitativos e Inform´ticos e a Universidad Polit´cnica de Cartagena e E-mail: r.canavate@upct.es Cobacho Tornel, Ma Bel´n e Departamento de M´todos Cuantitativos e Inform´ticos e a Universidad Polit´cnica de Cartagena e E-mail: belen.cobacho@upct.es Rodr´ıguez G´mez, Jos´ Miguel o e Departamento de M´todos Cuantitativos e Inform´ticos e a Universidad Polit´cnica de Cartagena e E-mail: jose.rodriguez@upct.es

Resumen El problema econ´mico de Weber ha sido ampliamente tratado en la literatura, o tanto te´rica como emp´ o ıricamente, gracias a su gran adaptabilidad a la modelizaci´n de situaciones reales. Su caso particular m´s estudiado es el queconsidera o a distancias eucl´ ıdeas, debido en parte al respaldo que este tipo de distancias ha recibido de algunos estudios aplicados. El algoritmo de Weiszfeld sigue siendo el m´todo m´s utilizado para su resoluci´n a pesar de que puede existir un conjunto e a o de puntos iniciales para los que el algoritmo no converja. En [Brimberg, 1995] se acotaba el tama˜o de este conjunto y se conclu´ que laprobabilidad de elegir n ıa al azar uno de estos punto iniciales es pr´cticamente nula. Sin embargo, en el a documento [C´novas et al., 1999] se rebate la validez de las demostraciones realia zadas en dicho art´ ıculo. De cualquier modo, se presenta en este trabajo un sencillo m´todo de elecci´n del punto inicial para el algoritmo de Weiszfeld que asegura la e o convergencia al ´ptimo, esto es, queelimina los problemas de aplicaci´n del proceso o o iterativo de Weiszfeld.

Palabras clave: Problema de Weber, Algoritmo de Weiszfeld, Norma eucl´ ıdea.

1

1

Introducci´n o

A principios del siglo XX, en su influyente libro sobre localizaci´n de industrias (v´ase o e [Weber, 1909]), el economista Alfred Weber formul´ el siguiente problema: Se necesita o establecer la ubicaci´n de unaf´brica que se abastecer´ de materia prima de dos almao a a cenes, y cuyo producto se vender´ en un cierto mercado. La distancia desde la f´brica a a a los almacenes y al mercado suponen un coste para la f´brica que puede ser estimado a y que se considera proporcional a dicha distancia. ¿Cu´l es la localizaci´n que genera a o un menor coste econ´mico para la empresa? Este problema, cuya resoluci´nrequiere la o o b´squeda de un punto que minimice la suma de las distancias ponderadas (por el factor u de proporci´n de los costes) a los tres puntos conocidos (los dos almacenes y el mercao do), y al que se denomina el problema de Weber, es el origen de una gran corriente de aplicaciones pr´cticas, adaptaciones y generalizaciones que perdura hasta nuestros d´ a ıas, y que lo convierten en untema especialmente fruct´ ıfero. Es importante observar que aunque el problema original de Weber fue formulado para unicamente tres puntos conocidos y para la localizaci´n de industrias, las aplicaciones ´ o pr´cticas (v´ase, por ejemplo, [Burstall et al., 1962], [Haley, 1963] y [O’Kelly, 1986]) cona e llevan normalmente una gran cantidad de puntos, y abarcan ´mbitos tan diversos como a la ergonom´o rob´tica (v´ase [Foulds y Hamacher, 1993] y [Ca˜avate et al., 2001]). ıa o e n Por otra parte, un aspecto fundamental es la determinaci´n de la funci´n de medida o o que se utilizar´ para estimar la distancia a los puntos fijos. Diversos estudios se han llevaa do a cabo sobre el tema, destacando los realizados para la determinaci´n de las funciones o apropiadas para la estimaci´n de distanciasreales por carretera. Entre ellos se pueden cio tar [Love y Morris, 1972] y [Love y Morris, 1979], sobre las distancias por carretera entre 25 ciudades de los Estados Unidos, y [Berens y K¨rling, 1985] y [Berens y K¨rling, 1988], o o acerca de las distancias por autopista entre 117 ciudades de la antigua Rep´blica Federal u de Alemania. Aunque los dos primeros parec´ indicar que la norma lp era...