Programación dinámica

Programación dinámica

9.1 Definición

El método de programación dinámica sirve para resolver problemas combinando las soluciones de subproblemas. Normalmente es usada para resolver problemas de optimización.

La programación dinámica es una técnica que se usa para determinar si hay posibilidades de modificar las decisiones durante cierto período.

La programación dinámica se ocupa también de los problemas en los que el tiempo no es una variable significativa; ejemplo: Hay que tomar una decisión en la distribución de una cantidad fija de recursos entre cierto número de usos alternativos. Este problema puede resolverse descomponiéndolo en varias etapas y de ese modo la decisión final se maneja como si fuera una serie de decisiones dependientes en el transcurso del tiempo

En contraste con la programación lineal no presenta una formulación matemática estándar, en la solución de los problemas; sino que se trata de un enfoque de tipo general para su solución y las ecuaciones especificadas, que se usan, se deben desarrollar para que representen cada situación individual de cada problema

9.2 estructura de la programación dinámica

Todo problema de programación dinámica debe reunir los siguientes pasos:

a.- El problema se divide en etapas, con una política de decisión requerida en cada etapa.

b.- Cada etapa tiene algunos estados asociados.

c.- Cada problema debe tener una variable de estado; la cual nos dice todo lo que necesitamos saber sobre el sistema, a fin de tomar decisiones.

d.- Cada estado debe contar con una decisión, la cual es una oportunidad para cambiar las variables de estado en una forma probabilística.

e.- El efecto de una decisión a cada etapa es transformar el estado corriente (actual), en uno asociado con la próxima etapa.

f.- Dado el estado corriente, la política óptima para las etapas que quedan es independiente a la política adoptada en etapas anteriores. En este caso “etapa anterior”, significa tiempo.

g.- El procesamiento empieza por escoger la decisión (política), óptima para cada estado de la ultima etapa.

h.- Debe tener una función RECURSIVA; la cual identifica la decisión (política), óptima para cada estado cuando quedan n-etapas, dada la decisión óptima para cada estado cuando quedan n-1 etapas.

i.- Usando esta relación recursiva, el método de solución mueve hacia atrás etapa por etapa, determinando la decisión óptima en cada etapa hasta llegar a la etapa final.

9.3 aplicación d la programación dinámica para resolver problemas

Hay dos condiciones que se deben cumplir antes de comenzar a pensar en una solución a un problema de optimización usando programación dinámica.

Sub-estructura óptima: Un problema tiene sub-estructura óptima cuando la solución óptima a un problema se puede componer a

...