UNIDAD 1.- Programacin dinmica

Introduccin A La Programacin Dinmica (Pd)La PD fue desarrollada por Richard Bellman y G B Dantzing. Sus importantes contribuciones sobre esta tcnica cuantitativa de toma de decisiones se publicaron en 1957 en un libro del primer autor denominado Dynamic Programming (Princeton University Press. Princeton, New Jersey) (Domnguez, 2000).Inicialmente a la PD se le denomin programacin lineal estocstica problemas de programacin lineal con incertidumbre.La programacin dinmica (PD) determina la solucin ptima de un problema den variables descomponindola en n etapas, con cada etapa incluyendo un subproblema de una sola variable. La principal contribucin de la PD es el principio de optimalidad, el cual establece que una poltica ptima consiste de subpolticas ptimas, un marco de referencia para descomponer el problema en etapas.La programacin dinmica es una tcnica que se puede aplicar para resolver muchos problemas de optimizacin. La mayor parte de las veces, la programacin dinmica 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 ms pequeos y ms tratables.

As, la programacin dinmica se puede definir como una tcnica matemtica til que resuelve una serie de decisiones secuenciales, cada una de las cuales afecta las decisiones futuras. Proporciona un procedimiento sistemtico para determinar la combinacin de decisiones que maximiza la efectividad total (Taha, 2004).En contraste para el problema de programacin dinmica, trata de un enfoque de tipo parcial para la solucin de problemas y las ecuaciones especficas que se usan se deben desarrollar para que represente cada situacin individual.

NDICE

1.1Caractersticas De Los Problemas De Programacin Dinmica11.2Ejemplos De Modelos De Programacin Dinmica2El problema de la diligencia.2Resumen de clculos para las diferentes etapas6Formalizacin de los clculos de programacin dinmica61.3Programacin Dinmica Determinstica (PDD)7Aplicaciones de programacin dinmica determinstica71.4Programacin Dinmica Probabilstica (PDP)8Aplicaciones de programacin dinmica probabilstica81.5Programas De ComputacinPara Resolver Problemas De Programacin8Programas De Computacin9CONCLUSIN9

1.1 Caractersticas De Los Problemas De Programacin Dinmica

Las caractersticas de la programacin dinmica se emplean para formular e identificar la estructura de los problemas de este tipo.A continuacin se presentarn estas caractersticas bsicas que distinguen a los problemas de programacin dinmica.1. El problema se puede dividir en etapas que requieren una poltica de decisin en cada una de ellas. En muchos problemas de programacin dinmica, la etapa es la cantidad de tiempo que pasa desde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.2. Cada etapa tiene un cierto nmero de estados asociados a ella. Por estado se entiende la informacin que se necesita en cualquier etapa para tomar una decisin ptima.3. El efecto de la poltica de decisin en cada etapa es transformar el estado actual en un estado asociado con la siguiente etapa (tal vez de acuerdo a una distribucin de probabilidad).4. El procedimiento de solucin est diseado para encontrar una poltica ptima para el problema completo, es decir, una receta para las decisiones de la poltica ptima en cada etapa para cada uno de los estados posibles.5. Dado el estado actual, una poltica ptima para las etapas restantes es independiente de la poltica adoptada en etapas anteriores. (este es el principio de ptimalidad para la programacin dinmica). En general en los problemas de PD, el conocimiento del estado actual del sistema expresa toda la informacin sobre su comportamiento anterior, y esta informacin es necesario para determinar la poltica ptima de ah en adelante. 6. El procedimiento de solucin se inicia al encontrar la poltica ptima para la ltima etapa. La poltica ptima para la ltima etapa prescribe la poltica ptima de decisin para cada estado posible en esa etapa. 7. Se dispone de una relacin recursiva que indica la poltica ptima para la etapa dada la poltica optima para la etapa (n+1) A pesar de esta caracterstica, los problemas que pueden ser atacados con la PD tienen otras dos propiedades adicionales:

Slo un nmero 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 nmero reducido de variables. El resultado de una decisin en cualquier etapa altera los valores numricos de un nmero reducido de variables relevantes al problema. La decisin actual ni incrementa ni decrementa el nmero de factores sobre los cuales depende el resultado. As, para la siguiente decisin en la secuencia, el mismo nmero 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 poltica ptima se debe perseguir. No importa cules fueron los estados y decisiones iniciales, las decisiones restantes constituirn una poltica ptima con respecto al estado resultante de la primera decisin.

1.2 Ejemplos De Modelos De Programacin Dinmica1. 1.1. El problema de la diligencia.Un problema construido especialmente por el Profesor H M Wagner de la Universidad de Stanford para ilustrar las caractersticas e introducir la terminologa de la PD es el problema de la diligencia.Este problema se refiere a un vendedor mtico que tuvo que viajar hacia el oeste utilizando como medio de transporte una diligencia, a travs de tierras hostiles, en el ltimo cuarto del siglo XIX. An cuando su punto de partida y destino eran fijos, tena un nmero considerable de opciones para elegir qu estados (o territorios que posteriormente se convirtieron en estados) recorrer en su ruta.En la figura 5.1 se muestran las rutas posibles, en donde cada estado se representa por un bloque numerado.

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

De la ilustracin 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) y10Puesto que se ofrecan seguros de vida a los pasajeros de las diligencias, este vendedor no quiso dejar pasar la oportunidad y se propuso determinar la ruta ms segura. Como el costo de cada pliza se basaba en una evaluacin cuidadosa de la seguridad de ese recorrido, la ruta ms segura deba ser aquella con la pliza de seguro de vida ms barata. El costo de la pliza estndar para el viaje en diligencia del estado i al j se muestra en figura 5.1 como una etiqueta en los caminos (flechas) para ir de un estado a otro.As la pregunta central es: cul ruta (conjunto de caminos) minimiza el costo total de la pliza?, para contestar esta pregunta es necesario hacer notar que, el procedimiento poco inteligente de seleccionar el camino ms barato ofrecido en cada etapa sucesiva no necesariamente conduce a una decisin ptima global.La PD parte de una pequea porcin del problema y encuentra la solucin ptima para ese problema ms pequeo. Entonces gradualmente agranda el problema, hallando la solucin ptima en curso a partir de la anterior, hasta que se resuelve por completo el problema original. A continuacin se explican los detalles involucrados en la implementacin de esta filosofa general.La idea es calcular el costo mnimo (acumulativo) de la pliza de seguros entre los dos estados de cada etapa y despus utilizar esos costos como datos de entrada para la etapa inmediata siguiente.CLCULOS PARA LA ETAPA 1Considerando los estados asociados con la etapa 1, se puede ver que los estados 2, 3 y 4 estn conectados cada uno con el estado inicial 1 por una sola flecha como se puede apreciar en la figura 5.2. Por consiguiente, para la etapa 1 se tiene:

Figura 5.2 etapa 1: estados 2, 3,4 conectados con el estado inicial 1

Costo mnimo al estado 2 = 2 (desde el estado 1)Costo mnimo al estado 3 = 4 (desde el estado 1)Costo mnimo al estado 4 = 3 (desde el estado 1)

CLCULOS PARA LA ETAPA 2Despus se avanza a la etapa 2 para determinar los costos mnimos(Acumulativos) para los estados 5, 6 y 7 como se aprecia en la figura 5.3.Considerando primero al estado 5, se ve que existen tres alternativas; a saber (2,5), (3,5), (4,5). Figura 5.3 Etapa 2: estados 5, 6, 7 conectados con los estados 2, 3, 4.

Esta informacin, junto con los costos mnimos de los estados 2, 3 y 4 (figura 5.4) determinan el costo mnimo (acumulativo) para el estado 5 como:Figura 5.4 etapa 2:Estados 5 conectado con los estados 2, 3, 4.

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

Figura 5.5 Etapa 2: Estados 6 conectado con los estados 2, 3, 4.

Finalmente para el estado 7 (figura 5.6), se tiene:Figura 5.6Etapa 2: Estados 7 conectados con los estados 2, 3, 4.

CLCULOS PARA LA ETAPA 3Para los clculos se toman los datos de la figura 5.7

Figura 5.7 Etapa 3: estados 8, 9 conectados con los estados 5, 6, 7.

CLCULOS PARA LA ETAPA 4 Para los clculos se toman los datos de la figura 5.8

Figura 5.8 Etapa 4: Estados 10 conectados con los estados 8, 9

Resumen de clculos para las diferentes etapasEl costo mnimo 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,10Por lo tanto existen 3 rutas ptimas a elegir ya que la tres implican el costo mnimo total que es 11. Formalizacin de los clculos de programacin dinmica Se mostrar ahora la forma en la cual se pueden expresar matemticamente los clculos recursivos de la PD.

i=1, 2,3n

Con la condicin inicial. La ecuacin indica que las distancias ms cortas en la etapa i se debe expresar en funcin del siguiente nodo . En la terminologa de la programacin dinmica, a 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 informacin que enlaza, conecta o vincula las etapas, de tal modo que se pueda tomar las decisiones para las etapas restantes sin volver a examinar cmo se lleg a las decisiones de las etapas anteriores. La definicin correcta de estado permite considerar por separado cada estado, y garantiza que la solucin sea factible para todos los estados.1.3 Programacin Dinmica Determinstica (PDD)En este caso se profundiza sobre el enfoque de programacin dinmica en los problemas determinsticos, en donde el estado en la siguiente etapa est completamente determinado por el estado y la poltica de decisin de la etapa actual. El caso probabilstico en el que existe una distribucin de probabilidad para el valor posible del siguiente estado este se analizara ms adelante.Aplicaciones de programacin dinmica determinstica Algunas de las aplicaciones de programacin dinmica determinstica son: Modelo de Volumen-Carga Mochila Modelo del tamao de la fuerza de trabajo Modelo de reposicin de equipos Modelo de inversin Modelos de inventariosA continuacin se presentarn algunas de estas aplicaciones, cada una de las cuales muestra una nueva idea en la puesta en prctica de la PD.A medida que se presente cada aplicacin, es importante prestar atencin a los tres elementos bsicos de un modelo de PD: Definicin de las etapas Definicin de las polticas o alternativas Definicin de los estados para cada etapa

De los tres elementos, la definicin del estado por lo comn es la ms sutil.Las aplicaciones que se presentan a continuacin muestran que la definicin de estado vara dependiendo de la situacin que se est modelando.Sin embargo, a medida que se presente cada aplicacin, resultar til considerar las siguientes preguntas: Qu relaciones unen las etapas? Qu informacin se necesita para tomar decisiones factibles en la etapa actual, sin reexaminar las decisiones que se tomaron en las etapas anteriores?La experiencia indica que la comprensin del concepto de estado se puede mejorar cuestionando la validez de la forma que dicta la intuicin.Se sugiere intentar una definicin de estado diferente que pueda parecer ms lgica y utilizarla en los clculos recursivos.Con el tiempo, se descubrir que las definiciones que se presentan en las siguientes aplicaciones proporcionan la forma correcta para resolver el problema.Mientras tanto, el proceso mental propuesto deber mejorar la comprensin del concepto de estado.

1.4 Programacin Dinmica Probabilstica (PDP)La programacin dinmica probabilstica (PDP) es una tcnica matemticamente 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 poltica de decisin de la etapa actual. En su lugar existe una distribucin de probabilidad para determinar cul ser el siguiente estado. Sin embargo, esta distribucin de probabilidad si queda bien determinada por el estado y la poltica de decisin en la etapa actual. Por consiguiente la diferencia entre la programacin dinmica probabilstica y la programacin dinmica determinstica (PDD) est en que los estados y los retornos o retribuciones en cada etapa son probabilsticos. La programacin dinmica probabilstica se origina en especial en el tratamiento de modelos estocsticos de inventarios y en los procesos markovianos de decisin. En este apartado se presentar algunos ejemplos generales, con objeto de hacer resaltar la naturaleza estocstica de la programacin dinmica.Aplicaciones de programacin dinmica probabilstica Algunas de las aplicaciones de programacin dinmica probabilstica son: Un juego aleatorio Problema de inversin Maximizacin del evento de lograr una meta. A continuacin se presentar una de estas aplicaciones.

1.5 Programas De ComputacinPara Resolver Problemas De ProgramacinEn este apartado, se presenta la documentacin relativa a los programas de computacin quesern utilizados en el curso para resolver problemas de programacin,adicionalmente, se pueden descargar los programas de computacin con fines acadmicos, con miras a resolver los problemas propuestos del curso y no deben ser utilizados con fines comerciales ya que los mismos estn protegidos por las leyes de derechos de autor.Programas De ComputacinAdicional al programa SOLVER, incluido en EXCEL-2000 de MIcrosoft (cuya explicacin didctica 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 mnima de 256 kb y capacidad de disco de 50 MB y los cuales pueden ser bajados a continuacin:. A.1) El programa WinQSB (3.9 Mb), cuya propiedad intelectual es del Dr. Yih-Long Chang y es aplicable a todos los problemas de Investigacin de Operaciones. Para conocer sus usos y aplicaciones, se incorpora el MANUAL DE USO del WINQSB. A.2) El programa PrgLin, cuya propiedad es de la Universidad de Lisboa (Portugal), el cual se aplica para soluciones grficas de problemas de dos dimensiones. A.3) El programa InvOp (361 kb), desarrollado por la Universidad del Cuyo en Argentina, se aplica para la solucin de problemas relacionados con transporte y redes.A.3) El programa Lingo, propiedad de Lindo Systems Inc (USA), que dado su gran tamao (18.9 Mb), se recomienda que Usted lo recupere directamente de la pagina Web del propietario de dicha tecnologia http:// www.lindo.com.

CONCLUSINLa programacin dinmica, en sus distintos casos, resulta ser til para resolver problemas de cualquier tipo, como se vio a lo largo del documento anterior. La extensa aplicacin de la programacin dinmica permite optimizar los recursos o disponibilidades que el problema presente, en forma general puede decirse que la programacin dinmica ayuda como base en las operaciones y ensayos, haciendo clculos de aproximacin dentro de la suboptimizacin.La programacin dinmica es una verdadera estrategia de optimizacin, ms que un ejercicio o rutina, en la cual se consideran solo las partes del problema. Una enorme ventaja visible, es que los errores pueden cometerse al decidir sobre alguna de las partes del problema, no impiden decidir correctamente en los prximos pasos del problema.Otra ventaja notable de la programacin, es que se reduce el nmero de variables sobre las que se debe examinar a un mismo tiempo. La programacin dinmica es una herramienta estratgica que se recomienda cuando puede obtenerse un balance apropiado para la reduccin de la dimensionalidad. Puede observarse que esta tcnica se aplica favorablemente a sistemas complejos.

9