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.
Regla 1: Cada actividad se debe representar sí y sólo sí, por un ramal o arco.
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.
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 crono grama 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.
Para el problema de la ruta corta tenemos varios algoritmos, en esta oportunidad se explicará el algoritmo de dijkstra el cual usa una técnica voraz (greedy). Al final del articulo se encuentran adjuntas las implementaciones en C++ y JAVA.
Descripción
El algoritmo de dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones:
Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS.
Si los pesos de mis aristas son negativos no puedo usar el algoritmo de dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.
Como trabaja
Primero marcamos todos los vértices como no utilizados. El algoritmo parte de un vértice origen que será ingresado, a partir de ese vértices evaluaremos sus adyacentes, como dijkstra usa una técnica greedy – La técnica greedy utiliza el principio de que para que un camino sea óptimo, todos los caminos que contiene también deben ser óptimos- entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se le conoce como relajación (relaxation).
Dijkstra es muy similar a BFS, si recordamos BFS usaba una Cola para el recorrido para el caso de Dijkstra usaremos una Cola de Prioridad o Heap, este Heap debe tener la propiedad de Min-Heap es decir cada vez que extraiga un elemento del Heap me debe devolver el de menor valor, en nuestro caso dicho valor será el peso acumulado en los nodos.
Tanto java como C++ cuentan con una cola de prioridad ambos implementan un Binary Heap aunque con un Fibonacci Heap la complejidad de dijkstra se reduce haciéndolo mas eficiente, pero en un concurso mas vale usar la librería que intentar programar una nueva estructura como un Fibonacci Heap, claro que particularmente uno puede investigar y programarlo para saber como funciona internamente.
Algoritmo en pseudocódigo
Considerar distancia[ i ] como la distancia mas corta del vértice origen ingresado al vértice i.
1 método Dijkstra(Grafo,origen):
2 creamos una cola de prioridad Q
3 agregamos origen a la cola de prioridad Q
4 mientras Q no este vacío:
5 sacamos un elemento de la cola Q llamado u
6 si u ya fue visitado continuo sacando elementos de Q
7 marcamos como visitado u
8 para cada vértice v adyacente a u en el Grafo:
9 sea w el peso entre vértices ( u , v )
10 si v no ah sido visitado:
11 Relajacion( u , v , w )
1 método Relajacion( actual , adyacente , peso ):
2 si distancia[ actual ] + peso < distancia[ adyacente ]
3 distancia[ adyacente ] = distancia[ actual ] + peso
4 agregamos adyacente a la cola de prioridad Q
Ejemplo y Código paso a paso
Tengamos el siguiente grafo, cuyos ID están en color negro encima de cada vértice, los pesos esta en color azul y la distancia inicial en cada vértice es infinito
Algunas consideraciones para entender el código que se explicara junto con el funcionamiento del algoritmo.
1
2
3
#define MAX 10005 //maximo numero de vértices
#define Node pair< int , int > //definimos el nodo como un par( first , second ) donde first es el vertice adyacente y second el peso de la arista
#define INF 1<<30 //definimos un valor grande que represente la distancia infinita inicial, basta conque sea superior al maximo valor del peso en alguna de las aristas
Inicializamos los valores de nuestros arreglos
Donde:
Vértices: ID de los vértices.
Distancia[ u ]: Distancia mas corta desde vértice inicial a vértice con ID = u.
Visitado[ u ]: 0 si el vértice con ID = u no fue visitado y 1 si ya fue visitado.
Previo[ u ]: Almacenara el ID del vértice anterior al vértice con ID = u, me servirá para impresión del camino mas corto.
En cuanto al código los declaramos de la siguiente manera:
1
2
3
4
5
6
vector< Node > ady[ MAX ]; //lista de adyacencia
intdistancia[ MAX ]; //distancia[ u ] distancia de vértice inicial a vértice con ID = u
boolvisitado[ MAX ]; //para vértices visitados
intprevio[ MAX ]; //para la impresion de caminos
priority_queue< Node , vector<Node> , cmp > Q; //priority queue propia del c++, usamos el comparador definido para que el de menor valor este en el tope
intV; //numero de vertices
Y la función de inicialización será simplemente lo siguiente
1
2
3
4
5
6
7
8
//función de inicialización
voidinit(){
for( inti = 0 ; i <= V ; ++i ){
distancia[ i ] = INF; //inicializamos todas las distancias con valor infinito
visitado[ i ] = false; //inicializamos todos los vértices como no visitado
previo[ i ] = -1; //inicializamos el previo del vértice i con -1
}
}
De acuerdo al vértice inicial que elijamos cambiara la distancia inicial, por ejemplo la ruta más corta partiendo del vértice 1 a todos los demás vértices:
El vértice 1 es visitado, la distancia de vértice 1 -> vértice 1 es 0 por estar en el mismo lugar.
1
2
Q.push( Node( inicial , 0 ) ); //Insertamos el vértice inicial en la Cola de Prioridad
distancia[ inicial ] = 0; //Este paso es importante, inicializamos la distancia del inicial como 0
Extraemos el tope de la cola de prioridad
1
2
3
while( !Q.empty() ){ //Mientras cola no este vacia
actual = Q.top().first; //Obtengo de la cola el nodo con menor peso, en un comienzo será el inicial
Q.pop(); //Sacamos el elemento de la cola
Si el tope ya fue visitado entonces no tengo necesidad de evaluarlo, por ello continuaría extrayendo elementos dela cola:
1
if( visitado[ actual ] ) continue; //Si el vértice actual ya fue visitado entonces sigo sacando elementos de la cola
En este caso al ser el tope el inicial no esta visitado por lo tanto marcamos como visitado.
1
visitado[ actual ] = true; //Marco como visitado el vértice actual
Hasta este momento la tabla quedaría de la siguiente manera
Ahora vemos sus adyacentes que no hayan sido visitados. Tendríamos 2 y 4.
1
2
3
4
for( inti = 0 ; i < ady[ actual ].size() ; ++i ){ //reviso sus adyacentes del vertice actual
adyacente = ady[ actual ][ i ].first; //id del vertice adyacente
peso = ady[ actual ][ i ].second; //peso de la arista que une actual con adyacente ( actual , adyacente )
if( !visitado[ adyacente ] ){ //si el vertice adyacente no fue visitado
Evaluamos primero para vértice 2
Vemos que la distancia actual desde el vértice inicial a 2 es ∞, verifiquemos el paso de relajación:
El paso de relajación es posible realizarlo entonces actualizamos la distancia en el vértice 2 y agregando el vértice en la cola de prioridad con nueva distancia quedando:
El paso de relajación se daría en la siguiente parte:
1
2
3
4
5
6
7
for( inti = 0 ; i < ady[ actual ].size() ; ++i ){ //reviso sus adyacentes del vertice actual
adyacente = ady[ actual ][ i ].first; //id del vertice adyacente
peso = ady[ actual ][ i ].second; //peso de la arista que une actual con adyacente ( actual , adyacente )
if( !visitado[ adyacente ] ){ //si el vertice adyacente no fue visitado
relajacion( actual , adyacente , peso ); //realizamos el paso de relajacion
En esta oportunidad hemos encontrado una ruta mas corta partiendo desde el vértice inicial al vértice 2, actualizamos la distancia en el vértice 2 y actualizamos el vértice previo al actual quedando:
En cuanto a la cola de prioridad como tenemos un vértice con menor peso este nuevo vértice ira en el tope de la cola, podemos ver que tenemos 2 veces el mismo vértice pero como usamos una técnica greedy siempre usaremos el valor óptimo:
Continuamos con los Vértices 3 y 5 como tienen valor ∞ si será posible relajarlos por lo que sería similar a los pasos iniciales solo que en los pasos iniciales distancia[ 1 ] era 0 en este caso distancia[ 4 ] es 2, quedando:
Hemos terminado de evaluar al vértice 4, continuamos con el tope de la cola que es vértice 2, el cual marcamos como visitado.
Los adyacentes no visitados del vértice 2 son los vértices 3 y 5. Comencemos con el vértice 3
Ahora vemos que la distancia actual del vértice inicial al vértice 3 es 10, verifiquemos el paso de relajación:
En esta oportunidad hemos encontrado una ruta mas corta partiendo desde el vértice inicial al vértice 3, dicha ruta sería 1 -> 4 -> 2 -> 3 cuyo peso es 6 que es mucho menor que la ruta 1 – > 4 -> 3 cuyo peso es 10, actualizamos la distancia en el vértice 3 quedando:
El siguiente vértice de la cola de prioridad es el vértice 3 y su único adyacente no visitado es el vértice 5.
Vemos que la distancia actual del vértice inicial al vértice 5 es 7, verifiquemos el paso de relajación:
En esta oportunidad se no cumple por lo que no relajamos el vértice 5, por lo que la tabla en cuanto a distancias no sufre modificaciones y no agregamos vértices a la cola:
Ahora tocaría el vértice 2 pero como ya fue visitado seguimos extrayendo elementos de la cola, el siguiente vértice será el 5.
Al ser el ultimo vértice a evaluar no posee adyacentes sin visitar por lo tanto hemos terminado el algoritmo. En el grafico anterior observamos que 2 aristas no fueron usadas para la relajación, las demás si fueron usadas. La tabla final quedaría de la siguiente manera:
De la tabla si deseo saber la distancia mas corta del vértice 1 al vértice 5, solo tengo que acceder al valor del arreglo en su índice respectivo (distancia[ 5 ]).
Shortest Path Tree
En el proceso anterior usábamos el arreglo previo[ u ] para almacenar el ID del vértice previo al vértice con ID = u, ello me sirve para formar el árbol de la ruta mas corta y además me sirve para imprimir caminos de la ruta mas corta.
Impresión del camino encontrado.
Para imprimir el camino mas corto deseado usamos el arreglo previo[ u ], donde u tendrá el ID del vértice destino, o sea si quiero imprimir el camino mas corto desde vértice 1 -> vértice 3 partiré desde previo[ 3 ] hasta el previo[ 1 ]. De manera similar a lo que se explico en el algoritmo BFS, en este caso se realizara de manera recursiva:
1
2
3
4
5
6
//Impresion del camino mas corto desde el vertice inicial y final ingresados
o, todos los caminos que contiene también deben ser óptimos- entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se le conoce como relajación (relaxation).
o, todos los caminos que contiene también deben ser óptimos- entre todos los vértices adyacentes, buscamos el que esté más cerca de nuestro punto origen, lo tomamos como punto intermedio y vemos si podemos llegar más rápido a través de este vértice a los demás. Después escogemos al siguiente más cercano (con las distancias ya actualizadas) y repetimos el proceso. Esto lo hacemos hasta que el vértice no utilizado más cercano sea nuestro destino. Al proceso de actualizar las distancias tomando como punto intermedio al nuevo vértice se le conoce como relajación (relaxation).
Revisamos sus adyacentes no visitados que serian vértices 2, 3 y 5.
Continuamos con los Vértices 3 y 5 como tienen valor ∞ si será posible relajarlos por lo que sería similar a los pasos iniciales solo que en los pasos iniciales distancia[ 1 ] era 0 en este caso distancia[ 4 ] es 2, quedando:
Hemos terminado de evaluar al vértice 4, continuamos con el tope de la cola que es vértice 2, el cual marcamos como visitado.
Los adyacentes no visitados del vértice 2 son los vértices 3 y 5. Comencemos con el vértice 3
El siguiente vértice de la cola de prioridad es el vértice 3 y su único adyacente no visitado es el vértice 5.
Vemos que la distancia actual del vértice inicial al vértice 5 es 7, verifiquemos el paso de relajación:
Al ser el ultimo vértice a evaluar no posee adyacentes sin visitar por lo tanto hemos terminado el algoritmo. En el grafico anterior observamos que 2 aristas no fueron usadas para la relajación, las demás si fueron usadas. La tabla final quedaría de la siguiente manera:
