Caminos 07

8 actividades, 5 rutas, reconstrucción desde las rutas y SVD

Enunciado

De un proyecto sólo se conocen sus rutas entre el nodo inicial y el final y las duraciones de sus actividades (en días).

  1. Construya la matriz de caminos del proyecto.
  1. Calcule con ella la duración del proyecto e identifique la ruta crítica.
  1. Reconstruya el cuadro de prelaciones inmediatas y dibuje los grafos PERT y Roy. Compruebe que sus rutas son las del enunciado.
  1. Calcule la sensibilidad de la duración del proyecto a cada actividad: ¿en cuánto aumenta la duración si una actividad dura un día más?
  1. Calcule la descomposición en valores singulares de la matriz de caminos y ordene rutas y actividades según el primer vector singular. Compare con la ruta crítica.
Tabla 1: Rutas del proyecto
actividades
Route_1 A - C - E - H
Route_2 A - D - H
Route_3 B - C - E - H
Route_4 B - F - G
Route_5 B - F - H
Tabla 2: Duración de las actividades
duration
activity
A 8
B 2
C 4
D 7
E 1
F 4
G 2
H 4

Resolución

Apartado 1

  1. Construya la matriz de caminos del proyecto.

La matriz de caminos tiene un 1 en la fila de una ruta y la columna de una actividad cuando la actividad pertenece a la ruta.

matriz de enlace

Apartado 2

  1. Calcule con ella la duración del proyecto e identifique la ruta crítica.
A B C D E F G H
Route_1 1 0 1 0 1 0 0 1
Route_2 1 0 0 1 0 0 0 1
Route_3 0 1 1 0 1 0 0 1
Route_4 0 1 0 0 0 1 1 0
Route_5 0 1 0 0 0 1 0 1
×
duration
A 8
B 2
C 4
D 7
E 1
F 4
G 2
H 4
=
duration
17
19
11
8
10

👆 Interactivo: pasa el ratón (o toca) una fila de la matriz de rutas: se recuadran los valores que se suman y el resultado.

Tabla 3: Duración de cada ruta, sumando sus actividades
actividades duración = suma duración
Route_1 A - C - E - H A(8) + C(4) + E(1) + H(4) = 17 17.0
Route_2 A - D - H A(8) + D(7) + H(4) = 19 19.0
Route_3 B - C - E - H B(2) + C(4) + E(1) + H(4) = 11 11.0
Route_4 B - F - G B(2) + F(4) + G(2) = 8 8.0
Route_5 B - F - H B(2) + F(4) + H(4) = 10 10.0

La duración del proyecto es 19 días, la de la ruta más larga, Route_2: A - D - H.

Apartado 3

  1. Reconstruya el cuadro de prelaciones inmediatas y dibuje los grafos PERT y Roy. Compruebe que sus rutas son las del enunciado.

Las predecesoras inmediatas de una actividad son las que la preceden inmediatamente en alguna ruta; las rutas son todas las secuencias posibles, así que el conjunto de parejas consecutivas de todas las rutas es exactamente el cuadro de prelaciones inmediatas. Las actividades que abren alguna ruta son iniciales.

predecessor duration
activity
A --- 8
B --- 2
C A,B 4
D A 7
E C 1
F B 4
G F 2
H D,E,F 4

Cálculo de los tiempos tempranos y tardíos de los sucesos y de las holguras totales paso a paso. El primer paso muestra el grafo resuelto; a partir del siguiente se calcula desde el principio (avance con los botones):

paso 0 de 29
Figura 1: Grafo PERT reconstruido, con tiempos y ruta crítica

Cálculo de los tiempos mínimos y máximos de los nodos del grafo Roy paso a paso. El primer paso muestra el grafo resuelto; a partir del siguiente se calcula desde el principio (avance con los botones):

paso 0 de 22
Figura 2: Grafo Roy reconstruido 
Las rutas del grafo coinciden con las del enunciado: True

Apartado 4

  1. Calcule la sensibilidad de la duración del proyecto a cada actividad: ¿en cuánto aumenta la duración si una actividad dura un día más?

La duración del proyecto es \(\tau = \max_r (P\,d)_r\). Si una actividad crítica dura un día más, la ruta crítica se alarga un día y con ella el proyecto: su sensibilidad es 1. Si una actividad no crítica dura un día más, la ruta más larga no cambia mientras no se agote la holgura: sensibilidad 0. Al acortar una actividad crítica el proyecto sólo se acorta hasta que otra ruta pasa a ser la más larga.

activity A B C D E F G H
sensibilidad (+1 día) 1.0 0.0 0.0 1.0 0.0 0.0 0.0 1.0
A B C D E F G H
+1 día 1 0 0 1 0 0 0 1
-1 día -1 0 0 -1 0 0 0 -1

Al acortar una actividad crítica el proyecto se reduce un día sólo si ninguna otra ruta alcanza la duración máxima; la segunda ruta más larga está a 2 día(s) de la crítica, así que esa es la reducción máxima que puede conseguirse acortando una única actividad crítica que no pertenezca también a esa segunda ruta.

Apartado 5

  1. Calcule la descomposición en valores singulares de la matriz de caminos y ordene rutas y actividades según el primer vector singular. Compare con la ruta crítica.

La descomposición en valores singulares \(P = U\,S\,V^T\) ordena la información de la matriz de caminos por importancia. El primer vector singular por la izquierda, \(u_1\), pondera las rutas, y el primero por la derecha, \(v_1\), las actividades: las actividades que aparecen en muchas rutas y las rutas que contienen muchas actividades compartidas reciben más peso. Es una ordenación estructural, que no usa las duraciones, y por eso no tiene por qué coincidir con la ruta crítica.

\(\displaystyle S = \begin{bmatrix} 3.03\\ 2.09\\ 1.50\\ 0.93\\ 0.60\\ \end{bmatrix}\)

Tabla 4: Rutas y actividades ordenadas por su peso en el primer vector singular
  H B C E A F D G Importancia
Route_3 0.252199 0.163509 0.152171 0.152171 0.000000 0.000000 0.000000 0.000000 0.277790
Route_1 0.252199 0.000000 0.152171 0.152171 0.119101 0.000000 0.000000 0.000000 0.260658
Route_5 0.252199 0.163509 0.000000 0.000000 0.000000 0.085003 0.000000 0.000000 0.193171
Route_2 0.252199 0.000000 0.000000 0.000000 0.119101 0.000000 0.045436 0.000000 0.160774
Route_4 0.000000 0.163509 0.000000 0.000000 0.000000 0.085003 0.000000 0.030411 0.107606

La ruta dominante según la SVD es Route_3 y la ruta crítica es Route_2. La actividad de mayor peso es H, que aparece en 4 de las 5 rutas.