Programacion Dinamica

A continuación se muestra otra aplicación de programación dinámica.

Ejemplo 1.2

El distrito escolar high shoals es un distrito escolar urbano en el cual una considerable proporción de los estudiantes tiene serios problemas de lectura. Jane Smith, coordinadora curricular para las escuelas primarias o elementales de ese distrito ha logrado obtener fondos del departamento de educación paracontratar a 5 profesores especiales. Desea ubicarlos en las escuelas que han tenido las peores puntuaciones en lectura con el objeto de mejorar la capacidad general de lectura de los estudiantes. Sin embargo, no sabe a cuantos profesores debe ubicar para maximizar la efectividad del programa de lectura. Consultando con los directores y profesores de las escuelas elaboro una tabla qué muestra elaumento promedio del nivel de calificaciones de lectura (en meses escolares) que se experimentara en cada escuela al asignar diversos números de profesores a ellas.

  | Escuela |
Números maestros | A | B | C |
0 | 0 | 0 | 0 |
1 | 6 | 9 | 12 |
2 | 10 | 14 | 18 |
3 | 15 | 18 | 21 |
4 | 18 | 20 | 21 |
5 | 20 | 20 | 21 |

Tabla 1. Aumento promedio en el nivel de calificación (mesesescolares)

Al estudiar la tabla jane se dio cuenta que se requiere un numero entero de profesores en cada caso. Se da cuenta también que de que este requerimiento de numero entero excluye el uso de cualquier modelo matemático que tenga la consideración de divisibilidad. Así mismo se percata de que aun cuando podría enumerar todas las combinaciones posibles para este problema pequeño, esemétodo no sería útil para problemas mayores. Dado que está considerando hacer una solicitud de fondos para utilizar el mismo método de enseñanza en todo el distrito escolar, piensa que es necesario desarrollar un método analítico para asignar los profesores de lectura.

Solución.

* A primera vista parecería que el problema del distrito escolar High Shoals no se le puede aplicar la programacióndinámica. No existe una secuencia evidente de decisiones que deben tomarse ni existen tiempos para la asignación de profesores. Sin embargo, si consideramos que el problema consiste en asignar profesores a la escuela A, después a la escuela B y por último a la escuela C, se introduce una secuencia de decisiones. Esta secuencia nos permite abordar el problema con una estructura de PD. Estasecuencia se muestra a continuación en la tabla en la cual el orden de las escuelas carece de importancias siempre y cuando se siga alguna secuencia

* Ahora, si utilizamos un enfoque retroactivo haríamos que la etapa 1 fuera la asignación a la escuela C, que la etapa 2 fuera la asignación a la escuela B, y que la etapa 3 fuera la asignación a la escuela A.

* Entonces la decisión de cadaesta es el número de profesores que deben asignarse a la escuela. La variable de estado es el número de profesores disponibles para asignarles a la escuela. SI Xn es la variable de estado y Dn es la decisión en la etapa.

Entonces.

Xn= Numero de maestros disponibles para la asignación.
Dn= Números de profesores asignados.

Xn-1=Xn- Dn (Relación recurrente)

* En cualquier etapa elrendimiento será la suma del rendimiento inmediato asociado con Dn y Xn mas el rendimiento optimo asociado con Xn-1=Xn – Dn de una tabla anterior.

* Utilizando este método en la etapa 1 utilizaremos una tabla de decisión como las que se analizaron en el problema anterior, después utilizando los resultados de esta tabla inicial de decisión se pasa a la etapa 2.

* Esta tabla es diferentede la etapa 1, por que las decisiones aparecerán como encabezados de las columnas. En el cuerpo de la tabla se muestra la suma del rendimiento inmediato y el rendimiento óptimo asociado con x2 - d2 en la intersección del renglón x2 y la columna d2. Por ejemplo, si x2 =3 y d2=2, entonces x2-d=1 y se obtiene el valor de 14+12=26 en esta celda de la tabla. Este valor proviene de la tabla 1 y es la...