informe tarea n 2 investigaci¶on de operaciones...

Informe Tarea N◦ 2

Investigacion de Operaciones I

Vıctor Pena y Lillo Z.

2273001-0

[email protected]

Patricia Trejo G.

2173019-K

[email protected]

Valparaıso, 9 de Septiembre de 2005

1. Representacion Grafica del Proyecto

Figura 1: Malla del proyecto

Intervalos de tiempo mas temprano y mas tarde para cada tarea:

• T01: (0,9) [0,9]

• T02: (0,7) [2,9]

• T03: (9,17) [9,17]

• T04: (9,11) [12,14]

• T05: (9,16) [9,16]

• T06: (9,14) [9,14]

• T07: (17,22) [17,22]

• T08: (22,27) [22,27]

• T09: (11,13) [14,16]

• T10: (16,23) [16,23]

Tarea N◦ 2 - Investigacion de Operaciones I 2

• T11: (23,30) [23,30]

• T12: (14,29) [16,22]

• T13: (14,15) [15,16]

• T14: (14,16) [14,16]

• T15: (14,21) [20,27]

• T16: (27,39) [27,30]

• T17: (30,32) [32,34]

• T18: (30,34) [30,34]

• T19: (32,36) [35,39]

• T20: (32,37) [34,39]

• T21: (36,38) [39,41]

• T22: (34,37) [34,37]

• T23: (37,39) [37,39]

• T24: (39,41) [39,41]

Duracion del Proyecto = 41 dıas.

Actividades que se pueden retrasar sin afectar la duracion del proyecto:

• T02 en 2 dıas.

• T04 en 3 dıas.

• T09 en 3 dıas.

• T12 en 2 dıas.

• T13 en 1 dıa.

• T15 en 6 dıas.

• T17 en 2 dıas.

• T19 en 3 dıas.

• T20 en 2 dıas.

• T21 en 3 dıas.

Rutas Crıticas

a) T01 - T03 - T07 - T08 - T16 - T18 - T22 - T23 - T24

b) T01 - T05 - T10 - T11 - T18 - T22 - T23 - T24

c) T01 - T06 - T14 - dummy - T10 - T11 - T18 - T22 - T23 - T24

2. Modelo de Programacion Lineal sin Aceleracion de Tareas

2.1. Variables de Decision

Xi : Tiempo acumulado hasta nodo i.i : 1..18

Universidad Tecnica Federico Santa Marıa


2.2. Modelo Propuesto

Minimizar tiempo de duracion del proyecto [dıas]:

Min z = X18 − X1

La funcion objetivo esta acotada por las siguientes restricciones:

1. Restricciones de Duracion de Tareas

X2 ≥ X1 + 7 (1)

X3 ≥ X1 + 9 (2)

X3 ≥ X2 (3)

X4 ≥ X3 + 8 (4)

X5 ≥ X3 + 5 (5)

X6 ≥ X3 + 2 (6)

X7 ≥ X4 + 5 (7)

X7 ≥ X5 + 6 (8)

X8 ≥ X5 + 2 (9)

X9 ≥ X5 + 1 (10)

X9 ≥ X6 + 2 (11)

X9 ≥ X3 + 7 (12)

X9 ≥ X8 (13)

X10 ≥ X7 + 5 (14)

X10 ≥ X5 + 7 (15)

X11 ≥ X9 + 7 (16)

X12 ≥ X11 + 7 (17)

X12 ≥ X10 + 3 (18)

X13 ≥ X12 + 2 (19)

X14 ≥ X12 + 4 (20)

X15 ≥ X13 + 4 (21)

X16 ≥ X14 + 3 (22)

X17 ≥ X16 + 2 (23)

X17 ≥ X13 + 5 (24)

X18 ≥ X15 + 2 (25)

X18 ≥ X17 + 2 (26)



2. Restricciones de Signo

Xi ≥ 0 ∀i = 1 : 18 (27)

2.3. Modelo en LINDO

MIN X18 - X1

SUBJECT TO

2) X2 - X1 >= 7

3) X3 - X1 >= 9

4) X3 - X2 >= 0

5) X4 - X3 >= 8

6) X5 - X3 >= 5

7) X6 - X3 >= 2

8) X7 - X4 >= 5

9) X7 - X5 >= 6

10) X8 - X5 >= 2

11) X9 - X5 >= 1

12) X9 - X6 >= 2

13) X9 - X3 >= 7

14) X9 - X8 >= 0

15) X10 - X7 >= 5

16) X10 - X5 >= 7

17) X11 - X9 >= 7

18) X12 - X11 >= 7

19) X12 - X10 >= 3

20) X13 - X12 >= 2

21) X14 - X12 >= 4

22) X15 - X13 >= 4

23) X16 - X14 >= 3

24) X17 - X16 >= 2

25) X17 - X13 >= 5

26) X18 - X15 >= 2

27) X18 - X17 >= 2

28) X1 >= 0

29) X2 >= 0

30) X3 >= 0

31) X4 >= 0

32) X5 >= 0

33) X6 >= 0

34) X7 >= 0

35) X8 >= 0

36) X9 >= 0

37) X10 >= 0

38) X11 >= 0

39) X12 >= 0

40) X13 >= 0

41) X14 >= 0

42) X15 >= 0

43) X16 >= 0

44) X17 >= 0



45) X18 >= 0

2.4. Solucion con LINDO

LP OPTIMUM FOUND AT STEP 21

OBJECTIVE FUNCTION VALUE

1) 41.00000

VARIABLE VALUE REDUCED COST

X18 41.000000 0.000000

X1 0.000000 0.000000

X2 9.000000 0.000000

X3 9.000000 0.000000

X4 17.000000 0.000000

X5 14.000000 0.000000

X6 11.000000 0.000000

X7 22.000000 0.000000

X8 16.000000 0.000000

X9 16.000000 0.000000

X10 27.000000 0.000000

X11 23.000000 0.000000

X12 30.000000 0.000000

X13 34.000000 0.000000

X14 34.000000 0.000000

X15 39.000000 0.000000

X16 37.000000 0.000000

X17 39.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 2.000000 0.000000

3) 0.000000 -1.000000

4) 0.000000 0.000000

5) 0.000000 -1.000000

6) 0.000000 0.000000

7) 0.000000 0.000000

8) 0.000000 -1.000000

9) 2.000000 0.000000

10) 0.000000 0.000000

11) 1.000000 0.000000

12) 3.000000 0.000000

13) 0.000000 0.000000

14) 0.000000 0.000000

15) 0.000000 -1.000000

16) 6.000000 0.000000

17) 0.000000 0.000000

18) 0.000000 0.000000

19) 0.000000 -1.000000

20) 2.000000 0.000000

21) 0.000000 -1.000000



22) 1.000000 0.000000

23) 0.000000 -1.000000

24) 0.000000 -1.000000

25) 0.000000 0.000000

26) 0.000000 0.000000

27) 0.000000 -1.000000

28) 0.000000 0.000000

29) 9.000000 0.000000

30) 9.000000 0.000000

31) 17.000000 0.000000

32) 14.000000 0.000000

33) 11.000000 0.000000

34) 22.000000 0.000000

35) 16.000000 0.000000

36) 16.000000 0.000000

37) 27.000000 0.000000

38) 23.000000 0.000000

39) 30.000000 0.000000

40) 34.000000 0.000000

41) 34.000000 0.000000

42) 39.000000 0.000000

43) 37.000000 0.000000

44) 39.000000 0.000000

45) 41.000000 0.000000

NO. ITERATIONS= 21

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE

X18 1.000000 INFINITY 0.000000

X1 -1.000000 INFINITY 0.000000

X2 0.000000 0.000000 0.000000

X3 0.000000 INFINITY 0.000000

X4 0.000000 INFINITY 0.000000

X5 0.000000 0.000000 0.000000

X6 0.000000 INFINITY 0.000000

X7 0.000000 INFINITY 0.000000

X8 0.000000 0.000000 0.000000

X9 0.000000 0.000000 0.000000

X10 0.000000 INFINITY 0.000000

X11 0.000000 0.000000 0.000000

X12 0.000000 INFINITY 0.000000

X13 0.000000 0.000000 0.000000

X14 0.000000 INFINITY 0.000000

X15 0.000000 0.000000 0.000000

X16 0.000000 INFINITY 0.000000

X17 0.000000 INFINITY 0.000000

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE



RHS INCREASE DECREASE

2 7.000000 2.000000 INFINITY

3 9.000000 INFINITY 2.000000

4 0.000000 2.000000 INFINITY

5 8.000000 INFINITY 0.000000

6 5.000000 0.000000 INFINITY

7 2.000000 3.000000 11.000000

8 5.000000 INFINITY 0.000000

9 6.000000 2.000000 INFINITY

10 2.000000 0.000000 1.000000

11 1.000000 1.000000 INFINITY

12 2.000000 3.000000 INFINITY

13 7.000000 0.000000 INFINITY

14 0.000000 0.000000 1.000000

15 5.000000 2.000000 0.000000

16 7.000000 6.000000 INFINITY

17 7.000000 0.000000 2.000000

18 7.000000 0.000000 2.000000

19 3.000000 2.000000 0.000000

20 2.000000 2.000000 INFINITY

21 4.000000 INFINITY 2.000000

22 4.000000 1.000000 INFINITY

23 3.000000 INFINITY 2.000000

24 2.000000 INFINITY 2.000000

25 5.000000 2.000000 1.000000

26 2.000000 1.000000 INFINITY

27 2.000000 INFINITY 1.000000

28 0.000000 0.000000 INFINITY

29 0.000000 9.000000 INFINITY

30 0.000000 9.000000 INFINITY

31 0.000000 17.000000 INFINITY

32 0.000000 14.000000 INFINITY

33 0.000000 11.000000 INFINITY

34 0.000000 22.000000 INFINITY

35 0.000000 16.000000 INFINITY

36 0.000000 16.000000 INFINITY

37 0.000000 27.000000 INFINITY

38 0.000000 23.000000 INFINITY

39 0.000000 30.000000 INFINITY

40 0.000000 34.000000 INFINITY

41 0.000000 34.000000 INFINITY

42 0.000000 39.000000 INFINITY

43 0.000000 37.000000 INFINITY

44 0.000000 39.000000 INFINITY

45 0.000000 41.000000 INFINITY

2.5. Comentarios

Evidentemente el problema anterior tiene muchas soluciones alternativas, debido a que algunas tareaspueden ser retrasadas sin afectar la duracion del proyecto y a la arbitrariedad en fijar el instante deinicio, sin embargo, todas ellas poseen como valor de la funcion objetivo z = 41.



3. Modelo de Programacion Lineal con Aceleracion de Tareas

3.1. Variables de Decision

Xi : Tiempo acumulado hasta nodo i.i : 1..18

Yj : Tiempo que se acelera la tarea Tj .j : 01..24

3.2. Modelo Propuesto

Minimizar costo para terminar el proyecto en un tiempo determinado (34 [dıas]):

Min z = 100 ∗ Y01 + 50 ∗ Y02 + 300 ∗ Y03 + 100 ∗ Y04 + 500 ∗ Y05 + 50 ∗ Y06 + 70 ∗ Y07 + 60 ∗ Y08

+ 150 ∗ Y09 + 350 ∗ Y10 + 20 ∗ Y11 + 80 ∗ Y12 + 40 ∗ Y13 + 230 ∗ Y14 + 10 ∗ Y15 + 30 ∗ Y16

+ 100 ∗ Y17 + 500 ∗ Y18 + 20 ∗ Y19 + 140 ∗ Y20 + 200 ∗ Y21 + 45 ∗ Y22 + 100 ∗ Y23 + 150 ∗ Y24

La funcion objetivo esta acotada por las siguientes restricciones:

1. Restricciones de Duracion de Tareas

X2 ≥ X1 + 7 − Y02 (28)

X3 ≥ X1 + 9 − Y01 (29)

X3 ≥ X2 (30)

X4 ≥ X3 + 8 − Y03 (31)

X5 ≥ X3 + 5 − Y06 (32)

X6 ≥ X3 + 2 − Y04 (33)

X7 ≥ X4 + 5 − Y07 (34)

X7 ≥ X5 + 6 − Y12 (35)

X8 ≥ X5 + 2 − Y14 (36)

X9 ≥ X5 + 1 − Y13 (37)

X9 ≥ X6 + 2 − Y09 (38)

X9 ≥ X3 + 7 − Y05 (39)

X9 ≥ X8 (40)

X10 ≥ X7 + 5 − Y08 (41)

X10 ≥ X5 + 7 − Y15 (42)

X11 ≥ X9 + 7 − Y10 (43)

X12 ≥ X11 + 7 − Y11 (44)

X12 ≥ X10 + 3 − Y16 (45)

X13 ≥ X12 + 2 − Y17 (46)



X14 ≥ X12 + 4 − Y18 (47)

X15 ≥ X13 + 4 − Y19 (48)

X16 ≥ X14 + 3 − Y22 (49)

X17 ≥ X16 + 2 − Y23 (50)

X17 ≥ X13 + 5 − Y20 (51)

X18 ≥ X15 + 2 − Y21 (52)

X18 ≥ X17 + 2 − Y24 (53)

2. Restricciones de Lımite de Aceleracion

Y01 ≤ 3 (54)

Y02 ≤ 3 (55)

Y03 ≤ 3 (56)

Y04 ≤ 1 (57)

Y05 ≤ 3 (58)

Y06 ≤ 2 (59)

Y07 ≤ 2 (60)

Y08 ≤ 2 (61)

Y09 ≤ 1 (62)

Y10 ≤ 3 (63)

Y11 ≤ 3 (64)

Y12 ≤ 3 (65)

Y13 ≤ 0 (66)

Y14 ≤ 1 (67)

Y15 ≤ 3 (68)

Y16 ≤ 2 (69)

Y17 ≤ 1 (70)

Y18 ≤ 2 (71)

Y19 ≤ 2 (72)

Y20 ≤ 2 (73)

Y21 ≤ 1 (74)

Y22 ≤ 2 (75)

Y23 ≤ 1 (76)

Y24 ≤ 1 (77)

3. Restriccion de Duracion del Proyecto

X18 − X1 ≤ 34 (78)

4. Restricciones de Signo

Xi ≥ 0 ∀i = 1 : 18 (79)

Yj ≥ 0 ∀j = 1 : 24 (80)



3.3. Modelo en LINDO

MIN 100 Y01 + 50 Y02 + 300 Y03 + 100 Y04 + 500 Y05 + 50 Y06 + 70 Y07 + 60 Y08 + 150 Y09

+ 350 Y10 + 20 Y11 + 80 Y12 + 40 Y13 + 230 Y14 + 10 Y15 + 30 Y16 + 100 Y17 + 500 Y18

+ 20 Y19 + 140 Y20 + 200 Y21 + 45 Y22 + 100 Y23 +150 Y24

SUBJECT TO

2) X2 - X1 + Y02 >= 7

3) X3 - X1 + Y01 >= 9

4) X3 - X2 >= 0

5) X4 - X3 + Y03 >= 8

6) X5 - X3 + Y06 >= 5

7) X6 - X3 + Y04 >= 2

8) X7 - X4 + Y07 >= 5

9) X7 - X5 + Y12 >= 6

10) X8 - X5 + Y14 >= 2

11) X9 - X5 + Y13 >= 1

12) X9 - X6 + Y09 >= 2

13) X9 - X3 + Y05 >= 7

14) X9 - X8 >= 0

15) X10 - X7 + Y08 >= 5

16) X10 - X5 + Y15 >= 7

17) X11 - X9 + Y10 >= 7

18) X12 - X11 + Y11 >= 7

19) X12 - X10 + Y16 >= 3

20) X13 - X12 + Y17 >= 2

21) X14 - X12 + Y18 >= 4

22) X15 - X13 + Y19 >= 4

23) X16 - X14 + Y22 >= 3

24) X17 - X16 + Y23 >= 2

25) X17 - X13 + Y20 >= 5

26) X18 - X15 + Y21 >= 2

27) X18 - X17 + Y24 >= 2

28) X1 >= 0

29) X2 >= 0

30) X3 >= 0

31) X4 >= 0

32) X5 >= 0

33) X6 >= 0

34) X7 >= 0

35) X8 >= 0

36) X9 >= 0

37) X10 >= 0

38) X11 >= 0

39) X12 >= 0

40) X13 >= 0

41) X14 >= 0

42) X15 >= 0

43) X16 >= 0

44) X17 >= 0

45) X18 >= 0

46) Y01 >= 0



47) Y02 >= 0

48) Y03 >= 0

49) Y04 >= 0

50) Y05 >= 0

51) Y06 >= 0

52) Y07 >= 0

53) Y08 >= 0

54) Y09 >= 0

55) Y10 >= 0

56) Y11 >= 0

57) Y12 >= 0

58) Y13 >= 0

59) Y14 >= 0

60) Y15 >= 0

61) Y16 >= 0

62) Y17 >= 0

63) Y18 >= 0

64) Y19 >= 0

65) Y20 >= 0

66) Y21 >= 0

67) Y22 >= 0

68) Y23 >= 0

69) Y24 >= 0

70) Y01 <= 3

71) Y02 <= 3

72) Y03 <= 3

73) Y04 <= 1

74) Y05 <= 3

75) Y06 <= 2

76) Y07 <= 2

77) Y08 <= 2

78) Y09 <= 1

79) Y10 <= 3

80) Y11 <= 3

81) Y12 <= 3

82) Y13 <= 0

83) Y14 <= 1

84) Y15 <= 3

85) Y16 <= 2

86) Y17 <= 1

87) Y18 <= 2

88) Y19 <= 2

89) Y20 <= 2

90) Y21 <= 1

91) Y22 <= 2

92) Y23 <= 1

93) Y24 <= 1

94) X18 - X1 <= 34



3.4. Solucion con LINDO

LP OPTIMUM FOUND AT STEP 49

OBJECTIVE FUNCTION VALUE

1) 470.0000

VARIABLE VALUE REDUCED COST

Y01 2.000000 0.000000

Y02 0.000000 50.000000

Y03 0.000000 240.000000

Y04 0.000000 100.000000

Y05 0.000000 460.000000

Y06 0.000000 50.000000

Y07 0.000000 10.000000

Y08 1.000000 0.000000

Y09 0.000000 150.000000

Y10 0.000000 310.000000

Y11 3.000000 0.000000

Y12 0.000000 80.000000

Y13 0.000000 40.000000

Y14 0.000000 230.000000

Y15 0.000000 10.000000

Y16 2.000000 0.000000

Y17 0.000000 100.000000

Y18 0.000000 400.000000

Y19 0.000000 20.000000

Y20 0.000000 140.000000

Y21 0.000000 200.000000

Y22 2.000000 0.000000

Y23 0.000000 0.000000

Y24 0.000000 50.000000

X2 7.000000 0.000000

X1 0.000000 0.000000

X3 7.000000 0.000000

X4 15.000000 0.000000

X5 12.000000 0.000000

X6 12.000000 0.000000

X7 20.000000 0.000000

X8 14.000000 0.000000

X9 14.000000 0.000000

X10 24.000000 0.000000

X11 21.000000 0.000000

X12 25.000000 0.000000

X13 27.000000 0.000000

X14 29.000000 0.000000

X15 31.000000 0.000000

X16 30.000000 0.000000

X17 32.000000 0.000000

X18 34.000000 0.000000



ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 0.000000

3) 0.000000 -100.000000

4) 0.000000 0.000000

5) 0.000000 -60.000000

6) 0.000000 0.000000

7) 3.000000 0.000000

8) 0.000000 -60.000000

9) 2.000000 0.000000

10) 0.000000 0.000000

11) 1.000000 0.000000

12) 0.000000 0.000000

13) 0.000000 -40.000000

14) 0.000000 0.000000

15) 0.000000 -60.000000

16) 5.000000 0.000000

17) 0.000000 -40.000000

18) 0.000000 -40.000000

19) 0.000000 -60.000000

20) 0.000000 0.000000

21) 0.000000 -100.000000

22) 0.000000 0.000000

23) 0.000000 -100.000000

24) 0.000000 -100.000000

25) 0.000000 0.000000

26) 1.000000 0.000000

27) 0.000000 -100.000000

28) 0.000000 0.000000

29) 7.000000 0.000000

30) 7.000000 0.000000

31) 15.000000 0.000000

32) 12.000000 0.000000

33) 12.000000 0.000000

34) 20.000000 0.000000

35) 14.000000 0.000000

36) 14.000000 0.000000

37) 24.000000 0.000000

38) 21.000000 0.000000

39) 25.000000 0.000000

40) 27.000000 0.000000

41) 29.000000 0.000000

42) 31.000000 0.000000

43) 30.000000 0.000000

44) 32.000000 0.000000

45) 34.000000 0.000000

46) 2.000000 0.000000

47) 0.000000 0.000000

48) 0.000000 0.000000

49) 0.000000 0.000000

50) 0.000000 0.000000

51) 0.000000 0.000000

52) 0.000000 0.000000

53) 1.000000 0.000000

54) 0.000000 0.000000



55) 0.000000 0.000000

56) 3.000000 0.000000

57) 0.000000 0.000000

58) 0.000000 0.000000

59) 0.000000 0.000000

60) 0.000000 0.000000

61) 2.000000 0.000000

62) 0.000000 0.000000

63) 0.000000 0.000000

64) 0.000000 0.000000

65) 0.000000 0.000000

66) 0.000000 0.000000

67) 2.000000 0.000000

68) 0.000000 0.000000

69) 0.000000 0.000000

70) 1.000000 0.000000

71) 3.000000 0.000000

72) 3.000000 0.000000

73) 1.000000 0.000000

74) 3.000000 0.000000

75) 2.000000 0.000000

76) 2.000000 0.000000

77) 1.000000 0.000000

78) 1.000000 0.000000

79) 3.000000 0.000000

80) 0.000000 20.000000

81) 3.000000 0.000000

82) 0.000000 0.000000

83) 1.000000 0.000000

84) 3.000000 0.000000

85) 0.000000 30.000000

86) 1.000000 0.000000

87) 2.000000 0.000000

88) 2.000000 0.000000

89) 2.000000 0.000000

90) 1.000000 0.000000

91) 0.000000 55.000000

92) 1.000000 0.000000

93) 1.000000 0.000000

94) 0.000000 100.000000

NO. ITERATIONS= 49

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE

Y01 100.000000 0.000000 20.000000

Y02 50.000000 INFINITY 50.000000

Y03 300.000000 INFINITY 240.000000

Y04 100.000000 INFINITY 100.000000

Y05 500.000000 INFINITY 460.000000



Y06 50.000000 INFINITY 50.000000

Y07 70.000000 INFINITY 10.000000

Y08 60.000000 10.000000 30.000000

Y09 150.000000 INFINITY 150.000000

Y10 350.000000 INFINITY 310.000000

Y11 20.000000 20.000000 INFINITY

Y12 80.000000 INFINITY 80.000000

Y13 40.000000 INFINITY 40.000000

Y14 230.000000 INFINITY 230.000000

Y15 10.000000 INFINITY 10.000000

Y16 30.000000 30.000000 INFINITY

Y17 100.000000 INFINITY 100.000000

Y18 500.000000 INFINITY 400.000000

Y19 20.000000 INFINITY 20.000000

Y20 140.000000 INFINITY 140.000000

Y21 200.000000 INFINITY 200.000000

Y22 45.000000 55.000000 INFINITY

Y23 100.000000 INFINITY 0.000000

Y24 150.000000 INFINITY 50.000000

X2 0.000000 0.000000 0.000000

X1 0.000000 INFINITY 0.000000

X3 0.000000 20.000000 0.000000

X4 0.000000 20.000000 0.000000

X5 0.000000 0.000000 0.000000

X6 0.000000 0.000000 0.000000

X7 0.000000 10.000000 0.000000

X8 0.000000 0.000000 0.000000

X9 0.000000 20.000000 0.000000

X10 0.000000 30.000000 0.000000

X11 0.000000 20.000000 0.000000

X12 0.000000 55.000000 0.000000

X13 0.000000 0.000000 0.000000

X14 0.000000 55.000000 0.000000

X15 0.000000 0.000000 0.000000

X16 0.000000 100.000000 0.000000

X17 0.000000 100.000000 0.000000

X18 0.000000 100.000000 0.000000

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE

RHS INCREASE DECREASE

2 7.000000 0.000000 INFINITY

3 9.000000 1.000000 2.000000

4 0.000000 0.000000 INFINITY

5 8.000000 1.000000 1.000000

6 5.000000 0.000000 INFINITY

7 2.000000 3.000000 INFINITY

8 5.000000 1.000000 1.000000

9 6.000000 2.000000 INFINITY

10 2.000000 0.000000 1.000000

11 1.000000 1.000000 INFINITY

12 2.000000 3.000000 INFINITY

13 7.000000 0.000000 0.000000

14 0.000000 0.000000 1.000000



15 5.000000 1.000000 1.000000

16 7.000000 5.000000 INFINITY

17 7.000000 0.000000 1.000000

18 7.000000 0.000000 1.000000

19 3.000000 1.000000 1.000000

20 2.000000 0.000000 INFINITY

21 4.000000 0.000000 0.000000

22 4.000000 1.000000 31.000000

23 3.000000 0.000000 0.000000

24 2.000000 0.000000 0.000000

25 5.000000 0.000000 1.000000

26 2.000000 1.000000 INFINITY

27 2.000000 0.000000 1.000000

28 0.000000 0.000000 INFINITY

29 0.000000 7.000000 INFINITY

30 0.000000 7.000000 INFINITY

31 0.000000 15.000000 INFINITY

32 0.000000 12.000000 INFINITY

33 0.000000 12.000000 INFINITY

34 0.000000 20.000000 INFINITY

35 0.000000 14.000000 INFINITY

36 0.000000 14.000000 INFINITY

37 0.000000 24.000000 INFINITY

38 0.000000 21.000000 INFINITY

39 0.000000 25.000000 INFINITY

40 0.000000 27.000000 INFINITY

41 0.000000 29.000000 INFINITY

42 0.000000 31.000000 INFINITY

43 0.000000 30.000000 INFINITY

44 0.000000 32.000000 INFINITY

45 0.000000 34.000000 INFINITY

46 0.000000 2.000000 INFINITY

47 0.000000 0.000000 INFINITY

48 0.000000 0.000000 INFINITY

49 0.000000 0.000000 INFINITY

50 0.000000 0.000000 INFINITY

51 0.000000 0.000000 INFINITY

52 0.000000 0.000000 INFINITY

53 0.000000 1.000000 INFINITY

54 0.000000 0.000000 INFINITY

55 0.000000 0.000000 INFINITY

56 0.000000 3.000000 INFINITY

57 0.000000 0.000000 INFINITY

58 0.000000 0.000000 INFINITY

59 0.000000 0.000000 INFINITY

60 0.000000 0.000000 INFINITY

61 0.000000 2.000000 INFINITY

62 0.000000 0.000000 INFINITY

63 0.000000 0.000000 INFINITY

64 0.000000 0.000000 INFINITY

65 0.000000 0.000000 INFINITY

66 0.000000 0.000000 INFINITY

67 0.000000 2.000000 INFINITY

68 0.000000 0.000000 INFINITY



69 0.000000 0.000000 INFINITY

70 3.000000 INFINITY 1.000000

71 3.000000 INFINITY 3.000000

72 3.000000 INFINITY 3.000000

73 1.000000 INFINITY 1.000000

74 3.000000 INFINITY 3.000000

75 2.000000 INFINITY 2.000000

76 2.000000 INFINITY 2.000000

77 2.000000 INFINITY 1.000000

78 1.000000 INFINITY 1.000000

79 3.000000 INFINITY 3.000000

80 3.000000 1.000000 0.000000

81 3.000000 INFINITY 3.000000

82 0.000000 INFINITY 0.000000

83 1.000000 INFINITY 1.000000

84 3.000000 INFINITY 3.000000

85 2.000000 1.000000 1.000000

86 1.000000 INFINITY 1.000000

87 2.000000 INFINITY 2.000000

88 2.000000 INFINITY 2.000000

89 2.000000 INFINITY 2.000000

90 1.000000 INFINITY 1.000000

91 2.000000 0.000000 0.000000

92 1.000000 INFINITY 1.000000

93 1.000000 INFINITY 1.000000

94 34.000000 2.000000 0.000000

3.5. Comentarios

El resultado obtenido por LINDO indica que el proyecto termina en 34 [dıas] con un costo mınimo de470 [miles de pesos].

4. Determinacion Duracion Proyecto vıa Monte Carlo

Se generaron 1000 proyectos aleatorios para lograr una aproximacion mas confiable acerca de la porba-bilidad de terminar el proyecto en menos de 39 dıas.

A nivel de codigo, el programa fue creado para trabajar unicamente con la malla propuesta en laTarea. Es decir, los diversos caminos parap oder calcular la duracion de los proyectos aleatorios estandefinidos a nivel de codigo y no es posible que el usuario los ingrese, para que sea menos engorroso ycubra lo pedido en el enunciado.

4.1. Codigo

% Tarea No2 Investigacion de Operaciones - ILI-292

%

% Integrantes: Victor Pe~na y Lillo 2272001-0



% Patricia Trejo 2173019-K

% Ayudante: Jorge Guerrero

% Fecha de Entrega: Viernes 09 de Septiembre de 2005

function [Prob]=MonteCarlo(T,A,M,B)

% Se reciben como parametros:

%

% T: Cantidad de dias en la que se desea terminar el proyecto

% M: Arreglo con el tiempo de termino de cada actividad

% A: Arreglo con la cantidad de dias minimo en las que se pueden llevar

% a cabo cada una de las actiivdades del proyecto

% B: Arreglo con la cantidad de dias maximo en las que se pueden llevar

% a cabo cada una de las actividades del proyecto

%

% En termino de la tarea realizada:

%

% T = 39;

% M = [9 7 8 2 7 5 5 5 2 7 7 6 1 2 7 3 2 4 4 5 2 3 2 2];

% A = [6 6 7 2 5 3 4 3 2 3 4 5 1 1 6 1 1 2 3 4 1 1 2 1];

% B = [11 8 10 3 9 6 5 6 2 9 9 7 2 4 7 4 2 5 5 7 4 4 2 3];

%

% Por lo que la funcion es llamada como:

%

% MonteCarlo(T,A,M,B)

tM = size(M); % tM(2) es la cantidad de actividades

% Generacion Randomica de N = 1000 datos aleatorios uniformemente distribuidos

% entre 0 y 1

N = 1000;

R = rand(1,N);

tR = size(R);

% Generacion de los N proyectos aleatorios de tM(2) tareas cada uno

for i=1:tR(2)

for j=1:tM(2)

if ((B(j)-A(j)) ~= 0)

if (R(i) <= ( (M(j)-A(j)) / (B(j)-A(j)) ) )

x(i,j) = A(j) + sqrt( R(i)*( M(j) - A(j) )/( B(j) - A(j) ));

elseif (R(i) >= ((M(j)-A(j))/(B(j)-A(j))))

x(i,j) = B(j) - 0.5*sqrt( 4*(B(j))^2 + 4*(A(j)*M(j) - A(j)*B(j)

- B(j)*M(j) - R(i)*(B(j))^2 + R(i)*A(j)*B(j)

+ R(i)*M(j)*B(j) - R(i)*A(j)*M(j) ));

end

end

end

end

% En busca de la Ruta Critica de cada proyecto aleatorio.



% 42 son las posibles Rutas, las duracion de cada proyeco

% se calcula a traves de la esperanza a traves de cada una

% de las rutas posibles. finalmente la Ruta Critca sera la de

% esperanza mayor, es decir, la que haya sumado el valor mayor

RC=zeros(tR(2),42);

for i=1:tR(2)

RC(i,1) = x(i,1) + x(i,3) + x(i,7) + x(i,8) + x(i,16) + x(i,17) + x(i,19) + x(i,21);


RC(i,3) = x(i,1) + x(i,3) + x(i,7) + x(i,8) + x(i,16) + x(i,18) + x(i,22) + x(i,23)

+ x(i,24);




+ x(i,24);




+ x(i,24);




+ x(i,24);

RC(i,13) = x(i,1) + x(i,6) + x(i,15) + x(i,16) + x(i,17) + x(i,19) + x(i,21);


RC(i,15) = x(i,1) + x(i,6) + x(i,15) + x(i,16) + x(i,18) + x(i,22) + x(i,23)

+ x(i,24);




+ x(i,24);




+ x(i,24);




+ x(i,24);




+ x(i,24);






+ x(i,24);




+ x(i,24);




+ x(i,24);




+ x(i,24);




+ x(i,24);

Esperanza(i) = max(RC(i,:));

end

% Dias para los cuales es necesario estimar la probabilidad de termino

% del proyecto es T, en este caso T = 39 dias

%T = 39;

% Calculo de la Probabilidad de termino del Proyecto

PreProb = 0;

for i=1:tR(2)

if (Esperanza(i) <= T)

Uni(i) = 1;

elseif (Esperanza(i) > T)

Uni(i) = 0;

end

PreProb = PreProb + Uni(i);

end

Prob = (PreProb/tR(2))*100;

disp(’La Probabilidad de Terminar el Proyecto en ’);

disp(T); disp(’[Dias] es de ’); disp(Prob); disp(’porciento’);

4.2. Comentarios

Es claro que al generar mas proyectos aumenta el grado de confiabilidad de la probabilidad a calcular.Cuando se generan 10 proyectos, la probabilidad es cercana al 80 %, mientras que con 1000, la pro-



babilidad se reduce a alrededor de 67 %. Si se prueba con 5000, el programa se demora mucho mas ydando un resultado muy parecido que al generar 1000. Por lo que se concluye que 1000 muestras sonuna cantidad razonable para el calculo de probabilidad de termino del proyecto.

VPZ-PTG LATEX


informe tarea n 2 investigaci¶on de operaciones...

Documents