Regimen Fiscal
Enviado por luisjosemartinez • 3 de Diciembre de 2012 • 1.103 Palabras (5 Páginas) • 359 Visitas
Características de las Aplicaciones de Programación Dinámica
A continuación veremos una explicación sobre las características del Ejemplo 3 que son comunes a la
mayor parte de las aplicaciones de la programación dinámica.
CARACTERÍSTICA 1
El problema se puede dividir en etapas; cada etapa requiere una decisión.
En el Ejemplo 3, la etapa t consistió en aquellas ciudades donde pudiera estar Juan al principio del día
t de su viaje.
En muchos problemas de programación dinámica, la etapa es la cantidad de tiempo que pasa desde el
inicio del problema.
Notaremos que en ciertos casos no se necesitan decisiones en cada etapa.
CARACTERÍSTICA 2
Cada etapa tiene un número de estados asociados con ella.
Por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima.
En el Ejemplo 3, el estado en la etapa t es simplemente la ciudad donde Juan está al inicio del día t
Por ejemplo, en la etapa 3, los estados posibles son Kansas City, Omaha y Dallas.
Observe que para tomar la decisión correcta en cada etapa Juan no necesita conocer cómo llegó hasta
su lugar actual.
Por ejemplo, si Juan se encuentra en Kansas City, entonces sus decisiones restantes no dependen de
cómo llegó a Kansas City; sus decisiones futuras sólo dependen del hecho que ahora está en Kansas
City.
CARACTERÍSTICA 3
La decisión tomada en cualquier etapa indica cómo se transforma el estado en la etapa actual en el
estado en la siguiente etapa.
En el Ejemplo 3, la decisión de Juan en cualquier etapa simplemente es cuál ciudad visitar.
Esto determina el estado en la siguiente etapa en forma obvia.
En muchos problemas, una decisión no determina con certeza el estado de la siguiente etapa; en lugar
de ello, la decisión actual sólo determina la distribución de probabilidad del estado en la etapa siguiente.
CARACTERÍSTICA 4
Dado el estado actual, la decisión óptima para cada una de las etapas restantes no debe depender de
estados previamente alcanzados o de decisiones previamente tomadas.
A esta idea se le conoce como principio de optimalidad.
En el contexto del Ejemplo 3, el principio de optimalidad se reduce a lo siguiente: Suponga que se sabe
que la trayectoria más corta (llamémosla R) de la ciudad 1 a la 10 pasa por la ciudad i
Entonces, la parte de R, que va de la ciudad i a la ciudad 10 debe ser una de las trayectorias más cortas
de la ciudad i a la ciudad 10.
Si no fuera así, podríamos crear una trayectoria de la ciudad 1 a la 10 que fuera más corta que R, mediante
la anexión de una trayectoria más corta de la ciudad i a la ciudad 10 a la parte de R que lleva de
la ciudad 1 a la 10.
Esto crearía una trayectoria de la ciudad 1 a la ciudad 10 que es más corta que R, con lo que se contradice
el hecho de que R es una de las trayectorias más cortas de la ciudad 1 a la 10.
Por ejemplo si se sabe que la trayectoria más corta de la ciudad 1 a la 10 pasa por la ciudad 2, entonces
la trayectoria más corta de la ciudad 1 a la 10 debe comprender una de las trayectorias más cortas de la ciudad 2 a la 10 (2—5—8—10).
Esto es así porque cualquier trayectoria de la ciudad 1 a
...