Programación dinamica

PROGRAMACIÓN DINÁMICA

1.- ¿QUÉ ES LA PROGRAMACIÓN DINÁMICA?

Es una técnica matemática utilizada para hacer una secuencia de decisiones interrelacionadas. Provee un procedimiento sistemático para determinar la combinación de decisiones, que optimiza el resultado del problema.

Es una manera ordenada de analizar todos los posibles cursos de acción y seleccionar el mejor.

2.- ¿PARA QUE SIRVE Y CUANDO SE UTILIZA?.

Sirve para seleccionar la mejor alternativa para lograr un objetivo preestablecido.

Se utiliza cuando existen muchos posibles cursos de acción para solucionar un problema, y cuando se tiene que tomar una secuencia de decisiones interrelacionadas.

3.- DEFINICIONES.

ETAPA: Cada punto del problema donde una decisión debe ser hecha.

ESTADO: Información que describe al problema en cada etapa, conceptualmente las variables de estado enlazan a las etapas en un problema de programación dinámica.

POLÍTICA: Una regla para tomar decisiones la cual, a cualquier etapa, permite una secuencia factible de decisiones. Una política transforma el estado de una etapa dada en un estado asociado con la siguiente etapa.

POLÍTICA ÓPTIMA: Una política que optimiza el valor de un criterio objetivo o función de retorna. Comenzando en un estado dado de cualquier etapa, la política óptima depende solamente de ese estado y no de cómo se llego a el. En otras palabras, de acuerdo con el principio de optimalidad, la decisión óptima en cualquier etapa no es de ninguna forma dependiente de la historian previa del sistema.

4.- NOMENCLATURA DE PROGRAMACIÓN DINÁMICA

n = Número de la etapa.

S = Etapa.

Xn = Variable de decisión en la etapa “n”, o destina inmediato en la etapa “n”.

Cij = Costo, valor o utilidad, de pasar del estado “i” al “j”.

fn (S, Xn ) = Valor de la mejor política para las etapas restantes dados (S y Xn) (función objetivo).

Xn* = Valor de Xn que optimiza fn (S, Xn).

Fn*(S) = Fn (S, Xn*) = mín. / máx. {fn (S, Xn)}

Xn Xn

Fn* (S) = máx. / mín. [Cs Xn * f*n+1 (Xn)] donde “*” {operador que puede ser (*), (/), (+), (-). }.

El objetivo de programación dinámica es encontrar Fi*(S) y la correspondiente política.

5.- CARACTERÍSTICAS DE LA PROGRAMACIÓN DINÁMICA:

a) El problema se divide en etapas y cada etapa requiere de una política de decisión.

b) Cada etapa tiene estados asociados a ella.

c) El efecto de la política de decisión, es relacionar el estado de la etapa correspondiente de las políticas que se adopten en estados o etapas anteriores.

d) La política óptima, para las etapas restantes, dado un estado es independiente de las políticas que se adopten en estados o etapas anteriores.

e) El procedimiento comienza en el ultimo estado.

f) La relación recursiva que da la política óptima para cada estado es:

Fn* (S) = mín. / máx. [Cs Xn * f*n+1 (Xn)] donde * [ (*) (/) (+) (-)]

g) El procedimiento de solución se mueve desde atrás encontrando la

Política óptima para cada estado, hasta llegar a la etapa inicial.

EJEMPLO 1: RUTA MÍNIMA

7 6

6 6 4

Fuente 3

...