Programación Dinámica

Programación Dinámica

1. Es un método basado en el principio de óptimo parcial.

2. Introducción

   • La programación dinámica es una técnica que se emplea típicamente para resolver problemas de optimización en los cuales el problema principal se encuadra en varios subproblemas.
     • Solucionando cada uno de ellos y luego ligando las soluciones de una forma óptima, donde la solución final permita resolver y tomar decisiones correctas a problemas actuales y futuros.
     • Esta técnica llega a la solución trabajando hacia atrás, partiendo del final del problema hacia el principio.
       • Por lo que un problema enorme e inmanejable se convierte en una serie de problemas más pequeños y manejables.
   • Busca el valor optimo de funciones que no todas las variables están relacionadas simultáneamente.
   • Los siguientes elementos conforman la resolución de un problema de Programación Dinámica: a)Etapas b)Estados c)Decisiones d)Formula recursiva e)Principio de optimalidad f)Condición a la frontera
     • Ejemplo...
       • Planteamiento
         • Problema de reemplazo. Se desea saber cuándo reemplazar una fotocopiadora en un proyecto de 5 años. La máquina solo puede mantenerse 1, 2 o hasta 3 años máximo. El costo de la fotocopiadora nueva es de $1,0000
       • Formulación
         • Etapas: 6 Años/Etapas Estados: Años de uso
         • Decisión: Comprar o mantener la fotocopiadora para el año t
         • Formula recursiva: ft (i, j) = dij + ft+1*(j)
         • Principio de factibilidad: ft*(i) = Min ft (i, j)
         • Condición a la frontera: f6*(i) = 0 I = 1, 2, 3
       • Red
       • Interpretación
       • Tablas

3. Ventajas

   • Divide el problema en problemas más pequeños y usa tablas para la facilitación de la resolución del problema
   • Resuelve problemas grandes
   • La ventaja de la descomposición es que el proceso de optimización en cada etapa involucra una única variable, una tarea más sencilla computacionalmente de involucrar todas las variables.

Bilder und Dateien der Mindmap