PROGRAMACIÓN DINÁMICA MAYOR
La programación dinámica es una técnica matemática útil en la toma de una serie de decisiones
interrelacionados, proporciona un procedimiento sistemático para determinar la combinación de
decisiones que maximiza la efectividad total.
Se necesita un cierto grado de creatividad y un buen conocimiento de la estructura general de
los problemas de programación dinámica para reconocer cuándo un problema se puede resolver
por medio de estos procedimientos y cómo esto se puede llevar a cabo.
REDES
1. Encuentre el flujo máximo de la siguiente red, los números representan las distancias
correspondientes reales entre los nodos, el nodo inicial es AI y el terminal GT.
6 B 4
4 1 E 4
AI C GT
1 3 3 9
4 F
D
Solución
Los problemas de flujos máximos consisten en tratar de llevar desde el Nodo AI la mayor cantidad
flujo posible al Nodo destino GT. Tomando en cuenta que los arcos o aristas tienen capacidades
diferentes.
Este problema se resuelve por pasos o Iteraciones:
En cada paso o iteración elegimos un camino cualquiera y enviamos la cantidad que permite el
arco con menor capacidad de ese camino y vamos reduciendo la capacidad de cada arco
restando lo enviado.
6-4=2* B 4-4=0
4-3=1 1 E 4-4=0
AI C GT
1-1=0 3-1=2 3-3=0
1-1=0 4-1=3 3-1=2 F 9-3=6 6-1=5 5-1=4
D
Iteración 1: Se toma la ruta AI – B – E –GT, con valores {6, 4, 4} donde el valor menor
es 4, que se resta a cada arco, quedando {2, 0. 0}.
6-4=2 B 4-4=0
E 4-4=0
AI GT
Queda el arco como {2, 0. 0}.
Iteración 2: Se toma la ruta AI – C – E –GT, con valores {4, 1, 4} donde el valor menor
es 3, que se resta a cada arco, quedando {3, 0. 3}.
1–1=0 E 4–1=3
4-3=3
AI C GT
Queda el arco como {3, 0. 3}.
Iteración 3: Se toma la ruta AI – C – F –GT, con valores {4, 3, 9} donde el valor menor
es 3, que se resta a cada arco, quedando {1, 0. 6}.
4-3=1
AI C 3-3=0 9-3=6 GT
F
Queda el arco como {1, 0. 6}.
Iteración 4: Se toma la ruta AI – C – D –F –GT, con valores {4, 3, 4, 9} donde el valor
menor es 1, que se resta a cada arco, quedando {1, 0, 1, 6}.
AI C GT
4-3 = 1 3-3 = 0
4-3=1 9–3=6
F
D
Queda el arco como {1, 0, 1, 6}.
Iteración 5: Se toma la ruta AI – D –F –GT, con valores {4, 4, 9} donde el valor menor es
1, que se resta a cada arco, quedando {0, 0, 5}.
AI GT
4–4=0
F 9–4=5
D 4–4=0
Queda el arco como {0, 0, 5}.
Por lo anterior se puede ver que solo se logran enviar 9 unidades (máximo) al nodo destino GT
a pesar que en AI se tienen 2 unidades en el arco AI-B, pero como el arco B-E, de la Iteración
1 no tiene capacidad B-E=0 se quedan sin enviarse las unidades del arco AI-B.
2 B 0
1 0 E 0
AI C GT
0 2 2 4
2 F
D
Al solucionar se determina que AI – B = 2; pero después ya no hay capacidad en B – E = 0
De igual manera se tiene que AI – C = 1; pero C – E = 0, no se tiene capacidad de envío.
De donde se ha llegado al flujo máximo de la red con capacidad de 9., que son los valores
resultantes en la Ruta 1 que son los arcos AI – C = 1; C – D = 2; D – F = 2; F – GT = 4; ∑ = 9
Lo anterior porque la Ruta 2 que son loa arcos AI – C = 1; C – F = 2; F – GT = 4; ∑ = 7
Con base en lo anterior se toma la que envía la mayor cantidad, por lo tanto es la Ruta 1 = 9
