PERT 01

8 actividades, 2 ficticias, 6 rutas

Enunciado

Considere el proyecto definido por el siguiente cuadro de prelaciones inmediatas.

  1. Dibuje el grafo PERT del proyecto utilizando el mínimo número de actividades ficticias y numere sus nodos de modo que todo arco vaya de un número menor a uno mayor.
  1. Para cada actividad ficticia, explique qué prelación transmite y por qué no puede evitarse.
  1. Las actividades C y D tienen las mismas predecesoras. ¿Pueden compartir nodo inicial y nodo final? Razone la respuesta.
  1. Enumere todas las rutas desde el nodo inicial al final e indique cuántas hay.
  1. Construya el cuadro de ancestros y compruebe que el grafo lo respeta.
Tabla 1: Cuadro de prelaciones del enunciado
predecessor
activity
A ---
B ---
C A,B
D A,B
E C
F D,E
G D
H F,G

El proyecto corresponde a la apertura de una clínica veterinaria; las actividades son las siguientes (las duraciones del cuadro están en semanas).

Tabla 2: Descripción de las actividades
Descripción
A Estudio de mercado y local
B Proyecto de reforma y licencia
C Obra de reforma
D Instalación de quirófano y radiología
E Mobiliario y equipamiento clínico
F Software de gestión
G Selección de personal
H Acuerdos con proveedores

Resolución

Apartado 1

  1. Dibuje el grafo PERT del proyecto utilizando el mínimo número de actividades ficticias y numere sus nodos de modo que todo arco vaya de un número menor a uno mayor.

Partimos del cuadro de prelaciones expandido: las filas dan las predecesoras inmediatas y las columnas las sucesoras. Dos actividades pueden compartir nodo final si tienen exactamente las mismas sucesoras, y nodo inicial si tienen las mismas predecesoras; en los demás casos hacen falta ficticias.

Tabla 3: Cuadro de prelaciones expandido
matriz de enlace
Figura 1: Grafo PERT con numeración de nodos; las ficticias se dibujan discontinuas 
El grafo tiene 8 nodos, 8 actividades reales y 2 ficticias: @2→3, @4→6

Apartado 2

  1. Para cada actividad ficticia, explique qué prelación transmite y por qué no puede evitarse.

Cada ficticia une el nodo final de unas actividades con el nodo inicial de otras. La prelación que transmite es «todas las que entran en su nodo origen preceden a todas las que salen de su nodo destino».

entran en el nodo origen salen del nodo destino
ficticia
@2→3 A C, D
@4→6 D F

Si en lugar de la ficticia se fusionaran ambos nodos, las actividades que salen del nodo destino pasarían a tener como predecesoras a todas las que entran en el origen y a las que entran en el destino, que no es lo que dice el cuadro; y si se eliminara sin fusionar, se perdería la prelación. Por eso ninguna puede evitarse.

Apartado 3

  1. Las actividades C y D tienen las mismas predecesoras. ¿Pueden compartir nodo inicial y nodo final? Razone la respuesta.

C y D tienen las mismas predecesoras, así que pueden compartir el nodo inicial. Pero dos arcos no pueden unir el mismo par de nodos (el grafo no distinguiría una actividad de la otra), de modo que sólo compartirán también el nodo final si además tienen las mismas sucesoras, y aun en ese caso una de las dos necesita una ficticia.

Sucesoras de C: ['E']
Sucesoras de D: ['F', 'G']

Apartado 4

  1. Enumere todas las rutas desde el nodo inicial al final e indique cuántas hay.
Tabla 4: Rutas del grafo (sin ficticias)
actividades
Route_1 A - C - E - F - H
Route_2 A - D - F - H
Route_3 A - D - G - H
Route_4 B - C - E - F - H
Route_5 B - D - F - H
Route_6 B - D - G - H 
El grafo tiene 6 rutas entre el nodo inicial y el final.

Apartado 5

  1. Construya el cuadro de ancestros y compruebe que el grafo lo respeta.
Tabla 5: Cuadro de ancestros
predecessors
A ----
B ----
C A, B
D A, B
E A, B, C
F A, B, C, D, E
G A, B, D
H A, B, C, D, E, F, G

Para cada actividad, el conjunto de actividades que aparecen antes que ella en alguna ruta debe coincidir con su fila del cuadro de ancestros:

coincide
A True
B True
C True
D True
E True
F True
G True
H True