Programacion Dinamica

UNIDAD 4 PROGRAMACION DINAMICA

“...Programación dinámica apareció en la década de 1950, creada por Richard Belirnan
y G.G. Dantzig, quienes fueron los que más contribuyeron con sus estudios al
desarrollo de esta técnica cuantitativa para resolver un sinnúmero de problemas, que
anteriormente necesitaban de difíciles procesos para ello...”
Apareció en la década de 1950, creada por RichardBellman y G.G. Dantzig, quienes
fueron los que más contribuyeron con sus estudios al desarrollo de esta técnica
cuantitativa.
En un principio se definía como programación lineal estocástida, o bien
problemas de programación lineal relacionados con la incertidumbre. En la actualidad
se ha desarrollado como una técnica cuantitativa para resolver un sinnúmero de
problemas, que anteriormentenecesitaban de difíciles procesos para ello.
Es una técnica matemática que permite encontrar la solución de una serie de
decisiones en secuencia, y se debe tomar una secuencia de decisiones, con cada una
de ellas, que afecte las decisiones futuras. Este paso es muy importante, ya que
difícilmente se encontrará una situación de operación en la cual la toma de una decisión
no se extienda alfuturo.
La programación dinámica es una técnica de descomposición para resolver
problemas de decisión con múltiples etapas; descompone el problema de decisión con
ni variables, en n problemas de decisión de una variable.
La programación dinámica está basada en el principio de optimalidad de Bellman:
"Una política (conjunto de decisiones) óptima tiene la propiedad de que
cualquiera que sea elestado inicial y las decisiones mismas, las decisiones
restantes constituyen una política óptima con respecto al estado resultante de la
primera decisión".
La programación dinámica se ocupa también de los problemas en los que el
tiempo no es una variable significativa.
En la programación dinámica sólo hay que conocer una pequeña cantidad de
datos en cada etapa, a fin de describir el problema.Realmente los problemas de programación dinámica se caracterizan por la
dependencia del resultado de las decisiones de una pequeña cantidad de variables.
Además, en cualquier etapa el resultado de una decisión altera los valores númericos
de la pequeña cantidad de variables relacionadas con el problema. La decisión real noaumenta ni disminuye el número de factores de los que dependen losresultados.
Por lo anterior, habrá que tomar en cuenta el mismo número de variables para la,
siguiente decisión de la serie.
Estructura de la programación dinámica
La programación dinámica es un algoritmo que permite resolver problemas de
planeación de carácter combinatorio, esto es: cuando existen gran número de
posibilidades interrelacionadas y sujetas a restricciones. Dicho de otro modo, laprogramación dinámica permite resolver problemas que se caracterizan por etapas
definidas con variables de estado. Estas variables de estado definen la condición del
sistema para cada una de las etapas consideradas.
Tratándose de un problema de tipo secuencial, las etapas serían los periodos
sucesivos considerados; el programa de cada periodo quedaría definido por los valores
que tomenlas variables de estado
Como puede verse, la programación dinámica puede resolver problemas de
programación de etapas múltiples, en donde las decisiones en una etapa se convierten
en una parte de las condiciones que determinan las mejores alternativas en las etapas
sucesivas. Lo anterior es lo que ha llevado a llamar a estos métodos, programación
dinámica
Teóricamente, no existe límite en elnúmero de variables de estado y tampoco
existe la limitación de que sean discretas.
1
Desde el punto de vista práctico, si las variables son continuas la mecanización
de los cálculos se vuelve muy compleja. Por lo tanto se consideran únicamente los
casos de variables discretas; se entiende que se podrán manejar variables continuas
tomando una serie grande pero finita de valores...