Programacion dinamica

Programación Dinámica. La programación dinámica es una técnica útil en la toma de una serie de decisiones interrelacionadas. Proporciona un procedimiento sistemático para determinar la combinación óptima de decisiones. En contraste con la programación lineal, no cuenta con una formulación matemática estándar para el problema de programación dinámica, sino que se trata de un enfoque de tipo general para la solución de problemas, y las ecuaciones específicas que se usan se deben desarrollar para que representen cada situación individual. EJEMPLO 1.- PROBLEMA DE LA DILIGENCIA. Este problema trata sobre un cazafortunas 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 cuando existían serios peligros de ser atacado. Aún cuando su punto de partida y su destino eran fijos, tenía muchas opciones en cuanto a qué estados debía elegir como puntos intermedios. En el grafo siguiente se ilustran las posibles rutas en donde la dirección del viaje es siempre de izquierda a derecha. Se requieren 4 etapas para viajar desde su punto de partida en el estado A a su destino en el estado J. Preocupado por la seguridad de su viaje se le ocurrió una manera bastante ingeniosa para determinar la ruta más segura. Se le ofrecían pólizas de seguros de vida a los viajeros de manera que para determinar la ruta más segura habría que elegir la que tuviera el menor costo total de la póliza. Los costos de las pólizas vienen dados en el grafo. El problema es determinar la ruta que minimiza el costo total de la póliza. Observemos primero que el procedimiento de elegir la ruta más barata en cada etapa sucesiva no conduce a una decisión óptima global. Al seguir esta estrategia se obtiene la ruta A,B,F,I,J con un costo de 13, pero un pequeño sacrificio en una etapa permite mayores ahorros en la etapa siguiente, así por ejemplo, A,D, F es más barato que A,B,F. La programación dinámica empieza con una pequeña porción del problema original y encuentra la solución óptima para este problema pequeño. En el problema de la diligencia se comienza con el problema sencillo en el que el agente casa ha llegado al final de su viaje y sólo tiene una etapa más por recorrer. En cada una de las iteraciones siguientes, el problema se agranda aumentando de uno en uno el número de etapas que le quedan por recorrer para completar el viaje. Formulación: Sean xn = variables que representan el destino inmediato de la etapa n. fn(s,xn) = costo total = costo inmediato (etapa n) + mínimo costo futuro (etapas n+1 en adelante) = csxn+ fn+1*(s,xn*) fn*(s) = mín fn(s,xn) = fn(s,xn*) Como el destino final (estado J) se alcanza al terminar la etapa 4, f5*(J) = 0. El objetivo es encontrar f1*(A) y la ruta correspondiente. La programación dinámica la encuentra al hallar sucesivamente f4*(s), f3*(s), f2*(s) para cada uno de los estados posibles s y usar después f2*(s) para encontrar f1*(A). Procedimiento de solución: n = 4 s f4*(s) x4* H 3 J I 4 J n = 3 s H I f3*(s) x3* E 4 8 4 H F 9 7 7 I G 6 7 6 H n = 2 s E F G f2*(s) x2* B 11 11 12 11 E ó F C 7 9 10 7 E D 8 8 11 8 E ó F n = 1 s B C D f1*(s) x1* A 13 11 11 11 C ó D En este punto se puede identificar una solución óptima a partir de las 4 tablas: A-C-E-H-J o bien A-D-E-H-J o bien A-D-F-I-J. Características generales de los problemas de programación dinámica. 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.

por favor me puedes enviar el documento de programacion dinamica

Me podría mandar el archivo por favor con la informacion de la Programación Dinámica, lo agradeceré mucho. Saludos.

NECESITO INFORMACION ACERCA DE EL PRINCIPIO DE LA DESCOMPOSICION. EL PROBLEMA DE DECISION DE UNA ETAPA. EL PROBLEMA DE DESICION DE n ETAPAS. LA FUNCION RECURSIVA. EJEMPLOS DE APLICACION.

Si fueras tan amable de reenviarme la informacion. Por favor

Si fueras tan amable de reenviarme la informacion. Por favor Miguel Santana

la programacion dinamica se basa en simplemente hacer menos tiempo, sacrificando memoria,"el que no recuerda el pasado esta condenado a repetirlo",

¿Programación dinámica? ¿Importancia y usos? ¿Condiciones y representaciones? Pasos ¿Que es recursivo? INTRODUCCIÓN Recursión es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición, las instancias complejas de un proceso se definen en términos de instancias más simples, estando las finales más simples definidas de forma explícita. Desde que fui estudiante siempre he sabido lo difícil que es entender qué es la recursividad y para qué sirve en computación. Para muchos la única forma de aprender a dominar esta importante técnica de programación es correr mentalmente muchos programas recursivos, hasta que, por insistencia, se llega a entender de qué trata este asunto. Como profesor, he tratado de explicar este importante concepto y, con el tiempo, he encontrado las tres formas de hacerlo que expongo aquí. PROGRAMACION DINAMICA Un procedimiento de la investigación operativa que intenta optimizar una función objetivo, en problemas no lineares, discretizables, que pueden ser tratados en forma secuenciál. La programación dinámica es una técnica matemática que a menudo resulta útil a tomar una sucesión de decisiones interrelacionadas. Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximice la efectividad global. Contrastando con la programación lineal, no existe un planteamiento matemático estándar "del" problema de programación dinámica. Más bien, la programación dinámica es un tipo general de enfoque para resolver problemas y las ecuaciones particulares usadas deben desarrollarse para que se ajusten a cada situación individual. Por lo tanto, se requiere un cierto grado de ingenio y de visión de la estructura general de los problemas de programación dinámica, a fin de reconocer cuando un problema se puede resolver mediante los procedimientos de esta programación y cómo se haría. Probablemente se puedan desarrollar mejor estas aptitudes por medio de una exposición de una amplia variedad de aplicaciones de la programación dinámica y de un estudio de las características que son comunes a todas estas. Por fortuna, la programación dinámica suministra una solución con mucho menos esfuerzo que la enumeración exhaustiva. (Los ahorros de cálculo serían enormes para versiones más grandes de un problema.) La programación dinámica parte de una pequeña porción del problema y encuentra la solución óptima para este 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. En seguida se dan los detalles involucrados en la implementación de esta filosofía general. CONDICIONES Considérese que las variables de decisión xn (n = 1,2,3,4) son el destino inmediato en la etapa n. Así, la ruta seleccionada sería 1 - XI - X2 - X3 - X4 en donde X4 = 10. Sea fn(s, Xn) el costo total de la mejor política global para las etapas restantes, dado que el vendedor se encuentra en el estado s listo para iniciar la etapa n y se selecciona a XII como el destino inmediato. Dados s y n, denotemos por x el valor de X*n que minimiza al fn(s, Xn) y sea f*(s) el valor mínimo correspondiente de fn(s, Xn) por tanto, f*n(s) = fn(s, Xn). El objetivo es hallar f1*(1) y la pol1tica correspondiente. La programación dinámica hace esto, hallando sucesivamente f4*(s),f3*(s), f2*(s) , a continuación, f1*(1). LA RECURSIVIDAD Es una técnica de programación mediante la cual un módulo puede invocarse a sí mismo. Es importante porque algunos algoritmos recursivos son mucho más compactos y elegantes que los algoritmos no recursivos equivalentes. Por eso quien domina las técnicas básicas de programación debe saber usar recursividad. Cuesta bastante entender por primera vez qué es recursividad, pero para hacerlo ayuda mucho conocer cómo se usan los registros de activación en la pila de ejecución del programa, para recordar la dirección de retorno del procedimiento y almacenar sus variables locales. La recursividad va ligado al de repetición. Son recursivos aquellos algoritmos que, estando encapsulados dentro de una función, son llamados desde ella misma una y otra vez, en contraposición a los algoritmos iterativos, que hacen uso de bucles while, do-while, for, etc. Recursivo si se define en términos de sí mismo (cuando para definirse hace mención a sí mismo). Para que una definición recursiva sea válida, la referencia a sí misma debe ser relativamente más sencilla que el caso considerado. Ejemplo: definición de nº natural: el N º 0 es natural el Nº n es natural si n-1 lo es. En un algoritmo recursivo distinguimos como mínimo 2 partes: Aquellas funciones cuyo dominio puede ser recursivamente definido pueden ser definidas de forma recursiva. El ejemplo más conocido es la definición recursiva de la función factorial f(n): f(0) = 1 f(n) = n • f(n-1) para todo número natural n > 0 Con esta definición veamos como funciona esta función para el valor del factorial de 3: f(3) = 3 • f(3-1) = 3 • f(2) = 3 • 2 • f(2-1) = 3 • 2 • f(1) = 3 • 2 • 1 • f(1-1) = 3 • 2 • 1 • f(0) = 3 • 2 • 1 • 1 = 6 Caso trivial, base o de fin de recursión: Es un caso donde el problema puede resolverse sin tener que hacer uso de una nueva llamada a sí mismo. Evita la continuación indefinida de las partes recursivas. PARTE PURAMENTE RECURSIVA: Relaciona el resultado del algoritmo con resultados de casos más simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base. TIPOS DE RECURSIÓN • Recursividad simple Aquella en cuya definición sólo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos. • Recursividad múltiple Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más difícil de hacer de forma iterativa. CONCLUSIONES La programación dinámica es una técnica muy útil pata tomar decisiones interrelacionadas. Requiere del planteamiento de una relación recursiva apropiada para cada problema individual. Sin embargo, da lugar a un gran ahorro de cálculos comparando con el uso de la enumeración exhaustiva para hallar la mejor combinación de decisiones, en especial para problemas grandes. Por ejemplo sin un problema tiene 10 etapas con 10 estados y 10 decisiones posibles Es una técnica de programación mediante la cual un módulo puede invocarse a sí mismo. Es importante porque algunos algoritmos recursivos son mucho más compactos y elegantes que los algoritmos no recursivos equivalentes. Por eso quien domina las técnicas básicas de programación debe saber usar recursividad. Cuesta bastante entender por primera vez qué es recursividad, pero para hacerlo ayuda mucho conocer cómo se usan los registros de activación en la pila de ejecución del programa, para recordar la dirección de retorno del procedimiento y almacenar sus en cada etapa, entonces la enumeración exhaustiva debe considerar hasta combinaciones.

es posible utilizar PD cuando en la funcion objetivo de un problema no lineal se encuentran terminos que dependen de mas de una variable?........si es asi, en la funcion recursiva, que etapa de desicion se utiliza el termino?

por favor; necesito aplicaciones de la PD, como lo es asignacion, mochila y confiabilidad, pero necesito más.....de antemano gracias......

Me podrías mandar el archivo word de PD

por favor enviame ejemplos con 20 articulos como minimo del modelo de la mochila con su respectiva solucion

por favor enviame ejemplos con 20 articulos como minimo del modelo de la mochila con su respectiva solucion

por favor enviame ejemplos con 20 articulos como minimo del modelo de la mochila con su respectiva solucion

buenos dias quisiera saber para q es la rapida recursiva en programacion

podria enviarme por favor el archivo a mi cuenta de correo

Me podrian enviar un ejemplo sencillo de programacion dinamica como el de la mochila gracias

Hola, si alguno de ustedes fuera tan amable, ¿podrían enviarme el archivo con el documento sobre Programación Dinámica?, muchas gracias de antemano.

por favor, necesito informacion sobre programacion dinamica probabilistica

por favor pudieras mandarme el programa te lo agradeceria mucho, un abraso gracias

google es uin mierda ahy puras webadas no hay nada de informacion solohay un monton de wadas que solo sirve oara distraer lo que busco es osbre problemas de confiabilidad

disculpe miguel santana me podria explicar acerdca de esta programacion.

hola miguel santana un favor me podrias mandsr esos datos ami correo, disculpa quien eres?porfavor urge que me contestes.gracias muchas gracias