Enunciado
La matriz de incidencia \(H\) del grafo PERT tiene una fila por arco (actividades y ficticias) y una columna por nodo, con −1 en el nodo origen del arco y +1 en el destino. Cada ruta es una cadena de arcos del nodo inicial al final. Considere el proyecto cuyo cuadro se adjunta.
- Dibuje el grafo PERT numerado y escriba la matriz de incidencia H (incluyendo las ficticias).
- Construya la matriz de rutas R con las ficticias (duración 0) y compruebe que R·H = 0 salvo en las columnas del nodo inicial y del final. ¿Por qué?
- Elija un vector y con un valor entero por nodo interior (0 en el inicial y el final) y defina la perturbación δ = H·y de las duraciones de los arcos. Compruebe que todas las rutas cambian de duración en la misma cantidad y que τ no cambia. Interprételo: ¿qué se ha hecho con los «tiempos de los nodos»?
- ¿Qué dimensión tiene el espacio de perturbaciones que dejan invariantes todas las duraciones de ruta? ¿Qué significa para la identificación de duraciones a partir de observaciones de rutas?
Resolución
Apartado 1
- Dibuje el grafo PERT numerado y escriba la matriz de incidencia H (incluyendo las ficticias).
Apartado 2
- Construya la matriz de rutas R con las ficticias (duración 0) y compruebe que R·H = 0 salvo en las columnas del nodo inicial y del final. ¿Por qué?
| Route_1 |
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
| Route_2 |
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
| Route_3 |
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
| Route_4 |
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
R·H es cero en las columnas interiores: True; en la columna del nodo inicial vale -1 y en la del final 1 para todas las rutas.
Una ruta entra y sale de cada nodo interior exactamente una vez, así que la suma de sus entradas de incidencia es +1 − 1 = 0; sólo sale del inicial (−1) y sólo entra en el final (+1).
Apartado 3
- Elija un vector y con un valor entero por nodo interior (0 en el inicial y el final) y defina la perturbación δ = H·y de las duraciones de los arcos. Compruebe que todas las rutas cambian de duración en la misma cantidad y que τ no cambia. Interprételo: ¿qué se ha hecho con los «tiempos de los nodos»?
| t |
0 |
0 |
8 |
3 |
6 |
3 |
7 |
8 |
4 |
| δ = H·y |
-3 |
-2 |
1 |
-1 |
2 |
0 |
0 |
-3 |
1 |
| t + δ |
-3 |
-2 |
9 |
2 |
8 |
3 |
7 |
5 |
5 |
| Route_1 |
22 |
22 |
0 |
| Route_2 |
17 |
17 |
0 |
| Route_3 |
20 |
20 |
0 |
| Route_4 |
18 |
18 |
0 |
τ = 22 antes y 22 después: las duraciones de todas las rutas cambian en 0 (= y_final − y_inicial = 0), así que τ es invariante.
δ = H·y añade a cada arco la diferencia de «potencial» entre su destino y su origen. Es lo mismo que mover el reloj de cada nodo: si al nodo j se le suma y_j a su tiempo, los arcos que llegan a j parecen y_j más largos y los que salen y_j más cortos, y a lo largo de cualquier ruta cerrada entre inicio y final todo se cancela. (Algunas duraciones perturbadas pueden salir negativas: es un ejercicio algebraico, no un calendario.)
Apartado 4
- ¿Qué dimensión tiene el espacio de perturbaciones que dejan invariantes todas las duraciones de ruta? ¿Qué significa para la identificación de duraciones a partir de observaciones de rutas?
Las columnas interiores de H generan un espacio de dimensión 5 (número de nodos interiores, 5) contenido en el núcleo de R. Hay por tanto 5 direcciones independientes en las que pueden moverse las duraciones de los 9 arcos sin que ninguna ruta cambie. Consecuencia: observando sólo duraciones de rutas no pueden identificarse las duraciones de los arcos; sólo se identifican módulo esas 5 direcciones.
