Problema de 1 centro

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de marzo de 2017; la verificación requiere 1 edición .

El problema de 1 centro o problema de colocación de objetos minimax es un problema clásico de optimización combinatoria , un problema en la disciplina de la investigación de operaciones , es un caso especial del problema de colocación de objetos . En el caso más general, se formula de la siguiente manera:

Se da un conjunto de ubicaciones de los consumidores, un espacio de posibles ubicaciones de los objetos (de producción o servicio) y una función del costo de transporte desde cualquier punto de posible ubicación hasta el punto de consumo. Es necesario encontrar la ubicación óptima de los objetos, minimizando el costo máximo de entrega del objeto al consumidor.

Un caso especial simple en el que los puntos de alojamiento y consumo están en un plano y el costo de envío es la distancia euclidiana ( problema de ubicación euclidiana planar minimax, problema de plano euclidiano de 1 centro ) también se conoce como el problema del círculo mínimo . Su generalización a espacios euclidianos de dimensiones superiores se conoce como el problema de la esfera mínima delimitante . En otra generalización ( problema de ubicación euclidiana ponderada ), se asignan pesos a los puntos de consumo y el costo del transporte es la suma de las distancias multiplicada por los pesos correspondientes. Otro caso especial es el problema de la línea más cercana , cuando la entrada del problema es la cadena , y la distancia se mide como la distancia de Hamming .

Existen numerosos casos especiales del problema, dependiendo tanto de la elección de la ubicación de los puntos de consumo y de los objetos de producción (o servicio), como de la elección de una función que calcule la distancia.

El problema de 1 centro en términos de teoría de grafos

La formulación de tal variante del problema radica en el hecho de que se da un gráfico , así como una función de costo, y es necesario encontrar un conjunto tal que sea mínimo, es decir un conjunto tal que el costo máximo de un camino desde el vértice más cercano a cualquier vértice sigue siendo mínimo. Además, el problema se puede complementar con la función de costo del vértice, y luego el radio se definirá como . $G=(V,E)$ $k\in {\matemáticas {N}}$ ${\displaystyle c\dos puntos E\to \mathbb {Q} ^{+))$ ${\ estilo de visualización Z \ subconjunto V}$ $\operatorname {rad} (Z)=\max _{v\in V}\min _{z\in Z}c(z,v)$ $Z$ $Z$ ${\displaystyle w\colon V\to \mathbb {Q} ^{+))$ $\operatorname {rad} (Z)=\max _{v\in V}[w(v)\cdot \min_{z\in Z}c(z,v)]$

La idea de una solución aproximada del problema es buscar mediante un algoritmo codicioso un radio fijo . Siempre que haya vértices que no estén cubiertos por , uno debe elegir con avidez un vértice y considerar todos los demás vértices disponibles . El algoritmo se repite para diferentes valores de . La siguiente es una descripción del método en una forma formal: $Z$ $R$ $Z$ $z$ ${\ estilo de visualización 2R}$ $R$

Instalar y . $Z=\emptyset$ ${\ estilo de visualización U = V}$
Adiós : $U\neq\emptyset$
1. ${\displaystyle z=\operatorname {argmax} \{w(u)\mid u\in U\))$ .
2. ${\displaystyle Z=Z\taza \{z\))$ .
3. ${\displaystyle U=U\setminus \{v\in U\mid w(v)\cdot \operatorname {dist} (v,z)\leqslant 2R\))$ .
sacar _ $Z$

Sea la solución óptima para . En el caso de que , el algoritmo codicioso devolverá un conjunto tal que . Con base en esto, definimos y observamos que la función no es monótona . A continuación, denotamos el radio , con la ayuda de la cual solo un vértice en puede cubrir todos los vértices del gráfico, es decir , un . $R^{*}$ $Z^*$ $R\geqslant R^{*}$ $Z$ $|Z|\leqslant |Z^{*}|$ $f(R)=|\operatorname {GreedyCenter} (G,c,w,R)|$ $F$ $R'=\max _{v\in V}[w(v)\cdot \sum_{e\in E}c(e)]$ $Z$ ${\ estilo de visualización f (R') = 1}$ ${\ estilo de visualización f (0) = | V | = n}$

Lema. Para cualquier gráfico con un conjunto y un radio óptimos , la desigualdad se cumple para todos . $G=(V,E)$ $Z^*$ $R^{*}=\nombre del operador {rad} (Z^{*})$ ${\ Displaystyle f (R) \ leqslant k}$ $R\geqslant R^{*}$

Prueba. Sea y el vértice seleccionado en el ciclo del algoritmo . Entonces la desigualdad real es: ${\displaystyle V_{i}=\{v\in V\mid w(v)\cdot \operatorname {dist} (v,z_{i})\leqslant R^{*}\))$ ${\ Displaystyle z \ en V_ {i}}$ $\operatorname {GreedyCenter}$

{\begin{alineado}w(v)\cdot \operatorname {dist} (v,z)&\leqslant w(v)\cdot (\operatorname {dist} (v,v_{i})+\ nombre del operador {dist} (v_{i},z))\\&\leqslant w(v)\cdot \nombre del operador {dist} (v,v_{i})+w(z)\cdot \nombre del operador {dist} ( v_{i},z)\\&\leqslant 2\cdot R^{*}\leqslant 2\cdot R\end{alineado}}

Todos los vértices de serán eliminados al final de la iteración, lo que significa que el ciclo terminará en un máximo de iteraciones y, por lo tanto, . $V_i$ $k=|Z^{*}|$ ${\ estilo de visualización | Z | \ leqslant k}$

Del lema se deduce que el algoritmo voraz se puede ejecutar hasta que el conjunto resultante sea menor que el requerido , usando la matriz de distancia para calcular los radios . Por lo tanto, la complejidad de tiempo general del algoritmo es y el factor de aproximación es . $Z$ $k$ $O(n^{4})$ $2$

Resolubilidad

Bajo la condición de que las clases P y NP no sean iguales, para ninguna no existe un algoritmo polinomial con un factor de aproximación . La prueba de esta afirmación se reduce a una reducción al problema del conjunto dominante : Démoslo como entrada al algoritmo que resuelve el problema del conjunto dominante. También deje para todos los bordes . Entonces contiene un conjunto dominante de tamaño si el conjunto contiene vértices y el radio ( ) es igual a . Si hubiera un algoritmo de aproximación con , entonces encontraría un conjunto dominante con exactamente el mismo factor de aproximación, lo cual es imposible. ${\ estilo de visualización r <2}$ $r$ ${\ estilo de visualización (G, k)}$ ${\ estilo de visualización c (e) = 1}$ ${\ estilo de visualización e \ en E (G)}$ $GRAMO$ $k$ $Z$ $k$ ${\ estilo de visualización \ nombre del operador {rad} (Z)}$ $una$ $r$ ${\mathcal {A}}$ ${\ estilo de visualización r <2}$ ${\mathcal {A}}(G,1,k,c)$

Véase también

El problema de colocar objetos con minimización de la suma de distancias (también conocido como "El problema de 1-mediana") con la mediana del conjunto de puntos como un caso especial
El problema de la colocación máxima de objetos (en la medida de lo posible, colocación de objetos dañinos)
El problema del k-centro
El problema de la k-mediana

Notas

Literatura

Nimrod Megido. El problema ponderado euclidiano de 1 centro // Matemáticas de la investigación operativa. — Hannover: Instituto de Investigación Operativa y Ciencias de la Gestión. - T. 8 , núm. 4 . — S. 498–504 . -doi : 10.1287/ moor.8.4.498 .
Abdelaziz Falta. Un problema de 1 centro en el plano con puntos de demanda uniformemente distribuidos // Cartas de investigación de operaciones. - Elsevier, 2006. - T. 34 , núm. 3 . — S. 264–268 . -doi : 10.1016/ j.orl.2005.04.011 .
R. Chandrasekaran. El problema de 1 centro euclidiano ponderado // Cartas de investigación de operaciones. - Elsevier, julio de 1982. - Vol. 1 , no. 3 . — S. 111–112 . - doi : 10.1016/0167-6377(82)90009-8 .
M. Colebrook, S. Alonso Gutiérrez, J. Sicilia. Un nuevo algoritmo para el problema indeseable de 1 centro en redes // Revista de la Sociedad de Investigación Operacional . - Palgrave Macmillan Journals, 2002. - V. 53 , no. 12 _ - S. 1357-1366 . doi : 10.1057 / palgrave.jors.2601468 . — .
Rainer E. Burkard, Helidon Dollani. Una nota sobre el problema robusto de 1 centro en árboles // Annals of Operations Research. - Editorial Académica Kluwer, 2002. - T. 110 , no. 1-4 . — págs. 69–82 . — ISSN 1572-9338 . -doi : 10.1023/A : 1020711416254 .