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:


PROBLEMA

4

Este problema se divide en etapas. El número de etapas dependerá de las características del problema:


ETAPA4

ETAPA3

ETAPA2

ETAPA1

5


ETAPA4

ETAPA3

ETAPA2

ETAPA1

Se resuelve una etapa cualquiera. Seleccionemos, por ejemplo, la etapa 4:

6


ETAPA4

ETAPA3

ETAPA2

ETAPA1

La solución óptima se determina de revisar todas las decisiones posibles de la etapa 4:

7


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):


ETAPA2

ETAPA1

ETAPAS3 Y 4

9


ETAPA2

ETAPA1

ETAPAS3 Y 4

La solución de las etapas 3 y 4 se utiliza para resolver la etapa 2:

10


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


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:


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:


14


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


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


Así por ejemplo ADFKMN es una política:

16


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


Una subpolítica será una porción continua de un camino. De este modo BEIM es una subpolítica:

17


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


Si se desea determinar el camino mínimo de A a N, ACEILN es la política óptima que responde a este objetivo:

18


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


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:


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.


21



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.


23



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.


25


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)


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.


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:


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.


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.


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.


31

EjemploDado el siguiente grafo determinar la ruta más corta del vértice A al vértice Z.


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


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


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



34

Iteración descendente


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



35


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



36



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



37


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



38



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



39


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



40



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



41


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



42


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



43


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



44


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



45


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



46


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



programacion dinamica

Documents