Investigacion De Operaciones

PROGRAMACIÓN DINÁMICA

La programación dinámica determina la solución óptima de un problema n variables descomponiéndola en n etapas, con cada etapa incluyendo un sub problema de una sola variable. La principal contribución de la probabilidad dinámica es el principio de optimalidad el cual establece que una política óptima consiste de sub-políticas óptimas, un marco de referencia para descomponer el problema en etapas.

Características de los problemas de programación dinámica

Las características de la programación dinámica se emplean para formular e identificar la estructura de los problemas de este tipo.

A continuación se presentarán éstas característica básicas que distinguen a los problemas de programación dinámica

1. el problema se puede dividir en etapas que requiere una política de decisión en cada una de ellas. En muchos problemas de programación dinámica, la etapa es la cantidad de tiempo que pasan desde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.

2. Cada etapa tiene un estado asociado a ella, por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima.

3. El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con la siguiente etapa (tal vez de acuerdo a una distribución de probabilidad).

4. El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo, es decir, una receta para las decisiones de la política óptima en cada etapa para cada uno de los estados posibles.

5. Dado el estado actual, una política óptima para la etapa restante es independiente de la política adoptada en etapas anterior. (Este es el principio de optimalidad para la programación dinámica). En general el problema en los problemas de programación dinámica, el conocimiento del estado actual del sistema expresa toda la información sobre su comportamiento anterior, y esta información es necesaria para determinar la política óptima de ahí en adelante.

6. El procedimiento de solución se inicia al encontrar la política óptima para la última etapa. La política óptima para la última etapa prescribe la política óptima de decisión para cada estado posible en esa etapa.

7. Se dispone de una relación recursiva que indica la política óptima para la etapa dada la política óptima para la etapa (n + 1).

A pesar de esta característica, los problemas que pueden ser atacados con la programación dinámica tienen otras dos propiedades adicionales.

• Sólo un número reducido de variables se debe conocer en cualquier etapa con el fin con el fin de describir al problema. En efecto, los problemas de la programación dinámica se caracterizan por la dependencia de los resultados derivados de decisiones sobre un número reducido de variables.

• El resultado de una decisión en cualquier etapa altera los valores numéricos de un número reducido de variables relevantes al problema. La decisión actual ni incrementa ni decrementa el número de factores sobre los cuales depende el resultado. Así, para la siguiente decisión en la secuencia, el número mismo de variable se considera.

Para que un problema pueda ser resuelto con la técnica de programación dinámica, debe cumplir con ciertas características:

• Naturaleza secuencial de las decisiones: El problema puede ser dividido en etapas.

• Cada etapa tiene un número de estados asociados a ella.

• La decisión óptima de cada etapa depende solo del estado actual y no de las decisiones anteriores.

• La decisión tomada en una etapa determina cual será el estado de la etapa siguiente.

En síntesis, la política óptima desde un estado S de la etapa K a la etapa final ésta constituida por una decisión que transforma S en un estado S0 de la etapa k + 1 y por la política óptima desde el estado S0 hasta la etapa final.

Para resolver un problema de programación dinámica debemos al menos realizar:

Identificación de etapas, variables de estados y variables de decisión:

• Cada etapa debe tener asociada una o más decisiones (problema de optimización), cuya dependencia de las decisiones anteriores está dada exclusivamente por las variables de estado.

• Cada estado debe contener toda la información relevante para la toma de decisión asociada a la etapa.

• Las variables de decisión son aquellas sobre las cuales debemos definir su valor de modo de optimizar el beneficio acumulado y modificar el estado de la próxima etapa.

Descripción de ecuaciones de recurrencia:

• Nos deben indicar como se acumula la función de beneficios a optimizar y como varían las funciones de estado de una etapa a otra.

Resolución:

Debemos optimizar cada sub-problema por etapas en función de los resultados de la resolución del sub-problema siguiente. Notar que para que las recurrencias estén bien definidas requerimos de condiciones de borde.

Respecto a lo último, la resolución tiene la particularidad de realizarse desde atrás hacia adelante, siguiendo los siguientes pasos:

1. Partir en la etapa n, haciendo k = n.

2. Colocar todos los valores factibles de las variables de estado y las de decisión en la etapa k.

3. Calcular HK para cada valor del par ordenado (Yk, Xk) calculado anteriormente.

4. Elegir para cada Yk el valor óptimo que debe tener Xk y el correspondiente valor de HK.

5. Si K = 1 parar, sino disminuir K en 1 y volver a (2).

6. Hacer K = 1

7. Dado que Y*K se conoce, buscar el valor óptimo de Xk correspondiente a Y*K y guardarlo en X*K, a partir del cual determinar Y*K + 1

8. Si k = n parar, sino aumentar k en 1 y volver a (7).

Luego, los valores de x*k, con k = 1; : : : ; n corresponde a las decisiones óptimas a tomar en cada etapa y f*1 (y*1) corresponde al valor del beneficio en la solución óptima.

EL PROBLEMA DE ASIGNACIÓN DE RECURSOS

El propietario de 3 tiendas ha comprado 5 cestas de cerezas, para satisfacer la demanda en las diferentes tiendas. El propietario desea determinar la forma de distribuir los canastos, de manera de maximizar el beneficio total. Los retornos (utilidades) en función del número de canastos distribuidos (se asume vendidos) en las 3 tiendas están dados en la siguiente tabla:

Canastas

Identifiquemos los elementos del modelo de programación dinámica:

Etapas: Cada etapa corresponde a una de las 3 tiendas,

...