Formula 01

7 actividades, 4 rutas; τ como norma infinito

Enunciado

La duración de un proyecto puede escribirse como una fórmula cerrada: si \(R\) es la matriz de rutas (una fila por cada ruta del nodo inicial al final, una columna por actividad, con un 1 donde la actividad pertenece a la ruta) y \(t\) el vector de duraciones, entonces

\[\tau = \lVert R\,t \rVert_\infty = \max_r \sum_i R_{ri}\,t_i .\]

Considere el proyecto cuyo cuadro de prelaciones y duraciones (días) se adjunta.

  1. Dibuje el grafo PERT, enumere sus rutas y construya la matriz de rutas R. ¿Qué dimensiones tiene?
  1. Calcule el vector R·t y su norma infinito. Compruebe que coincide con el tiempo más temprano del último nodo obtenido por el método de Zaderenko.
  1. ¿Por qué la norma infinito y no otra? ¿Qué daría ‖R·t‖₁? ¿Y qué significaría el mínimo de R·t?
  1. Escriba τ en función de t_E (la duración de E) dejando fijas las demás, y dibuje esa función. ¿Es lineal? ¿Dónde cambia de pendiente?
Tabla 1: Cuadro de datos del enunciado
predecessor duration
activity
A --- 8
B --- 6
C A,B 2
D C 5
E C 2
F E 4
G D,F 4

Resolución

Apartado 1

  1. Dibuje el grafo PERT, enumere sus rutas y construya la matriz de rutas R. ¿Qué dimensiones tiene?
Figura 1: Grafo PERT
Tabla 2: Matriz de rutas R
actividades
Route_1 A - C - D - G
Route_2 A - C - E - F - G
Route_3 B - C - D - G
Route_4 B - C - E - F - G
👆 Interactivo: haz clic en una fila de la matriz para resaltar en el grafo las actividades y los nodos de esa ruta (otro clic la deselecciona).

R tiene 4 filas (rutas) y 7 columnas (actividades).

Apartado 2

  1. Calcule el vector R·t y su norma infinito. Compruebe que coincide con el tiempo más temprano del último nodo obtenido por el método de Zaderenko.
A B C D E F G
Route_1 1 0 1 1 0 0 1
Route_2 1 0 1 0 1 1 1
Route_3 0 1 1 1 0 0 1
Route_4 0 1 1 0 1 1 1
×
duration
A 8
B 6
C 2
D 5
E 2
F 4
G 4
=
duration
19
20
17
18

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

τ = 20

Algoritmo de Zaderenko paso a paso, con el grafo PERT arriba y la matriz debajo. El primer paso muestra el resultado final; a partir del siguiente se construye desde el principio (avance con los botones):

Tabla 3: Matriz de Zaderenko
paso 0 de 16

‖R·t‖∞ = 20; tiempo más temprano del último nodo = 20; la librería (proyecto.tau) da 20. Las tres coinciden: el cálculo de tiempos hacia delante es una forma de calcular el máximo sin enumerar las rutas.

Apartado 3

  1. ¿Por qué la norma infinito y no otra? ¿Qué daría ‖R·t‖₁? ¿Y qué significaría el mínimo de R·t?

‖R·t‖₁ = 74 sumaría las duraciones de todas las rutas, contando varias veces cada actividad compartida: no tiene sentido como plazo. El mínimo de R·t, 17, es la ruta más corta: el tiempo que como mínimo ocupa cualquier cadena del proyecto, pero el proyecto no termina hasta que acaba la última ruta. El plazo es el máximo porque todas las rutas deben completarse; de ahí la norma infinito.

Apartado 4

  1. Escriba τ en función de t_E (la duración de E) dejando fijas las demás, y dibuje esa función. ¿Es lineal? ¿Dónde cambia de pendiente?

τ es el máximo de varias funciones lineales de t_E (una por ruta): las rutas que no contienen a E son constantes y las que la contienen tienen pendiente 1. El resultado es lineal a trozos y convexo: pendiente 0 mientras otra ruta manda y pendiente 1 a partir de t_E = 1 (cuando la ruta más larga que pasa por E alcanza a la crítica). La duración actual de E es 2: su sensibilidad es 1.