Formula 03

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 --- 5
B --- 6
C A,B 3
D C 7
E A,B 3
F C 8
G D,E 7
H G 3
I F,H 4
J I 7

El proyecto corresponde a la organizaciĂłn de un congreso cientĂ­fico; las actividades son las siguientes (las duraciones del cuadro estĂĄn en semanas).

Tabla 2: Descripción de las actividades
DescripciĂłn
A DefiniciĂłn del programa y fechas
B Reserva de la sede
C Convocatoria de comunicaciones
D PĂĄgina web e inscripciones
E ContrataciĂłn de ponentes invitados
F RevisiĂłn de los trabajos recibidos
G ElaboraciĂłn del programa definitivo
H ContrataciĂłn de catering y viajes
I EdiciĂłn del libro de actas
J PreparaciĂłn de salas y audiovisuales

ResoluciĂłn

Apartado 1

  1. Construya R y calcule su SVD. DĂ© los valores singulares y el cociente σ₁/σ₂.
Tabla 3: 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.05 & 0.00 & 0.00 & 0.00 & 0.00 & 0.00\\ 0.00 & 2.22 & 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.61 & 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.050, σ₂ = 2.218; σ₁/σ₂ = 2.28.

Apartado 2

  1. Ordene las actividades por |v₁| y las rutas por |u₁|. ÂżQuĂ© tienen en comĂșn las actividades mejor situadas?
J I G H C A B D E F
v₁ 0.48 0.48 0.35 0.35 0.318 0.24 0.24 0.189 0.162 0.129
rutas en las que aparece 6.00 6.00 4.00 4.00 4.000 3.00 3.00 2.000 2.000 2.000
u₁ actividades nÂș actividades
Route_1 0.477 A - C - D - G - H - I - J 7
Route_4 0.477 B - C - D - G - H - I - J 7
Route_3 0.408 A - E - G - H - I - J 6
Route_6 0.408 B - E - G - H - I - J 6
Route_5 0.326 B - C - F - I - J 5
Route_2 0.326 A - C - F - I - J 5

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?

τ = 37; aproximaciĂłn de rango 1: τ₁ = 5.050 × 0.477 × 15.210 = 36.60; error relativo 1.1 %.

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₁ J I G H C A B D E F
crĂ­tica True True True True True False True True False False

La actividad mejor clasificada, J, 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.