El problema de 1 centro , también conocido como problema minimax o problema de ubicación minmax , es un problema clásico de optimización combinatoria en la investigación de operaciones del tipo de ubicación de instalaciones . En su caso más general, el problema se plantea de la siguiente manera: dado un conjunto de n puntos de demanda, un espacio de ubicaciones factibles de una instalación y una función para calcular el costo de transporte entre una instalación y cualquier punto de demanda, encuentre una ubicación de la instalación lo que minimiza el costo máximo de transporte del punto de demanda de la instalación.
Existen numerosos casos particulares del problema, dependiendo de la elección de las ubicaciones tanto de los puntos de demanda como de las instalaciones, así como de la función de distancia.
Un caso especial simple es cuando las ubicaciones factibles y los puntos de demanda están en el plano con la distancia euclidiana como costo de transporte ( problema de ubicación de instalaciones euclidianas mínimas planas, problema euclidiano de 1 centro en el plano, etc.). También se conoce como el problema del círculo más pequeño . Su generalización a espacios euclidianos n - dimensionales se conoce como el problema de la bola envolvente más pequeña . Una generalización adicional ( ubicación de la instalación euclidiana ponderada ) es cuando el conjunto de pesos se asigna a los puntos de demanda y el costo de transporte es la suma de los productos de las distancias por los pesos correspondientes. Otro caso especial, el problema de cuerdas más cercano , surge cuando las entradas son cuerdas y su distancia se mide utilizando la distancia de Hamming .
El problema de 1 centro se puede replantear como encontrar una estrella en un gráfico completo ponderado que minimiza el peso máximo de los bordes seleccionados. El problema correspondiente de minimizar el peso máximo de una ruta entre dos vértices seleccionados, en lugar de una estrella, se denomina problema de ruta minimax .
Referencias
- Megiddo, Nimrod (noviembre de 1983). "El problema de 1 centro euclidiano ponderado" (PDF) . Matemáticas de la investigación operativa . 8 (4): 498–504. doi : 10.1287 / moor.8.4.498 .
- Falta, Abdelaziz (mayo de 2006). "Un problema de 1 centro en el plano con puntos de demanda distribuidos uniformemente". Cartas de investigación operativa . Elsevier. 34 (3): 264–268. doi : 10.1016 / j.orl.2005.04.011 .
- Chandrasekaran, R. (julio de 1982). "El problema de 1 centro euclidiano ponderado". Cartas de investigación operativa . Elsevier. 1 (3): 111–112. doi : 10.1016 / 0167-6377 (82) 90009-8 .
- Colebrook, M .; J. Gutiérrez, S. Alonso; J. Sicilia (diciembre de 2002). "Un nuevo algoritmo para el problema de 1 centro indeseable en las redes". Revista de la Sociedad de Investigación Operativa . Revistas Palgrave Macmillan. 53 (12): 1357-1366. doi : 10.1057 / palgrave.jors.2601468 . JSTOR 822725 .
- Burkard, Rainer E .; Helidon Dollani (febrero de 2002). "Una nota sobre el problema robusto de un centro en los árboles". Anales de investigación operativa . Editores académicos de Kluwer. 110 (1–4): 69–82. doi : 10.1023 / A: 1020711416254 . ISSN 1572-9338 .