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.

Imágenes y archivos del mapa