Scribd
Cargar
67 vistas21 páginas

Modelos de Redes y Árboles de Expansión

El documento describe conceptos básicos de redes como nodos, arcos y rutas. Luego, presenta tres problemas comunes de redes: el problema del árbol de expansión mínima, el problema del flujo máximo y el problema de la ruta más corta. Finalmente, incluye ejemplos para ilustrar cómo aplicar la técnica del árbol de expansión mínima para encontrar la red más económica para proporcionar servicio de cable o oleoductos entre diferentes ubicaciones.

Cargado por

peraltaluis1499
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
67 vistas21 páginas

Modelos de Redes y Árboles de Expansión

El documento describe conceptos básicos de redes como nodos, arcos y rutas. Luego, presenta tres problemas comunes de redes: el problema del árbol de expansión mínima, el problema del flujo máximo y el problema de la ruta más corta. Finalmente, incluye ejemplos para ilustrar cómo aplicar la técnica del árbol de expansión mínima para encontrar la red más económica para proporcionar servicio de cable o oleoductos entre diferentes ubicaciones.

Cargado por

peraltaluis1499
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

Conceptos Básicos

3 6
• Nodos 1
5
2
• Arcos 7
• Rutas 4

¿Cuántas rutas posibles entre dos nodos si todos están


interconectados?

1 2 5 16
Modelos de redes
Las redes sirven para modelar una
amplia gama de problemas. En temas
anteriores vimos problemas de
transporte, asignación modelados como
redes.

En esta sección se estudiarán los


siguientes problemas de redes: el
problema del árbol de expansión
mínima, el problema del flujo máximo y
el problema de la ruta más corta.
Tomado del libro Métodos cuantitativos para los
negocios, Render, stair y Hanna. undécima edición
•Pasos para la técnica del árbol de expansión mínima
•1. Seleccionar cualquier nodo en la red.
•2. Conectar este nodo con el nodo más cercano que
minimice la distancia total.
•3. Considerar todos los nodos que están conectados,
encontrar y conectar el nodo más cercano que no esté
conectado. Si hay un empate en el nodo más cercano,
seleccionar uno de manera arbitraria. Un empate sugiere que
existe más de una solución óptima.
•4. Repetir el paso 3 hasta que todos los nodos estén
conectados.
Primera iteración
Ejemplo 6.2-1
Midwest TV Cable Company va a proporcionar servicio de cable a cinco
desarrollos habitacionales. La figura 6.6 ilustra las posibles conexiones de TV a las
cinco áreas, con las millas de cable
anexadas a cada arco. El objetivo es determinar la red de cables más económica.
Tomado de Investigación de operaciones de
Taha
El algoritmo se inicia en el nodo 1 (en realidad, cualquier otro nodo puede ser un punto
de
inicio), el cual da por resultado
Las iteraciones del algoritmo se resumen en la figura 6.7. Los arcos delgados
proporcionan todos
los candidatos entre C y . Los arcos gruesos son los vínculos permanentes del conjunto
conectado C, y el arco de rayas es el nuevo vínculo (permanente) agregado en cada
iteración. Por
ejemplo, en la iteración 1, la rama (1, 2) es el vínculo más corto (5 1 milla) entre todas
las ramas
candidatas del nodo 1 a los nodos 2, 3, 4, 5 y 6 en el conjunto no conectado . De ahí que
el
vínculo (1, 2) se hace permanente y j* 5 2, de lo cual resulta
El árbol de mínima expansión que se muestra en la iteración 6 de la figura 6.7 da la
solución. Las
millas de cable mínimas resultantes que se necesitan para proporcionar el servicio de
Ejemplo
La figura 6.9 da la distancia en millas de los vínculos
factibles que conectan nueve cabezales de pozos de
gas natural localizados a una cierta distancia de la
costa con un punto
de distribución costero. Como el cabezal del pozo 1 es
el más cercano a la costa, dispone de una suficiente
capacidad de bombeo y almacenamiento para
bombear la producción de los ocho pozos restantes al
punto de distribución. Determine la red de oleoductos
mínima que vincule los cabezales de los pozos al punto
de distribución.

También podría gustarte