Calidad
Páginas: 27 (6585 palabras)
Publicado: 25 de septiembre de 2012
Un algoritmo para el cálculo del conjunto dominante finito del problema generalizado de la p-centdiana
M. J. Canós Darós, Universidad de Valencia M. L. Martínez Romero, Florida Universitaria M. Mocholí Arce, Universidad de Valencia
RESUMEN Los problemas de localización tratan de averiguar la ubicación de las instalaciones de una empresa de modo que se minimicen los costes o se maximicen losbeneficios. Dos de los modelos más utilizados en localización en redes son el problema de la p-mediana y el problema del p-centro. El primero consiste en minimizar la suma total de las distancias ponderadas, mientras que el segundo trata de minimizar la máxima distancia ponderada desde un centro de servicio hasta sus usuarios asignados. El objetivo del problema de la p-mediana hace que sea eficientepero no equitativo, mientras que la cota implícita en el problema del p-centro lo convierte en equitativo pero no eficiente. Para combinar ambos aspectos, aparece en la década de los 70 un nuevo problema, el de la p-centdiana, cuya función objetivo es una mezcla de las dos anteriores. En este trabajo consideramos el problema generalizado de la p-centdiana sobre una red en la que los pesosasociados al p-centro y a la p-mediana no son necesariamente iguales. Mientras que los conjuntos dominantes finitos de los dos primeros problemas son relativamente sencillos de calcular, esto no es así para la p-centdiana generalizada. Proponemos un algoritmo que nos permitirá calcular este conjunto. Palabras clave: Localización, p-centdiana, conjunto dominante finito.
87
Canós et al.
1.INTRODUCCIÓN Dos de los modelos básicos más conocidos de localización sobre redes son el problema del p-centro y el de la p-mediana, planteados por primera vez por Hakimi (1964, 1965). El problema del p-centro trata de encontrar la localización de p centros de servicio de forma que se minimice la máxima distancia entre un punto demanda y su centro de servicio más próximo (equidad). Por su parte, elproblema de la p-mediana consiste en calcular la ubicación de p centros de servicio de forma que se minimice la distancia total (o media) ponderada recorrida para atender toda la demanda (eficiencia). En muchos problemas reales, sin embargo, se busca una mezcla de ambos objetivos. Por ejemplo, si queremos localizar un parque de bomberos intentaremos no discriminar a las poblaciones remotas y con bajadensidad sin generar por ello un gran incremento en la distancia total. Aparece, entonces, de forma natural el problema de la p-centdiana cuya función objetivo es una combinación de las funciones objetivo de los problemas de la p-mediana y del p-centro En el primer trabajo aparecido sobre el problema de la p-centdiana, Halpern (1976) aborda el problema de encontrar un único centro de servicio sobreuna red con estructura de árbol con el objetivo de combinar la eficiencia de la localización con la equidad. Este objetivo queda reflejado matemáticamente mediante una combinación convexa entre la función objetivo de la mediana y la función del centro. En este mismo trabajo, el autor acuña el término centdiana para referirse al nuevo objetivo, nomenclatura que terminará triunfando sobre el nombrealternativo, medicentro, propuesto por Handler (1985). Posteriormente, el mismo autor (Halpern, 1978) extiende los resultados a una red general y demuestra (Halpern, 1980) que la centdiana es un caso especial del problema de minimizar uno de los criterios sujeto a una restricción en la que el otro criterio está acotado. A principios de los 90, Hansen, Labbé y Thisse (1991) dan una caracterizacióncompleta de las centdianas en el caso de un árbol, extienden los resultados de Halpern y presentan un nuevo algoritmo para determinar el conjunto de soluciones en el caso de una red general. Simultáneamente, Berman y Yang (1991) enfocan el problema como
88
Un algoritmo para el cálculo del conjunto dominante finito del problema generalizado de la p-centdiana
un caso particular del...
M. J. Canós Darós, Universidad de Valencia M. L. Martínez Romero, Florida Universitaria M. Mocholí Arce, Universidad de Valencia
RESUMEN Los problemas de localización tratan de averiguar la ubicación de las instalaciones de una empresa de modo que se minimicen los costes o se maximicen losbeneficios. Dos de los modelos más utilizados en localización en redes son el problema de la p-mediana y el problema del p-centro. El primero consiste en minimizar la suma total de las distancias ponderadas, mientras que el segundo trata de minimizar la máxima distancia ponderada desde un centro de servicio hasta sus usuarios asignados. El objetivo del problema de la p-mediana hace que sea eficientepero no equitativo, mientras que la cota implícita en el problema del p-centro lo convierte en equitativo pero no eficiente. Para combinar ambos aspectos, aparece en la década de los 70 un nuevo problema, el de la p-centdiana, cuya función objetivo es una mezcla de las dos anteriores. En este trabajo consideramos el problema generalizado de la p-centdiana sobre una red en la que los pesosasociados al p-centro y a la p-mediana no son necesariamente iguales. Mientras que los conjuntos dominantes finitos de los dos primeros problemas son relativamente sencillos de calcular, esto no es así para la p-centdiana generalizada. Proponemos un algoritmo que nos permitirá calcular este conjunto. Palabras clave: Localización, p-centdiana, conjunto dominante finito.
87
Canós et al.
1.INTRODUCCIÓN Dos de los modelos básicos más conocidos de localización sobre redes son el problema del p-centro y el de la p-mediana, planteados por primera vez por Hakimi (1964, 1965). El problema del p-centro trata de encontrar la localización de p centros de servicio de forma que se minimice la máxima distancia entre un punto demanda y su centro de servicio más próximo (equidad). Por su parte, elproblema de la p-mediana consiste en calcular la ubicación de p centros de servicio de forma que se minimice la distancia total (o media) ponderada recorrida para atender toda la demanda (eficiencia). En muchos problemas reales, sin embargo, se busca una mezcla de ambos objetivos. Por ejemplo, si queremos localizar un parque de bomberos intentaremos no discriminar a las poblaciones remotas y con bajadensidad sin generar por ello un gran incremento en la distancia total. Aparece, entonces, de forma natural el problema de la p-centdiana cuya función objetivo es una combinación de las funciones objetivo de los problemas de la p-mediana y del p-centro En el primer trabajo aparecido sobre el problema de la p-centdiana, Halpern (1976) aborda el problema de encontrar un único centro de servicio sobreuna red con estructura de árbol con el objetivo de combinar la eficiencia de la localización con la equidad. Este objetivo queda reflejado matemáticamente mediante una combinación convexa entre la función objetivo de la mediana y la función del centro. En este mismo trabajo, el autor acuña el término centdiana para referirse al nuevo objetivo, nomenclatura que terminará triunfando sobre el nombrealternativo, medicentro, propuesto por Handler (1985). Posteriormente, el mismo autor (Halpern, 1978) extiende los resultados a una red general y demuestra (Halpern, 1980) que la centdiana es un caso especial del problema de minimizar uno de los criterios sujeto a una restricción en la que el otro criterio está acotado. A principios de los 90, Hansen, Labbé y Thisse (1991) dan una caracterizacióncompleta de las centdianas en el caso de un árbol, extienden los resultados de Halpern y presentan un nuevo algoritmo para determinar el conjunto de soluciones en el caso de una red general. Simultáneamente, Berman y Yang (1991) enfocan el problema como
88
Un algoritmo para el cálculo del conjunto dominante finito del problema generalizado de la p-centdiana
un caso particular del...
Leer documento completo
Regístrate para leer el documento completo.