Programación Dinamica

Plan your website and create the next important tasks for get your project rolling

Get Started. It's Free
or sign up with your email address
Rocket clouds
Programación Dinamica by Mind Map: Programación Dinamica

1. Ventajas

1.1. -Sirve para resolver problemas muy grandes. -La formula recursiva es la misma para la mayoría de los problemas. - Secciona el problema para una fácil resolución. -Es fácil de aplicar.

2. Red

2.1. La red se plantea de modo que cada articulo sea una etapa como se muestra a continuación.

3. Tablas

3.1. .

4. Formulacion

4.1. Etapas: 4, Etapas=Artículos. Estados : Peso Disponible para el articulo t. Etapas Estados Art 1 4 Art 2 4,2,0 Art 3 4,1,2,0 4 4,3,2,1,0 Decisión: Se asignan articulo t. Formula Recursiva= f(i,j)=dij + Ft+1(j) Principio de Optimalidad= max Fj(i,j) Condicion a la frontera f*4(i)=0 i=0,1,2,3,4

5. Interpretación de Resultados

5.1. La ganancia total máxima a la que Don Juan puede ser acreedor es de 652 pesos y la asignación que debe hacer se muestra en la tabla. La cual es que meta dos artículos del tipo 1 para así obtener dicha ganancia máxima.

6. Introducción

6.1. La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas. El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados. Caracteristicas: -Dividir el problema en subproblemas más pequeños. -Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente. -Usar estas soluciones óptimas para construir una solución óptima al problema original.

7. Planteamiento

7.1. Utilizaremos el siguiente ejemplo para mostrar el uso de la programación dinámica. A Don Juan le pidieron llenar una caja de madera con 3 diferentes artículos, al hacerlo cada uno genera una ganancia para Don Juan, el primer articulo pesa 2 kg y otorga una ganancia de 31 pesos, el segundo articulo pesa 3 kg y da 47 pesos de ganancia y el ultimo articulo pesa 1 kg y da de ganancia 14 pesos.¿Como debe Don Juan llenar la caja para maximizar sus ganancias?