13 problema de redes

redes

1. Objetivos del Capítulo
Conceptos y definiciones de redes.
Importancia de los modelos de redes
Modelos de programación lineal, representación en redes y
soluciones usando el computador para:
* Modelos de transporte.* Modelos de transporte.
* Modelos de capacidad de transporte* Modelos de capacidad de transporte
* Modelos de asignación* Modelos de asignación
* Modelo del vendedor viajero* Modelo del vendedor viajero
* Modelos de la ruta mas corta* Modelos de la ruta mas corta
* Modelos de la rama mas corta* Modelos de la rama mas corta
Modelo de Redes

2. Un problema de Un problema de redes es aquel que puede es aquel que puede
representarse por:representarse por:
Nodos
Arcos
8
9
10
1
0
7
6
Funciones en los arcos

3. Problemas de transporte o
Distribución de Mercancías
•Es un problema particular que se resuelve con los procedimientos de la
programación lineal.
•Un problema de transporte surge cuando se necesita un modelo costo-
efectividad 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 mercancía,
desde varias plantas (orígenes) a diferentes centros de
almacenamiento (destinos), de manera que se minimice el costo del
transporte
•la cantidad de los bienes disponibles en cada localización (origen) es
limitada y la cantidad de demanda de los bienes necesarios (destino)
en cada una de las localizaciones es conocida

4. Problemas de transporte o
Distribución de Mercancías
•Para que un problema pueda ser resuelto por el método del transporte
debe cumplir:
1)La función 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
producción 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 fábricas ni en los centros de ventas.

5. Problemas de Transporte
Foster Generation tiene plantas en
Cleveland, Bedford, New York, la
capacidad de producción para el siguiente
periodo de plantación para un tipo
especifico de generador es como sigue
OrigenPlanta Capacidad de
producción (unidades)
1 Cleveland 5,000
2 Bedford 6,000
3 New York 2,500
TOTAL 13,500
La empresa distribuye sus generadores a
través de 4 centros regionales de
distribución localizados en Boston,
Chicago, San Luís y Lexington; el
pronostico de la demanda de los centros
de distribución es como sigue:
OrigenCentro de
distribución
Pronostico demanda
(unidades)
1 Boston 6,000
2 Chicago 4,000
3 San Luis 2,000
4 Lexington 1,500
TOTAL 13,500
COSTO UNITARIO DE TRANSPORTE (FOSTER)
Origen Boston ChicagoSan LuisLexington
Cleveland3 2 7 6
Bedford 7 5 2 3
New York 2 5 4 5
Los costos unitario de los orígenes
hacia los destino se dan en la
siguiente tabla:

6. Problemas de Transporte
La administración desea
determinar cuanto de su
producción deberá embarcarse
desde cada una de las plantas
hacia cada uno de los centros
de distribución
El objetivo es determinar las
rutas a usar y la cantidad a
embarcar en cada una de ellas
y que den el mínimo costo de
transporte total
1
Cleveland
2
Bedford
3
New York
1
Boston
2
Chicago
3
San Luis
4
Lexington
5000
6000
2500
6000
4000
2000
1500
3
2
7
6
7
5
2
3
2
5
4
5
Plantas
(Origen)
Centro Distribución
(Destino)
Costo
transporte
Unitario

7. Problemas de Transporte
Cleveland = 3X
11
+ 2X
12
+ 7X
13
+ 6X
14
Bedford = 3X
21
+ 2X
22
+ 7X
23
+ 6X
24
New York = 3X
31
+ 2X
32
+ 7X
33
+ 6X
34
La función objetivo es minimizar el costo total de transporte de Foster Generation,
para esto se debe sumar los costos de transporte de cada planta (origen)
+
Restricciones
de Suministro:
Suministro de Cleveland X
11
+ X
12
+ X
13
+ X
14
≤ 5000
Suministro de Bedford X
21
+ X
22
+ X
23
+ X
24
≤ 5000
Suministro de New York X
31
+ X
32
+ X
33
+ X
34
≤ 5000
Cada uno de los suministros
tiene una demanda especifica
Restricciones
de Demanda:
de Boston X
11
+ X
21
+ X
31
= 6000
de Chicago X
12
+ X
22
+ X
33
= 4000
de San Luís X
13
+ X
23
+ X
33
= 2000
Cada centro de distribución
tiene una demanda para
asegurar satisfacer las
demandas de los destinos de Lexington X
14
+ X
24
+ X
34
= 1500

8. Combinando la
función objetivo
y las
restricciones en
un modelo de
programación
lineal
Problemas de Transporte
VariableX11X12X13X14X21X22X23X24X31X32X33X34
Minimize 3 2 7 6 7 5 2 3 2 5 4 5
C1 1 1 1 1 >=
500
0
C2 1 1 1 1 >=
600
0
C3 1 1 1 1>=
250
0
C4 1 1 1 =
600
0
C5 1 1 1 =
400
0
C6 1 1 1 =
200
0
C7 1 1 1=
150
0
DecisionSolutionUnit Cost orTotal Reduced
VariableValue Profit C(j)ContributionCost
1X11 3,500.00 310,500.00 0
2X12 1,500.00 2 3,000.00 0
3X13 0 7 0 8
4X14 0 6 0 6
5X21 0 7 0 1
6X22 2,500.00 512,500.00 0
7X23 2,000.00 2 4,000.00 0
8X24 1,500.00 3 4,500.00 0
9X31 2,500.00 2 5,000.00 0
10X32 0 5 0 4
11X33 0 4 0 6
12X34 0 5 0 6
ObjectiveFunction(Min.) = 39,500.00

9. Problemas de Transporte (QSB)

10. R
ango O
ptim
o
Análisis de Sensibilidad por WINQSB
Análisis de Sensibilidad por WINQSB

11. R
a
n
g
o

d
e

f
a
c
t
i
b
i
l
i
d
a
d
Precio sombra de la distribuidora - el costo de demandar
una unidad más por la distribuidora.
Precio sombra de la planta - el costo de cada unidad
extra disponible en la planta.

12. Interpretación de los resultados del análisis de
sensibilidad.
* Reducción de Costos: * Reducción de Costos:
- La cantidad a transportar que reduce el costo por unidad entrega la La cantidad a transportar que reduce el costo por unidad entrega la
ruta más económicamente atractiva. ruta más económicamente atractiva.
- Si una ruta debe usarse obligatoriamente, incurriendo asi en el costo Si una ruta debe usarse obligatoriamente, incurriendo asi en el costo
que ello significa, por cada carga transportada , el costo total que ello significa, por cada carga transportada , el costo total
aumentara en una cantidad igual a la reducción del costo hecha. aumentara en una cantidad igual a la reducción del costo hecha.
* Precios Sombra:* Precios Sombra:
-Para las plantas el precio sombra de transporte corresponde al costo Para las plantas el precio sombra de transporte corresponde al costo
de cada unidad disponible en la planta. de cada unidad disponible en la planta.
- Para las distribuidoras, el precio sombra de transporte corresponde Para las distribuidoras, el precio sombra de transporte corresponde
al costo de cada unidad extra demandada por la distribuidora. al costo de cada unidad extra demandada por la distribuidora.

13. 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
distribución (destino)
Segundo Identificar las celdas donde se almacenan los valores de las
variables de decisión

14. Problemas de Transporte (Solver)
Seleccione el menú Herramientas  Solver (Resolver)
La solución óptima
de este problema es

15. VARIANTES DEL PROBLEMAVARIANTES 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
modificación al modelo de PL, aparecerá en la solución de la PL
un suministro excedente (como una holgura)
b) Si Oferta < demanda total: el modelo no tendrá solución 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.Maximización de la función objetivo: simplemente se resuelve como
maximización en vez de minimización, las restricciones no cambian
3.Rutas con capacidad limitada: una o mas rutas pueden tener
capacidad limitada o cantidades mínimas.
4.Rutas no aceptables o prohibidas: se hace desaparecer el arco
correspondiente de la red y se elimina la variable correspondiente al
modelo. O también se le asigna un costo muy alto para impedir que
sea utilizada por la solución optima

16. Modelos de
Asignación

17. • Asignar tareas a maquinarias, agentes a trabajos especiales,
personal de ventas a territorios, contratos a licitantes
• Una característica que distingue a los problemas de
asignación es que un agente se le asigna a una y solamente
una tarea
• Buscamos el conjunto de asignaciones que optimizarán un
objetivo dado (minimizar el tiempo o maximizar la utilidad)
• El problema de asignación 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 AsignaciónModelos de Asignación

18. Definición del Problema
* m trabajadores deben ser asignados a m trabajos.* m trabajadores deben ser asignados a m trabajos.
* Un costo unitario (o ganancia) C* Un costo unitario (o ganancia) C
ij ij es asociado al trabajador i que es asociado al trabajador i que
realizara el trabajo j.realizara el trabajo j.
* Minimizar el costo total ( o maximizar la ganancia total) de la * Minimizar el costo total ( o maximizar la ganancia total) de la
asignación de trabajadores a sus respectivos empleos que le asignación de trabajadores a sus respectivos empleos que le
corresponde a cada uno, tratando de que esta asignación sea la corresponde a cada uno, tratando de que esta asignación sea la
óptima posible.óptima posible.
Modelos de AsignaciónModelos de Asignación

19. Modelos de Asignación – Ejemplo:Modelos de Asignación – 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 líder o
jefe del proyecto (agente) a cada cliente (tarea). Fowle cuenta con 3
ejecutivos que están disponibles, sin embargo se da cuenta de que el
tiempo requerid para terminar cada uno de los estudios dependerá de la
experiencia del líder de proyecto.
La administración de Fowle desea asignar lideres de proyecto para
minimizar el numero total de días necesarios para completar los 3
proyectos. Si se debe asignar a un líder a un solo cliente. ¿Qué
asignaciones deberán efectuarse?
Líder proyecto Cliente
1 2 3
1 Terry 10 15 9
2. Carle 9 18 5
3. McClymond 6 14 3
Tiempo
estimado
(días) de
terminación
del proyecto

20. Solución del problema como asignación
•Los nodos corresponden a lideres del proyecto y a clientes, y los arcos
representan asignaciones posibles de líder del proyecto a cliente
•La oferta en cada nodo y la demanda en cada nodo es igual a 1
•El costo de asignar un líder del proyecto a un cliente es el tiempo que le tomara
a dicho líder terminar la tarea del cliente

21. VARIANTES DEL PROBLEMAVARIANTES 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
asignación.
b) Si numero de tareas > Agentes: el modelo no tendrá solución factible.
Se agrega agentes ficticios para igualar al numero de tareas
2.Maximización de la función objetivo: simplemente se resuelve como
maximización en vez de minimización, las restricciones no cambian
3.Asignaciones no aceptables : se puede eliminar la variable de decisión en
la formulación del PL. Esta situación pudiera ocurrir si uno de los agentes no
tuviera la experiencia necesaria para una o mas de las tareas
åå
==
m
1i
n
1J
CijXij Min.
å
å
=
=
=
£
m
i
n
j
Xij
Xij
1
1
1
1 i = 1, 2, …, m
Agentes
i = 1, 2, …, m
Agentes
Modelo de Asignación

22. 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

23. EjerciciosEjercicios: Transportes y
Asignación
1.El viernes 13 de abril, Carbón del Perú SA
tenia carros vacios en las siguientes
localidades con las cantidades indicadas
Población Oferta de Carros
Origen 1 35
Origen 2 60
Origen 3 25
2.Para el Lunes 16 de abril, las siguientes
localidades necesitaran carros de carbón,
según el orden siguiente
3.El despachador construye una tabla de Km
de distancia para las localidades anteriores.
Población Oferta de Carros
Destino 1 30
Destino 2 45
Destino 3 25
Destino 4 20
PoblaciónDestino 1Destino 2Destino 3Destino 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 carbón

24. EjerciciosEjercicios: Transportes y
Asignación
•Una empresa fabrica acondicionadores de aire en Houston, Phoenix y
Mamphis. Los aparatos se envían a distribuidores regionales
localizados en Dallas, Atlanta y Denver. Los costos de envió varían y a
la compañía le gustaría 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
DallasAtlantaDenver
Houston$ 8 $ 12 $ 10
Phoenix$ 10$ 14 $ 9
Memphis$ 11$ 8 $ 12
Cuantas unidades deberán ser enviadas de cada planta a cada centro
de distribución regional. ¿Cuál es el costo total de esta operación?

25. EjerciciosEjercicios: Transportes y
Asignación
•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 estándar 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
Demanda 90 70 40 50 250
¿Cuantos envíos deberán hacerse semanalmente de cada banco de
sangre a cada hospital de modo que los costos de envió totales se
reduzcan al mínimo

26. Problema de
trasbordo

27. Problema de Trasbordo
•El problema de trasbordo es una extensión 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 deberán
embarcarse en cada uno de los arcos de la red, de manera que todas las
demandas – destino se satisfagan al costo de transporte mínimo posible
å
arcos los todos
CijXijMin
j destino de Nodo j Demanda
Trasbordo de Nodos 0
iOrigen de Nodos i Suministro
salida de arcosentrada de arcos
entrada de arcossalida de arcos
entrada de arcossalida de arcos
=-
=-
£-
åå
åå
åå
XijXij
XijXij
XijXij
Sujeto a
Xij = numero de unidades
embarcadas del nodo i al nodo j
Cij = Costo unitario de embarque
del nodo i al nodo j

28. Ryan Electronic es una empresa con instalaciones de producción en Denver y en
Atlanta. Los componentes de producción en cualquiera de estas instalaciones
pueden ser embarcadas a cualquiera de los almacenes de la empresa que están
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
Orleáns.
Almacén
PlantaKansas
City
Louisville
Denver 2 3
Atlanta 3 1
Distribución al detalle
Almacén Detroi
t
MiamiDallas Nueva
Orleáns
Kansas City 2 6 3 6
Louisville 4 4 6 5

29. 1
Denver
2
Atlanta
3
Kansas
City
4
Louisville
6
Miami
8
Nueva
Orleans
5
Detroit
7
Dallas
2
3
3
1
600
400
2
6
3
6
4
4
6
5
200
150
350
300
Plantas
(nodo origen)
Almacenes
(nodo de trasbordo)
Distribuidores al menudeo
(nodo destino)
Suministros
Demandas
Rutas de distribución
(arcos)

30. •Igual que el problema de transporte y de asignación, podemos
formular un modelo de PL a partir de la representación en red.
•Supongamos que Xij denota el número 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 (almacén 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 almacén, es decir
Almacén de
Kansas City
(Nodo 3)
Unidades embarcadas
hacia fuera del nodo 3
Unidades embarcadas
hacia fuera del nodo 3
X13 + X12 X35 + X36 + X37 + X38

31. 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 = 200satisfacer la demanda de 200 unidades en el nodo 5
X36 + X46 = 150satisfacer la demanda de 200 unidades en el nodo 6
X37 + X47 = 350satisfacer la demanda de 200 unidades en el nodo 7
X38 + X48 = 300satisfacer la demanda de 200 unidades en el nodo 8
La función objetivo refleja el costo total de embarque en las 12 rutas de embarque.
Combinando la función objetivo y las restricciones nos lleva al modelo de PL con
12 variables y 8 restricciones del problema de trasbordo de Ryan Electronics

32. 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 = 200
X36 + X46 = 150
X37 + X47 = 350
X38 + X48 = 300

33. Problema del vendedor viajero
Definición del problema
–Existen m nodos
–Un costo unitario C
ij
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.

34. Importancia
- Diversas aplicaciones pueden ser resueltas como un - Diversas aplicaciones pueden ser resueltas como un
problema de vendedor viajeroproblema de vendedor viajero
- Ejemplo- Ejemplo
* Rutas a seguir por buses escolares* Rutas a seguir por buses escolares
* Distribución de bombas militares* Distribución de bombas militares
- El problema tiene importancia teórica porque este representa - El problema tiene importancia teórica porque este representa
una clase de problemas llamados NP-completos.una clase de problemas llamados NP-completos.
Complejidad
Escribir el modelo matemático y resolverlo resulta muchas
veces incómodo, ya que un problema de 20 ciudades requiere
de 500,000 restricciones.

35. 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
Tiempo en minutos para trasladarse de una oficina a otraTiempo en minutos para trasladarse de una oficina a otra
Hacia la oficina
H 1 2 3 4
FOf. Princ 30 45 65 80
rOf. 1 30 25 50 50
oOf. 2 45 25 40 40
mOf. 3 65 50 40 35
Of. 4 80 50 40 35
Problema del vendedor viajero

36. Red que representa el problema de vendedor viajero de AGERed que representa el problema de vendedor viajero de AGE
30
25
40
35
80
6545
50
50
40
Of. Princ
1
2
3
4
Problema del vendedor viajero

37. Solución
- Identificación de los posibles ciclos.- Identificación de los posibles ciclos.
* Existen (m-1)! ciclos posibles* Existen (m-1)! ciclos posibles
* Solo problemas pequeños pueden ser * Solo problemas pequeños pueden ser
resueltos.resueltos.
- Se utiliza una combinación de problemas de - Se utiliza una combinación de problemas de
asignación con la técnica Branch and Bound asignación con la técnica Branch and Bound
(ramas y (ramas y
consolidados) consolidados)
- Problemas con menos de 20 nodos pueden ser - Problemas con menos de 20 nodos pueden ser
resueltos en forma eficiente por este método. resueltos en forma eficiente por este método.

38. Datos de entrada para el problema de vendedor viajero en WINQSB
Datos de entrada para el problema de vendedor viajero en WINQSB

39. Solución de WINQSB -Una combinación de
problema de asignación y la técnica
Branch and Bound
Solución de WINQSB -Una combinación de
problema de asignación y la técnica
Branch and Bound

40. 30
25
40
35
80
6545
50
50
40
Of. Princ
1
2
3
4

41. Problemas de la Ruta más 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.
•Definición del Problema
- - Se tienen n nodos, partiendo del nodo inicial 1 y terminando Se tienen n nodos, partiendo del nodo inicial 1 y terminando
en el nodo final n. en el nodo final n.
- Arcos bi-direccionales conectan los nodos i y j con distancias - Arcos bi-direccionales conectan los nodos i y j con distancias
mayores que cero, d mayores que cero, d
ijij
- Se desea encontrar la ruta de mínima distancia que conecta - Se desea encontrar la ruta de mínima distancia que conecta
el nodo 1 con el nodo n. el nodo 1 con el nodo n.
•Por medio de la aplicación del algoritmo de este problema podemos
conocer la menor distancia entre un nodo origen y un nodo destino.

42. Ejemplo 1:
•La administración de Seervada Park necesita determinar
los caminos bajo los cuales se deben tender las líneas
telefónicas para conectar las estaciones con una
longitud total mínima de cable.
•Se describirá paso a paso la solución 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 líneas delgadas representan ligaduras
potenciales.
Problemas de la Ruta más corta

43. RED SEERVADA PARK
Problemas de la Ruta más corta

44. Usando WinQSB

45. Lineas Fairway Van
Determine la ruta mas corta entre Seattle y El
Paso para la siguiente red de carreteras.
Problemas de la Ruta más corta

46. Salt Lake City
1
2
3 4
5
6
7 8
9
10
11
12
13
14
15
16
17
18
19
El Paso
Seattle
Boise
Portland
Butte
Cheyenne
Reno
Sac.
Bakersfield
Las Vegas
Denver
Albuque.
Kingman
Barstow
Los Angeles
San Diego
Tucson
Phoenix
599
691
497
180
432
345
440
102
452
621
420
526
138
291
280
432
108
469
207
155
114
386
403
118
425 314

48. Problemas de la Ruta más corta

49. Árbol de expansión mínima
•Determina la trayectoria a través de una red que conecta
todos los puntos minimizando la distancia total sin formar
bucles
•El árbol de expansión mínima es apropiado para
problemas en los cuales la redundancia es expansiva, o
el flujo a lo largo de los arcos se considera instantáneo.
•Ejemplo: conectar todas las casas a la energía eléctrica,
sistema cableado telefonico, sistemas de tuberías de
agua

50. EL TRANSITO DEL DISTRITO METROPOLITANO
•La ciudad de Jaen esta planificando el desarrollo de una
nueva línea en sistemas de tránsito.
•El sistema debe unir 8 residencias y centros comerciales.
•El distrito metropolitano de transito necesita seleccionar
un conjunto de líneas que conecten todos los centros a
un mínimo costo.
•La red seleccionada debe permitir:
- Factibilidad de las líneas que deban ser construídas.- Factibilidad de las líneas que deban ser construídas.
- Mínimo costo posible por línea.- Mínimo costo posible por línea.
Árbol de expansión mínima

51. 5
2 6
4
7
8
1
3
Zona Oeste
Zona Norte
Universidad
Distrito
Comercial
Zona Este
Shopping
Center
Zona Sur
Zona
Centro
3
3
50
3
0
5
5
34
2
8
3
2
35
39
45
3
8
43
44
41
3
7
3
6
4
0
RED QUE
REPRESENTA
EL ARBOL
EXPANDIDO.
Árbol de
expansión
mínima

52. Solución óptima mediante WINQSB

53. Shopping
Center
Bucle
5
2 6
4
7
8
1
3
Zona Oeste
Zona Norte
Universidad
Distrito
Comercial
Zona Este
Zona Sur
Zona
Centror
3
3
50
3
0
5
5
34
2
8
3
2
35
39
45
3
8
43
44
41
3
7
3
6
4
0
Costo Total = $236 milliones
RED QU E
REPRESENTA LA
SOLUCIÖN ÖPTIMA

54. 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 ubicación de las instalaciones y
distancias se dan a continuación
Árbol de expansión mínima
1
2
3
4
5
7
86
Juan Arroyo, debe
determinar la forma mas
barata de suministrar
agua a cada instalación
12
13
14
9
18
15
12
8
12
10
8
10
10

55. Árbol de expansión mínima
Ingreso de DatosIngreso de Datos

56. Árbol de expansión mínima
SoluciónSolución

57. Problema del flujo máximo
•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 través 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
dirección del arco.
•Nos permite conocer (calcular) la máxima cantidad de
cualquier artículo o información que podemos transportar
desde un origen hasta un destino.
•El objetivo es encontrar la máxima cantidad de flujo que salga
del nodo 1 al nodo n sin exceder la capacidad de los arcos.

58. Problema del flujo máximo
Algunas Aplicaciones
( !
)& %

(
)& %

( !&

(


( &

"% !

•Maximizar el flujo a través de la red de distribución de una
compañía desde sus fábricas hasta sus clientes.
•Maximizar el flujo a través de la red de suministros de una
compañía de proveedores a las fábricas.
•Maximizar el flujo de petróleo por tuberías.
•Maximizar el flujo de agua a través de un sistema de
acueductos.
•Maximizar el flujo de vehículos por una red de transporte.
•Numero máximo de automóviles que pueden fluir por una
carretera

59. Definición del Problema
•Existe un nodo origen (con el número 1), del cual los Existe un nodo origen (con el número 1), del cual los
flujos emanan.flujos emanan.
•Existe un nodo terminal (con el número n), en el cual Existe un nodo terminal (con el número n), en el cual
todos los flujos de la red son depositados.todos los flujos de la red son depositados.
•Existen n-2 nodos (númerados del 2, 3,....,n-1), en el Existen n-2 nodos (númerados del 2, 3,....,n-1), en el
cual el flujo que entra es igual al flujo que sale.cual el flujo que entra es igual al flujo que sale.
•La capacidad CLa capacidad C
ij ij que transita del nodo i al nodo j, y la que transita del nodo i al nodo j, y la
capacidad Ccapacidad C
jiji para la dirección opuesta. para la dirección opuesta.
Problema del flujo máximo

60. Ejemplo 1: Ejemplo 1: Problema de flujo máximo
de Seervada Park
O
A
D
B
C E
T
5
3
7
4
4
2
4
5
9
6
1
1
Tiene varias fábricas y múltiples clientes. Se trata de aumentar la red
original que incluya una fuente ficticia y un destino ficticio y algunos
arcos nuevos.

61. Maximal Flow Problem
SOLUCION WINQSB

62. Ejemplo 2
•Encontrar el flujo máximo, en la red,, dado que la
capacidad a través del arco que va del nodo i al nodo j
es el número más cercano al nodo i del arco entre
estos nodos.
6
3
4
1
1
4
9
4
4
3
I
A
B
C
T
D
E
Origen
Final

63. Solución
WinQSB
Problema del flujo máximo

64. Solución final
I A
B
TD
E
C
Problema del flujo máximo

65. EJEMPLO 3: COMPAÑÍA QUIMICA UNIDA
•Química unida produce pesticidas y otros productos de control
agrícola.
•El veneno químico necesario para la producción es depositado en
grandes tambores.
•Una red de tubos y válvulas regula el flujo del químico de los
tambores a las diferentes áreas de producción.
•El departamento de seguridad debe diseñar un procedimiento que
vacíe los tambores de la forma más rápida posible dentro de los
tubos del área de depósito, usando la misma red de tubos y válvulas.
•El procedimiento debe determinar:
- Qué válvulas deben abrirse y cerrarse- Qué válvulas deben abrirse y cerrarse
- Estimar el tiempo total de descarga.- Estimar el tiempo total de descarga.
Problema del flujo máximo

66. DatosDatos
Tambores
con químico
Tubo de Seg.
1
7
4
2
3
6
5
10
0
8
0
0
0
0
0
0
0
10
6
1
12
1
4
4
2
2
8
3
3
7
2
El máximo flujo de 2 a 4 es 8
No se permite flujo de 4 a 2.

67. El máximo flujo obtenido por WINQSB El máximo flujo obtenido por WINQSB
Tambores
con químico
Tubo de Seg.
1
7
4
2
3
6
5
8
8
2
7
7
10
7
8
2
Flujo Máximo= 17

68. PROBLEMA
•PetroChem, una refinería de petróleo esta diseñando 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 administración de
PetroChem le gustaría determinar la cantidad máxima de combustible
que puede fluir a través de la planta, del nodo 1 al nodo 7
Problema del flujo máximo
1
2
3
4
6
75
2
6
9
0
2
1
0
4
4
0
0
5
8
1
1
3
3
3
4
3
1
01
5
3

69. EvaluaciónEvaluación
1.Que técnica se utiliza para conectar todos los puntos de una red al
mismo tiempo que se minimiza la distancia entre ellos
a)Flujo máximo
b)Flujo mínimo
c)Árbol de expansión mínima
d)Ruta mas corta
e)Distancia mas larga
1.En que técnica se conecta el nodo mas cercano a la solución
existente que actualmente no esta conectada
a)Árbol mínimo
b)Ruta mas corta
c)Árbol de expansión mínima
d)Flujo máximo
e)Flujo mínimo

70. EvaluaciónEvaluación
3.En la técnica 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)Verdadero
b)Falso
3.En cual técnica los números de capacidad de flujo en una
trayectoria es un paso importante
a)Árbol mínimo
b)Ruta mas corta
c)Árbol de expansión mínima
d)Flujo máximo
e)Flujo mínimo