INTITUTO TECNOLÓGICO SUPERIOR
DE HUICHICHAPAN
Ingeniería en Gestión Empresarial
Actividad 2 (Práctica)
Cadena de suministro G1
M. en C. Ana Isabel Ramírez Sabino
Nava Saenz Alex Yadir
Semestre: Octavo
Grupo: 1
HUICHAPAN, HGO.
03/Febrero/2023
Introducción
La programación dinámica es una técnica matemática que se utiliza para la solución de
problemas matemáticos seleccionados, en los cuales se toma una serie de decisiones
en forma secuencial. Orientada a la solución de problemas con decisiones secuenciales
en etapas sucesivas donde se debe minimizar el coste total de dichas decisiones. En
cada etapa se valora no sólo el coste actual de tomar una decisión sino los costes
futuros que se originan a partir de ella.
Objetivo
Proporciona un procedimiento sistemático para encontrar la combinación de
decisiones que maximice la efectividad total, al descomponer el problema en
etapas, las que pueden ser completadas por una o más formas (estados), y
enlazando cada etapa a través de cálculos recursivos.
Encuentre la ruta más corta de la siguiente red. Los números representan las distancias
correspondientes reales entre los nodos.
Encuentre el flujo máximo de la red que se le muestra a continuación, donde el nodo
inicial es (AI) y el terminal es (GT).
Encuentre la ruta más corta de la siguiente red. Los números representan las
distancias correspondientes reales entre los nodos.
La solución problemas de ruta más corta se debe partir del origen (O) y debemos llegar
al Destino (T) y se tiene que hacer por la ruta más corta. Es decir, tenemos minimizar la
distancia del nodo Origen al Nodo destino como podemos observar tenemos 11 nodos.
Empezamos del origen (O) lo cual se puede llegar a A,B y C. pero tienen diferente
distancia 4,3 y 6.
La distancia de origen a los nodos es A=4, C=6, B=3
Como podemos ver toca ir al Nodo D y podemos llegar desde A y C. se puede llegar a D
por A con una distancia de 4+3=7; pero también desde C con distancia de 6+2=8, por lo
cual AD. Pero ahora toca ir a E, los nodos más cerca son B y C. por lo tanto se puede
llegar a E desde B con 3+6= 9; pero se puede llegar a E desde C con 6+5=11 la
distancia más corta es BE llegar Y para F se puede llegar desde C con 6 + 2= 8, D con
7+2=9; E con 9+1=10; el que tiene la distancia más corta de los tres es C con 8 por lo
que elegimos CF
La distancia de origen a los nodos es D=7, F=8, E=9
Tenemos que ir a G desde D y F. se puede ir a G desde D con 7+4=11; desde F con
8+2=10; por lo que elegimos FD. Toca ir a H desde E,F y G. se puede ir a H desde E
con 9+2= 11; desde F con 8+5=13, desde G 10+2=12; lo cual elegimos los nodos de EH
con la distancia 11. Toca ir a I desde los nodos más cercanos los cuales son E y H. se
puede ir desde E con 9 + 5=14; desde H con 11+3=14; pero aquí la distancia de ambos
es igual por lo cual hay dos opciones posibles. HI y EI
La distancia de origen a los nodos es G=10, H=11, I=14
Toca ir a T desde los nodos G,H y E por lo tanto se puede ir a T desde G con 10+7=17; desde H
con 11+8=29 o desde I con 14+4=18, se puede ver que de los tres la distancia más corta es 17
desde GT
Por lo cual la ruta más corta es OC-CF-FG-GT o lo que es lo mismo que O-C-F-G-T = 17
Encuentre el flujo máximo de la red que se le muestra a continuación,
donde el nodo inicial es (AI) y el terminal es (GT).
Este problema se resuelve por pasos o Iteraciones:
Encuentra el flujos máximo consiste en tratar de ir desde el Nodo AI la mayor cantidad de flujo posible al
Nodo GT. Se tiene que ir por un lado elegimos cualquiera y enviamos la cantidad con menor
capacidad y se va reduciendo la capacidad de cada uno restando lo enviado.
Primero vamos por AI – B – E-GT, en este vemos AIB, BE, EGT ahora el mínimo de la capacidad de los
arcos es: min 6,4,4 = 4 lo cual el mínimo es 4. En la red se reduce su capacidad en los arcos que
hemos utilizado. 4-4=0
6-4=2 4-4=0
Segundo elegimos a AI-C-F-GT , en este encontramos AIC, CF y FGT, por lo cual el mínimo de los
arcos es : min {4,3,9}=3
4-4=1
9-3=6
3-3=0
Tercero: Puede verse que después de los dos caminos hay capacidades que ya no son viables
para ir, es decir se han agotados; BE=0; EGT=0; CF=0, pero tenemos caminos de AI a GT. Uno es
AI-C-D-F-GT, en este camino encontramos los arcos: AIC, CD, DF,FGT, el mínimo de los arcos es:
min {1,3,4,6}= 1
1-1=0
6-1=5
4-1=3
3-1=2
Cuarta: Se están quedado cuatro arcos con capacidad cero. B-E, E-GT, AI-C, C-F. Pero teneos un
camino el cual es AI-D-F-GT con un mínimo de min (1,3,5)=1
5-1=4
1-1=0
3-1=2
Solo logramos ir con un flujo de nodo destino GT a pesar que en AI tengo 2 unidades en el arco
AIB pero como el arco BE no tiene capacidad (BE=0) se quedan sin enviarse. Por lo tanto hemos
llegado al flujo máximo de la red con capacidad de 9.
Conclusión
El primer ejercicio fue obtener la ruta más corta el cual se cumplió con el objetivo
teniendo el resultado de O-C-F-G-T = 17 Podemos observar que en el problema 2
con el objetivo de obtener el flujo máximo se realizó varios pasos para lograr el
objetivo el cual se llegó al resultado de 9 .
Referencias
DISTANCIA, F. D. (s.f.). UNIDAD 4. PROGRAMACIÓN DINÁMICA. Obtenido de
http://virtual.umng.edu.co/distancia/ecosistema/ovas/ingenieria_civil/
investigacion_de_operaciones_ii/unidad_4/DM.pdf
Plus, K. (05 de junio de 2020). TIP IO - 83. Algoritmo de Dijkstra. Ruta más corta. modelo de redes.
Ejercicio 6.3B-1 Taha 9e. Obtenido de https://www.youtube.com/watch?v=3mMb3IKnepY
Quispe, L. C. (28 de septiembre de 2014). PROGRAMACIÓN DINÁMICA EN REDES. Obtenido de
https://prezi.com/eemqwdenwzem/programacion-dinamica-en-redes/
Rodríguez, U. d. (s.f.). Problema de la ruta más corta. Obtenido de
https://analisisderedes.wordpress.com/unidad-ii/problema-de-la-ruta-mas-corta/
Unidad 6. (s.f.). Obtenido de
https://gc.scalahed.com/recursos/files/r157r/w13111w/MateNegocios_unidad%206.pdf
