Investigación De Operaciones

El método PERT (Project Evaluation and Review Techniques), es un algoritmo basado en la teoría de redes diseñado para facilitar la planificación de proyectos. El resultado final de la aplicación de este algoritmo será un cronograma para el proyecto, en el cual se podrá conocer la duración total del mismo, y la clasificación de las actividades según su criticidad.

El algoritmo PERT se desarrolla mediante intervalos probabilísticos, considerando tiempos optimistas, probables y pesimistas, lo cual lo diferencia del método CPM que supone tiempos determinísticos.

CONCEPTOS BÁSICOS PARA DIAGRAMAR ACTIVIDADES CON REDES

Regla 1: Cada actividad se debe representar sí y sólo sí, por un ramal o arco.

Teoría de Redes — www.ingenieriaindustrialonline.com

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

Red PERT

La red PERT (a veces denominada gráfico PERT) consta de los siguientes elementos:

Tareas (a veces denominadas actividades o etapas), representadas por una flecha. Se le asigna a cada una de las tareas un código y una duración. Sin embargo, la longitud de la flecha es independiente de la duración de la tarea.

Etapas, es decir, el inicio y el final de la tarea. Cada tarea tiene una etapa de inicio y una de finalización. Con excepción de las etapas iniciales y finales, cada etapa final es una etapa de inicio de la siguiente tarea. Las etapas generalmente están numeradas y representadas por un círculo, pero en algunos otros casos pueden estar representadas por otras formas (cuadrados, rectángulos, óvalos, etc.).

Tareas ficticias, representadas por una flecha punteada que indica las limitaciones de las cadenas de tareas entre ciertas etapas.

VIDEO DEL METODO!

El algoritmo de Dijkstra te permite calcular la ruta más corta entre un nodo (tú eliges cuál) y todos los demás nodos en el grafo. Encontrarás una descripción del algoritmo al final de esta página, pero ¡vamos a estudiarlo con un ejemplo explicado! Calcularemos la distancia más corta entre el nodo C y los demás nodos del grafo:

Durante la ejecución del algoritmo, iremos marcando cada nodo con su distancia mínima al nodo C (nuestro nodo elegido). Para el nodo C, esta distancia es 0. Para el resto de nodos, como todavía no conocemos esa distancia mínima, empieza siendo infinita (∞):

También tendremos un nodo actual. Inicialmente, el nodo actual será C (nuestro nodo elegido). En la imagen, marcaremos el nodo actual con un punto rojo.

Ahora, revisaremos los vecinos de nuestro nodo actual (A, B y D) en cualquier orden. Empecemos con B. Sumamos la mínima distancia del nodo actual (en este caso, 0) con el peso de la arista que conecta al nodo actual con B (en este caso, 7), y obtenemos 0 + 7 = 7. Comparamos ese valor con la mínima distancia de B (infinito); el valor más pequeño es el que queda como la distancia mínima de B (en este caso, 7 es menos que infinito):

Bien. Ahora revisaremos al vecino A. Sumamos 0 (la distancia mínima de C, nuestro nodo actual) con 1 (el peso de la arista que conecta nuestro nodo actual con A) para obtener 1. Comparamos ese 1 con la mínima distancia de A (infinito) y dejamos el menor valor:

OK. Repetimos el procedimiento para D:

Genial. Hemos revisado todos los vecinos de C. Por ello, lo marcamos como visitado. Representemos a los nodos visitados con una marca de verificación verde:

Ahora debemos seleccionar un nuevo nodo actual. Ese nodo debe ser el nodo no visitado con la menor distancia mínima, es decir, el nodo con el menor número y sin marca de verificación verde. En este caso, ese nodo es A. Vamos a marcarlo con el punto rojo:

Ahora, repetimos el algoritmo. Revisamos los vecinos de nuestro nodo actual, ignorando los visitados. Esto significa que solo revisaremos B.

Para B, sumamos 1 (la distancia mínima de A, nuestro nodo actual) con 3 (el peso de la arista conectando a A con B) para obtener 4. Comparamos ese 4 con la distancia mínima de B (7) y dejamos el menor valor: 4.

Después, marcamos A como visitado y elegimos un nuevo nodo: D, que es el nodo no visitado con la menor distancia mínima.

Repetimos el algoritmo de nuevo. Esta vez, revisamos B y E.

Para B, obtenemos 2 + 5 = 7. Comparamos ese valor con la distancia mínima de B (4) y dejamos el menor valor (4). Para E, obtenemos 2 + 7 = 9, lo comparamos con la distancia mínima de E (infinito) y dejamos el valor menor (9).

Marcamos D como visitado y establecemos nuestro nodo actual en B.

Casi terminamos. Sólo debemos verificar E. 4 + 1 = 5, que es menos que la distancia mínima de E (9), así que dejamos el 5. Marcamos B como visitado y establecemos E como el nodo actual.

E no tiene vecinos no visitados, así que no verificamos nada. Lo marcamos como visitado.

Como no hay nodos no visitados, ¡terminamos! La distancia mínima de cada nodo ahora representa la mínima distancia entre ese nodo y el nodo C (el nodo que elegimos como nodo inicial).

Aquí está una descripción del algoritmo:

Marca el nodo inicial que elegiste con una distancia actual de 0 y el resto con infinito.
Establece el nodo no visitado con la menor distancia actual como el nodo actual A.
Para cada vecino V de tu nodo actual A: suma la distancia actual de A con el peso de la arista que conecta a A con V. Si el resultado es menor que la distancia actual de V, establécelo como la nueva distancia actual de V.
Marca el nodo actual A como visitado.
Si hay nodos no visitados, ve al paso 2.