1. INTRODUCCIÓNEl presente trabajo comprende la exposición de la teoría y algunos ejemplos de

Programación Dinámica (P.D.). La P.D. está comprendida dentro de un conjunto

de técnicas matemáticas que a su vez forman parte de un área más amplia,

conocida como Investigación de Operaciones. Esta última puede definirse como

una ciencia interdisciplinaria que tiene por objeto la búsqueda de estrategias que

permitan obtener resultados óptimos en el desarrollo de actividades por parte de

sistemas hombre-máquina (estos sistemas pueden estar formados exclusivamente

por hombres, por máquinas o por una combinación de los dos). Como se verá más

adelante, los problemas propios de la P.D. son aquellos que pueden ser divididos

en subproblemas, los cuales, a su vez, tienen una estructura igual al problema

original (en este sentido podría decirse que tienen una estructura “fractal”). Para

este propósito, el método consiste en dividir el problema en etapas, resolver la

primera de estas, utilizar esta solución para resolver la etapa siguiente y continuar

así sucesivamente hasta encontrar la solución del problema en su totalidad. Son

características esenciales de la P.D. por un lado, la versatilidad con respecto a la

amplia gama de problemas que puede atacar y, por otra parte, que la P.D. se

limita a aportar un esquema de solución (ya mencionado arriba) dejando al ingenio

de quien resuelva el problema la construcción del modelo matemático para realizar

la optimización de cada caso en particular. En este sentido el trabajo en P.D. está

más en relación directa con la labor del matemático que del ingeniero, pues este

último no necesita comprender la base teórica en la cual descansa el

procedimiento, sino únicamente conocer el algoritmo propio del problema

particular que pretende resolver. Para lograr la comprensión de la técnica el

trabajo se ha estructurado sobre ejemplos que ilustran la versatilidad de la P.D.,

con este fin se presentan soluciones de problemas propios del trabajo en

Programación Lineal, Programación Lineal Entera, Programación No Lineal etc. El

objetivo es más presentar la potencia de la P.D. que proponerla como la panacea

de los métodos de Investigación de Operaciones, pues también se verá que

aunque funciona, en ocasiones la técnica puede resultar impráctica al momento de

resolver problemas de cierta envergadura.

2. PROGRAMACION DINAMICA

2.1 Características De Los Problemas De Programación Dinámica

La programación dinámica es una técnica matemática que se utiliza para la solución de problemas matemáticos seleccionados, en los cuales se toma una serie de decisiones en forma secuencial.

Proporciona un procedimiento sistemático para encontrar la combinación de decisiones que maximice la efectividad total, al descomponer el problema en etapas, las que pueden ser completadas por una o más formas (estados), y enlazando cada etapa a través de cálculos recursivos.

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.

La programación dinámica parte de una pequeña porción del problema y llega a la solución óptima para esa pequeña parte del problema, entonces gradualmente se agranda el problema hallando la solución óptima en curso a partir de la anterior. Este proceso se repite hasta obtener la solución óptima del problema original.

El problema de la diligencia es un prototipo literal de los problemas de programación dinámica. Por tanto una manera de reconocer una situación que se puede formular como un problema de programación dinámica es poder identificar una estructura análoga a la del problema de la diligencia.

Características básicas.

1.- El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas.

2.- Cada etapa tiene cierto número de estados asociados con su inicio. Los estados son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema.

3.- El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente etapa.

4.- El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo.

5.- 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 optimalidad para programación dinámica.

6.- El procedimiento de solución se inicia al encontrar la política óptima para la última etapa.

7.- Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa n+1. La forma precisa de relación recursiva difiere de un problema a otro de programación dinámica, pero usaremos una notación análoga a la siguiente:

N = número de etapas.

n = etiqueta para la etapa actual ( n = 1,2,...,N)

sn = estado actual para la etapa n

xn = variable de decisión para la etapa n

xn* = valor óptimo de xn (dado sn)

fn(sn,xn) = contribución a la función objetivo de las etapas n, n+1,...,N, si el sistema se encuentra en el estado sn en la etapa n, la decisión inmediata es xn y en adelante se toman decisiones óptimas. fn*(sn) = fn(sn,xn*) La relación recursiva siempre tendrá la forma: fn*(sn) = mín fn(sn,xn) ó fn*(sn) = max fn(sn,xn)

8.- Cuando se usa esta relación recursiva, el procedimiento de solución comienza al final y se mueve hacia atrás etapa por etapa, hasta que encuentra la política óptima desde la etapa inicial.

Procedimiento de solución.

1. Se construye una relación recursiva que identifica la política óptima para cada estado en la etapa n, dada la solución óptima para cada estado en la etapa n + l.

2. Se encuentra la decisión óptima en la última etapa de acuerdo a la política de decisión establecida. Comúnmente la solución de esta última etapa es trivial, es decir, sin ningún método establecido, tomando en cuenta solamente la "contribución" de la última etapa.

3. La idea básica detrás de la relación recursiva es trabajar "hacia atrás", preguntándose en cada etapa: ¿qué efecto total tendría en el problema si tomo una decisión particular en esta etapa y actúo óptimamente en todas las etapas siguientes?

Si se resolviera el problema "hacia adelante", es decir, de la primera etapa hacia la sería necesario realizar una enumeración exhaustiva de todas las

alternativas, que resolviéndolo "hacia atrás" reducimos el número de alternativas a analizar, simplificando la solución del problema. Cuando se llega a la etapa inicial se encuentra la solución óptima.

2.2 Ejemplos De Modelos De Programación Dinámica

1. El problema de la diligencia.

Fue elaborado especialmente para ilustrar las características e introducir la terminología de la programación dinámica. Trata sobre un cazafortunas mítico de Missouri que decide ir al oeste a unirse a la fiebre del oro en California a mediados del siglo XIX. Tiene que hacer el viaje en diligencia a través de territorios sin ley donde existen serios peligros de ser atacado por merodeadores. Aun cuando su punto de partida y su destino son fijos, tiene muchas opciones en cuanto a qué estados (o territorios que más tarde se convirtieron en estados) debe elegir como puntos intermedios. En la figura 1 se muestran las rutas posibles, en donde cada estado está representado por un círculo con una letra y la dirección del viaje es siempre de izquierda a derecha en el diagrama. Como se puede observar, se requieren cuatro etapas (jornadas en diligencia) para viajar desde su punto de partida en el estado^! (Missouri) a su destino en el estado/ (California).

Este cazafortunas es un hombre prudente preocupado por su seguridad. Después de reflexionar un poco se le ocurrió una manera bastante ingeniosa para determinar la ruta más segura.

Se ofrecen pólizas de seguros de vida a los pasajeros. Como el costo de la póliza para cualquier jornada en la diligencia está basado en una evaluación cuidadosa de la seguridad del recorrido, la ruta más segura debe ser la que tiene el menor costo total de la póliza del seguro.

El costo de la póliza estándar para el viaje en diligencia, del estado i alestado/, que se a;- nota por CIJ, es

Estos costos se muestran en la figura 1

La atención se centrará sobre la pregunta: ¿cuál es la ruta que minimiza el costo total de la póliza?

Solución del problema

Observe primero que el procedimiento poco inteligente de elegir la ruta más barata en caca etapa sucesiva no conduce a una decisión óptima global. Al seguir esta estrategia se obtiene la ruta A -> B -> F -> I ->/, con un costo total de 13. Pero un pequeño sacrificio en una etapa puede permitir mayores ahorros más adelante. Por ejemplo, A —> D -> F es en total más barato que A —> B —> F.

Un enfoque posible para resolver este problema es el de prueba y error.1 Sin embargo, el número de rutas posibles es grande (18) y el cálculo del costo total para cada ruta no es una tarea atractiva.

Figura 1. Problema de la diligencia

2. El problema de las monedas.

Para el problema de las monedas con programación dinámica se necesita crear un algoritmo que permita a una máquina expendedora devolver el cambio mediante el menor número de monedas posible. Mediante la programación dinámica se solucionará el caso en el que el número de monedas de cada tipo es ilimitado. En el problema de las monedas mediante el algoritmo voraz el que el número de monedas es ilimitado.

3. El problema de la mochila.

Existen multitud de variantes del problema de la mochila. En este caso, trataremos con una variante del problema que se denomina Problema de la Mochila 0-1.

Supóngase que se tiene n objetos distintos y una mochila. Cada uno de los objetos tiene asociado un peso positivo wi y un valor positivo vi para i=1, 2, …, n. La mochila puede llevar un peso que no sobrepase la cantidad W. Teniendo en cuenta estos datos, el objetivo del problema es llenar la mochila de tal forma que se maximice el valor de los objetos transportados en ella. Hay que tener en cuenta que la suma de los pesos de los objetos seleccionados no debe superar la capacidad máxima W de la mochila. Por lo tanto, para obtener la solución deseada, se debe decidir para cada uno de los objetos, si se introduce o no en la mochila. Cada objeto tiene asociado una variable xi que toma el valor 1 si el objeto se mete en la mochila y 0 en caso contrario. Cualquier objeto se puede introducir en la mochila si hay espacio para él, pero lo que no se puede hacer es transportar en ella una fracción o parte de un objeto. A este tipo de problemas en los que los objetos no pueden ser fraccionados se les llama Problemas de la Mochila 0-1 o Entera.

Matemáticamente el problema se puede formular como se muestra a continuación:

Sn Sn +1

fn (Sn,Xn) fn+1* (Sn+1*)

Contribución al objetivo

Cn (Xn)

2.3 Programación Dinámica Determinista

Los problemas determinísticos de programación dinámica son aquellos en los cuales el estado asociado en la etapa siguiente está totalmente determinado por el estado y la política de decisión de la etapa actual. La siguiente figura describe el funcionamiento de la programación dinámica determinística.

Figura 2 El funcionamiento de la programación

Los problemas de programación dinámica determinística son aquéllos en los que el estado en la etapa siguiente queda completamente determinado por el estado y la política en la etapa actual.

Una manera de catalogar los problemas de programación dinámica determinística es por la forma de la función objetivo. Por ejemplo, el objetivo podría ser minimizar la suma de contribuciones de las etapas individuales, o bien minimizar un producto de tales términos y así sucesivamente. En un problema de programación dinámica, las temporadas deben ser las etapas.

2.4 Programación Dinámica Probabilista

La programación dinámica probabilística difiere de la programación dinámica determinística en que el estado de la etapa siguiente no queda completamente determinado por el estado y la decisión de la política en el estado actual. En lugar de ello existe una distribución de probabilidad para lo que será el estado siguiente. Sin embargo, esta distribución de probabilidad todavía está completamente determinada por el estado y la decisión de la política del estado actual. En la siguiente figura 3 se describe diagramáticamente la estructura básica que resulta para la programación dinámica probabilística, en donde N denota el número de estados posibles en la etapa n+1.

En lo que se refiere a este diagrama, sea S el número de estados posibles en la etapa n + 1 y etiquete estos estados en el lado derecho por 1,2,..., S. El sistema cambia al estado i con probabilidad p¡ (i = 1,2,..., S) dados el estado sn y la decisión xn en la etapa n. Si el sistema cambia al estado z, Q es la contribución de la etapa n a la función objetivo.

Cuando se expande la figura 3 para incluir todos los estados y las decisiones posibles en todas las etapas, se obtiene lo que con frecuencia se conoce como un árbol de decisión. Si este árbol de decisión no es muy grande, proporciona una forma útil de resumir estas posibilidades.

Debido a la estructura probabilística, la relación entre fn(sn, XH ) y f,*+i(sn+i) necesariamente es más complicada que para el caso determinístico. La forma exacta de esta relación dependerá de la forma global de la función objetivo.

Para ilustrar esto, suponga que el objetivo es minimizar la suma esperada de las contribuciones de las etapas individuales. En este caso, /„ (sn, xn) representa la suma esperada mínima de la etapa n en adelante, dado que en la etapa w, el estado es sn y la política de decisión es xn.

En consecuencia

Con

Donde la minimización se toma sobre todos los valores factibles de x n + l.

Figura 3. Estructura básica para programación dinámica probabilística

Cuando se desarrolla de esta forma para incluir todos los estados y decisiones posibles en todas las etapas, a veces recibe el nombre de árbol de decisión. Si el árbol de decisión no es demasiado grande, proporciona una manera útil de resumir las diversas posibilidades que pueden ocurrir.