Essays.club - Ensayos gratis, notas de cursos, notas de libros, tareas, monografías y trabajos de investigación
Buscar

Programacion dinamica.

Enviado por   •  28 de Octubre de 2017  •  3.396 Palabras (14 Páginas)  •  423 Visitas

Página 1 de 14

...

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

...

Descargar como  txt (18.8 Kb)   pdf (132.8 Kb)   docx (23.2 Kb)  
Leer 13 páginas más »
Disponible sólo en Essays.club