Enunciado
Considere el proyecto cuyo cuadro de prelaciones y duraciones (días) se adjunta. Durante la revisión del plan se descubre que la actividad F no puede empezar hasta que termine E: hay que añadir esa prelación.
- Construya la matriz de rutas \(R\) del proyecto original y calcule \(\tau = \lVert R\,t \rVert_\infty\).
- Razone, sin recalcular todo, qué le ocurre a \(R\) al añadir la prelación E → F: ¿qué rutas dejan de serlo (quedan «absorbidas» por otras más largas) y qué rutas nuevas aparecen?
- Construya la matriz de rutas del proyecto modificado y compruebe su razonamiento. Calcule el nuevo τ y la nueva ruta crítica.
- ¿Puede añadir una prelación reducir τ? ¿Y aumentar el número de rutas? Justifíquelo con \(R\).
Resolución
Apartado 1
- Construya la matriz de rutas \(R\) del proyecto original y calcule \(\tau = \lVert R\,t \rVert_\infty\).
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):
τ = ‖R·t‖∞ = 29 (ruta Route_2: A - C - F - G).
Apartado 2
- Razone, sin recalcular todo, qué le ocurre a \(R\) al añadir la prelación E → F: ¿qué rutas dejan de serlo (quedan «absorbidas» por otras más largas) y qué rutas nuevas aparecen?
Añadir E → F crea un arco nuevo. Aparecen rutas nuevas: las que llegan hasta E por cualquier camino (prefijos), saltan a F y continúan desde F hasta el final (sufijos): hasta «número de prefijos × número de sufijos» filas nuevas. Las rutas antiguas siguen existiendo, salvo una excepción: si alguna prelación antigua q → F se vuelve redundante (porque q es antecesora de E), el cuadro depurado la elimina y las rutas que usaban ese salto directo desaparecen, absorbidas por rutas nuevas que pasan por q, …, E, F y son más largas. Y si E era final (o F inicial), las rutas que terminaban en E (o empezaban en F) dejan de serlo: se prolongan a través del nuevo arco. En la práctica \(R\) gana filas y puede perder alguna.
Rutas por E: Route_1, Route_3; rutas por F: Route_2, Route_4, Route_5. Se esperan hasta 2 × 3 = 6 combinaciones prefijo-sufijo (menos las repetidas).
Apartado 3
- Construya la matriz de rutas del proyecto modificado y compruebe su razonamiento. Calcule el nuevo τ y la nueva ruta crítica.
| Route_1 |
A - C - E - F - G |
32 |
| Route_2 |
B - C - E - F - G |
27 |
| Route_3 |
B - D - F - G |
20 |
Rutas que desaparecen: A - C - E - G; A - C - F - G; B - C - E - G; B - C - F - G.
Rutas nuevas: A - C - E - F - G; B - C - E - F - G.
Nuevo τ = 32 (antes 29); ruta crítica Route_1: A - C - E - F - G.
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):
Apartado 4
- ¿Puede añadir una prelación reducir τ? ¿Y aumentar el número de rutas? Justifíquelo con \(R\).
Añadir una prelación nunca reduce τ: cada ruta nueva contiene como subconjunto de actividades a alguna combinación que ya restringía el proyecto, y las rutas que desaparecen son las contenidas en alguna ruta nueva (su suma de duraciones es menor o igual). Formalmente, para cada fila antigua \(r\) existe una fila nueva \(r'\) con \(R'_{r'} \ge R_r\) componente a componente, luego \(\max R' t \ge \max R t\). El número de rutas sí puede crecer (producto de prefijos por sufijos) o decrecer (si muchas quedan absorbidas): \(R\) no es monótona en tamaño, sólo en lo que restringe.