Post on 06-Mar-2016
description
transcript
Luis Medina Aquino
PROGRAMACIN DINMICA
CONCEPTOS
BSICOS
Mtodo de optimizacin
Descomponer un problema
grande en
Problemas mas pequeos con resolucin mas
fcil
La Programacin dinmica resuelve el problema en etapas (problemas multietpicos).
En cada etapa interviene una variable de optimizacin.
Los clculos de las diferentes etapas se enlazan de forma recursiva para generar la solucin ptima.
CARACTERSTICAS
Cada etapa en una estructura en serie, se caracteriza por cuatro variables o funciones (Fig. 1). Estas son: variable de entrada, Sn; variable de decisin, dn; variable de salida, Sn+1 ; y funcin de retorno, Rn. Estas dos ltimas dependen de la entrada y de las decisiones.
ANLISIS GENERAL
Etapa iSi Si+1
Ri
di
Se tiene un contrato para entregar 3 unidades mensuales decierto producto durante 4 meses, la capacidad deproduccin de la planta es de 5 unidades mensuales comomximo. El stock a fin de mes no puede ser mayor de 4unidades. El costo de fabricacin C(x) es como sigue:C(0) = 0, C(1) = 15, C(2) = 17, C(3) = 19, C(4) = 21, y C(5) = 23.El costo de almacenamiento por unidad-mes es 2.El inventario inicial (II) es cero.El inventario final (IF) es cero.Se pide optimizar la produccin en un horizonte de 4 meses
ANLISIS GENERAL
Un inversionista tiene $7000 para invertir entres riesgos. l debe invertir en unidades de$1000. El retorno potencial a partir de lainversin en cualquier riesgo depende de lacantidad invertida, de acuerdo a la tablasiguiente:
ANLISIS GENERAL
A B C
0 0 0 0
1000 80 90 100
2000 170 200 190
3000 260 240 280
4000 320 340 320
5000 450 480 430
Determine cunto tiene que invertir en cada riesgo para maximizar su retorno
Determine, por programacin dinmica, el nmero decada uno de los siguientes artculos que debenincluirse en el cargamento de una camioneta deservicio rural, tal que el valor del cargamento semaximice. La capacidad de la camioneta es de 400kilos. Adems, debe haber por lo menos un artculode cada tipo.
ANLISIS GENERAL
Artculo Descripcin Peso Valor
1 Arroz Saco de 25 kg S/. 35
2 Azcar Saco de 75 kg S/. 100
3 Frijol Saco de 100 kg S/. 140
ANLISIS GENERAL
En un proceso en serie de multietapas la salida de la
etapa n es la entrada en la etapa n+1 (Fig. 2)
FIGURA 2
Etapa
1
S1 S2
R1
d1
Etapa
2
S3
R2
d2
Etapa
n-1
Sn-1 Sn
Rn-1
dn-1
Etapa
n
Sn+1
Rn
dn
f2(S2) fn(Sn)f1(S1) fn-1(Sn-1)
por tanto, la decisin que d como resultado el ptimo para cada entrada posible, puede ser
determinada para cada etapa
La ltima etapa de un proceso en serie, no tiene ninguna variable de salida que afecte alguna otra
unidad del sistema
Por lo general, el anlisis en programacin dinmica comienza con la ltima etapa y termina con la
primera
ANLISIS GENERAL
Richard Bellman, desarroll en los aos cincuenta las ideas bsicas de la programacin dinmica, postulando el principio de optimalidad que dice:
Una poltica ptima tiene la propiedad de que cualquiera que sean su estado y decisin iniciales, las decisiones subsecuentes deben constituir una poltica ptima con respecto al estado resultante de la decisin inicial
PRINCIPIO DE OPTIMALIDAD
PRINCIPIO DE OPTIMALIDAD
Matemticamente el principio de optimalidad es:
fn(Sn) = mx [Rn(Sn, dn) + fn+1(Sn+1)] dn
fn(Sn) = mn [Rn(Sn, dn) + fn+1(Sn+1)] dn
en caso de maximizar la funcin de retorno,
en caso de minimizar la funcin de retorno
*
*
PRINCIPIO DE OPTIMALIDAD
Para el caso de maximizar la funcin de retorno:
fn(Sn) = mx [Rn(Sn, dn) + fn+1(Sn+1)] dn
*
n = nmero de etapas subsecuentes en el proceso
Sn = variables de entrada a la n-sima etapa
dn = variable de decisin en la n-sima etapafn(Sn) = retorno mximo de un proceso con n etapas
y entradas Sn en la n-sima etapa
rn =Rn(Sn, dn) = funcin de retorno de la etapa n con
entrada Sn y variable de decisin dn
Sn +1 = salida de la etapa n y entrada a la etapa n+1
fn+1(Sn+1) = funcin de retorno mximo desde la ltima etapa hasta la etapa n+1.
*
EJEMPLO 1
Este problema se refiere a un vendedor mtico que tuvo que viajar hacia el oeste por diligencia, a travs de tierras indias hostiles, aproximadamente hace 125 aos. Aun cuando su punto de partida y destino eran fijos, tena un nmero considerable de opciones para elegir, qu estados recorrer en su ruta.
*
Los costos de la pliza estndar para elviaje en diligencia del estado i al j son:
SEGUROS DE PLIZAS
AD
C
B
G
F
E
I
H
J
2
1
4
3
3
6
3
1
4
3
4
5
4
2
3
6
4
7
4
3
*
DESEOS DEL VENDEDOR VIAJERO
Determinar cul es la ruta mssegura, es decir, desea correr elmenor riesgo posible.
Cul es la ruta que minimiza el
costo total?
DETERMINAR
SOLUCIN
Una forma bsica de resolver este
problema es por tanteo.
Pero el nmero de rutas posibles es muy
alto (en este caso 18) y por lo tanto son
muchos los clculos a realizar.
SOLUCIN
La programacin dinmica suministra una
solucin con mucho menos esfuerzo que
la numeracin exhaustiva
DEFINIR
Etapas
Variables de decisin
Variables de Estado
Funcin de retorno
Objetivo
ETA
PA
S
El problema puede dividirse enetapas, con una decisin de la
poltica requerida en cada
etapa. Las etapas a considerar
van a depender del tipo de
problema a resolver.
21
4
3
3
6
3
1
4
3
4
5
4
2
3
6
4
7
4
3
C
B
D
E
F
G
H
I
JA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
VA
RIA
BLE
S D
E D
EC
ISI
N
Consideremos que lasvariables de decisin dn (n
= 1, 2, 3, 4) son el destino
inmediato en la etapa n.
21
4
3
3
6
3
1
4
3
4
5
4
2
3
6
4
7
4
3
C
B
D
E
F
G
H
I
JA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
d1={B,C,D} d2={E,F,G} d3={H,I} d4={J}
VA
RIA
BLE
S D
E E
STA
DO
Cada etapa tiene ciertonmero de variables deestado asociados a ella.
En nuestro caso lasvariables de estado son:
S1, S2, S3, S4, S5
21
4
3
3
6
3
1
4
3
4
5
4
2
3
6
4
7
4
3
C
B
D
E
F
G
H
I
JA
S5={J}Etapa 1
S2={B,C,D}Etapa 2 Etapa 3 Etapa 4
S3={E,F,G} S4={H,I}S1={A}
d1={B,C,D} d2={E,F,G} d3={H,I} d4={J}
S2 = d1 S5 = d4S4 = d3S3 = d2
FUNCIN DE RETORNO
Se dispone de una relacin recursivaque identifica la poltica ptima para cada
estado en la etapa n, dada la poltica ptima
para cada estado en la etapa (n + 1).
21
4
3
3
6
3
1
4
3
4
5
4
2
3
6
4
7
4
3
C
B
D
E
F
G
H
I
JA
S5={J}Etapa 1
S2={B,C,D}Etapa 2 Etapa 3 Etapa 4
S3={E,F,G} S4={H,I}S1={A}
d1={B,C,D} d2={E,F,G} d3={H,I} d4={J}
R1(S1,d1) R2(S2,d2) R3(S3,d3) R4(S4,d4)
S2 = d1 S5 = d4S4 = d3S3 = d2
OBJETIVO
Minimizar los costos totales
Hallar f*1 (A) y la poltica ptima correspondiente.
*
21
4
3
3
6
3
1
4
3
4
5
4
2
3
6
4
7
4
3
C
B
D
E
F
G
H
I
JA
S5={J}Etapa 1
S2={B,C,D}Etapa 2 Etapa 3 Etapa 4
S3={E,F,G} S4={H,I}S1={A}
d1={B,C,D} d2={E,F,G} d3={H,I} d4={J}
R1(S1,d1) R2(S2,d2) R3(S3,d3) R4(S4,d4)
S2 = d1 S5 = d4S4 = d3S3 = d2
f*1 (A) f*2(S2) f*3 (S3) f*4(S4)
El proceso de calculo
es de atrs hacia
adelante
*
IH
J
Estados posibles
S4=H y S4= I
S5={J}Etapa 4
S4={H,I}
d4={J}
R4(S4,d4)
3
4
*
f4(S4) = R4(S4, d4 ) + f5*(S5) minf4*(S4) d4*d4 =J
H 3 + 0 = 3 3 J
I 4 + 0 = 4 4 J
ETAPA N = 4
d4
S4
0
S5={J}Etapa 1
S2={B,C,D}Etapa 2 Etapa 3 Etapa 4
S3={E,F,G} S4={H,I}S1={A}
d1={B,C,D} d2={E,F,G} d3={H,I} d4={J}
R1(S1,d1) R2(S2,d2) R3(S3,d3) R4(S4,d4)
S2 = d1 S5 = d4S4 = d3S3 = d2
Estados posibles
S3 = E, S3=F y S3= J
G
F
E
I
H
J
Decisiones posibles: d3 = H y
d3 = I
Etapa 3S3={E,F,G} S4={H,I}
d3={H,I}
R3(S3,d3)
1
3
4
6
3
3
ETAPA N = 3
ETAPA N = 3
f3(S3) = R3(S3, d3 ) + f4*(S4)f3*(S3) d3*
d3 = H d3 = I
E 1+ 3 = 4 4 +4 = 8 4 H
F 6+ 3 = 9 3 + 4 = 7 7 I
G 3 +3 = 6 3 + 4 = 7 6 H
d3S3S4 f4*(S4) d4*
H 3 J
I 4 J
ETAPA 4
S5={J}Etapa 1
S2={B,C,D}Etapa 2 Etapa 3 Etapa 4
S3={E,F,G} S4={H,I}S1={A}
d1={B,C,D} d2={E,F,G} d3={H,I} d4={J}
R1(S1,d1) R2(S2,d2) R3(S3,d3) R4(S4,d4)
S2 = d1 S5 = d4S4 = d3S3 = d2
ETAPA 3: Variable de enlace S4 = d3
Etapa n= 2
Estados posibles
S2 = B, S2 = C y S2 = D
G
F
E
I
H
J
Decisiones posibles:
d2 = E,d2 = F y d2
= G
D
C
B
S2={B,C,D} Etapa 2
S3={E,F,G}
d2={E,F,G}
R2(S2,d2)
7
6
4
4
4
2
3
1
5
ETAPA N = 2
ETAPA N = 2
f2(S2) = R2(S2, d2 ) + f3*(S3)f2*(S2) d2*
d2 = E d2 = F d2 = G
B 7+ 4 = 11 4 + 7 = 11 6 + 6 = 12 11 E F
C 3 + 4 = 7 2 + 7= 9 4 + 6 = 10 7 E
D 4 + 4 = 8 1 + 7 = 8 5 + 6 = 11 8 E F
S2
d2
S5={J}Etapa 1
S2={B,C,D}Etapa 2 Etapa 3 Etapa 4
S3={E,F,G} S4={H,I}S1={A}
d1={B,C,D} d2={E,F,G} d3={H,I} d4={J}
R1(S1,d1) R2(S2,d2) R3(S3,d3) R4(S4,d4)
S2 = d1 S5 = d4S4 = d3S3 = d2
S3 f3*(S3) d3*
E 4 H
F 7 I
G 6 H
ETAPA 3 ETAPA 2: Variable de enlace S3 = d2
Etapa n= 1
Estado posibleS1 = A G
F
E
I
H
J
Decisiones posibles: d1
= B,d1 = C y d1 = D
D
C
B
A
Etapa 1
S2={B,C,D}S1={A}
d1={B,C,D}
R1(S1,d1)
2
4
3
ETAPA N = 1
ETAPA N = 1
f1(S1) = R1(S1, d1 ) + f2*(S2)f1*(S1) d1*
d1 = B d1 = C d1 = D
A 2 +11 = 13 4 + 7 = 11 3 + 8 = 11 11 C D
ETAPA 1: variable de enlace S2 = d1
S2 f2*(S2) d2*
B 11 E F
C 7 E
D 8 E F
ETAPA 2
S5={J}Etapa 1
S2={B,C,D}Etapa 2 Etapa 3 Etapa 4
S3={E,F,G} S4={H,I}S1={A}
d1={B,C,D} d2={E,F,G} d3={H,I} d4={J}
R1(S1,d1) R2(S2,d2) R3(S3,d3) R4(S4,d4)
S2 = d1 S5 = d4S4 = d3S3 = d2
S1
d1
SOLUCION
S1 f1*(S1) d1*
A 11 C D
ETAPA 1
S2 = d1
S2 f2*(S2) d2*
B 11 E F
C 7 E
D 8 E F
ETAPA 2
S3 = d2
S3 f3*(S3) d3*
E 4 H
F 7 I
G 6 H
ETAPA 3
S4 = d3
S4 f4*(S4) d4*
H 3 J
I 4 J
ETAPA 4
Etapa i di Ri
1 C 4
2 E 3
3 H 1
4 J 3
Etapa i di Ri
1 D 3
2 E 4
3 H 1
4 J 3
Etapa i di Ri
1 D 3
2 F 1
3 I 3
4 J 4
SOLUCION 1 SOLUCION 2 SOLUCION 3
COSTO TOTAL = 11
A C
E
H
J
Ruta N 1(Alternativa 1)
4
3
1
3
AD
E
H
J
Ruta N 2(Alternativa 2)
3
4
1
3
AD
F
I
J
Ruta N 3(Alternativa 3)
31
3 4