programacion dinamica

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)