UNIVERSIDAD NACIONAL AUTÓNOMA DE HONDURAS
ASUNTO:
INFORME METODOS DE REDES
CATEDRATICO:
ING. NARCISO MELGAR
ASIGNATURA:
INVESTIGACION DE OPERACIONES
ALUMNOS:
ANGIE NICCOLLE REYES 20212020799
CINTHIA CAROLINA FERNANDEZ 20212000808
ANDREA STEPHANY VILLACORTA 20222000282
JAFETH RAMÒN LOPEZ 20212030407
ANGEL EDGARDO BÚ CALIX 20212030361
UNAH-CORTÉS 20 AGOSTO 2024
Introducción
La gestión eficiente de proyectos y recursos en redes es un desafío clave en múltiples
campos, desde la ingeniería hasta la logística y las telecomunicaciones. Herramientas como el
Algoritmo PERT (Program Evaluation and Review Technique)**, el Algoritmo de Flujo
Máximo, y el Algoritmo de la Ruta Más Corta juegan un papel crucial en la planificación,
optimización y ejecución de proyectos y procesos que involucran múltiples tareas
interdependientes, flujos de materiales o información, y rutas a través de una red.
El Algoritmo PERT es fundamental en la gestión de proyectos, permitiendo a los gestores
planificar y coordinar tareas complejas en condiciones de incertidumbre temporal. Al mismo
tiempo, el Algoritmo de Flujo Máximo optimiza el movimiento de recursos a través de una
red, asegurando que se maximice el uso eficiente de capacidades limitadas. Por su parte, el
Algoritmo de la Ruta Más Corta es esencial para encontrar la ruta de menor distancia o
tiempo en una red, optimizando trayectos y minimizando costos.
Estos algoritmos, cuando se aplican de manera complementaria, proporcionan soluciones
robustas a problemas complejos de planificación, optimización y gestión de recursos,
permitiendo a las organizaciones mejorar la eficiencia operativa y cumplir con sus objetivos
de manera más efectiva.
Objetivos
1. Presentar los principios fundamentales de cada algoritmo, explicando sus procesos,
aplicaciones y el tipo de problemas que resuelven en la gestión de proyectos y redes.
2. Demostrar cómo el Algoritmo PERT, el Algoritmo de Flujo Máximo y el Algoritmo de
la Ruta Más Corta pueden ser utilizados en situaciones reales para planificar proyectos,
optimizar el uso de recursos y determinar las rutas más eficientes.
3. Evaluar las similitudes y diferencias entre estos algoritmos, destacando cómo pueden ser
utilizados en conjunto para abordar problemas complejos que involucran múltiples variables y
restricciones.
4. Identificar las principales ventajas que ofrecen estos algoritmos en términos de
eficiencia, precisión y aplicabilidad, así como las limitaciones que pueden enfrentar en
proyectos y redes de gran escala o con alta complejidad.
5. Incluir ejemplos prácticos que ilustren cómo cada algoritmo puede ser aplicado para
resolver problemas específicos, desde la planificación y gestión de un proyecto complejo
hasta la optimización de rutas y flujos en una red de transporte o comunicación.
Algoritmo PERT
El algoritmo PERT (Program Evaluation and Review Technique) es una herramienta de
gestión de proyectos que se utiliza para planificar, programar y coordinar tareas dentro de un
proyecto. Desarrollado en la década de 1950 por la Marina de los Estados Unidos junto con la
empresa Lockheed, el método PERT se diseñó para gestionar proyectos complejos con
incertidumbre en la estimación de tiempos, como el desarrollo del misil balístico Polaris. El
algoritmo permite a los gestores de proyectos identificar las tareas críticas y evaluar el tiempo
mínimo necesario para completar un proyecto.
Descripción del Algoritmo PERT
El método PERT se basa en un modelo de red que representa las tareas (o actividades)
como nodos y las dependencias entre ellas como aristas. A continuación, se describen los
pasos principales del algoritmo:
1. Definición de Actividades y Secuencia: Identificar todas las tareas necesarias para
completar el proyecto y establecer el orden en que deben realizarse.
2. Estimación de Duraciones: Para cada tarea, se estiman tres duraciones de tiempo:
- Tiempo Optimista (O): El tiempo mínimo posible si todo sale mejor de lo esperado.
- Tiempo Pesimista (P): El tiempo máximo posible si todo sale mal.
- Tiempo Más Probable (M): El tiempo que se espera que tome la tarea bajo condiciones
normales.
Con estas tres estimaciones, se calcula el Tiempo Esperado (TE) para cada tarea utilizando la
fórmula:
TE = (O + 4M + P) / 6
3. Construcción del Diagrama de Red: Se dibuja un diagrama de red donde las tareas son
nodos, y las flechas indican la secuencia y las dependencias entre ellas.
4. Identificación de la Ruta Crítica: La Ruta Crítica es la secuencia de tareas que determina
la duración mínima total del proyecto. Se identifican todas las rutas posibles desde el inicio
hasta el final del proyecto, sumando los tiempos esperados de cada tarea en cada ruta. La ruta
con la mayor duración total es la ruta crítica.
5. Análisis de la Variabilidad y Riesgo: Debido a que el tiempo esperado se basa en
estimaciones, se calcula la varianza y la desviación estándar de cada tarea para evaluar el
riesgo de que el proyecto se retrase.
Ventajas del Algoritmo PERT
- Gestión de la Incertidumbre: Al utilizar estimaciones de tiempo optimista, pesimista y
más probable, PERT permite manejar la incertidumbre en la planificación del proyecto.
- Identificación de la Ruta Crítica: El algoritmo ayuda a identificar las tareas que son
críticas para el éxito del proyecto, lo que permite a los gestores enfocar sus recursos en ellas.
- Flexibilidad: Es adaptable a proyectos de cualquier tamaño y complejidad.
Limitaciones del Algoritmo PERT
- Estimaciones Subjetivas: La precisión de PERT depende de la exactitud de las
estimaciones de tiempo, que pueden ser subjetivas.
- Complejidad en Proyectos Grandes: En proyectos muy grandes, la cantidad de tareas y
dependencias puede hacer que la construcción y el análisis del diagrama PERT sea compleja.
- Suposición de Independencia: PERT asume que las tareas son independientes, lo cual
puede no ser cierto en todos los casos.
Aplicaciones del Algoritmo PERT
El algoritmo PERT se utiliza ampliamente en la gestión de proyectos en industrias como la
construcción, la ingeniería, el desarrollo de software y la fabricación. Es particularmente útil
en proyectos donde el tiempo es un factor crítico y existen incertidumbres significativas en las
duraciones de las tareas.
Ejemplo:
Para desarrollar este proyecto por el método PERT como las indicaciones mencionan
debemos calcular el tiempo esperado de la matriz que se nos proporcióna
Trazamos la gráfica de Gantt:
El método PERT soluciona esta deficiencia al tomar en cuenta las relaciones existentes
entre las diferentes actividades y nos proporciona la ruta crítica, es decir, identifica las
actividades que repercuten directamente en el proyecto.
Algoritmo del método PERT
Estimar los tiempos esperados de cada actividad.
Construir la red de proyectos, añadiendo actividades ficticias si es necesario para mantener
una relación de una actividad entre dos eventos.
Determinar los tiempos para eventos: a) Calcular la terminación próxima de cada evento
como la terminación próxima del evento anterior más el tiempo esperado de la actividad entre
esos eventos. b) Calcular la terminación lejana de cada evento de derecha a izquierda como la
terminación lejana del evento posterior menos el tiempo esperado de la actividad entre esos
eventos.
Si hay múltiples trayectorias que llegan a un evento, se elige la de mayor (para la
terminación próxima) o menor (para la terminación lejana) tiempo.
Se asigna un valor de terminación próxima igual a cero al evento inicial y la terminación
próxima del evento final se utiliza como su terminación lejana.
Los tiempos se indican con una cruz sobre cada evento, mostrando la terminación próxima
en la parte superior izquierda y la terminación lejana en el lado superior derecho.
Calcular los tiempos para las actividades:
La terminación próxima de la actividad (TPA) es la terminación próxima del evento más el
tiempo de duración de la actividad.
La holgura de una actividad se define como la diferencia entre la terminación próxima y la
terminación lejana de la actividad.
La ruta crítica consiste en las actividades con una holgura igual a cero.
Debido a la naturaleza probabilística de los tiempos de cada actividad, se calcula un
intervalo donde se espera que se encuentre el tiempo de terminación. Se utilizan fórmulas para
calcular la esperanza y la varianza de la variable que mide el tiempo de finalización del
proyecto.
Ejemplo
Encontrar la ruta crítica del siguiente proyecto: Un ingeniero eléctrico debe hacer una
instalación eléctrica en una ampliación realizada a una fábrica. A continuación, se presenta la
matriz de precedencia y tiempos estimados en días.
Estimamos los tiempos esperados de cada actividad
Construimos la red del proyecto.
Calculamos los tiempos de cada evento, utilizando la siguiente tabla.
Una vez que calculamos los tiempos de los eventos, calculamos los tiempos para
las actividades, para ello utilizamos la siguiente tabla:
De la tabla anterior concluimos que la ruta crítica está formada por los eventos A, B y E, es
decir:
RC = A + B + E
Por lo tanto, el ingeniero debe tener especial cuidado en:
La colocación de los ductos para el cableado.
Colocación de cables.
Colocación de contactos y arrancadores.
Para que, de esta manera, el proyecto se lleve a buen término. El tiempo esperado
para la terminación del proyecto es:
E(T) = 1.5 + 2 + 3 = 6.5 días
El tiempo esperado para la terminación del proyecto es de 6.5 días, con una desviación
estándar de0.5 días. Esto significa que el 68.27% de la probabilidad está dentro del intervalo
de [6,7] días
Ruta más corta
El algoritmo de la ruta más corta consiste, si es necesario decirlo, en
una modalidad de problemas de redes, en la cual se debe determinar el
plan de rutas que genere la trayectoria con la mínima distancia total, que
una un nodo fuente con un nodo destino, sin importar el número de nodos
que existan entre estos.
Se centra en identificar el camino de menor longitud entre un punto de
partida y un punto de llegada específicos, empleando los datos disponibles
en una red y respetando las condiciones establecidas, como la distancia y
las conexiones existentes.
Se considera una red conexa y no dirigida con dos nodos especiales
llamados origen y destino. A cada ligadura (arco no dirigido) se asocia una
distancia no negativa. El objetivo es encontrar la ruta más corta —la
trayectoria con la mínima distancia total— del origen al destino. La
esencia del proceso es analizar toda la red desde el origen y encontrar la
ruta más corta a cada uno de los nodos en orden ascendente de sus
distancias desde el origen. El problema se resuelve una vez llegando al
nodo destino.
Aplicaciones:
Planificación de rutas en redes de transporte (carreteras, ferrocarriles,
etc.).
Diseño de redes de comunicación (routers, switches).
Optimización de logística y distribución.
Algoritmo de la ruta más corta:
1. Objetivo de la n-ésima iteración: Encontrar el n-ésimo nodo más
cercano al origen
2. Datos para la n-ésima iteración: Son los n-1 nodos más cercanos al
origen, incluida su ruta más corta y la distancia desde el origen.
3. Candidatos para el n-ésimo nodo más cercano: Cada nodo resuelto
que tiene conexión directa por una ligadura con uno o más nodos no
resueltos, proporciona un candidato y éste es el nodo no resuelto que
tiene la ligadura más corta.
4. Cálculo del n-ésimo nodo más cercano: Para cada nodo resuelto y sus
candidatos, se suma la distancia entre ellos y la distancia de la ruta más
corta desde el origen a este nodo resuelto. El candidato con la distancia
total más pequeña es el n-ésimo nodo más cercano y su ruta más corta es
la que genera esta distancia
Ejemplo. La administración de Seervada Park necesita encontrar la ruta
más corta desde la entrada del parque (nodo O) hasta el mirador (nodo T)
a través del sistema de caminos que se presenta en la figura.
• La primera columna (n) indica el número de la iteración.
• La segunda proporciona una lista de los nodos resueltos para
comenzar la iteración actual,después de quitar los que no sirven (los que
no tienen conexión directa con nodos no resueltos).
• La tercera columna da los candidatos para el n-ésimo nodo más
cercano (nodos no resueltos con la ligadura más corta al nodo resuelto).
•La cuarta columna calcula la distancia más corta de la ruta desde el
origen a cada candidato, es decir, la distancia entre el nodo resuelto y la
ligadura que va al candidato.
Según la quinta columna, el nodo n-ésimo más cercano al origen es el
candidato con la suma de distancias más pequeña.
• Las dos columnas finales contienen la información necesaria para las
siguientes iteraciones, que es la distancia de la ruta más corta del origen
al nodo y la última rama de esta ruta.
Ahora se deben relacionar las columnas con la descripción del
algoritmo. Los datos para la n-ésima iteración se encuentran en las
columnas 5 y 6 de las iteraciones anteriores, donde los nodos resueltos de
la quinta columna se enumeran después en la segunda para la iteración
actual después de eliminar los que no tienen conexión directa con nodos
no resueltos. Los candidatos para el nésimo nodo más cercano se
enumeran en la tercera columna de la iteración actual. El cálculo del n-
ésimo nodo más cercano se realiza en la columna 4 y los resultados se
registran en las últimas tres columnas de la iteración actual.
La ruta más corta desde el nodo destino hasta el origen se puede
rastrear hacia atrás en la última columna de la tabla, con lo que se obtiene
T → D → E → B → A → O o bien T → D → B → A → O.
Por tanto, se identificaron las dos opciones de ruta más corta desde el
origen hasta el destino como
O → A → B → E → D → T y O → A → B → D → T, con una distancia total de
13 millas en cualquiera de las dos.
Flujo Máximo
Al intentar optimizar el flujo dentro de una red, se enfrenta un problema
donde se tiene un nodo inicial, denominado fuente, y otro nodo final, llamado
destino. La meta es aumentar al máximo posible la cantidad de flujo que se
desplaza desde la fuente hasta el destino. Es importante considerar que el flujo
en cada arco de la red se dirige en una sola dirección, tal como se especifica en
el diagrama que representa la red. En este contexto, el desafío consiste en
encontrar la manera de maximizar el flujo total que puede trasladarse desde el
nodo de origen hasta el nodo de llegada, respetando las capacidades y
restricciones de cada arco. Este tipo de problema se conoce comúnmente como
problema de flujo máximo, y su resolución implica la búsqueda de la
configuración óptima de flujos que permita transferir la mayor cantidad de
recurso posible a través de la red desde el punto de inicio hasta el punto final.
Este tipo de problema se aplica en múltiples áreas, incluyendo:
Optimización de la red de distribución en empresas
Se utiliza para aumentar al máximo el flujo de productos desde las fábricas
de una compañía hasta los clientes finales, garantizando una distribución
eficiente y oportuna.
Gestión de la cadena de suministro
Se enfoca en maximizar el flujo de materiales y recursos desde los
proveedores hasta las fábricas, mejorando la eficiencia en la producción y
reduciendo los costos de inventario y transporte.
Transporte de recursos naturales
Es crucial en la maximización del flujo de petróleo a través de sistemas de
tuberías, asegurando que el recurso se transporte de manera eficiente y segura
desde los pozos de extracción hasta las refinerías o puntos de distribución.
Distribución de agua en infraestructuras urbanas
Se emplea para maximizar el flujo de agua en un sistema de acueductos,
optimizando la entrega de agua potable desde las fuentes hasta los hogares y
empresas, garantizando un suministro adecuado y minimizando pérdidas.
Gestión del tráfico vehicular
Este enfoque es utilizado para maximizar el flujo de vehículos a través de
redes de transporte urbano, con el objetivo de mejorar la movilidad, reducir los
tiempos de viaje y disminuir la congestión en las calles y avenidas de una
ciudad.
Algoritmo de la trayectoria de aumento para resolver el problema de flujo
máximo:
1. Identificación de la trayectoria de aumento
Se busca una trayectoria en la red residual que conecte el nodo origen con el
nodo destino, asegurando que todos los arcos en esta trayectoria tengan una
capacidad residual estrictamente positiva. Si no se encuentra ninguna trayectoria
con estas características, significa que los flujos netos actuales representan una
solución óptima al problema de flujo máximo.
2. Determinación de la capacidad residual mínima
Una vez identificada la trayectoria de aumento, se analiza cada uno de los
arcos que la componen para determinar cuál es la capacidad residual mínima
entre ellos. Esta capacidad residual mínima se designa como c*, y representa la
máxima cantidad de flujo que se puede aumentar a lo largo de esta trayectoria.
3. Actualización del flujo y de la red residual
Se procede a incrementar en c* el flujo a lo largo de la trayectoria de
aumento. Como consecuencia, la capacidad residual de cada arco en dicha
trayectoria se reduce en c*. Adicionalmente, para cada arco de la trayectoria, se
incrementa en c* la capacidad residual de su arco en la dirección opuesta (esto
permite revertir parte del flujo si se descubre una mejor solución en iteraciones
posteriores).
4. Repetición del proceso
Se regresa al paso 1 para identificar una nueva trayectoria de aumento en la
red residual actualizada. Este proceso se repite hasta que no se puedan encontrar
más trayectorias de aumento con capacidad residual estrictamente positiva, lo
que indica que se ha alcanzado el flujo máximo en la red.
Ejemplo
Considera los flujos de la siguiente red y determina la trayectoria de
aumento para el problema de flujo máximo.
Primero se determina una trayectoria de aumento desde el nodo fuente hacia
el destino de la red residual, para este caso la trayectoria de aumento está dada
por 0→B→C→D→F, que tiene una capacidad residual igual al min (9,12,7,9) =
7, que corresponde a las capacidades residuales de cada arco. Asignamos el
flujo de 7 a esta trayectoria para obtener:
Otra trayectoria de aumento desde el nodo fuente hacia el destino de la red
residual para esta segunda iteración es la trayectoria de aumento por 0→
B→C→E→F, la cual tiene una capacidad residual igual al min (2,5,6,6) = 2, que
corresponde a las capacidades residuales de cada arco. Asignamos el flujo de 2
a esta trayectoria para obtener:
Iteración 3. Una trayectoria más será 0→A→C→E→F mín. (7, 7, 4, 4) = 4.
Asignamos el flujo de 4 a esta trayectoria para obtener:
Como ya no existen trayectorias de aumento, el patrón de flujo actual es
óptimo. Entonces la solución óptima de este problema de flujo máximo está
dada por la siguiente red:
Esto quiere decir que el flujo máximo para esta red es de 13 unidades.
CONCLUSIONES
1. Un modelo de redes consiste en un conjunto de nodos conectados por arcos, donde estos
arcos están asociados a la red de flujo. El flujo máximo en la red puede ser limitado o
ilimitado, dependiendo de las capacidades asignadas a cada arco.
2. El principal objetivo del algoritmo PERT es calcular el tiempo estimado necesario para
completar un proyecto. Esto se logra utilizando herramientas como las gráficas de Gantt, que
permiten crear un cronograma detallado de actividades y tiempos.
3. La función de la ruta más corta es identificar el camino de menor distancia entre un
punto de inicio y un punto de destino específico, considerando la disponibilidad de la red, la
distancia, y las conexiones existentes.
4. El flujo máximo tiene múltiples aplicaciones, como la optimización del flujo en redes de
distribución, cadenas de suministro, transporte de petróleo y agua. Es crucial que la red sea
conexa y dirigida para lograr estos objetivos.
