Prog Dinamica

Vista previa del material en texto

PROGRAMACION DINAMICA (PD)
La programación Dinámica, es una técnica matemática
que se utiliza para la solución de problemas matemáticos,
en los cuales se toma una decisión de forma secuencial.
Es un procedimiento sistemático para determinar la
combinación de decisiones que maximice la “efectividad
global”.
Determina la solución óptima de un problema de n
variables de decisión, descomponiéndolo en n etapas,
cada etapa es un sub-problema de una sola variable.
A diferencia de programación lineal, no existe un planteo
matemático estándar, mas bien es un tipo de enfoque para
resolver problemas.
Programación Dinámica (PD)
Los cálculos en la PD se hacen recursivamente, en el sentido de
que la solución óptima de un sub-problema se utiliza como una
entrada para el siguiente sub-problema.
En el momento que se resuelva el último sub-problema, tendremos
la solución óptima para todo el problema.
En general, los sub-problemas se vinculan por medio de
restricciones (variables de estado). A medida que se avanza de
un sub-problema a otro, se debe verificar la viabilidad de estas
restricciones.
La Programación Dinámica parte de una pequeña porción del
problema, comenzando desde la etapa final y encuentra la
solución óptima para éste, gradualmente lo va ampliando, hallando
la solución óptima en curso, a partir de la anterior, hasta llegar a la
primera etapa.
Elementos que caracterizan el problema
1- Etapas: División del problema, con una decisión de la política requerida
en cada etapa.
2- Estado: es el que refleja la condición o estado de las restricciones que
enlazan las etapas. Representa la “liga” entre etapas, de tal manera que
cuando cada etapa se optimiza por separado la decisión resultante es
automáticamente factible para el problema completo.
3- El efecto de la decisión de una política es transformar el estado actual en
un estado asociado con la etapa siguiente.
4- La teoría fundamental de la programación dinámica es el Principio de
Optimalidad de Bellman, que nos indica básicamente como se puede
resolver un problema adecuadamente descompuesto en etapas utilizando
cálculos recursivos.
5- Se dispone de una relación recursiva que identifica la política óptima
para cada estado en la etapa n, dada la política óptima para cada estado en
la etapa n+1.
Función recursiva: fn (s, xn), es el costo total de la mejor política global para 
las etapas restantes, dado que se encuentra en el estado s, listo para iniciar 
la etapa n y selecciona a xn como el destino inmediato.
fn(s,xn) = c (s,xn)+ fn+1*
Optima : fn*(s)= min xn c (s;xn)+ f* n+1 (xn) 
Programación Dinámica Determinística
Problema de la ruta más corta
2
3
2
4
5
6
7
8
9
101 4
3
7
4
6
3
2
4
4 1
5
1
4
6
3
3
3
3
4
Etapa 1 Etapa 2 Etapa 3 Etapa 4
Variable de decisión: xn , n = 1, 2, 3, 4 son los destinos inmediatos en la etapa n. 
Cada etapa tiene asociado un costo que depende del estado actual y la decisión
(destino inmediato) a tomar en la etapa n
Función recursiva: fn (s, xn), es el costo total de la mejor política global para las
etapas restantes, dado que el vendedor se encuentra en el estado s, listo para
iniciar la etapa n y selecciona a xn como el destino inmediato.
s f4*(s) x4*
8 3 10
9 4 10
s \ x3
8 9
f3 
*(s,) x3 
*
5 4= 1+3 10=6+4 4 8 
6 9=6+3 7=3+4 7 9
7 6=3+3 7= 3+4 6 8
2
3
2
4
5
6
7
8
9
101 4
3
7
4
6
3
2
4
4 1
5
1
4
6
3
3
3
3
4
Etapa 4 : f4(s,x4) =c(s,x4)+f5*
Etapa 3 f3(s,x3) =c(s,x3)+f4*(x3)
Minimizar el costo total de 1 a 10
811=5+68=1+78=4+44
710=4+69=2+77=3+43
1112=6+611=4+711=7+42
f2 
*(s,x2)
65
s \ x2
7
1\ x1
f1(s,x1)= c(s,x1) + f2*(x1)
f1(1,x1)
2 3 4 
1
13=2+11 11 11 11
2
3
2
4
5
6
7
8
9
101 4
3
7
4
6
3
2
4
4 1
5
1
4
6
3
3
3
3
4
Etapa 2: f2(s,x2) =c(s,x2)+f3*(x3)
Etapa 1 
Solución optima, dos caminos posibles
Etapa 1: de 1 a 3 a 4
Etapa 2: de 3 a 5 , o de 4 a 5, 6
Etapa 3: de 5 a 8; o de 5 a 8; 6 a 9
Etapa 4: de 8 a 10; o de 9 a 10
Costo total mínimo es 11
Aplicaciones de PD
Para definir un problema debemos:
1. Definir las etapa: qué relaciones unen a las etapas?
2. Definir las decisiones (alternativas) en cada etapa
3. Definir los estados para cada etapa
4. Definir la Función Objetivo
Modelo de volumen - carga (Problema de la mochila)
Aborda el problema de cargar artículos en un medio de transporte (barco, avión,
mochila) con una capacidad de peso limitada. Cada artículo tiene un peso
determinado y produce un nivel de utilidad. El objetivo es cargar el transporte
con la carga más valiosa.
• Etapa: artículo
• Decisiones (alternativas): nº de unidades del artículo incluidas en la carga.
• Estado en la etapa: el peso total asignado a cada etapa.
• Función objetivo: Minimizar el costo total de la carga a transportar
Ejemplo: modelo de la mochila
Un barco de 4 toneladas se carga, con uno o más de tres artículos. La tabla
proporciona el peso por unidad wi en toneladas y la utilidad por unidad ri en
miles de dólares por el artículo i. Como se debe cargar el barco para
maximizar la utilidad total?
Como los pesos por unidad y el peso máximo asumen valores enteros, el
estado si solo puede asumir valores enteros.
Etapa 3: el peso exacto que se va a asignar a esta etapa no se conoce con
anticipación, pero será entre 0 y 4. Como w3 =1 ton/unidad, el nº máximo que
se puede cargar es[4/1]=4, lo que significa que los valores posibles de x3 son
0,1,2,3 y 4.
Entonces para la etapa 3; f3(s3)= max x3 {14 x3}
En la tabla se deben comparar las alternativas factibles para cada valor de s3.
Artículo wi ri
1 2 31
2 3 47
3 1 14
x1 x2 x3
S1 S2 S3 S4
s3\x3 0 1 2 3 4 f*3(s3) x3*
0 0 - - - - 0 0
1 0 1*14 - - - 14 1
2 0 14 2*14 - - 28 2
3 0 14 28 3*14 - 42 3
4 0 14 28 42 4*14 56 4
Solución
Articulo 3: f3(s3)= maxx3 { 14 x3 }
x1 x2 x3
S1 S2 S3 S4
Articulo 2: f2(s2)= maxx2 { 47 x2 + f3 (s3- 3 x2)} 
s2\x2 0 1 f2(s2) X2*
0 0 - 0 0
1 0+14 - 14 0
2 0+28 - 28 0
3 0+42 47+0 47 1
4 0+56 47+14 61 1
Articulo 1: f1(s1)= maxx1 { 31 x1 + f2 (s2 – 2 x1)} 
S1\x1 0 1 2 F1(s1) X1*
4 0+61 1*31+28= 59 2*31+0=62 62 2
Optimo: Articulo 1: 2
Articulo 2: 0
Articulo 3: 0 
Beneficio Máximo: 62$
Max
Modelo de inventario
Determinar cuántas unidades tener en inventario en cada período a fin de
minimizar costos y teniendo en cuenta condiciones de demanda y restricciones
de espacio.
Se aplica cuando la demanda varia de un periodo a otro, cuando la capacidad
productiva es inferior a la demanda de algún periodo, cuando existen costos de
set up asociados, costos de mantenimiento de inventario; etc.
Ejemplo
Una empresa debe decidir su política de producción e inventario para los
próximos tres meses, la empresa ha adquirido algunos compromisos importantes
de entrega para los meses: 3, 2, y 4 unidades respectivamente.
En el proceso productivo se incurre en costos de producción y de
almacenamiento, estos costos son:
• Costo de almacenamiento: corresponde al costo de oportunidad de mantener
el material en bodega (capital inmovilizado, perdidas, etc) su valor es hi por
unidad de producto-mes.
• Costo de producción: corresponde al costo unitario de producción de mano de
obra , materiales , equipos, etc
El valor inicial del inventario es cero.
Modelo de inventario
mes hi Ci
1 1 10
2 3 15
3 2 20
y3\x3 0 1 2 3 4 f*3(y3) x3*
0 - - - - 80=
4*20
4 80
1 - - - 60 - 3 60
2 - - 40 - - 2 40
3 - 20 - - - 1 20
4 0 - - - - 0 0
Solución
Etapa 3= periodo 3: 
f3(y3)= mixx3 { 20 x3+2 (y3+ x3-4) + f4* (y4)]
Restriccion para valores de X3
y3+x3= y4+4
y4 = 0
x3 + y3= 4 
x3 = 4 – y3
x3 ≥ 0; entero
x1 x2 x3
y1 y2 y3 y4 = 0
d1 = 3 d2 = 2 d3 = 4
y1+x1= y2+3
y2+x2= y3+2
y3+x3= y4+4 
y2\x2 0 1 2 3 4 5 6 f*2(y2) x2*
0 - - 110 108 106 104 102 102 6
1 - 95 93 91 89 87 - 87 5
2 80 78 76 74 72 - - 72 4
3 63 61 59 57 - 57 3
4 46 44 42 - - 42 2
5 29 27- - - - - 27 1
6 12 - - - - - - 12 0
Etapa 2= periodo 2 
f2(y2)= mixx2 { 15 x2+3 (y2+ x2 - 2) + f3* (y3)
y2+x2= y3+2 ; x2 = y3+ 2 – y2
Si y2 = 0; x2 = y3 + 2 ; y3 = 0, 1, 2, 3, 4 
Si y3 = 4 ; x2 = 6 
f2(y2)= 15 * 6 + 3 (0+ 6 - 2) + f3* (y3 = 4) = 90 + 3 * 4 + 0 = 102
Si y2 = 0 ; x2 = y3 + 2 ; y3 = 3 ; x2 = 5 
f2(y2)= 15 *5 + 3 (0+ 5 - 2) + f3* (y3 = 3) = 75 + 3 * 3 + 20 = 104
,,, 
Si y2= 6; x2 = y3 + 2 - 6 ; x2 = y3 - 4; por lo que solo puede ser y3 = 4;entonces x2 = 0
f2(y2)= 15 * 0 + 3 (6+ 0 - 2) + f3* (y3 = 4)
f2(y2)= 0 + 3* 4 + 0 = 12
Max valor de y2= 6, porque
x2 = y3+ 2 – y2 y max y3= 4
x2 = 4 + 2 – y2 entoces max y2 ≤ 6
y1\x1 3 4 5 6 7 8 9 f*1(s1) x1*
0 132 128 124 120 116 112 108 108 9
Etapa 1= periodo 1
f1(y1)= mixx1 { 10 x1+ 1 (y1+ x1 - 3) + f2* (y2)
y1+x1= y2+3 ; x1 = y2+ 3 – y1
El stock inicial es cero
y1= 0 y si y2= 0; x1 = 3
,,,
y1 = 0 y si y2 = 6; x1 = 9 
f1(y1)= 10 * 9+ 1 (0+ 9 - 3) + f2* (y2 = 6) = 90 + 1* 6 + 12 = 108
El costo de la política optima es de 108 $ para los próximos tres meses
Como x1 = 9 ; entonces 9 = y2+ 3 – y1; y1 = 0; y2 = 6; de la etapa 2; x2 = 0
x2 = y3+ 2 – y2 ; 0 = y3+ 2 – 6
→y3 = 4 , y de la tabla de la etapa 3, → X3 = 0
Por lo tanto la política optima es producir 9 unidades el mes 1, y los meses 
siguientes no producir, solo almacenar inventario para satisfacer los requerimientos
Modelo de reemplazo de equipos
Mientras más tiempo esté en servicio una máquina, más elevado será su costo
de mantenimiento y su producción será menor. Cuando una máquina llega a
cierta edad, puede resultar más económico reemplazarla. Por consiguiente, el
problema se reduce a determinar la edad más económica de la máquina. Se
considera utilidad y costo de operación anual, valor de recuperación y costo de
adquirir una máquina nueva.
Etapa: año i
Alternativas: se conserve o se reemplace la máquina al principio del año.
Estado en la etapa: es la edad de la máquina al principio del año i
Modelo de inversión (Modelo de asignación de recursos)
Invertir cantidades P1, P2,....Pn al principio de cada uno de los n años siguientes, en dos 
entidades financieras que pagan diferentes tasas de interés. El objetivo es diseñar un 
programa de inversión durante los próximos n años.
Etapa: año
Alternativas en la etapa: cantidades a invertir en cada entidad financiera.
Estado en la etapa: cantidad de capital disponible para invertir a principio de cada año.
Modelo de confiabilidad de un sistema
Determinar cuántas unidades (en paralelo) deben instalarse para maximizar la probabilidad
de que el sistema funcione (producto de las probabilidades de funcionamiento de los
componentes)
Programación Dinámica Probabilística
La mayoría de las actividades : industriales, comerciales, de
servicios, se encuentran en el caso de un futuro incierto, y si las
estimaciones lo permiten, aleatorio.
Es decir, un futuro para el cual los acontecimientos son previsibles
en términos de probabilidad.
La Programación Dinámica probabilística difiere de la determinística
en que el estado en la etapa siguiente no queda completamente
determinado por el estado y la decisión de la política en el estado
actual.
En cambio, existe una distribución de probabilidad para lo que
será el estado siguiente.
Cada etapa consta de dos partes, una de azar y otra de decisión.
En la de azar se busca el valor esperado de encontrarse en cada
etapa, y en la decisión , se decide de acuerdo al objetivo.
1
2
N
xnsn
p1
C1 p2
C2
pn Cn
Etapa 
n+1
f*n+1(1)
f*n+1(2)
f*n+1(N)
fn(sn, xn)
Etapa n
N: nº de estados posibles en la etapa n+1
p1, p2,...pN: distribución de probabilidad de lo que será el estado, dados el estado sn y la 
decisión xn en la etapa n.
Ci: contribución resultante a la función objetivo de la etapa n, si el estado resulta ser el i.
Ej.: Min la suma esperada de las contribuciones de las etapas individuales 
fn(sn, xn)=  pi  (Ci + f*n+1 (i)  ; i =1 a N
f*n+1 (s n+1 )= minxn+1 fn+1(sn+1, xn+1) 
800
1000
900
A
B
C
0.5
0.40.1
.3
.2
.5
.6
.4
1000
600
1200
0.5
0.4
0.1
0.3
0.2
0.5
0.6
0.4
A
B
C
AzarDecisiónAzarDecisión
Etapa 1 Etapa 2
Ejemplo: Juego consistente en la adopción de una decisión y la determinación
de un valor por un mecanismo aleatorio, se quiere maximizar la ganancia del
juego
Podemos seleccionar tres posiciones.
Queremos definir cuál es la decisión con la que vamos a 
operar en las dos etapas que configure una política óptima en 
base a la Esperanza de la ganancia
E(A)= 800 * .5 + 1000 * .4 + 900 * .1 = 890
E(B)= 800 * .3 + 1000 * .2 + 900 * .5 = 890
E(C)= 1000 * .6 + 900 * .4 = 960
Decisión: fn(s,xn)= E(s, xn) fn*(s)=max fn(s,xn)
s x A B C fn*(s) x*
A 890 - 960 960 C
B 890 890 - 890 A o B
C -- 890 960 960 C
Siguiendo igual razonamiento: en la primera etapa
E1(A)= .5 (1000 + 960) + .4( 600 + 890) + .1 (1200 +960) = 1792
E1(B)= .3 (1000 + 960) + .2( 600 + 890) + .5 (1200 +960) = 1966
E1(C)= .6( 600 + 890) + .4 (1200 +960) = 1758.
Maximo beneficio, será elegir B en la etapa 1 y A o B en la etapa 2
Decisiones:
La Programación Dinámica probabilística difiere de la
determinística en que el estado en la etapa siguiente no queda
completamente determinado por el estado y la decisión de la
política en el estado actual.
En cambio, existe una distribución de probabilidad para lo que
será el estado siguiente, que ésta completamente determinada
por el estado y la decisión de la política en la etapa actual.
Aplicaciones:
Modelos probabilísticos de inventario
Reemplazo de equipos
Confiabilidad de sistemas
Decisiones de inversión
Se ha considerado únicamente la PDP con un número finito
de etapas. Se verá una clase general de modelo para la
PDP, en el que las etapas se siguen repitiendo
indefinidamente: los procesos markovianos de decisión.