Reduccion 06

9 actividades; reducir 3 semanas: Ackoff 16 k€ frente a PL 16 k€

Enunciado

Considere el proyecto cuyo cuadro de prelaciones, duraciones normal y tope (semanas) y coste unitario de reducción CUR (k€/semana) se adjunta. Las actividades con CUR infinito no pueden acelerarse. Se quiere reducir la duración del proyecto en 3 semanas con el mínimo sobrecoste.

1. Calcule la duración normal del proyecto, construya la matriz de caminos \(R\) y la duración de cada ruta.
   

2. Aplique el algoritmo de Ackoff-Sasieni para reducir 3 semanas y obtenga el sobrecoste total.
   

3. Plantee el problema como un programa lineal: variables \(x_i\) = semanas que se acorta la actividad \(i\); minimizar \(\sum_i CUR_i\, x_i\) sujeto a que ninguna ruta supere la duración objetivo, \(R\,(d - x) \le T_{obj}\), y \(0 \le x_i \le d_i - d_i^{tope}\). Resuélvalo con scipy.optimize.linprog.
   

4. Compare las dos soluciones. ¿Puede el algoritmo voraz ser peor que el óptimo? ¿Por qué el programa lineal da aquí soluciones enteras?
   

Tabla 1: Cuadro de datos del enunciado

	predecessor	duration	cap_duration	ucr
activity
A	---	7	4	6.0
B	---	3	3	inf
C	A	4	3	8.0
D	B,C	6	4	5.0
E	A	6	4	3.0
F	D,E	2	1	6.0
G	D	4	3	7.0
H	F	6	6	inf
I	G,H	5	5	inf

Resolución

Apartado 1

1. Calcule la duración normal del proyecto, construya la matriz de caminos \(R\) y la duración de cada ruta.
   

Cálculo de los tiempos tempranos y tardíos de los sucesos y de las holguras totales paso a paso. El primer paso muestra el grafo resuelto; a partir del siguiente se calcula desde el principio (avance con los botones):

paso 0 de 28

Figura 1: Grafo PERT con las duraciones normales

Tabla 2: Matriz de caminos y duración de cada ruta

	actividades	duración = suma	duración
Route_1	A - C - D - F - H - I	A(7) + C(4) + D(6) + F(2) + H(6) + I(5) = 30	30.0
Route_2	A - C - D - G - I	A(7) + C(4) + D(6) + G(4) + I(5) = 26	26.0
Route_3	A - E - F - H - I	A(7) + E(6) + F(2) + H(6) + I(5) = 26	26.0
Route_4	B - D - F - H - I	B(3) + D(6) + F(2) + H(6) + I(5) = 22	22.0
Route_5	B - D - G - I	B(3) + D(6) + G(4) + I(5) = 18	18.0

Apartado 2

2. Aplique el algoritmo de Ackoff-Sasieni para reducir 3 semanas y obtenga el sobrecoste total.
   

Tabla 3: Algoritmo de Ackoff-Sasieni

paso -1 de 3

Algoritmo de Ackoff-Sasieni: tabla completa. Pulse «siguiente» para ver cómo se construye.

Datos: coste unitario de reducción de cada actividad en las rutas que la contienen, duración inicial de cada ruta (columna 0) y periodos que puede reducirse cada actividad (fila 0).

Iteración 0: rutas críticas Route_1 (duración 30); se acorta un periodo la combinación de menor coste: D (coste 5). Resultado: periodos disponibles (fila 1) y duración de las rutas (columna 1); el proyecto dura 29.

Iteración 1: rutas críticas Route_1 (duración 29); se acorta un periodo la combinación de menor coste: D (coste 5). Resultado: periodos disponibles (fila 2) y duración de las rutas (columna 2); el proyecto dura 28.

Iteración 2: rutas críticas Route_1 (duración 28); se acorta un periodo la combinación de menor coste: A (coste 6). Resultado: periodos disponibles (fila 3) y duración de las rutas (columna 3); el proyecto dura 27. Se alcanzó el número de reducciones pedido.

Tabla 4: Opciones consideradas en cada paso

	duración	rutas críticas	opciones (coste)	elegida	coste del paso
paso
1	30	Route_1	D (5); A (6); F (6); C (8)	D	5.0
2	29	Route_1	D (5); A (6); F (6); C (8)	D	5.0
3	28	Route_1	A (6); F (6); C (8)	A	6.0

Ackoff-Sasieni acorta A (1), D (2) con un sobrecoste de 16 k€; duración 27.

Apartado 3

3. Plantee el problema como un programa lineal: variables \(x_i\) = semanas que se acorta la actividad \(i\); minimizar \(\sum_i CUR_i\, x_i\) sujeto a que ninguna ruta supere la duración objetivo, \(R\,(d - x) \le T_{obj}\), y \(0 \le x_i \le d_i - d_i^{tope}\). Resuélvalo con scipy.optimize.linprog.
   

Cada fila de \(R\) es una ruta; \(R\,d\) son las duraciones de las rutas y \(R\,x\) lo que se acorta cada una. La restricción \(R\,(d - x) \le T_{obj}\) se escribe como \(-R\,x \le T_{obj} - R\,d\) para linprog (que exige la forma \(A x \le b\)).

	A	B	C	D	E	F	G	H	I
x (Ackoff)	1.0	0.0	0.0	2.0	0.0	0.0	0.0	0.0	0.0
x (PL)	0.0	0.0	0.0	2.0	0.0	1.0	0.0	0.0	0.0
CUR	6.0	inf	8.0	5.0	3.0	6.0	7.0	inf	inf

La programación lineal acorta D (2), F (1) con sobrecoste 16 k€; todas las rutas quedan en como mucho 27 semanas (objetivo 27).

Tabla 5: Duración de cada ruta con la solución del programa lineal

	actividades	duración = suma	duración
Route_1	A - C - D - F - H - I	A(7.0) + C(4.0) + D(4.0) + F(1.0) + H(6.0) + I...	27.0
Route_2	A - C - D - G - I	A(7.0) + C(4.0) + D(4.0) + G(4.0) + I(5.0) = 24.0	24.0
Route_3	A - E - F - H - I	A(7.0) + E(6.0) + F(1.0) + H(6.0) + I(5.0) = 25.0	25.0
Route_4	B - D - F - H - I	B(3.0) + D(4.0) + F(1.0) + H(6.0) + I(5.0) = 19.0	19.0
Route_5	B - D - G - I	B(3.0) + D(4.0) + G(4.0) + I(5.0) = 16.0	16.0

Apartado 4

4. Compare las dos soluciones. ¿Puede el algoritmo voraz ser peor que el óptimo? ¿Por qué el programa lineal da aquí soluciones enteras?
   

Aquí las dos soluciones cuestan lo mismo: el algoritmo voraz ha acertado. No siempre es así: decide semana a semana y no revisa decisiones anteriores, por lo que puede ser más caro que el óptimo cuando una actividad acortada pronto deja de ser útil al cambiar las rutas críticas. Aquí el PL ha dado una solución entera: con datos enteros suele ocurrir, pero no está garantizado (la matriz de caminos no es en general totalmente unimodular); si hiciera falta, habría que exigir x entera con un programa entero, que linprog no resuelve. En todo caso el óptimo del PL es una cota inferior del coste de cualquier reducción entera.