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

...