Modelo de Redes
Objetivos del Captulo
Conceptos y definiciones de redes.
Importancia de los modelos de redes
Modelos de programacin lineal, representacin en redes y
soluciones usando el computador para:
* Modelos de transporte.
* Modelos de capacidad de transporte
* Modelos de asignacin
* Modelo del vendedor viajero
* Modelos de la ruta mas corta
* Modelos de la rama mas corta
Un problema de redes es aquel que puede
representarse por:
Nodos
10
Arcos
10
Funciones en los arcos
Problemas de transporte o
Distribucin de Mercancas
Es un problema particular que se resuelve con los procedimientos de la
programacin lineal.
Un problema de transporte surge cuando se necesita un modelo costoefectividad que permita transportar ciertos bienes desde un lugar de
origen a un destino que necesita aquellos bienes , con ciertas
restricciones en la cantidad que se puede transportar.
Objetivo: Trata de encontrar los caminos para trasladar mercanca,
desde varias plantas (orgenes) a diferentes centros de
almacenamiento (destinos), de manera que se minimice el costo del
transporte
la cantidad de los bienes disponibles en cada localizacin (origen) es
limitada y la cantidad de demanda de los bienes necesarios (destino)
en cada una de las localizaciones es conocida
Problemas de transporte o
Distribucin de Mercancas
Para que un problema pueda ser resuelto por el mtodo del transporte
debe cumplir:
1)La funcin objetivo y las restricciones deben ser lineales.
2)El total de unidades que salen en origen debe ser igual al total de
unidades que entran en destino, es decir se exige que toda la
produccin sea distribuida a los centros de ventas en las cantidades
que precisa cada uno; por tanto, no pueden generarse inventario del
producto ni en las fbricas ni en los centros de ventas.
Problemas de Transporte
Foster Generation tiene plantas en
Cleveland, Bedford, New York, la
capacidad de produccin para el siguiente
periodo de plantacin para un tipo
especifico de generador es como sigue
Origen
Planta
Capacidad de
produccin (unidades)
Cleveland
5,000
Bedford
6,000
New York
2,500
TOTAL
13,500
La empresa distribuye sus generadores a
travs de 4 centros regionales de
distribucin localizados en Boston,
Chicago, San Lus y Lexington; el
pronostico de la demanda de los centros
de distribucin es como sigue:
Los costos unitario de los orgenes
hacia los destino se dan en la
siguiente tabla:
Origen
Centro de
distribucin
Pronostico demanda
(unidades)
Boston
6,000
Chicago
4,000
San Luis
2,000
Lexington
1,500
TOTAL
13,500
COSTO UNITARIO DE TRANSPORTE (FOSTER)
Origen
Boston
Chicago
San Luis
Lexington
Cleveland
Bedford
New York
Problemas de Transporte
La administracin desea
determinar cuanto de su
produccin deber embarcarse
desde cada una de las plantas
hacia cada uno de los centros
de distribucin
El objetivo es determinar las
rutas a usar y la cantidad a
embarcar en cada una de ellas
y que den el mnimo costo de
transporte total
Centro Distribucin
(Destino)
Plantas
(Origen)
Costo
transporte
Unitario
1
Boston
6000
2
Chicago
4000
3
San Luis
2000
4
Lexington
1500
5000
1
Cleveland
2
7
6
7
6000
2
Bedford
5
2
3
2500
3
New York
5
4
5
Problemas de Transporte
La funcin objetivo es minimizar el costo total de transporte de Foster Generation,
para esto se debe sumar los costos de transporte de cada planta (origen)
Cleveland = 3X11 + 2X12 + 7X13 + 6X14
Bedford = 3X21 + 2X22 + 7X23 + 6X24
New York = 3X31 + 2X32 + 7X33 + 6X34
Restricciones
de Suministro:
Cada uno de los suministros
tiene una demanda especifica
Restricciones
de Demanda:
Cada centro de distribucin
tiene una demanda para
asegurar satisfacer las
demandas de los destinos
Suministro de Cleveland
X11 + X12 + X13 + X14 5000
Suministro de Bedford
X21 + X22 + X23 + X24 5000
Suministro de New York
X31 + X32 + X33 + X34 5000
de Boston
X11 + X21 + X31 = 6000
de Chicago X12 + X22 + X33 = 4000
de San Lus X13 + X23 + X33 = 2000
de Lexington X14 + X24 + X34 = 1500
Problemas de Transporte
Combinando la
funcin objetivo
y las
restricciones en
un modelo de
programacin
lineal
Variable
X11
X12
X13
X14
X21
X22
X23
X24
X31
X32
X33
X34
Minimize
C1
C2
C3
C4
1
1
>=
500
0
>=
600
0
>=
250
0
600
0
400
C5
C6
C7
1
1
1
2
3
14
5
6
7
8
9
10
11
12
Decision 1 Solution Unit Cost or 1Total
Reduced
=
0
Variable Value
Profit C(j)
Contribution Cost
200
X11
3,500.00
3
10,500.00
0 0
1
1
=
X12
1,500.00
2
3,000.00
0
150
X13
0
7
0
8
1
1
=
X14
0
6
0
6 0
X21
0
7
0
1
X22
2,500.00
5
12,500.00
0
X23
2,000.00
2
4,000.00
0
X24
1,500.00
3
4,500.00
0
X31
2,500.00
2
5,000.00
0
X32
0
5
0
4
X33
0
4
0
6
X34
0
5
0
6
Objective Function (Min.) =
39,500.00
Problemas de Transporte (QSB)
Anlisis
Anlisisde
deSensibilidad
Sensibilidadpor
porWINQSB
WINQSB
ng
a
R
o
m
i
pt
O
o
Ra
ng
o
de
f
ac
tib
ilid
ad
Precio sombra de la distribuidora - el costo de demandar
una unidad ms por la distribuidora.
Precio sombra de la planta - el costo de cada unidad
extra disponible en la planta.
Interpretacin de los resultados del anlisis de
sensibilidad.
* Reduccin de Costos:
La cantidad a transportar que reduce el costo por unidad entrega la
ruta ms econmicamente atractiva.
Si una ruta debe usarse obligatoriamente, incurriendo asi en el costo
que ello significa, por cada carga transportada , el costo total
aumentara en una cantidad igual a la reduccin del costo hecha.
* Precios Sombra:
- Para las plantas el precio sombra de transporte corresponde al costo
de cada unidad disponible en la planta.
- Para las distribuidoras, el precio sombra de transporte corresponde
al costo de cada unidad extra demandada por la distribuidora.
Problemas de Transporte (Solver)
Primero
Ingresar en la hoja de calculo los datos de costos de transporte,
capacidad de la planta (origen) y la demanda de los centros de
distribucin (destino)
Segundo
Identificar las celdas donde se almacenan los valores de las
variables de decisin
Problemas de Transporte (Solver)
Seleccione el men Herramientas Solver (Resolver)
La solucin ptima
de este problema es
VARIANTES DEL PROBLEMA
1. Oferta y demanda total desiguales: a menudo el suministro total
no es igual a la demanda total
a) Si Oferta > demanda total: no es necesaria ninguna
modificacin al modelo de PL, aparecer en la solucin de la PL
un suministro excedente (como una holgura)
b) Si Oferta < demanda total: el modelo no tendr solucin factible.
Se agrega un origen ficticio con un suministro igual a la diferencia entre
la demanda total y el suministro total con costo unitario igual a cero
2. Maximizacin de la funcin objetivo: simplemente se resuelve como
maximizacin en vez de minimizacin, las restricciones no cambian
3. Rutas con capacidad limitada: una o mas rutas pueden tener
capacidad limitada o cantidades mnimas.
4. Rutas no aceptables o prohibidas: se hace desaparecer el arco
correspondiente de la red y se elimina la variable correspondiente al
modelo. O tambin se le asigna un costo muy alto para impedir que
sea utilizada por la solucin optima
Modelos de
Asignacin
Modelos de Asignacin
Asignar tareas a maquinarias, agentes a trabajos especiales,
personal de ventas a territorios, contratos a licitantes
Una caracterstica que distingue a los problemas de
asignacin es que un agente se le asigna a una y solamente
una tarea
Buscamos el conjunto de asignaciones que optimizarn un
objetivo dado (minimizar el tiempo o maximizar la utilidad)
El problema de asignacin es un caso especial de problema
de transporte, en que todos los valores de oferta y demanda
son iguales a 1, y la cantidad que se embarca en cada uno
de los arcos es 0 o 1
Modelos de Asignacin
Definicin del Problema
* m trabajadores deben ser asignados a m trabajos.
* Un costo unitario (o ganancia) Cij es asociado al trabajador i que
realizara el trabajo j.
* Minimizar el costo total ( o maximizar la ganancia total) de la
asignacin de trabajadores a sus respectivos empleos que le
corresponde a cada uno, tratando de que esta asignacin sea la
ptima posible.
Modelos de Asignacin Ejemplo:
Fowle Marketing Co. acaba de recibir solicitudes de inv. de mercado de 3
clientes nuevos. La empresa se enfrenta a la tarea de asignar un lder o
jefe del proyecto (agente) a cada cliente (tarea). Fowle cuenta con 3
ejecutivos que estn disponibles, sin embargo se da cuenta de que el
tiempo requerid para terminar cada uno de los estudios depender de la
experiencia del lder de proyecto.
La administracin de Fowle desea asignar lideres de proyecto para
minimizar el numero total de das necesarios para completar los 3
proyectos. Si se debe asignar a un lder a un solo cliente. Qu
asignaciones debern efectuarse?
Lder proyecto
Tiempo
estimado
(das) de
terminacin
del proyecto
Cliente
1
1 Terry
10
15
2. Carle
18
3. McClymond
14
Solucin del problema como asignacin
Los nodos corresponden a lideres del proyecto y a clientes, y los arcos
representan asignaciones posibles de lder del proyecto a cliente
La oferta en cada nodo y la demanda en cada nodo es igual a 1
El costo de asignar un lder del proyecto a un cliente es el tiempo que le tomara
a dicho lder terminar la tarea del cliente
VARIANTES DEL PROBLEMA
1. Numero total de agentes distinto al numero total de tareas
a) Si numero de agentes > Tareas: Los agentes adicionales se quedan sin
asignacin.
b) Si numero de tareas > Agentes: el modelo no tendr solucin factible.
Se agrega agentes ficticios para igualar al numero de tareas
2. Maximizacin de la funcin objetivo: simplemente se resuelve como
maximizacin en vez de minimizacin, las restricciones no cambian
3. Asignaciones no aceptables : se puede eliminar la variable de decisin en
la formulacin del PL. Esta situacin pudiera ocurrir si uno de los agentes no
tuviera la experiencia necesaria para una o mas de las tareas
Min.
n
Modelo de Asignacin
CijXij
i 1 J 1
Xij 1
j 1
i = 1, 2, , m
Agentes
Xij 1
i 1
i = 1, 2, , m
Agentes
Preguntas
1. Si la demanda = a la oferta total, de un problema de transporte, el
problema es:
a) Balanceado
b) Desbalanceado
c) Infactible
2. Si en un problema de transportes , la demanda total es mayor que la
capacidad total entonces:
a) Se debe agregar un origen ficticio
b) Se debe agregar un destino ficticio
c) Se debe agregar un origen y destino ficticio.
3. El modelo de transporte es un ejemplo de toma de decisiones con certeza
o toma de decisiones con incertidumbre?. Porque
Ejercicios:
Ejercicios Transportes y
Asignacin
1. El viernes 13 de abril, Carbn del Per SA
tenia carros vacios en las siguientes
localidades con las cantidades indicadas
2. Para el Lunes 16 de abril, las siguientes
localidades necesitaran carros de carbn,
segn el orden siguiente
3. El despachador construye una tabla de Km
de distancia para las localidades anteriores.
Poblacin
Poblacin
Oferta de Carros
Origen 1
35
Origen 2
60
Origen 3
25
Poblacin
Oferta de Carros
Destino 1
30
Destino 2
45
Destino 3
25
Destino 4
20
Destino 1
Destino 2
Destino 3
Destino 4
Oferta 1
50
30
60
70
Oferta 2
20
80
10
90
Oferta 3
100
40
80
30
Minimizando la
distancia (Km) total
que recorren, calcular
el mejor envi de
carros de carbn
Ejercicios:
Ejercicios Transportes y
Asignacin
Una empresa fabrica acondicionadores de aire en Houston, Phoenix y
Mamphis. Los aparatos se envan a distribuidores regionales
localizados en Dallas, Atlanta y Denver. Los costos de envi varan y a
la compaa le gustara encontrar la forma de minimizar sus costos
para satisfacer las demandas de cada uno de los distribuidores.
Dallas requiere 800 unidades al mes, Atlanta 600 y Denver 200.
Houston tiene 850 unidades al mes, Phoenix 650 y Memphis 300.
El costo de envi por unidad son
Dallas Atlanta
Denver
Houston
$8
$ 12
$ 10
Phoenix
$ 10
$ 14
$9
$8
$ 12
Memphis $ 11
Cuantas unidades debern ser enviadas de cada planta a cada centro
de distribucin regional. Cul es el costo total de esta operacin?
Ejercicios:
Ejercicios Transportes y
Asignacin
Los tres bancos de sangre de una ciudad son coordinados por la
oficina central que suministra sangre a cuatro hospitales. el costo de
envi de un recipiente estndar son:
Hospital
1
Hospital
2
Hospital
3
Hospital
4
Demanda
Banco 1
$8
$9
$ 11
$ 16
50
Banco 2
$ 12
$7
$5
$8
80
Banco 3
$ 14
$ 10
$6
$7
120
90
70
40
50
250
Demanda
Cuantos envos debern hacerse semanalmente de cada banco de
sangre a cada hospital de modo que los costos de envi totales se
reduzcan al mnimo
Problema de
trasbordo
Problema de Trasbordo
El problema de trasbordo es una extensin al problema de transporte, en el
cual se agrega nodos intermedios conocidos como nodos de trasbordo por
ejemplo: Almacenes
La oferta o suministro en cada origen es limitada y en cada destino la demanda
es conocida
El problema de trasbordo permite embarcar de bienes del origen a los nodos de
trasbordo y hacia los de destino
El objetivo del problema de trasbordo es determinar cuantas unidades debern
embarcarse en cada uno de los arcos de la red, de manera que todas las
demandas destino se satisfagan al costo de transporte mnimo posible
Min
CijXij
todos los arcos
Sujeto a
Xij
arcos de salida
Xij
arcos de salida
Xij Suministro i
arcos de entrada
Xij 0
Nodos de Trasbordo
arcos de entrada
Xij Xij Demanda j
arcos de entrada
Nodos de Origen i
arcos de salida
Nodo de destino j
Xij = numero de unidades
embarcadas del nodo i al nodo j
Cij = Costo unitario de embarque
del nodo i al nodo j
Ryan Electronic es una empresa con instalaciones de produccin en Denver y en
Atlanta. Los componentes de produccin en cualquiera de estas instalaciones
pueden ser embarcadas a cualquiera de los almacenes de la empresa que estn
localizadas en Kansas City y en Lousiville. De los almacenes regionales la
empresa suministra a los detallistas al menudeo en Detroit, Miami, Dallas y nueva
Orlens.
Distribucin al detalle
Almacn
Almacn
Detroi
t
Miami
Dallas
Nueva
Orlens
Planta
Kansas
City
Louisville
Kansas City
Denver
Louisville
Atlanta
Distribuidores al menudeo
(nodo destino)
Plantas
(nodo origen)
600
1
Denver
Almacenes
(nodo de trasbordo)
2
3
3
Kansas
City
6
3
6
Suministros
2
Atlanta
200
6
Miami
150
7
Dallas
350
8
Nueva
Orleans
300
400
5
Detroit
4
4
Louisville
Rutas de distribucin
(arcos)
6
5
Demandas
Igual que el problema de transporte y de asignacin, podemos
formular un modelo de PL a partir de la representacin en red.
Supongamos que Xij denota el nmero de unidades embarcadas del
nodo i hacia el nodo j.
Dado que el suministro de la planta de Denver es de 600 unidades,
las cantidades embarcadas desde la planta de Denver debe de ser
menor que o igual a 600
X13 + X14 600
Similarmente, para la planta de Atlanta tenemos
X23 + X24 400
Consideremos ahora como expresar las restricciones que
corresponden a los 2 nodos de trasbordo.
Para el nodo 3 (almacn de Kansas City), debemos garantizar que el
numero de unidades que se embarquen sea igual al numero de
unidades que se hayan recibido en el almacn, es decir
Unidades embarcadas
hacia fuera del nodo 3
X13 + X12
Almacn de
Kansas City
(Nodo 3)
Unidades embarcadas
hacia fuera del nodo 3
X35 + X36 + X37 + X38
Obtenemos
X35 + X36 + X37 + X38 = X13 + X23 - X13 - X23 + X35 + X36 + X37 + X38 = 0
De manera similar para el nodo 4 es
X45 + X46 + X47 + X48 = X14 + X24 - X14 - X24 + X45 + X46 + X47 + X48 = 0
Para desarrollar las restricciones asociadas con los nodos destino, reconocemos
que cada nodo, la cantidad embarcada al destino debe ser igual a la demanda.
Por ejemplo
X35 + X45 = 200
X36 + X46 = 150
X37 + X47 = 350
X38 + X48 = 300
satisfacer la demanda de 200 unidades en el nodo 5
satisfacer la demanda de 200 unidades en el nodo 6
satisfacer la demanda de 200 unidades en el nodo 7
satisfacer la demanda de 200 unidades en el nodo 8
La funcin objetivo refleja el costo total de embarque en las 12 rutas de embarque.
Combinando la funcin objetivo y las restricciones nos lleva al modelo de PL con
12 variables y 8 restricciones del problema de trasbordo de Ryan Electronics
Min. 2X13 + 3X14 + 3X23 + 1X24 + 2X35 + 6X36 + 3X37 + 6X38 + 4X45 + 4X46 + 6X47 + 5X48
Restricciones de los nodos de origen
Sujeto a
X13 + X14 600
Restricciones de los nodos de trasbordo
X23 + X24
400
-X13
- X23
+ X35 + X36 + X37 + X38 = 0
- X14
- X24
+ X45 + X46 + X47 + X48= 0
Restricciones de los nodos de destino
X35
+ X45
X36
+ X46
X37
+ X47
X38
+ X48
= 200
= 150
= 350
= 300
Problema del vendedor viajero
Definicin del problema
Existen m nodos
Un costo unitario Cij es asociado al arco (i,j).
El objetivo es encontrar el ciclo que minimice el costo total al
visitar todos los nodos exactamente una vez.
Se trata de un tour es un recorrido que comienza en una ciudad de
partida visitando cada ciudad (nodo) de una cierta red, exactamente
una vez y volviendo al punto de partida.
El objetivo es minimizar el viaje, ya sea desde los puntos de vista
de tiempo y distancia.
Importancia
- Diversas aplicaciones pueden ser resueltas como un
problema de vendedor viajero
- Ejemplo
* Rutas a seguir por buses escolares
* Distribucin de bombas militares
- El problema tiene importancia terica porque este representa
una clase de problemas llamados NP-completos.
Complejidad
Escribir el modelo matemtico y resolverlo resulta muchas
veces incmodo, ya que un problema de 20 ciudades requiere
de 500,000 restricciones.
Problema del vendedor viajero
AGENCIA GUBERNAMENTAL DE EMERGENCIA
Se debe realizar una visita a cuatro oficinas locales de la AGE,
partiendo de la oficina principal y volviendo a la misma, la cual esta
ubicada en Northridge, Southern California.
Datos
F
r
o
m
Tiempo en minutos para trasladarse de una oficina a otra
Hacia la oficina
H
1
2
3
Of. Princ
30
45
65
Of. 1
30
25
50
Of. 2
45
25
40
Of. 3
65
50
40
Of. 4
80
50
40
35
4
80
50
40
35
Problema del vendedor viajero
Red que representa el problema de vendedor viajero de AGE
2
40
25
35
50
40
50
4
45
65
30
80
Of. Princ
Solucin
- Identificacin de los posibles ciclos.
* Existen (m-1)! ciclos posibles
* Solo problemas pequeos pueden ser resueltos.
- Se utiliza una combinacin de problemas de
asignacin con la tcnica Branch and Bound (ramas y
consolidados)
- Problemas con menos de 20 nodos pueden ser
resueltos en forma eficiente por este mtodo.
Datos
Datosde
deentrada
entradapara
paraelelproblema
problemade
devendedor
vendedorviajero
viajeroen
enWINQSB
WINQSB
Solucin
Solucin de
de WINQSB
WINQSB -Una
-Una combinacin
combinacin de
de
problema
problema de
de asignacin
asignacin yy la
la tcnica
tcnica
Branch
Branch and
and Bound
Bound
2
25
40
50
40
50
45
35
4
65
30
80
Of. Princ
Problemas de la Ruta ms corta
Encuentra la ruta mas corta a una serie de destinos
Se trata de encontrar la ruta de menor distancia, o costo,
a entre el punto de partida o nodo inicial y el destino o
nodo terminal.
Definicin del Problema
- Se tienen n nodos, partiendo del nodo inicial 1 y terminando
en el nodo final n.
- Arcos bi-direccionales conectan los nodos i y j con distancias
mayores que cero, dij
- Se desea encontrar la ruta de mnima distancia que conecta
el nodo 1 con el nodo n.
Por medio de la aplicacin del algoritmo de este problema
podemos conocer la menor distancia entre un nodo origen
y un nodo destino.
Problemas de la Ruta ms corta
Ejemplo 1:
La administracin de Seervada Park necesita determinar
los caminos bajo los cuales se deben tender las lneas
telefnicas para conectar las estaciones con una
longitud total mnima de cable.
Se describir paso a paso la solucin de este problema,
en base a los datos que se proporcionan en la figura
siguiente. Los nodos y distancias se muestran en la red,
en donde las lneas delgadas representan ligaduras
potenciales.
Problemas de la Ruta ms corta
RED SEERVADA PARK
Usando WinQSB
Problemas de la Ruta ms corta
Lineas Fairway Van
Determine la ruta mas corta entre Seattle y El
Paso para la siguiente red de carreteras.
Seattle
497
180
3
Sac.
691
420
345
Reno
138
Bakersfield
114
526
6
102
432
621
Denver
Las Vegas
11
280
108
155
Barstow
13
469
Albuque.
Phoenix
386
17
12
403
16
425
452
Kingman
15
207
118
San Diego
440
14
Los Angeles
Cheyenne
Salt Lake City
291
10
Butte
Boise
4
432
Portland
599
Tucson
18
19
314
El Paso
Problemas de la Ruta ms corta
rbol de expansin mnima
Determina la trayectoria a travs de una red que conecta
todos los puntos minimizando la distancia total sin formar
bucles
El rbol de expansin mnima es apropiado para
problemas en los cuales la redundancia es expansiva, o el
flujo a lo largo de los arcos se considera instantneo.
Ejemplo: conectar todas las casas a la energa elctrica,
sistema cableado telefonico, sistemas de tuberas de agua
rbol de expansin mnima
EL TRANSITO DEL DISTRITO METROPOLITANO
La ciudad de Jaen esta planificando el desarrollo de una
nueva lnea en sistemas de trnsito.
El sistema debe unir 8 residencias y centros comerciales.
El distrito metropolitano de transito necesita seleccionar
un conjunto de lneas que conecten todos los centros a
un mnimo costo.
La red seleccionada debe permitir:
- Factibilidad de las lneas que deban ser construdas.
- Mnimo costo posible por lnea.
RED QUE
REPRESENTA
EL ARBOL
EXPANDIDO.
Zona Norte
3
33
34
Zona Oeste
1
Universidad
50
30
Distrito
Comercial 39
4
38
45
32
28
40
41
36
37
rbol de
expansin
mnima
43
35
Zona 2
Centro
55
Shopping
Center
44
Zona Sur
Zona Este
Solucin ptima mediante WINQSB
RED QU E
REPRESENTA LA
SOLUCIN PTIMA
Zona Norte
30
34
1
Bucle
38
45
32
28
40
Distrito
Comercial39
4
33
Zona Oeste
Universidad
50
43
35
Zona 2
Centror
55
41
37
36
Shopping
Center
44
Costo Total = $236 milliones
Zona Sur
Zona Este
rbol de expansin mnima
PROBLEMA
Juan Arroyo es propietario de un establo de caballos y planea
instalar un sistema de agua que conecte todos los establos y
graneros. La ubicacin de las instalaciones y distancias se
dan a continuacin
12
2
10
18
15
12
8
13
10
12
10
14
Juan Arroyo, debe
determinar la forma mas
barata de suministrar
agua a cada instalacin
rbol de expansin mnima
Ingreso de Datos
rbol de expansin mnima
Solucin
Problema del flujo mximo
Este modelo se utiliza para reducir los embotellamientos entre
ciertos puntos de partida y destino en una red.
Existe un flujo que viaja desde un nico lugar de origen hacia un
nico lugar destino a travs de arcos que conectan nodos
intermedios
Cada arco tiene una capacidad que no puede ser excedida
La capacidad no debe ser necesariamente la misma para cada
direccin del arco.
Nos permite conocer (calcular) la mxima cantidad de cualquier
artculo o informacin que podemos transportar desde un origen
hasta un destino.
El objetivo es encontrar la mxima cantidad de flujo que salga
del nodo 1 al nodo n sin exceder la capacidad de los arcos.
Problema del flujo mximo
Algunas Aplicaciones
Maximizar el flujo a travs de la red de distribucin de una
compaa desde sus fbricas hasta sus clientes.
Maximizar el flujo a travs de la red de suministros de una
compaa de proveedores a las fbricas.
Maximizar el flujo de petrleo por tuberas.
Maximizar el flujo de agua a travs de un sistema de
acueductos.
Maximizar el flujo de vehculos por una red de transporte.
Numero mximo de automviles que pueden fluir por una
carretera
Problema del flujo mximo
Definicin del Problema
Existe un nodo origen (con el nmero 1), del cual los flujos
emanan.
Existe un nodo terminal (con el nmero n), en el cual todos los
flujos de la red son depositados.
Existen n-2 nodos (nmerados del 2, 3,....,n-1), en el cual el
flujo que entra es igual al flujo que sale.
La capacidad Cij que transita del nodo i al nodo j, y la
capacidad Cji para la direccin opuesta.
Ejemplo 1: Problema de flujo mximo
de Seervada Park
Tiene varias fbricas y mltiples clientes. Se trata de aumentar la red
original que incluya una fuente ficticia y un destino ficticio y algunos
arcos nuevos.
A
5
4
2
E
Maximal Flow Problem
SOLUCION WINQSB
Ejemplo 2
Encontrar el flujo mximo, en la red,, dado
que la capacidad a travs del arco que va
del nodo i al nodo j es el nmero ms
cercano al nodo i del arco entre estos
4
A
nodos.
6
I
Origen
1
B
3
4
C
9
E
Final
Problema del flujo mximo
Solucin
WinQSB
Problema del flujo mximo
Solucin final
I
Problema del flujo mximo
EJEMPLO 3: COMPAA QUIMICA UNIDA
Qumica unida produce pesticidas y otros productos de control
agrcola.
El veneno qumico necesario para la produccin es depositado en
grandes tambores.
Una red de tubos y vlvulas regula el flujo del qumico de los
tambores a las diferentes reas de produccin.
El departamento de seguridad debe disear un procedimiento que
vace los tambores de la forma ms rpida posible dentro de los
tubos del rea de depsito, usando la misma red de tubos y vlvulas.
El procedimiento debe determinar:
- Qu vlvulas deben abrirse y cerrarse
- Estimar el tiempo total de descarga.
No se permite flujo de 4 a 2.
Datos
El mximo flujo de 2 a 4 es 8
2
6
1
10
1
Tambores
con qumico
6
4
10
1
0
3
3
0
7
0
4
2
12
0
8
5
Tubo de Se
El
El mximo
mximo flujo
flujo obtenido
obtenido por
por WINQSB
WINQSB
7
2
7
Flujo Mximo= 17
Tambores
con qumico
10
2
3
8
8
5
Tubo de Seg.
Problema del flujo mximo
PROBLEMA
PetroChem, una refinera de petrleo esta diseando una nueva planta
para producir combustible Diesel. La siguiente figura muestra la red de
los centros de procesamiento principales, junto con su velocidad de
flujo existente (en miles de galones). A la administracin de PetroChem
le gustara determinar la cantidad mxima de combustible que puede
fluir a travs de la planta, del nodo 1 al nodo 7
0
3
3
8
3
0
4
3
0
1
2
5 5
1
4
7
0
Evaluacin
1.
Que tcnica se utiliza para conectar todos los puntos de una red al
mismo tiempo que se minimiza la distancia entre ellos
a)
b)
c)
d)
e)
2.
Flujo mximo
Flujo mnimo
rbol de expansin mnima
Ruta mas corta
Distancia mas larga
En que tcnica se conecta el nodo mas cercano a la solucin
existente que actualmente no esta conectada
a)
b)
c)
d)
e)
rbol mnimo
Ruta mas corta
rbol de expansin mnima
Flujo mximo
Flujo mnimo
Evaluacin
3.
En la tcnica de la ruta mas corta, el objetivo es determinar la ruta
de un origen a un destino que pase por el menor numero de otros
nodos
a)
b)
4.
Verdadero
Falso
En cual tcnica los nmeros de capacidad de flujo en una
trayectoria es un paso importante
a)
b)
c)
d)
e)
rbol mnimo
Ruta mas corta
rbol de expansin mnima
Flujo mximo
Flujo mnimo
