República Bolivariana de Venezuela

Universidad Bicentenaria de Aragua

Vicerrectorado académico
Facultad de ingeniería
Escuela de ingeniería en sistemas
San Joaquín de Turmero - Edo. Aragua

Ensayo sobre la programación dinámica

Autor: Antonio Rodriguez

CI: 26.320.645

San Joaquín, Marzo de 2024

 La Programación Dinámica ha sido una herramienta de suma
importancia para el análisis de diferentes problemáticas que ha captado
mi atención. En este informe, exploraremos los diversos aspectos
relacionados con esta técnica, que ha demostrado ser una piedra angular
en la solución de una amplia gama de problemas en diferentes campos.

En primer lugar, abordaré los fundamentos de la programación

dinámica y su aplicación en la optimización. Esta metodología no solo
proporciona soluciones eficientes, sino que también ofrece una
perspectiva única para abordar problemas complejos mediante la
descomposición en subproblemas más simples.

Posteriormente, vamos a analizar los diferentes modelos de

programación dinámica. Desde la formulación de problemas de rutas más
cortas hasta la resolución de problemas lineales, existe una variedad de
enfoques y técnicas que se adaptan a diferentes contextos y requisitos.

En el desarrollo teórico, haré enfasis en la ecuación recursiva de

retroceso de la programación dinámica. Esta ecuación es fundamental
para comprender cómo se construyen las soluciones óptimas a partir de la
combinación de soluciones a subproblemas. Además, exploraré cómo la
programación dinámica se aplica específicamente en la solución de
problemas lineales. Esta aplicación conlleva una serie de pasos y
consideraciones que permiten encontrar soluciones óptimas en
situaciones donde los recursos son limitados y los objetivos son
maximizar los beneficios o minimizar los costos.

Por último, antes de concluir, realizaré un ejercicio práctico a mano

que ilustrará la aplicación de la programación dinámica en la resolución
de un problema lineal de costos/beneficios. Este ejercicio se documentará
detalladamente con imágenes de cada paso, demostrando así la
efectividad y la claridad de esta técnica en la práctica.
 La optimización es un campo crucial en la toma de decisiones, ya
sea en la gestión, la ingeniería, la economía o la ciencia. Dentro de este
contexto, la Programación Dinámica surge como una herramienta
fundamental para abordar problemas de optimización complejos y
multidimensionales.

En esencia, la programación dinámica se basa en la

descomposición de un problema en subproblemas más simples y
manejables, lo que permite encontrar la solución óptima global
combinando las soluciones óptimas de los subproblemas. Este enfoque
divide el problema en pasos sucesivos y utiliza la información de los
pasos anteriores para tomar decisiones óptimas en cada etapa, lo que
resulta en una solución eficiente y óptima en términos de un criterio
específico, como maximizar ganancias o minimizar costos.

Una de las contribuciones más destacadas en este campo proviene

de Hillier (2010), quien enfatiza la importancia de entender la estructura
del problema y la identificación de subproblemas solapados o recurrentes
para aplicar eficazmente la programación dinámica. Además, Hillier
destaca la relevancia de “la formulación precisa de la función objetivo y
las restricciones del problema”, ya que esto influye directamente en la
eficacia del enfoque dinámico.

Fig. 1 Descomposición del problema de la ruta más corta en

etapas
 Por otro lado, Moskowits (2011) aborda la programación dinámica
como una “herramienta para resolver problemas de optimización en un
contexto de incertidumbre y cambio”. Destaca la flexibilidad de esta
técnica para adaptarse a situaciones variables y dinámicas, permitiendo
ajustes continuos en las decisiones tomadas a lo largo del tiempo. Esta
perspectiva dinámica es fundamental en entornos empresariales y
operativos donde las condiciones pueden cambiar rápidamente.

Otro aspecto importante a considerar son los denominados

modelos de programación dinámica abarcan una amplia variedad de
enfoques y técnicas que se adaptan a diferentes contextos y tipos de
problemas. Desde la optimización de rutas hasta la gestión de inventarios,
estos modelos proporcionan un marco estructurado para abordar
problemas complejos de manera eficiente.

Hillier (2010) destaca la importancia de comprender la estructura

del problema y la naturaleza de las decisiones secuenciales en la
formulación de modelos de programación dinámica. En su enfoque,
enfatiza la necesidad de “identificar las variables de decisión, las
restricciones y los costos asociados en cada etapa del proceso de toma
de decisiones”. Esta comprensión profunda del problema subyacente es
fundamental para diseñar un modelo de programación dinámica efectivo y
aplicable.

Los modelos de programación dinámica pueden variar según el

tipo de problema que se esté abordando. Por ejemplo, en el caso de la
optimización de rutas, el modelo puede incluir variables como la distancia
recorrida, el tiempo de viaje y las restricciones de capacidad, mientras
que en la gestión de inventarios, las variables pueden incluir el nivel de
inventario, la demanda esperada y los costos de almacenamiento. De
este modo podemos mencionar algunos ejemplos puntuales de los
modelos, tales como:
 1. Problema del camino más corto: Este modelo se utiliza para
encontrar el camino más corto entre dos puntos en un grafo
ponderado, donde los nodos representan ubicaciones y las aristas
representan conexiones entre ellas con un costo asociado.
2. Problema de la mochila: Este modelo se utiliza para determinar la
combinación óptima de artículos que se pueden colocar en una
mochila con una capacidad limitada, maximizando el valor total de
los artículos sin exceder la capacidad de la mochila.
3. Problema de la cadena de Markov: Este modelo se utiliza para
predecir estados futuros en un proceso estocástico, donde la
transición de un estado a otro está determinada por una matriz de
probabilidades de transición.

En este ensayo vamos a ver con detenimiento lo que conlleva la

formulación de problemas de rutas más cortas según la perspectiva de
la programación dinámica

La formulación de este problema implica definir un conjunto de

nodos (ubicaciones) y aristas (conexiones entre nodos) con pesos
asociados (distancias, tiempos de viaje, costos, etc.). El objetivo es
encontrar la ruta que minimice la suma de los pesos a lo largo del camino.

Para abordar este problema utilizando Programación Dinámica,

primero debemos entender la naturaleza recursiva de la solución. En lugar
de intentar encontrar directamente la ruta más corta entre los nodos,
descomponemos el problema en subproblemas más simples.

En este caso, Hillier sugiere que podemos pensar en la ruta más

corta entre dos nodos como la combinación de la ruta más corta desde el
nodo de inicio hasta un nodo intermedio, más la ruta más corta desde ese
nodo intermedio hasta el nodo de destino. Esta idea nos lleva a una
estructura recursiva que podemos utilizar para calcular la ruta más corta
entre todos los pares de nodos.

La programación dinámica nos permite almacenar y reutilizar las

soluciones a los subproblemas, evitando así el cálculo repetitivo y
optimizando el proceso de encontrar la ruta más corta. Esto se logra
mediante la construcción de una matriz de distancias mínimas, donde
cada entrada representa la distancia mínima entre dos nodos.

Una vez que hemos calculado esta matriz, podemos determinar la

ruta más corta entre cualquier par de nodos simplemente siguiendo las
conexiones óptimas de nodo en nodo, Este caso lo podremos ver con
más detalle en el ejemplo ilustrativo que se presenta más adelante.

Por otro lado, en este ensayo debemos explicar la formulación de

la ecuación recursiva, la cual tiene la forma que se expresa en la
imagen adjunta (Fig.2). Como es bien sabido, la ecuación recursiva de
retroceso/avance en programación dinámica es fundamental para
entender cómo se construyen las soluciones óptimas a partir de
subproblemas más simples. Esta técnica se basa en dos conceptos clave:
el principio de optimalidad de Bellman y la ecuación de Bellman.

El principio de optimalidad de Bellman establece que una solución

globalmente óptima debe incluir subproblemas que también sean óptimos.
Esto significa que si tomamos cualquier parte de una solución óptima, el
resto de la solución debe ser óptima para el subproblema restante.

La ecuación de Bellman es una herramienta matemática que

expresa la relación entre la solución óptima de un problema y las
soluciones óptimas de sus subproblemas. Esta ecuación define cómo se
combinan las soluciones a subproblemas más simples para construir una
solución óptima global.
 Fig. 2 Ecuaciones de relación recursiva

Finalmente, antes de comenzar con algunos ejemplo ilustrativos,

es importante dejar en claro el procedimiento para resolver problemas
de programación dinámica. En esencia, los problemas lineales son
aquellos en los que las relaciones entre las variables pueden expresarse
mediante ecuaciones lineales y se busca optimizar una función objetivo
lineal sujeta a un conjunto de restricciones lineales. Estos problemas son
fundamentales en la optimización de recursos limitados y la toma de
decisiones eficientes.

La programación dinámica se adapta a problemas lineales al

descomponerlos en subproblemas más simples y resolverlos de manera
recursiva. Este enfoque aprovecha la estructura lineal de los problemas
para optimizar la solución paso a paso, utilizando la información de los
pasos anteriores para tomar decisiones óptimas en cada etapa.

Al utilizar la programación dinámica para resolver problemas

lineales, se pueden aplicar diversos algoritmos y técnicas, como el
método del simplex, el método de la dualidad, la programación entera,
entre otros. Estos enfoques permiten encontrar soluciones óptimas en
situaciones donde los recursos son limitados y los objetivos son
maximizar los beneficios o minimizar los costos. Además, la programación
dinámica proporciona una herramienta poderosa para modelar y resolver
problemas lineales complejos con múltiples variables y restricciones. Esto
permite abordar desafíos del mundo real, como la planificación de la
producción, la asignación de recursos, entre otros, de manera eficiente y
efectiva.
Conclusiones:

En conclusión, la programación dinámica emerge como una

herramienta poderosa y versátil para abordar una amplia gama de
problemas de optimización en diversos campos. A lo largo de este
informe, hemos explorado los fundamentos, modelos y aplicaciones de
esta técnica, así como su relevancia en la resolución de problemas
lineales.

Desde su formulación inicial hasta su aplicación práctica, la

programación dinámica se basa en principios fundamentales como la
descomposición de problemas en subproblemas más simples, la
recursividad y la optimización de las soluciones locales. Estos principios
proporcionan un marco sistemático y eficiente para encontrar soluciones
óptimas en problemas complejos y multidimensionales.

Los modelos de programación dinámica, como el problema del

camino más corto, la mochila y la secuencia de producción, ofrecen
enfoques específicos para abordar diferentes tipos de problemas de
optimización. Estos modelos se adaptan a una variedad de contextos y
requisitos, desde la logística hasta la gestión de inventarios,
proporcionando soluciones eficientes y efectivas.

Además, el desarrollo teórico de la ecuación recursiva de retroceso

en programación dinámica, como lo expuesto por Taha, nos permite
comprender cómo se construyen las soluciones óptimas a partir de
subproblemas más simples, utilizando principios de optimalidad y
ecuaciones de Bellman.
Referencias:

● Hillier, J (2010). Investigación de Operaciones. (9 ed). México:

McGraw-Hill. Recuperado de enlace
● Moskowits, H (2011). Investigación de Operación. (8 ed). México:
McGraw-Hill.
● Taha, H (2011). Investigación de Operaciones. Madrid, España:
Addison-Wesley iberoamericana. Recuperado de enlace
● Wayne. W (2004). Investigación de Operaciones. Aplicaciones y
Algoritmos.(4 ed). Editorial Thomson ediciones. Recuperado de
enlace