View
33
Download
0
Embed Size (px)
DESCRIPTION
Programacion dinamica investigacion operativa
Citation preview
ProgramaciónDinámica
Docente : Lic. Gabriel Solari Carbajal
Universidad Nacional Mayor de San MarcosFacultad de Ingeniería de Sistemas e Informática
Investigación Operativa II
2
INTRODUCCIONLa Programación Dinámica (PD), es una técnica que permite resolver problemas en los cuales se debe tomar no una sino una secuencia de decisiones.
El francés P. Massé en 1946 utilizó un método semejante a la PD, pero no recibió toda la atención que merecía. En 1957 el matemático norteamericano Richard Bellman publica su obra DynamicProgramming, donde describe los fundamentos de la PD.
La facilidad de su metodología ha permitido la resolución de innumerables problemas.
Programación Dinámica
3
FUNDAMENTO DE LA PDDado un problema:
Programación Dinámica
PROBLEMA
4
Este problema se divide en etapas. El número de etapas dependerá de las características del problema:
Programación Dinámica
ETAPA4
ETAPA3
ETAPA2
ETAPA1
5
Programación Dinámica
ETAPA4
ETAPA3
ETAPA2
ETAPA1
Se resuelve una etapa cualquiera. Seleccionemos, por ejemplo, la etapa 4:
6
Programación Dinámica
ETAPA4
ETAPA3
ETAPA2
ETAPA1
La solución óptima se determina de revisar todas las decisiones posibles de la etapa 4:
7
Programación Dinámica
ETAPA4
ETAPA3
ETAPA2
ETAPA1
La solución de la etapa 4 se utiliza para resolver la etapa 3:
8
La nueva solución óptima se determina de revisar todas las decisiones posibles de la etapa 3 (integrando las soluciones de la etapa 4):
Programación Dinámica
ETAPA2
ETAPA1
ETAPAS3 Y 4
9
Programación Dinámica
ETAPA2
ETAPA1
ETAPAS3 Y 4
La solución de las etapas 3 y 4 se utiliza para resolver la etapa 2:
10
Programación Dinámica
ETAPA1
ETAPAS2, 3 Y 4
La nueva solución óptima se determina de revisar todas las decisiones posibles de la etapa 2 (integrando las soluciones de las etapas 3 y 4):
11
Programación Dinámica
ETAPA1
ETAPAS2, 3 Y 4
La solución de las etapas 2, 3 y 4 se utiliza para resolver la etapa 1:
12
La nueva solución óptima se determina de revisar todas las decisiones posibles de la etapa 1 (integrando las soluciones de las etapas 2, 3 y 4), ésta es la solución del problema original:
Programación Dinámica
ETAPAS1, 2, 3 Y 4
13
PRINCIPIO DE OPTIMALIDAD DE BELLMANEl teorema presentado por Bellman, denominado Principio de Optimalidad, dice: “Una política óptima sólo puede estar formado por subpolíticas óptimas”.
Dada la siguiente red:
Programación Dinámica
14
Programación Dinámica
A C
D
B
E
F
I
J
L
M
N
G K
H
5
2
3
11
8
4
9
6
6
83
2
11
5
9
4
7
3
9
6
8
5
4
3
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
Si queremos determinar un camino de A a N, este se denominará una política:
15
Programación Dinámica
A C
D
B
E
F
I
J
L
M
N
G K
H
5
2
3
11
8
4
9
6
6
83
2
11
5
9
4
7
3
9
6
8
5
4
3
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
Así por ejemplo ADFKMN es una política:
16
Programación Dinámica
A C
D
B
E
F
I
J
L
M
N
G K
H
5
2
3
11
8
4
9
6
6
83
2
11
5
9
4
7
3
9
6
8
5
4
3
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
Una subpolítica será una porción continua de un camino. De este modo BEIM es una subpolítica:
17
Programación Dinámica
A C
D
B
E
F
I
J
L
M
N
G K
H
5
2
3
11
8
4
9
6
6
83
2
11
5
9
4
7
3
9
6
8
5
4
3
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
Si se desea determinar el camino mínimo de A a N, ACEILN es la política óptima que responde a este objetivo:
18
Programación Dinámica
A C
D
B
E
F
I
J
L
M
N
G K
H
5
2
3
11
8
4
9
6
6
83
2
11
5
9
4
7
3
9
6
8
5
4
3
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
Ahora, si se desea determinar una subpolítica óptima de C a L, esta será CEIL:
19
CARACTERISTICAS DE LOS PROBLEMAS DE PDEn los problemas de PD se localizan:
Programación Dinámica
ETAPAS O PERIODOS
VARIABLES DE ESTADO
VARIABLES DE DECISION
FUNCION COSTO-BENEFICIO
OBJETIVO
20
ETAPAS O PERIODOSEs cada una de las partes en las que se divide el problema.
Programación Dinámica
21
Programación Dinámica
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
22
VARIABLES DE ESTADOEs la variable que indica la situación en que se encuentra el problema al inicio de cada etapa. Los valores de esta variable forman el llamado DOMINIO DE ESTADO.
Programación Dinámica
23
Programación Dinámica
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
f1(x1) f2(x2) f3(x3) f4(x4) f5(x5) f6(x6)
24
VARIABLES DE DECISIONEs la variable que indica la decisión a tomar en cada etapa. Los valores de esta variable forman el llamado DOMINIO DE CONTROL.
Programación Dinámica
25
Programación Dinámica
f1(x1) f2(x2) f3(x3) f4(x4) f5(x5) f6(x6)
d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5) d(x5, x6)
ETAPA 1 ETAPA 2 ETAPA 3 ETAPA 4 ETAPA 5
26
FUNCION COSTO-BENEFICIOEs la función que indica el resultado obtenido cuando en una etapa cualquiera se toma una decisión que depende del estado inicial. Esta función también se denomina FORMULA RECURSIVA DE LA PD.
Programación Dinámica
fi(xi) = min [ d(xi , xi+1) + fi+1(xi+1) ]todas las
rutasfactibles( xi , xi+1 )
FORMULA RECURSIVA HACIA ATRAS
27
Otra forma de presentar la función costo-beneficio es:
Programación Dinámica
fi(xi) = min [ d(xi-1 , xi) + fi-1(xi-1) ]todas las
rutasfactibles( xi-1 , xi )
FORMULA RECURSIVA HACIA ADELANTE
28
OBJETIVODetermina la secuencia de decisiones que optimice la función Costo-Beneficio.
Programación Dinámica
A C
E I L
N28
2 34
29
PROCEDIMIENTO DE LA PDPara resolver un problema por medio de la PD se pueden utilizar diferentes procedimientos.
Los que más se utilizan son los de fórmulas recursivas hacia adelante y los de fórmulas recursivas hacia atrás.
La metodología requiere de dos iteraciones.
La primera iteración denominada DESCENDENTE, es la que resuelve cada etapa integrándolas sucesivamente a las siguientes soluciones. Esta iteración es la más laboriosa.
Programación Dinámica
30
La segunda iteración denominada ASCENDENTE, es la que permite construir la secuencia óptima de decisiones. Esta iteración es la más simple.
La metodología descrita puede ser aplicada en diferente forma sobre un mismo problema.
Programación Dinámica
31
EjemploDado el siguiente grafo determinar la ruta más corta del vértice A al vértice Z.
Programación Dinámica
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
32
Programación Dinámica
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
33
Programación Dinámica
Fórmula recursiva hacia atrásfi(xi) = min [ d(xi , xi+1) + fi+1(xi+1) ], i = 1, 2, 3, 4
todas lasrutas
factibles( xi , xi+1 )
fn(xn) = 0
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
34
Iteración descendente
Programación Dinámica
f5(x5) = f5(Z) = 0
f4(x4) = min [ d(x4 , x5) + f5(x5) ]ETAPA 4
r. f.
f4(H) = min [ d(H , Z) + f5(Z) ]x4 = H
r. f
f4(H) = min [ 4 + 0 ] = 4r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
35
Programación Dinámica
f4(I) = min [ d(I , Z) + f5(Z) ]x4 = I
r. f
f4(I) = min [ 3 + 0 ] = 3r. f
f4(J) = min [ d(J , Z) + f5(Z) ]x4 = J
r. f
f4(J) = min [ 5 + 0 ] = 5r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
36
Programación Dinámica
f3(x3) = min [ d(x3 , x4) + f4(x4) ]ETAPA 3
r. f.
f3(E) = min [ d(E , H) + f4(H) , d(E , I) + f4(I) ]
x3 = E
r. f
f3(E) = min [ 6 + 4 , 3 + 3 ] = 6r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
37
Programación Dinámica
f3(F) = min [d(F, H)+f4(H), d(F, I)+f4(I), d(F, J)+f4(J)]x3 = F
r. f
f3(F) = min [ 7 + 4 , 5 + 3 , 4 + 5 ] = 8r. f
f3(G) = min [ d(G , I) + f4(I) , d(G , J) + f4(J) ]x3 = G
r. f
f3(G) = min [ 7 + 3 , 4 + 5 ] = 9r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
38
Programación Dinámica
f2(x2) = min [ d(x2 , x3) + f3(x3) ]ETAPA 2
r. f.
f2(B) = min [ d(B , E) + f3(E) , d(B , F) + f3(F) ]
x2 = B
r. f
f2(B) = min [ 7 + 6 , 6 + 8 ] = 13r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
39
Programación Dinámica
f2(C) = min [d(C, E)+f3(E), d(C, F)+f3(F), d(C, G)+f3(G)]x2 = C
r. f
f2(C) = min [ 4 + 6 , 3 + 8 , 3 + 9 ] = 10r. f
f2(D) = min [ d(D , F) + f3(F) , d(D , G) + f3(G) ]x2 = D
r. f
f2(D) = min [ 4 + 8 , 2 + 9 ] = 11r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
40
Programación Dinámica
f1(x1) = min [ d(x1 , x2) + f2(x2) ]ETAPA 1
r. f.
f1(A) = min [d(A ,B)+f2(B), d(A,C)+f2(C), d(A,D)+f2(D)]
x1 = A
r. f
f1(A) = min [ 3 + 13 , 5 + 10 , 2 + 11 ] = 13r. f
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
41
Programación Dinámica
Iteración ascendenteLa ruta mínima óptima de A a Z, resulta:
La distancia mínima es: 13
2 2 54 J ZGDA
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
42
Programación Dinámica
H ir a Z 4 ir a Z 4I ir a Z 3 ir a Z 3J ir a Z 5 ir a Z 5
DISTANCIA MINIMA
ESTADO INICIAL
DECISIONES POSIBLES
DISTANCIA ASOCIADA
DECISION OPTIMA
FORMA TABULARIteración descendente
ETAPA 4
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
43
Programación Dinámica
ir a H 6 + 4 = 10ir a I 3 + 3 = 6ir a H 7 + 4 = 11ir a I 5 + 3 = 8ir a J 4 + 5 = 9ir a I 7 + 3 = 10ir a J 4 + 5 = 9
ESTADO INICIAL
DECISIONES POSIBLES
DISTANCIA ASOCIADA
DECISION OPTIMA
DISTANCIA MINIMA
G
ir a I
ir a I
ir a J
6
8
9
E
F
ETAPA 3
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
44
Programación Dinámica
ir a E 7 + 6 = 13ir a F 6 + 8 = 14ir a E 4 + 6 = 10ir a F 3 + 8 = 11ir a G 3 + 9 = 12ir a F 4 + 8 = 12ir a G 2 + 9 = 11
ESTADO INICIAL
DECISIONES POSIBLES
DISTANCIA ASOCIADA
DECISION OPTIMA
DISTANCIA MINIMA
B ir a E 13
C ir a E 10
D ir a G 11
ETAPA 2
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
45
Programación Dinámica
ir a B 3 + 13 = 16ir a C 5 + 10 = 15ir a D 2 + 11 = 13
DISTANCIA MINIMA
A ir a D 13
ESTADO INICIAL
DECISIONES POSIBLES
DISTANCIA ASOCIADA
DECISION OPTIMA
ETAPA 1
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)
46
Programación Dinámica
Iteración ascendenteLa ruta mínima óptima de A a Z, resulta:
La distancia mínima es: 13
2 2 54 J ZGDA
3
5
2
7
6
4
3
3
2
4
4
3
54
5
7
6
3
7
B E H
I ZF
D 4G J
CA
Etapa 1 Etapa 2 Etapa 3 Etapa 4
f5(x5)f4(x4)f3(x3)f2(x2)f1(x1) d(x1, x2) d(x2, x3) d(x3, x4) d(x4, x5)