Programación dinámica

INTRODUCCIÓN.

La Programación Dinámica fue desarrollada por Richard Bellman y G B Dantzing. Sus importantes contribuciones sobre esta técnica cuantitativa de toma de decisiones se publicaron en 1957 en un libro del primer autor denominado “Dynamic Programming” (Princeton University Press. Princeton, New Jersey).

Inicialmente a la PD se le denominó programación lineal estocástica ó problemas de programación lineal con incertidumbre. La programación dinámica (PD) determina la solución óptima de un problema de n variables descomponiéndola en n etapas, con cada etapa incluyendo un subproblema de una sola variable. La principal contribución de la PD es el principio de optimalidad, el cual establece que una política óptima consiste de subpolíticas óptimas, un marco de referencia para descomponer el problema en etapas.

La programación dinámica es una técnica que se puede aplicar para resolver muchos problemas de optimización. La mayor parte de las veces, la programación dinámica obtiene soluciones con un avance en reversa, desde el final de un problema hacia el principio con lo que un problema grande y engorroso se convierte en una serie de problemas más pequeños y más tratables.

Así, la programación dinámica se puede definir como una técnica matemática útil que resuelve una serie de decisiones secuenciales, cada una de las cuales afecta las decisiones futuras. Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximiza la efectividad total. En contraste para el problema de programación dinámica, trata de un enfoque de tipo parcial para la solución de problemas y las ecuaciones específicas que se usan se deben desarrollar para que represente cada situación individual.

PROGRAMACIÓN DINÁMICA.

1.1 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 estas características básicas que distinguen a los problemas de programación dinámica.

El problema se puede dividir en etapas que requieren 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 pasa desde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.

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

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).

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.

Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores. (este es el principio de óptimalidad para la programación dinámica). En general en los problemas de PD, el conocimiento del estado actual del sistema expresa toda la información sobre su comportamiento anterior, y esta información es necesario para determinar la política óptima de ahí en adelante.

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.

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 PD tienen otras dos propiedades adicionales:

Sólo un número reducido de variables se debe conocer en cualquier etapa con el fin de describir al problema. En efecto, los problemas de la PD 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 mismo número de variables se considera (Hillier, 1991).

En un problema de PD una serie de decisiones se deben tomar en una secuencia dada. Cuando esto se cumple, una política óptima se debe perseguir. No importa cuáles fueron los estados y decisiones iniciales, las decisiones restantes constituirán una política óptima con respecto al estado resultante de la primera decisión.

1.2. EJEMPLOS DE MODELOS DE PROGRAMACIÓN DINÁMICA

El problema de la diligencia.

Un problema construido especialmente por el Profesor H M Wagner de la Universidad de Stanford para ilustrar las características e introducir la terminología de la PD es el problema de la diligencia.

Este problema se refiere a un vendedor mítico que tuvo que viajar hacia el oeste utilizando como medio de transporte una diligencia, a través de tierras hostiles, en el último cuarto del siglo XIX. Aun cuando su punto de partida y destino eran fijos, tenía un número considerable de opciones para elegir qué estados (o territorios que posteriormente se convirtieron en estados) recorrer en su ruta.

En la figura 1.1 se muestran las rutas posibles, en donde cada estado se representa por un bloque numerado.

Figura 1.1. Sistema de caminos para el problema de la diligencia.

De la ilustración se puede observar que el viaje se puede realizar en 4 etapas, partiendo del estado 1 hasta su destino en el estado 10:

Primera etapa: estados 1 y (2, 3, 4)

Segunda etapa: estados (2, 3,4) y (5, 6, 7)

Tercera etapa: estados (5,6,7) y (8, 9)

Cuarta etapa: estado (8,9) y10

Puesto que se ofrecían seguros de vida a los pasajeros de las diligencias, este vendedor no quiso dejar pasar la oportunidad y se propuso determinar la ruta más segura. Como el costo de cada póliza se basaba en una evaluación cuidadosa de la seguridad de ese recorrido, la ruta más segura debía ser aquella con la póliza de seguro de vida más barata. El costo de la póliza estándar para el viaje en diligencia del estado i al j se muestra en figura 1.1 como una etiqueta en los caminos (flechas) para ir de un estado a otro.

Así la pregunta central es: ¿cuál ruta (conjunto de caminos) minimiza el costo total de la póliza?, para contestar esta pregunta es necesario hacer notar que, el procedimiento poco inteligente de seleccionar el camino más barato ofrecido en cada etapa sucesiva no necesariamente conduce a una decisión óptima global.

La PD parte de una pequeña porción del problema y encuentra la solución óptima para ese problema más pequeño. Entonces gradualmente agranda el problema, hallando la solución óptima en curso a partir de la anterior, hasta que se resuelve por completo el problema original.

A continuación se explican los detalles involucrados en la implementación de esta filosofía general.

La idea es calcular el costo mínimo (acumulativo) de la póliza de seguros entre los dos estados de cada etapa y después utilizar esos costos como datos de entrada para la etapa inmediata siguiente.

CÁLCULOS PARA LA ETAPA 1

Considerando los estados asociados con la etapa 1, se puede ver que los estados 2, 3 y 4 están conectados cada uno con el estado inicial 1 por una sola flecha como se puede apreciar en la figura 1.2. Por consiguiente, para la etapa 1 se tiene

Costo mínimo al estado 2 = 2 (desde el estado 1)

Costo mínimo al estado 3 = 4 (desde el estado 1)

Costo mínimo al estado 4 = 3 (desde el estado 1)

CÁLCULOS PARA LA ETAPA 2

Después se avanza a la etapa 2 para determinar los costos mínimos

(Acumulativos) para los estados 5, 6 y 7 como se aprecia en la figura 1.3.

Considerando primero al estado 5, se ve que existen tres alternativas; a saber (2,5), (3,5), (4,5).

Esta información, junto con los costos mínimos de los estados 2, 3 y 4 (figura 1.4) determinan el costo mínimo (acumulativo) para el estado 5 como:

De forma similar para el estado 6 (figura 1.5), se tiene:

Finalmente para el estado 7 (figura 1.6), se tiene:

CÁLCULOS PARA LA ETAPA 3

Para los cálculos se toman los datos de la figura 1.7

CÁLCULOS PARA LA ETAPA 4

Para los cálculos se toman los datos de la figura 1.8

Resumen de cálculos para las diferentes etapas

El costo mínimo total desde el estado 1 al estado 10 es de 11.

El estado 10 se puede alcanzar desde los estados 8 y 9.

Si se elige el estado 9, este proviene de haber elegido el estado 6, el cual a su vez de haber elegido el estado 4 y finalmente el estado 1.

Es decir la ruta óptima es: 1, 4, 6, 9,10

Si se elige el estado 8, este proviene de haber elegido el estado 5, el cual a su vez de haber elegido el estado 4 o el 3.

Si se elige el estado 4, la ruta óptima es: 1, 4, 5, 8,10.

Si se elige el estado 3, la ruta óptima es: 1, 3, 5, 8,10

Por lo tanto existen 3 rutas óptimas a elegir ya que la tres implican el costo mínimo total que es 11.

Formalización de los cálculos de programación dinámica

Se mostrará ahora la forma en la cual se pueden expresar matemáticamente los cálculos recursivos de la PD.

Con la condición inicial . La ecuación indica que las distancias más cortas en la etapa i se debe expresar en función del siguiente nodo . En la terminología de la programación dinámica, a x_i se le llama estado del sistema en la etapa i.

De hecho se considera que el estado del sistema en la etapa i es la información que enlaza, conecta o vincula las etapas, de tal modo que se pueda tomar las decisiones para las etapas restantes sin volver a examinar cómo se llegó a las decisiones de las etapas anteriores. La definición correcta de estado permite considerar por separado cada estado, y garantiza que la solución sea factible para todos los estados.

1.3. PROGRAMACIÓN DINÁMICA DETERMINISTA

En este caso se profundiza sobre el enfoque de programación dinámica en los problemas determinísticos, en donde el estado en la siguiente etapa está completamente determinado por el estado y la política de decisión de la etapa actual. El caso probabilístico en el que existe una distribución de probabilidad para el valor posible del siguiente estado este se analizara más adelante.

Aplicaciones de programación dinámica determinística

Algunas de las aplicaciones de programación dinámica determinística son:

Modelo de Volumen-Carga “Mochila”

Modelo del tamaño de la fuerza de trabajo

Modelo de reposición de equipos

Modelo de inversión

Modelos de inventarios

A continuación se presentarán algunas de estas aplicaciones, cada una de las cuales muestra una nueva idea en la puesta en práctica de la PD.

A medida que se presente cada aplicación, es importante prestar atención a los tres elementos básicos de un modelo de PD:

Definición de las etapas

Definición de las políticas o alternativas

Definición de los estados para cada etapa

De los tres elementos, la definición del estado por lo común es la más sutil.

Las aplicaciones que se presentan a continuación muestran que la definición de estado varía dependiendo de la situación que se está modelando.

1.4. PROGRAMACIÓN DINÁMICA PROBABILISTA

La programación dinámica probabilística (PDP) es una técnica matemáticamente útil para la toma de decisiones interrelacionadas, se presenta cuando el estado en la siguiente etapa no está determinado por completo por el estado y la política de decisión de la etapa actual. En su lugar existe una distribución de probabilidad para determinar cuál será el siguiente estado. Sin embargo, esta distribución de probabilidad si queda bien determinada por el estado y la política de decisión en la etapa actual. Por consiguiente la diferencia entre la programación dinámica probabilística y la programación dinámica determinística (PDD) está en que los estados y los retornos o retribuciones en cada etapa son probabilísticos. La programación dinámica probabilística se origina en especial en el tratamiento de modelos estocásticos de inventarios y en los procesos markovianos de decisión.

Algunas de las aplicaciones de programación dinámica probabilística son:

Un juego aleatorio

Problema de inversión

Maximización del evento de lograr una meta.

1.5. USO DE PROGRAMAS DE COMPUTACIÓN

Adicional al programa SOLVER, incluido en EXCEL-2000 de MIcrosoft (cuya explicación didáctica del funcionamiento del programa Solver (445 kb), se incluye en este documento que puede ser bajado por Usted), se incorporan otros programas que operan bajo sistema WIndows 98/ME/2000/XP, debiendo disponer de una computadora actualizada con procesador Pentium II y superiores, memoria mínima de 256 kb y capacidad de disco de 50

MB y los cuales pueden ser bajados a continuación:

El programa WinQSB (3.9 Mb), cuya propiedad intelectual es del Dr. Yih-Long Chang y es aplicable a todos los problemas de Investigación de Operaciones. Para conocer sus usos y aplicaciones, se incorpora el MANUAL DE USO del WINQSB.

El programa PrgLin, cuya propiedad es de la Universidad de Lisboa (Portugal), el cual se aplica para soluciones gráficas de problemas de dos dimensiones.

El programa InvOp (361 kb), desarrollado por la Universidad del Cuyo en Argentina, se aplica para la solución de problemas relacionados con transporte y redes.

El programa Lingo, propiedad de Lindo Systems Inc (USA), que dado su gran tamaño (18.9 Mb), se recomienda que Usted lo recupere directamente de la página Web del propietario de dicha tecnología http:// www.lindo.com

CONCLUSIÓN

La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro.

Además, nos permite resolver casos prácticos que suceden en la vida diaria como son los casos del viajero, producción y de carga o de mochila. Se clasifican en determinanticos y probabilísticos.

REFERENCIAS BIBLIOGRAFICAS

Domínguez, A. (Noviembre de 2000). Programación dinámica. http://www.slideshare.net/Alexdfar/programacin-dinmica-5688350

Hillier, F. S. (1991). Introducción a la Investagación de Operaciones (3 ed.). México: McGraw-Hill.

Taha, H. A. (2004). Investigación de Operaciones (7 ed.). México: PEARSON EDUCATION.

Goic F., Marcel. Programación Dinámica. Facultad de Ciencias Físicas y Matemáticas-Departamento de Ingeniería Industrial: Universidad de Chile

...