Date post: | 10-Nov-2015 |
Category: |
Documents |
Upload: | milton-alfaro |
View: | 16 times |
Download: | 0 times |
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 1
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
1
INVESTIGACIN OPERATIVA
FLUJO MXIMO
MGMGMGMG. ROSMERI MAYTA H.
2015
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
2
APLICACIONES
1. Diseo de redes de transporte paraminimizar el costo total de proporcionarlas ligaduras (vas ferroviarias,carreteras, etc.)
2. Diseo de una red de tuberas paraconectar varias localidades.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
3
APLICACIONES3- Determinacin del programa de costo mnimo
de los campos petrolferos a refineras yfinalmente a los campos de distribucin.
4.- Se pueden enviar petrleo crudo y productosderivados de la gasolina en buques tanque,oleoductos y/o camiones.
5.- Adems de la disponibilidad de la ofertamxima en los campos petrolferos y losrequisitos de demanda mnima en los centrosde distribucin, deben tomarse en cuentarestricciones sobre la capacidad de lasrefineras y los modos de transporte.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
4
MODELO DE FLUJO MXIMO
Se trata de enlazar un nodo fuente y unnodo destino a travs de una red de arcosdirigidos. Cada arco tiene una capacidadmxima de flujo admisible. El objetivo esde obtener la mxima capacidad de flujoentre la fuente y el destino.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
5
CARACTERISTICA Todo flujo a travs de una red conexa dirigida se origina
en un nodo, llamado fuente, y termina en otro nodollamado destino.
Los nodos restantes son nodos de trasbordo. Se permite el flujo a travs de un arco slo en la
direccin indicada por la flecha, donde la cantidadmxima de flujo est dado por la capacidad del arco. Enla fuente, todos los arcos sealan hacia fuera. En eldestino, todos sealan hacia el nodo.
El objetivo es maximizar la cantidad total de flujo de lafuente al destino. Esta cantidad se mide en cualquierade las dos maneras equivalentes, esto es, la cantidadque sale de la fuente o la cantidad que entra al destino.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
6
El problema de flujo mximo se puedeformular como un problema deprogramacin lineal, se puede resolvercon el mtodo smplex y usar cualquiersoftware.
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 2
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
7
FLUJO MXIMO
Red que transporta petrleo crudo:
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
8
RED DE TRANSPORTERED DE TRANSPORTERED DE TRANSPORTERED DE TRANSPORTE.
Es el grafo finito sin anillo que cumple ciertascondiciones:
1. En una red de transporte, cada arco tieneasociado una capacidad C(u) 0.
2. Existe una fuente tal que el conjunto de losarcos incidentes es el conjuntovaco: W- (X0) = 0.
3. Existe un sumidero tal que el conjunto de losarcos incidentes al exterior, esvaco; es decir: W+ (Xn) = 0.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
9
FUENTEEs el nico nodo que slo tiene arcos de salida.
SUMIDEROEs el nico nodo que slo tiene arcos de entrada.
CAPACIDAD C(i,j)Es la mxima 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).
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
10
ARCO SATURADOSe 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. Conservacin de flujo:
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
11
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
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
12
FLUJO COMPLETOEl 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.
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 3
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
13
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
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
14
FORMULACIN DE UN PL PARA CALCULAR EL FLUJO MXIMO
Dado una red sin anillos se trata de hallar elmximo flujo de la fuente al sumidero, sujetoa las capacidades de arco que forma la red yen el supuesto que exista una conservacinde flujo.
F.O. : Max Q(u) Q(u) u W+ (X0) u W-(Xn)
1. Q(u) C(u) ; para todo u A2. Q(u) = Q(u)
u W+ (X0) u W-(Xn)
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
15
GRFICO
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
16
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)
FORMULACIN DE UN PL PARA HALLAR EL FLUJO MXIMO
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
17
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).
MTODO DE FORD FULKERSONProcedimiento:1.-Establecer un flujo de la fuente al sumidero.2.-Tratar de etiquetar los vrtices.3.-Si existe etiqueta en el sumidero, asignar un
flujo y regresar al paso 2.07/04/2015 ROSMERI MAYTA H.
INVESTIGACION OPERATIVA 18
Si ya no se puede etiquetar el sumidero,Entonces ya se tiene el flujo mximo.Para etiquetar:
gjk : Capacidad no saturada del arco JK.Xij : Flujo asignado del arco IJ.dJ : Flujo que puede pasar an por elvrtice J.
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 4
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
19
PROBLEMA
Encuentre el flujo mximo de la fuente al sumidero en la siguiente red .
a) Calcular el flujo mximo aplicando el algoritmo de Ford Fulkerson
b) Realizar un PL para hallar el flujo mximo.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
20
GRFICO DE LA RED
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
21
Maxz= XF1+XF2
S.a:En cada nodoXF1=X13+X14XF1=X21+X24X13=X38X14+X24=X45XF1+XF2=X35+X45
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
22
En la redXF1+XF2=X35+X45Por capacidadXF1
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 5
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
25
CORTE DE LA RED
Corte: se define como corte a una seriede arcos cuya supresin de la red causaun interrupcin completa del flujo entre losnodos del punto de origen y del sumidero.
Capacidad de corte: Es igual a la sumade las capacidades de los arcosasociados.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
26
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
27
Y X , X = conjunto de vrticesXo Y A = conjunto de arcosW (Y)El corte C1 XC1 = {Xo}Arcos incidentes a C1W-(C1) ={ (x1,x2) ,(X1,X4),(X1,X3)}
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
28
Capacidad de corte:Q[ W-(c1)] = c(u)Teorema fundamental de flujoPara una red de transporte dada, el valor
mximo de flujo es igual a la capacidad de corte mnimo
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
29
Q[w-(c1)]= c(u)= 2+10+4 = 16Q[w-(c2)]= c(u)= 6+9 = 15Q[w-(c3)]= c(u)= 5+8+7+1=21Q[w-(c4)]= c(u)= 1+7+6=14
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
30
Aplicando el teorema encontramos que el flujo mximo es de : 14
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 6
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
31
Problema
Se tiene siete asentamiento humanos yse quiere instalar tuberas para agua.
En la siguiente red se encuentra losdatos. Calcular el flujo mximo que ira delA.H 1 al A.H 7
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
32
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
33
a) Caminos: 1 2 5 7 Min {2, 5, 6} = 21 4 5 7 Min {10, 8, 4} = 4 1 4 6 7 Min {6, 7, 9} = 61 3 4 6 7 Min {4, 3, 1, 3} = 11 3 6 7 Min {3, 1, 2} = 1_
14b) W-(C1) = C12 + C14 + C13 = 2+10+4 = 16W-(C2) = C57 + C67 = 6+9 = 15W-(C3) = C25 + C45 + C46 + C36 = 5+8+7+1
= 21W-(C4) = C57 + C46 + C36 = 6+7+1 = 14
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
34
Ejemplo:Se tiene la siguiente red con sus respectivascapacidades. Determinar el flujo mximo a travs de lared.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
35
Camino: 1 2 4 7 = Min { 7 , 8 , 4 } = 4 Camino: 1 2 5 7 = Min { 3 , 4 , 7 } = 3 Camino: 1 3 5 7 = Min { 10 , 3 , 7 } = 3 Camino: 1 3 - 2 5 7 = Min { 7 , 8 , 1 , 1 } = 1 Camino: 1 3 6 7 = Min { 6 , 3 , 5 } = 4 14 Respuesta: El flujo mximo es: 14
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
36
RED:
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 7
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
37
CORRIDA CON UN SOFTWARE
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
38
PROGRAMACION EN LINGO
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
39
PROBLEMA DE FLUJO MXIMOTres refineras mandan un producto
petrolero hacia dos terminales dedistribucin por una red de oleoductos.Toda la demanda que no se puedesatisfacer por la red se adquiere de otrasfuentes. La red de tuberas contiene tresestaciones de bombeo, como se ve en lafigura.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
40
RED
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
41
El producto va por la red en la direccinque indican las flechas. La capacidad decada segmento de tubera se vedirectamente en los arcos, y esta enmillones de barriles por da. Determinar elFlujo Mximo de producto que circula porla red,
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
42
Red
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 8
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
43
PROGRAMACIN EN LINGOFLUJO MXIMO !PROBLEMA DE FLUJO MAXIMO; SETS: NODES/1..10/; ARCS(NODES,NODES) /1,2 1,3 1,4 2,5 3,5 3,6 3,7 4,5 5,6 5,7 5,8 6,7 6,9 7,8 7,9 8,10 9,10 10,1/ :CAPACIDAD,FLUJO; ENDSETS MAX=FLUJO(10,1); @FOR(ARCS(I,J):FLUJO(I,J)
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 9
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
49
Representacin de la red:
X i j : Es el nmero de unidades de flujo enviado delnodo i al nodo j.Ci j : Costo de transportar 1 unidad de producto delnodo i al nodo j.Ui j : Capacidad mxima del arco (i, j).bi j : Flujo neto en el nodo i ( salida entrada ) 07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA 50
bi > 0 Si el nodo i es un punto de oferta.bi < 0 Si el nodo i es un punto de demanda..bi = 0 Si el nodo i es un punto de
transbordo.Condicin:En una red de costo mnimo una condicin
necesaria para que tenga solucin factiblees:
bi = 0 ( oferta = demanda )
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
51
EJEMPLO:
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
52
Formulando:Min Z = 4 X12 + 5 X13 + X 23S.a:
X12 + X13 = 13 Nodo 1- X12 + X23 = 0 Nodo 2- X13 - X23 = -13 Nodo 3
X12 8 X13 7 X23 10Xi j 0
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
53
Formulacin de un PL para un red F:O Min Z = C i j . X i jS. A: X i j - X ki = bi
X i j U i jX i j 0
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
54
PROBLEMA:En la siguiente red: Realizar un PL para hallar el flujo mximo a mnimo costo.
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 10
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
55
Formulacin de un PL para hallar el Flujomximo a minimo costo
Min Z = 4 X12 + 2 X24 + 3X 13 + 5X34 + 2 X32
S.A: X12 + X13 = 11 Nodo 1
X24 - X12 - X32 = -8 Nodo 2X34 + X32 - X13 = 9 Nodo 3
- X24 - X34 = -12 Nodo 4
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
56
2 X12 80 X13 60 X32 50 X24 123 X34 11Xij 0
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
57
PROBLEMA FLUJO MXIMO La compaa de gaseosas ABC posee 3 plantas
con capacidad de produccin de 20, 30 y 15 milcajas las cuales deben ser distribuidas a 5centros distribucin (CD). La capacidad deentrega de los CD a los intermediarios de ventason de 10, 10, 15, 25 y 5 mil cajas semanal. Lacapacidad de transporte de las plantas a los CDes como sigue:
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
58
SOLUCION EN LINGO
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
59
Datos:
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
60
Grafico
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 11
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
61
SOLUCIN
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
62
CORRIDA EN LINGO
Global optimal solution found at step: 21
Objective value: 63.00000
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
63
PROBLEMA
Los capuleto, Prez, Jurez, y los Anastacios sevan a un da de campo familiar anual se disponede 4 mviles para transportar a las familias. Enlos automviles caben los siguientes nmerosde personas: automvil 1 , 4; automvil 2,3;automvil 3,3; automvil 4,4. Hay 4 personasen cada familia y ningn automvil puede llevarms de 2 personas de cualquier familia.Formule el problema de cmo transportar elnmero mximo posible de personas al pueblo.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
64
DIAGRAMA DE LA RED
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
65
SOLUCION
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
66
PROGRAMACION EN LINGO
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 12
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
67
Solucin en lingo
Global optimal solution found at step: 18
Objective value: 14.00000
ProblemaCuatro fabricas producen cuatro tipos de
juguetes, la tabla nos muestra los juguetesque producen cada una de ellas.Las capacidades diarias de las 4 fabricasson 250, 180, 300 y 100 juguetesrespectivamente. Las demandas diarias delos 4 juguetes son 200, 150, 350 y 100unidades. Se requiere que se satisfaga lamayor parte de las demandas de los 4juguetes.07/04/2015 ROSMERI MAYTA H.
INVESTIGACION OPERATIVA 68
Fabrica Juguetes
1 1, 2, 3
2 1, 3, 4
3 3, 4, 2
4 1, 2, 3, 4
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
69 07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
70
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
71
Codificacin en Lingo
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
72
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 13
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
73
PROBLEMA FLUJO MXIMO A MNIMO COSTO
Determinar el flujo mximo a mnimo costo en la siguiente red.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
74
RED: Solucin con un software y programacin en lingo
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
75 07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
76
CORRIDA
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
77
Programacin en lingo
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
78
Resultados de la corrida
Global optimal solution found at step: 8
Objective value: 590.0000
ROSMERI MAYTA 07/04/2015
INVESTIGACION OPERATIVA 14
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
79
PROBLEMA
Se tiene dos fbricas y tres centros dedistribucin, en cada arco se indican lascapacidades y los costos.
Formular un PL para calcular el flujomximo a costo mnimo.
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
80
Grfico
07/04/2015 ROSMERI MAYTA H. INVESTIGACION OPERATIVA
81
Formulacin de un PL F.O: MIN. Z = 8X24 + 4X25 + 6X26+ 7X35 + 4X36 S.A: X12 + X13 = 49 -X47 X57 X67 = -49 Capacidad de arco X12