Enunciado
Un compañero ha redactado el cuadro de prelaciones inmediatas del proyecto que se muestra a continuación. Antes de dibujar el grafo conviene revisarlo: sospechamos que contiene prelaciones redundantes (ya implicadas por otras) y al menos una errata que hace imposible ejecutar el proyecto.
- Compruebe si el cuadro es coherente. Si existe algún ciclo, identifíquelo e indique qué prelación debe eliminarse, suponiendo que la errata consiste en una actividad tardía anotada por error como predecesora de una temprana.
- Identifique las prelaciones redundantes y escriba el cuadro de prelaciones inmediatas mínimo.
- Construya el cuadro de prelaciones expandido (matriz de prelaciones inmediatas) y, a partir de él, indique las actividades iniciales y finales del proyecto.
- Construya el cuadro de ancestros (prelaciones transitivas) y compruebe que las prelaciones redundantes del apartado anterior aparecen en él.
- Dibuje el grafo PERT del proyecto y compruebe sobre él el cuadro de ancestros.
Resolución
Apartado 1
- Compruebe si el cuadro es coherente. Si existe algún ciclo, identifíquelo e indique qué prelación debe eliminarse, suponiendo que la errata consiste en una actividad tardía anotada por error como predecesora de una temprana.
La librería detecta los ciclos al construir la tabla de prelaciones. Un ciclo significa que alguna actividad debería terminar antes de empezar ella misma, lo que hace el proyecto inejecutable.
La tabla de precedencias contiene un ciclo: C → F → G → H → C. Revisa las prelaciones: ninguna actividad puede preceder(se) a sí misma.
En el ciclo participa la prelación «H precede a C». Como H es, por el resto del cuadro, descendiente de C, esa anotación es la errata: eliminándola el cuadro vuelve a ser acíclico.
Apartado 2
- Identifique las prelaciones redundantes y escriba el cuadro de prelaciones inmediatas mínimo.
Una prelación «p precede a a» es redundante cuando p es antecesora de alguna otra predecesora inmediata de a: la relación ya está garantizada por transitividad. La reducción transitiva del grafo de prelaciones conserva exactamente las no redundantes.
F → I es redundante: F ya precede a H, que precede(n) a I
G → J es redundante: G ya precede a I, que precede(n) a J
La librería hace esta misma depuración al construir la tabla de prelaciones, por lo que podemos usarla como comprobación:
| A |
--- |
| B |
--- |
| C |
A,B |
| D |
B |
| E |
D |
| F |
C,D |
| G |
F |
| H |
G |
| I |
E,H |
| J |
I |
Apartado 3
- Construya el cuadro de prelaciones expandido (matriz de prelaciones inmediatas) y, a partir de él, indique las actividades iniciales y finales del proyecto.
En el cuadro expandido cada fila indica las predecesoras inmediatas de una actividad y cada columna sus sucesoras inmediatas. Una fila vacía señala una actividad inicial; una columna vacía, una actividad final.
Actividades iniciales: A, B
Actividades finales: J
Apartado 4
- Construya el cuadro de ancestros (prelaciones transitivas) y compruebe que las prelaciones redundantes del apartado anterior aparecen en él.
F ∈ ancestros(I): True
G ∈ ancestros(J): True
Apartado 5
- Dibuje el grafo PERT del proyecto y compruebe sobre él el cuadro de ancestros.
Las actividades ficticias (discontinuas) del grafo transmiten precisamente las prelaciones que no pueden representarse compartiendo nodos. Siguiendo hacia atrás los arcos desde el final de cada actividad se recorren todos sus ancestros.
