21 flujo maximo

8/13/2019 21 Flujo Maximo

1/88

Modelos de Redes: ProblemaModelos de Redes: Problemadel flujo mdel flujo mximoximo

M. En C. Eduardo Bustos FarM. En C. Eduardo Bustos Farasas


2/88

2

Problema del flujo mProblema del flujo mximoximo


3/88

Problema del flujo mProblema del flujo mximoximo Este modelo se utiliza para reducir losEste modelo se utiliza para reducir los

embotellamientos entre ciertos puntos de partida yembotellamientos entre ciertos puntos de partida ydestino en una red.destino en una red.

Existe un flujo que viaja desde unExiste un flujo que viaja desde un nico lugar denico lugar deorigen hacia unorigen hacia un nico lugar destino a travnico lugar destino a travs de arcoss de arcosque conectan nodos intermediosque conectan nodos intermedios

Cada arco tiene una capacidad que no puede serCada arco tiene una capacidad que no puede serexcedidaexcedida

La capacidad no debe ser necesariamente la mismaLa capacidad no debe ser necesariamente la mismapara cada direccipara cada direccin del arco.n del arco.


4/88


5/88

5

En este tipo de problemas se intentaEn este tipo de problemas se intentaconducir el flujo por las ramas o arcosconducir el flujo por las ramas o arcosde la red en formade la red en forma ptima, aunqueptima, aunque

dicho flujo estdicho flujo est limitado porlimitado porrestricciones diversas tales como:restricciones diversas tales como:

condiciones de la carpeta asfcondiciones de la carpeta asfltica,ltica,didimetros de tubermetros de tubera, etc.a, etc.

Al lAl lmite mmite mximo de flujo de una ramaximo de flujo de una ramase le denominarse le denominar capacidad de flujo.capacidad de flujo.


6/88

6

Se quiere transportar la mSe quiere transportar la mxima cantidad de flujo desdexima cantidad de flujo desdeun punto de partida (fuente) o un punto final (pozo)un punto de partida (fuente) o un punto final (pozo)ieie..

Al respecto diremos que existen muchos algoritmosAl respecto diremos que existen muchos algoritmosespecializados para dar soluciespecializados para dar solucin a losn a los P.F.MP.F.M..


7/88

7

ObservaciObservacin:n:

1.Se debe considerar una red dirigida.1.Se debe considerar una red dirigida.2.Tiene una fuente y un pozo.2.Tiene una fuente y un pozo.3.Los otros nodos son de trasbordo.3.Los otros nodos son de trasbordo.4.Capacidad de los arcos.4.Capacidad de los arcos.

5.El objetivo es determinar el patr5.El objetivo es determinar el patrn factible de flujo a travn factible de flujo a travs de las de lared que maximice el flujo total desde la fuente de destino.red que maximice el flujo total desde la fuente de destino.


8/88

DefiniciDefinicin del Probleman del Problema

-- Existe un nodo origen (con el nExiste un nodo origen (con el nmero 1), del cual los flujosmero 1), del cual los flujosemanan.emanan.

-- Existe un nodo terminal (con el nExiste un nodo terminal (con el nmero n), en el cual todos losmero n), en el cual todos losflujos de la red son depositados.flujos de la red son depositados.

-- Existen nExisten n--2 nodos (2 nodos (nnmeradosmerados del 2, 3,....,ndel 2, 3,....,n--1), en el cual el1), en el cual elflujo que entra es igual al flujo que sale.flujo que entra es igual al flujo que sale.

-- La capacidad CLa capacidad Cijij que transita del nodo i al nodo j, y laque transita del nodo i al nodo j, y lacapacidadcapacidad CCjiji para la direccipara la direccin opuesta.n opuesta.


9/88

El objetivo es encontrar la mEl objetivo es encontrar la mximaximacantidad de flujo que salga del nodocantidad de flujo que salga del nodo1 al nodo n sin exceder la capacidad1 al nodo n sin exceder la capacidadde los arcos.de los arcos.


10/88

10

El problema consiste en encontrar laEl problema consiste en encontrar lammxima cantidad de flujo total quexima cantidad de flujo total quepuede circular a travpuede circular a travs de la red en unas de la red en unaunidad de tiempo.unidad de tiempo.

ElEl nico requerimiento en ellos es quenico requerimiento en ellos es quepara cada nodo (que no sea la fuente opara cada nodo (que no sea la fuente oel destino) la relaciel destino) la relacin de equilibrio deben de equilibrio debe

cumplirse:cumplirse:

flujo que sale = flujo que entraflujo que sale = flujo que entra


11/88


12/88

12

El algoritmo de flujo mEl algoritmo de flujo mximo se fundamentaximo se fundamentaen pasos de sentido comen pasos de sentido comn: encontrar unn: encontrar uncamino que inicie en la fuente y concluya encamino que inicie en la fuente y concluya enlala antifuenteantifuente, que tenga capacidad de flujo en, que tenga capacidad de flujo enel sentido deseado y mayor a cero para todasel sentido deseado y mayor a cero para todaslas ramas que integran el camino o ruta.las ramas que integran el camino o ruta.

Debemos continuar buscando caminos queDebemos continuar buscando caminos quevayan de fuentes a depvayan de fuentes a depsitos y que sigansitos y que siganteniendo capacidad mayor a cero para todasteniendo capacidad mayor a cero para todaslas ramas en el sentido del flujo.las ramas en el sentido del flujo.


13/88


14/88

14

EJEMPLO 1EJEMPLO 1

Flujo mFlujo mximoximo


15/88

15

Una ciudad es atravesada por una redUna ciudad es atravesada por una redinterestatal de carreteras de norte a sur queinterestatal de carreteras de norte a sur quele permite alcanzar un nivel de 15,000le permite alcanzar un nivel de 15,000

vehvehculos/hora en el horarioculos/hora en el horariopicopico.. Debido a un programa de mantenimientoDebido a un programa de mantenimiento

general, el cual exige cerrar dichas vgeneral, el cual exige cerrar dichas vas, unas, un

grupo de ingenieros ha propuesto una red degrupo de ingenieros ha propuesto una red derutas alternas para cruzar la ciudad de norterutas alternas para cruzar la ciudad de nortea sur, la cual incorpora avenidas importantes.a sur, la cual incorpora avenidas importantes.


16/88

16

La red propuesta es la siguiente. Incluye el nmero de vehculos(miles) que pueden circular por dichas vas.


17/88

17

1.1. Puede la red propuesta dar cabida aPuede la red propuesta dar cabida aun flujo mun flujo mximo de 15,000 v/h deximo de 15,000 v/h denorte a sur?norte a sur?

2.2. CuCul es el flujo ml es el flujo mximo de vehximo de vehculosculosque permite la red cada hora?que permite la red cada hora?

3.3. QuQu flujo se debe canalizar sobreflujo se debe canalizar sobrecada rama?cada rama?


18/88

18

SOLUCISOLUCINN


19/88

19

3

2

0 5

1. 1-2-5-7 3


20/88

20

3

6

2

0 5

1. 1-2-5-7 3

2. 1-3-6-7 6

0 11


21/88


22/88

22

3

611

2

0 5

1. 1-2-5-7 32. 1-3-6-7 63. 1-4-6-7 14. 1-4-6-5-7 1

0 11

4

4

0

3

3

0

4

SOLUCINFINAL


23/88

23

3+6+1+1+2=13

2

0 5

1. 1-2-5-7 32. 1-3-6-7 63. 1-4-6-7 1

4. 1-4-6-5-7 15. 1-2-3-5-7 2

0 11

4

4

0

3

3

0

4

0 0

1

2

SOLUCIN FINAL

0 5 4 2


24/88

24

3

611

2

2

0 11

4

4

0

3

3

0

0 0

1

3 6

5

2

2 2

6

2

6

17


25/88

25

EJERCICIO 2EJERCICIO 2



26/88

26

La compaLa compaa estatal de petra estatal de petrleo cuenta con una red deleo cuenta con una red de

oleoductos que utiliza para transportar petroleoductos que utiliza para transportar petrleo desde suleo desde surefinerrefinera (fuente) hasta diversos centros de almacenamiento.a (fuente) hasta diversos centros de almacenamiento.

Una parte de la red de oleoductos es la siguiente:Una parte de la red de oleoductos es la siguiente:

Cul es el flujo mximo?


27/88

27

Como puede observarse, las capacidades de flujo sonComo puede observarse, las capacidades de flujo son

variables como resultado de los diversos divariables como resultado de los diversos dimetrosmetrosde losde los ductosductos capscaps. en miles de. en miles de galgal. por hora.. por hora.

1.1. LaLa empresa desea abastecer el almacempresa desea abastecer el almacn 7,n 7, CuCul esl esel flujo mel flujo mximo con el cual puede abastecerlo?ximo con el cual puede abastecerlo?

2.2. CuCunto tiempo se requiere para satisfacer unanto tiempo se requiere para satisfacer unademanda de 95,000 galones para el mismo almacdemanda de 95,000 galones para el mismo almacn?n?

3.3. SiSi se presentarse presentar una ruptura o cierre en eluna ruptura o cierre en el ductoducto quequeva de 2va de 2--3,3, CuCul serl sera ahora el flujo ma ahora el flujo mximo para elximo para elsistema?sistema?


28/88

28

SOLUCISOLUCINN

0


29/88

29

33

3

02

1. 1-2-5-7 3

0


30/88

30

3+

3+2

3

02

4

0

1. 1-2-5-7 32. 1-4-7 2

0


31/88

31

3+

+2

3+2+2

3

02

4

0

2

1

0 3

1. 1-2-5-7 32. 1-4-7 23. 1-4-3-6-7 2

0


32/88

32

1. 1-2-5-7 32. 1-4-7 23. 1-4-3-6-7 24. 1-4-3-5-7 1

3+2

+2+1

3+2+2+1

3

02

4

0

2

1

0 31

0

1

1


33/88

02 1


34/88

34

1. 1-2-5-7 32. 1-4-7 23. 1-4-3-6-7 24. 1-4-3-5-7 1

5. 1-4-6-7 16. 1-2-3-5-7 1

3+2+2+1+1

+1

3+2+2+1+1

3

2

4

0

2

1

0 31

0

1

1

0

0

2

2

1

0

0

02 1


35/88

35

1. 1-2-5-7 32. 1-4-7 2

3. 1-4-3-6-7 24. 1-4-3-5-7 15. 1-4-6-7 1

6. 1-2-3-5-7 1

3+2+2+1+1

+1

El Flujo mximo es:3+2+2+1+1+1=10

3

2

4

0

2

1

0 31

0

1

1

0

0

2

2

1

0

0


36/88

36

4

3

511

63 1

2

32

El Flujo mximo es:3+2+2+1+1+1=10


37/88

37

Ejemplo 3Ejemplo 3



38/88

38

En una ciudad se va a construir una obraEn una ciudad se va a construir una obra

civil que inutilizarcivil que inutilizar vvas primariasas primariasdurante una temporada. Los ingenierosdurante una temporada. Los ingenierosproponen una red alterna formada porproponen una red alterna formada por

calles mcalles ms peques pequeas para distribuir elas para distribuir eltrtrnsito.nsito.

Actualmente hay un flujo de 10 milActualmente hay un flujo de 10 mil

autos por hora en las horas pico.autos por hora en las horas pico. La red de desviaciLa red de desviacin tendrn tendr lala

capacidad de canalizar este flujo?capacidad de canalizar este flujo?


39/88

39

1

1

1

1

1 1

0

4

0

6

0 2

6 0

06

0

0

3

04

0

2

1

2

3

4

5

6


40/88

40

SOLUCISOLUCINN

USANDO EL TORAUSANDO EL TORA


41/88

41


42/88

42


43/88

43


44/88

44

DeducciDeduccin del modelo den del modelo de

programaciprogramacin lineal para eln lineal para elproblema del flujo mproblema del flujo mximoximo

El problema es enviar gas naturalEl problema es enviar gas naturaldesde un campo de produccidesde un campo de produccin an a


45/88

45

desde un campo de produccidesde un campo de produccin an a

una ciudad a travuna ciudad a travs des degaseoductos.gaseoductos.

El planteamiento con estos datosEl planteamiento con estos datosseseraa:


46/88

46

sersera:a:

MMxx f sujeto a:f sujeto a:

fxxxxx

xxxx

xxx

fxx

=+=+

=+

=

=+

4535

453424

35342313

242312

1312

0

0

0

ijx

x

x

x

x

xx

x

ij

,0

8

8

7

5

36

10

45

35

34

24

23

13

12


47/88

47

Este planteamiento no se ajusta a laEste planteamiento no se ajusta a la

formulaciformulacin estn estndar de programacindar de programacin linealn linealde costo mde costo mnimo, puesto que se desconoce f ynimo, puesto que se desconoce f yaparece simultaparece simultneamente en la funcineamente en la funcinnobjetivo y en el lado derecho de lasobjetivo y en el lado derecho de lasrestricciones.restricciones.

Si se plantea asSi se plantea asno es posible utilizar elno es posible utilizar elalgoritmo de programacialgoritmo de programacin lineal, por ellon lineal, por ello

utilizaremos el artificio de agregar un arcoutilizaremos el artificio de agregar un arcoficticio entre los nodos inicial y final (x51), conficticio entre los nodos inicial y final (x51), conello ahora el planteamiento serello ahora el planteamiento sera:a:


48/88

48

x 1012


49/88

49

fxxxxxx

xxxx

xxxxxx

=++

=+

=+

==

453551

453424

35342313

242312

131251

0

0

00

ijx

x

xx

x

x

x

x

ij

,0

8

87

5

3

6

10

45

35

34

24

23

13

12


50/88

50

Ejemplo 4Ejemplo 4

COMPACOMPAA QUIMICA UNIDAA QUIMICA UNIDA

Algoritmo de flujo mAlgoritmo de flujo mximoximo



51/88


QuQumica unida produce pesticidas y otros productosmica unida produce pesticidas y otros productosde control agrde control agrcola.cola. El veneno quEl veneno qumico necesario para la produccimico necesario para la produccin esn es

depositado en grandes tambores.depositado en grandes tambores. Una red de tubos y vUna red de tubos y vlvulas regula el flujo dellvulas regula el flujo del

ququmico de los tambores a las diferentesmico de los tambores a las diferentes reas dereas de

producciproduccin.n. El departamento de seguridad debe diseEl departamento de seguridad debe disear unar un

procedimiento que vacprocedimiento que vace los tambores de la formae los tambores de la forma

mm

s rs r

pida posible dentro de los tubos delpida posible dentro de los tubos del

rea derea de

depdepsito, usando la misma red de tubos y vsito, usando la misma red de tubos y vlvulas.lvulas. El procedimiento debe determinar:El procedimiento debe determinar:

-- QuQu vvlvulas deben abrirse y cerrarselvulas deben abrirse y cerrarse-- Estimar el tiempo total de descarga.Estimar el tiempo total de descarga.

DatosDatos0Elm imofl jode2a4es8

No se permite flujo de 4 a 2.


52/88

Tamborescon qumico

Tubo de Seg.

1 7

4

2

3

6

5

10

0

80

0

0

0

0

0

0

10

6

1

12

14

4 2

2 8

3

3

7

2

El mximo flujo de 2 a 4 es 8

SoluciSolucinn --AnalogAnaloga de un problema de programacia de un problema de programacinnlineallineal


53/88

lineallineal

Variables de decisiVariables de decisinnXXijij -- Flujo que viaja desde el nodo i hacia el nodo j a travFlujo que viaja desde el nodo i hacia el nodo j a travssdel arco que conecta ambos nodos.del arco que conecta ambos nodos.

FunciFuncin Objetivon Objetivo -- Maximizar el flujo que sale del nodo 1Maximizar el flujo que sale del nodo 1

Max X12 + X13Max X12 + X13 RestriccionesRestricciones

[Flujo total que sale del nodo 1] = [Flujo total que entra[Flujo total que sale del nodo 1] = [Flujo total que entra

en el nodo 7]en el nodo 7]X12 +X13 = X47 + X57 + X67X12 +X13 = X47 + X57 + X67

[Para cada nodo intermedio: Flujo que entra = flujo que[Para cada nodo intermedio: Flujo que entra = flujo quesale]sale]

Nodo 2: X12 + X32Nodo 2: X12 + X32 = X23 +X24 + X26= X23 +X24 + X26Nodo 3:Nodo 3:X13 +X23 + 63X13 +X23 + 63 = X32 +X35 + X36= X32 +X35 + X36Nodo 4:Nodo 4:X24 +X64X24 +X64 = X46 + X47= X46 + X47

Nodo 5:Nodo 5:X35 +X65X35 +X65 = X56 + X57= X56 + X57Nodo 6:Nodo 6:X26 +X36 + X46 +X56X26 +X36 + X46 +X56 = X63 +X64 +X65 + X67= X63 +X64 +X65 + X67

EL flujo no puede exceder la capacidad de los arcosEL flujo no puede exceder la capacidad de los arcos


54/88

EL flujo no puede exceder la capacidad de los arcosEL flujo no puede exceder la capacidad de los arcos X12 >= 10; X13 >= 10; X23 >= 1; X24 >= 8; X26 >= 6;X12 >= 10; X13 >= 10; X23 >= 1; X24 >= 8; X26 >= 6;

X32 >= 1;X32 >= 1;X35X35 >=>= 15; X3615; X36 >=>= 4; X464; X46 >=>= 3; X473; X47 >=>= 7; X567; X56 >=>= 2; X572; X57

>=>= 8;8;X63X63

>=>= 4; X644; X64

>=>= 3; X653; X65

>=>= 2; X672; X67

>=>= 2;2;

Los flujos no pueden ser negativos: TodosLos flujos no pueden ser negativos: Todos XXijij >= 0>= 0

Se debe tener presente que este problema esSe debe tener presente que este problema esrelativamente pequerelativamente pequeo y la solucio y la solucin puede ser obtenidan puede ser obtenidarrpidamente usando el modelo de programacipidamente usando el modelo de programacin lineal.n lineal.

Sin embargo para problemas de mayor envergadura seSin embargo para problemas de mayor envergadura seaconseja usar el modelo de redes.aconseja usar el modelo de redes.

SoluciSolucinn--AnalogAnaloga con un problema de redesa con un problema de redes


55/88

-- La idea bLa idea bsica es la siguiente:sica es la siguiente:

* Encontrara un camino de capacidad* Encontrara un camino de capacidad mmnimaennimaen cada unocada uno

de sus arcos.de sus arcos.* Aumentar el flujo de esos arcos por la m* Aumentar el flujo de esos arcos por la mnima capacidadnima capacidadde uno de los arcos de la ruta.de uno de los arcos de la ruta.

* Repetir este procedimiento hasta completar la ruta de* Repetir este procedimiento hasta completar la ruta demanera tal que todos los arcos tengan una capacidadmanera tal que todos los arcos tengan una capacidadresidual positiva.residual positiva.*Designar un nodo origen y un nodo de flotaci*Designar un nodo origen y un nodo de flotacinn

* Definir las capacidades de todos los arcos en la red ( en* Definir las capacidades de todos los arcos en la red ( enambos sentidos)ambos sentidos)* A continuaci* A continuacin se muestra la solucin se muestra la solucin obtenida usandon obtenida usandoWINQSB.WINQSB.

El mximo flujo obtenido por WINQSB

El mximo flujo obtenido por WINQSB


56/88

Tamborescon qumico

Tubo de Seg.

1 7

4

2

3

6

5

8

8

2

7

7

10

7

8

2

Flujo Mximo= 17


57/88

57

Ejercicio para resolverEjercicio para resolver


Un conjunto de vUn conjunto de vas ras rpidas tiene las siguientespidas tiene las siguientes


58/88

58

Un conjunto de vUn conjunto de vas ras rpidas tiene las siguientespidas tiene las siguientes

capacidades (miles de vehcapacidades (miles de vehculos/hora).culos/hora).

1. Determinar el flujo mximo de vehculos/hora que pueden pasar por el sistema.2. Cuntos vehculos/hora deben pasar por cada va para lograr el flujo mximo?


59/88

59

SOLUCISOLUCINN

3 6

4

1 2


60/88

60

3 3

3

5 3

6

2

1 2

ITERACIN CAMINOSELECCIONADO

Pf(vehculos/hora)

FLUJO TOTAL DESPUSDE LA ITERACIN

1 1-4-6 (1-4) 3,000 3,000

2 1-2-5-6 (1-2) 3,000 6,000

3 1-3-6 (3-6) 2,000 8,000

4 1-3-4-2-5-6 (2-5) 1,000 9,0005 1-3-4-5-6 (3-4) 2,000 11,000


61/88

61

ITERACIN CAMINO

SELECCIONADO

Pf

(vehculos/hora)

FLUJO TOTALDESPUS DE LA

ITERACIN

1 1-4-6 (1-4) 3,000 3,000

2 1-2-5-6 (1-2) 3,000 6,000

3 1-3-6 (3-6) 2,000 8,000

4 1-3-4-2-5-6 (2-5) 1,000 9,000

5 1-3-4-5-6 (3-4) 2,000 11,000


62/88

62

EJERCICIO PARA RESOLVEREJERCICIO PARA RESOLVER


63/88

63

El alcalde del distrito Florencia de Mora desea conocer a travEl alcalde del distrito Florencia de Mora desea conocer a travssde los 15 postes de lade los 15 postes de la MzMzA para el alumbrado elA para el alumbrado elctricoctrico -- que esque esproveproveda por una estacida por una estacin central perteneciente an central perteneciente a HidrandinaHidrandina ,,que dista de estaque dista de esta MzMz entre los 4000 y 6000entre los 4000 y 6000 mtsmts..-- , por donde, por dondecircula la mayor cantidad de energcircula la mayor cantidad de energa, teniendo en cuenta quea, teniendo en cuenta quesus habitantes consumen la mayor cantidad de luz por lassus habitantes consumen la mayor cantidad de luz por lasmamaanas, a diferencia de los fines de semana que el mayoranas, a diferencia de los fines de semana que el mayorconsumo se da por las noches .consumo se da por las noches .

La siguiente red representa la capacidad de cada posteLa siguiente red representa la capacidad de cada poste;expresando dicha capacidad en;expresando dicha capacidad en WatsWats..

Aplicar el algoritmo de flujo mAplicar el algoritmo de flujo mximo para saber por dximo para saber por dndende

fluye la mayor cantidad de energfluye la mayor cantidad de energa en esta red de distribucia en esta red de distribucinnde alumbrado elde alumbrado elctrico de lactrico de la MzMzA perteneciente al distritoA perteneciente al distritoFlorencia de Mora?Florencia de Mora?


64/88

64


65/88

65

SOLUCISOLUCINN


66/88

66


67/88

67



68/88

68

El complejo hidroelEl complejo hidroelctrico de la cuenca delctrico de la cuenca del

RimacRimac consta de 7 centrales hidroelconsta de 7 centrales hidroelctricasctricasque se encuentran en actual funcionamiento.que se encuentran en actual funcionamiento. La capacidad que genera es de 543000 Kw.La capacidad que genera es de 543000 Kw.

La demanda que no se puede satisfacer deLa demanda que no se puede satisfacer delas centrales hidroellas centrales hidroelctricas se obtiene de lasctricas se obtiene de lasplantas termoelplantas termoelctricas (petrctricas (petrleo), la energleo), la energaaes llevada a traves llevada a travs de conductores els de conductores elctricosctricos

a hacia las ciudades.a hacia las ciudades. La figura resume los enlaces de la red juntoLa figura resume los enlaces de la red junto

con la capacidad de cada conducto.con la capacidad de cada conducto.


69/88

69


70/88

70

SOLUCISOLUCINN


71/88

71

Maximal flow = 110.0000Maximal flow = 110.0000From To Arc Capacity Flow Amount Residue

---------------------------------------------------------------------------------------

N1 N2 70.00 50.00 20.00

N1 N3 50.00 20.00 30.00

N1 N4 60.00 40.00 20.00

N1 N5 0.00 0.00 0.00

N1 N6 0.00 0.00 0.00

N1 N7 0.00 0.00 0.00

N2 N1 70.00 0.00 70.00

N2 N3 0.00 0.00 0.00

N2 N4 30.00 30.00 0.00

N2 N5 0.00 0.00 0.00

N2 N6 20.00 20.00 0.00

N2 N7 0.00 0.00 0.00

N3 N1 50.00 0.00 50.00

N3 N2 0.00 0.00 0.00

N3 N4 20.00 0.00 20.00

N3 N5 20 00 20 00 0 00


72/88

72

N3 N5 20.00 20.00 0.00

N3 N6 0.00 0.00 0.00

N3 N7 0.00 0.00 0.00

N4 N1 60.00 0.00 60.00

N4 N2 30.00 0.00 30.00

N4 N3 20.00 0.00 20.00

N4 N5 0.00 0.00 0.00

N4 N6 20.00 20.00 0.00

N4 N7 50.00 50.00 0.00

N5 N1 0.00 0.00 0.00

N5 N2 0.00 0.00 0.00

N5 N3 20.00 0.00 20.00

N5 N4 0.00 0.00 0.00

N5 N6 0.00 0.00 0.00

N5 N7 70.00 20.00 50.00

N6 N1 0.00 0.00 0.00

N6 N2 20.00 0.00 20.00

N6 N3 0.00 0.00 0.00

N6 N4 20.00 0.00 20.00

N6 N5 0.00 0.00 0.00


73/88

73

N6 N7 70.00 40.00 30.00

N7 N1 1.00 0.00 1.00

N7 N2 0.00 0.00 0.00

N7 N3 0.00 0.00 0.00

N7 N4 0.00 0.00 0.00

N7 N5 4.00 0.00 4.00

N7 N6 6.00 0.00 6.00


74/88

74



75/88

75

TelefTelefnica quiere saber el flujo mnica quiere saber el flujo mximoximoque debe de salir de la ciudad 1 y llegarque debe de salir de la ciudad 1 y llegara la ciudad 12 pasando por otros nodosa la ciudad 12 pasando por otros nodos

o puntos de transmisio puntos de transmisin de datos.n de datos.


76/88

76


77/88

77

SOLUCISOLUCINN


78/88

78



79/88

79


80/88

80TOTAL = 2 + 3 + 6 + 2 = 13


81/88

81

PROBLEMAS DE FLUJO MPROBLEMAS DE FLUJO MXIMOXIMOCONCON

GRAFOSGRAFOS

AANNEEXXOO

Problemas de flujo en redesProblemas de flujo en redes Supongamos un grafo dirigido G=(V, A) con pesos en las aristas.Supongamos un grafo dirigido G=(V, A) con pesos en las aristas. LosLos


82/88

82

pesos de cada arista C(v, w) representa el npesos de cada arista C(v, w) representa el nmero mmero mximo de unidadesximo de unidadesque puedenque puedenfluirfluirdesde el nodo v al w.desde el nodo v al w. Por ejemplo:Por ejemplo: C(v, w) puede ser la cantidad mC(v, w) puede ser la cantidad mxima de agua que puede ir porxima de agua que puede ir por

una tuberuna tubera que comunica v con w, o el na que comunica v con w, o el nmero de coches mmero de coches mximo que cabe enximo que cabe en

una calle.una calle. Problema de flujo mProblema de flujo mximo.ximo.

Dado un nodo origen s y un nodo destino t en un grafo dirigido cDado un nodo origen s y un nodo destino t en un grafo dirigido cononpesos, encontrar la cantidad mpesos, encontrar la cantidad mxima de flujo que puede pasar de s a t.xima de flujo que puede pasar de s a t.

s t

a c

b d2

3 3

41

2

3

2

s t

a c

b d2

3 2

10

2

3

2

La suma de entradas para cada nodo interior debe ser igual a laLa suma de entradas para cada nodo interior debe ser igual a la suma de salidas.suma de salidas.

Los valores de flujo en cada arista no pueden superar los valoreLos valores de flujo en cada arista no pueden superar los valores ms mximos.ximos.

Problemas de flujo en redesProblemas de flujo en redes Algoritmo para calcular el flujo mAlgoritmo para calcular el flujo mximo.ximo.


83/88

83

1. Inicializar un grafo de flujo1. Inicializar un grafo de flujo GGff con los mismos nodos y aristas de G, perocon los mismos nodos y aristas de G, perocon pesos 0. Este grafo guardarcon pesos 0. Este grafo guardar el resultado del algoritmo.el resultado del algoritmo.

2. Buscar un camino en G, desde s hasta t (camino creciente). Se2. Buscar un camino en G, desde s hasta t (camino creciente). Sea m el valora m el valormmnimo de los costes de las aristas por las que pasa el camino (ponimo de los costes de las aristas por las que pasa el camino (por ester este

camino pueden fluir hasta m unidades de flujo).camino pueden fluir hasta m unidades de flujo).3. Para cada arista (v, w) del camino, a3. Para cada arista (v, w) del camino, aadir al costo de la aristaadir al costo de la arista corresponcorrespon--

diente endiente en GGff el valor m:el valor m: CCff[v[v, w] =, w] = CCff[v[v, w] + m., w] + m.4.4. DecrementarDecrementar el valor m en cada arista (v, w) del camino, en el grafo G. Siel valor m en cada arista (v, w) del camino, en el grafo G. Si

la arista toma el valor 0, eliminarla de G.la arista toma el valor 0, eliminarla de G.5. Volver al paso 2 mientras sigan existiendo caminos entre s y5. Volver al paso 2 mientras sigan existiendo caminos entre s y t en G.t en G.

Ejemplos:Ejemplos:

Caso 1: (s, b, d, t) con m=2; (s, a, c, t) con m=2; (s, a, d, t)Caso 1: (s, b, d, t) con m=2; (s, a, c, t) con m=2; (s, a, d, t) con m=1. FINcon m=1. FIN Caso 2: (s, a, d, t) con m=3. FINCaso 2: (s, a, d, t) con m=3. FIN

El algoritmo es no determinista y no garantiza una soluciEl algoritmo es no determinista y no garantiza una solucinn ptima.ptima. SoluciSolucin:n: en el paso 4 aen el paso 4 aadir una arista a G con costo madir una arista a G con costo m

(para permitir deshacer los caminos).(para permitir deshacer los caminos).


84/88

84

EJEMPLO 5EJEMPLO 5

FLUJO MFLUJO MXIMOXIMO


85/88

85

Una ciudad es atravesada por una red de aguaUna ciudad es atravesada por una red de aguapotable que le permite alcanzar un nivel de 10potable que le permite alcanzar un nivel de 10mil litros por hora.mil litros por hora.

Debido a un programa de mantenimientoDebido a un programa de mantenimientogeneral, hay que desviar el flujo por ciertasgeneral, hay que desviar el flujo por ciertas

vvas. Un grupo de ingenieros propone una redas. Un grupo de ingenieros propone una redde rutas alternas para abastecer la ciudad.de rutas alternas para abastecer la ciudad. Puede la red propuesta dar cabida al flujo dePuede la red propuesta dar cabida al flujo de

15 mil litros por hora?15 mil litros por hora?

CuCul es el flujo ml es el flujo mximo que permite la redximo que permite la redcada hora?cada hora? QuQu flujo debe canalizarse sobre cada rama?flujo debe canalizarse sobre cada rama?


86/88

86


87/88

87

SOLUCISOLUCINN


88/88

88

21 flujo maximo

Documents