Programación dinamica
Páginas: 8 (1814 palabras)
Publicado: 14 de enero de 2010
Programación dinámica
Concepto
Método de optimización para resolver problemas que involucran decisiones secuenciales. Una decisión tomada en una etapa afectará los estados del problema y las posibles decisiones en la etapa siguiente.
Las dificultades que presentaba la resolución de determinados problemas de gestión de stocks determinaron el nacimiento, a comienzos de la década de loscincuenta, de la programación dinámica. R. Bellman descubrió el principio de optimización de esta gama de problemas, a los que denominó programas dinámicos. Los problemas de Programación dinámica son problemas de decisión por etapas o de carácter secuencial; problemas en los que la variable tiempo es relevante, y en los que las decisiones tomadas en un estado o fase del sistema condicionan lasdecisiones a tomar en los siguientes.
No existe un formato estándar, sino más bien se trata de una forma general de resolver este tipo de problemas.
La programación dinámica se suele utilizar en problemas de optimización, donde una solución está formada por una serie de decisiones. Igual que la técnica divide y vencerás, resuelve el problema original combinando las soluciones para subproblemas máspequeños; Sin embargo, la programación dinámica no utiliza recursividad, si no que almacena los resultados de los subproblemas en una tabla, calculando primero las soluciones para los problemas pequeños.
Con esto se pretende evitar la repetición de cálculos para problemas más pequeños.
♣La Programación Dinámica (PD) intenta mejorar la eficiencia del cálculo de problemas descomponiéndolos ensubproblemas de menor tamaño, más fáciles de resolver.
♣La PD está basada en el principio de Optimalidad de Bellman:
“Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones que resuelve un problema, también debe ser óptima respecto al subproblema resuelto.”
♣La PD resuelve el problema en etapas (problemas multietápicos).
♣En cada etapa interviene una variable deoptimización.
♣Los cálculos de las diferentes etapas se enlazan de forma recursiva para generar la solución óptima.
♣La PD se aplica en problemas como calendarización (scheduling), edición de cadenas, almacenamiento e inventario.
Una serie de estados agrupados en etapas, de cada etapa a la siguiente ocurre una transformación la cual depende de una decisión.
Los posibles estados en cadaetapa, si son finitos o enumerables, los puedo representar como Nodos.
Las transformaciones que me llevan a cada estado posible en la siguiente etapa a partir de cada estado actual los puedo representar como arcos.
El problema se puede dividir en etapas, con una decisión xt que se debe tomar en cada etapa.
Existe un cierto número de estados “s” asociados a cada etapa “t”, y la decisión realizadaen una etapa afecta el estado del sistema en la siguiente etapa.
Iniciando con la última etapa, un sub-problema de una etapa puede ser resuelto dando las decisiones óptimas para cada estado en la última etapa.
Pueden encontrarse relaciones recursivas que permiten la solución de subproblemas de una etapa que sean empleadas para encontrar las soluciones a mayores y mayores subproblemas hastaque el último subproblema es el problema original.
Dado el estado actual, la decisión óptima para las etapas restantes, es independiente de las decisiones previamente tomadas. Por ello, sólo depende del estado actual y no de cómo llegamos a él.
La programación dinámica, PD, intenta encontrar una solución de un problema en forma secuencial.
La PD no es un algoritmo de solución única, sino unmétodo para resolver un problema grande y único mediante resolver una secuencia de problemas más pequeños.
Ejemplo de introducción
La Fábrica de tortillas Mi Tierra, es una pequeña compañía ubicada en San Antonio, Tx,, en ella se fabrican diversos productos de maíz y de trigo.
La Burrito Bell desea adquirir 200 cajas, con 1000 tortillas cada una, en cada uno de los próximos 7 meses a un...
Concepto
Método de optimización para resolver problemas que involucran decisiones secuenciales. Una decisión tomada en una etapa afectará los estados del problema y las posibles decisiones en la etapa siguiente.
Las dificultades que presentaba la resolución de determinados problemas de gestión de stocks determinaron el nacimiento, a comienzos de la década de loscincuenta, de la programación dinámica. R. Bellman descubrió el principio de optimización de esta gama de problemas, a los que denominó programas dinámicos. Los problemas de Programación dinámica son problemas de decisión por etapas o de carácter secuencial; problemas en los que la variable tiempo es relevante, y en los que las decisiones tomadas en un estado o fase del sistema condicionan lasdecisiones a tomar en los siguientes.
No existe un formato estándar, sino más bien se trata de una forma general de resolver este tipo de problemas.
La programación dinámica se suele utilizar en problemas de optimización, donde una solución está formada por una serie de decisiones. Igual que la técnica divide y vencerás, resuelve el problema original combinando las soluciones para subproblemas máspequeños; Sin embargo, la programación dinámica no utiliza recursividad, si no que almacena los resultados de los subproblemas en una tabla, calculando primero las soluciones para los problemas pequeños.
Con esto se pretende evitar la repetición de cálculos para problemas más pequeños.
♣La Programación Dinámica (PD) intenta mejorar la eficiencia del cálculo de problemas descomponiéndolos ensubproblemas de menor tamaño, más fáciles de resolver.
♣La PD está basada en el principio de Optimalidad de Bellman:
“Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones que resuelve un problema, también debe ser óptima respecto al subproblema resuelto.”
♣La PD resuelve el problema en etapas (problemas multietápicos).
♣En cada etapa interviene una variable deoptimización.
♣Los cálculos de las diferentes etapas se enlazan de forma recursiva para generar la solución óptima.
♣La PD se aplica en problemas como calendarización (scheduling), edición de cadenas, almacenamiento e inventario.
Una serie de estados agrupados en etapas, de cada etapa a la siguiente ocurre una transformación la cual depende de una decisión.
Los posibles estados en cadaetapa, si son finitos o enumerables, los puedo representar como Nodos.
Las transformaciones que me llevan a cada estado posible en la siguiente etapa a partir de cada estado actual los puedo representar como arcos.
El problema se puede dividir en etapas, con una decisión xt que se debe tomar en cada etapa.
Existe un cierto número de estados “s” asociados a cada etapa “t”, y la decisión realizadaen una etapa afecta el estado del sistema en la siguiente etapa.
Iniciando con la última etapa, un sub-problema de una etapa puede ser resuelto dando las decisiones óptimas para cada estado en la última etapa.
Pueden encontrarse relaciones recursivas que permiten la solución de subproblemas de una etapa que sean empleadas para encontrar las soluciones a mayores y mayores subproblemas hastaque el último subproblema es el problema original.
Dado el estado actual, la decisión óptima para las etapas restantes, es independiente de las decisiones previamente tomadas. Por ello, sólo depende del estado actual y no de cómo llegamos a él.
La programación dinámica, PD, intenta encontrar una solución de un problema en forma secuencial.
La PD no es un algoritmo de solución única, sino unmétodo para resolver un problema grande y único mediante resolver una secuencia de problemas más pequeños.
Ejemplo de introducción
La Fábrica de tortillas Mi Tierra, es una pequeña compañía ubicada en San Antonio, Tx,, en ella se fabrican diversos productos de maíz y de trigo.
La Burrito Bell desea adquirir 200 cajas, con 1000 tortillas cada una, en cada uno de los próximos 7 meses a un...
Leer documento completo
Regístrate para leer el documento completo.