Tema PDin

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
10
1
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.
Se comienza por la ultima etapa, es decir la etapa 4 en este caso, si voy de 8 a 10 me cuesta 3, y si voy de 9 a 10 me cuesta 4
	s	f4*(s)	x4*
	8	3	10
	9	4	10
	s \ x3	8	9
	f3 *(s,)	x3 *
	5	4= 1+3	10=4+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
10
1
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
Seria 0 porque estoy al final del camino
En que nodo me encuentro
A donde voy
1 es el costo de 5 a 8, y 3 el costo de 8 a 10, y asi con todas las opciones
8
11=5+6
8=1+7
8=4+4
4
7
10=4+6
9=2+7
7=3+4
3
11
12=6+6
11=4+7
11=7+4
2
f2 *(s,x2)
6
5
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
10
1
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, tres caminos posibles
Con el mismo costo
Etapa 1: de 1 a 3 o 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
El 4 es el mejor costo para ir a 10 por 5
Un camino es 1 a 3 a 5 a 8 y a10
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: Valores posible
4. Definir la Función Objetivo y construir la función recursiva
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. O se el peso de cada conjunto de artículos a cargar
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
Cuantos artículos tipo 1 voy a cargar
Cuantos artículos tipo 2 voy a cargar
Cuantos artículos tipo 3 voy a cargar
La vble admisible que vincula una con otra es el peso admisible que me queda, las S
	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 }
S: Cantidad de ton por cargar
X3: Cantidad que cargo de X3, como puedo cargar 4 ton y X3 pesa 1, puedo cargar X3 hasta 4 veces, entonces si puedo cargar 2 ton por ejemplo (S=2), puedo elegir hasta cargar 2 veces X3 (X3=2), obteniendo una utilidad de 28, que es el maximo
Haga clic para modificar el estilo de texto del patrón
Segundo nivel
Tercer nivel
Cuarto nivel
Quinto nivel
 
 
 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 esinferior 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
x3+y3= y4+4
y4 = 0
x3 + y3= 4 
x3 = 4 – y3 ; y3= 0,1,2,3,4
x3 ≥ 0; entero
 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 ; los valores de : 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
xn
sn
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.4
0.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
Azar
Decisión
Azar
Decisió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.
x1x2x3
S1S2S3S4
x1x2x3
y1y2y3y4 = 0
d1 = 3d2 = 2d3 = 4
cantidad
x1
x2d2
d1d3
y1
y3y4
y2
t