programacion dinamica

APUNTE DE INVESTIGACIÓN OPERATIVA

PROGRAMACIÓN DINÁMICA

Definición:
La programación dinámica, es una técnica que permite la resolución de problemas que tratan de alcanzar determinados fines, a través, de una serie de etapas o fases compuestas de diversos estados, de estos es necesario hacer una elección, de tal manera que se alcance la máxima efectividad global, también podemos decir,que es una técnica matemática que trata con la optimización de procesos de decisión. La optimización es por fases en vez de simultánea.

Elementos que intervienen en un problema de programación dinámica:

1.- ETAPAS:
Se pueden definir como cada uno de los pasos que se deben seguir para llegar al objetivo. Las representamos por líneas discontinuas.

2.- ESTADOS:
Son las diversascondiciones posibles en la que el sistema podría estar en esa etapa del problema. Se representan por círculos.

3.- POLÍTICA:
Es cualquiera de los caminos que llevan de la primera a la última etapa.

4.- SUBPOLÍTICA:
Es un subconjunto de la política.









Ejemplo:


















Luego, por el Teorema de Optimidad, podemos afirmar lo siguiente:

"Una políticaóptima sólo puede estar formada por subpolíticas óptimas".

Este teorema es suceptible de ser demostrado:

Una subpolítica de la política óptima, si esa subpolítica no es óptima, existe otra mejor, la cual completada con el resto de la política, permitirá mejorar esta, por lo tanto, nos daría otra política óptima y por lo señalado, sería contrario a la hipótesis.

BELLMAN enunció el Teorema dela Optimidad, bajo la forma de un principio general:
" Una política es óptima, sí en un período dado, cualesquiera que sean las decisiones que se tomen, constituyan una política óptima teniendo en cuenta los resultados de las decisiones precedentes".

CARACTERÍSTICAS DE LAS APLICACIONES DE PROGRAMACIÓN DINÁMICA
1 El problema se puede dividir en etapas; cada etapa requiere una decisión. Enmuchos problemas de programación dinámica, la etapa es la cantidad de tiempo que pasa desde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.

2 Cada etapa tiene un número de estados asociados con ella. Por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima.

3 La decisión tomada en cualquier etapa indica cómo setransforma el estado en la etapa actual en el estado en la siguiente etapa. En muchos problemas, una decisión no determina con certeza el estado de la siguiente etapa; en lugar de ello, la decisión actual sólo determina la distribución de probabilidad del estado en la etapa siguiente.

4 Dado el estado actual, la decisión óptima para cada una de las etapas restantes no debe depender de estadospreviamente alcanzados o de decisiones previamente tomadas. A esta idea se le conoce como principio de optimalidad.

5 Si los estados del problema se han clasificado en uno de N etapas, debe haber una fórmula recursiva que relacione el costo o beneficio durante las etapas n, n+1,…, N con el costo o beneficio de las etapas n+1, n+2,…,N. En esencia, la fórmula recursiva formaliza el procedimiento demarcha atrás.


Ejercicios
PREGUNTA N° 1

Los datos corresponden a los costos que le significa a una empresa enviar unidades de cierto artículo de una ciudad a otra. Se pide determinar la ruta óptima de envío desde la ciudad A a la ciudad N.

B C D E F G H I J K L M N
A 7 65 B 8 7 6 E 6 5 - H 6 7 5 K 6
C 7 6 5 F 6 - 7 I 7 6 7 L 7
D 8 7 6 G 7 6 6 J 6 7 8 M 8
PREGUNTA N° 2

Una...