Ejemplo de Programacion Dinamica Probabilistica
5
EJEMPLO DE PROGRAMACION DINAMICA PROBABILISTICA Una estudiante universitaria tiene 7 días para preparar los exámenes finales de 4 cursos y quiere asignar el tiempo que tiene para estudiar de la manera más eficiente posible. Necesita por lo menos un día para cada curso y quiere concentrarse solo en un curso cada día, por lo que quiere asignar 1, 2, 3 ó 4 días a cada curso. Como hace poco tomó un curso de investigación de operaciones, ha decidido aplicar programación dinámica para hacer estas asignaciones que maximicen el total de puntos obtenidos en los 4 cursos. Estima que las distintas opciones de días de estudio redituarán puntos de calificación según la siguiente tabla: PUNTOS DE CALIFICACION ESTIMADOS # DE DIAS CURSO 1 CURSO 2 CURSO 3 CURSO 4 1 3 5 2 6 2 5 5 4 6 3 6 6 7 7 4 7 9 8 9
Transcript of Ejemplo de Programacion Dinamica Probabilistica
EJEMPLO DE PROGRAMACION DINAMICA PROBABILISTICA
Una estudiante universitaria tiene 7 días para preparar los exámenes finales de 4 cursos y quiere asignar el tiempo que tiene para estudiar de la manera más eficiente posible. Necesita por lo menos un día para cada curso y quiere concentrarse solo en un curso cada día, por lo que quiere asignar 1, 2, 3 ó 4 días a cada curso. Como hace poco tomó un curso de investigación de operaciones, ha decidido aplicar programación dinámica para hacer estas asignaciones que maximicen el total de puntos obtenidos en los 4 cursos.
Estima que las distintas opciones de días de estudio redituarán puntos de calificación según la siguiente tabla:
PUNTOS DE CALIFICACION ESTIMADOS# DE DIAS CURSO 1 CURSO 2 CURSO 3 CURSO 4
1 3 5 2 62 5 5 4 63 6 6 7 74 7 9 8 9
n=4
S4 F4*S4 X4*1 6 12 7 23 9 34 9 4
n=3
X3 = 1 f3(3,1) = P3(1) + f4*(3-1) =2+6 = 8
X3 = 1 f3(4,1) = P3(1) + f4*(4-1) = 2+7 = 9
X3 = 2 f3(4,2) = P3(2) + f4*(4-2) = 4+6 = 10
X3 = 1 f3(5,1) = P3(1) + f4*(5-1) = 2+9 = 11
X3 = 2 f3(5,2) = P3(2) + f4*(5-2) = 4+7 = 11
X3 = 3 f3(5,3) = P3(3) + f4*(5-3) = 7+6 = 13
X3 = 1 f3(6,1) = P3(1) + f4*(6-1) = 2+9 = 11
X3 = 2 f3(6,2) = P3(2) + f4*(6-2) = 4+9 = 13
X3 = 3 f3(6,3) = P3(3) + f4*(6-3) = 7+7 = 14
X3 = 4 f3(6,4) = P3(4) + f4*(6-4) = 8+6 = 14
X3 1 2 3 4 F3*(S3) X3*S3
1 8 8 12 9 10 10 23 11 11 13 13 24 11 13 14 14 14 3,4
n=2
X2 = 1 f2(3,1) = P2(1) + f3*(3-1) =5+8 = 13
X2 = 1 f2(4,1) = P2(1) + f2*(4-1) = 5+10 = 15
X2 = 2 f2(4,2) = P2(2) + f2*(4-2) = 5+8 = 13
X2 = 1 f2(5,1) = P2(1) + f3*(5-1) = 5+13 = 18
X2 = 2 f2(5,2) = P2(2) + f3*(5-2) = 5+10 = 15
X2 = 3 f2(5,3) = P2(3) + f3*(5-3) = 6+8 = 14
X2 = 1 f2(6,1) = P2(1) + f3*(6-1) = 5+14 = 19
X2 = 2 f2(6,2) = P2(2) + f3*(6-2) = 5+13 = 18
X2 = 3 f2(6,3) = P2(3) + f3*(6-3) = 6+10 = 16
X2 = 4 f2(6,4) = P2(4) + f3*(6-4) = 9+8 = 17
X2 1 2 3 4 F3*(S3) X3*S21 13 13 12 15 13 15 13 18 15 14 18 14 19 18 16 17 19 1
X1 = 1 f2(7,1) = P1(1) + f2*(7-1) = 3+19 = 22
X2 = 2 f2(7,2) = P1(2) + f2*(7-2) = 5+18 = 23
X3 = 3 f2(7,3) = P1(3) + f2*(7-3) = 6+15 = 21
X4 = 4 f2(7,4) = P1(4) + f2*(7-4) = 7+13 = 20
X2 1 2 3 4 F3*(S3) X3*S2
7 22 23 21 20 23 2
SOLUCION:
2→1→3→1 =5+5+7+6=23
