Задачи оптимального управления

Задача дискретной оптимизации

Задачи линейного и квадратичного программирования

Задачей линейного программирования (ЛП) называется задача минимизации или максимизации линейной функции при линейных ограничениях. Так, задача (1.21) является задачей ЛП, если f, g_i, ..., g_m – линей­ные функции, а Р – полиэдр, т.е. множество, само задаваемое линейными условиями (см. (1.17)).

Задачей квадратичного программирования называется задача ми­нимизации при линейных ограничениях квадратичной функции вида

f(x)= áCx, xñ + ád, xñ,

где С – симметрическая неотрицательно определенная матрица раз­мера п´п, d – вектор из Rⁿ. Стало быть, задача квадратичного программирова­ния – это частный случай задачи выпуклого программирования, а задача ЛП – частный случай их обеих (С = 0). Эти два подкласса задач выпуклого программирования в настоящее время наиболее хорошо изучены.

В литературе принят ряд специальных форм записи задачи ЛП, каждая из которых удобнее других в том или ином круге вопросов. Задача ЛП в форме

,

, i =1, …, k,

, i = k+1, …, m,

x_j ³ 0, j = 1, …, s.

называется общей, в форме

, , i = 1, …, m, (1.23)

– основной, в форме

, , i = 1, …, m, x_j ³ 0, j = 1, …, n. (1.24)

– стандартной, в форме

, , i = 1, …, m, x_j ³ 0, j = 1, …, n. (1.25)

– канонической. Здесь с_j, а_ij, b_i – заданные числа.

Часто прибегают к векторно-матричной записи тех же задач. Например, задачу (1.23) можно записать в виде

ác, xñ® min, áa_i, xñ³ b_i, i = 1, …, m, (1.26)

или в виде

ác, xñ® min, Ax ³ b,

где c = (c_i, ..., с_n) Î Rⁿ, b = (b_i, ..., b_m) Î R^m, A–матрица раз­мера т´п со строками a₁, ..., a_m и элементами а_ij.

В дальнейшем будем назы­вать конечные множества и счетные множества без предельных точек дискретными. Задача (1.1) (или (1.4)) называется задачей дискретной оптимизации, если либо само допустимое множество Х Ì Rⁿ дискретно, либо лишь некоторые из координат вектора х = (x₁, ..., x_п) пробегают дискретные множества на числовой оси, когда х пробегает X.

Часто допустимое множество задачи дискретной оптимизации имеет вид

,

где D = D₁ ´ ... ´ D_n, причем D_j Ì {0, ±1, ±2, ...} для j Î J и D_j = R для j Ï J. Здесь J – некоторое подмножество множества {1, ..., п}. В качестве D_j (j Î J) могут выступать, например, D_j ={0, ±1, ±2,...}, D_j = {0, 1, 2,...}, D_j = {0, 1}. Это соответственно означает, что координата x_j вектора х может принимать лишь целые, натуральные, булевые значения.

Задачу (1.1) (или 1.4)) с указанным множеством Х называют задачей дискретного программирования, а при J = {1,..., п} – также задачей целочисленного программирования.

Как мы видим, по своей постановке задача дискретного програм­мирования отличается от общей задачи математического программи­рования специальным заданием прямого ограничения. Здесь также используется запись типа (1.21), т. е.

f(x) ® min,

g_i(x) £ 0, i = 1, …, k, (1.30)

g_i(x)= 0, i = k+1, …, т, x Î D.

Если функции f, g₁, ..., g_m линейны, то задачу (1.30) при J = {1, ..., п} называют целочисленной задачей линейного программи­рования (ЛП), а при J ¹ {1, ..., п} – частично целочисленной зада­чей ЛП. Если D_j = {0, 1}, то иногда говорят о {частично} булевой задаче ЛП.

Постановка задачи опти­мального управления значительно сложнее, чем постановка ранее рассмотренных задач. Поэтому начнем с содержательного примера.

Рассмотрим задачу запуска ракеты в космос. Пусть плоскость орбиты фиксирована, тогда положение ракеты как материальной точки задается двумя координатами x₁, x₂, ее скорость – координа­тами x₃, x₄, масса – координатой x₅. Обозначим через u₁ величину тяги двигателя, а через u₂ – угол между направлением тяги и осью x₁. Тогда, в соответствии с законами механики, движение ра­кеты описывается следующей системой дифференциальных уравнений

, ,

(1.31)

, , ,

где p₁, p₂ – суммарные проекции внешних сил, действующих на ракету, таких как сила тяжести, сопротивление воздуха и т. д., q(u₁) – секундный расход массы, т. е. скорость расхода рабочего вещества. Ракета управляется с помощью выбора параметров управ­ления u = (u₁, u₂), которые подчинены ограничениям вида

, . (1.32)

Вектор управлений задается как функция времени u = u(t), удов­летворяющая ограничениям (1.32). Если теперь подставить и(t)в правую часть системы (1.31), то при выполнении некоторых усло­вий эта система будет иметь единственное решение х(t), определяющее состояние системы (т.е. движение ракеты) в момент t, как только заданы начальные условия х(t₀) = х⁰. Наряду с начальными могут быть заданы и конечные условия при t = Т. Например, если ракету необходимо вывести на круговую орбиту радиуса R с кру­говой скоростью V, то конечные условия примут вид:

(x₁(T))² + (x₂(T))² = R²,

x₁(T) x₃(T) + x₂(T) x₄(T) = R² , (1.33)

(x₃(T))² + (x₄(T))² = V².

Кроме того, существуют ограничения и на фазовые координаты х(t) – фазовые ограничения. Скажем, траектория ракеты не должна пересекать поверхность Земли, не должна заходить в зону радиа­ционных поясов и т. д.

Цель выбора управления u(t), удовлетворяющего условию (1.32), в задаче оптимального управления ракетой (1.31) может состоять, например, в минимизации расхода топлива

. (1.34)

При этом траектория должна удовлетворять начальным и конечным условиям, а также фазовым ограничениям Можно ставить и задачу оптимального быстродействия, т. е. минимизации Т – t₀. Если же требуется вывести ракету на круговую орбиту максимального ра­диуса, то следует максимизировать функционал

(x₁(T))² + (x₂(T))² . (1.35)

Перейдем теперь к общей постановке задачи оптимального управ­ления Аналогом системы (1.31) служит здесь система дифферен­циальных уравнений

, (1.36)

описывающая движение некоторого управляемого объекта, подчинен­ное начальным условиям

x(t₀)Î S₀(t₀), (1.37)

конечным условиям

x(T)Î S(T), (1.38)

и фазовым ограничениям

x(t)Î X(t), t Î [t₀, T]. (1.39)

Ограничения на управление можно записать в общем виде как

u(t)Î U(t), t Î [t₀, T]. (1.40)

Здесь [t₀, T] – отрезок времени, на котором происходит управление системой (1.36), S₀(t₀), S(T), X(t), U(t), при каждом t – заданные множества из пространств соответствующих размерностей.

В качестве целевого функционала (аналога функции цели в за­даче оптимизации (1.1)) примем

. (1.41)

Очевидно, в (1.41) объединены целевые функционалы типа (1.34) и (1.35).

В соответствии с тем, что мы говорили выше, задачу оптималь­ного управления поставим как задачу минимизации функ­ционала (1.41) при ограничениях (1.36), (1.37), (1.38), (1.39), (1.40).