Programacion Dinámica
Páginas: 18 (4403 palabras)
Publicado: 13 de mayo de 2012
- DEFINICIÓN DE PROGRAMACIÓN DINÁMICA.
Bajo su forma general el modelo de decisiones secuenciales a las que el método se puede aplicar, se presenta de la manera siguiente:
Un sistema se encuentra en todo instante en un estado caracterizado por un cierto número de parámetros numéricos, sea el vector « y », llamada variable de estado.
La evolución del sistema através del tiempo está regida por la selección de una variable de control o de decisión.
El objetivo que se persigue es la maximización de una componente « yo » del vector de estado al final del período considerado.
En el caso de un modelo de tiempo discreto o de horizonte limitado el problema se formula como:
Max. yo (T)
y (t+1) = f ( t, y (t), u (t)( t =0, 1,...., T – 1
Por la selección de decisiones u(t) sometidas eventualmente a ciertas restricciones que toman en cuenta las condiciones iniciales impuestas.
De la misma manera, para un modelo en tiempo continuo se tendría una formulación del tipo:
Max. yo (T)
( d/dt y (t) ( f = (t, y, u).
Hagamos notar que en la mayor parte de los casoslas dos relaciones anteriores están definidas por una función « f » que no comprende la componente « yo » entre sus argumentos.
Se puede entonces representar una función definida sobre la trayectoria en el espacio de otras componentes. Esta componente está entonces enteramente definida a partir de las condiciones iniciales y de la serie de valores dados a la variable de control o dedecisión.
El método de resolución POR RECURRENCIA se basa en el principio de optimalidad de Bellman:
Representación gráfica
- Representación de la Programación Dinámica por UNA RED:
- Un estado está representado por un nodo;- una transición entre dos nodos corresponde a una decisión;
- una etapa es el punto que puede representar el tiempo.
Sea :
Lt ( j ) = costo mínimo que corresponde a la etapa « t » cuando se llega al estado « j ».
Cj,t (j1) = costo de la transición entre el estado j1 que corresponde a la etapa « t-1 » y el estado « j » correspondiente a laetapa « t »
Las ecuaciones de recurrencia son:
Lo (j) = 0
L-1 (j) = (j,1, (j1)
Lt (j) = min ( Cjt (j1) + Lt-1 (j1)(
j1
-Producción y stock (ejemplo)
Se trata de minimizar el costo de producción y el costo de almacenaje.
Llamaremos:
i = el stock al final del período « t »; t = 1, 2, ...., N
Xt = la producción durante el período t ;
Dt = demanda del producto en el curso del período « t »
Min.:
[pic]El costo de la mejor decisión cuando faltan « n » períodos por recorrer :
[pic]
Para satisfacer la demanda, ya que si la producción es muy grande, encontraríamos una cantidad a almacenar al final del período.
Para n= 0; fo (0) = 0
N = 1
F1 (i) = min ( C1 (X,0) + fo (G)(
x
f1 (i)= C1 (d1 – i, 0)
n = 2
fz (i) = min ( C2 (x, i + x –d2) + f1 (i + x – d2)(
x
d2 – i ( x ( d1 + d2 - i
fN (i) = ...................
El problema se puede resolver utilizando el algoritmo del «camino más corto».
EL PROBLEMA DE PRODUCCIÓN Y ALMACENAMIENTO ÓPTIMOS, SE PUEDE...
Bajo su forma general el modelo de decisiones secuenciales a las que el método se puede aplicar, se presenta de la manera siguiente:
Un sistema se encuentra en todo instante en un estado caracterizado por un cierto número de parámetros numéricos, sea el vector « y », llamada variable de estado.
La evolución del sistema através del tiempo está regida por la selección de una variable de control o de decisión.
El objetivo que se persigue es la maximización de una componente « yo » del vector de estado al final del período considerado.
En el caso de un modelo de tiempo discreto o de horizonte limitado el problema se formula como:
Max. yo (T)
y (t+1) = f ( t, y (t), u (t)( t =0, 1,...., T – 1
Por la selección de decisiones u(t) sometidas eventualmente a ciertas restricciones que toman en cuenta las condiciones iniciales impuestas.
De la misma manera, para un modelo en tiempo continuo se tendría una formulación del tipo:
Max. yo (T)
( d/dt y (t) ( f = (t, y, u).
Hagamos notar que en la mayor parte de los casoslas dos relaciones anteriores están definidas por una función « f » que no comprende la componente « yo » entre sus argumentos.
Se puede entonces representar una función definida sobre la trayectoria en el espacio de otras componentes. Esta componente está entonces enteramente definida a partir de las condiciones iniciales y de la serie de valores dados a la variable de control o dedecisión.
El método de resolución POR RECURRENCIA se basa en el principio de optimalidad de Bellman:
Representación gráfica
- Representación de la Programación Dinámica por UNA RED:
- Un estado está representado por un nodo;- una transición entre dos nodos corresponde a una decisión;
- una etapa es el punto que puede representar el tiempo.
Sea :
Lt ( j ) = costo mínimo que corresponde a la etapa « t » cuando se llega al estado « j ».
Cj,t (j1) = costo de la transición entre el estado j1 que corresponde a la etapa « t-1 » y el estado « j » correspondiente a laetapa « t »
Las ecuaciones de recurrencia son:
Lo (j) = 0
L-1 (j) = (j,1, (j1)
Lt (j) = min ( Cjt (j1) + Lt-1 (j1)(
j1
-Producción y stock (ejemplo)
Se trata de minimizar el costo de producción y el costo de almacenaje.
Llamaremos:
i = el stock al final del período « t »; t = 1, 2, ...., N
Xt = la producción durante el período t ;
Dt = demanda del producto en el curso del período « t »
Min.:
[pic]El costo de la mejor decisión cuando faltan « n » períodos por recorrer :
[pic]
Para satisfacer la demanda, ya que si la producción es muy grande, encontraríamos una cantidad a almacenar al final del período.
Para n= 0; fo (0) = 0
N = 1
F1 (i) = min ( C1 (X,0) + fo (G)(
x
f1 (i)= C1 (d1 – i, 0)
n = 2
fz (i) = min ( C2 (x, i + x –d2) + f1 (i + x – d2)(
x
d2 – i ( x ( d1 + d2 - i
fN (i) = ...................
El problema se puede resolver utilizando el algoritmo del «camino más corto».
EL PROBLEMA DE PRODUCCIÓN Y ALMACENAMIENTO ÓPTIMOS, SE PUEDE...
Leer documento completo
Regístrate para leer el documento completo.