Programacion dinamica.
Enviado por mondoro • 28 de Octubre de 2017 • 3.396 Palabras (14 Páginas) • 424 Visitas
...
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
...