Programación dinámica. Programación dinámica. Problemas clásicos

Programación dinámica

1. Programación dinámica. Conceptos básicos……………………2

2. La esencia del método de programación dinámica…………………………..4

3. Un ejemplo de resolución de un problema utilizando el método de programación dinámica…………………………………………………………...7

Lista de fuentes utilizadas……………………………………...11

1. Programación dinámica. Conceptos básicos.

Programación dinámica (DP) en la teoría de sistemas informáticos, una forma de resolver problemas complejos dividiéndolos en subtareas más simples. Se aplica a problemas con una subestructura óptima, que parece un conjunto de subproblemas superpuestos cuya complejidad es ligeramente menor que la original. En este caso, el tiempo de cálculo, en comparación con los métodos "ingenuos", se puede reducir significativamente.

La idea clave en la programación dinámica es bastante simple. Como regla general, para resolver un problema determinado, es necesario resolver partes individuales del problema (subtareas) y luego combinar las soluciones de las subtareas en una solución general. A menudo, muchas de estas subtareas son las mismas. El enfoque de programación dinámica consiste en resolver cada subproblema solo una vez, reduciendo así la cantidad de cálculos. Esto es especialmente útil en casos donde el número de subtareas repetidas es exponencialmente grande.

La programación dinámica es una técnica matemática que aborda la solución de una determinada clase de problemas dividiéndolos en partes, problemas más pequeños y menos complejos. Al mismo tiempo, un rasgo distintivo es la solución de problemas por etapas, a intervalos fijos, períodos de tiempo, lo que determinó la aparición del término programación dinámica. Cabe señalar que los métodos de programación dinámica también se utilizan con éxito para resolver problemas en los que no se tiene en cuenta el factor tiempo. En general, el aparato matemático se puede representar como programación paso a paso o paso a paso. La solución de problemas mediante métodos de programación dinámica se realiza sobre la base del principio de optimización formulado por R. E. Bellman: el comportamiento óptimo tiene la propiedad de que cualquiera que sea el estado inicial del sistema y la solución inicial, la solución posterior debe determinar el comportamiento óptimo. relativo al estado obtenido como resultado de la solución inicial.
De esto se desprende que la planificación de cada paso debe realizarse teniendo en cuenta el beneficio global obtenido al finalizar todo el proceso, lo que permite optimizar el resultado final según el criterio seleccionado.

Así, la programación dinámica en un sentido amplio es el control óptimo de un proceso cambiando los parámetros controlados en cada paso y, por tanto, influyendo en el progreso del proceso, cambiando el estado del sistema en cada paso.

En general, la programación dinámica es una teoría armoniosa de entender y lo suficientemente simple como para ser utilizada en actividades comerciales al resolver problemas tanto lineales como no lineales.

La programación dinámica es una de las ramas de la programación óptima. Se caracteriza por métodos y técnicas específicos aplicados a operaciones en las que el proceso de toma de decisiones se divide en etapas (pasos). Los métodos de programación dinámica se utilizan para resolver problemas de optimización de variantes con criterios de optimización dados, con ciertas conexiones entre las variables y la función objetivo, expresadas por un sistema de ecuaciones o desigualdades. En este caso, como en los problemas resueltos mediante métodos de programación lineal, las restricciones se pueden dar en forma de igualdades o desigualdades. Sin embargo, si en problemas de programación lineal las dependencias entre la función criterio y las variables son necesariamente lineales, entonces en problemas de programación dinámica estas dependencias también pueden ser no lineales. La programación dinámica se puede utilizar tanto para resolver problemas asociados con la dinámica de un proceso o sistema, como para problemas estáticos asociados, por ejemplo, con la asignación de recursos. Esto amplía significativamente el alcance de la programación dinámica para resolver problemas de control. Y la posibilidad de simplificar el proceso de solución, que se logra limitando el área y el número de examinados al pasar a la siguiente etapa de opciones, aumenta las ventajas de este conjunto de métodos.

Sin embargo, la programación dinámica también tiene desventajas. En primer lugar, no existe un único método de solución universal. Casi todos los problemas resueltos por este método tienen sus propias características y requieren la búsqueda del conjunto de métodos más adecuado para resolverlo. Además, los grandes volúmenes y la complejidad de resolver problemas de varios pasos con muchos estados llevan a la necesidad de seleccionar problemas de baja dimensión o utilizar información comprimida. Esto último se logra utilizando métodos para analizar opciones y procesar la lista de estados.

Para procesos de tiempo continuo, la programación dinámica se considera una versión limitante de un esquema de solución discreta. Los resultados obtenidos en este caso prácticamente coinciden con los obtenidos por los métodos máximos de L. S. Pontryagin o Hamilton-Jacobi-Bellman.

La programación dinámica se utiliza para resolver problemas en los que la búsqueda de un óptimo es posible con un enfoque paso a paso, por ejemplo, la distribución de inversiones de capital escasas entre nuevas áreas de su uso; desarrollo de reglas de gestión de demanda o inventario que establezcan el momento de reabastecimiento y el tamaño de la orden de reabastecimiento; desarrollo de principios para la programación de la producción y la igualación del empleo en condiciones de demanda fluctuante de productos; elaboración de planes calendario para reparaciones importantes y actuales de equipos y su reemplazo; buscar las distancias más cortas en la red de transporte; formación de la secuencia de desarrollo de una operación comercial, etc.

La esencia del método de programación dinámica.

El método de programación dinámica se basa en principio de optimidad, formulado en 1957 por el matemático estadounidense Richard Bellman: “El comportamiento óptimo tiene la propiedad de que cualquiera que sea el estado inicial y la decisión en el momento inicial, las decisiones posteriores deben constituir un comportamiento óptimo en relación con el estado resultante de la primera decisión”.

La esencia física del principio de optimización es que el error al elegir una solución en este momento no se puede corregir en el futuro.

Se considera el siguiente problema general. Existe un determinado sistema físico en el que ocurre algún proceso, que consiste en norte pasos. La eficiencia del proceso se caracteriza por algún indicador. W. que se llama ganar. Deja que la ganancia total W. para todo norte Los pasos del proceso se componen de ganancias en pasos individuales.

Dónde yo- ganancias en i-ésimo paso. Si W. tiene esta propiedad, se llama criterio aditivo.

El proceso en cuestión es un proceso controlado, es decir. es posible elegir algunos parámetros que influyen en su curso y resultado, y en cada paso se selecciona alguna solución, de la que dependen las ganancias en este paso. Esta solución se llama control de pasos. El conjunto de todos los controles de pasos representa el control del proceso en su conjunto. Denotémoslo con la letra. Ud. y controles de pasos, por letras. Entonces

Los controles de pasos en el caso general no son números, sino, por regla general, vectores, funciones, etc.

En el modelo de programación dinámica, el proceso en cada paso se encuentra en uno de los estados s conjunto de estados S. Se cree que cada estado está asociado con algunos controles escalonados. Estos controles son tales que el control seleccionado en un estado dado para cualquier historial previo del proceso determina completamente el siguiente estado del proceso. Normalmente hay dos condiciones especiales: s 0 - inicial y sudoeste-final.

Entonces, supongamos que a cada estado se le asigne un conjunto de controles de paso admisibles, y cada control de paso corresponde - el estado desde el que entra el proceso si yo como resultado del uso del control por pasos tu. Deja que el proceso esté en su estado inicial. s 0. La elección pone el proceso en estado s 1 = σ( s 0 ,tu 1), elección - indicar s 2 = σ( s 1 ,tu 2) etc. El resultado es una trayectoria de proceso que consta de una secuencia de pares

y termina con el estado final. Por coherencia, podemos suponer que sólo está involucrado un estado, dejando el proceso en el mismo estado final. Cabe señalar que los conjuntos de estados y controles admisibles

finito y A nosotros para varios s no se crucen.

En general, el problema de programación dinámica se formula de la siguiente manera: encuentre una trayectoria del proceso en la que la ganancia (2.1) sea máxima.

El control que logra la máxima ganancia se llama control óptimo. Consta de un conjunto de controles de paso.

La ganancia máxima que se consigue con este control se denotará por Wmáx:

Wmáx= máximo Ud.{W.(tu)}. (2.5)

Utilizando el ejemplo del problema de la mochila, consideremos lo que se entiende por paso, estado, control y pago.

Cargar una mochila se puede considerar como un proceso que consiste en norte pasos. En cada paso, debes responder la pregunta: ¿deberías llevar este artículo en tu mochila o no? Entonces el paso del proceso es asignar a una variable. xyo valores 1 o 0.

Ahora definamos los estados. Evidentemente, el estado actual del proceso se caracteriza por la capacidad de carga residual de la mochila, el peso que queda a nuestra disposición hasta el final (hasta que la mochila esté completamente guardada). Por lo tanto, bajo el estado anterior i-se entiende por paso la cantidad

(2.6)

al mismo tiempo s 0 es el estado inicial al que corresponde el valor b- capacidad de carga inicial de la mochila.

Gestión en i El -ésimo paso significa asignación a una variable binaria xyo valores 0 o 1. Esto significa que en cada paso tenemos solo dos controles. Además, la admisibilidad del control tu yo, estableciendo xyo= 1, determinado por la condición

(2.8)

La ganancia de paso se puede definir como . Es por eso

(2.10)

Es necesario encontrar el control óptimo en el que el valor de ganancia (2.10) sea máximo.

3. Un ejemplo de resolución de un problema utilizando el método de programación dinámica.

Ejercicio. El inversor asigna fondos por valor de 5 mil den. unidades, que deberán distribuirse entre tres empresas.

Se requiere, utilizando el principio de optimización de Bellman, construir un plan para la distribución de inversiones entre empresas que proporcione la mayor ganancia total si cada empresa, al invertir en ella, x mil. unidades genera ganancias p;(x) mil. unidades (i=1, 2 y 3) según los siguientes datos:

Solución. Creemos un modelo matemático del problema.

1.El número de pasos es 3.

2. Sea la cantidad de fondos disponibles antes de un paso determinado y caracterice el estado del sistema en cada paso.

3. Control en el i-ésimo paso (i=1,2,3) seleccionamos x i - la cantidad de fondos invertidos en la i-ésima empresa.

4. La ganancia p i (xi) en el i-ésimo paso es la ganancia que genera la i-ésima empresa al invertir fondos xi en ella. Si denotamos el beneficio total W ganando en su conjunto, entonces W=p 1 (x 1)+ p 2 (x 2)+ p 3 (x 3).

5. Si se dispone de fondos por valor de s.000 den. unidades y se invierten x mil dinero en la i-ésima empresa. unidades, entonces quedan (s-x) miles de dinero para futuras inversiones. unidades Por lo tanto, si en el i-ésimo paso el sistema estaba en el estado s y se seleccionó el control x, entonces en el (i+1)-ésimo paso el sistema estará en el estado (s-x) y, por lo tanto, la función de transición a un nuevo estado tiene la forma: f i (s, x) = s-x.

6. En el último paso (i=3), el control óptimo corresponde a la cantidad de fondos disponibles y la ganancia es igual a los ingresos generados por la última empresa: x 3 (s) = s, W 3 (s) = página 3 (s).

7. De acuerdo con el principio de optimización de Bellman, el control en cada paso debe elegirse de modo que la suma de los beneficios en todos los pasos restantes hasta el final del proceso, incluido el beneficio en este paso, sea óptima. La ecuación funcional principal toma la forma

W 2 (s) = máx( pag 2(x) + W 3 (s - incógnita))

Realicemos una optimización paso a paso, en función de cuyos resultados completaremos la tabla.

s	yo=3	yo=2	yo=1
	x 3(es)	W3(s)	x2(es)	W2(s)	xi(s)	Wi (s)
		4,27		4,27
		7,64		7,64
		10,25		10,97
		15,93		15,93
		16,12		19,26		19,26

La primera columna de la tabla registra los posibles estados del sistema y la línea superior contiene el número de pasos con control y rentabilidad óptimos en cada paso, comenzando desde el último. Dado que para el último paso i=3 la ecuación funcional tiene la forma x 3 (s)=s, W3(s)=p3(s), entonces las dos columnas de la tabla correspondientes a i=3 se completan automáticamente según la tabla de datos de origen.

En el paso i=2 la ecuación funcional principal tiene la forma

W 2 (s) = máx(p 2 (x) + W 3 (s - x))

Por lo tanto, para llevar a cabo la optimización en este paso, completamos la tabla para varios estados s en el paso i=3.

s	incógnita	sexo	p2(x)	W 3 (sexo)	p 2 (x)+W 3 (s-x)	W2(s)
				4,27	4,27	4,27
		3,33		3,33
				7,64	7,64	7,64
		3,33	4,27	7,6
		4,87		4,87
				10,25	10,25	10,97
		3,33	7,64	10,97
		4,87	4,27	9,14
		5,26		5,26
				15,93	15,93	15,93
		3,33	10,25	13,58
		4,87	7,64	12,51
		5,26	4,27	9,53
		7,34		7,34
				16,12	16,12	19,26
		3,33	15,93	19,26
		4,87	10,25	15,12
		5,26	7,64	12,9
		7,34	4,27	11,61
		9,49		9,49

En el paso i=1 la ecuación funcional principal tiene la forma

W x (s) = máx( p x (x) + W 2 (s - x))

y el estado del sistema antes del primer paso es s=5, por lo que para realizar la optimización en este paso rellenaremos la tabla.

s	incógnita	sexo	p i (x)	W 2 (sexo)	p i (x)+W 2 (s-x)	Wi(s)
				19,26	19,26	19,26
		3,22	15,93	19,15
		3,57	10,97	14,54
		4,12	7,64	11,76
			4,27	8,27
		4,85		4,85

Se puede ver que el valor ganador más alto es 19,26. En este caso, el control óptimo en el primer paso es x 1 (s 1)=0 (s 1 =5), en el segundo paso x 2 (s 2) =1 (s 2 =s 1 -x 1 =5 ) y en el tercer paso x 3 (s 3) =4 (s 3 =s 2 -x 2 =4).

Esto significa que (0, 1, 4) es el plan óptimo para distribuir las inversiones entre empresas.

Así, para obtener el mayor beneficio total por valor de 19,26 mil. unidades, es necesario invertir 1 mil den. unidades a la segunda empresa y 4 mil den. unidades a una tercera empresa.

Lista de fuentes utilizadas

1. Bellman R., Programación dinámica, trad. De inglés, M., 1960.

2. Boltyansky V.G., Métodos matemáticos de control óptimo, M., 1966

PROGRAMACIÓN DINÁMICA, una sección de control óptimo dedicada a la teoría y métodos de resolución de problemas de varios pasos. En los problemas de control óptimo, entre los posibles controles, se busca aquel que alcanza el valor extremo (menor o mayor) de la llamada función objetivo, alguna característica numérica del proceso. En programación dinámica, varios pasos significan una estructura de proceso de múltiples etapas o el hecho de que el control se divide en varias etapas (pasos) sucesivas, correspondientes, por regla general, a diferentes momentos en el tiempo. A veces, la naturaleza de varios pasos surge de la esencia del proceso, pero también puede introducirse artificialmente para garantizar la posibilidad de utilizar métodos de programación dinámica. La programación en programación dinámica se refiere a la toma de decisiones (planificación), y la palabra "dinámica" indica el papel esencial del tiempo y el orden de las operaciones. Los métodos de programación dinámica son una parte integral de los métodos utilizados en la investigación de operaciones y se utilizan en problemas de planificación óptima (por ejemplo, en problemas de asignación óptima de recursos, en teoría de gestión de inventarios, en problemas de reemplazo de equipos) y en la resolución de muchos problemas técnicos (por ejemplo). ej., en problemas de control de procesos químicos secuenciales, en problemas de tendido óptimo de carreteras).

Dejemos que el proceso de gestión de algún sistema X conste de m pasos (etapas); en el i-ésimo paso, el control y i transfiere el sistema del estado x i-1, en el que se encontraba después del (i - 1) -ésimo paso, a un nuevo estado x i. En este caso, se da la función f i (x, y), y el nuevo estado está determinado a partir de esta función por los valores x i-1, y i de modo que x i = f i (x i-1, y i), i = 1, 2,..., metro. Así, los controles y 1, y 2, ..., y m transfieren el sistema desde el estado inicial x 0 ∈ X 0 al estado final x m ∈ X m, donde X 0 y X m son conjuntos de estados iniciales y finales permisibles de el sistema X.

Una de las posibles formulaciones de problemas de programación dinámica es la siguiente. Dado el estado inicial x 0, es necesario seleccionar los controles y 1, y 2, ..., y m de tal manera que el sistema X entre en un estado final admisible y al mismo tiempo la función objetivo dada F(x 0, y 1, x 1, .., y m, x m) alcanzó el valor máximo F*, es decir.

donde el máximo se toma sobre todos los controles y 1, ..., y m, para los cuales x m ∈ X m.

En programación dinámica, normalmente se supone que la función objetivo es aditiva. En el ejemplo considerado, esto significa que

Además, en la programación dinámica se supone que no hay efectos secundarios en el problema: las decisiones (controles) tomadas en el paso i afectan sólo el estado x i del sistema en el momento i. Las dos condiciones restrictivas mencionadas pueden atenuarse, pero sólo a expensas de una importante complicación del método.

La programación dinámica se basa en el principio de optimización formulado por R. Bellman. Dejemos que se seleccionen algunos controles y 1, y 2, ..., y k y, por lo tanto, se establezca una trayectoria x 0, x 1, ..., x k y se requiere para completar el proceso, es decir, seleccione y k+1, . .., y m (y por tanto x k+1 , ..., x m).

Si la parte final del proceso no es óptima en términos de lograr la máxima función

entonces todo el proceso no será óptimo. Utilizando el principio de optimización de Bellman, podemos obtener la relación funcional básica de la programación dinámica, que es la siguiente. Sea ω m (x) = 0,

k = 1, 2, ..., m, donde se toma el máximo sobre todos los controles y permitidos en el paso k. La relación que determina la dependencia de ω k-1 de ω k se llama ecuación de Bellman. El significado de estas funciones es bastante claro: si el sistema en el paso k-1 está en el estado x, entonces ω k-1 (x) es el valor máximo posible de la función F k. Simultáneamente con la construcción de las funciones ω k-1 (x), en cada paso se encuentran controles óptimos condicionales y k (x), es decir, los valores del control óptimo bajo todos los supuestos posibles sobre el estado x del sistema en paso k-1. Los controles óptimos finales se encuentran calculando secuencialmente las cantidades ω 0 (x 0) = F*, y 1, x 1, y 2, ..., y m, x m.

Con la ayuda de la programación dinámica, no se resuelve ningún problema específico para un determinado x 0, pero todos los problemas similares del mismo tipo se resuelven a la vez para cualquier estado inicial. La implementación numérica de la programación dinámica es bastante compleja, ya que requiere memorizar una gran cantidad de información, por lo que es recomendable utilizar la programación dinámica en los casos en que sea necesario resolver repetidamente problemas típicos (por ejemplo, determinar el modo de vuelo óptimo de una aeronave). bajo condiciones climáticas cambiantes). Normalmente, el problema de programación dinámica se formula para procesos discretos, pero en algunos casos la programación dinámica también se utiliza para resolver problemas dinámicos con parámetros continuos.

La programación dinámica proporcionó un nuevo enfoque a muchos problemas del cálculo de variaciones. Una sección importante de la programación dinámica consiste en problemas de programación dinámica estocástica, es decir, problemas en los que el estado del sistema y la función objetivo están influenciados por factores aleatorios.

Una justificación rigurosa de la programación dinámica se desprende de los resultados de L. S. Pontryagin y sus estudiantes sobre la teoría matemática de los procesos controlados.

Iluminado.: Bellman R. Programación dinámica. M., 1960; Teoría matemática de procesos óptimos. M., 1961; Howard R. A. Programación dinámica y procesos de Markov. M., 1964; Hedley J. Programación dinámica y no lineal. M., 1967; Hedley J., Whitin T. Análisis de sistemas de gestión de inventarios. M., 1969.

La programación dinámica (también conocida como “planificación dinámica”) es un método especial para optimizar decisiones, específicamente adaptado a las llamadas operaciones de “varios pasos” (o “varias etapas”).

Imaginemos una operación O, descompuesta en una serie de “pasos” o “etapas” sucesivos; por ejemplo, la actividad de una industria durante varios años económicos; o un grupo de aviones superando varias zonas de defensa aérea; o una secuencia de pruebas utilizadas en el control de equipos. Algunas operaciones (como las anteriores) se dividen en pasos de forma natural; en algunos, la división debe introducirse artificialmente; por ejemplo, el proceso de apuntar un misil a un objetivo se puede dividir en etapas, cada una de las cuales lleva algún tiempo.

Entonces, considere la operación O, que consta de pasos (etapas). Dejemos que la efectividad de la operación se caracterice por algún indicador W, que por brevedad llamaremos "ganancia" en este capítulo. Supongamos que el pago W de toda la operación es la suma de los pagos en los pasos individuales:

¿Dónde está el pago en el i-ésimo paso?

Si W tiene tal propiedad, entonces se llama criterio aditivo.

La operación O en cuestión es un proceso controlado, es decir, podemos elegir algunos parámetros que influyen en su progreso y resultado, y en cada paso seleccionamos alguna solución de la que depende la ganancia en este paso y las ganancias de la operación en su conjunto. Llamaremos a esta solución "control de pasos". El conjunto de todos los controles de paso representa el control de la operación en su conjunto. Designémoslo con la letra y los controles de paso con las letras:

Hay que tener en cuenta que en el caso general no se trata de números, sino quizás de vectores, funciones, etc.

Se requiere encontrar un control tal que la ganancia W sea máxima:

El control bajo el cual se logra este máximo se denominará control óptimo. Consta de un conjunto de controles de pasos óptimos:

Denotaremos la ganancia máxima que se consigue con este control:

La fórmula (12.5) dice así: el valor de W es el máximo de todos bajo diferentes controles (el máximo se toma sobre todos los controles posibles bajo condiciones dadas). A veces esto último se especifica en la fórmula y se escribe:

Veamos varios ejemplos de operaciones de varios pasos y para cada uno de ellos explicaremos qué se entiende por “control” y qué es la “ganancia” (indicador de desempeño)

1. Las actividades de un grupo de empresas industriales se planifican para el período de ejercicios económicos (año). Al comienzo del período, se asignaron algunos fondos para el desarrollo del grupo, que de alguna manera debían distribuirse entre las empresas. Durante el funcionamiento de una empresa, los fondos invertidos en ella se gastan (deprecian) parcialmente y se ahorran parcialmente y pueden redistribuirse nuevamente. Cada empresa genera ingresos al año, dependiendo de cuánto dinero se invierte en ella. Al comienzo de cada año comercial, los fondos disponibles se redistribuyen entre las empresas. Se plantea la pregunta: ¿cuánto dinero debería asignarse a cada empresa al comienzo de cada año para que los ingresos totales a lo largo de los años sean máximos?

El pago W (ingreso total) es la suma de los ingresos en los pasos individuales (años):

Esto significa que tiene la propiedad de aditividad.

La gestión de un paso consiste en que a principios de año se asignan algunos fondos a las empresas (el primer índice es el número de paso, el segundo es el número de empresa). Por tanto, el control por pasos es un vector con k componentes:

Por supuesto, los valores de la fórmula (12.6) dependen de la cantidad de fondos invertidos en la empresa.

El control de toda la operación consta de un conjunto de todos los controles de paso:

Es necesario encontrar dicha distribución de fondos por empresa y por año (control óptimo en el que el valor de W se vuelve máximo).

En este ejemplo, los controles de pasos eran vectores; en ejemplos posteriores serán más simples y se expresarán simplemente como números.

2. Un cohete espacial consta de etapas, y el proceso de puesta en órbita consta de etapas, al final de cada una de las cuales se reinicia la siguiente etapa. A todas las etapas (sin tener en cuenta el peso "útil" de la cabina) se les asigna un peso total determinado:

¿Dónde está el peso del paso?

Como resultado de la etapa (combustión y desechado de la etapa), el cohete recibe un incremento de velocidad A, dependiendo del peso de esta etapa y del peso total de todas las restantes más el peso de la cabina. La pregunta es, ¿cómo se debe distribuir el peso G entre las etapas para que la velocidad del cohete V cuando se ponga en órbita sea máxima?

En este caso, el indicador de eficiencia (ganancia) será

donde A es la ganancia (aumento de velocidad) en el paso.

La gestión es un conjunto de pesos de todas las etapas.

El control óptimo será la distribución de pesos entre los pasos en los que la velocidad V sea máxima. En este ejemplo, el control de pasos es un número único, es decir, el peso de un paso determinado.

3. El propietario del coche lo utiliza desde hace años. Al comienzo de cada año, puede tomar una de tres decisiones:

1) vender el coche y sustituirlo por uno nuevo;

2) repararlo y continuar con su funcionamiento;

3). continuar funcionando sin reparación.

Control de pasos: elegir una de estas tres soluciones. No se expresan directamente en números, pero puede asignar el valor numérico 1 al primero, 2 al segundo y 3 al tercero. Qué decisiones deben tomarse por año (es decir, cómo alternar los controles 1, 2, 3) ¿Para que los costos totales de operación, reparación y adquisición de autos nuevos fueran mínimos?

El indicador de eficiencia (en este caso no es “ganar”, sino “perder”, pero eso no importa) es igual a

(12.10)

¿Dónde están los gastos en el i-ésimo año? El valor de W debe reducirse al mínimo.

lo que significa: operar el auto sin reparación durante los primeros dos años, repararlo durante los siguientes tres años, venderlo al inicio del sexto año, comprar uno nuevo, luego operarlo nuevamente sin reparación, etc. Cualquier control es un vector (un conjunto de números):

donde cada uno de los números tiene uno de tres valores: 1, 2 o 3. Es necesario seleccionar un conjunto de números (12.11) para los cuales el valor (12.10) sea mínimo.

4. Se está colocando un tramo de vía férrea entre los puntos A y B (Fig. 12.1).

El terreno es accidentado e incluye áreas boscosas, colinas, pantanos y un río sobre el cual se debe construir un puente. Se requiere construir el camino desde B de tal manera que los costos totales de construcción del tramo sean mínimos.

En este problema, a diferencia de los tres anteriores, no existe una división natural en pasos: hay que introducirla artificialmente, para lo cual, por ejemplo, se puede dividir el segmento AB en partes, trazar rectas perpendiculares a AB a través de los puntos de división. y cuente la transición de una de esas líneas rectas a otra. Si los acercas lo suficiente entre sí, en cada paso podrás considerar que la sección del camino es recta. El control de paso en el i-ésimo paso es el ángulo que forma la sección del camino con la línea recta AB. El control de toda la operación consta de un conjunto de controles por pasos:

Es necesario elegir un control (óptimo) en el que los costos totales para la construcción de todas las secciones sean mínimos:

(12.12)

Hasta ahora hemos visto algunos ejemplos de problemas de investigación de operaciones de varios pasos. Ahora hablemos de cómo se puede resolver este tipo de problema.

Cualquier problema de varios pasos se puede resolver de diferentes maneras: buscar todos los elementos de la solución en todos los pasos a la vez o crear un control óptimo paso a paso, optimizando solo un paso en cada etapa del cálculo. Normalmente, el segundo método de optimización resulta más sencillo que el primero, especialmente cuando se trata de un gran número de pasos.

Esta idea de optimización gradual, paso a paso, subyace al método de programación dinámica. Optimizar un paso, por regla general, es más sencillo que optimizar todo el proceso: resulta que es mejor resolver un problema relativamente simple muchas veces que uno complejo una vez.

A primera vista, la idea puede parecer bastante trivial.

De hecho, lo que parecería más sencillo: si resulta complicado optimizar la operación en su conjunto, dividirla en varios pasos. Cada uno de estos pasos será una pequeña operación separada, que no es difícil de optimizar. Es necesario seleccionar dicho control en este paso para que la efectividad de este paso sea máxima. ¿No es así?

¡No, para nada así! El principio de programación dinámica no implica en absoluto que cada paso se optimice por separado, independientemente de los demás. Por el contrario, el control de pasos debe elegirse con previsión, teniendo en cuenta todas sus consecuencias en el futuro. ¿Cuál es el punto si elegimos en este paso un control que maximiza la eficiencia de este paso, si este paso nos priva de la oportunidad de ganar bien en los pasos siguientes?

Supongamos, por ejemplo, planificar el trabajo de un grupo de empresas industriales, algunas de las cuales se dedican a la producción de bienes de consumo y el resto a producir máquinas para ellos. El objetivo de la operación es obtener el máximo volumen de producción de bienes de consumo a lo largo de los años. Digamos que las inversiones de capital están previstas para el primer año. Teniendo en cuenta los estrechos intereses de este paso (año), tendríamos que invertir todos los fondos disponibles en la producción de bienes de consumo. Pero, ¿será correcta tal decisión desde el punto de vista de la eficacia de la operación en su conjunto? Obviamente no. Esta decisión es un desperdicio y una visión miope. De cara al futuro, es necesario destinar una parte de los fondos a la producción de máquinas. Por supuesto, esto reducirá el volumen de producción durante el primer año, pero se crearán las condiciones para su aumento en los años siguientes.

Otro ejemplo. Supongamos que en la tarea 4 (colocar una vía férrea de A a B) nos seduce la idea de apresurarnos inmediatamente en la dirección más fácil (más barata). ¿De qué sirve ahorrar en el primer paso si en el futuro nos llevará (literal o figurativamente) a un “pantano”?

Esto significa que al planificar una operación de varios pasos, es necesario elegir el control en cada paso, teniendo en cuenta todas sus consecuencias futuras en los pasos venideros. El control en un paso se elige no para que las ganancias en este paso en particular sean máximas, sino para que la suma de las ganancias en todos los pasos restantes hasta el final más este sea máxima.

Sin embargo, existe una excepción a esta regla. Entre todos los pasos, hay uno que se puede planificar de forma sencilla, sin tener en cuenta el futuro. ¿Qué paso es este? ¡Obviamente el último! Este paso, el único de todos, puede planificarse de manera que, como tal, aporte el mayor beneficio.

Por lo tanto, el proceso de programación dinámica generalmente se desarrolla de principio a fin: el último paso se planifica primero. ¿Cómo podemos planificarlo si no sabemos cómo terminó el penúltimo? Es decir, ¿desconocemos las condiciones bajo las cuales iniciamos el último paso?

Aquí es donde comienza lo más importante. Al planificar el último paso, es necesario hacer diferentes suposiciones sobre cómo terminó el penúltimo paso y, para cada una de estas suposiciones, encontrar el control óptimo condicional en el paso ("condicional" porque se elige en función de la condición de que finalice el penúltimo paso). de tal o cual manera, etcétera).

Supongamos que hemos hecho esto y que para cada uno de los posibles resultados del penúltimo paso conocemos el control óptimo condicional y el pago óptimo condicional correspondiente en el paso. ¡Excelente! Ahora podemos optimizar el control en el penúltimo paso. Nuevamente, hagamos todas las suposiciones posibles sobre cómo terminó el anterior y no encontremos una ganancia condicionalmente óptima, sino simplemente una ganancia óptima.

De hecho, háganos saber en qué estado se encontraba el sistema controlado (objeto de control S) al comienzo del primer paso. Luego podemos elegir el control óptimo en el primer paso. Una vez aplicado, cambiamos el estado del sistema a una nueva S y en este estado llegamos al segundo paso. Entonces también conocemos el control óptimo condicional que, al final del segundo paso, transfiere el sistema al estado, etc. En cuanto a la ganancia óptima W para toda la operación, ya la sabemos: después de todo, estaba en el base de su máximo que elegimos el control en el primer paso.

Por lo tanto, en el proceso de optimización del control utilizando el método de programación dinámica, el proceso de varios pasos se "recorre" dos veces: la primera vez, desde el final hasta el principio, como resultado de lo cual se obtienen controles óptimos condicionales y ganancias óptimas condicionales para el resto " se encuentran la cola” del proceso; la segunda vez, de principio a fin, cuando todo lo que tenemos que hacer es "leer" las recomendaciones ya preparadas y encontrar el control óptimo incondicional que consta de controles escalonados óptimos.

La primera etapa, la optimización condicional, es incomparablemente más difícil y más larga que la segunda. La segunda etapa casi no requiere cálculos adicionales.

El autor no se enorgullece de tener la esperanza de que, a partir de tal descripción del método de programación dinámica, un lector que no lo haya conocido antes comprenda realmente su idea. La verdadera comprensión surge al considerar ejemplos específicos, a los que pasaremos más adelante.

Entre los problemas resueltos mediante programación matemática, se puede distinguir una clase separada de problemas que requieren optimización de procesos de múltiples pasos (varias etapas). Estos problemas se distinguen por la posibilidad de dividir la solución en varias etapas interconectadas. Para resolver este tipo de problemas se utiliza la programación dinámica o, como también se la llama, programación de múltiples etapas. Sus métodos están optimizados para encontrar la solución óptima a problemas de varios pasos que se pueden dividir en varias etapas, pasos, etc.

Origen del término

El uso de la palabra "dinámico" en el nombre originalmente implicaba que la división en subtareas se produciría principalmente en el tiempo. Cuando se utilizan métodos dinámicos para resolver problemas productivos, económicos y de otro tipo en los que aparece el factor tiempo, no es difícil dividirlo en etapas separadas. Pero también es posible utilizar técnicas de programación dinámica en tareas donde las etapas individuales no están relacionadas en el tiempo. En un problema de varios pasos, siempre puede seleccionar un parámetro o propiedad que pueda usarse para dividirlo en pasos separados.

Algoritmo (método) para resolver problemas de varias etapas.

El algoritmo o método de programación dinámica se basa en el principio de optimización secuencial de un problema, cuando la solución a un problema general se divide en varias soluciones a subproblemas individuales y luego se combina en una única solución. Muy a menudo, los subproblemas individuales resultan ser los mismos y una solución general reduce significativamente el tiempo de cálculo.

Una característica del método es la autonomía para resolver el problema en cada etapa individual, es decir, independientemente de cómo se optimizó y resolvió el proceso en la etapa anterior, en el cálculo actual solo se utilizan los parámetros del proceso que lo caracterizan en este momento. Por ejemplo, un conductor que circula por una carretera toma una decisión sobre el giro actual independientemente de cómo y durante cuánto tiempo condujo antes.

Método desde arriba y método desde abajo

A pesar de que al calcular en una etapa separada de la resolución de un problema, se utilizan los parámetros del proceso en el momento actual, el resultado de la optimización en la etapa anterior afecta los cálculos de las etapas posteriores para lograr el mejor resultado en su conjunto. La programación dinámica llama a este principio de solución el método de optimización, que determina que la estrategia óptima para resolver un problema, independientemente de las decisiones y condiciones iniciales, debe ser seguida por decisiones posteriores en todas las etapas para formar una estrategia óptima en relación con el estado inicial. Como podemos ver, el proceso de resolución de un problema es una optimización continua del resultado en cada etapa individual desde la primera hasta la última. Este método se denomina método de programación de arriba hacia abajo. La figura muestra esquemáticamente el algoritmo de solución de arriba hacia abajo. Pero hay una clase de problemas de varios pasos en los que ya se conoce el efecto máximo en la última etapa, por ejemplo, ya llegamos del punto A al punto B y ahora queremos saber si condujimos correctamente en cada etapa anterior. etapa o si algo se podría haber hecho de manera más óptima. Surge una secuencia recursiva de etapas, es decir, vamos, por así decirlo, "desde la dirección opuesta". Este método de solución se denomina "método de programación ascendente".

Aplicación práctica

La programación dinámica se puede utilizar en cualquier campo de actividad donde existan procesos que se puedan dividir en un número de pequeñas etapas idénticas según algún parámetro (tiempo, cantidad, temperatura, etc.). Los métodos de solución dinámica se utilizan más ampliamente en la teoría del control y en el desarrollo de sistemas informáticos.

Encontrar el camino óptimo

Con la optimización dinámica, es posible resolver una amplia clase de problemas de búsqueda u optimización del camino más corto y otros problemas en los que el método "clásico" de enumerar posibles opciones de solución conduce a un aumento en el tiempo de cálculo y, a veces, es completamente inaceptable. El problema clásico de programación dinámica es el problema de la mochila: dado un cierto número de objetos con una determinada masa y costo, es necesario seleccionar un conjunto de objetos con el máximo costo y masa que no exceda el volumen de la mochila. La búsqueda clásica de todas las opciones para encontrar una solución óptima llevará un tiempo considerable, pero con la ayuda de métodos dinámicos el problema se resuelve en un plazo aceptable. Los problemas de encontrar el camino más corto para la logística de transporte son básicos y los métodos de solución dinámica son óptimos para resolverlos. El ejemplo más sencillo de esta tarea es construir la ruta más corta utilizando un navegador GPS para automóvil.

Producción

La programación dinámica se usa ampliamente para resolver una variedad de problemas de producción, como la gestión de inventarios para mantener la cantidad requerida de componentes en un momento dado, la programación del proceso de producción, la rutina y revisión de los equipos, la carga de trabajo uniforme del personal y la distribución más eficiente. de fondos de inversión, etc. Para resolver problemas de producción utilizando métodos de programación dinámica, se han desarrollado paquetes de software especiales que se integran en sistemas populares de gestión empresarial, como SAP.

Campo científico

Los métodos de programación dinámica se utilizan ampliamente en diversas investigaciones científicas. Por ejemplo, se utilizan con éxito en algoritmos de reconocimiento de voz e imágenes, al procesar grandes cantidades de datos en sociología y

4.1. Principio de optimización

Considere el sistema

y funcionalidad

(4.2)

que es necesario minimizar. El extremo derecho de las coordenadas de fase está libre.

Junto a este problema variacional, consideramos uno auxiliar, cuando el proceso se considera en el intervalo
y la funcionalidad se minimiza

. (4.3)

Deja que el mínimo se encuentre primero. (4.2) y el control óptimo correspondiente (Fig. 14a):

y luego - mínimo (4.3) y control óptimo (Fig. 14b):

En este último caso, se supone que en este momento el proceso comienza desde el estado
, logrado por el momento del tiempo al optimizar el proceso en el intervalo
.

En términos generales, la gestión
Y
difieren en intervalo y valores. El principio de optimización establece que los controles óptimos
Y
en la parte general del intervalo
coinciden, independientemente de los antecedentes del proceso y están completamente determinados por el estado
en este momento
.

En el caso de un extremo derecho libre, se demuestra el principio de optimización. De hecho, supongamos que en el sitio
gestión
Y
no coinciden y

(4.6)

Arroz. 14 A Fig.14 b

Luego para el primer problema introducimos el control.

(4.7)

y calcular el funcional

Al conducir (4.7) funcional (4.2) toma un valor menor que con (4.4). Pero controlar es óptimo. Por tanto, la suposición (4.6) es incorrecta.

una suposición

contradice lo que
- gestión que minimice
(4.3).

Así, queda que

,

y si solo hay un control óptimo, entonces

Brevemente, el principio de optimización se puede formular de la siguiente manera: la última sección de la trayectoria óptima es óptima independientemente de la historia del proceso.

4.2. Ecuación básica del método de programación dinámica.

Apliquemos el principio de optimización a la solución del problema variacional (4.1), (4.2). Para hacer esto, primero considere la funcionalidad. (4.3). Denotemos su valor más pequeño en las conexiones (4.1):

. (4.8)

Si
- control óptimo, entonces

.

Control óptimo
depende del estado inicial
en este momento
. Por eso, es una función de Y :
, y desde el control y sus variaciones funcionan
no depende. Está completamente determinado por los valores.
.

Intervalo
dividir en dos intervalos
Y
y escribimos la expresión (4.8) de la forma:

.

Según el principio de optimización, la última sección también es óptima:

(4.9)

Denotemos:

, (4.10)

Dónde
- incremento del vector de coordenadas de fase a lo largo del tiempo
. Se determina según las ecuaciones de movimiento (4.1). Sustituyendo
de (4.10) a la igualdad (4.9), obtenemos:

.

Aunque la función
Depende sólo de las coordenadas de fase y del tiempo, no se puede quitar del signo.
. Valor de incremento
a tiempo
depende del control de intervalos
. Pero
no depende del control en el intervalo
y se puede incluir bajo el signo
. vamos a presentar
bajo el signo de mínimo y dividir por
:

.

considerando que

;

,

obtenemos la ecuación básica del método de programación dinámica:

(4.11)

Esta relación consta de dos declaraciones:

Si
- control que minimiza la expresión
, entonces la ecuación básica del método de programación dinámica

(4.12)

Aquí
depende del control por definición, la función
no depende de él. Sin embargo, la derivada depende de la gestión. Esto se puede verificar si se representa en la forma

Y sustituir según sistema (4.1):

.(4.13)

Sustituyendo (4.13) en (4.12) obtenemos la ecuación de R. Bellman:

. (4.14)

Esta es una ecuación diferencial parcial con respecto a
, que después de la sustitución
se vuelve no lineal. Según la definición (4.8) en
se debe cumplir la condición final

.

En el caso de un intervalo infinito en
el proceso debe ser asintóticamente estable, es decir
.

En el caso de que se considere el funcional Boltz

(4.15)

La ecuación (4.12) sigue siendo válida, la función v en este momento
debe satisfacer la condición

. (4.16)

4.3. Dos problemas de control óptimo

En la teoría del control óptimo se distinguen problemas de dos tipos: control de programa y síntesis. En el primer problema, control óptimo construido en función del tiempo para condiciones iniciales y finales específicas, si se especifican. Adicción
considerado como un programa.

En el segundo problema, control óptimo. está construido para cada momento en el tiempo en función del vector de coordenadas de fase aquellos. en la forma

. (4.17)

La construcción de tal dependencia es el objetivo del problema de síntesis. La importancia de la segunda tarea es que la dependencia
da la ecuación de retroalimentación o controlador óptimo que cierra el sistema. Se utiliza para un control óptimo del proceso transitorio.

El control del programa y el control de retroalimentación funcionan de maneras técnicamente diferentes. La primera puede realizarse mediante un mecanismo de reloj software, según una ley estricta, en función del tiempo. . Este control no reacciona de ninguna manera ante posibles desviaciones del estado del objeto respecto del estado ideal y deseable. El control de retroalimentación se lleva a cabo mediante un regulador que, basándose en los resultados de medir el estado real de las coordenadas de fase, genera una señal según la cual se desvía el elemento de control.

Ambas tareas están interconectadas. La solución a uno se puede expresar a través del otro. Sin embargo, observamos que el principio de máximo generalmente conduce a la representación del control en forma de programa, y ​​el método de programación dinámica, en forma de síntesis.

El problema de sintetizar el control óptimo de los procesos descritos por un sistema lineal de ecuaciones diferenciales minimizando al mismo tiempo los funcionales cuadráticos integrales ha recibido un desarrollo significativo. Se llama problema de diseño analítico de controladores óptimos (ACOR), o problema de A.M.

4.4. El problema del diseño analítico de controladores óptimos.

Supongamos que las ecuaciones del movimiento perturbado del sistema tienen la forma

(4.18)

matrices
, dimensiones
Y
, en consecuencia, tienen funciones conocidas como sus elementos
.

También se supone que el estado del sistema (4.18) en cada momento conocido.

El funcional cuadrático de Boltz se considera un criterio de optimización.

Dónde
- matrices definidas no negativas simétricas,
- matriz definida positiva; *) - índice de transposición.

Se requiere encontrar el control óptimo (funcional minimizador 4.19), que es función del estado actual.
.

Para resolver este problema, puede utilizar el principio máximo, pero el camino más corto es el método de programación dinámica.

Según este método, necesitas encontrar la función.
, satisfaciendo la ecuación

. (4.20)

En el caso general, este es un problema difícil, pero para sistemas lineales con un criterio de optimización cuadrática la función
se puede buscar en forma de alguna forma cuadrática.

(4.21)

Dónde
- existe alguna forma cuadrática, aún desconocida, que, en virtud de (4.16), satisface la condición final

. (4.22)

Por tanto, para sistemas lineales el problema se reduce a encontrar la función
. Derivando (4.21) teniendo en cuenta (4.18) obtenemos

Minimizando (4.23) por
, obtenemos

(4.24)

Porque
, entonces el control (4.24) en realidad proporciona un mínimo a la expresión
.

Sustituyendo (4.24) en (4.23), obtenemos

La forma cuadrática (4.25) es igual a cero para cualquier
sólo en el caso de que la matriz que lo forma sea igual a cero. Así, obtenemos la ecuación para determinar la matriz.

(2.26)

con la condición de frontera (4.22).

Integrando la ecuación (4.26) en la dirección opuesta, obtenemos
, y por tanto los parámetros de control óptimos (4.24). Es fácil demostrar que la matriz
- matriz simétrica. Para ello basta con transponer la ecuación (4.26). Entonces

de donde, teniendo en cuenta la simetría de las matrices resulta que
.

Nota 1. En el caso en que el sistema (4.18) sea estacionario (matrices A Y B– matrices numéricas), matrices - matrices numéricas,
(Se considera estado estacionario). Matriz también es numérico y satisface la ecuación algebraica

Nota 2. De la expresión (4.24) se deduce que para implementar un control óptimo se requiere información completa y precisa sobre el estado del proceso controlado.
. En el caso de que no se pueda obtener esta información, para implementar un control óptimo se utilizan estimaciones estatales obtenidas sobre la base de información incompleta disponible.

4.5. Síntesis del control local óptimo.

Al diseñar sistemas de control, a menudo es necesario que el comportamiento del sistema sea óptimo en algún sentido en un momento dado.

Consideremos un proceso controlado continuo descrito por un sistema de ecuaciones diferenciales (4.18).

Sea una funcional (función) dada
paramétricamente dependiente del tiempo y definido en un conjunto de funciones
Y
.

Necesitamos encontrar la ecuación.
, minimizando
, Dónde - momento actual en el tiempo. Este control se denomina localmente óptimo.

Como criterio de optimización, consideramos el funcional.

matriz cumplir los mismos requisitos que en el punto 4.4.

Es fácil demostrar que la ecuación localmente óptima
necesariamente satisface la condición

. (4.28)

Utilicemos esta condición.

Luego, derivando (4.27) en virtud de (4.18), encontramos una expresión para determinar la derivada

de la condición
Encontremos el control local óptimo.

El control encontrado en realidad entrega la derivada.
, porque

.

De la expresión (4.30) se deduce que el control local óptimo está completamente determinado por las matrices
, y para implementarlo se requiere información completa sobre el estado del proceso.
. Dadas varias matrices de funciones de peso.
, es posible garantizar determinadas propiedades del proceso controlado, en particular las propiedades de estabilidad o estabilidad asintótica.

Requerimos, por ejemplo, que el control local óptimo satisfaga la condición

. (4.31)

Luego, sustituyendo (4.30) en (4.29), de (4.31) encontramos

(4.32)

De la condición (4.32) se deduce que se cumplirá si la matriz
se determinará a partir de la condición

Consideremos ahora el movimiento controlado en el segmento
, Dónde - algún punto fijo en el tiempo. También requerimos que en el momento función matricial
cumplió la condición final

(4.34)

Luego, de una comparación de las fórmulas (4.24), (4.26), (4.22) y (4.30), (4.33), (4.34) se deduce que el control local óptimo (4.30) según el criterio (4.27) con la matriz
, determinado a partir de la ecuación (4.33) con la condición (4.34) coincide con el control (4.24), óptimo según el criterio cuadrático (4.19) en el intervalo
.

5. Control óptimo de sistemas estocásticos en condiciones de incertidumbre.

5.1. Características de las señales aleatorias.

El manual utiliza procesos y secuencias estocásticas (aleatorias) como modelos matemáticos de perturbaciones y errores de medición.

Proceso aleatorio
es una función cuyo valor en un momento fijo es una variable aleatoria, es decir un proceso aleatorio puede considerarse como una variable aleatoria dependiendo del parámetro . En el caso de que el parámetro cambia discretamente, el proceso aleatorio se llama secuencia aleatoria.

A través de
denotaremos la realización del proceso aleatorio
.

Cabe señalar que muchas características estadísticas de procesos y secuencias aleatorias coinciden.

Como es sabido, la característica más completa de un proceso aleatorio es - ley de distribución dimensional

o -densidad de distribución dimensional

Aquí el símbolo indica la probabilidad del evento encerrado entre paréntesis. Significado puede ser cualquier cosa desde yo hasta
. Para un proceso aleatorio arbitrario es imposible disponer de dicha información. Sin embargo, existe una clase de procesos aleatorios (secuencias), llamados procesos de Markov, cuyas características estadísticas están completamente determinadas por una ley de distribución bidimensional o densidad de distribución bidimensional.

A menudo, especialmente en problemas aplicados, se utilizan valores iniciales para describir estadísticamente procesos aleatorios.
y central
momentos -ésimo orden. Aquí el símbolo
Se indica la operación de promediación (expectativa matemática). Los siguientes puntos juegan el papel más importante:

Expectativa matemática (valor medio)

; (5.3)

Varianza de un proceso aleatorio

Segundo momento inicial

Dónde
- proceso aleatorio centrado con expectativa matemática cero;

Desviación estándar

. (5.6)

De la definición
,
,
Y
de ello se deduce que estas cantidades caracterizan un proceso aleatorio sólo en una sección fija . Para caracterizar la conexión entre dos secciones diferentes de un proceso aleatorio, se utiliza una función de correlación;

. (5.7)

Si la expectativa matemática
El proceso aleatorio no depende del tiempo y la función de correlación es función de un argumento.
, entonces tal proceso se llama estacionario en sentido amplio.

Si la densidad de distribución tiene un carácter gaussiano, entonces dicho proceso se llama gaussiano.

.

El proceso gaussiano se determina completamente especificando la expectativa matemática
y función de correlación
.

Una característica importante de un proceso aleatorio estacionario en un sentido amplio es la densidad espectral
- densidad de distribución de dispersión (energía) sobre frecuencias.

Densidad espectral
y función de correlación
conectado por transformada de Fourier directa e inversa:

; (5.8)

. (5.9)

Un proceso (secuencia) puramente aleatorio es un proceso en el que las variables aleatorias
son mutuamente independientes para cualquier valor de los argumentos. Un proceso de este tipo se caracteriza completamente por una función de distribución unidimensional. Un proceso estacionario puramente aleatorio se llama ruido blanco si la función de correlación tiene la forma - funciones. La densidad espectral de tal proceso es constante en todas las frecuencias. Porque
, entonces es fácil ver que la varianza del ruido blanco es infinitamente grande. En realidad, estos procesos no existen en la naturaleza. Sin embargo, el ruido real puede ser sustituido por ruido blanco en su efecto sobre el sistema. Además, un proceso aleatorio real se puede representar como la señal de salida de algún sistema (filtro de conformación), cuya entrada es ruido blanco. Por tanto, el problema del análisis o síntesis estadístico de sistemas con características reales de influencias aleatorias se puede reducir al problema del análisis o síntesis estadístico cuando la señal de entrada es ruido blanco. Este tutorial generalmente utilizará ruido blanco y modelos de secuencia aleatoria pura.

Junto con los procesos aleatorios escalares, también se pueden considerar procesos aleatorios vectoriales:

donde cada componente
es un proceso aleatorio. Para caracterizar un proceso aleatorio vectorial, se introducen los siguientes vectores y matrices:

Expectativa :

; (5.11)

Matriz de dispersión
:

(5.12)

con elementos

; (5.13)

Matriz de covarianza
:

(5.14)

con elementos

; (5.15)

Matriz

con elementos

. (5.17)

Aquí
significa transposición.

Directamente desde la definición de la matriz.
Se puede observar que las varianzas de los componentes del proceso aleatorio se ubican en su diagonal.

matrices
,
Y
tener las siguientes propiedades:

; (5.18)

para todos Y (5.I9)

Para un proceso aleatorio vectorial estacionario
la matriz de densidades espectrales se introduce como la transformada de Fourier de la matriz de covarianza
, es decir.

. (5.21)

Matriz
tiene la siguiente propiedad:

(5.22)

5.2. Descripción matemática de sistemas lineales bajo perturbaciones aleatorias.

En general, la ecuación de un sistema dinámico controlado se puede escribir como:

Dónde - operador (o en un caso particular función) del sistema, es decir un conjunto de reglas mediante las cuales se transforma la condición inicial
, acciones de control
, influencias perturbadoras
a la salida del sistema
en este momento .

Si el parámetro cambia continuamente, entonces llamaremos a dicho sistema continuo; Si cambia discretamente, entonces el sistema se llama discreto.

Si el operador no depende de los parámetros Y , entonces dicho sistema se llama estacionario. Operador puede ser lineal o no lineal, homogéneo o no homogéneo y puede especificarse de diversas formas, por ejemplo, en forma de ecuaciones diferenciales e integrodiferenciales, utilizando funciones de transferencia y ecuaciones en diferencias.

En este tutorial, solo se considerarán sistemas lineales.

Consideremos sistemas descritos por ecuaciones diferenciales.

Denotemos por

-vector dimensional del estado del sistema; a través de
- -vector dimensional de acciones de control; a través de
- -vector dimensional de perturbaciones. Entonces la ecuación de movimiento de un sistema dinámico continuo lineal se puede escribir en la siguiente forma diferencial:

Aquí
,
,
- matrices dimensionales, respectivamente. Los elementos de estas matrices son funciones continuas. Si matrices
Y son constantes, entonces el sistema controlado se llama estacionario. Las ecuaciones (5.24) suelen denominarse ecuaciones de estado, ya que describen el cambio en las variables de estado del sistema a lo largo del tiempo.

A efectos de gestión es necesario conocer el estado del sistema en cada momento. Sin embargo, con la ayuda de medidores es posible obtener información, por regla general, solo sobre algunos procesos componentes o sus combinaciones. Además, las variables observadas (de salida) pueden contener errores de medición. En lo que sigue asumiremos que las ecuaciones de medición tienen la forma:

Dónde
-
-señal observada dimensional;
- matriz de dimensiones
, caracterizando el método de medición;
- error de medición. Si
(- matriz de identidad) y
, entonces dicen que la medición es completa y precisa.

En algunos casos, es conveniente representar la solución del sistema (5.24) en forma integral a través de la matriz fundamental de soluciones.
, que satisface la siguiente ecuación matricial:

(5.26)

En forma integral, la solución del sistema (5.24), de acuerdo con la fórmula de Cauchy, se puede representar de la siguiente forma:

(5.27)

En la expresión (5.27), el primer componente tiene en cuenta el libre movimiento provocado por la condición inicial , el segundo componente tiene en cuenta el movimiento forzado provocado por las acciones de control durante el intervalo de tiempo
, el tercer componente caracteriza el movimiento forzado causado por perturbaciones
en el intervalo
.

Respecto al sistema (5.24), (5.25), hacemos los siguientes supuestos:

(5.28)

De las relaciones (5.28) está claro que los procesos aleatorios
Y
Son procesos de tipo ruido blanco. matrices
y vector son considerados famosos. Se supone conocido en cada momento. y controlar las influencias.

Un tipo de sistemas dinámicos son los sistemas discretos, que se pueden dividir en dos tipos:

a) los propios sistemas discretos, como ordenadores digitales, máquinas automáticas de diversos tipos, etc.;

b) sistemas discretos que se obtienen como resultado del uso de sistemas continuos en momentos discretos en el tiempo, en particular, cuando se utilizan en el circuito de control de computadoras. El comportamiento de los sistemas discretos generalmente se describe mediante ecuaciones en diferencias, que son análogas a las ecuaciones diferenciales para sistemas continuos.

R Consideremos el comportamiento de un sistema continuo con control discreto, que se puede representar como una función vectorial constante por partes (Fig.15), es decir Las acciones de control se pueden escribir de la siguiente forma:

para (5.29)

Dónde - una secuencia de momentos en el tiempo, no necesariamente equidistantes entre sí.

Si estamos interesados ​​en el estado del sistema sólo en momentos discretos en el tiempo , entonces el sistema continuo (5.24) en estos momentos, usando la relación (5.27), se puede escribir de la siguiente forma:

(5.30)

Teniendo en cuenta (5.29), reescribimos la relación (5.30) como:

(5.31)

El tercer término de la relación (5.3I) puede considerarse como una secuencia aleatoria. En el caso de que el proceso aleatorio sea del tipo ruido blanco, entonces es válida la siguiente relación:

,

Dónde
- secuencia puramente aleatoria.

Introduciendo designaciones

(5.32)

escribimos el sistema de ecuaciones (5.31) en la forma:

Las matrices se denominan matrices de transición de estado, control y perturbación, respectivamente;
- tiempo discreto.

En consecuencia, la ecuación de medición se puede escribir como:

A veces el sistema (5.33) - (5.34) se escribe de la siguiente forma:

Respecto a los sistemas (5.33), (5.34), asumiremos que:

(5.37)

Ejemplo. Consideremos el movimiento de rotación de un cuerpo alrededor de uno de los ejes bajo la influencia de un momento perturbador.
. Las ecuaciones de movimiento son:

, (5.38)

Dónde - momento de inercia del cuerpo; - ángulo de rotación del cuerpo en algún sistema de coordenadas inercial. Introduciendo nuevas variables

(5.39)

obtenemos las ecuaciones de movimiento del objeto en forma normal:

(5.40)

Para este sistema de ecuaciones la matriz fundamental
consta de dos soluciones vectoriales de columna para el siguiente sistema de ecuaciones

con condiciones iniciales

De ello se deduce que la matriz
tiene la forma:

(5.41)

Se obtiene el mismo resultado si buscamos la matriz
en forma de serie:

Consideremos el comportamiento del sistema (5.40) en intervalos de tiempo regulares. en momentos , es decir.
.

Con base en las relaciones (5.3I) - (5.33), suponiendo que
constantemente en el paso discreto, obtenemos el siguiente sistema discreto equivalente:

(5.43)

(5.44)

En el futuro, necesitarás conseguir una dependencia.
no sólo de Y
, pero de y todo lo anterior
. Usando las relaciones (5.33), para varios se puede escribir:

Continuando con los cálculos correspondientes, podemos obtener la relación

, (5.45)

donde esta la matriz
se define de la siguiente manera:

y
en
.

Las relaciones resultantes (5.45), (5.46) se utilizarán en el análisis estadístico de sistemas discretos.

5.3. Ecuaciones de momento para sistemas lineales.

Veamos primero los sistemas continuos. Dejemos que las ecuaciones de movimiento tengan la forma;

. (5.47)

Sobre las influencias perturbadoras
y estado inicial asumiremos que satisfacen las condiciones (5.28).

Al obtener relaciones para la expectativa matemática del estado del sistema.
Promedimos la ecuación (5.47):

Teniendo en cuenta (5.28), obtenemos:

. (5.48)

Con base en (5.47), (5.48), la ecuación para el componente centrado
tiene la forma:

. (5.49)

Ahora encontremos la ecuación de la matriz de dispersión. Diferenciando por matriz
y dado que las matrices
Y
no al azar, obtenemos:

(5.50)

Para calcular la expectativa matemática.
Usamos la fórmula de Cauchy (5.27):

. (5.51)

Multiplicando la expresión (5.51) de la derecha por
, promediando teniendo en cuenta (5.28), obtenemos:

(5.52)

considerando que

, (5.53)

la ecuación (5.50) tomará la forma;

con condición inicial
.

Ahora describamos el comportamiento del sistema mediante la ecuación discreta

Supondremos que la condición inicial e influencias perturbadoras
satisfacer relaciones (5.37). Encontremos las ecuaciones para la expectativa matemática y la matriz de dispersión.

Promediando (5.55) y teniendo en cuenta (5.37), obtenemos:

Ecuación para el componente centrado.
tiene la forma:

Usando (5.57) y (5.37), encontramos la ecuación para la matriz de dispersión
:

(5.58)

Definamos la expectativa matemática.
, usando la relación (5.45) y las propiedades (5.37):

(5.59)

Asimismo

.

Por tanto, la ecuación para determinar la matriz es
tiene la forma:

5.4. El problema de filtrado óptimo y su solución por el método de Kalman.

Como se mostró anteriormente, para un control de retroalimentación óptimo es necesario tener información completa sobre el estado del sistema. Sin embargo, sólo se pueden medir algunas funciones estatales o combinaciones de ellas. Además, la señal observada contiene errores de medición. En tal situación, la tarea importante es obtener la mejor estimación del estado del sistema basándose en los resultados de la medición: el problema del filtrado óptimo.

Supongamos que el proceso dinámico se describe mediante un conjunto de ecuaciones diferenciales.

Dónde
--vector de estado dimensional,
--vector dimensional de influencias perturbadoras,
Y
matrices de dimensiones correspondientes.

Que sea mensurable
-vector dimensional de algunas combinaciones de funciones de estado (5.25)

Dónde
- error de medición.

En cuanto a las propiedades de los procesos aleatorios.
y estado inicial
asumirá que satisfacen las condiciones (5.28), es decir Supondremos que se trata de procesos aleatorios como el ruido blanco, no correlacionados entre sí y con el estado inicial del sistema.

Matemáticamente, el problema del filtrado óptimo se plantea como el problema de encontrar una estimación
estado del sistema (5.61)
basado en la información disponible
.

Kalman propuso buscar la ecuación del filtro en forma de un sistema lineal a cuya entrada se suministra la señal observada.
. Entonces las ecuaciones de movimiento de dicho sistema pueden describirse mediante un conjunto de ecuaciones

(5.63)

donde estan las matrices
Y
sujeto a determinación, es decir se especifica la estructura del filtro y los parámetros de la estructura y el estado inicial se determinan a partir de condiciones adicionales.

Porque
, entonces siempre habrá un error de estimación

.

Luego para determinar las matrices requeridas.
Y
Puedes utilizar la condición de estimación imparcial.

(5.64)

y la condición para su optimización

Dónde
es una matriz definida positiva simétrica.

Para utilizar las condiciones (5.64) y (5.65), encontramos una ecuación para el error de estimación. Restando (5.63) de (5.61) teniendo en cuenta (5.62), obtenemos

Si ahora ponemos eso

entonces la ecuación para el error de estimación es
tomará la forma:

con condición inicial

. (5.68)

De (5.67), (5.68) se deduce que la condición para la estimación insesgada (5.64) se cumplirá si ponemos

. (5.69)

Para verificar esto, basta con tomar la expectativa matemática de las expresiones (5.67), (5.68)

aquellos. obtuvo una ecuación lineal homogénea con condiciones iniciales cero, de la cual se sigue inmediatamente que
para cualquiera .

Queda por definir la matriz.
de la condición del criterio mínimo (5.65). Supongamos para simplificar los cálculos que
es una matriz identidad constante, entonces

Aquí
- matriz de correlación del error de estimación (matriz de los segundos momentos centrales de errores de estimación de los componentes del vector de estado del sistema). Denotémoslo por
, entonces el criterio de optimización es la suma de los elementos diagonales de esta matriz. De acuerdo con la condición de optimización local, buscaremos el valor óptimo de la matriz.
de la condición de derivada mínima A criterios de tiempo:

. (5.71)

Es fácil demostrar que minimizar la derivada del criterio proporciona un mínimo para el criterio mismo.

Escribamos la expresión.
, omitiendo el tiempo por simplicidad :

. (5.72)

Sustituyendo en (5.72) la expresión para de (5.67) y la expresión correspondiente para , obtenemos:

(5.73)

encontraremos
, para lo cual escribimos la ecuación de Cauchy para (5.67):

Dónde
- función de matriz de peso. Entonces

Usamos la propiedad de la función delta:

,

Si tiene un hueco en el punto
.

Porque

. (5.74)

Del mismo modo puedes encontrar
:

. (5.75)

Sustituyendo las expresiones resultantes por
y expresiones correspondientemente transpuestas para
en (5.73) obtenemos:

La siguiente identidad se puede verificar fácilmente abriendo los corchetes del lado derecho y usando la simetría de la matriz.
:

Teniendo en cuenta la identidad, reducimos la ecuación (5.76) a la forma:

En el lado derecho (5.78) del coeficiente
Sólo dependerá el último término, que es una matriz definida positiva. Obviamente, para minimizar el criterio (5.71) se debe elegir
en la siguiente forma:

En este caso, el último término de la ecuación (5.78) se vuelve cero y la ecuación toma la forma

con valor inicial
.

Entonces, podemos escribir la ecuación del filtro.

Las ecuaciones (5.79), (5.80), (5.81) son las ecuaciones del filtro de Kalman-Bucy.

El sistema de evaluación (filtro) se presenta esquemáticamente en la Fig. 16.

Cabe señalar que la ecuación del filtro y sus parámetros no dependen de la matriz.
, sin embargo, este último debe ser positivo definido.

Para un sistema estacionario con perturbación estacionaria y ruido de medidor estacionario, después del final de los procesos transitorios, la ganancia de la matriz en el filtro de Kalman se vuelve constante
, y la ecuación de Riccati (5.80) degenera a una algebraica. En este caso, el proceso.
y, con Por lo tanto, el proceso
son estacionarios, entonces
.

Escribamos las ecuaciones del filtro de Kalman estacionario de la siguiente forma:

; (5.83)

Uno de los métodos utilizados con frecuencia para resolver la ecuación (5.84) (generalmente usando una computadora digital) es resolver la ecuación no estacionaria (5.80) con los valores constantes correspondientes de los coeficientes a partir de los cuales se forman las matrices A, C, Q, R están compuestos, y una matriz definida arbitraria no negativa de condiciones iniciales para en el tiempo actual hasta que la solución resultante alcance un valor constante en estado estacionario. Este valor final se toma como la solución deseada a la ecuación (5.84). Este método de solución es conveniente porque los algoritmos para resolver ecuaciones diferenciales son, por regla general, más eficientes que los algoritmos para resolver ecuaciones algebraicas no lineales.

Nota 1.

Una propiedad importante del error resultante es que no está correlacionado con el error de estimación, es decir

.

Nota 2.

Consideremos ahora que la ecuación de medición tiene la forma (5.62) y no hay error de medición. En este caso, para obtener una estimación
necesitas usar la derivada
señal observada

que se puede representar como (5.62)

Nota 3.

Para sistemas controlables descritos por un conjunto de ecuaciones.

La ecuación del filtro se puede derivar de manera similar. En este caso, la ecuación del filtro tendrá la forma

donde esta la matriz
y la matriz de correlación
, como antes, se encuentra a partir de la ecuación matricial

con condición inicial
.

CON El sistema de evaluación (filtro) se presenta esquemáticamente en la Fig. 17.

5.5. Síntesis de control localmente óptimo de sistemas estocásticos lineales con información completa y precisa.

Deje que el movimiento controlado en condiciones de perturbación se describa mediante un sistema de ecuaciones.

Proceso aleatorio
y estado inicial asumiremos que son independientes y tienen propiedades (5.28). Se supone que la condición
en cualquier momento conocido. busquemos el control
como alguna función lineal del estado actual

. (5.88)

Entonces el problema de determinar el control local óptimo se reduce a encontrar
-matrices
. Matriz óptima
Buscaremos entre matrices cuyos elementos sean funciones continuas con valores del dominio abierto.

Como funcional que caracteriza el movimiento controlado, tomamos la expectativa matemática del funcional local
(4.27)

.

Introduzcamos la matriz de momentos de correlación.

. (5.89)

Usando (5.88), (5.89) funcional podemos
convertir para ver

(5.90)

Así, el valor del criterio de calidad en el momento actual está determinado por la matriz de momentos de correlación.

Encontremos una ecuación para determinarlo. La ecuación del proceso controlado (5.87) teniendo en cuenta (5.88) se puede representar en la forma

donde esta la matriz

De acuerdo con (5.54), la ecuación de la matriz
se verá como

o, teniendo en cuenta (5.91),

(5.92)

La condición inicial es obviamente

De (5.92), (5.93) teniendo en cuenta el supuesto de que las matrices son simétricas ,
Inmediatamente se deduce que la matriz
es simétrico, es decir
.

Así, el problema de determinar el control óptimo se ha reducido al problema de determinar la matriz
desde la condición mínima
(5,90). Para encontrarlo, usamos la condición (4.28). Derivando (5.90) ​​y teniendo en cuenta (5.92), obtenemos

Escribamos los componentes.
, Dependiendo de
:

Denotemos por
la matriz localmente óptima deseada. Introduzcamos en consideración una familia de funciones de comparación matricial.

.

Dónde
- pequeña variación arbitraria de la función matricial
de la clase en cuestión.

Incremento
, causado por la variación de la matriz
, se verá como

Entonces de (5.94) se sigue que

Por arbitrariedad
y suponiendo que la matriz
no especial, debido a las condiciones
obtenemos una ecuación para determinar la matriz óptima

Valor encontrado
realmente ofrece el mínimo
, desde la segunda variación

debido a la cierta positividad de la matriz
. Aquí.

Comparando (5.88), (5.95) con (4.30), vemos que el control local óptimo encontrado coincide completamente con el control local óptimo para el caso determinista.

Así, el control localmente óptimo sintetizado para un sistema determinista con información completa y precisa sobre su estado resulta ser localmente óptimo para un sistema estocástico excitado por una perturbación aleatoria como el ruido blanco.

Un resultado similar ocurre con el criterio de calidad cuadrático (4.19).

Esto se explica por el hecho de que cuando
El comportamiento de un sistema estocástico depende de la perturbación.
, cuyo valor no es posible predecir, por lo que es aconsejable dejar el control igual que en el caso determinista en ausencia de estas perturbaciones.

5.6. Síntesis del control localmente óptimo de sistemas estocásticos lineales (teorema de separación).

Deje que el movimiento controlado se describa mediante la ecuación (5.87) y la ecuación de medición – (5.62).

Consideremos el problema de síntesis que es óptima según el criterio

En este caso buscaremos un control cuyo valor en el momento del tiempo determinado por los valores de la función vectorial
en el segmento
.

Denotemos por
evaluación óptima del estado del sistema controlado, mediante
- error de estimación.

Junto con el sistema (5.87), consideramos el correspondiente sistema incontrolable

con ecuación de medición

Para el sistema auxiliar se ha solucionado el problema de filtrado y se ha estimado
satisface la ecuación

(5.98)

con condición inicial

donde esta la matriz
determinado a partir de las ecuaciones (5.79), (5.80).

De las ecuaciones (5.87) y (5.97) se deduce que

, (5.99)

Dónde
- matriz fundamental de soluciones de sistemas (5.87).

Buscamos un control que se determine en el momento del tiempo. valores de la función vectorial
en el segmento
. Luego para cada implementación
proceso
control
adquiere un significado específico, es decir El control es un operador determinista sobre un vector de observaciones. Es por eso

(5.100)

De (5.99) y (5.100) se deduce que

Encontremos ahora la ecuación para determinar
. Para ello, derivando (5.100), obtenemos

Teniendo en cuenta (5.98), encontramos

(5.101)

Entonces la ecuación del filtro finalmente se escribirá en la forma (5.85)

con condición inicial

, (5.103)

aquellos. un filtro para determinar una evaluación del estado de control de un sistema es un enlace dinámico, cuya entrada recibe la señal medida y el control
.

Teorema de separación. El control local óptimo del sistema (5.87) según el criterio (5.96) tiene la forma:

Aquí
son las matrices dadas del funcional local, y
- solución de la ecuación vectorial (5.102) con la condición inicial (5.103).

Prueba. Consideremos el funcional (5.96). Teniendo en cuenta que las estimaciones
y error de estimación
no correlacionado para todos , funcional (5.96) se puede representar como

,

Desde entonces
tampoco afecta
, ni
, entonces el problema se reduce a minimizar bajo las condiciones (5.102), (5.103). En este caso, la valoración es completamente observable.

Considere la expresión

Teniendo esto en cuenta, no es difícil demostrar que

Así, en la ecuación (5.102), la expresión
puede considerarse como "ruido blanco" equivalente con una matriz de correlación
.

Como resultado, llegamos al problema de sintetizar una ecuación localmente óptima en el sistema (5.102), (5.103), perturbado por el "ruido blanco" con una medición completa y precisa de su estado, cuya solución se dio en el sección anterior. El teorema ha sido demostrado. Se puede demostrar que el teorema de separación también es válido cuando se sintetiza el control óptimo utilizando una solución cuadrática.