• Author / Uploaded
• Rocio Mejía

Citation preview

Investigación Operativa

05/09/2016

APLICACIONES

INVESTIGACIÓN OPERATIVA

1. Diseño de redes de transporte para minimizar el costo total de proporcionar las ligaduras (vías ferroviarias, carreteras, etc.) 2. Diseño de una red de tuberías para conectar varias localidades. 3. Determinación del programa de costo mínimo de los campos petrolíferos a refinerías y finalmente a los campos de distribución.

FLUJO MÁXIMO

MG. MG ROSMERI MAYTA H. 2016 05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

1


Se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es de obtener la máxima capacidad de flujo entre la fuente y el destino.

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

2

CARACTERISTICA

MODELO DE FLUJO MÁXIMO

05/09/2016

05/09/2016

3

1. Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino. 2. Los nodos restantes son nodos de trasbordo. 3. Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dado por la capacidad del arco. En la fuente, todos los arcos señalan hacia fuera. En el destino, todos señalan hacia el nodo. 4. El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto es, la cantidad que sale de la fuente o la cantidad que entra al destino.

05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

4

FLUJO MÁXIMO
El problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método símplex y usar cualquier software.

Red que transporta petróleo crudo:

05/09/2016

05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

Mg. Rosmeri Mayta H.

5

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

6

1

Investigación Operativa

05/09/2016

RED DE TRANSPORTE. TRANSPORTE Es el grafo finito sin anillo que cumple ciertas condiciones: 1. En una red de transporte, cada arco tiene asociado una capacidad C(u) ≥ 0. 2. Existe una fuente tal que el conjunto de los arcos incidentes es el conjunto vacío: W- (X0) = 0. 3. Existe un sumidero tal que el conjunto de los arcos incidentes al exterior, es vacío; es decir: W+ (Xn) = 0. 05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

7

ARCO SATURADO Se dice que un arco es saturado si C(i,j) = f(i,j) El flujo de la red es factible si cumple: 1. 0 ≤ f(i,j) ≤ C(i,j) 2. Conservación de flujo: 05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

9

FLUJO COMPLETO El flujo en la red es completo si toda la ruta o camino que va desde la fuente al sumidero contiene al menos un arco saturado.

05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

Mg. Rosmeri Mayta H.

FUENTE Es el único nodo que sólo tiene arcos de salida. SUMIDERO Es el único nodo que sólo tiene arcos de entrada. CAPACIDAD C(i,j) Es la máxima cantidad de producto que puede fluir por el arco (i,j). FLUJO DE ARCO f(i,j) Es la cantidad de producto que fluye por el arco (i,j). 05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

8

En cada nodo i : Flujo que entra en el nodo i = Flujo que sale en el nodo j ∑ f( k, i ) = ∑ f( i, j ) En la red : Flujo que sale de la fuente = Flujo que llega al sumidero ∑ f( X0, k ) = ∑ f( j, Xn ) = F

05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

10

Ejemplo:

X0 – 1 – 4 – Xn X0 – 3 – 5 – Xn CAPACIDAD RESIDUAL DE UN ARCO (I,J) Cr (i,j) = C(i,j) - f(i,j) Ejemplo. Cr (4,Xn) = C(4,Xn) - f(4,Xn) = 5 -3 = 2

11

05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

12

2

Investigación Operativa

05/09/2016

FORMULACIÓN DE UN PL PARA CALCULAR EL FLUJO MÁXIMO Dado una red sin anillos se trata de hallar el máximo flujo de la fuente al sumidero, sujeto a las capacidades de arco que forma la red y en el supuesto que exista una conservación de flujo. F.O. : Max ∑ Q(u) ∑ Q(u) u Є W + (X0) u Є W -(Xn) 1. Q(u) ≤ C(u) ; para todo u Є A 2. ∑ Q(u) = ∑ Q(u) u Є W + (X0) u Є W -(Xn) 05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

GRÁFICO

13

FORMULACIÓN DE UN PL PARA HALLAR EL FLUJO MÁXIMO F.O. : Max Z = Q(X0, X1) + Q(X3, X2) + Q(X0, X3) S. a : Q(X0, X1) ≤ C(X0, X1) Q(X0, X2) ≤ C(X0, X2) .... Q(X5, Xn) ≤ C(X5, Xn) En la red: Q(X0, X1) + Q(X3, X2) + Q(X0, X3) = Q(X4, Xn) + Q(X5, Xn) 05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

15

Si ya no se puede etiquetar el sumidero, Entonces ya se tiene el flujo máximo. Para etiquetar:

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

Mg. Rosmeri Mayta H.

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

14

En los nodos : Nodo 1: Q(X0, X1) = Q(X1, X4) 2 : Q(X0, X2) = Q(X2, X4) + Q(X2, X5) 3 : Q(X0, X3) = Q(X3, X4) + Q(X3, X5) …. MÉTODO DE FORD FULKERSON Procedimiento: 1.-Establecer un flujo de la fuente al sumidero. 2.-Tratar de etiquetar los vértices. 3.-Si existe etiqueta en el sumidero, asignar un flujo y regresar al paso 2. 05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

16

PROBLEMA Encuentre el flujo máximo de la fuente al sumidero en la siguiente red . a) Calcular el flujo máximo aplicando el algoritmo de Ford Fulkerson b) Realizar un PL para hallar el flujo máximo.

gjk : Capacidad no saturada del arco JK. Xij : Flujo asignado del arco IJ. dJ : Flujo que puede pasar aún por el vértice J. 05/09/2016

05/09/2016

17

05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

18

3

Investigación Operativa

05/09/2016

GRÁFICO DE LA RED
Maxz= XF1+XF2
S.a:
En cada nodo
XF1=X13+X14
XF1=X21+X24
X13=X38
X14+X24=X45
XF1+XF2=X35+X45 05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

19

05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

20

21

05/09/2016

ROSMERI MAYTA H. INVESTIGACION OPERATIVA

22


En la red
XF1+XF2=X35+X45
Por capacidad
XF1