Sem 05 - Introdución A La Programación Dinámica

Investigación de Operaciones II
Introducción a la Programación Dinámica
Ing. Luis Mantilla Rodriguez

[email protected]
Ing. Industrial
Logro de Aprendizaje
Al término de la sesión, el estudiante plantea y resuelve Casos Generales de PDD en base a una
situación problemática empresarial ó de cualquier índole, relacionando de manera coherente los
elementos del modelo de PDD, encontrando la solución óptima e interpretándola correctamente.
¿Que es Programación Dinámica (PD)?

Técnica que resuelve diversos problemas de Optimización, llegando a la solución trabajando hacia
atrás, es decir partiendo del final del problema hacia el principio. Proporciona un procedimiento
sistemático para determinar la combinación de desiciones que maximiza el beneficio total ó
minimiza el costo total en un problema.
Resuelve problemas de Redes, Inventarios, Asignación de Recursos, Producción, Reemplazo de

Equipos, etc. La PD encuentra la solución óptima de un problema con “n” variables
descomponiéndolo en “n” etapas, donde cada etapa es un Subproblema de una sola variable. La
naturaleza de la etapa difiere de acuerdo con el tipo de problema que se aborde .
Elementos de un modelo de Programación Dinámica
Elemento
Etapa (n) n=1 n=2 n=3 n=4
Estado (sn)
Evolución del sistema

Variable decisión (xn)
Función recurrente (fn) Etapa es el período de tiempo, lugar, contexto, fase ó situación en
donde se produce un cambio debido a una decisión (xn).
Elemento
Etapa (n)
Estado (sn)

El estado muestra la situación actual del sistema cuando nos

Función recurrente (fn) encontramos en la “etapa n”. Cada etapa tiene su propio estado (ó
estados). Tiene información que enlaza las etapas y que permite
tomar las decisiones. El estado varia según la situación que se ha
de modelar.
Elemento
Etapa (n)
Estado (sn)
Hacen referencia a toma de decisiones (o política de decisión) que

Función recurrente (fn) se producen en una etapa y que provoca un cambio en el estado
actual del sistema. En cada etapa se toma solamente una desición y
cada etapa tiene su propia variable de desición.
Elemento
Etapa (n)
Estado (sn)

Función recurrente (fn) Refleja el comportamiento del sistema en función de los estados y
de las variables de decisión. Cada etapa tiene su propia función
recurrente. Relaciona el costo o la contribución ganada durante
alguna etapa con el costo o la contribución ganada en la etapa
posterior de forma acumulativa.
Fases de un problema de Programación Dinámica
1. Fase de ANALISIS : Se empieza por la última etapa y se analiza todas las opciones posibles
de dicha etapa. Después se pasa a la etapa anterior, se evalua todas las opciones posibles y
se agrega a los resultados obtenidos previamente. Asi sucesivamente hasta llegar a la etapa 1.
2. Fase de DECISIÓN : Aquí los cálculos se realizan al contrario (desde el principio hasta el final).
Empezamos por la etapa 1 y se decide por la mejor opción posible, y asi se va pasando por
todas las etapas eligiendo la mejor opción posible en cada una.
Llegado a éste punto obtenemos la solución final al problema.

Caso 1: El Problema de la Ruta más Corta

Suponga que debemos seleccionar la ruta más corta entre dos ciudades. La red inferior muestra las rutas posibles
entre el nodo de inicio 1 y el nodo destino 7. Las rutas pasan por ciudades intermedias, representadas por los nodos
2 a 6. Este problema se puede resolver enumerando en forma detallada todas las rutas entre los nodos 1 y 7,
donde vemos que hay cinco rutas. Sin embargo, en una red mas grande, la enumeración exhaustiva no se puede
manejar tan fácilmente, haciendo más compleja su solución computacional.
Solución:
Resumen Etapa 1 :
Resumen Etapa 2 :
Solución:
Resumen Etapa 3 :
Conclusión y resultado final :

o Distancia más corta entre nodos 1 y 7 es: 21 millas.
o Determinemos la ruta óptima a seguir; para ello comenzaremos con el resumen de la etapa 3, donde el nodo 7
se conecta al nodo 5. En el resumen de la etapa 2 el nodo 4 se conecta al nodo 5; y en el resumen de la etapa
1 el nodo 4 se conecta al nodo 1. Por lo tanto la Ruta más Corta es :
Propiedades Básicas de los Cálculos de Programación Dinámica
1. Los cálculos en cada etapa son una función de las Rutas Factibles de dicha etapa y solo de
ésa etapa.
2. Una etapa actual esta conectada a la etapa inmediatamente precedente (no tiene en cuenta
las etapas anteriores).
La Ecuación Recursiva de Programación Dinámica

El ejercicio anterior muestra que los cálculos recursivos pueden expresarse matemáticamente de la siguiente
manera :
Etapas (n): El problema tiene 3 etapas, entonces n = 1,2,3

Estados (Sn): Cada uno de los nodos en cada etapa n
Variable desición (Xn): Desición de ir al nodo Sn estando en la etapa n
Función recurrente fn(Sn): Distancia mas corta al nodo Sn en la etapa n
Definimos : d(Sn-1,Sn) como la distancia del nodo Sn-1 al nodo Sn.
f0(S0 = 1) = 0 (en el nodo 1 la distancia es 0)

Recursividad “hacia atrás” (Retroceso)

 El caso anterior se desarrolló con la recursividad hacia adelante, donde los cálculos van de la
etapa 1 a la etapa 3.
 Ahora lo resolveremos por medio de la recursividad hacia atrás, comenzando en la etapa 3 y

terminando en la etapa 1, para llegar al mismo resultado.
 Aun cuando la recursividad hacia adelante parece más lógico, la mayor parte de la literatura de PD
utiliza la recursividad hacia atrás.
La Ecuación Recursiva Inversa para el mismo ejemplo es :
Etapa 3 :

Etapa 2 :

Etapa 1 :
La solución de la etapa 1 conecta la ciudad 1

con la ciudad 4. Luego, la solución de la etapa 2
conecta la ciudad 4 con la ciudad 5. Por último la
solución de la etapa 3 conecta la ciudad 5 con la
ciudad 7. La ruta óptima es 1,4,5,7 y la distancia
asociada es 21 millas.
Programación Dinámica Determinística PDD

[email protected]
Ing. Industrial
Programación Dinámica Determinística - PDD
El Problema de la Mochila
o Consiste en determinar los artículos más valiosos que una persona debe cargar en su mochila.
o Representa un modelo de asignación de recursos, los mismos que son limitados por varias actividades económicas.
o El objetivo es maximizar el rendimiento total.
o Conocido también como : problema del equipo de vuelo (determinar los artículos más valiosos que un piloto de avión
debe llevar a bordo), y problema de carga de un contenedor (determinar los artículos más valiosos que se cargarán
en un buque).
El Problema de la Mochila : Un barco de 4 Ton puede cargarse con uno o más de tres artículos. La siguiente tabla muestra
el peso unitario p en Ton y el ingreso unitario r en $ para cada artículo n. El objetivo es: Determinar que cantidad de
cada artículo debemos cargar al barco para maximizar el rendimiento total.
“No cargar unidades de

cualquier artículo, no genera
ningún ingreso”.
Solución : (Fase de Análisis)

Elementos del Modelo
Etapas (n) : C/u de los artículos a cargar en el barco
Variables (Xn) : Cantidad del artículo n a cargar en el barco Xn ≤ (W/pn)
Estado (Sn) : Capacidad de peso disponible en el barco en la etapa n.
Función Recursiva (fn) : Rendimiento máximo obtenido en la etapa n
Datos adicionales :
o Capacidad en peso del barco W = 4 Ton
o El límite de peso es la única restricción que liga a todas las etapas.
o Dado que pn y W son enteros, el estado Sn asume sólo valores enteros.
Solución (Fase de Análisis) – Etapa 3 :

o Función de Rendimiento = (14,000)(X3)


Solución (Fase de Desición)
Etapa 1 : Mejor desición cargar 2 und del

artículo 1, utilidad = $62000

artículo 2, peso disponible = 0

artículo 3, peso disponible = 0
PDD – Asignación de Recursos

[email protected]
Ing. Industrial
Una empresa a contratado a 3 personas para asignar a 3 tareas (A, B y C). Solamente se pueden asignar 2 personas
como máximo a una tarea. La utilidad que genera asignar 0, 1 ó 2 personas a una tarea se muestra en la siguiente
tabla :
¿Cuantas personas debemos asignar a cada tarea para Maximizar la Utilidad?
Solución : (Fase de Análisis) - Elementos del Modelo

o Etapas (n) : Cada una de las 3 Tareas a donde iremos asignando trabajadores
o Estados (en) : Cantidad de trabajadores disponibles para asignar en la etapa n
o Variables de Desición (Xn) : Cantidad de Trabajadores que se asignan en la etapa n
o Función Recursiva : (fn) : Rendimiento máximo obtenido en la etapa n
Solución : Etapa 3
f3(e3,X3) = Rendimiento (X3)
Solución : Etapa 2
f2(e2,X2) = Rendimiento (X2) + f*3(e2 - X2)
Solución : Etapa 1
f1(e1,X1) = Rendimiento (X1) + f*2(e1 – X1)

Solución : Fase de Desición
El valor obtenido en la Etapa 1, es el rendimiento óptimo

acumulado, por lo tanto la utilidad máxima que se puede
conseguir es 13, asignando 2 personas a esa etapa.
En la etapa 2, con solo 1 trabajador disponible, la mejor

desición es asignar 0 personas, por tanto sigue
quedando 1 persona por asignar en la etapa 3.
En la etapa 3, con 1 solo trabajador disponible, la mejor

desición es asignar 1 persona.
PDD – Producción e Inventarios

[email protected]
Ing. Industrial
Producción e Inventarios
Una compañía sabe que la demanda de su producto durante los próximos 4 meses será como sigue : Mes 1 = 1
und; Mes 2 = 3 und; Mes 3 = 2 und; Mes 4 = 4 und. Al principio de cada mes la empresa debe determinar
cuántas und. deben fabricarse en dicho mes. Durante cada mes, si se produce al menos 1 und, la empresa incurre
en un costo inicial de $3, mas $1 por cada und producida. Al final de cada mes cada und que queda en Inventario
ocasiona un costo de $0.50. Las limitaciones en la capacidad permiten producir un máximo de 5 und/mes. Las
dimensiones de la bodega restringen a mantener un inventario final máximo de 4 und. La empresa desea
determinar un Plan de Producción que cumpla con toda la demanda a tiempo y minimice la suma de Costos de
producción y almacenaje durante los cuatro meses. Suponga que al inicio del primer mes el Inventario inicial es =
0 und, y en el Mes 4 el inventario final debe ser = 0 und.
Solución : (Fase de Análisis) - Elementos del Modelo

Etapas (n) : C/u de los 4 meses que se va a determinar la producción e inventarios a mantener
Estados (Sn) : Inventario inicial al comienzo de la etapa n
Variables (Xn) : Cantidad a producir en la etapa n para minimizar costos de producción y almacenamiento
Función Recursiva (fn) : Costo total mínimo de producir, almacenar y cumplir con la demanda en la etapa n
Costo de Producción C(xn) : Costo de producir Xn und en la etapa n
Capacidad Almacén = 4 Und.

Capacidad Producc = 5 Und.
Costo Producción = C(Xn) = $3 + (1)(Xn) …. Cuando Xn > 0
Costo Producción = C(Xn) = 0 ……….…….. Cuando Xn = 0
Costo Almacenaje = $0.5 und
Costo Etapa = CAlmac. + CProd. + CEtapa Siguiente
Invent.Final = Invent.Inicial + Producción - Demanda
“La cantidad a producir en cada mes va a estar en función del Inventario Inicial, de la Demanda, de la Capacidad del
Almacenamiento, y de la Capacidad de Producción”
Solución : Etapa 4
Capacidad Almacén = 4 Und.

Capacidad Producc = 5 Und.
Costo Prod. C(Xn) = 3 + (1)(Xn); Xn > 0
Costo Prod. C(Xn) = 0; Xn = 0
 S4 = máximo 4, por inventario final mes anterior, además en la etapa 4 inv fin = 0 Costo Almacenaje = $0.5 und
 X4 = de 0 a 4, si llegamos con 0 producir 4, si llegamos con 4, producir 0.
Solución : Etapa 3
Ahora Ud. complete la etapa

3 (estados 3 y 4), y continúe
desarrollando el ejercicio
para las etapas 2 y 1.
GRACIAS POR SU ATENCION
• Ing. Luis A. Mantilla Rodriguez
• [email protected]
• Ing. Industrial

Sem 05 - Introdución A La Programación Dinámica

Cargado por

Copyright:

Formatos disponibles

Sem 05 - Introdución A La Programación Dinámica

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Sem 05 - Introdución A La Programación Dinámica

Cargado por

Copyright:

Formatos disponibles

Investigación de Operaciones II

Introducción a la Programación Dinámica

Ing. Luis Mantilla Rodriguez

¿Que es Programación Dinámica (PD)?

Resuelve problemas de Redes, Inventarios, Asignación de Recursos, Producción, Reemplazo de

Elementos de un modelo de Programación Dinámica

Etapa (n) n=1 n=2 n=3 n=4

Evolución del sistema

Elementos de un modelo de Programación Dinámica

Evolución del sistema

El estado muestra la situación actual del sistema cuando nos

Elementos de un modelo de Programación Dinámica

Hacen referencia a toma de decisiones (o política de decisión) que

Elementos de un modelo de Programación Dinámica

Variable decisión (xn)

Fases de un problema de Programación Dinámica

Llegado a éste punto obtenemos la solución final al problema.

Caso 1: El Problema de la Ruta más Corta

Conclusión y resultado final :

Propiedades Básicas de los Cálculos de Programación Dinámica

La Ecuación Recursiva de Programación Dinámica

Etapas (n): El problema tiene 3 etapas, entonces n = 1,2,3

Definimos : d(Sn-1,Sn) como la distancia del nodo Sn-1 al nodo Sn.

f0(S0 = 1) = 0 (en el nodo 1 la distancia es 0)

Recursividad “hacia atrás” (Retroceso)

 Ahora lo resolveremos por medio de la recursividad hacia atrás, comenzando en la etapa 3 y

Recursividad “hacia atrás” (Retroceso)

La Ecuación Recursiva Inversa para el mismo ejemplo es :

Recursividad “hacia atrás” (Retroceso)

Recursividad “hacia atrás” (Retroceso)

La solución de la etapa 1 conecta la ciudad 1

Programación Dinámica Determinística PDD

Ing. Luis Mantilla Rodriguez

“No cargar unidades de

Solución : (Fase de Análisis)

Solución (Fase de Análisis) – Etapa 3 :

Solución (Fase de Análisis) – Etapa 2 :

Solución (Fase de Análisis) – Etapa 1 :

Solución (Fase de Desición)

Etapa 1 : Mejor desición cargar 2 und del

Etapa 2 : Mejor desición cargar 0 und del

Etapa 3 : Mejor desición cargar 0 und del

PDD – Asignación de Recursos

Ing. Luis Mantilla Rodriguez

¿Cuantas personas debemos asignar a cada tarea para Maximizar la Utilidad?

Solución : (Fase de Análisis) - Elementos del Modelo

f1(e1,X1) = Rendimiento (X1) + f*2(e1 – X1)

Solución : Fase de Desición

El valor obtenido en la Etapa 1, es el rendimiento óptimo

En la etapa 2, con solo 1 trabajador disponible, la mejor

En la etapa 3, con 1 solo trabajador disponible, la mejor

PDD – Producción e Inventarios

Ing. Luis Mantilla Rodriguez

Solución : (Fase de Análisis) - Elementos del Modelo

Capacidad Almacén = 4 Und.

Costo Etapa = CAlmac. + CProd. + CEtapa Siguiente

Invent.Final = Invent.Inicial + Producción - Demanda

Capacidad Almacén = 4 Und.