Formula 11

10 actividades, 6 rutas; SVD de R y ranking frente al conjunto crĂ­tico

Enunciado

La matriz de rutas \(R\) describe la estructura del proyecto sin usar duraciones. Su descomposiciĂłn en valores singulares \(R = U\,\Sigma\,V^T\) permite resumir esa estructura: \(u_1\) pondera las rutas y \(v_1\) las actividades, y el cociente \(\sigma_1/\sigma_2\) indica cuĂĄnto domina esa primera direcciĂłn. Considere el proyecto cuyo cuadro se adjunta.

  1. Construya R y calcule su SVD. DĂ© los valores singulares y el cociente σ₁/σ₂.
  1. Ordene las actividades por |v₁| y las rutas por |u₁|. ÂżQuĂ© tienen en comĂșn las actividades mejor situadas?
  1. Con las duraciones, calcule τ exacto y la aproximaciĂłn de rango 1, τ₁ = σ₁ · mĂĄx(u₁) · (v₁ᔀ t) (R ≈ σ₁ u₁ v₁ᔀ). ÂżQuĂ© error relativo comete?
  1. Compare el ranking por |v₁| con el conjunto de actividades crĂ­ticas: Âżes crĂ­tica la actividad mejor clasificada? ÂżQuĂ© fracciĂłn de las k mejor clasificadas son crĂ­ticas (k = nĂșmero de crĂ­ticas)? ÂżPor quĂ© la SVD, que no usa duraciones, puede acertar?
Tabla 1: Cuadro de datos del enunciado
predecessor duration
activity
A --- 1
B --- 5
C --- 3
D A,B 1
E D 6
F E 5
G C,F 2
H G 5
I H 3
J H 8

ResoluciĂłn

Apartado 1

  1. Construya R y calcule su SVD. DĂ© los valores singulares y el cociente σ₁/σ₂.
Tabla 2: Matriz de rutas R
👆 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).

\(\displaystyle \Sigma = \begin{bmatrix} 5.15 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00\\ 0.00 & 2.11 & 0.00 & 0.00 & 0.00 & 0.00\\ 0.00 & 0.00 & 1.73 & 0.00 & 0.00 & 0.00\\ 0.00 & 0.00 & 0.00 & 1.41 & 0.00 & 0.00\\ 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00\\ 0.00 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00\\ \end{bmatrix}\)

σ₁ = 5.153, σ₂ = 2.108; σ₁/σ₂ = 2.44.

Apartado 2

  1. Ordene las actividades por |v₁| y las rutas por |u₁|. ÂżQuĂ© tienen en comĂșn las actividades mejor situadas?
G H F E D I J A B C
v₁ 0.458 0.458 0.365 0.365 0.365 0.229 0.229 0.182 0.182 0.093
rutas en las que aparece 6.000 6.000 4.000 4.000 4.000 3.000 3.000 2.000 2.000 2.000
u₁ actividades nÂș actividades
Route_1 0.47 A - D - E - F - G - H - I 7
Route_2 0.47 A - D - E - F - G - H - J 7
Route_3 0.47 B - D - E - F - G - H - I 7
Route_4 0.47 B - D - E - F - G - H - J 7
Route_5 0.24 C - G - H - I 4
Route_6 0.24 C - G - H - J 4

Las actividades con mayor \(v_1\) son las que aparecen en mĂĄs rutas, sobre todo en las rutas largas y con muchas actividades compartidas (las que a su vez tienen mayor \(u_1\)): \(v_1\) es una medida de centralidad estructural. Las actividades iniciales o finales Ășnicas aparecen en todas las rutas y encabezan la lista.

Apartado 3

  1. Con las duraciones, calcule τ exacto y la aproximaciĂłn de rango 1, τ₁ = σ₁ · mĂĄx(u₁) · (v₁ᔀ t) (R ≈ σ₁ u₁ v₁ᔀ). ÂżQuĂ© error relativo comete?

τ = 32; aproximaciĂłn de rango 1: τ₁ = 5.153 × 0.470 × 11.483 = 27.83; error relativo 13.0 %.

La aproximaciĂłn sustituye cada fila de \(R\) por un mĂșltiplo de \(v_1\): funciona bien cuando las rutas se parecen entre sĂ­ (σ₁ ≫ σ₂) y peor cuando el proyecto tiene varias ramas muy distintas. El τ exacto es siempre la norma infinito de \(R\,t\); la SVD es un resumen.

Apartado 4

  1. Compare el ranking por |v₁| con el conjunto de actividades crĂ­ticas: Âżes crĂ­tica la actividad mejor clasificada? ÂżQuĂ© fracciĂłn de las k mejor clasificadas son crĂ­ticas (k = nĂșmero de crĂ­ticas)? ÂżPor quĂ© la SVD, que no usa duraciones, puede acertar?
ranking por v₁ G H F E D I J A B C
crĂ­tica True True True True True False True False True False

La actividad mejor clasificada, G, es crĂ­tica. Entre las 7 primeras hay 6 crĂ­ticas (precisiĂłn 0.86). La SVD sĂłlo ve la estructura: una actividad por la que pasan muchas rutas tiene muchas ocasiones de estar en la mĂĄs larga, sea cual sea el vector de duraciones; por eso acierta a menudo, pero no siempre, porque la ruta crĂ­tica concreta la fijan las duraciones.