UNIVERSIDAD NACIONAL DEL CENTRO DEL PERÚ
FACULTAD DE CIENCIAS APLICADAS
E.P. ADMINISTRACIÓN DE NEGOCIOS
PROGRAMACIÓN
Dinámica
ASIGNATURA:
Métodos Cuantitativos Para Negocios II
DOCENTE:
GONZALES BORDA, Juan Carlos
INTEGRANTES:
CALDERON LAZO, Frank Jhojan
GREGORIO CARDENAS, Brayan Michael
INGARUCA YAURI, Joselyn
ROJAS VARGAS, Fernando Gustavo
YAURI ASTUHUMAN,Yen
TARMA - 2024
FIUBA. Teoría de algoritmos 1. Módulo 5:
Programación dinámica
Introducción y Origen Ejemplo Práctico - El Problema de Corte de Cuerda:
La programación dinámica (PD) es una técnica de optimización
desarrollada por Richard Bellman en los años 50 para resolver problemas En este problema, se busca maximizar la ganancia al cortar una cuerda en
complejos al descomponerlos en partes más pequeñas. Fue creada en un diferentes segmentos, donde cada corte puede tener un valor distinto en función
contexto de investigación en la Rand Corporation, para problemas que
del tamaño del segmento. La PD permite evaluar todas las combinaciones de
requerían soluciones óptimas en decisiones estratégicas.
cortes posibles y calcular cuál maximiza la ganancia total, analizando cómo
cada corte impacta en la longitud restante de la cuerda y en las ganancias
obtenidas.
Principios Fundamentales:
Subestructura Óptima: La solución óptima de un problema general se construye a partir de
las soluciones óptimas de sus subproblemas. Esto significa que, al resolver cada parte del
problema de forma óptima, se puede combinar para lograr la solución global óptima.
Optimización Temporal y Espacial
Problemas Superpuestos: Muchos subproblemas se repiten al resolver el problema
La PD es útil para optimizar tanto el tiempo de ejecución como
principal. Al almacenar las soluciones de estos subproblemas, se pueden reutilizar cuando el uso de memoria. Gracias a la tabla de memorización y al
vuelvan a aparecer, lo cual optimiza el proceso al evitar cálculos redundan enfoque iterativo (que resuelve primero los subproblemas más
pequeños), se ahorra memoria y se reducen los tiempos de
cálculo en comparación con métodos puramente recursivos.
Uso de Relaciones de Recurrencia:
Las relaciones de recurrencia son ecuaciones que expresan
Reconstrucción de Decisiones Óptimas
Además de encontrar la solución óptima en términos de valor, la PD permite
el problema en función de sus subproblemas. Esto permite
reconstruir el conjunto de decisiones que llevaron a esa solución. En el caso del
definir cómo la solución de los subproblemas se vincula y
problema de corte de cuerda, una vez que el programa ha calculado la máxima
construye la solución general, ayudando a calcular el
ganancia, es posible rastrear los cortes específicos que se realizaron para obtener
resultado óptimo de forma sistemática ese resultado. Esto se hace siguiendo las decisiones almacenadas en la tabla de
memorización, lo que permite ver paso a paso cómo se llegó a la solución óptima.
Este proceso de reconstrucción de decisiones es útil en problemas de planificación y
toma de decisiones, ya que proporciona una guía clara de las acciones que se deben
tomar para alcanzar el mejor resultado.
Memorización para la Optimización
Una de las claves de la PD es la "memorización", que consiste en
almacenar los resultados de subproblemas ya resueltos en una
tabla. Esta tabla, conocida como tabla de memorización, evita
repetir cálculos y mejora la eficiencia temporal del algoritmo. Al
consultar esta tabla, el programa recupera rápidamente la solución
de subproblemas ya calculados.
Conclusión
La programación dinámica es una técnica de
resolución de problemas de optimización que divide
el problema en subproblemas, reutiliza soluciones
ya calculadas y mejora el tiempo y memoria
usados. Al hacer esto, PD es capaz de resolver
problemas de manera rápida y eficaz, lo que la
convierte en una herramienta esencial para muchos
algoritmos de optimización en computación.
EJEMPLO
Un Ingeniero Forestal, requiere saber: i)Cuál es el costo mínimo, y ii)Cuál
es la ruta con ese costo mínimo, para ir desde su oficina hasta el lugar
donde está la cosecha. En su camino debe pasar por 3 sectores o
Problema
ciudades antes de llegar a su destino, y lugares posibles en esos
sectores o ciudades. Las posibles rutas, y el costo asociado por Kms. de
distancia y otros en $, se ven en el siguiente esquema:
Soluciones
Para ir de 1 a 13 hay 48 rutas posibles. Una posibilidad para encontrar la solución es calcular el valor
asociado a cada una y ver cual es la que proporciona el menor costo. ¿Y si fuesen miles de rutas?. Por se
descarta esa alternativa y se usa el método de la programación Dinámica, donde se resuelve desde el
final hacia el inicio, y hay etapas y estados.
Etapas: Son 4. La etapa 1 es decidir ir del estado inicial 1 al estado 2,3,4 o 5 que son los puntos posibles
en el sector siguiente. La etapa 2 es decidir ir a 6, 7 u 8. La etapa 3 es decidir ir a 9, 10, 11 o 12. La etapa 4
es decidir a 13.
Estado: Lugar donde se encuentra. La etapa 1 tiene 1 estado: el 1. La etapa 2 tiene 4 estados: 2, 3, 4, 5. La
etapa 3 tiene 3 estados: 6,7,8. La etapa 4 tiene 4 estados: 9, 10, 11, 12.
CÁLCULOS
RESPUESTA
El Ingeniero Forestal tiene un costo mínimo de $24 para ir desde su
oficina al lugar de cosecha, y ese mínimo lo puede lograr yendo desde su
oficina al lugar 3 luego al lugar 8 luego al lugar 9 y de ahí al lugar 13, que
es donde está la cosecha.
