• Author / Uploaded
• Angel Castrejon

• Categories
• Programación dinámica
• Toma de decisiones
• Programación lineal
• Programación de computadoras
• Dinámica (Mecánica)

Citation preview

Introducción La solución óptima de ciertos problemas que se nos plantean ha sido fuente de diversos estudiosos matemáticos, como es el caso de Richard Bellman quien invento la programación dinámica en 1953, con la finalidad de

optimizar

problemas complejos que pueden ser desglosados, es decir, descomponiéndolos en sub problemas de menor tamaño y por consiguiente más fáciles de calcular. Generando así la solución más factible. Pero basta de preámbulos, a continuación detallaremos lo que es la programación dinámica desde su definición, diferencias con la programación lineal y los pasos a seguir para obtener la solución correcta del problema a desarrollar.

Programación Dinámica La programación dinámica consiste en una técnica que permite determinar de manera eficiente las decisiones que optimizan el comportamiento de un sistema que evoluciona a lo largo de una serie de etapas. En otras palabras, trata de encontrar la secuencia de decisiones que optimiza el comportamiento de un proceso poliétapico. La naturaleza del razonamiento que se debe realizar en programación dinámica es muy diferente al de la programación lineal. En programación lineal, intenta describir una determinada situación en términos de un modelo matemático determinado; una vez conocida la naturaleza de las variables de decisión, y expresadas la función objetivo y las restricciones en función de esas variables, la resolución del modelo puede confiarse, sin mayores problemas, a un programa informático. La programación dinámica no admite una resolución sistemática de este tipo; mas que un modelo concreto, es una estrategia de resolución común a muchas situaciones en principio diferentes que se ha de modelizar. En contrapartida, las simplificaciones que en ocasiones deben realizarse en programación lineal para poder resolver el modelo no son necesarias en programación dinámica, que admite gran variedad de relaciones entre variables.

Características y metodología Vamos ahora

enumerar las características que constituyen el método de la

programación dinámica: i.

Cada problema debe dividirse en etapas, cada una de las cuales requiere de una política de decisión, que se determinara conforme a la función objetivo.

ii.

Cada etapa se divide a su vez en un cierto número de estados asociados a ella, donde cada uno de estos representa una posibilidad de llevar a cabo la etapa.

iii.

En cada etapa habrá una política de decisión la cual deberá eslabonar la etapa actual con la siguiente del problema.

iv.

El método de programación dinámica deberá hallar una solución óptima para el problema total, la que es diferente de la solución óptima de etapa a etapa.

v.

El principio de optimalidad de Bellman dice: “cuando el problema se encuentra en un estado de una etapa dada, para salir de el, la decisión tomada debe constituir una política optima, independientemente de las decisiones hechas anteriormente”.

vi.

El problema se inicia por la ultima etapa y se mueve recursivamente, es decir, desde la ultima hasta la primera etapa, en la cual una vez determinada la decisión de la misma, el problema habrá sido resuelto.

Terminología Ahora daremos a conocer la terminología que se incluye en la programación dinámica para su mejor comprensión en el manejo de problemas. N = Numero total de etapa n = Etapa particular, donde n = 1, 2,…, N = Estado particular de la etapa n = Variable de decisión para la etapa n

= Valor optimo de

para cada

= Contribución acumulada de la función objetivo de la entapa n hasta la N.

, la cual deberá optimizarse. Hay problemas de programación dinámica de adición y de multiplicación, según la forma de obtener la función objetivo a partir de las variables de decisión en cada etapa. Son mas frecuente los casos de adición en la práctica, sin embargo, también aparecen situaciones de multiplicación como en aquellos casos de probabilidad conjunta.

Procesos poliétapicos de decisión Las situaciones susceptibles de ser representadas mediante programación dinámica

pueden

describirse

como

procesos

poliétapicos

de

decisión.

Seguidamente se exponen algunas características propias de este tipo de procesos.

“El problema puede dividirse en etapas. En casa una de esas etapas, debe tomarse una decisión. Tendremos la solución del problema cuando conozcamos la decisión óptima para cualquier situación que pueda presentarse en la evolución del sistema.”

La programación dinámica va asociada a situaciones de evolución de un sistema que va evolucionando a lo largo de varias etapas (de ahí su carácter dinámico). En la mayoría de las ocasiones, se tratara de representar el comportamiento de un sistema que evoluciona a lo largo del tiempo. En otros casos, se tratara de situaciones en las que las decisiones se toman de manera simultánea en el tiempo, pero en las que se evalúan las decisiones de manera secuencial. Nótese la diferencia con la programación lineal, en las que las decisiones se toman de manera simultanea (aunque

en

ocasiones representemos sistemas que

evolucionan a lo largo del tiempo, como los planes de producción). “Al comenzar cada una de las etapas, antes de tomar la decisión, el sistema podrá encontrarse en un estado de los varios posibles para esa etapa.” Esto significa que para cada etapa debe definirse un conjunto de estados. El estado debe sintetizar toda la información que debemos conocer de la evolución del sistema en las etapas anteriores. Los estados posibles para una etapa no tienen por que ser los mismos que para las etapas siguientes (aunque si deben definirse de la misma manera: los estados aseguran la continuidad entre una y otra etapa) y el número de estados puede ser finito o infinito.

“Una vez tomada la decisión en estado correspondiente, el sistema evolucionara hacia alguno de los estados posibles para la etapa siguiente”.

Por lo tanto, el comportamiento del sistema puede percibirse como una secuencia de decisiones y evoluciones. Dicha evolución puede ser conocida con certeza, una vez tomada la decisión (tendremos una situación de programación dinámica determinista), o bien el sistema puede evolucionar hacia diferentes estados, según una ley de probabilidad conocida (siendo entonces programación dinamiza aleatoria). “El objetivo de la programación dinámica es de encontrar cual es la política optima para cada una de las etapas de la evolución del sistema. La política para una determinada etapa es la decisión optima en cada uno de los posibles estados del sistema en dicha etapa”. Nótese que, para cada etapa, debe definirse una variable de decisión

. Si el

sistema tiene k estados en esa etapa, una política será un vector de k componentes, cuya componente -sima es el valor de la variable de decisión para el estado

en la etapa n.

La esencia de la estrategia de la programación dinámica se expresa mediante el principio de optimalidad: En un modelo de programación dinámica, la política óptima para las etapas que faltan hasta la finalización del proceso es independiente de las políticas adoptadas en las etapas anteriores. Esta propiedad es la esencia de la programación dinámica y tiene dos implicaciones importantes: En primer lugar, la evolución futura del sistema a partir de una determinada etapa depende exclusivamente del estado en que nos encontremos en esa etapa. Observe entonces que todo modelo de programación dinámica debe cumplir la propiedad markoviana: solo necesitamos conocer la situación del sistema en el momento presente para determinar su evolución en las etapas siguientes.

En segundo lugar, un modelo de programación dinámica debe resolverse hacia atrás. Esto admite dos formulaciones, en esencia equivalentes:  Si n son las etapas que ya ha realizado el sistema, conociendo la política óptima para la etapa n + 1, podremos encontrar la política óptima para la etapa n.  Si N son las etapas que faltan para que finalice la evolución del sistema, conociendo la política óptima cuando faltan N – 1 etapas, podremos encontrar la política óptima para cuando falten N etapas. Esta segunda formulación es especialmente útil para problemas de horizonte infinito. El procedimiento de solución se inicia al encontrar la política óptima para la última etapa. Esta propiedad tiene que ver con la solución hacia atrás de la que se hablaba en la propiedad anterior. Es conveniente que la solución para la última etapa sea trivial, esto es, que pueda encontrarse sin problemas la decisión optima para cada uno de los estados de la última etapa. Esto puede lograrse definiendo adecuadamente la función a optimizar. Es frecuente definir la función

a

optimizar en la etapa N como el valor de dicha función para las N ultimas etapas. Para encontrar la política optima para las etapas anteriores, es necesario definir una relación recursiva para la función a optimizar. Esto significa que, para la etapa n, la función a optimizar ha de poder expresarse en función de alguno de estos elementos:  El estado en que nos encontremos en la etapa n-ésima.  Los valores de la variable de decisión

posibles para cada estado

 El óptimo de la función para la etapa n+1, para el estado (o estados) a que evoluciones el sistema después de tomar la decisión

.

Para cada uno de los estados, deberemos determinar el valor óptimo de la función (que dependerá exclusivamente del estado del sistema), así como el valor

de

la variable de decisión que optimiza el comportamiento del sistema para ese estado. Ese valor

formara parte de la política óptima para esa etapa.

Ejemplo Cierto estudiante desea destinar los siete días de la semana próxima a estudiar cuatro cursos. Necesita al menos un día para cada curso y el puntaje que puede lograr se da en la siguiente tabla: ¿Cuantos días debe estudiar cada curso para lograr un puntaje?

Conclusión La programación dinámica nos permite resolver problemas complejos, caracterizados por decisiones interrelacionadas, es decir, decisiones que se deben tomar en forma secuencial y las cuales influyen en las decisiones de estas secuencias. De acuerdo a la información anterior el análisis se basa en el principio de “optimalidad”, el cual expresa que una política óptima esta conformada por sub políticas igual de optimas. Posteriormente debemos descomponer la incógnita en una serie de sub problemas. Lo característico es que se comienza por los que se sitúan de último, empleando la idea de recursión, retrocediendo hasta llegar a los primeros sub problemas. Se hace énfasis en la diferencia que existe entre los problemas de programación lineal y los de programación dinámica, pero quizás la más significativa sea la presencia del tiempo, esto quiere decir que los problemas de programación lineal se plantean para resolver una situación que ocurre en un determinado momento, en cambio los de programación dinámica tienen variaciones con relación al tiempo. Todo lo anterior lo convierte en un método eficaz para encontrar solución a problemas complejos de diversa índole, incluyendo los problemas industriales, el conocerlo y saber implementarlo nos será de gran soporte para el ámbito universitario y mejor aún: el ámbito industrial.

Fuentes

Métodos cuantitativos de organización industrial II, por José María Sallán Leyes, Joan Baptista Fonollosa Guardiet, pág. 99-101 http://books.google.com.mx/books?id=s17qyqho9NIC&pg=PA99&dq=programacion+dina mica&hl=es&sa=X&ei=ahEiUqaDPfSgsQS04BI&ved=0CDMQ6AEwAQ#v=onepage&q=programacion%20dinamica&f=false

Fundamentos de investigación de operaciones para administración, por Juan Manuel Izar Landeta, pág. 179-181 http://books.google.com.mx/books?id=piS59lBXhi0C&pg=PA179&dq=programacion+dina mica+investigacion+de+operaciones&hl=es&sa=X&ei=9Q4iUuLvDamwsQTMhoDABQ&ved =0CDoQ6AEwAg#v=onepage&q=programacion%20dinamica%20investigacion%20de%20o peraciones&f=false