PROGRAMACION DINAMICA
DETERMINISTICA
CARRERA:
[Link] DE DATOS
[Link] GAXIOLA
INTEGRANTES:
RIVERA ARELLANO MIGUEL
ESQUERRA AMARILLAS JUAN
RODRIGUEZ RAMOS JAEL
CARDOZA RIOS GABRIEL
INTRODUCCIÓN A LA PROGRAMACIÓN DINÁMICA (PD)
La programación dinámica es un método de solución de problemas que permiten
descomponer un modelo matemático de gran magnitud, que puede ser muy difícil
de resolver, en diversos problemas más pequeños que por lo general son de
resolución mucho más fáciles. Además, el método de programación dinámica
permite descomponer el problema de manera que una vez que se han resuelto
los problemas menores se tiene la solución óptima para el problema mayor,
principio de optimalidad. Cada uno de tales problemas más pequeños que se
crean, se identifican con una etapa del procedimiento de solución de la
programación dinámica. Con frecuencia, tales etapas se crean por el hecho de
que se debe tomarse una secuencia de decisiones en el transcurso del tiempo.
En la mayor parte de los casos, no es posible considerar a estos problemas más
pequeños como si fueran completamente independientes de los demás y es aquí
en donde el método de la programación dinámica resulta útil.
EJEMPLO
Supóngase que hay 30 cerillos en una mesa. Se comienza tomando 1,2 o 3.
Entonces el oponente debe tomar 1, 2 o 3 cerillos. Continuando de este modo hasta
que se toma el último cerillo. El perdedor es el jugador que toma el último cerillo.
¿Cómo se puede estar seguro (si mi turno es el primero) de ganar el juego?
SOLUCION
SI PUEDO ASEGURAR QUE EL TURNO DE MI CONTRARIO SEA CUANDO QUEDA UN
CERILLO, GANARÉ. DANDO UN PASO HACIA ATRÁS, SI PUEDO ASEGURAR QUE SEA EL
TURNO DE MI CONTRARIO CUANDO QUEDEN 5 CERILLOS, GANARÉ. LA RAZÓN DE ELLO
ES QUE INDEPENDIENTEMENTE DE LO QUE HAGA CUANDO QUEDEN 5 CERILLOS,
PUEDO ASEGURAR QUE CUANDO SEA SU SIGUIENTE TURNO QUEDARÁ SÓLO UN
CERILLO, ¿POR QUÉ? IGUALMENTE, PUEDO HACER QUE MI CONTRARIO JUEGUE
CUANDO QUEDEN 5, 9, 13, 17, 21, 25 O 29 CERILLOS. TENGO SEGURA LA VICTORIA.
ASÍ, NO PUEDO PERDER SI ESCOJO 30-29=1 CERILLO EN MI PRIMER TURNO. DESPUÉS
TAN SÓLO ME ASEGURO DE QUE MI CONTRARIO SIEMPRE TENGA 29, 25, 21, 17, 13, 9 O
5 CUANDO SEA SU TURNO.
HISTORIA
La PD fue desarrollada por Richard Bellman y Dantzing. Sus importantes
contribuciones sobre esta técnica cuantitativa de toma de decisiones se publicaron en
1957 en su libro del primer autor denominado “Dynamic programming”.
Inicialmente a la PD se le denomino programación lineal estocástica (es una técnica de
optimización que aplica la programación dinámica a problemas de control en tiempo
discreto donde el sistema está sujeto a incertidumbre aleatoria) o problemas de
programación lineal con incertidumbre.
La programación dinámica determina la solución óptima de un problema de n variables
descomponiéndola en n etapas, con cada etapa incluyendo un subproblema de una sola
variable. La principal contribución de la PD es el principio de optimalidad, el cual
establece que una política optima consiste en subpoliticas optimas, un marco de
referencia para descomponer el problema en etapas.
CARACTERISTICAS DE LOS PROBLEMAS DE PROGRAMACION DINAMICA:
Las características de la programación dinámica se emplean para formular e identificar la
estructura de los problemas de este tipo.
-. Características básicas que distinguen a los problemas de programación dinámica.
1.- El problema se puede dividir en etapas que requieren una política de decisión en cada una de
ellas. En muchos problemas de programación dinámica, la etapa es la cantidad de tiempo que
pasa desde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.
2.- Cada etapa tiene cierto número de estados asociados a ella. Por estado se entiende la
información que se necesita en cualquier etapa para tomar una decisión optima.
3.- El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado
asociado con la siguiente etapa (tal vez de acuerdo con una distribución de probabilidad).
4.-El procedimiento de solución está diseñado para encontrar una política óptima para el problema
completo, es decir, una receta para las decisiones de la política optima en cada etapa para cada
uno de los estados posibles.
CARACTERISTICAS DE LOS PROBLEMAS DE PROGRAMACION DINAMICA:
5.- Dado el estado actual, una política óptima para las etapas restantes es independiente de
la política adoptada en etapas anteriores. En general en los problemas de PD, el
conocimiento del estado actual del sistema expresa toda la información sobre su
comportamiento anterior, y esta información es necesario para determinar la política optima
de ahí en adelante.
6.-El procedimiento de solución se inicia al encontrar la política óptima para la última etapa.
La política óptima para la última etapa prescribe la política optima de decisión para cada
estado posible en esa etapa.
7.-se dispone de una relación recursiva que indica la política óptima para la etapa dada la
política óptima para la etapa (n + 1).
QUE ES LA PROGRAMACION DINAMICA:
Es una técnica matemática útil que resuelve una serie de decisiones secuenciales, cada una de las cuales afecta las
decisiones futuras.
Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximiza la
efectividad total.
En este caso se profundiza sobre el enfoque de programación dinámica en los problemas determinísticos, en donde
el estado en la siguiente etapa está completamente determinado por el estado y la política de decisión de la etapa
actual.
Algunas de las aplicaciones de programación dinámica determinística son:
Modelo de volumen-carga “Mochila”
Modelo del tamaño de la fuerza de trabajo
Modelo de reposición de equipos
Modelo de inversión
Modelos de inventarios
A medida que se presente cada aplicación, es importante prestar atención a los tres elementos básicos de un modelo
de PD:
Definición de las etapas
Definición de las políticas o alternativas
Definición de los estados para cada etapa
EL PROBLEMA DE LA DILIGENCIA:
Un problema construido especialmente por el profesor Wagner de la universidad
de Stanford para ilustrar las características e introducir la terminología de la PD
es el problema de la diligencia.
Este problema se refiere a un vendedor mítico que tuvo que viajar hacia el oeste
utilizando como medio de transporte una diligencia, a través de tierras hostiles,
en el último cuarto del siglo XIX. Aun cuando su punto de partida y destino eran
fijos, tenía un número considerable de opciones para elegir que estados (o
territorios que posteriormente se convirtieron en estados) recorrer en su ruta.
PROBLEMA DE LA DILIGENCIA REPRESETACION GRAFICA:
Nota: Rutas posibles, en donde cada estado se representa por un bloque numerado.
DE LA ILUSTRACIÓN SE PUEDE
OBSERVAR QUE EL VIAJE SE
PUEDE REALIZAR EN 4 ETAPAS,
PARTIENDO DEL ESTADO 1 HASTA
SU DESTINO EN EL ESTADO 10:
PRIMERA ETAPA: ESTADOS 1 Y
(2,3,4)
SEGUNDA ETAPA: ESTADOS
(2,3,4) Y (5,6,7)
TERCERA ETAPA: ESTADOS
(5,6,7) Y (8,9)
CUARTA ETAPA: ESTADO (8,9)
Y 10
PRINCIPIO DE OPTIMALIDAD DE BELLMAN
El principio de optimalidad de Bellman se define como un concepto fundamental
que permite sustituir las evaluaciones simultáneas de todos los controles óptimos
por una secuencia de evaluaciones locales de controles óptimos en diferentes
etapas de la programación dinámica. Este principio es crucial para establecer la
existencia de potenciales de rendimiento óptimos y derivar ecuaciones de
programación dinámica relevantes.
DEFINICIÓN DEL PROBLEMA Y ETAPIFICACIÓN
Identificar las etapas Definir los estados
El problema general debe poder En cada etapa , se deben identificar los posibles
dividirse en una secuencia de etapas o estados en los que se puede encontrar el
periodos de tiempo finitos. El número sistema. Los estados son la información
de etapas puede ser fijo o variable. necesaria para tomar decisiones óptimas en las
etapas restantes, independientemente de cómo
se llegó a ese estado.
Definir las decisiones Definir la función objetivo y la función de
transición
En cada estado de cada etapa, se Establecer la métrica a optimizar (maximizar o
identifican las acciones o decisiones minimizar, por ejemplo, costo o recompensa) y
cómo una decisión en un estado lleva a un nuevo
posibles que se pueden tomar.
estado en la siguiente etapa.
SOLUCION POR ETAPAS
ANÁLISIS DATO 1
[Link] ETAPAS 2. DEFINIR LOS ESTADOS
Una etapa es cada nivel del recorrido desde Buenaventura La ciudad en la que se encuentra el paquete en
hasta Bogotá. cada etapa.
En el diagrama, las ciudades están organizadas en niveles: Entonces:
→
Etapa 1: Ciudad inicial Buenaventura Etapa 1: estado = Buenaventura
Etapa 2: Ciudades posibles desde Buenaventura → Cali, Etapa 2: estados = {Cali, Medellín, Armenia}
Medellín, Armenia Etapa 3: estados = {Ibagué, Pereira,
Etapa 3: Ciudades que siguen → Ibagué, Pereira, Manizales}
Manizales Etapa 4: estado = Bogotá (final)
Etapa 4: Ciudad final→ Bogotá
3. DEFINIR LAS DESICIONES 4. FUNCION OBJETIVO Y TRANSICION
la decisión es escoger a qué ciudad moverse desde el Función objetivo
estado actual, siempre siguiendo las conexiones Minimizar el costo total de envío del paquete desde
permitidas. Buenaventura hasta Bogotá.
Ejemplos: Es decir:
Desde Buenaventura puedes decidir ir a: Minimizar ∑ costos de los arcos
Cali (73)
Medellín (310) Función de transición
Armenia (166) La función que indica cómo se pasa de un estado a otro:
Nuevo estado = ciudad a la que lleva la decisión
METODOS DE SOLUCION
RECURSION HACIA ATRAS:
La recursión hacia atrás es el método clásico de la programación dinámica. Consiste en
comenzar por la última etapa de un problema y retroceder etapa por etapa hasta llegar al
estado inicial. La idea es calcular la función de costo futuro, se parte de un valor final
conocido, y se “desenrolla” hacia atrás.
¿Cuándo usar recursión hacia atrás? Cuando el número total de etapas del problema
está claramente definido y cuando se conoce el costo final o las condiciones del último
estado.
METODOS DE SOLUCION
RECURSION HACIA ADELANTE:
La recursión hacia adelante sigue el proceso contrario, comienza desde el estado inicial
y va construyendo los estados alcanzables en las etapas siguientes. En cada paso, se
generan todos los posibles estados futuros que resultan de las decisiones tomadas y se
actualiza el costo mínimo asociado a cada uno.
¿Cuándo usar recursión hacia delante? Cuando el estado final no está definido, pero
sí el inicial y cuando los estados futuros se generan naturalmente desde el estado
inicial.
COMPLEJIDAD GENERAL
¿Cuál es la complejidad general?
La complejidad general es una medida del tiempo y la memoria que un
algoritmo necesita para resolver un problema, dependiendo del tamaño del
mismo. La fórmula general es : O(T⋅S⋅A).
T: es el número de etapas totales del problema
S: el número de estados por etapas
A: el número total de decisiones por estado.
Si el inicio y final ya estan definidos, ¿qué metodo utilizo?
Recursividad hacia atras, porque si el final está definido, es más eficiente
empezar desde allí y retroceder, es mejor porque puede partir de un costo final
conocido y luego aplicar la ecuación de Bellman hacia atrás evitando generar
estados innecesarios.
EJEMPLOS CLÁSICOS
1. Problema del inventario determinista
Planteamiento: Una empresa debe decidir cuánto producir o cuánto pedir de un
producto en cada periodo para satisfacer la demanda conocida (determinista),
minimizando costos como:
Costo de producción o pedido, costo de mantener inventario, costo de faltantes (si se
permitieran)
El estado es el nivel de inventario, la decisión es cuánto producir o pedir, y la transición
es:
Q= Cantidad economica de pedido
K= Demanda anual
D= Costo de realizar un pedido
G= Costo de almacenamiento
EJEMPLOS CLÁSICOS
2. Problema del camino mínimo (algoritmo de Dijkstra)
Planteamiento: Aunque Dijkstra no se suele presentar como programación dinámica, es
un ejemplo perfecto de programación dinámica determinista hacia adelante. Encontrar
la ruta de menor costo desde un nodo inicial a todos los demás en un grafo con pesos
positivos. El estado es el nodo actual, la decisión es qué nodo visitar, y el costo es el
peso del arco.
EJEMPLOS CLÁSICOS
3. Problema de asignación de recursos
Planteamiento: Se tienen recursos limitados y varias actividades o proyectos que
pueden recibir una parte de esos recursos. Cada cantidad asignada genera cierto
beneficio, y se quiere maximizar el beneficio total. El estado es la cantidad de recursos
disponibles, la decisión es cuánto asignar a cada proyecto, y se resuelve por etapas (un
proyecto por etapa).
EJEMPLOS CLÁSICOS
4. Problema del corte de varillas (Rod Cutting Problem)
Planteamiento: Dada una barra de longitud n y una tabla con el precio de venta de cada
longitud posible, queremos cortarla en piezas para maximizar el ingreso total. El estado
es la longitud restante y la decisión es dónde hacer el primer corte.
4. ELEMENTOS DE UN MODELO DE PDD
Estado
El estado dentro de un modelo de PDD representa la situación actual del sistema en
una etapa específica y resume toda la información necesaria para decidir qué acción
tomar. Esto se basa en la propiedad de Markov, la cual establece que el futuro del
sistema depende únicamente del estado actual y no de cómo se llegó a él. Por ello, el
estado debe ser completo, relevante y mínimo: contiene solo los datos esenciales para
avanzar en el proceso de decisión. A medida que se toman decisiones y se pasa de una
etapa a otra, el estado cambia. Algunos ejemplos de estado incluyen el inventario
disponible en un periodo, la posición actual en una ruta o la cantidad de recursos
restantes en un proceso.
4. ELEMENTOS DE UN MODELO DE PDD
Decisiones
son las acciones que el investigador de decisiones puede elegir en cada etapa para
influir en la evolución del sistema. Estas decisiones determinan cómo cambia el estado
actual hacia el siguiente y afectan tanto los costos como los resultados finales del
proceso. Cada decisión debe ser viable según las restricciones del problema y debe
seleccionarse con el objetivo de optimizar la función objetivo. Ejemplos de decisiones
incluyen cuánto producir en un periodo, qué ruta tomar en un trayecto o cuánto
recurso asignar a una actividad.
4. ELEMENTOS DE UN MODELO DE PDD
Función de Transición
La función de transición determina el nuevo estado del sistema después de tomar una
decisión en una etapa determinada.
Se suele denotar como:
Donde:
xt= estado actual en la etapa t
ut= decisión tomada en la etapa t
xt+1 = estado resultante en la siguiente etapa
ft= función que describe cómo el estado cambia
4. ELEMENTOS DE UN MODELO DE PDD
ejemplo
Ejemplo simple
Imagina que estás administrando un inventario:
xt= cantidad de productos en bodega
ut= cantidad de productos a pedir
xt+1=xt+ut−demanda
Aquí, la función de transición muestra cómo el inventario cambia de un periodo a otro
según la decisión de cuánto pedir.
4. ELEMENTOS DE UN MODELO DE PDD
Funcion de costo
La función de costo asigna un valor numérico a cada decisión que tomas en un estado y
etapa determinados. Representa el “precio” o “costo” de moverse de un estado a otro
tomando cierta acción.
Se suele denotar como:
Donde:
xt= estado actual en la etapa t
ut= decisión tomada en la etapa t
gt(xt,ut) = costo asociado a esa decisión
4. ELEMENTOS DE UN MODELO DE PDD
Funcion de costo ejemplo
Siguiendo el ejemplo del inventario:
xt= cantidad de productos en bodega
ut= cantidad de productos a pedir
gt(xt,ut)=costo pedido+costo almacenamiento
Así, cada decisión de cuánto pedir tiene un costo asociado, y la programación dinámica
busca la secuencia de pedidos que minimice el costo total.
4. ELEMENTOS DE UN MODELO DE PDD
Restricciones
Las restricciones en un modelo de Programación Dinámica Determinística son las
condiciones o limitaciones que deben cumplirse al tomar decisiones en cada etapa.
Estas restricciones pueden estar relacionadas con recursos disponibles, capacidades
máximas, tiempos, costos u otras condiciones específicas del problema. Su función es
restringir el conjunto de decisiones viables, asegurando que las soluciones propuestas
sean factibles y coherentes con la realidad del sistema. Por ejemplo, una restricción
puede limitar la cantidad de producto que se puede fabricar en un periodo por la
capacidad de la planta, o establecer un límite en el presupuesto disponible para asignar
recursos. Cumplir estas restricciones es esencial para garantizar que el resultado final
del modelo sea aplicable y correcto.
4. ELEMENTOS DE UN MODELO DE PDD
Funcion Objetivo
es la expresión matemática que se busca maximizar o minimizar a lo largo de todas las
etapas del proceso. Representa el criterio de desempeño del sistema, como el costo
total, la ganancia, el tiempo, la eficiencia o cualquier medida que se quiera optimizar. La
función objetivo se calcula en función de los estados y las decisiones tomadas, y su
optimización guía la selección de la mejor secuencia de decisiones a lo largo de todas las
etapas. Por ejemplo, puede buscar minimizar los costos de producción acumulados,
maximizar las ganancias en un plan de inversión o reducir el tiempo total de recorrido
en un problema de rutas.
5. FORMULACION MATEMATICA
Ecuación de Bellman determinista
La ecuación de Bellman determinista es la fórmula central de la Programación Dinámica
Determinística que permite calcular de manera recursiva el valor óptimo del problema
en cada etapa. Establece que el valor óptimo en un estado dado es igual al mínimo o
máximo del costo o beneficio inmediato de tomar una decisión más el valor óptimo del
estado siguiente.
Se puede expresar de la siguiente manera:
donde:
Vt(s) es el valor óptimo en el estado s en la etapa t
A(s) es el conjunto de decisiones viables en el estado s
C(s,a) es el costo o beneficio inmediato de tomar la decisión a en el estado s.
s′ es el estado siguiente, determinado por la función de transición s′=f(s,a).
5. FORMULACION MATEMATICA
Interpretacion a fondo de cada termino
Vt(s): Representa el valor óptimo acumulado desde la etapa t en el estado s hasta el
final del horizonte del problema. Es decir, la mejor “ganancia” o el menor “costo”
posible partiendo de ese estado.
A(s): Es el conjunto de decisiones viables que se pueden tomar cuando el sistema se
encuentra en el estado s. Limita las opciones a aquellas que cumplen las
restricciones del problema.
C(s,a): Es el costo o beneficio inmediato de tomar la decisión a en el estado s.
Representa el efecto directo de la acción antes de considerar etapas futuras.
s′: Es el estado siguiente, que resulta de aplicar la decisión a al estado actual s según
la función de transición del sistema (s′=f(s,a)).
min o max: Indica que se selecciona la decisión que minimiza el costo o maximiza el
beneficio, de acuerdo con el objetivo del problema.
5. FORMULACION MATEMATICA
Horizonte finito vs. infinito
el horizonte se refiere al número de etapas o periodos que se consideran para tomar
decisiones:
Horizonte finito: Se analiza un número limitado de etapas, desde el inicio hasta un
punto final definido. Cada etapa tiene un impacto conocido sobre las siguientes, y el
proceso termina en un estado final donde se evalúa la función objetivo. Este
enfoque es útil cuando se planifica sobre un periodo específico, como un año fiscal,
un proyecto con duración determinada o un número limitado de movimientos en un
juego.
Horizonte infinito: Se considera un número ilimitado de etapas, y el proceso se
evalúa de manera indefinida. Aquí, la función objetivo generalmente se ajusta
mediante descuentos o criterios de promedio para garantizar que el valor total
converja. Este enfoque se aplica cuando se busca una política estable a largo plazo,
como en la gestión continua de inventarios, control de producción perpetuo o
decisiones económicas recurrentes.
VENTAJAS
1. Garantía de optimalidad
La PDD produce soluciones óptimas globales, siempre que:
- Se cumpla el principio de optimalidad de Bellman.
- El modelo esté bien definido (estados, decisiones, transiciones y recompensas determinísticas).
2. Estructura clara y descomposición del problema
La PDD divide el problema en subproblemas más pequeños, lo que:
- Facilita el análisis.
- Reduce trabajo repetido.
3. Flexibilidad para problemas secuenciales
Es adecuada para problemas que se resuelven paso a paso, donde cada etapa depende del estado anterior.
Muy útil en:
- Inventarios
- Procesos de producción
- Caminos mínimos
LIMITACIONES
1. Curse of dimensionality (maldición de la dimensionalidad)
El número de estados y decisiones crece exponencialmente con:
- el número de variables
- el número de etapas
- el tamaño del espacio de estados
Esto vuelve la PDD impráctica cuando:
- Hay muchas variables de estado.
- El horizonte temporal es largo.
- Los estados son continuos.
2. Requiere transiciones determinísticas
La PDD básica solo funciona cuando el resultado de una decisión siempre es el mismo (no hay incertidumbre).
Si hay incertidumbre, se necesita Programación Dinámica Estocástica o MDPs.
[Link]ícil de aplicar si no hay estructura recursiva
Si el problema no cumple el principio de optimalidad, la PDD no funciona.
También falla si el problema no puede ser descompuesto en etapas secuenciales claras.
CASOS ADECUADOS
El problema tiene pocas variables de estado o estados discretizados.
Existe una recursión clara entre etapas.
Las transiciones entre estados son determinísticas.
Se necesita una solución óptima exacta.
El horizonte temporal es moderado.
Ejemplos:
Problemas de rutas y caminos mínimos.
Control de inventarios simple.
Problemas de producción secuenciales.
Optimización de costos en sistemas deterministas.
CASOS NO ADECUADOS
El número de estados es demasiado grande →aparece curse of dimensionality.
Las transiciones son aleatorias o inciertas (mejor usar un MDP).
El problema no tiene:
estructura recursiva
etapas bien definidas.
CONCLUSIONES
La Programación Dinámica Determinística es una herramienta poderosa para resolver problemas complejos
que requieren tomar decisiones secuenciales. Su principal fortaleza está en la descomposición del problema en
etapas, aplicando el principio de optimalidad de Bellman para garantizar soluciones óptimas.
Aunque ofrece gran claridad estructural y precisión, su uso es adecuado solo cuando el número de estados y
decisiones es manejable y el sistema es completamente predecible. Cuando la complejidad crece demasiado o
existe incertidumbre, la PDD se vuelve limitada y se requieren otros métodos.
La PDD es ideal para problemas bien definidos, con etapas claras y transiciones deterministas, permitiendo
encontrar soluciones exactas y óptimas de manera sistemática.
¡MUCHAS
GRACIAS!
Dudas preguntas....