Reduccion 13

9 actividades; reducir 3 semanas: Ackoff 3 k€ frente a PL 3 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	---	3	1	5.0
B	---	2	2	inf
C	A,B	7	6	4.0
D	C	7	7	inf
E	B	4	3	1.0
F	C,E	8	8	inf
G	D,E	5	3	9.0
H	F,G	4	1	1.0
I	H	5	5	inf

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

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 mínimos y máximos de los nodos del grafo Roy 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 24

Figura 1: Grafo Roy con las duraciones normales

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

	actividades	duración = suma	duración
Route_1	A - C - D - G - H - I	A(3) + C(7) + D(7) + G(5) + H(4) + I(5) = 31	31.0
Route_2	A - C - F - H - I	A(3) + C(7) + F(8) + H(4) + I(5) = 27	27.0
Route_3	A - C - G - H - I	A(3) + C(7) + G(5) + H(4) + I(5) = 24	24.0
Route_4	B - C - D - G - H - I	B(2) + C(7) + D(7) + G(5) + H(4) + I(5) = 30	30.0
Route_5	B - C - F - H - I	B(2) + C(7) + F(8) + H(4) + I(5) = 26	26.0
Route_6	B - C - G - H - I	B(2) + C(7) + G(5) + H(4) + I(5) = 23	23.0
Route_7	B - E - F - H - I	B(2) + E(4) + F(8) + H(4) + I(5) = 23	23.0
Route_8	B - E - G - H - I	B(2) + E(4) + G(5) + H(4) + I(5) = 20	20.0

Apartado 2

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

Tabla 4: 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 31); se acorta un periodo la combinación de menor coste: H (coste 1). Resultado: periodos disponibles (fila 1) y duración de las rutas (columna 1); el proyecto dura 30.

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

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

Tabla 5: Opciones consideradas en cada paso

	duración	rutas críticas	opciones (coste)	elegida	coste del paso
paso
1	31	Route_1	H (1); C (4); A (5); G (9)	H	1.0
2	30	Route_1	H (1); C (4); A (5); G (9)	H	1.0
3	29	Route_1	H (1); C (4); A (5); G (9)	H	1.0

Ackoff-Sasieni acorta H (3) con un sobrecoste de 3 k€; duración 28.

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)	0.0	0.0	0.0	0.0	0.0	0.0	0.0	3.0	0.0
x (PL)	0.0	0.0	0.0	0.0	0.0	0.0	0.0	3.0	0.0
CUR	5.0	inf	4.0	inf	1.0	inf	9.0	1.0	inf

La programación lineal acorta H (3) con sobrecoste 3 k€; todas las rutas quedan en como mucho 28 semanas (objetivo 28).

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

	actividades	duración = suma	duración
Route_1	A - C - D - G - H - I	A(3.0) + C(7.0) + D(7.0) + G(5.0) + H(1.0) + I...	28.0
Route_2	A - C - F - H - I	A(3.0) + C(7.0) + F(8.0) + H(1.0) + I(5.0) = 24.0	24.0
Route_3	A - C - G - H - I	A(3.0) + C(7.0) + G(5.0) + H(1.0) + I(5.0) = 21.0	21.0
Route_4	B - C - D - G - H - I	B(2.0) + C(7.0) + D(7.0) + G(5.0) + H(1.0) + I...	27.0
Route_5	B - C - F - H - I	B(2.0) + C(7.0) + F(8.0) + H(1.0) + I(5.0) = 23.0	23.0
Route_6	B - C - G - H - I	B(2.0) + C(7.0) + G(5.0) + H(1.0) + I(5.0) = 20.0	20.0
Route_7	B - E - F - H - I	B(2.0) + E(4.0) + F(8.0) + H(1.0) + I(5.0) = 20.0	20.0
Route_8	B - E - G - H - I	B(2.0) + E(4.0) + G(5.0) + H(1.0) + I(5.0) = 17.0	17.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.