1.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.
2. Tablas
2.1. .
3. Red
3.1. La red se plantea de modo que cada articulo sea una etapa como se muestra a continuación.
4. Ventajas
4.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.
5. Introducción
5.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.
6. Planteamiento
6.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?
7. Formulacion
7.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
