Escuela Superior Politecnica Del Litoral

Escuela Superior Politécnica del Litoral
Facultad de Ciencias Sociales y Humanísticas
Gerencia de
Operaciones I
Preparado por: Ph.D. David Sabando Vera

[email protected]
1
Modelos de Redes
• Problema del árbol de expansión

mínima.
• Problema del flujo máximo
• Problema de la ruta más corta
2
Problema del árbol de expansión mínima.
La técnica del árbol de expansión mínima
implica conectar todos los puntos de una red,
al tiempo que minimiza la distancia entre
ellos. Se aplica, por ejemplo, en las
compañías telefónicas para conectar entre sí
varios teléfonos minimizando la longitud
total del cable.
3
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.
4
Ejemplo:
Considere la compañía Lauderdale Construction, que desarrolla un

proyecto habitacional de lujo en Panama City Beach, Florida.
Melvin Lauderdale, dueño y presidente de Lauderdale
Construction, tiene que determinar la forma menos costosa de
suministrar agua y electricidad a cada casa. La red de viviendas se
muestra en la figura siguiente.
5
6
Solución.
7
8
Problema del flujo máximo..
El problema del flujo máximo implica determinar la

cantidad máxima de material que en una red puede fluir de
un punto (el origen) a otro (el destino final). Los ejemplos
de este tipo de problema incluyen determinar el número
máximo de autos que circulan por un sistema de carreteras,
la cantidad máxima de líquido que fluye por una red de
tuberías y la cantidad máxima de datos que pueden fluir por
una red de cómputo.
9
Cuatro pasos de la técnica del flujo máximo
1. Elegir cualquier ruta del inicio (origen) al final (destino) con
algún flujo. Si no existe una trayectoria con flujo, entonces, se
encontró la solución óptima.
2. Determinar el arco en esta ruta con la menor capacidad de flujo
disponible. Llamar C a tal capacidad, lo cual representa la capacidad
adicional máxima que puede asignarse a esta ruta.
3. Para cada nodo en esta ruta, disminuir en la cantidad C la
capacidad del flujo en la dirección del flujo. Para cada nodo en esta
ruta, incrementar la capacidad del flujo en la cantidad C en la
dirección contraria.
4. Repetir los pasos anteriores hasta que no sea posible aumentar el
flujo.
10
Ejemplo:
Waukesha, un pequeño pueblo en Wisconsin, está en el proceso

de desarrollar un sistema de caminos para el área del centro.
Bill Blackstone, uno de los planeadores de la ciudad, quiere
determinar el número máximo de automóviles que pueden fluir
por el pueblo de oeste a este. La red de caminos se ilustra en la
figura siguiente:
11
12
13
14
Problema de la ruta más corta
El objetivo del problema de la ruta más corta es encontrar la

menor distancia para ir de un lugar a otro. En una red, esto
suele implicar la determinación de la ruta más corta de un nodo
a cada uno de los otros nodos. Este problema se resuelve con la
técnica de la ruta más corta.
15
Pasos de la técnica de la ruta más corta
1. Encontrar el nodo más cercano al origen (planta). Colocar
la distancia en un cuadro al lado del nodo.
2. Encontrar el siguiente nodo más cercano al origen (planta)
y poner la distancia en un cuadro al lado del nodo. En algunos
casos, deberán revisarse varias rutas para encontrar el nodo
más cercano.
3. Repetir este proceso hasta que se haya revisado la red
completa. La última distancia en el nodo final será la distancia
de la ruta más corta. Debería observar que la distancia
colocada en el cuadro al lado de cada nodo será la distancia de
la ruta más corta a ese nodo. Tales distancias se usan como
resultados parciales para encontrar el siguiente nodo más
cercano.
16
Ejemplo:
Todos los días, Ray Design debe transportar camas,

sillas y otros muebles de la fábrica al almacén; necesita
pasar por varias ciudades y Ray desea encontrar la ruta
con la distancia más corta. La red de carreteras se
muestra en la figura siguiente:
17
18
19
20
21

Escuela Superior Politecnica Del Litoral

Cargado por

Copyright:

Formatos disponibles

Escuela Superior Politecnica Del Litoral

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Escuela Superior Politecnica Del Litoral

Cargado por

Copyright:

Formatos disponibles

Escuela Superior Politécnica del Litoral

Facultad de Ciencias Sociales y Humanísticas

Preparado por: Ph.D. David Sabando Vera

• Problema del árbol de expansión

Considere la compañía Lauderdale Construction, que desarrolla un

El problema del flujo máximo implica determinar la

Waukesha, un pequeño pueblo en Wisconsin, está en el proceso

El objetivo del problema de la ruta más corta es encontrar la

Todos los días, Ray Design debe transportar camas,

También podría gustarte