UPN Programacion Dinámica 1

PROGRAMACIN DINMICA
Luis Medina Aquino
Mtodo de
optimizacin
CONCEPTOS
BSICOS
Descompone
r un
problema
grande en
Problemas
mas
pequeos
con
resolucin
mas fcil
CARACTERSTICAS
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.
ANLISIS GENERAL
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.
di
Si
Etapa i
Ri
Si+1
ANLISIS GENERAL
Se tiene un contrato para entregar 3 unidades
mensuales de cierto producto durante 4 meses,
la capacidad de produccin de la planta es de 5
unidades mensuales como mximo. El stock a
fin de mes no puede ser mayor de 4 unidades. 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 en tres riesgos. l debe
invertir en unidades de $1000. El
retorno potencial a partir de la
inversin en cualquier riesgo depende
de la cantidad invertida, de acuerdo a
la tabla siguiente:
A
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
ANLISIS GENERAL
Determine, por programacin dinmica, el
nmero de cada uno de los siguientes
artculos que deben incluirse en el
cargamento de una camioneta de servicio
rural, tal que el valor del cargamento se
maximice. La capacidad de la camioneta es
de 400 kilos. Adems, debe haber por lo
menos un artculo de cada tipo.
Artculo
Descripcin
Peso
Valor
Arroz
Saco de 25
kg
S/. 35
Azcar
Saco de 75
kg
S/. 100
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)
d1
S1
Etapa
1
dn1
d2
S2
Etapa
2
S3
Sn1
Etapa
n-1
dn
Sn
Etapa
n
R
1
R
2
Rn1
R
n
f1(S1)
f2(S2)
fn-1(Sn-1)
fn(Sn)
FIGURA 2
Sn
+1
ANLISIS GENERAL
Por lo general, el anlisis en programacin
dinmica comienza con la ltima etapa y
termina con la primera
La ltima etapa de un proceso en serie, no
tiene ninguna variable de salida que
afecte alguna otra unidad del sistema
por tanto, la decisin que d como
resultado el ptimo para cada entrada
posible, puede ser determinada para cada
etapa
PRINCIPIO DE OPTIMALIDAD
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
Matemticamente el principio de optimalidad es:
*
fn(Sn) = mx [Rn(Sn, dn) + fn+1(Sn+1)]
dn
en caso de maximizar
la funcin de retorno,
*
fn(Sn) = mn [Rn(Sn, dn) +

f
n+1(Sn+1)]
en caso de minimizar la funcin de retorno
dn
Para el caso de maximizar la funcin de retorno:
*
fn(Sn) = mx [Rn(Sn, dn) + fn+1(Sn+1)]
dnde etapas subsecuentes en el proceso

n = nmero
Sn = variables de entrada a la n-sima etapa
dn = variable de decisin en la n-sima etapa
fn(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
* (Sn+1) = funcin de retorno mximo desde la ltima
fn+1
etapa hasta la etapa n+1.
EJEMPLO 1
*PROBLEMA DE LA
DILIGENCIA
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.
SEGUROS DE PLIZAS
Los costos de la pliza estndar

para el viaje en diligencia del
estado i al j son:
*Diagrama: Red de
las Rutas Posibles

7
4
2
3
4
A
3
3
1
4
I
3
DESEOS DEL VENDEDOR VIAJERO
Determinar cul es la ruta ms

segura, es decir, desea correr el
menor riesgo posible.
DETERMINAR
Cul es la ruta que minimiza el

costo total?
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
ETAPAS
El problema puede dividirse en

etapas, con una decisin de la
poltica requerida en cada
etapa. Las etapas a considerar
van a depender del tipo de
problema a resolver.
4
2
3
4
A
3
Etapa
1
3
1
Etapa
2
4
I
3
Etapa
3
Etapa
4
VARIABLES DE DECISIN
Consideremos que las

variables de decisin dn (n
= 1, 2, 3, 4) son el destino
inmediato en la etapa n.
4
2
3
4
A
3
d1={B,C,D}
Etapa
1
3
1
4
I
3
d2={E,F,G}
d3={H,I}
Etapa
2
Etapa
3
d4={J}
Etapa
4
VARIABLES DE ESTADO
Cada
etapa
tiene
cierto
nmero de variables de estado
asociados a ella.
En nuestro caso las variables
de estado son:
S1, S2, S3, S4, S5
4
2
3
4
A
3
d1={B,C,D}
S1={A}
3
1
5
d2={E,F,G}
4
I
3
d3={H,I}
d4={J}
Etapa S2={B,C,D} Etapa S3={E,F,G} Etapa S4={H,I} Etapa S5={J}

1
2
3
4
S2 = d1
S3 = d2
S4 = d3
S5 = d4
FUNCIN DE RETORNO
Se dispone de una relacin recursiva que
identifica la poltica ptima para cada estado en
la etapa n, dada la poltica ptima para cada
estado en la etapa (n + 1).
B
2
3
4
3
1
D
d1={B,C,D}
S1={A}
d2={E,F,G}
J
4
I
3
d3={H,I}
d4={J}

1
2
3
4
S2 = d1
S3 = d2
S4 = d3
S5 = d4
R1(S1,d1)
R2(S2,d2)
R3(S3,d3)
R4(S4,d4)
OBJETIVO
Minimizar los costos totales
*Procedimiento
Hallar f*1 (A) y la poltica
ptima correspondiente.
f*1 (A)
f*2(S2)
7
B
2
f*3 (S3)
E
3
1
D
d1={B,C,D}
S1={A}
1
4
f*4(S4)
d2={E,F,G}
J
4
I
3
d3={H,I}
d4={J}

1
2
3
4
S2 = d1
S3 = d2
S4 = d3
S5 = d4
R1(S1,d1)
R2(S2,d2)
R3(S3,d3)
R4(S4,d4)
*Procedimiento
El proceso de calculo
es de atrs hacia
adelante
*Etapa
n=4
H
3
J
4
Estados
posibles
S4=H y
I
d4={J}
S4= I
S4={H,I} Etapa S5={J}

4
R4(S4,d4)
ETAPA N = 4
d1={B,C,D}
S1={A}
d2={E,F,G}
d3={H,I}
d4={J}
Etapa S2={B,C,D} Etapa S3={E,F,G} Etapa S4={H,I} Etapa

1
2
3
4
S2 = d1
S3 = d2
S4 = d3
R1(S1,d1)
R2(S2,d2)
d4
R3(S3,d3)
f4(S4) = R4(S4, d4 ) +
f5*(S5)
R4(S4,d4)
d4 =J
min
f4*(S
4)
3+0=3
4+0=4
S4
d4 *
S5={J}
S5 = d 4
ETAPA N = 3
Decisiones
posibles: d3 =
H y d3 = I
1
4
F
3
I
3
Estados
posibles
S3 = E,
S3=F y
S3= J
d3={H,I}
3
S3={E,F,G} Etapa S4={H,I}
3
R3(S3,d3)
ETAPA N = 3
d1={B,C,D}
S1={A}
d2={E,F,G}
d3={H,I}
d4={J}

1
2
3
4
S2 = d1
S3 = d2
S4 = d3
R1(S1,d1)
R2(S2,d2)
ETAPA 4
S4
f4*(S
4)
d4*
R3(S3,d3)
S5={J}
S5 = d 4
R4(S4,d4)
ETAPA 3: Variable de enlace S4 = d3

f3(S3) = R3(S3, d3 ) +
d3
f4*(S4)
f3*(S
S3
3)
d3 = H
d3 = I
d3*
1+ 3 = 4
4 +4 = 8
6+ 3 = 9
3+4=7
ETAPA N = 2
7
Decisiones
posibles:
d2 = E,
d2 = F y
d2 = G
4
6
3
2
Estados
posibles
S2 = B, S2
= C y S2 =
D
4
1
d2={E,F,G}
5
Etapa n= 2
G
S2={B,C,D Etapa S3={E,F,G}
}
2
R2(S2,d2)
ETAPA N = 2
d1={B,C,D}
S1={A}
d2={E,F,G}
d3={H,I}
d4={J}

1
2
3
4
S2 = d1
S3 = d2
S4 = d3
R1(S1,d1)
R2(S2,d2)
ETAPA 3
S3 f3*(S3) d3*
E
d2
S2
R3(S3,d3)
S5={J}
S5 = d 4
R4(S4,d4)
ETAPA 2: Variable de enlace S3 = d2

f2(S2) = R2(S2, d2 ) + f3*(S3)
f2*(S2
d2*
)
d2 = E
d2 = F
d2 = G
7+ 4 =
11
4+7=
11
6+6=
12
11
EF
3+4=
7
2 + 7=
9
4+6=
10
ETAPA N = 1
Decisione
s
posibles:
d1 = B,
d1 = C y
d1 = D
H
4
Estado
posible
S1 = A
Etapa n= 1
d1={B,C,D}
G
S1={A} Etapa S2={B,C,D}
1
R1(S1,d1)
ETAPA N = 1
d1={B,C,D}
S1={A}
d2={E,F,G}
d4={J}

1
2
3
4
S2 = d1
S3 = d2
S4 = d3
R1(S1,d1)
S2
d3={H,I}
ETAPA 2
f2*(S
d2*
)
2
11
EF
EF
R2(S2,d2)
d1
S1
A
R3(S3,d3)
S5={J}
S5 = d 4
R4(S4,d4)
ETAPA 1: variable de enlace S2 = d1

f1(S1) = R1(S1, d1 ) + f2*(S2)
f1*(S1
d1*
)
d1 = B
d1 = C
d1 = D
2 +11 =
13
4+7=
3 + 8 = 11 11
11
CD
SOLUCION
ETAPA 1
S1
ETAPA 2
S2 = d1
f1*(S1
d1*
)
11
ETAPA 3
S3 = d2
S f2*(S2
d2 *
)
2
CD
SOLUCION 1
ETAPA 4
S4 = d3
f3*(S3 d3
)
*
S3
S4
f4*(S
4)
d4 *
11
EF
EF
G
SOLUCION 2
SOLUCION 3
Etapa
i
di
Ri
Etapa
i
di
Ri
Etapa
i
di
Ri
4
J
3
COSTO TOTAL = 11
Ruta N 1
(Alternativa 1)
E
1
3
H
A
3
J
Ruta N 2
(Alternativa 2)
E
1
H
4
A
3
D
3
J
Ruta N 3
(Alternativa 3)
F
1
3
D
J
3
4
I

UPN Programacion Dinámica 1

Cargado por

Copyright:

Formatos disponibles

UPN Programacion Dinámica 1

Cargado por

Información del documento

Descripción 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

UPN Programacion Dinámica 1

Cargado por

Copyright:

Formatos disponibles

PROGRAMACIN DINMICA

Luis Medina Aquino

Richard Bellman, desarroll en los aos

fn(Sn) = mn [Rn(Sn, dn) +

dnde etapas subsecuentes en el proceso

vendedor mtico que tuvo que

Los costos de la pliza estndar

las Rutas Posibles

DESEOS DEL VENDEDOR VIAJERO

Determinar cul es la ruta ms

Cul es la ruta que minimiza el

Una forma bsica de resolver este

La programacin dinmica suministra una

El problema puede dividirse en

Consideremos que las

Etapa S2={B,C,D} Etapa S3={E,F,G} Etapa S4={H,I} Etapa S5={J}

Etapa S2={B,C,D} Etapa S3={E,F,G} Etapa S4={H,I} Etapa S5={J}

Etapa S2={B,C,D} Etapa S3={E,F,G} Etapa S4={H,I} Etapa S5={J}

S4={H,I} Etapa S5={J}

Etapa S2={B,C,D} Etapa S3={E,F,G} Etapa S4={H,I} Etapa

Etapa S2={B,C,D} Etapa S3={E,F,G} Etapa S4={H,I} Etapa

ETAPA 3: Variable de enlace S4 = d3

Etapa S2={B,C,D} Etapa S3={E,F,G} Etapa S4={H,I} Etapa

ETAPA 2: Variable de enlace S3 = d2

Etapa S2={B,C,D} Etapa S3={E,F,G} Etapa S4={H,I} Etapa

ETAPA 1: variable de enlace S2 = d1

También podría gustarte