IO2 - Practico programacion dinamica

Problema 2:

[pic 1]

[pic 2]

Para toda [pic 3]=1,2,3,…,25.

[pic 4]longitud de la ruta más corta de ir del nodo [pic 5]al nodo 25.

Ecuación recursiva:

[pic 6]

Etapa 8, estado 25.

f(25)=0

Etapa 7, estado 22, 23 y 24.

f(22) = min { c22,25 + f(25) } =  15 la decisión optima es (22,25)

f(23) = min { c23,25 + f(25) } =  8 la decisión optima es (23,25)

f(24) = min { c24,25 + f(25) } =  20 la decisión optima es (24,25)

Etapa 6, estado 18, 19, 20 y 21.

f(18) = min { c18,22 + f(22) } =  21 la decisión optima es (18,22)

f(19) = min { c19,23 + f(23) } =  15 la decisión optima es (19,23)

f(20) = min { c20,23 + f(23) } =  15 la decisión optima es (20,23)

f(21) = min { c21,24 + f(24) } =  30 la decisión optima es (21,24)

Etapa 5, estado 14, 15, 16 y 17

f(14) = min { c14,18 + f(18) } =  26 la decisión optima es (14,18)

f(15) = min { c15,19 + f(19) } =  21 la decisión optima es (15,19)

f(16) = min { c16,20 + f(20) } =  21 la decisión optima es (16,20)

f(17) = min { c17,20 + f(20), c17,21 + f(21)  } = 35   la decisión optima es (17,20)

Etapa 4, estado 10, 11, 12 y 13

f(10) = min { c10,14 + f(14) } =  31 la decisión optima es (10,14)

f(11) = min { c11,15 + f(15) } =  26 la decisión optima es (11,15)

f(12) = min { c12,16 + f(16) } =  26 la decisión optima es (12,16)

f(13) = min { c13,16 + f(16) } =  27 la decisión optima es (13,16)

Etapa 3, estado 5, 6, 7, 8 y 9

f(5) = min { c5,10 + f(10) } = 39 la decisión optima es (5,10)

f(6) = min { c6,11 + f(11) } = 34 la decisión optima es (6,11)

f(7) = min { c7,12 + f(12) } =  34 la decisión optima es (7,12)

f(8) = min { c8,13 + f(13) } =  35 la decisión optima es (8,13)

f(9) = min { c9,17 + f(17) } =  52 la decisión optima es (9,17)

Etapa 2, estado 2, 3 y 4

f(2) = min { c2,5 + f(5) } =  54 la decisión optima es (2,5)

f(3) = min { c3,6 + f(6), c3,7 + f(7) } =40 la decisión optima es (3,7)

f(4) = min { c4,8 + f(8), c4,9 + f(9) } =45 la decisión optima es (4,8)

Etapa 1, estado 1

f(1) = min { c1,2 + f(2), c1,3 + f(3), c1,4 + f(4) } = 49 la decisión optima es (1,3)

Interpretación de la solución:

La ruta más corta de ir al nodo 1 al nodo 25; nodo(estados)

1-3-7-12-16-20-23-25 con un costo total de 49

9+6+8+5+6+7+8 = 49

Problema 4:

[pic 7]

[pic 8]

f(E,0) = max {0} = 0 la decisión optima es asignar 0 máquinas al producto E

f(E,1) = max {0,10} = 10 la decisión optima es asignar 1 máquinas al producto E

f(E,2) = max {0,10,9} = 10 la decisión optima es asignar 1 máquinas al producto E

f(E,3) = max {0,10,9,30} = 30 la decisión optima es asignar 3 máquinas al producto E

f(E,4) = max {0,10,9,30,16} = 30 la decisión optima es asignar 3 máquinas al producto E

f(E,5) = max {0,10,9,30,16,50} = 50 la decisión optima es asignar 5 máquinas al producto E

f(E,6) = max {0,10,9,30,16,50,13} = 50 la decisión optima es asignar 5 máquinas al producto E

f(D,0) = max {0 + f(E,0)} = 0 la decisión optima es asignar 0 máquinas al producto D

f(D,1) = max {0 + f(E,1), 8 + f(E,0)} = max { 0+10, 8 +0 } = 10 la decisión optima es asignar 0 máquinas al producto D

f(D,2) = max {0 + f(E,2), 8 + f(E,1), 14 + f(E,0)} = max { 0+10, 8 +10,14+0 } = 18 la decisión optima es asignar 1 máquinas al producto D

f(D,3) = max {0 + f(E,3), 8 + f(E,2), 14 + f(E,1), 24 + f(E,0)} = max { 0+30, 8 +10,14+10,24+0 } = 30 la decisión optima es asignar 0 máquinas al producto D

f(D,4) = max {0 + f(E,4), 8 + f(E,3), 14 + f(E,2), 24 + f(E,1), 35 + f(E,0)} = max { 0+30, 8 +30,14+10,24+10,35+0 } = 38 la decisión optima es asignar 1 máquinas al producto D

f(D,5) = max {0 + f(E,5), 8 + f(E,4), 14 + f(E,3), 24 + f(E,2), 35 + f(E,1), 43 + f(E,0)} = max { 0+50, 8 +30,14+30,24+10,35+10,43+0 } = 50 la decisión optima es asignar 0 máquinas al producto D

f(D,6) = max {0 + f(E,6), 8 + f(E,5), 14 + f(E,4), 24 + f(E,3), 35 + f(E,2), 43 + f(E,1), 21 + f(E,0)} = max { 0+50, 8 +50,14+30,24+30,35+10,43+10,21+0 } = 58 la decisión optima es asignar 1 máquinas al producto D

f(C,0) = max {0 + f(D,0)} = 0 la decisión optima es asignar 0 máquinas al producto C

f(C,1) = max {0 + f(D,1), 5 + f(D,0)} = max { 0+10, 5 +0 } = 10 la decisión optima es asignar 0 máquinas al producto C

f(C,2) = max {0 + f(D,2), 5 + f(D,1), 12 + f(D,0)} = max { 0+18, 5 +10,12+0 } = 18 la decisión optima es asignar 0 máquinas al producto C

f(C,3) = max {0 + f(D,3), 5 + f(D,2), 12 + f(D,1), 22 + f(D,0)} = max { 0+30, 5 +18,12+10, 22+0 } = 30 la decisión optima es asignar 0 máquinas al producto C

f(C,4) = max {0 + f(D,4), 5 + f(D,3), 12 + f(D,2), 22 + f(D,1), 34 + f(D,0)} = max { 0+38, 5 +30,12+18, 22+10, 34+0 } = 38 la decisión optima es asignar 0 máquinas al producto C

f(C,5) = max {0 + f(D,5), 5 + f(D,4), 12 + f(D,3), 22 + f(D,2), 34 + f(D,1), 48 + f(D,0)} = max { 0+50, 5 +38,12+30, 22+18, 34+10, 48+0 } = 50 la decisión optima es asignar 0 máquinas al producto C

f(C,6) = max {0 + f(D,6), 5 + f(D,5), 12 + f(D,4), 22 + f(D,3), 34 + f(D,2), 48 + f(D,1), 11 + f(D,0)} = max { 0+58, 5 +50, 12+38, 22+30, 34+18, 48+10, 11+0 } = 58 la decisión optima es asignar 0 máquinas al producto C.

O

58 la decisión optima es asignar 5 máquinas al producto C

f(B,0) = max {0 + f(C,0)} = 0 la decisión optima es asignar 0 máquinas al producto B

f(B,1) = max {0 + f(C,1), 17 + f(C,0)} = max { 0+10, 17 +0 } = 17 la decisión optima es asignar 1 máquinas al producto B

f(B,2) = max {0 + f(C,2), 17 + f(C,1), 30 + f(C,0)} = max { 0+18, 17 +10, 30+0 } = 30 la decisión optima es asignar 2 máquinas al producto B

f(B,3) = max {0 + f(C,3), 17 + f(C,2), 30 + f(C,1), 49 + f(C,0)} = max { 0+30, 17 +18, 30+10, 49+0 } = 49 la decisión optima es asignar 3 máquinas al producto B

f(B,4) = max {0 + f(C,4), 17 + f(C,3), 30 + f(C,2), 49 + f(C,1), 64 + f(C,0)} = max { 0+38, 17+30, 30+18, 49+10, 64+0 } = 64 la decisión optima es asignar 4 máquinas al producto B

f(B,5) = max {0 + f(C,5), 17 + f(C,4), 30 + f(C,3), 49 + f(C,2), 64 + f(C,1), 76 + f(C,0)} = max { 0+50, 17+38, 30+30, 49+18, 64+10, 76+0 } = 76 la decisión optima es asignar 5 máquinas al producto B

f(B,6) = max {0 + f(C,6), 17 + f(C,5), 30 + f(C,4), 49 + f(C,3), 64 + f(C,2), 76 + f(C,1), 52 + f(C,0)} = max { 0+58, 17+50, 30+38, 49+30, 64+18, 76+10, 52+0 } = 86 la decisión optima es asignar 5 máquinas al producto B

f(A,0) = max {0 + f(B,0)} = 0 la decisión optima es asignar 0 máquinas al producto A

f(A,1) = max {0 + f(B,1), 12 + f(B,0)} = max { 0+17, 12 +0 } = 17 la decisión optima es asignar 0 máquinas al producto B

f(A,2) = max {0 + f(B,2), 12 + f(B,1), 17 + f(B,0)} = max { 0+30, 12+17, 17+0 } = 30 la decisión optima es asignar 0 máquinas al producto B

f(A,3) = max {0 + f(B,3), 12 + f(B,2), 17 + f(B,1), 25 + f(B,0)} = max { 0+49, 12+30, 17+17, 25+0 } = 49 la decisión optima es asignar 0 máquinas al producto B

f(A,4) = max {0 + f(B,4), 12 + f(B,3), 17 + f(B,2), 25 + f(B,1), 34 + f(B,0)} = max { 0+64, 12+49, 17+30, 25+17, 34+0 } = 64 la decisión optima es asignar 0 máquinas al producto B

f(A,5) = max {0 + f(B,5), 12 + f(B,4), 17 + f(B,3), 25 + f(B,2), 34 + f(B,1), 45 + f(B,0)} = max { 0+76, 12+64, 17+49, 25+30, 34+17, 45+0 } = 76 la decisión optima es asignar 0 máquinas al producto B

O

76 la decisión optima es asignar 1 máquinas al producto B

f(A,6) = max {0 + f(B,6), 12 + f(B,5), 17 + f(B,4), 25 + f(B,3), 34 + f(B,2), 45 + f(B,1), 15 + f(B,0)} = max { 0+86, 12+76, 17+64, 25+49, 34+30, 45+17, 15+0 } = 88 la decisión optima es asignar 1 máquinas al producto B

Interpretación de la solución:

Asignar 1 maquina al producto A

Asignar 5 máquinas al producto B

Asignar 0 maquina al producto C

Asignar 0 maquina al producto D

Asignar 0 maquina al producto E

Con esta asignación se obtiene una utilidad total 88.

...