PROGRAMACIÓN DINÁMICA-

DILIGENCIA

Materia: Optimización I
Ingería industrial y logística
Simon Vazquez Sanchez
Matricula: 127786
Maestro: Rhuskin de Jesus Ruiz Luna
 INDICE
INTRODUCCIÓN .................................................................................................................................... 2
Programacion dinámica ....................................................................................................................... 3
Para que se puede usar ........................................................................................................................ 4
Ventajas ................................................................................................................................................ 5
Como se aplica en ingeniería ............................................................................................................... 6
Problema de diligencia ......................................................................................................................... 7
Conclusión ............................................................................................................................................ 8
BIBLIOGRAFÍAS ..................................................................................................................................... 9
 INTRODUCCIÓN
La programación dinámica es una técnica fundamental en el campo de la
informática y la ciencia de la computación, reconocida por su capacidad para
resolver problemas complejos mediante la descomposición en subproblemas más
simples. A diferencia de los enfoques tradicionales que podrían implicar soluciones
recursivas ineficientes, la programación dinámica optimiza el rendimiento al
almacenar y reutilizar resultados de subproblemas ya resueltos. Este enfoque
estratégico no solo mejora la eficiencia computacional, sino que también permite
abordar problemas que de otro modo serían demasiado grandes para resolver de
manera práctica. En esta introducción, exploraremos los principios clave de la
programación dinámica y cómo se aplica para resolver una variedad de desafíos
computacionales.

La programación dinámica es una técnica matemática utilizada para resolver

problemas de decisión secuenciales. Se basa en descomponer un problema
complejo en subproblemas más simples y resolverlos de manera recursiva para
encontrar una solución óptima. Uno de los problemas clásicos resueltos mediante
programación dinámica es el problema de la diligencia.
En este problema, se busca encontrar la ruta más corta entre un nodo de origen y
un nodo de destino, dados varios nodos y arcos que los conectan.

Un ejemplo clásico es el problema de encontrar el número mínimo de monedas

para dar un cambio determinado. Este problema se puede resolver eficientemente
utilizando programación dinámica mediante la construcción de una tabla que
almacena las soluciones óptimas para todos los montos desde cero hasta el
monto deseado.
En resumen, la programación dinámica es una técnica poderosa para resolver
problemas que exhiben propiedades de subestructura óptima y solapamiento de
subproblemas. Se usa mucho en algoritmos de optimización y en la resolución de
problemas computacionales complejos.
 Programacion dinámica
La programación dinámica es una técnica en informática y matemáticas utilizada
para resolver problemas complejos dividiéndolos en subproblemas más simples y
resolviendo estos subproblemas una sola vez, almacenando sus soluciones para
evitar recálculos innecesarios en el futuro.
En términos generales, los problemas que se resuelven mediante programación
dinámica suelen tener las siguientes características:
Subestructura óptima: La solución óptima global puede ser construida a partir de
soluciones óptimas de subproblemas más pequeños.
Solapamiento de subproblemas: Los subproblemas individuales suelen
solucionarse más de una vez durante la resolución del problema general. La
programación dinámica evita este retrabajo almacenando soluciones ya calculadas
en una tabla (a menudo llamada tabla de memorización).
Los pasos comúnes para aplicar la programación dinámica:
1. Definir el problema en términos de subproblemas: Descomponer el
problema original en subproblemas más pequeños que puedan ser
resueltos de manera independiente.
2. Definir la relación de recurrencia: Formular una relación matemática o de
recursión que relacione la solución del problema original con las soluciones
de sus subproblemas.
3. Resolver los subproblemas de manera recursiva o iterativa: Dependiendo
de la formulación, implementar una solución que calcule las soluciones de
los subproblemas y las almacene en una tabla (memoización).
4. Construir la solución óptima del problema original: Usar las soluciones de
los subproblemas para construir la solución óptima del problema original.
 Para que se puede usar
La programación dinámica se puede usar en una amplia variedad de problemas
computacionales y matemáticos donde se encuentran las siguientes
características:
Optimización de problemas: Cuando se necesita encontrar la mejor solución
posible según ciertos criterios (como minimizar o maximizar algún valor).
Subproblemas solapados: Donde la solución de un mismo subproblema se utiliza
varias veces en el cálculo general del problema.
Problemas de decisión: Donde se deben tomar decisiones secuenciales o
interdependientes para alcanzar la solución óptima.
Además puede ser aplicada en:
Problemas de optimización de rutas: Encontrar la ruta más corta o más rápida
entre dos puntos en un grafo (por ejemplo, el algoritmo de Dijkstra).
Problemas de asignación: Como asignar recursos limitados para maximizar el
beneficio o minimizar el costo (por ejemplo, el problema de la mochila).
Problemas de secuenciación: Donde se deben tomar decisiones secuenciales que
afectan el resultado final (por ejemplo, problemas de planificación de proyectos).
Problemas de búsqueda: Como encontrar la subsecuencia común más larga entre
dos secuencias (por ejemplo, el algoritmo de Longest Common Subsequence).
Problemas de combinación: Donde se deben calcular todas las combinaciones
posibles de un conjunto de elementos (por ejemplo, el problema de la
subsecuencia más larga creciente).
 Ventajas
La programación dinámica ofrece varias ventajas importantes que la hacen una
técnica muy poderosa para resolver problemas computacionales y matemáticos.
Optimalidad: La programación dinámica garantiza encontrar la solución óptima al
problema, ya que construye la solución final a partir de soluciones óptimas de
subproblemas más pequeños. Esto es especialmente útil en problemas de
optimización donde se busca maximizar o minimizar algún valor.
Reducción del tiempo de ejecución: Al almacenar y reutilizar las soluciones a
subproblemas ya resueltos (mediante técnicas como la memorización o la
tabulación), se evitan cálculos innecesarios. Esto conduce a una mejora
significativa en el tiempo de ejecución, especialmente en problemas con
solapamiento de subproblemas.
Simplicidad conceptual: Aunque los problemas que se resuelven con
programación dinámica pueden ser complejos, la técnica en sí misma proporciona
una estructura clara y sistemática para descomponer y resolver el problema. Esto
facilita el diseño y la implementación de soluciones.
Aplicabilidad amplia: La programación dinámica se puede aplicar a una amplia
gama de problemas en diversos campos, como la optimización de rutas, la
asignación de recursos, la secuenciación de tareas, entre otros. Esto la convierte
en una herramienta versátil para ingenieros, científicos de datos, matemáticos y
desarrolladores de software.
Eficiencia espacial controlable: Aunque la programación dinámica puede requerir
espacio adicional para almacenar las soluciones de subproblemas (en
comparación con un enfoque recursivo simple), la cantidad de espacio adicional es
manejable y a menudo se puede optimizar mediante técnicas de gestión de
memoria.
Adaptabilidad a problemas complejos: Es capaz de manejar problemas complejos
con múltiples variables y restricciones, donde otros enfoques podrían ser
ineficaces o difíciles de implementar.
 Como se aplica en ingeniería
La programación dinámica encuentra numerosas aplicaciones en ingeniería
debido a su capacidad para resolver problemas complejos de manera eficiente y
óptima.
Optimización de rutas y logística: En la planificación de rutas de transporte, la
distribución de recursos y la optimización de la cadena de suministro, la
programación dinámica se utiliza para encontrar la ruta más corta, la distribución
de cargas más eficiente, o para optimizar el uso de vehículos y recursos limitados.
Planificación de proyectos y gestión de recursos: En la gestión de proyectos de
ingeniería, la programación dinámica ayuda a programar tareas de manera
eficiente, asignar recursos de manera óptima y minimizar los tiempos de espera o
retrasos.
Diseño de redes de comunicación: En el diseño de redes de telecomunicaciones,
la programación dinámica puede utilizarse para optimizar la conexión entre nodos,
maximizar el rendimiento de la red o minimizar la interferencia.
Ingeniería de software: En la optimización de algoritmos y en el diseño de
sistemas informáticos complejos, la programación dinámica puede emplearse para
mejorar la eficiencia y la velocidad de ejecución de aplicaciones.
Control y automatización: En el diseño de sistemas de control y automatización, la
programación dinámica es útil para optimizar el control de procesos en tiempo
real, ajustando parámetros de manera óptima para maximizar la eficiencia y
minimizar errores.
Simulación y modelado numérico: En ingeniería mecánica, civil, eléctrica y otras
disciplinas, la programación dinámica puede aplicarse para resolver problemas de
simulación y modelado numérico, optimizando el diseño y el comportamiento de
sistemas complejos.
Procesamiento de señales: En aplicaciones como el procesamiento de imágenes y
señales, la programación dinámica se utiliza para optimizar algoritmos de
compresión, reconocimiento de patrones o restauración de imágenes.
En cada una de estas áreas, la programación dinámica se aplica identificando
subproblemas repetitivos y resolviéndolos de manera eficiente utilizando técnicas
de memorización o tabulación. Esto permite a los ingenieros obtener soluciones
óptimas a problemas complejos, mejorar el rendimiento de los sistemas y
optimizar recursos limitados, contribuyendo significativamente al avance y la
eficiencia en el campo de la ingeniería.

Problema de diligencia

Ahora interpretamos los resultados: Nuestro vendedor se va a desplazar por la

siguiente ruta: A-C-E-H-J a un costo de $ 11 por las pólizas. Y listo nos quedó
resuelto el problema.
 Conclusión
La programación dinámica es una técnica poderosa para resolver problemas
computacionales complejos al descomponerlos en subproblemas más simples y
almacenar las soluciones a estos subproblemas para evitar recálculos
innecesarios.

La programación dinámica ofrece una estrategia sistemática y eficiente para

abordar problemas de optimización y decisión en informática. Al descomponer los
problemas en subproblemas más pequeños y aprovechar el almacenamiento de
soluciones previamente calculadas, no solo optimiza el tiempo de ejecución, sino
que también permite resolver problemas que de otro modo serían intratables. Esta
técnica no solo mejora la eficiencia computacional, sino que también abre la
puerta a soluciones elegantes y escalables para una amplia gama de desafíos
computacionales.

En resumen, la programación dinámica es útil si el problema se descompone en

subproblemas más pequeños que se resuelven óptimamente y se puede usar la
memorización (almacenamiento de resultados de subproblemas) para mejorar la
eficiencia computacional. Es una técnica poderosa para mejorar la eficiencia y
resolver problemas complejos en una amplia variedad de dominios, desde la
informática hasta la optimización matemática y la planificación estratégica.
 BIBLIOGRAFÍAS
(76) Problema de la diligencia | Ramiro Espinoza Lagos - Academia.edu
https://diposit.ub.edu/dspace/bitstream/2445/186821/2/tfg_rosell_esau_keila_ruth.
pdf
https://minerva.usc.es/xmlui/bitstream/handle/10347/28920/L%C3%B3pez_Fern%
C3%A1ndez_Lidia.pdf
https://www.ingenieria.unam.mx/sistemas/PDF/Avisos/Seminarios/SeminarioV/Sesi
on6_IdaliaFlores_20abr15.pdf