Enunciado
El fichero pat20.rcp del conjunto de instancias de Patterson (formato RCP: primera línea, número de actividades y de recursos; segunda, disponibilidad de cada recurso; después, una línea por actividad con su duración, sus necesidades de recursos, el número de sucesoras y sus sucesoras) describe un proyecto con actividades ficticias de inicio y fin de duración cero:
- Lea el fichero con
read_rcp (escribiéndolo antes en disco), construya el cuadro de prelaciones y el proyecto. ¿Cuántas actividades reales, ficticias, nodos y rutas tiene?
- Calcule τ = ‖R·t‖∞ y compárelo con la duración obtenida por el cálculo de tiempos (CPM). Indique las actividades críticas.
- Calcule la SVD de R y el cociente σ₁/σ₂. Ordene las actividades por |v₁| y mida la precisión del ranking: fracción de las k primeras (k = número de críticas) que son críticas.
- Compare el tamaño de R con el del grafo. ¿Cómo crece el número de rutas con el tamaño del proyecto y qué implica para proyectos de cientos de actividades?
Resolución
Apartado 1
- Lea el fichero con
read_rcp (escribiéndolo antes en disco), construya el cuadro de prelaciones y el proyecto. ¿Cuántas actividades reales, ficticias, nodos y rutas tiene?
| predecessor |
--- |
A01 |
A01 |
A01 |
A02,A03 |
A02,A04 |
A04 |
A03 |
A05,A07,A08 |
A05,A07,A08 |
A06 |
A06 |
A09,A11,A12 |
A10 |
A11 |
A12 |
A13 |
A15,A16 |
A14 |
A18,A19 |
A17 |
A20,A21 |
| duration |
0 |
3 |
2 |
9 |
7 |
7 |
3 |
2 |
1 |
2 |
4 |
2 |
2 |
3 |
5 |
1 |
1 |
8 |
6 |
4 |
2 |
0 |
22 actividades (incluidas las dos ficticias del formato, de duración 0), 6 ficticias añadidas por el grafo, 20 nodos y 16 rutas.
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):
Apartado 2
- Calcule τ = ‖R·t‖∞ y compárelo con la duración obtenida por el cálculo de tiempos (CPM). Indique las actividades críticas.
τ = ‖R·t‖∞ = 37; CPM = 37; coinciden: True. Actividades críticas: A01, A04, A06, A11, A15, A18, A20, A22.
Apartado 3
- Calcule la SVD de R y el cociente σ₁/σ₂. Ordene las actividades por |v₁| y mida la precisión del ranking: fracción de las k primeras (k = número de críticas) que son críticas.
| v₁ |
0.485 |
0.485 |
0.267 |
0.267 |
0.267 |
0.255 |
0.219 |
0.187 |
0.185 |
0.127 |
0.127 |
0.127 |
0.117 |
0.115 |
0.113 |
0.104 |
0.104 |
0.104 |
0.058 |
0.058 |
0.058 |
0.056 |
| crítica |
True |
True |
False |
False |
False |
True |
True |
False |
True |
False |
True |
False |
False |
True |
False |
False |
False |
False |
False |
True |
False |
False |
σ₁/σ₂ = 1.76. La mejor clasificada, A22, es crítica; precisión en las 8 primeras: 0.50.
En el conjunto de Patterson (110 instancias) la actividad mejor clasificada por \(v_1\) es crítica en el 77 % de los casos, y la identificación falla sobre todo cuando σ₁/σ₂ está cerca de 1 (dos direcciones dominantes). El ranking es informativo, no determinista.
Apartado 4
- Compare el tamaño de R con el del grafo. ¿Cómo crece el número de rutas con el tamaño del proyecto y qué implica para proyectos de cientos de actividades?
El grafo tiene 20 nodos y 28 arcos, pero R tiene 16 filas: el número de rutas crece de forma combinatoria con la anchura del grafo (en las instancias de 51 actividades de Patterson hay hasta varios miles). Por eso la fórmula es útil como herramienta analítica (sensibilidad, estructura, simulación vectorizada), mientras que para calcular τ en proyectos grandes basta el cálculo de tiempos hacia delante, que es lineal en el número de arcos.