Investigación Operaciones UBA-Guayana: Programación Dinamica

Programación Dinámica

En muchos casos las decisiones del pasado afectan los escenarios del futuro. En estos casos se pueden tomar 2 opciones: asumir que el efecto temporal o dinámico es poco relevante y solo considerar modelos de un periodo (PPL) o considerar el efecto dinámico dentro del modelo (programación dinámica).

La programación dinámica nace después de la segunda guerra mundial, donde se presentó la necesidad de resolver procesos de decisión en múltiples etapas. Está técnica usa funciones recursivas y un principio de optimalidad, desarrollado por Bellman, para resolver este tipo de problemas.

El Modelo de Programación Dinámica

A continuación se muestra la formulación backward:

Describamos cada elemento:

1. Etapas: k

Particiones del problema en los cuales se pueden tomar decisiones que no dependan de estados anteriores, sino sólo del estado actual. Ej.: días, meses, años, etapas de producción en una línea, etc. Para su programación debe existir una etapa final (n).

2. Variables de Estado: Yk

Variables que caracterizan la situación en la que se encuentra el sistema en una etapa dada. Estás variables dan la independencia a la etapa actual de las etapas anteriores, por lo que deben existir tantas variables de estado como las que permitan establecer en qué condiciones comienza (o finaliza) una etapa para su posterior optimización.

3. Variables de Decisión: Xk

Decisiones cuantificables cuyos valores se intenta determinar por medio de la resolución del modelo. Su valor determina el valor de las variables de estado de las etapas futuras.

4. Espacio de Soluciones Factibles: Ak(yk)

Espacio de soluciones factibles de las variables de decisión. Estos valores pueden depender de las variables de estado, es decir, para valores distintos de las variables de estado puede haber distintos espacios de soluciones factibles.

5. Ecuaciones de Recurrencia:

Función de Recursión: fk

Ecuación que indica cómo se acumula la función de valor desde la etapa k hasta la etapa final.

Función de Transformación: yk+1 = Tk(yk; xk)

Ecuación que indican como se relaciona las variables de estado y decisión de una etapa con la variable de estado de la etapa posterior.

6. Función de Valor o Beneficio: (Función Objetivo) Hk

Criterio de comparación entre distintos valores de las variables de estado. Es el objetivo a alcanzar por la resolución del problema en cada etapa.

7. Condiciones de Borde: y1 = M y fn+1(yn+1) = F

Limitaciones que deben imponerse al problema, corresponden a condiciones iniciales o finales que deben cumplirse.

Veamos algunas características de este modelo importantes de ser destacadas

1. Esta formulación tiene el concepto de recursividad, que es la generalización del concepto dinámico del modelo. Esto se observa en que fk(yk) es definido en función de las variables (yk, xk) del periodo k y en función de sí misma en el periodo siguiente (fk+1(yk+1)).

2. Las condiciones de borde permiten obtener la solución explícita del modelo, ya que la etapa n requiere conocer fn+1, y la etapa 1 requiere desparametrizar la solución, asignando un valor conocido a y1.

3. La función Hk corresponde a la representación de la función.0 objetivo en la etapa k hasta la etapa n. Ella debería construirse de manera de ir dando cuenta del valor de la función objetivo en cada etapa.

4. La función de transformación Tk(yk; xk) establece la relación entre las variables de Estado yk e yk+1 para 2 periodos consecutivos. La variable de estado de la etapa siguiente (yk+1) es expresada como una función de la variable de estado (yk) y de la variable de decisión (xk) de la etapa actual.

5. El conjunto Ak representa al conjunto de restricciones asociadas a la variable de decisión de la etapa k. Estas restricciones sólo deben incluir a las variables de decisión de la etapa k y no deben incluir a las de otras etapas.

6. La solución del subproblema de optimización en la etapa k, es una solución Paramétrica en la variable de estado yk, ya que f es en función de ella. Este subproblema de optimización tiene como variable de decisión a xk, y el resultado es leído como: “para la etapa k, xk es la mejor decisión para un yk dado, y fk(yk) es el mejor valor de la función objetivo desde la etapa k hasta la etapa n”.

7. Se denomina política ´optima de la etapa k; k + 1; … ; n para un determinado estado inicial en la etapa k. La política ´optima global, esto es, desde la etapa 1, constituye la solución ´optima del problema, puesto que en la etapa 1 se tiene sólo un estado inicial factible.

ECUCACION RECURSIVA DE RETROCESO

La diferencia principal entre los métodos de avance y de retroceso ocurre en la forma como definimos el estado del sistema.

Este método de cálculo se conoce como procedimiento de avance porque los cálculos avanzan de la primera hasta la última etapa. Sin embargo, cuando el lector estudie la mayoría de las obras dedicadas a la programación dinámica, advertirá que la ecuación recursiva se construye de manera que los cálculos comienzan en la última etapa y después “regresan” hacia la etapa 1. Este método recibe el nombre de procedimiento de retroceso.

Los cálculos se efectúan en el orden

Este método de cálculo de conoce como procedimiento de avance porque los cálculos avanzan de la primera a la última etapa. Sin embargo, cuando el lector estudie la mayoría de las obras dedicadas a la programación dinámica advertirá que la ecuación recursiva se construye de manera que los cálculos comienzan en la última etapa y después “regresan” hacia la etapa 1. Este método recibe el nombre de

Procedimiento de retroceso

La diferencia principal entre los métodos de avance y de retroceso ocurre en la forma en que definimos el estado del sistema. Para ser específicos, volveremos a considerar el ejemplo del presupuesto de capital. Para el procedimiento de retroceso, definimos los estados yj como:

y1 = monto de capital asignado a las etapas 1, 2 y 3
y2 = monto de capital asignado a las etapas 2 y 3
y3 = monto de capital asignado a la etapa 3

Para apreciar la diferencia entre la definición de los estados xj y yj en los métodos de avance y retroceso, las dos definiciones se resumen en forma gráfica La ecuación recursiva de retroceso se escribe, por tanto como: