Modelos de Operaciones I Asignación 4

UNIVERSIDAD DE ORIENTE

NÚCLEO DE ANZOÁTEGUI

 EXTENSIÓN REGIÓN CENTRO SUR

 DEPARTAMENTO DE INGENIERÍA DE SISTEMAS[pic 1]

[pic 2]

Modelos de Operaciones I

Asignación 4

Profesora:                                                                                                   Bachiller:

Arelina Ruiz                                                                     Luis González Ci: 27.143.015

Ensayo

El problema del flujo máximo es un problema de redes que consiste en determinar la máxima cantidad de flujo que puede ser enviada a lo largo de una red dirigida, esta dispone de una cierta capacidad por unidad de tiempo asociada a cada una de ella, es decir, que no se puede mandar todo el flujo de una vez si la red no tiene la capacidad. Para resolver estos problemas existen diversos métodos entre los cuales tenemos los siguientes:

• Método Ford Fulkerson
• Método WINQSB u otro software

El ejercicio que se va a usar como ejemplo es el siguiente:

[pic 3]

[pic 4][pic 5]

[pic 6][pic 7][pic 8][pic 9][pic 10]

[pic 11][pic 12][pic 13][pic 14]

[pic 15]

[pic 16][pic 17][pic 18]

[pic 19][pic 20]

[pic 21][pic 22]

[pic 23]

Donde 1 es el origen y 5 es el objetivo.

El método Ford Fulkerson consiste en los siguientes pasos:

1. Se escoge en el nodo origen el flujo que sea mayor en este ejercicio es 30 y va al nodo 3.
2. Se crea el identificador [30,1] para el nodo de transbordo, donde 30 es la capacidad de flujo y 1 el nodo de donde proviene la capacidad de flujo.
3. Se repite el proceso anterior, obteniendo otro nodo de transbordo [20,3].
4.  Luego de haber llegado al nodo destino se procede a calcular k y las nuevas capacidades

        K=min(30,20)

        K=20

        C12,21=(30-20,0+20)

        C12,21=(10,20)

        C35,53=(20-20,0+20)

C35,53=(0,20)

1. Una vez calculadas las capacidades, se reemplazan.

[pic 24]

[pic 25][pic 26]

[pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34]

...