jueves, 21 de noviembre de 2019
Método Pert
El método PERT (Program Evaluation and Review Technique) es una metodología que a diferencia de CPM permite manejar la incertidumbre en el tiempo de término de las actividades.
En este sentido el tiempo de ejecución de las actividades es obteniendo a través de la estimación de 3 escenarios posibles: optimista (a), normal (m) y pesimista (b). El tiempo (aleatorio) que requiere cada actividad esta asociado a una función probabilista beta, que ha demostrado ser la que mejor modela la distribución del tiempo de duración de una actividad. A continuación se presenta un gráfico que muestra la función de densidad de probabilidad para la función beta, la cual tiene una asimetría positiva.
Regla 1: Cada actividad se debe representar sí y sólo sí, por un ramal o arco.
Regla 2: Cada actividad debe estar identificada por dos nodos distintos. En el caso de existir actividades concurrentes (que inicien al mismo tiempo, o que el inicio de una actividad dependa de la finalización de 2 o más actividades distintas) se debe recurrir a actividades ficticias (representadas por arcos punteados que no consumen ni tiempo ni recursos) para satisfacer esta regla.
Por ejemplo, la actividad C para su inicio requiere que finalicen A y B. Las actividades A y B inician al mismo tiempo.
FASES PARA LA PLANIFICACIÓN DE UN PROYECTO CON PERT
PASO 1: ACTIVIDADES DEL PROYECTO
La primera fase corresponde a identificar todas las actividades que intervienen en el proyecto, sus interrelaciones, sucesiones, reglas de precedencia. Con la inclusión de cada actividad al proyecto se debe cuestionar respecto a que actividades preceden a esta, y a cuales siguen inmediatamente esta finalice. Además, deberán relacionarse los tiempos estimados para el desarrollo de cada actividad.
A diferencia del método CPM, el método PERT asume tres estimaciones de tiempo por cada actividad, estas estimaciones son:
Tiempo optimista (a): Duración que ocurre cuando el desarrollo de la actividad transcurre de forma perfecta. En la práctica suele acudirse al tiempo récord de desarrollo de una actividad, es decir, el mínimo tiempo en que una actividad de esas características haya sido ejecutada.
Tiempo más probable (m): Duración que ocurre cuando el desarrollo de la actividad transcurre de forma normal. En la práctica suele tomarse como el tiempo más frecuente de ejecución de una actividad de iguales características.
Tiempo pesimista (b): Duración que ocurre cuando el desarrollo de la actividad transcurre de forma deficiente, o cuando se materializan los riesgos de ejecución de la actividad.
PASO 2: ESTIMAR EL TIEMPO ESTIMADO (DURACIÓN PROMEDIO) Y LA VARIANZA
Para efectos de determinar la ruta crítica del proyecto se acude al tiempo de duración promedio, también conocido cómo tiempo estimado. Este tiempo es determinado a partir de las estimaciones como:
El cálculo del tiempo estimado deberá hacerse entonces para cada actividad. Por ejemplo para la actividad A:
Además de calcular el tiempo estimado, deberá calcularse la varianza de cada actividad. El cálculo de esta medida de dispersión se utiliza para determinar la incertidumbre de que se termine el proyecto de acuerdo al programa. Para efectos del algoritmo PERT, el cálculo de la varianza se hará a partir de sus estimaciones tal cómo se muestra a continuación:
El cálculo de la varianza deberá hacerse entonces para cada actividad. Por ejemplo para la actividad A:
Para las actividades del tabulado mencionado en el Paso 1, los tiempos estimados y varianzas serían las siguientes:
PASO 3: DIAGRAMA DE RED
Con base en la información obtenida en la fase anterior y haciendo uso de los conceptos básicos para diagramar una red, obtendremos el gráfico del proyecto (los tiempos relacionados con cada actividad en el gráfico corresponden a los tiempos estimados):
PASO 4: CALCULAR LA RED
Para el cálculo de la red se consideran 3 indicadores, T1, T2 y H. Estos indicadores se calculan en cada evento o nodo (entiéndase nodo entonces como un punto en el cual se completan actividades y se inician las subsiguientes.
T1: Tiempo más temprano de realización de un evento. Para calcular este indicador deberá recorrerse la red de izquierda a derecha y considerando lo siguiente:
- T1 del primer nodo es igual a 0.
- T1 del nodo n = T1 del nodo n-1 (nodo anterior) + duración de la actividad (tiempo estimado) que finaliza en el nodo n.
- Si en un nodo finaliza más de una actividad, se toma el tiempo de la actividad con mayor valor.
En este caso para el cálculo del T1 en el nodo 8, en el que concurre la finalización de 2 actividades, deberá considerarse el mayor de los T1 resultantes:
T1 (nodo 6) + G = 13 + 6 = 19
T1 (nodo 7) + H = 8 + 4 = 12
Así entonces, el T1 del nodo 8 será igual a 19 (el mayor valor).
T2: Tiempo más tardío de realización del evento. Para calcular este indicador deberá recorrerse la red de derecha a izquierda y considerando lo siguiente:
- T2 del primer nodo (de derecha a izquierda) es igual al T1 de este.
- T2 del nodo n = T2 del nodo n-1 (nodo anterior, de derecha a izquierda) - duración de la actividad que se inicia (tiempo estimado).
- Si en un nodo finaliza más de una actividad, se toma el tiempo de la actividad con menor valor.
En este caso para el cálculo del T2 del nodo 1, en el que concurren el inicio de 2 actividades deberá entonces considerarse lo siguiente:
T2 nodo 2 - B = 6 - 6 = 0
T2 nodo 3 - C = 9 - 2 = 7
Así entonces, el T2 del nodo 1 será 0, es decir el menor valor.
H: Tiempo de holgura, es decir la diferencia entre T2 y T1. Esta holgura, dada en unidades de tiempo corresponde al valor en el que la ocurrencia de un evento puede tardarse. Los eventos en los cuales la holgura sea igual a 0 corresponden a la ruta crítica, es decir que la ocurrencia de estos eventos no puede tardarse una sola unidad de tiempo respecto al cronograma establecido, dado que en el caso en que se tardara retrasaría la finalización del proyecto.
Las actividades críticas por definición constituyen la ruta más larga que abarca el proyecto, es decir que la sumatoria de las actividades de una ruta crítica determinará la duración estimada del proyecto. Puede darse el caso en el que se encuentren más de una ruta crítica.
Ruta crítica:
Esta ruta se encuentra compuesta por las actividades A, C, E, G, I, J. La duración del proyecto sería de 22 semanas.
PASO 4: CÁLCULO DE LA VARIANZA, DESVIACIÓN ESTÁNDAR Y PROBABILIDADES
La varianza y la desviación estándar para la culminación del proyecto se relacionan con las actividades que comprenden la ruta crítica. Así entonces, para calcular la varianza basta con sumar las varianzas de las actividades A, C, E, G, I y J:
La desviación estándar corresponde a la raíz cuadrada de la varianza del proyecto, es decir:
Con la información que acabamos de obtener podemos efectuar cálculos probabilísticos de terminación del proyecto. Por ejemplo, sí se nos pide hallar la probabilidad de que el proyecto se culmine antes de 26 semanas, procederíamos de la siguiente forma y siguiendo la teoría de distribución normal:
Buscando este valor en una tabla de distribución normal encontramos que equivale a 0,9612, es decir que la probabilidad de culminar el proyecto en 26 semanas o menos es del 96,12%.
PASO 4: ESTABLECER EL CRONOGRAMA
Para establecer un cronograma deberán considerarse varios factores, el más importante de ellos es la relación de precedencia, y el siguiente corresponde a escalonar las actividades que componen la ruta crítica de tal manera que se complete el proyecto dentro de la duración estimada.
martes, 29 de octubre de 2019
El camino mas corto y método Dijkstra
El Problema del Camino más Corto (o ruta más barata) consiste en encontrar una ruta o camino óptimo entre un nodo fuente y un nodo destino, los cuales están enlazados a través de una red con arcos que poseen un cierto atributo, el cual puede ser costo, distancia, tiempo, etc.
La Programación Entera permite abordar de forma eficiente este tipo de problemas, en especial cuando la cantidad de nodos y rutas posibles resulta ser un número significativo. Utilizar en estos casos un enfoque intuitivo de resolución es tedioso y de no ser exhaustivo no garantiza la identificación de la mejor alternativa o ruta.
Consideremos el siguiente diagrama donde los números asignados a cada uno de los arcos representan la distancia en kilómetros de un nodo a otro. Se desea encontrar la ruta con la distancia mínima para ir del nodo 1 al nodo 8.
El tamaño reducido de la red anterior permite encontrar el camino más corto simplemente enumerando las distintas alternativas que comenzando en el nodo 1 permita llegar al nodo 8. De esta forma las rutas posibles son:
- Ruta 1-2-5-7-8: 4+8+17+9=38[km]
- Ruta 1-3-4-7-8: 3+12+20+9=44[km]
- Ruta 1-3-4-6-8: 3+12+2+22=39[km]
- Ruta 1-3-4-8: 3+12+15=30[km]
- Ruta 1-3-6-8: 3+4+22=29[km]
La ruta o camino más corto esta dada por la secuencia 1-3-6-8 con una distancia total de 29[km].
A continuación se formula un modelo de Programación Entera que permite extender este tipo de resultados a un problema de estas características:
Variables de Decisión:
Función Objetivo: Minimizar la distancia total en [km] dada por la siguiente expresión:
Restricciones:
- La primera restricción (1) garantiza que sólo un nodo (entre el 2 y el 3) pueda ser el que se visita a continuación de comenzar en el nodo 1.
- La restricción (2) determina que si se visito el nodo 2 después del nodo 1, entonces necesariamente el nodo 5 será visitado después del nodo 2.
- La restricción (3) permite verificar que si el nodo 3 fue visitado luego del nodo 1, entonces a continuación se visita el nodo 4 o el nodo 6 (sólo uno de ellos).
- La restricción (4) establece que si el nodo 5 fue visitado luego del nodo 2, entonces el nodo 7 debe ser visitado luego del nodo 5.
- La restricción (5) garantiza que si el nodo 4 fue visitado luego del nodo 3, entonces a continuación se visita uno de los siguientes nodo: 7, 8 o 6.
- La restricción (6) indica que si el nodo 6 fue visitado inmediatamente luego de estar en el nodo 3 o 4, a continuación se visita el nodo 8.
- La restricción (7) determina que si el nodo 7 fue visitado inmediatamente luego de estar en el nodo 4 o 5, a continuación se visita el nodo 8.
- Finalmente la restricción (8) asegura que ya sea el nodo 7, 4 o 6 sea el último en visitar previo a terminar la ruta en el nodo 8.
Al implementar en Solver el problema del Camino más Corto o Ruta Mínima anterior se alcanzan los siguientes resultados:
Donde se corrobora que la ruta más corta (solución óptima) corresponde al camino 1-3-6-8 con una distancia total de 29[km] (valor óptimo).
Método Dijkstra:
El Algortimo de Dijkstra, también denominado Algoritmo de caminos mínimos, es un modelo que se clasifica dentro de los algoritmos de búsqueda. Su objetivo, es determinar la ruta más corta, desde el nodo origen, hasta cualquier nodo de la red. Su metodología se basa en iteraciones, de manera tal que en la práctica, su desarrollo se dificulta a medida que el tamaño de la red aumenta, dejándolo en clara desventaja, frente a métodos de optimización basados en programación matemática.
¿Qué tipos de redes pueden resolverse por medio del Algoritmo de Dijkstra?
Este algoritmo, al igual que el método de Floyd, tienen la capacidad de resolver el problema de la ruta más corta, tanto para redes cíclicas, como para redes acíclicas. De manera tal que los bucles que presente una red, no restringen el uso del algoritmo.
El algoritmo de Dijkstra hace uso y define etiquetas a partir del nodo origen y para cada uno de los nodos subsiguientes. Estas etiquetas contienen información relacionada con un valor acumulado del tamaño de los arcos y con la procedencia más próxima de la ruta.
Las etiquetas corresponden a los nodos, no a los arcos. En el algoritmo de Dijkstra, estas etiquetas son temporales y permanentes. Las etiquetas temporales son aquellas que son susceptibles de modificarse mientras exista la posibilidad de hallar para sí, una ruta más corta; de lo contrario, dicha etiqueta pasa a ser permanente.
Etiqueta = [acumulado, nodo procedente] iteración
Algoritmo de Dijkstra - Ejemplo
Teniendo en cuenta la siguiente red, que tiene como origen el nodo 1:
Procedemos con las iteraciones, partimos de la iteración 0, es decir, asignar la etiqueta para el nodo origen:
Iteración 0
En este paso, asignamos una etiqueta permanente para el nodo origen. Recordemos que la etiqueta se compone por un valor acumulado, que en este caso debe ser 0, ya que es el punto base y que no existe procedencia:
Etiqueta nodo 1 = [valor acumulado, procedencia] iteración
Etiqueta nodo 1 = [0, -] 0
Iteración 1
En este paso, evaluamos a cuáles nodos se puede llegar desde el nodo 1. En este caso se puede llegar a los nodos 2 y 3. De manera que debemos asignar las etiquetas para cada nodo:
Etiqueta nodo 2 = [valor acumulado, procedencia] iteración
Etiqueta nodo 2 = [0 + 100, 1] 1
0 es el valor acumulado en la etiqueta del nodo de procedencia, en este caso el valor acumulado para el nodo 1. 100 es el valor del arco que une el nodo procedencia (1) y el nodo destino (2). 1 es el número de la iteración.
Etiqueta nodo 3 = [valor acumulado, procedencia] iteración
Etiqueta nodo 3 = [0 + 30, 1] 1
En este caso, podemos observar que la etiqueta del nodo 3, ya contiene el menor valor acumulado posible para llegar a este. Ya que 30 es la mínima distancia posible, toda vez que para llegar al nodo 3 por medio del nodo 2, tendrá que recorrer como mínimo el valor absoluto del arco que une el origen con el nodo 2 = 100. Así entonces, la etiqueta del nodo 3 pasa a ser permanente.
Tabulamos la iteración 1:
Iteración 2:
En este paso, evaluamos las posibles salidas desde el nodo 3, es decir los nodos 4 y 5. De manera que debemos asignar las etiquetas para cada nodo:
Etiqueta nodo 4 = [valor acumulado, procedencia] iteración
Etiqueta nodo 4 = [30 + 10, 3] 2
Etiqueta nodo 4 = [40, 3] 2
30 es el valor acumulado en la etiqueta del nodo de procedencia, en este caso el valor acumulado para el nodo 3. 10 es el valor del arco que une el nodo procedencia (3) y el nodo destino (4). 2 es el número de la iteración.
Etiqueta nodo 5 = [valor acumulado, procedencia] iteración
Etiqueta nodo 5 = [30 + 60, 3] 2
Etiqueta nodo 4 = [90, 3] 2
30 es el valor acumulado en la etiqueta del nodo de procedencia, en este caso el valor acumulado para el nodo 3. 60 es el valor del arco que une el nodo procedencia (3) y el nodo destino (5). 2 es el número de la iteración.
En este caso, podemos observar que la etiqueta del nodo 4, contiene el menor valor acumulado posible para llegar a este. Así entonces, la etiqueta del nodo 4 pasa a ser permanente.
Tabulamos la iteración 2:
Iteración 3:
En este paso, evaluamos las posibles salidas desde el nodo 4, es decir los nodos 2 y 5. De manera que debemos asignar las etiquetas para cada nodo:
Etiqueta nodo 2 = [valor acumulado, procedencia] iteración
Etiqueta nodo 2 = [40 + 15, 4] 3
Etiqueta nodo 2 = [55, 4] 3
40 es el valor acumulado en la etiqueta del nodo de procedencia, en este caso el valor acumulado para el nodo 4. 15 es el valor del arco que une el nodo procedencia (4) y el nodo destino (2). 3 es el número de la iteración.
Etiqueta nodo 5 = [valor acumulado, procedencia] iteración
Etiqueta nodo 5 = [40 + 50, 4] 3
Etiqueta nodo 5 = [90, 4] 3
40 es el valor acumulado en la etiqueta del nodo de procedencia, en este caso el valor acumulado para el nodo 3. 50 es el valor del arco que une el nodo procedencia (4) y el nodo destino (5). 3 es el número de la iteración.
En este caso, podemos observar que el nodo 2 ahora cuenta con 2 etiquetas temporales, y definitivas, ya que no existe otra ruta hacia dicho nodo. De manera que se elige la etiqueta que tenga el menor valor acumulado. Así entonces, la etiqueta del nodo 2 con procedencia del nodo 4, pasa a ser permanente.
Tabulamos la iteración 3:
Iteración 4:
En este paso, evaluamos las posibles salidas desde el nodo 2 y el nodo 5. Sin embargo, el nodo 2 solo tiene un posible destino, el nodo 3, el cual ya tiene una etiqueta permanente, de manera que no puede ser reetiquetado. Ahora, evaluamos el nodo 5 y es un nodo que no tiene destinos. Así entonces, su etiqueta temporal pasa a ser permanente, en este caso cuenta con 2 etiquetas que tienen el mismo valor, es decir, alternativas óptimas. De esta manera concluye el algoritmo de Dijkstra.
¿Cuál es la ruta más corta?
La ruta más corta entre el nodo 1 (origen) y cualquier otro nodo de la red (destino), se determina partiendo desde el nodo destino y recorriendo las procedencias de sus etiquetas. Por ejemplo:
¿Cuál es la ruta más corta entre el nodo 1 y el nodo 4?
En este caso, debemos partir desde la etiqueta del nodo 4.
La ruta más corta entre el nodo 1 y el nodo 4 tiene un valor acumulado de: 40
Es necesario considerar, que los valores utilizados en los arcos de la red objeto de estudio del algoritmo de Dijkstra, no necesariamente representan distancias. Si bien, es un modelo que aborda el denominado "problema de la ruta más corta"; en la práctica, puede utilizarse para optimizar: distancia, costos, tiempo.
De hecho, los sistemas de ruteo utilizados en la actualidad, priorizan los costos y el tiempo como variable decisión de los modelos de optimización.
Suscribirse a:
Entradas (Atom)