Programacion dinamica.

1

UNIVERSIDAD DE LIMA

FACULTAD DE INGENIERIA DE SISTEMAS

DEPARTAMENTO ACADEMICO DE INGENIERIA DE SISTEMAS

ASIGNATURA : INVESTIGACION OPERATIVA II

SECCION : 901, 902

PROFESORA : ANGELICA KAMIYAMA M.

PER. ACADEMICO: 2001-1

Programación Dinámica

El término proceso de decisiones secuenciales describe una actividad que involucra una

secuencia de decisiones para cumplir un determinado fin. Programación Dinámica es la

colección de herramientas matemáticas para el análisis de procesos de decisiones

secuenciales determinando los valores óptimos de dichas decisiones.

Aplicaciones :

Determinación de políticas de inventarios

Operación de reservorios

Selección de inversiones

Determinación de políticas de expansión de capacidad

Problema de caminos más cortos

I. Problema prototipo de Programación Dinámica:

Problema de caminos más cortos

Ejemplo: En la siguiente red hallar un camino más corto del nodo 1 al nodo 9

12 5

2 7

4 7

1 6 15

3

1 4 7

10

3 8 9

2 3

7 15

3 4

6

2

Sean

t i J = longitud del arco ( i, j )

f i = la mínima distancia de i a 9 (longitud de un camino más corto de i a 9)

Entonces,

t i J + f J = longitud total del camino de i a 9 que se inicia en el arco ( i, j ) y

luego toma el camino más corto de j a 9

f i < t i J + f J i ¹ 9

Por lo tanto,

f i = min í t i J + f J ý i ¹ 9, puesto que un camino más corto de i a 9

j pasa por algún arco ( i, j )

Entonces, como f 9 = 0

f 8 = 10 + f 9 = 10

f 7 = 3 + f 9 = 3

f 6 = min { 7 + f 8 , 15 + f 9 } = min { 7 + 10 , 15 + 0 } = 15

… … ..

f 1 = min { 1 + f 2 , 2 + f 3 } = min { 1 + 20 , 2 + 17 } = 19

Por lo tanto, la longitud de un camino más corto de 1 a 9 es 19.

II. Propiedades Recurrentes

El problema de caminos más cortos y una gran variedad de otros procesos de decisiones

secuenciales comparten varias propiedades :

1. El problema original está sumergido en un conjunto de problemas de optimización.

2. La solución óptima del problema de optimización está caracterizada por una ecuación

recursiva.

3. La solución óptima puede ser calculada evaluando la ecuación recursiva en los

estados en una secuencia predeterminada.

4. Se cumple el principio de optimalidad :

4.1 “ Sea P un camino óptimo de i a j. Cualquier subcamino de ip a iq contenido en

P es un camino óptimo de ip a iq “.

4.2 “ La mejor ruta desde cualquier nodo z al nodo final depende solo del nodo z y no

de la ruta usada para llegar a z ”.

3

4.3 “ Una ruta óptima tiene la propiedad de que cualquiera sea el nodo inicial y arco

inicial, los arcos restantes deben constituir una ruta óptima con respecto al primer

nodo alcanzado después del nodo inicial “.

III. Estructuración de la técnica

1. Estado

Un estado es un resumen de la historia del proceso que es suficientemente detallada

para poder tomar una decisión. Los estados son entonces los puntos donde se toman las

decisiones.

Las variables de estado son los elementos de un (vector de) estado.

Notación :

S = vector de estado

= ( s1, s2, … ., sn)

si = variable de estado i

E = conjunto de todos los estados

2. Decisión

D(S) = conjunto de decisiones para el estado S

{ d1, d2, … ., dn }

3. Función de transición

Es la función T que define el nuevo estado al tomar la decisión d en el estado actual S,

Sn = T( d, S )

Sn = nuevo estado

4. Generación de estados

Dado un estado inicial la aplicación repetida de la función de transición generará el

conjunto de todos los estados del problema siempre y cuando se tomen en cuenta las

restricciones del problema.

5. Función de valor óptimo

4

A cada estado se le asocia un subproblema del mismo tipo que el problema original pero

de menor tamaño. La función de valor óptimo es la regla que asigna al estado S el valor

óptimo de la función objetivo del subproblema asociado a él. Dicha función es denotada

como f (S).

6. Función de política óptima

Es la regla que asigna la mejor primera decisión a cada subproblema. Se denota por P

(S) .

7. Función de retorno

Sea ad ( S ) = valor (costo o utilidad) asociado a la decisión d tomada en el estado S

Entonces

R( S, d ) = valor de la ruta desd S al estado final dada la decisión d y la ruta

óptima desde Sn.

= ad( S ) + f (Sn)

8. Ecuación recursiva

f ( S ) = min { R(S,d) }

dÎD(S)

9. Condición de contorno

Valor o valores de la función de valor optimo f que son obvios o que no requieren cálculo.

Tabla de generación de estados

5

Estado actual Decisión Nuevo estado

S d Sn

-------------------------------------------------------------------------

1 2 2

3 3

-------------------------------------------------------------------------

2 5 5

9 9

------------------------------------------------------------------------

3 4 4

6 6

-------------------------------------------------------------------------

4 5 5

6 6

7 7

8 8

-------------------------------------------------------------------------

5 7 7

-------------------------------------------------------------------------

6 8 8

9 9

-------------------------------------------------------------------------

7 9 9

-------------------------------------------------------------------------

8 9 9

Procedimiento tabular de solución

S d Sn ad(S) f(Sn) R(S,d) f(S) P(S)

6

9 0 ___

8 9 9 10 0 10 10 9_

7 9 9 3 0 3 3 9_

6 8 8 7 10 17 15 9

9 9 15 0 15 __

5 7 7 7 3 10 10 7_

4 5 5 4 10 14 14 5

7 7 15 3 18

8 8 7 10 17

6 6 3 15 18 __

3 4 4 3 14 17 17 4

6 6 4 15 19 __

2 5 5 12 10 22 20 4

4 4 6 14 20 __

1 2 2 1 20 21 19 3

3 3 2 17 19 __

7

El problema de la alforja

Se tienen N objetos de peso Pi y valor Vi. Se desea escoger los objetos a llevar en una

alforja que puede llevar como máximo un peso W. La elección de los objetos debe

maximizar el valor total de la carga.

Modelo de Programación Matemática:

Max S Vi XI

s.a.

S Pi Xi < W

Xi = 0, 1 i = 1 ,… , N

Modelo de Programación Dinámica:

1. Estado :

S = ( s1, s2 )

s1 = el objeto que se va a decidir llevar o no

s2 = capacidad disponible de la alforja

2. Decisión:

d = llevar o no llevar el objeto s1.

= 1 si llevar el objeto s1

0 no llevar el objeto s1

D(S) = { 0, 1}

3. Transición :

sn1 = s1 + 1

sn2 = s2 – Ps1 * d

4. Generación de estados :

Estado inicial : S = (1,W)

Restricciones : sn1 < N, sn2 > 0

5. Función de valor óptimo :

Subproblema asociado a S = (s1,s2) : Determinar los objetos desde el s1-ésimo

objeto hasta el N-ésimo de valor total máximo, tomando en cuenta que la capacidad

disponible es s2.

f (s1,s2) = máximo valor que se puede obtener escogiendo entre los objetos desde el

s1-ésimo hasta el N-ésimo , y partiendo de una capacidad disponible de s2.

7. Función de retorno:

ad( S ) = beneficio inmediato que se obtiene al tomar la decisión d en el

estado S.

= Vs1 d

8

R(S, d) = maximo beneficio total que se obtiene al tomar la decisión d en el

estado S y desde el nuevo estado se toman las mejores decisiones.

= Vs1 * d + f ( Sn )

f ( Sn ) es el beneficio futuro que se obtiene al tomar la decisión d en el

estado S

8. Ecuación recursiva :

f ( S ) = max { R(S,d) }

dÎ D(S)

= máxima utilidad a obtener con los artículos desde el s1, partiendo con

una capacidad disponible s2.

9. Condiciones de contorno

0 si s2 < PN

f( N, s2) =

VN si s2 ³ PN

Los estados (N, s2) son los estados de contorno.

Aplicación : Se dispone de un camión de 10 ton. de capacidad para trasladar 4 bultos. Se

desea determinar los bultos a trasladar de manera que se maximice el valor total que se

traslada :

Bulto 1 2 3 4

Peso Pi (ton) 3 6 7 5

Valor Vi ($) 7 16 19 15

Solución :

Conjunto de estados : no

(3,1) (4, 1)

si

(2, 7)

si no si (4, 0)

(3, 7)

(1,10) no (4, 7)

no (3, 4) no (4, 4)

si

(2,10) (4, 3)

no si

(3,10)

no (4,10)

Procedimiento tabular de solución

9

s1 s2 d ad(s) sn1 sn2 f(Sn) R(S,d) f(S) P(S)

4 0,1,3,4 0 0 0

4 7,10 1 15 1

3 1 0 0 4 1 0 0 0 0

3 7 0 0 4 7 15 15 19 1

1 19 4 0 0 19

3 4 0 0 4 4 0 0 0 0

3 10 0 0 4 10 15 15 19 1

1 19

...