Universidad Federico Henríquez & Carvajal
(UFHEC)
Recinto la Romana, Rep. Dom.
FACULTAD DE CIENCIAS DE LAS INGENIERIA Y RECURSOS
NATURALES ESCUELA DE INGENIERIA INDUSTRIAL
CARRERA DE INGENIERIA INDUSTRIAL
Investigación de Operaciones II
TEMA:
PRACTICA #4
SUSTENTANTE:
Luis Guillermo Ledesma Espinal LR-2023-04780
Sección: LR-INI-450-LR07
Profesor: Jancy Manuel Cabral Santana
La Romana, Rep. Dom.
21/03/2025
[Link] maderera Wirehouse talará árboles en ocho zonas de la misma área.
Pero antes debe desarrollar un sistema de caminos de tierra para tener acceso
a cualquier zona desde cualquier otra. La distancia (en millas) entre cada par
de zonas es:
El problema es determinar los pares de zonas entre los que deben construirse
caminos para conectar todas con una longitud de caminos total mínima.
3
2.6
0.9
2 1.8 1.7 4
1.2 1.0 2.5
2.6 1.9 0.7
1.1 2.3 0.9
1.5
1.6
1.3
2.1
0.9
0.7
1 5
1.8
2.0 0.8
1.1 2.6
1.5
1.0
8
0.6
0.5 6
7
Interacción #1 Interacción #2
C= [1,5]⇒ 𝑐̃ [2,3,4,6,7,8] C= [1,5,4]⇒ 𝑐̃ [2,3,6,7,8]
Interacción #3 Interacción #4
C= [1,5,4,8]⇒ 𝑐̃ [2,3,6,7] C= [1,5,4,8,7]⇒ 𝑐̃ [2,3,6]
Interacción #5 Interacción #6
C= [1,5,4,8,7,6]⇒ 𝑐̃ [2,3] C= [1,5,4,8,7,6,3]⇒ 𝑐̃ [2]
Interacción #7
C= [1,5,4,8,7,6,3,2]⇒ 𝑐̃ []
Describa cómo se ajusta este problema a la descripción del problema del
árbol de expansión mínima
El problema que estamos analizando encaja perfectamente con el concepto
de árbol de expansión mínima en la teoría de grafos, ya que cumple con los
principios fundamentales de esta estructura. Aquí te explico por qué:
1. Conexión de Nodos
o Un árbol de expansión mínima garantiza que todos los nodos
de un grafo estén conectados.
o En nuestro caso, el problema plantea la necesidad de conectar
diferentes puntos (como zonas, ciudades o elementos dentro
de una red) de manera que todos puedan comunicarse sin
quedar aislados.
2. Minimización del Costo o Peso Total
o Cada conexión en un árbol de expansión mínima tiene un peso
asociado, que puede representar distancia, costo o tiempo, y el
objetivo es minimizar la suma de estos valores.
o En nuestro problema, buscamos establecer las conexiones
necesarias utilizando la menor cantidad de recursos posible,
evitando gastos innecesarios.
3. Evitar Ciclos o Redundancias
o Un árbol de expansión mínima es una estructura sin ciclos, lo
que significa que no hay caminos redundantes.
o Esto es clave en nuestro problema, ya que eliminar conexiones
innecesarias ayuda a optimizar el uso de recursos y a evitar
costos adicionales.
4. Selección Inteligente de Conexiones
o Algoritmos como Prim o Kruskal permiten construir un árbol
de expansión mínima seleccionando de manera estratégica las
conexiones más eficientes.
o En nuestro caso, el proceso de elegir cuidadosamente las
mejores conexiones sigue la misma lógica: se comparan las
alternativas y se seleccionan solo aquellas que garantizan la
conectividad con el menor costo posible.
[Link] gerente de operaciones de la empresa Lumax CxA debe de colocar un
sistema de cables que es obligatorio iniciar desde una cuidad O y debe
expandirse por varias ciudades hasta llegar a la cuidad, T. La siguiente red
muestra las ligaduras que tiene cada cuidad cuando se conecta con otra y en
los arcos se estima la cantidad de rollos de cables a usar.
Determine el árbol de mínima expansión de la red y calcule el mínimo de
rollos de cable a usar.
Interacción #1 Interacción #2 Interacción #3
C= [O,B]⇒ 𝑐̃ [A,C,E,D,F,G,H,I,T] C= [O,B,A]⇒ 𝑐̃ [C,E,D,F,G,H,I,T] C= [O,B,A,D]⇒ 𝑐̃ [C,E,F,G,H,I,T]
Interacción #4 Interacción #5 Interacción #6
C= [O,B,A,D,C]⇒ 𝑐̃ [E,F,G,H,I,T] C= [O,B,A,D,C,F]⇒ 𝑐̃ [E,G,H,I,T] C= [O,B,A,D,C,F,E]⇒ 𝑐̃ [G,H,I,T]
Interacción #7 Interacción #8 Interacción #9
C= [O,B,A,D,C,F,E,G]⇒ 𝑐̃ [H,I,T] C= [O,B,A,D,C,F,E,G,H]⇒ 𝑐̃ [I,T] C= [O,B,A,D,C,F,E,G,H,I]⇒ 𝑐̃ [T]
Interacción #10
C= [O,B,A,D,C,F,E,G,H,I,T]⇒ 𝑐̃ []