Tarea Fb

Departamento de informática - Casa central.
ILI281-Fundamentos de investigación de operaciones
TAREA 2 - Método PERT/CPM,
programación lineal entera y programación dinámica.

Alumnos:
Franco Migliaro 201111024-2
Benjamin Diaz 201104089-9

Profesor:
Alvaro Luzzi
Carlos Castro

Ayudante:
Yaichi Perez
Francisco Benavides

Fecha de entrega:
25 de Mayo de 2015

1.

Pregunta 1: "PERT/CPM"
(a) Enprimera instancia se realizó el grafo para tener la duración total del proyecto:

Con esto se concluye que el proyecto demorará 96 días.
La ruta crítica obtenida es: A-E-K-L-M-Q-U-W-Z (color rojo en el grafo) .
(b) Si se desea disminuir en 6 días la duración del proceso, hay que acelerar algunas etapas, y como se quiere
minimizar costos, se acalerarán las etapas que sean parte de la ruta crítica queposean menor costo de aceleracion,
de la siguiente forma:
2 días en la actividad A, con un costo de 4 billones de dólares.
1 día en la actividad E, con un costo de 8 billones de dólares.
2 días en la actividad L, con un costo de 8 billones de dólares.
1 día en la actividad Z, con un costo de 9 billones de dólares.
Esto da un total de 29 billones de dólares. Por tanto no alcanza con el presupuesto de20.
(c) Por otro lado se resolvió mediante el programa LPsolve usando el siguinte código:

Función objetivo:
MIN: z = 2ya + 23yb + 4yc + 7yd + 8ye + 4yg + 2yi + 4yj + 50yk + 4yl + 70ym + 4yn + 8yo + 4yp + 7yr + 8ys +
6yt + 10yu + 9yv + 6yx + 4yy + 9yz

1

Restricciones:
Naturaleza de las variables
x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18 ≥ 0
ya, yb, yc, yd,ye, yg, yi, yj, yk, yl, ym, yn, yo, yp, yr, ys, yt, yu, yv, yx, yy, yz ≥ 0
Aceleración:
x17 - x1 <90
Acumulación de tiempo:
x2 - x1 + ya >6
x3 - x1 + yb >8
x4 - x1 + yc >4
x5 - x1 + yd >2
x2 - x4 >0
x5 - x4 >0
x3 - x4 >0
x6 - x2 + ye >7
x12 - x3 >9
x12 - x5 + yg >9
x12 - x4 >2
x7 - x6 + yi >8
x9 - x6 + yj >4
x10 - x6 + yk >12
x18 - x10 + yl >4
x12 - x18 + ym >3
x8 - x7 + yn>7
x11 - x9 + yo >7
x11- x18 + yp>6
x13 - x12 >5
x15 - x8 + yr >7
x15 - x9 + ys >6
x14 - x11 + yt >8
x14 - x13 + yu >15
x16 - x13 + yv >11
x16 - x14 >16
x17 - x15 + yx >53
x17 - x14 + yy >13
x17 - x16 + yz >28
x9 - x7 >0
x11 - x8 >0
x14 - x15 >0

2

Máxima aceleración por actividad:
ya <2
yb <4
yc <4
yd <2
ye <1
yg <8
yi <1
yj <3
yk <4
yl <2
ym <3
yn <1
yo <4
yp <2
yr <3
ys <2
yt <5
yu <1
yv <3
yx <4
yy <1
yz <2Obteniendo los siguientes resultados:

ya = 2
ye = 1
yl = 2
yz = 1
Con un costo total de $29 billones, las etapas a acelerar son A (2 dias), E (1 día), L (2 dias) y Z (1 dia).

Se logra verificar que los calculos obtenidos de forma rápida estan correctos.
NOTA: Se adjunta archivo de LPSolve con el programa.

3

2.

Pregunta 2: "PLE: Concierto chileno"

Este problema se trata de decidir que bandasinvitar para un concierto que se realizará, la primera parte tiene
un límite de dinero fijo por lo que se maximizara la cantidad de personas y la segunda parte tiene un limite de
personas fijo, donde se determinará el costo mínimo. Al ser un problema de desicion, se tratará como programación
lineal entera binaria, donde los resultados de las variables serán 0 o 1, dependiendo si combiene o no invitara las
determinadas bandas.
Parte a: Maximización de personas
En la primera parte se nos pide maximizar la cantidad de personas.
Variables:

Xi : 1 si la banda i es invitada o 0 si la banda no es invitada
y: 1 si las bandas 1 y 8 (Cable a Tierra y Bus Band Blues) son invitadas o 0 si una de las dos bandas no es invitada
Función objetivo:
M AXZ = pX1 + 5,11pX2 + 0,64pX3 + 2,71pX4 + 0,79pX5 +11,87pX6 + 2,13x7 + 2,64x8

Restricciones:
x6 + x2 > 1
x5 − x7 > 0
x3 − x7 > 0
x1 + x8 − 2y > 0
La restricción anterior es la encargada asignar el doble del costo asociado a invitar a la banda 1 y la banda 8.
ci xi + y(c8 + c1 ) < 2000000
pi xi < 5000
pi xi > 1500
Naturaleza:
x1, x2, x3, x4, x5, x6, x7, x8 ∈ 0, 1

4

Resolviendo el problema con LpSolve:
Z=1238 personas
x1 = 1 , x2 = 1 , x3 = 1 , x4 =...