Задача быстродействия "из множества во множество"

Постановка задачи

Задача быстродействия - задача перевода системы из начального фиксированного положения в конечное, также фиксированное, положение за минимальное время. Пусть система определяется условиями: \begin{cases} \dot x(t) = A(t)x(t) + B(t)u(t) + f(t), \\ x(t_0) \in \mathcal{X}^0, x(t_1) \in \mathcal{X}^1, \\ u(t) \in \mathcal{P}(t) \in \text{conv}\mathbb{R}^n, \\ \mathcal{X}^0, \mathcal{X}^1 \in \text{conv}\mathbb{R}^n, \\ t_0 - \text{фиксировано}, \\ t_1 - t_0 \rightarrow \underset{u(\cdot)}{\text{inf}}, \end{cases} где \( A(t), B(t), f(t) \) - непрерывны, а \( \mathcal{P} \) непрерывно как многозначное отображение (это требование гарантирует нам, что для любого \( l: \rho(l\vert\mathcal{P}(\tau))\) по \(\tau\) непрерывна\(^1\)).

\(^1\)В частности, при \(m=1\) множество \(\mathcal{P}\) выглядит как \(\mathcal{P}(\tau) = [a(\tau), b(\tau)]\); неперерывность многозначного отображения означает, что \(a(\tau), b(\tau)\) - непрерывны.

Множества достижимости и разрешимости

Множеством достижимости в момент времени \(t\) будем называть \(\mathcal{X}[t] = \mathcal{X}(t, t_0, \mathcal{X}^0) = \{x| \exists u(\cdot) - \text{измеримая, т.ч.} \forall \tau \leqslant t: u(\tau) \in \mathcal{P}(\tau), \exists x^0 \in \mathcal{X}^0: x(t, t_0, x^0| u(\cdot)) = x\} = \underset{x^0 \in \mathcal{X}^0}{\cup}\mathcal{X}(t, t_0, x^0)\) Множеством разрешимости в момент времени \(t\) будем называть \(\mathcal{W}[t] = \mathcal{W}(t, t_1, \mathcal{X}^1) = \{x| \exists u(\cdot) - \text{измеримая, т.ч.} \forall \tau \leqslant t: u(\tau) \in \mathcal{P}(\tau), \exists x^1 \in \mathcal{X}^1: x(t, t_1, x^1| u(\cdot)) = x\} = \underset{x^1 \in \mathcal{X}^1}{\cup}\mathcal{W}(t, t_1, x^1)\)

Пример множеств достижимости и разрешимости.

Заметим, что \(\mathcal{X}[t_1] \cap\mathcal{W}[t_0]\) содержит в себе оптимальную траекторию (см.рисунок).

Свойства множеств достижимости и разрешимости

Выпуклость и компактность

Утверждение: Множества достижимости и разрешимости - непустые выпуклые компакты.

Доказательство: Заметим, что: \[ \begin{cases} \mathcal{X}\left(t, t_0, \mathcal{X}^0\right) = X(t, t_0)\mathcal{X}^0 + \mathcal{X}(t, t_0, 0), \\ \mathcal{W}\left(t, t_1, \mathcal{X}^1\right) = X(t, t_1)\mathcal{X}^1 + \mathcal{W}(t, t_1, 0), \end{cases} \] где \(X(t, \tau)\) - фундаментальная матрица Коши[1]. В самом деле, по формуле Коши[2]: \[ x(t) = X(t, t_0)x^0 + \int\limits_{t_0}^{t}X(t, \tau)(B(\tau)u(\tau)+f(\tau))d\tau. \] Тогда в силу определения множества достижимости через объединение по всем допустимым значениям из исходного множества \(\mathcal{X}^0\) и всем допустимым управлениям \(u(\cdot)\) получаем формулу выше. Аналогичным образом посутпаем с формулой для множества разрешимости. При решении задачи быстродействия "из точки в точку" доказываются следующие два факта: \[ \begin{cases} \mathcal{X}(t, t_0, 0) \in \text{conv}\mathbb{R}^n, \\ \mathcal{W}(t, t_1, 0) \in \text{conv}\mathbb{R}^n. \end{cases} \] По условию задачи: \(\mathcal{X}^0, \mathcal{X}^1 \in \text{conv}\mathbb{R}^n\). Тогда: \[ X(t, t_0)\mathcal{X}^0 \in \text{conv}\mathbb{R}^n, \\ X(t, t_1)\mathcal{X}^1 \in \text{conv}\mathbb{R}^n. \] Суммируя непустые выпуклые компакты, получаем: \[ \begin{cases} X(t, t_0)\mathcal{X}^0 + \mathcal{X}(t, t_0, 0) \in \text{conv}\mathbb{R}^n, \\ X(t, t_1)\mathcal{X}^1 + \mathcal{W}(t, t_1, 0) \in \text{conv}\mathbb{R}^n, \end{cases} \] что и требовалось.

Критерий оптимальности конечного времени

Утверждение: \(t_1^*\) - оптимальное конечное время тогда и только тогда, когда \(t_1^*\) - минимальный корень уравнения (относительно \(t\)): \[ d(\mathcal{X}(t, t_0, \mathcal{X}^0), \mathcal{X}^1) = 0, \] на луче \(t_1 \geqslant t_0\), где \(d(X, Y)\) - евклидово расстояние между множествами \(X\) и \(Y\).

Теорема фон Неймана о минимаксе [3]

Если выполнены следующие условия: \[ \begin{cases} X, Y - \text{выпуклые компакты}, \\ X \subseteq \mathbb{R}^k, Y \subseteq \mathbb{R}^l, \\ \varphi : X \times Y \rightarrow \mathbb{R} \text{, непрерывна на } X \times Y, \\ \forall y\in Y: \varphi(\cdot, y) -\text{ выпукла по }x, \\ \forall x\in X: \varphi(x, \cdot) -\text{ вогнута по }y, \end{cases} \] то: \[ \underset{x\in X}{\text{inf}}~\underset{y\in Y}{\text{sup}}~\varphi(x, y) = \underset{y\in Y}{\text{sup}}~\underset{x\in X}{\text{inf}}~\varphi(x, y). \] Доказательство теоремы фон Неймана приводится в теоремах 1.3 и 1.1 курса лекций по теории игр и исследованию операций Морозова В.В. [4].

Принцип максимума Понтрягина

Пусть задана линейная задача быстродействия: \[ \begin{cases} \dot{x} = Ax + Bu, \hspace{5mm} t \in [t_0, +\infty], \\ x(t_0) \in \mathcal{X}_0, x(t_1) \in \mathcal{X}_1, \\ \forall t: u(t) \in \mathcal{P(t)}, \\ (t_1 - t_0) \rightarrow \underset{u}{\text{inf}}. \end{cases} \] Пусть \((x^*(t), u^*(t))\) - оптимальная пара, \(u^*(t)\) переводит фазовую точку из положения \(x(t_0) \in \mathcal{X}_0\) в положение \(x(t_1) \in \mathcal{X}_1\) за время \(t_1\). Тогда существует непрерывная вектор-функция \(\psi = \psi(t)\), нигде не обращающаяся в нуль и удовлетворяющая следующим условиям: \[ \begin{cases} \dot{\psi(t)} = -A^T\psi(t) ~ \textbf{(сопряжённая система)}, \\ \langle B^T\psi(t), u^*(t) \rangle \stackrel{\text{п.в.}}{=} \rho(B^T\psi(t) ~|~ \mathcal{P}) ~ \textbf{ (условие максимума)}, \\ \langle \psi(t_0), x(t_0) \rangle = \rho(\psi(t_0) ~|~ \mathcal{X}_0) ~ \textbf{ (условие трансверсальности в \(\mathcal{X}_0\))}, \\ \langle -\psi(t_1), x(t_1) \rangle = \rho(-\psi(t_1) ~|~ \mathcal{X}_1) ~ \textbf{ (условие трансверсальности в \(\mathcal{X}_1\))}, \end{cases} \] где под \(\rho(l|X)\) понимается значение опорной функции множества \(X\) в направлении \(l\).

Доказательство принципа максимума Понтрягина можно найти в книге: Л.C.Понтрягин, В.Г.Болтянский, Р.В.Гамкрелидзе, Е.Ф.Мищенко. "Математическая теория оптимальных процессов". — М.: Наука, 1976 [5].