ECUACIONES

La ecuación de Duhem – Margules , llamada así por Pierre Duhem y Max Margules , es una declaración termodinámica de la relación entre los dos componentes de un solo líquido donde la mezcla de vapor se considera un gas ideal :

$${\ displaystyle \ left ({\ frac {d \, \ ln \, P_ {A}} {d \, \ ln \, x_ {A}}} \ right) _ {T, P} = \ left ({ \ frac {d \, \ ln \, P_ {B}} {d \, \ ln \, x_ {B}}} \ right) _ {T, P}}

donde P _A y P _B son las presiones de vapor parciales de los dos constituyentes y x _A y x _B son las fracciones molares del líquido.

Derivación

La ecuación de Duhem - Margulus da la relación entre el cambio de la fracción molar con la presión parcial de un componente en una mezcla líquida.

Consideremos una mezcla líquida binaria de dos componentes en equilibrio con su vapor a temperatura y presión constantes. Entonces de Gibbs - la ecuación de Duhem es

n _A dμ _A + n _B dμ _B = 0 ... (I)

Donde n _A y n _B son el número de moles del componente A y B, mientras que μ _A y μ _B es su potencial químico.

Dividiendo equ. (i) por n _A + n _B , entonces

(n _A / n _A + n _B ) dμ _A + (n _B / n _A + n _B ) dμ _B = 0

O

x _A dμ _A + x _B dμ _B = 0. ... (ii)

Ahora, el potencial químico de cualquier componente en la mezcla depende de la temperatura, la presión y la composición de la mezcla. Por lo tanto, si la temperatura y la presión toman un potencial químico constante, entonces

dμ _A = (dμ _A / dx _A ) _{T, P} dx _A ... (iii)

dμ _B = (dμ _B / dx _B ) _{T, P} dx _B . ... (iv)

Poniendo estos valores en equ. (ii), entonces

x _A (dμ _Α / dx _A ) _{T, P} dx _A + x _B (dμ _B / dx _B ) _{T, P} dx _B = 0 ... (v)

Debido a que la suma de la fracción molar de todos los componentes en la mezcla es la unidad, es decir,

x ₁ + x ₂ = 1

Por lo tanto

dx ₁ + dx ₂ = 0 o dx ₁ = -dx ₂

poniendo estos valores en equ. (v), entonces

x _A (dμ _Α / dx _A ) _{T, P} = x _B (dμ _B / dx _B ) _{T, P} ... (vi)

Ahora el potencial químico de cualquier componente en la mezcla es tal que

μ = μ _o + RT en P, donde P es la presión parcial del componente. Ahora diferenciando este equ.

dμ / dx = RT (d In P / dx)

Anteriormente, se puede escribir para el componente A y B es

dμ _A / dx _A = RT (d In P _A / dx _A )… (vii)

dμ _B / dx _B = RT (d En P _B / dx _B )… (viii)

Sustituyendo estos valores en la ecuación (vi), entonces

x _A (d In P _A / dx _A ) = x _B (d In P _B / dx _B )

o

(d En P _A / d lnx _A ) = (d En P _B / d lnx _B )

esta es la ecuación final de la ecuación de Duhem-Margules.

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

No debe confundirse con lenguaje de programación dinámico o problema dinámico .

Figura 1. Encontrar la ruta más corta en un gráfico utilizando una subestructura óptima; una línea recta indica un solo borde; una línea ondulada indica una ruta más corta entre los dos vértices que conecta (entre otras rutas, no mostradas, que comparten los mismos dos vértices); La línea en negrita es el camino más corto en general desde el inicio hasta la meta.

La programación dinámica es tanto un método de optimización matemática como un método de programación por computadora. El método fue desarrollado por Richard Bellman en la década de 1950 y ha encontrado aplicaciones en numerosos campos, desde la ingeniería aeroespacial hasta la economía . En ambos contextos, se refiere a simplificar un problema complicado dividiéndolo en subproblemas más simples en una recursivamanera. Si bien algunos problemas de decisión no se pueden separar de esta manera, las decisiones que abarcan varios puntos en el tiempo a menudo se dividen recursivamente. Del mismo modo, en ciencias de la computación, si un problema puede resolverse de manera óptima dividiéndolo en subproblemas y luego encontrando recursivamente las soluciones óptimas para los subproblemas, se dice que tiene subestructura óptima .

Si los subproblemas se pueden anidar recursivamente dentro de problemas mayores, de modo que los métodos de programación dinámica sean aplicables, entonces existe una relación entre el valor del problema mayor y los valores de los subproblemas. ^[1] En la literatura de optimización, esta relación se llama la ecuación de Bellman .

Descripción general [ editar ]

Optimización matemática [ editar ]

En términos de optimización matemática, la programación dinámica generalmente se refiere a simplificar una decisión dividiéndola en una secuencia de pasos de decisión a lo largo del tiempo. Esto se hace definiendo una secuencia de funciones de valores V ₁ , V ₂ , ..., V _n tomando y como un argumento que representa el estadodel sistema en los tiempos i de 1 a n . La definición de V _n ( y ) es el valor obtenido en el estado y en la última vez que n . Los valores V _i en tiempos anteriores i =  n  −1,  n  - 2, ..., 2, 1 se puede encontrar trabajando hacia atrás, usando una relación recursiva llamada ecuación de Bellman . Para i  = 2, ...,  n , V _i −1 en cualquier estado y se calcula a partir de V _i maximizando una función simple (generalmente la suma) de la ganancia de una decisión en el tiempo i  - 1 y la función V _i en el nuevo estado del sistema si se toma esta decisión. Dado que V _i ya se ha calculado para los estados necesarios, la operación anterior produce V _i−1 para esos estados. Finalmente, V ₁ en el estado inicial del sistema es el valor de la solución óptima. Los valores óptimos de las variables de decisión se pueden recuperar, uno por uno, haciendo un seguimiento de los cálculos ya realizados.

Teoría de control [ editar ]

En teoría del control , un problema típico es encontrar un control admisible$${\ displaystyle \ mathbf {u} ^ {\ ast}} lo que hace que el sistema $${\ displaystyle {\ dot {\ mathbf {x}}} (t) = \ mathbf {g} \ left (\ mathbf {x} (t), \ mathbf {u} (t), t \ right)} seguir una trayectoria admisible $${\ displaystyle \ mathbf {x} ^ {\ ast}} en un intervalo de tiempo continuo $${\ displaystyle t_ {0} \ leq t \ leq t_ {1}}que minimiza una función de costo

$${\ displaystyle J = b \ left (\ mathbf {x} (t_ {1}), t_ {1} \ right) + \ int _ {t_ {0}} ^ {t_ {1}} f \ left (\ mathbf {x} (t), \ mathbf {u} (t), t \ right) \ mathrm {d} t}

La solución a este problema es una ley o política de control óptimo. $${\ displaystyle \ mathbf {u} ^ {\ ast} = h (\ mathbf {x} (t), t)}, lo que produce una trayectoria óptima. $${\ displaystyle \ mathbf {x} ^ {\ ast}} y una función de pérdida optimizada $${\ displaystyle J ^ {\ ast}}. Este último obedece a la ecuación fundamental de la programación dinámica:

$${\ displaystyle -J_ {t} ^ {\ ast} = \ min _ {\ mathbf {u}} \ left \ {f \ left (\ mathbf {x} (t), \ mathbf {u} (t), t \ right) + J_ {x} ^ {\ ast {\ mathsf {T}}} \ mathbf {g} \ left (\ mathbf {x} (t), \ mathbf {u} (t), t \ right )\Correcto\}}

una ecuación diferencial parcial conocida como la ecuación de Hamilton-Jacobi-Bellman , en la cual$${\ displaystyle J_ {x} ^ {\ ast} = {\ frac {\ partial J ^ {\ ast}} {\ partial \ mathbf {x}}} = \ left [{\ frac {\ partial J ^ {\ ast}} {\ parcial x_ {1}}} ~~~~ {\ frac {\ parcial J ^ {\ ast}} {\ parcial x_ {2}}} ~~~~ \ dots ~~~~ {\ frac {\ parcial J ^ {\ ast}} {\ parcial x_ {n}}} \ derecha] ^ {\ mathsf {T}}} y $${\ displaystyle J_ {t} ^ {\ ast} = {\ frac {\ partial J ^ {\ ast}} {\ partial t}}}. Uno encuentra la minimización.$${\ displaystyle \ mathbf {u}} en términos de $${\ displaystyle t}, $${\ displaystyle \ mathbf {x}}, y la función desconocida $${\ displaystyle J_ {x} ^ {\ ast}} y luego sustituye el resultado en la ecuación de Hamilton-Jacobi-Bellman para obtener la ecuación diferencial parcial que se resolverá con la condición de contorno $${\ displaystyle J \ left (t_ {1} \ right) = b \ left (\ mathbf {x} (t_ {1}), t_ {1} \ right)}. ^[2]En la práctica, esto generalmente requiere técnicas numéricas para alguna aproximación discreta a la relación de optimización exacta.

Alternativamente, el proceso continuo se puede aproximar mediante un sistema discreto, que conduce a una relación de recurrencia siguiente análoga a la ecuación de Hamilton-Jacobi-Bellman:

$${\ displaystyle J_ {k} ^ {\ ast} \ left (\ mathbf {x} _ {nk} \ right) = \ min _ {\ mathbf {u} _ {nk}} \ left \ {{\ hat { f}} \ left (\ mathbf {x} _ {nk}, \ mathbf {u} _ {nk} \ right) + J_ {k-1} ^ {\ ast} \ left ({\ hat {g}} \ left (\ mathbf {x} _ {nk}, \ mathbf {u} _ {nk} \ right) \ right) \ right \}}

en el $${\ displaystyle k}-th etapa de $${\ displaystyle n} intervalos de tiempo discretos igualmente espaciados, y donde $${\ displaystyle {\ hat {f}}} y $${\ displaystyle {\ hat {g}}} denotar aproximaciones discretas a $${\ displaystyle f} y $${\ displaystyle \ mathbf {g}}. Esta ecuación funcional se conoce como la ecuación de Bellman , que se puede resolver para obtener una solución exacta de la aproximación discreta de la ecuación de optimización. ^[3]

Ejemplo de economía: el problema de ahorro óptimo de Ramsey [ editar ]

Ver también: modelo Ramsey-Cass-Koopmans.

En economía, el objetivo generalmente es maximizar (en lugar de minimizar) alguna función dinámica de bienestar social . En el problema de Ramsey, esta función relaciona las cantidades de consumo con los niveles de utilidad . En términos generales, el planificador se enfrenta a la compensación entre el consumo contemporáneo y el consumo futuro (a través de la inversión en el capital social que se utiliza en la producción), conocida como elección intertemporal . El consumo futuro se descuenta a una tasa constante.$${\ displaystyle \ beta \ in (0,1)}. Una aproximación discreta a la ecuación de transición del capital está dada por

$${\ displaystyle k_ {t + 1} = {\ hat {g}} \ left (k_ {t}, c_ {t} \ right) = f (k_ {t}) - c_ {t}}

dónde $${\ displaystyle c} es el consumo, $${\ displaystyle k} es capital, y $${\ displaystyle f}Es una función de producción que satisface las condiciones de Inada . Un capital social inicial{\ displaystyle k_ {0}> 0} se supone.

Dejar $${\ displaystyle c_ {t}}Se consumirá en el periodo t , y se asumirá que el consumo genera utilidad. $${\ displaystyle u (c_ {t}) = \ ln (c_ {t})}Mientras el consumidor viva. Supongamos que el consumidor es impaciente, por lo que descuenta la utilidad futura en un factor b en cada período, donde{\ displaystyle 0 . Dejar$${\ displaystyle k_ {t}}Ser capital en el periodo t . Supongamos que el capital inicial es una cantidad dada{\ displaystyle k_ {0}> 0}y supongamos que el capital y el consumo de este período determinan el capital del próximo período como $${\ displaystyle k_ {t + 1} = Ak_ {t} ^ {a} -c_ {t}}, donde A es una constante positiva y{\ displaystyle 0 . Supongamos que el capital no puede ser negativo. Entonces el problema de decisión del consumidor se puede escribir de la siguiente manera:

$${\ displaystyle \ max \ sum _ {t = 0} ^ {T} b ^ {t} \ ln (c_ {t})} sujeto a $${\ displaystyle k_ {t + 1} = Ak_ {t} ^ {a} -c_ {t} \ geq 0} para todos $${\ displaystyle t = 0,1,2, \ ldots, T}

Escrito de esta manera, el problema parece complicado, porque implica resolver todas las variables de elección $${\ displaystyle c_ {0}, c_ {1}, c_ {2}, \ ldots, c_ {T}}. (Tenga en cuenta que$${\ displaystyle k_ {0}} no es una variable de elección: el capital inicial del consumidor se toma como se indica.)

El enfoque de programación dinámica para resolver este problema implica dividirlo en una secuencia de decisiones más pequeñas. Para ello, definimos una secuencia de funciones de valor. $${\ displaystyle V_ {t} (k)}, para $${\ displaystyle t = 0,1,2, \ ldots, T, T + 1}que representan el valor de tener cualquier cantidad de capital k en cada momento t . Tenga en cuenta que$${\ displaystyle V_ {T + 1} (k) = 0}, es decir, no hay (por supuesto) ninguna utilidad de tener capital después de la muerte.

El valor de cualquier cantidad de capital en cualquier momento anterior se puede calcular por inducción hacia atrás utilizando la ecuación de Bellman . En este problema, para cada$${\ displaystyle t = 0,1,2, \ ldots, T}, la ecuación de Bellman es

$${\ displaystyle V_ {t} (k_ {t}) \, = \, \ max \ left (\ ln (c_ {t}) + bV_ {t + 1} (k_ {t + 1}) \ right)} sujeto a $${\ displaystyle k_ {t + 1} = Ak_ {t} ^ {a} -c_ {t} \ geq 0}

Este problema es mucho más simple que el que anotamos antes, porque involucra solo dos variables de decisión, $${\ displaystyle c_ {t}} y $${\ displaystyle k_ {t + 1}}. Intuitivamente, en lugar de elegir su plan de toda la vida al nacer, el consumidor puede tomar las cosas paso a paso. En el momento t , su capital actual.$${\ displaystyle k_ {t}} Se da, y solo necesita elegir consumo actual. $${\ displaystyle c_ {t}} y ahorrando $${\ displaystyle k_ {t + 1}}.

Para resolver realmente este problema, trabajamos hacia atrás. Por simplicidad, el nivel actual de capital se denota como k .$${\ displaystyle V_ {T + 1} (k)} Ya se conoce, así que usando la ecuación de Bellman una vez que podamos calcular $${\ displaystyle V_ {T} (k)}, y así sucesivamente hasta que lleguemos a $${\ displaystyle V_ {0} (k)}, que es el valor del problema de decisión inicial para toda la vida. En otras palabras, una vez que sepamos$${\ displaystyle V_ {T-j + 1} (k)}, podemos calcular $${\ displaystyle V_ {Tj} (k)}, que es el máximo de $${\ displaystyle \ ln (c_ {Tj}) + bV_ {T-j + 1} (Ak ^ {a} -c_ {Tj})}, dónde $${\ displaystyle c_ {Tj}} es la variable de elección y $${\ displaystyle Ak ^ {a} -c_ {Tj} \ geq 0}.

Trabajando hacia atrás, se puede mostrar que el valor funciona en el momento $${\ displaystyle t = Tj} es

$${\ displaystyle V_ {Tj} (k) \, = \, a \ sum _ {i = 0} ^ {j} a ^ {i} b ^ {i} \ ln k + v_ {Tj}}

donde cada $${\ displaystyle v_ {Tj}} Es una constante, y la cantidad óptima para consumir en el tiempo. $${\ displaystyle t = Tj} es

$${\ displaystyle c_ {Tj} (k) \, = \, {\ frac {1} {\ sum _ {i = 0} ^ {j} a ^ {i} b ^ {i}}} Ak ^ {a }}

que se puede simplificar a

{\ displaystyle {\ begin {alineado} c_ {T} (k) & = Ak ^ {a} \\ c_ {T-1} (k) & = {\ frac {Ak ^ {a}} {1 + ab }} \\ c_ {T-2} (k) & = {\ frac {Ak ^ {a}} {1 + ab + a ^ {2} b ^ {2}}} \\ & \ dots \\ c_ {2} (k) & = {\ frac {Ak ^ {a}} {1 + ab + a ^ {2} b ^ {2} + \ ldots + a ^ {T-2} b ^ {T-2 }}} \\ c_ {1} (k) & = {\ frac {Ak ^ {a}} {1 + ab + a ^ {2} b ^ {2} + \ ldots + a ^ {T-2} b ^ {T-2} + a ^ {T-1} b ^ {T-1}}} \\ c_ {0} (k) & = {\ frac {Ak ^ {a}} {1 + ab + a ^ {2} b ^ {2} + \ ldots + a ^ {T-2} b ^ {T-2} + a ^ {T-1} b ^ {T-1} + a ^ {T} b ^ {T}}} \ end {alineado}}}

Vemos que es óptimo consumir una fracción más grande de la riqueza actual a medida que uno envejece, finalmente consumiendo toda la riqueza restante en el período T , el último período de la vida.

Ejemplos: algoritmos informáticos [ editar ]

El algoritmo de Dijkstra para el problema de la ruta más corta [ editar ]

Desde el punto de vista de la programación dinámica, el algoritmo de Dijkstra para el problema de la ruta más corta es un esquema de aproximación sucesiva que resuelve la ecuación funcional de la programación dinámica para el problema de la ruta más corta mediante el método Reaching . ^{[7] [8] [9]}

De hecho, la explicación de Dijkstra de la lógica detrás del algoritmo, ^{[10] a} saber

Problema 2. Encuentre la ruta de la longitud total mínima entre dos nodos dados$${\ displaystyle P} y $${\ displaystyle Q}.

Utilizamos el hecho de que, si $${\ displaystyle R} es un nodo en el camino mínimo desde $${\ displaystyle P} a $${\ displaystyle Q}, el conocimiento de este último implica el conocimiento del camino mínimo desde $${\ displaystyle P} a $${\ displaystyle R}.

es una paráfrasis del famoso Principio de Optimalidad de Bellman en el contexto del problema del camino más corto .

Secuencia de Fibonacci [ editar ]

Aquí es una aplicación ingenua de una función de búsqueda de la n º miembro de la sucesión de Fibonacci , basado directamente en la definición matemática:

   función fib (n)
        si n <= 1 retorno n
        retorno fib (n - 1) + fib (n - 2)

Tenga en cuenta que si llamamos, digamos, fib(5)producimos un árbol de llamadas que llama a la función en el mismo valor muchas veces:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

En particular, fib(2)se calculó tres veces desde cero. En ejemplos más grandes , se recalculan muchos más valores fibo subproblemas , lo que lleva a un algoritmo de tiempo exponencial.

Ahora, supongamos que tenemos un objeto de mapa simple , m , que asigna cada valor de fibese ya calculado a su resultado, y modificamos nuestra función para usarlo y actualizarlo. La función resultante requiere solo O ( n ) tiempo en lugar de tiempo exponencial (pero requiere O ( n ) espacio):

   var m: = mapa (0 → 0, 1 → 1)
    función fib (n)
        si la tecla n no está en el mapa m
           m [n]: = fib (n - 1) + fib (n - 2)
       devolver m [n]

Esta técnica de guardar valores que ya se han calculado se denomina memorización ; Este es el enfoque de arriba hacia abajo, ya que primero dividimos el problema en subproblemas y luego calculamos y almacenamos los valores.

En el enfoque de abajo hacia arriba , calculamos los valores más pequeños del fibprimero, luego construimos valores más grandes a partir de ellos. Este método también usa el tiempo O ( n ) ya que contiene un bucle que se repite n - 1 veces, pero solo ocupa espacio constante (O (1)), en contraste con el enfoque de arriba hacia abajo que requiere espacio O ( n ) para almacenar el mapa.

   función fib (n)
        si n = 0
            devuelve 0
        o 
           var var FIB anterior: = 0, currentFib: = 1
            repetición n - 1 veces  // el bucle se omite si n = 1 
               var newFib: = previousFib + currentFib
               previousFib: = currentFib
               currentFib: = newFib
       volver currentFib

En ambos ejemplos, solo calculamos fib(2)una vez, y luego lo usamos para calcular ambos fib(4)y fib(3), en lugar de calcularlos cada vez que se evalúa uno de ellos.

Tenga en cuenta que el método anterior realmente toma $${\ displaystyle \ Omega (n ^ {2})} tiempo para n grande porque la suma de dos enteros con $${\ displaystyle \ Omega (n)} bits cada uno toma $${\ displaystyle \ Omega (n)}hora. (El n ^º número de fibonacci tiene$${\ displaystyle \ Omega (n)}bits.) Además, existe una forma cerrada para la secuencia de Fibonacci, conocida como fórmula de Binet , de la cual$${\ displaystyle n}-el término se puede calcular en aproximadamente$${\ displaystyle O (n (\ log n) ^ {2})}Tiempo, que es más eficiente que la técnica de programación dinámica anterior. Sin embargo, la simple recurrencia da directamente la forma de matriz que conduce a una$${\ displaystyle O (n \ log n)}Algoritmo por exponencia rápida de matrices .