Flujo Maximo

UNIVERSIDAD TECNOLÓGICA DE PUEBLA

INGENIERIA EN DESARROLLO E INNOVACIÓN EMPRESARIAL

MATERIA:

INVESTIGACIÓN DE OPERACIONES 2

EJERCICIOS:

FLUJO MAXIMO

Índice

Portada…………………………………………………………1

Índice…………………………………………………………...2

Foto y frase……………………………………………………3

Teoría…....……………………………………………………..4

Ejercicio 1……………………………………………………..5

Ejercicio 2……………………………………………………..6

Ejercicio 3……….…………………………………………….8

Ejercicio 4………...……………………………………….....10

Teoría Flujo Máximo

Existe un flujo que viaja desde un único lugar de origen hacia un único lugar de destino a través de arcos que conectan nodos intermediarios. Los arcos tienen una capacidad máxima de flujo y se trata de enviar desde la fuente al destina la mayor cantidad posible de flujo.

Hay problemas donde lo importante es la cantidad de flujo que pasa a través de la red como por ejemplo: en las líneas de oleoductos, redes eléctricas o de transmisión de datos. Por esta razón en dichos problemas se determina el flujo máximo que pasa a través de una red.

Definiciones básicas

Flujo: Circulación de unidades homogéneas de un lugar a otro.

Capacidad de flujo: es la capacidad de unidades que pueden entrar por el nodo fuente y salir por el nodo destino.

Origen o fuente de flujo: nodo por el cual el flujo ingresa.

Destino o Sumidero de flujo: nodo por el cual el flujo sale.

Capacidades residuales: capacidades restantes unas vez que el flujo pasa el arco.

Ford Fulkerson

Para la resolución de problemas de flujo máximo se requiere el uso del método Ford Fulkerson. Este método propone buscar caminos en los que se pueda aumentar el flujo hasta que se alcance el flujo máximo, la idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos de origen y destino.

• El flujo es siempre positivo y con unidades enteras.

• El flujo a través de un arco es menor o igual que la capacidad.

• El flujo que entra en un nodo es igual al que sale de él.

Ejercicio 1

Mailo es un pollero y necesita entregar a los Estados Unidos 60 personas por diferentes caminos sin embargo no todos los caminos tienen la mima capacidad para llevar a sus clientes ¿cuál sería la distribución sobre cada camino?

Modelado grafico WinQSB 1

Solución óptima WinQSB 1

Solución grafica WinQSB 1

Solución Invop 1

Solución

Con esta distribución se cumple con el 100% de entrega de clientes a USA por lo cual se presenta la siguiente distribución:

1. México-Camino 3-USA = 10

2. México-Camino

...