Edgargarciainvo2.docx

UNIVERSIDAD BICENTENARIA DE ARAGUA ESCUELA DE INGENIERIA DE SISTEMA INVESTIGACION DE OPERACIONES MARACAY - VENEZUELA

PROGRAMACIÓN DINÁMICA Actividad 3

Alumno: Edgar José Garcia Guerrero Cedula de identidad: V-20131051 Correo: [email protected]

Introducción Al pasar de los años nuestra sociedad evoluciona conociendo nuevos límites para el poder de nuestra imaginación, impulsado por nuevas corrientes se creó la programación dinámica que consiste en resolver un problema complejo descomponiéndolo en algoritmos mas sencillos caracterizada por decisiones que se deben tomar en forma secuencial, aparte busca optimizar ganancias disminuyendo costos, entre sus características están dividir el problema en etapas, resolver los sub problemas una sola vez, el tiempo de ejecución puede optimizarse bastante. Teniendo en cuenta que la programación dinámica nos puede resultar extremadamente útil ya que resuelve problemas de una manera eficaz, a continuación, desarrollaremos aspectos importantes para su conocimiento.

2

PROGRAMACIÓN DINÁMICA Origen El término Programación Dinámica fue utilizado originalmente en los 40’s por Richard Bellman para describir el proceso de resolver problemas donde se necesita encontrar las mejores decisiones una tras otra para 1953, el refinó esto a su significado moderno, el cual se refiere específicamente a anidar pequeños problemas de decisión dentro de grandes decisiones, luego de esto el campo fue reconocido por la lEEE como un tópico de análisis de sistemas e ingeniería. La contribución de Bellman es recordada en el nombre de la ecuación de Bellman, un resultado central de programación dinámica que replantea un problema de optimización en forma recursiva. Originalmente la palabra “programación” en “programación dinámica” no tenía conexión con la programación de computadoras y en cambio venía del término “programación matemática”. Sin embargo, actualmente muchos problemas de optimización son mejor resueltos escribiendo programas de computadoras que implementa un algoritmo de programación dinámica, lo cual resulta mejor que llevar a cabo cientos de cálculos a mano.

Importancia Importancia de la Programación Dinámica Este algoritmo evita calcular dos veces la misma información, manteniendo una tabla de resultados conocidos, la cual se va llenando a medida que se resuelven los sub-problemas. La programación dinámica se aplica no solo por razones de eficiencia, sino porque permite resolver de manera eficiente problemas que no se pueden resolver por otras metodologías, en las cuales no toman como prioridad optimizar el tiempo y disminuir costes.

Contribuciones 1.- Una de las características esenciales es la toma de decisiones en secuencia. 2.- Ayuda con el problema porque se puede dividir en etapas, las cuales requieren de una política de decisión, en cada una de ellas. 3

3.- Es necesarios conocer pocos datos para describir el problema en cada etapa. 4.- La dependencia del resultado de las decisiones de una pequeña cantidad de Variables. 5.- En cualquier etapa, el resultado de una decisión, altera los valores numéricos de la pequeña cantidad de variables relacionadas con el problema. 6.- Cada etapa tiene un cierto numero de estados asociados a ella. Estos son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema. 7.- 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. 8.- La decisión real no aumenta ni disminuye el número de factores de los que dependen los resultados. 9.- El procedimiento de solución esta diseñado para encontrar una política de solución optima, para el problema planteado

.

PROGRAMACIÓN DINÁMICA DETERMINÍSTICA Conceptualización En la programación determinista el estado en la siguiente etapa esta completamente determinado por el estado y la política de decisión de la etapa actual. El enfoque de programación dinámica en los problemas determinísticos, en donde el estado en la siguiente etapa esta 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. Una manera de clasificar los problemas de programación dinámica determinísticas es con base en la forma de función objetivo. 4

Por ejemplo puede ser minimizar la suma de las contribuciones en cada etapa individual como en el problema de la diligencia o maximizar esa suma, o bien minimizar el producto de los términos, etc. Otra clasificación se puede hacer en términos dela naturaleza del conjunto de estados en las respectivas etapas.

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” Consiste en elegir, de entre un conjunto de n elementos y/o artículos de un negocio, (cada uno con un valor y un peso), aquellos que puedan ser cargados en la mochila de un individuo. La mochila resiste un peso máximo y se debe tener en cuenta que el individuo pretende acumular el mayor valor posible, entre todos los objetos que recoge.

Modelo del tamaño de la fuerza de trabajo En proyectos de construcción, contratación y despidos se debe mantener la fuerza de trabajo, ¿cómo se debe mantener esta durante el proyecto? Se supone que el proyecto se desea realizar en un lapso de n semanas y la fuerza de trabajo mínima requeridos en la semana es i y bi trabajadores. El estado ideal es que fuerza de trabajo=bi, sin embargo es importante que teniendo en cuenta los costos la fuerza de trabajo varié. Modelo de Reposición Mientras mas tiempo este en servicio una maquina, su costo de mantenimiento es mayor y su productividad es menor. Cuando la maquina llega a cierta antiguedad sera mas economico remplazarla. Es asi entonces que el problema se reduce a determinación de antigüedad mas economica de la maquina. 5

Programación Dinámica Probabilista La programación dinámica probabilística difiere de la determinística 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 inventario. Se considera a un Modelo Estocástico cuando algunas variables están en función a un modelo de probabilidad de que el evento se lleve a cabo.

Aplicaciones de programación dinámica probabilística 1 El problema se puede dividir en etapas; cada etapa requiere una decisión. 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. 2 Cada etapa tiene un número de estados asociados con ella. Por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima. 3 La decisión tomada en cualquier etapa indica cómo se transforma el estado en la etapa actual en el estado en la siguiente etapa. En muchos problemas, una decisión no determina con certeza el estado de la siguiente etapa; en lugar de ello, la decisión actual sólo determina la distribución de probabilidad del estado en la etapa siguiente. 4 Dado el estado actual, la decisión óptima para cada una de las etapas restantes no debe depender de estados previamente alcanzados o de decisiones previamente tomadas. A esta idea se le conoce como principio de optimalidad. 5 Si los estados del problema se han clasificado en uno de N etapas, debe haber una fórmula recursiva que relacione el costo o beneficio durante las etapas n, n+1,…, N con el costo o beneficio de las etapas n+1, n+2,…,N. En esencia, la fórmula recursiva formaliza el procedimiento de marcha atrás.

6

Conclusión La Programación Dinámica es una técnica que permite la optimización de soluciones a problemas adaptandandolos a la metodología divide y vencerás, fraccionando el problema en subproblemas o subcasos y solucionando a cada uno de ellos mediante el uso de la recursividad para luego combinar estas soluciones parciales para obtener la solución al problema. Cabe destacar que para que un problema se pueda resolver mediante la Programación Dinámica debe cumplir ciertas características para que pueda ser tratado como así. Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no tiene una forma estándar. Así, para cada problema es necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica. Sin embargo un aspecto realmente destacable es la posibilidad de amplio campo de aplicación que posee la programación dinámica, que desde un turista queriendo viajar o la posibilidad de combinar objetos de una mochila para ahorrar espacio o también la planificación de programación de producción e inventarios y sin olvidarse de la gran importancia que posee la “Programación Dinámica” en la informática.

7