Programación Dinámica
Determinística
1. Introducción
La programación dinámica es una técnica de resolución de problemas utilizada
para optimizar decisiones secuenciales. Es decir, es útil cuando un problema
puede dividirse en etapas, y las decisiones tomadas en una etapa afectan a las
etapas siguientes. Esta técnica ha demostrado ser muy eficaz para enfrentar
problemas complejos en diferentes áreas como la administración, la ingeniería,
la economía, la informática, entre otras.
En este informe se presenta el enfoque determinístico de la programación
dinámica, es decir, cuando todos los datos y condiciones del problema son
conocidos con certeza. También se explica cómo se diferencia de su versión
estocástica, donde interviene la incertidumbre, y se mencionan algunas de sus
aplicaciones más comunes.
1.1. Objetivos del informe
- Comprender los fundamentos teóricos de la programación dinámica determinística.
- Diferenciar la programación dinámica determinística de su versión estocástica.
- Ilustrar sus aplicaciones en problemas reales como planificación de producción, ruteo,
control de inventarios y asignación de recursos.
- Resolver paso a paso un problema práctico aplicando esta técnica.
1.2. Importancia de la programación dinámica en la toma de decisiones
En muchos contextos reales, las decisiones no se toman de manera aislada.
Una elección hoy puede afectar las opciones disponibles mañana. La
programación dinámica permite resolver estos problemas secuenciales
optimizando cada etapa, garantizando que el resultado final sea el mejor posible.
Además, esta técnica ayuda a tomar decisiones más informadas, especialmente
cuando se deben asignar recursos limitados o minimizar costos en situaciones
que se desarrollan a lo largo del tiempo. Al dividir un problema complejo en
subproblemas más simples, facilita el análisis y la solución óptima del conjunto.
2. Generalidades de la Programación Dinámica
2.1. Concepto y origen de la programación dinámica determinística y
estocástica
La programación dinámica fue desarrollada por Richard Bellman en la década de
1950 como una herramienta para resolver problemas de decisiones múltiples en
etapas. Su propósito era encontrar soluciones eficientes a problemas complejos
que no podían abordarse mediante métodos convencionales.
Existen dos tipos principales:
- Programación Dinámica Determinística: Se basa en la suposición de que toda
la información sobre el problema es conocida y no varía con el tiempo. No hay
incertidumbre en los datos. Las decisiones se toman considerando que los
resultados son predecibles.
- Programación Dinámica Estocástica: Se utiliza cuando algunos aspectos del
problema son inciertos o aleatorios, como la demanda, los precios o el clima.
Aquí, se trabaja con probabilidades y escenarios posibles, y se busca una
política de decisión que sea óptima en promedio o en el largo plazo, tomando en
cuenta esa incertidumbre.
2.2. Diferencias entre programación dinámica determinística y estocástica
Característica Determinística Estocástica
Información del Conocida con certeza Incierta o aleatoria
problema
Resultados esperados Predecibles Sujetos a variabilidad y
riesgo
Tipo de decisiones Basadas en datos fijos Basadas en
probabilidades y
escenarios posibles
Herramientas utilizadas Tablas, ecuaciones de Expectativas,
recurrencia distribuciones de
probabilidad
Solución Óptima exacta para Óptima en promedio o
datos fijos robusta frente a
incertidumbre
Ejemplo típico Producción con Producción con
demanda conocida demanda incierta
2.3. Aplicaciones comunes
La programación dinámica determinística tiene muchas aplicaciones en áreas
donde las decisiones deben tomarse en secuencia y los datos son conocidos.
Algunas de las más relevantes son:
- Gestión de inventarios: Determinar cuántas unidades de un producto se deben
pedir en cada periodo para minimizar costos de almacenamiento y faltantes,
asumiendo que la demanda es fija.
- Asignación de recursos: Distribuir de manera óptima un presupuesto entre
varios proyectos o departamentos, conociendo los retornos de cada uno.
- Planeación de la producción: Decidir cuánto producir en cada etapa para
cumplir con la demanda futura al menor costo posible.
- Optimización de rutas: Encontrar el camino más corto o económico en redes de
transporte, como el caso clásico del problema del viajero (TSP).
- Finanzas: Tomar decisiones de inversión o ahorro a lo largo del tiempo,
sabiendo con certeza los rendimientos o tasas de interés.