López León Diego Alonso 201720408
Camacho Moreno Erica Yulieth 201721408
Chaparro Sánchez Leidy Marcela 201711435
INVESTIGACION MODELO P-MEDIANA
La localización de planta es el proceso de elegir un lugar en el espacio geográfico, para realizar las
operaciones de la organización. El proceso de ubicación del lugar adecuado para instalar una
planta industrial, requiere del análisis de diversos factores y de puntos de vista económicos,
sociales, tecnológicos y del mercado, entre otros.
Uno de los problemas de localización más profundamente estudiados es el problema de la p-
mediana. Las aplicaciones de este problema son numerosas (2), pues el problema de la p-mediana
y sus extensiones se han utilizado para ubicar óptimamente almacenes, fábricas, sucursales
bancarias, estaciones de ferrocarril, etc., utilizándose el término genérico de centro de servicio
para referirse a cualquiera de ellos, llamándose por tanto centro de servicio a cada uno de los
distintos puntos que componen una p-median.
EL PROBLEMA DE LA P-MEDIANA
Teniendo en cuenta que uno de los principales objetivos de cualquier organización es reducir los
costos que se generan con la realización de sus operaciones. (3) De esta manera, para minimizar
los costos de localización y distribución de una empresa se plantea el modelo de la p-mediana. en
el que a partir de un gráfico, donde el conjunto de vértices es un número finito, |V|= n. Se
establece wj como el peso asociado al vértice j∈V, denominado usualmente demanda, y l ij al peso
o distancia asociada a la arista que va del vértice i al j, siendo D={d ij} la matriz de distancias
asociada al algoritmo de Floyd- Warshall, y obtenida a partir de los l ij, que contiene el camino más
corto entre cualquier par de vértices del grafo.
El modelo p-mediana identifica ubicaciones para p nuevas instalaciones en algún espacio (como el
plano euclidiano o una red de carreteras) para atender n puntos de demanda, de modo que la
distancia ponderada total (o costo) entre las instalaciones y los puntos de demanda a los que
sirven es minimizado. Es una extensión de múltiples instalaciones del problema de Weber (Weber,
1909), que es ampliamente aceptado como el primer problema formalizado de ubicación de
instalaciones en la literatura. Los primeros tratamientos del problema de la P-mediana se deben a
Cooper (1963) y Hamiki (1995). ReVell y Swain (1970) proporcionaron una formulación de
programación entera para el problema discreto de p-mediana, que se da a continuación.
n n
{
min Z=∑ ∑ wi d ij x ij
i=1 j=1
}
S.A
López León Diego Alonso 201720408
Camacho Moreno Erica Yulieth 201721408
Chaparro Sánchez Leidy Marcela 201711435
n
( 1 ) ∑ xij=1 ∀ i
j=1
(2) x ij ≤ x jj ∀i , j
n
(3) ∑ x jj=¿ p ¿
j=1
(4) x ij ∈ {0,1 } ∀i , j
Donde,
Z= Costo total en el sistema producto del desplazamiento.
x ij= 1 si el punto i se asigna a la instalación ubicada en el punto j o 0 en caso contrario.
x jj = 1 si una instalación está ubicada en el punto j o 0 en caso contrario.
w i= Demanda total en la localización i .
d ij= Distancia de viaje entre los puntos i y j (Costo de viaje entre los puntos).
P= Número de instalaciones a ubicar.
n= Puntos de demanda
La función objetivo minimiza el costo total (fijo +variable) de establecer y operar la red. En la
restricción número 1 se estipula que cada nodo de demanda debe asignarse a una instalación. En
la restricción número 2 se estipula que ninguna planta puede abastecer más de lo que permite su
capacidad. La restricción 3 afirma que la suma total de instalaciones que pueden ser abiertas
debe ser igual a P. Y finalmente la restricción 4 refuerza el que cada planta abierta ( x ij =1) y
cerrada ( x ij =0).
La solución al modelo de programación matemática anterior identifica las ubicaciones de las
instalaciones y la asignación de los puntos de demanda a las instalaciones. En la solución óptima,
todos los puntos de demanda se atienden desde la instalación más cercana, la demanda no se
divide. El modelo asume que no existen limitaciones de capacidad en las instalaciones. Hay un
viaje separado para cada par de punto de demanda-instalación; los viajes a varios puntos de
demanda no se pueden combinar. Si bien estos supuestos parecen algo limitantes, el modelo p-
mediano es, de hecho, una herramienta de planificación muy útil para muchos sistemas de
distribución (o recopilación) de un solo nivel. Se puede utilizar para ubicar instalaciones de
producción o almacenamiento para dar servicio a una gran región, o para ubicar instalaciones
públicas (como bibliotecas) en una ciudad. Si se detecta al menos una solución mejorada, el
algoritmo toma lo mejor de todas esas soluciones mejoradas, las convierte en las soluciones
actuales y continúa buscando.
López León Diego Alonso 201720408
Camacho Moreno Erica Yulieth 201721408
Chaparro Sánchez Leidy Marcela 201711435
MATRIZ DE DISTANCIAS MÍNIMAS- ALGORITMO DE FLOYD- WARSHALL
El problema que intenta resolver este algoritmo es el de encontrar el camino más corto entre
todos los pares de nodos o vértices de un grafo. (4)Un ejemplo de aplicación se da al construir una
tabla con todas las distancias mínimas entre pares de ciudades de un mapa, indicando además la
ruta a seguir para ir de la primera ciudad a la segunda. Este es uno de los problemas más
interesantes que se pueden resolver con algoritmos de grafos.
An (i, j) = Longitud del camino mínimo que hay desde la ciudad i hasta la ciudad j
suponiendo que podemos pasar por cualquier ciudad intermedia.
A0 (i, j) = Longitud del camino mínimo que hay desde la ciudad i hasta la ciudad j,
suponiendo que no podemos pasar por ninguna ciudad intermedia.
“Si no hay arista entre dos vértices determinados, se considera + ∞”
En otras palabras, y como se puede observar en la imagen, la matriz de distancias refleja en una
distancia las rutas más cortas entre vértices que pueden indicar puntos específicos de un mapa. El
problema de la p-mediana consiste en encontrar p puntos del plano de modo que se minimice la
distancia total ponderada entre estos puntos y los vértices del grafo.
López León Diego Alonso 201720408
Camacho Moreno Erica Yulieth 201721408
Chaparro Sánchez Leidy Marcela 201711435
EJERCICIO DE APLICACIÓN
Como consecuencia de la masiva ocupación de las UCI (unidades de cuidados intensivos) en los
hospitales por tema COVID-19, el gobierno desea anticiparse a un colapso total en la atención de
los hospitales, creando un plan de contingencia, decidiendo algunos puntos en los cuales
construirán centros de emergencia especializados en tratar pacientes con este virus en las zonas
más afectadas. En el mapa que se presenta a continuación se identifican las zonas que pueden son
más afectadas y los tiempos de transporte esperados entre cada una de ellas, el gobierno
considera que no es necesario abrir todos los centros de emergencia especializados y los afectados
tendrían que movilizarse para recibir la respectiva atención.
El gobierno desea ubicar los centros de emergencia necesarios en busca de minimizar los costos de
localización y distribución. En el mapa que se presenta a continuación, se identifican las zonas
donde se podría ubicar dichos centros y las personas afectadas en cada uno de esos puntos.
20
37
B
12
C
25
F 14
36 D
17
8
E
Matriz de distancias mínimas
López León Diego Alonso 201720408
Camacho Moreno Erica Yulieth 201721408
Chaparro Sánchez Leidy Marcela 201711435
A B C D E F
A 0 20 32 45 53 37
B 63 0 12 25 33 26
C 51 69 0 44 36 14
D 62 25 37 0 8 25
E 54 33 31 8 0 17
F 37 57 14 58 50 0
A B C D E F
Demanda 30 50 60 90 100 120
Costo de 16 20 16 20 16 24
atención
Costo 10000 20000 15000 19000 22000 21000
apertura
Formulación:[ CITATION Mar \l 9226 ]
Conjuntos
i: conjunto de nodos a atender (i)
j: conjunto de nodos a abrir (j)
Parámetros:
w i: Demanda del nodo i (und/t)
d ij: Distancia entre el nodo de demanda i y el nodo candidato de localización j (Km)
r i : Costo de enviar al nodo de demanda i y desde el nodo de localización j ($/Km*und)
f j :Costo de apertura nodo j ($)
Variables:
{1 si0seenabre
X j=
laubicacion j
caso contrario
1 si el punto de demandai es atendido por la ubicacion j
Y ={
ij
0 en caso contrario
López León Diego Alonso 201720408
Camacho Moreno Erica Yulieth 201721408
Chaparro Sánchez Leidy Marcela 201711435
Bibliografía
1. Garcia, J. A. (2012). Relajacion lagrangeana para el "problema de particionamiento de
areas geograficas". Revista de Matematica: Teorıa y Aplicaciones, 169-181.
2. Hakimi, S. (1964). Optimum distribution of switching centers in a communications network.
Operations Research.
3. María José Canós, M. M. (n.d.). TÉCNICAS DE OPTIMIZACIÓN ROBUSTA APLICADAS AL
PROBLEMA DE LA P-MEDIANA EN CONDICIONES DE INCERTIDUMBRE. Valencia:
Universidad de Valencia.
4. Villalobos, A. R. (2010). Grafos - software para la construcción, edición y análisis de grafos.
Madrid: Bubok publishing S.L.
5. Drezner, Z., & Hamacher, H. W. (Eds.). (2001). Facility location: applications and theory.
Springer Science & Business Media.
