Programación Dinamica

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

Comienza Ya. Es Gratis
ó regístrate con tu dirección de correo electrónico
Programación Dinamica por 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?