IO2 - Practico programacion dinamica
Enviado por Jose Ricardo Cuellar Justiniano • 10 de Mayo de 2020 • Trabajo • 3.296 Palabras (14 Páginas) • 208 Visitas
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
...