Lección 02 — El grafo PERT y las actividades ficticias

Actividades como arcos, sucesos como nodos, ficticias, numeración y rutas

Qué se aprende

A representar un cuadro de prelaciones como grafo PERT (actividades en los arcos), a entender por qué a veces hacen falta actividades ficticias y cuántas son imprescindibles, a numerar los nodos y a enumerar las rutas del grafo, que es la base de la matriz de caminos.

Conceptos

Representación AoA (activity on arrow). Cada actividad es un arco orientado \(i \to j\) entre dos sucesos (nodos): el suceso \(i\) es «todas las predecesoras de la actividad han terminado» y el \(j\) es «la actividad ha terminado». El grafo tiene un único nodo inicial (del que salen las actividades iniciales) y un único nodo final (al que llegan las finales).

Regla de construcción. Las actividades que tienen exactamente las mismas predecesoras pueden salir del mismo nodo; una actividad llega al nodo del que salen sus sucesoras. El problema aparece cuando dos actividades comparten parte de sus predecesoras: en el ejemplo guía, C depende de A y D depende de A y B. Si C y D salieran del mismo nodo, C dependería también de B (prelación inventada); si salieran de nodos distintos, A tendría que llegar a dos nodos, lo que un arco no puede hacer.

Actividad ficticia. Un arco de duración cero (se dibuja discontinuo, en la librería se nombra @i→j) que transporta una prelación de un nodo a otro sin consumir tiempo. Resuelve dos situaciones:

  1. Prelaciones parcialmente compartidas: A llega a un nodo del que sale C; una ficticia lleva «A terminada» hasta el nodo del que sale D, al que también llega B.
  2. Arcos paralelos: dos actividades con las mismas predecesoras y las mismas sucesoras irían entre los mismos dos nodos, y un grafo no admite dos arcos iguales (se identificarían por sus extremos); una de ellas se desvía por una ficticia.

Mínimo número de ficticias. Un grafo PERT puede dibujarse con muchas ficticias de más. Construirlo con el mínimo es un problema combinatorio difícil en general; en los tamaños de clase se consigue con la regla práctica siguiente, que es la que implementa la librería (create_project(simplify=True)): primero se da a cada actividad su propio nodo de salida y se conectan con ficticias todas las prelaciones; después se funden los nodos que pueden fundirse (dos nodos de salida se funden si los conjuntos de predecesoras coinciden) y se eliminan las ficticias que se vuelven redundantes (una ficticia \(i \to j\) sobra si todo lo que llega a \(i\) ya llega a \(j\) por otro camino de ficticias, o si \(i\) tiene una única salida y \(j\) una única entrada, en cuyo caso los nodos se funden).

Numeración de los nodos. Se numeran de modo que todo arco vaya de un número menor a uno mayor. Siempre es posible (el grafo no tiene ciclos) y en general no es única; con esa numeración la matriz de Zaderenko es triangular superior.

Rutas. Una ruta es un camino del nodo inicial al final. Cada ruta pasa por un conjunto de actividades reales (las ficticias se ignoran al leerla), y la duración de la ruta es la suma de las duraciones de esas actividades. El proyecto dura lo que la ruta más larga: la ruta crítica.

Ejemplo guía

Con el cuadro de la lección 01 (A, B iniciales; C ← A; D ← A, B; E ← B; F ← C, D; G ← E) el PERT mínimo tiene 7 nodos y 2 ficticias:

Arco Actividad
1 → 3 A
1 → 2 B
3 → 6 C
3 → 5 @ (ficticia: lleva A al nodo de D)
2 → 5 @ (ficticia: lleva B al nodo de D)
5 → 6 D
2 → 4 E
6 → 7 F
4 → 7 G

D necesita las dos ficticias porque comparte A con C (que sale del nodo 3) y B con E (que sale del nodo 2), y no puede salir ni del 3 ni del 2 sin heredar una prelación de más.

El grafo PERT del proyecto guía dibujado por la librería (ficticias discontinuas)

Rutas (sin contar ficticias como actividades): A–C–F (10), A–D–F (7), B–D–F (6), B–E–G (6). Ruta crítica: A–C–F, duración 10.

Cómo dibujarlo a mano

  1. Listar las actividades iniciales: salen todas del nodo 1.
  2. Agrupar las actividades por su conjunto de predecesoras. Cada grupo con el mismo conjunto sale de un mismo nodo.
  3. Para cada grupo cuyo conjunto de predecesoras sea exactamente «las actividades que llegan a un nodo ya dibujado», usar ese nodo. Si no, crear un nodo nuevo y traer las predecesoras que falten con ficticias.
  4. Las actividades finales llegan todas al nodo final.
  5. Comprobar: (a) ningún par de actividades entre los mismos dos nodos; (b) no hay dos ficticias que transporten la misma prelación; (c) cada ficticia es necesaria (quitarla cambiaría alguna prelación).
  6. Numerar los nodos con \(i < j\) en cada arco.

Con pmULE

proyecto = prelaciones.create_project()             # mínimo de ficticias
proyecto.dummies                                    # ['@2→5', '@3→5']
proyecto.pert(durations=False)                      # dibujo (graphviz)
proyecto.paths(dummies=False)                       # rutas como listas de actividades
bruto = prelaciones.create_project(simplify=False)  # versión sistemática, sin fundir nodos

Preguntas de comprobación

  • ¿Puede un proyecto sin prelaciones compartidas necesitar ficticias? Sí: dos actividades con las mismas predecesoras y las mismas sucesoras (arcos paralelos).
  • ¿Cambia la duración del proyecto si se dibujan ficticias de más? No: duran cero. Cambian el grafo, los nodos y la matriz de Zaderenko, no el calendario.
  • ¿Por qué no hay ficticias en el grafo Roy? Porque allí las actividades son nodos y cada prelación es un arco propio (lección 03).

Qué practica cada variante

minimo-ficticias: dibujar con el mínimo, justificar cada ficticia, enumerar rutas y ancestros. paralelas: dos actividades idénticas en predecesoras y sucesoras. mas-ficticias: proyecto mayor. compartir-nodos: qué parejas de actividades pueden compartir nodo inicial, final o ambos. ficticias-sobrantes: el grafo sistemático frente al mínimo; cuáles sobran y por qué.