3.9. задача об управлении самолетом

3.9. задача об управлении самолетом

Условие задачи. Самолет, имеющий скорость V0 и находящийся на высоте Но, должен увеличить скорость и высоту полета до значений Vi > Vo и Hi > Н0. Требуется найти такое оптимальное управление самолетом, позволяющее выполнить заданный маневр с минимальными затратами топлива.

26

28

29

т

42

Т 47

т

48

Я, 5

т

24

- 25 ->

- 27 ->

Т 46

т

38

т

42

45

22

- 23 ->

- 26 ->

t 43

t 35

т

39

Т 41

т

20

21

24

t 34

t 38

т

41

36

18

21

19

t 37

t 31

t 39

t 35

18

17

16

t 34

3

Vi

H0 0

0 Vo

Рис. 3.20

Данные о затратах топлива на выполнение самолетом элементарных операций по увеличению скорости на постоянной высоте и по набору высоты при постоянной скорости получены при проведении летных испытаний и представлены в виде схемы на рис. 3.20, в которой для определенности интервал изменения скорости (Vo, Vi) разбит на три равных шага, а интервал изменения высоты (Я0,Яі) — на пять равных шагов.

На данной схеме точками представлены характерные значения скорости и высоты, для которых проведены замеры на испытаниях; эти точки являются вершинами графа, интерпретирующего поставленную задачу. Числа между вершинами графа указывают затраты топлива в усл. ед. на выполнение операций по увеличению скорости или набору высоты. Считается, что при выполнении заданного маневра самолету не разрешается снижать скорость и высоту полета (иными словами, изменение параметров полета должно проводиться на схеме по стрелкам направленным вправо при ускорении или вверх при подъеме); данное предположение естественным образом вводит ориентацию на графе.

Решение. Данная задача является примером общей задачи о кратчайшем пути на орграфе, в которой роль длины пути играют затраты

топлива на выполнение соответствующего маневра. Представленная

в условии задачи схема является взвешенным орграфом специального вида. Каждая вершина данного орграфа однозначно определяется парой координат, равных числу шагов от вершины, отвечающей

начальным значениям (Vo,Hq), по осям скорости V и высоты Я к рассматриваемой вершине. Например, вершина, отвечающая начальным

значениям (Vo, Яп), имеет координаты (0;0), а вершина, отвечающая

конечным значениям (Vi, Н), имеет координаты (3;5). Шаг по скорости

составляет т, ТЛ

Hi н0

AV = ^,

шаг по высоте

АН

5

Решим задачу, проводя запись на самом графе. В соответствии с методом ДП определим функцию L(v) как длину кратчайшего пути от вершины v до конечной вершины с координатами (3;5); при этом L(3;5) = 0. Установим, для каких вершин может быть вычислено значение функции L(v) в настоящий момент; у этих вершин все исходящие дуги должны заходить в вершину (3;5). Очевидно, что такими вершинами являются две вершины орграфа, имеющие координаты (2;5) и (3;4). Для вершины с координатами (2;5) единственная исходящая дуга соответствует увеличению скорости и заходит в конечную вершину. По основной расчетной формуле (1) метода ДП получаем:

L(2; 5) = 29 + L(3; 5) = 29 + 0 = 29.

Аналогичным образом, для вершины с координатами (3;4) единственная исходящая дуга соответствует набору высоты и заходит в конечную вершину; соответственно

L(3; 4) = 48 + L(3; 5) = 48 + 0 = 48.

Таким образом, значение функции L(v) вычислено уже для трех вершин.

Продолжим расчеты далее и установим, для каких вершин могут быть вычислены значения функции L(v) в настоящий момент. Этими вершинами являются три вершины орграфа, имеющие координаты (1;5), (2;4) и (3;3), лежащие на одной «диагонали». При этом для вершин (1;5) и (3;3) имеется лишь по одной исходящей дуге, заходящей в вершину с уже известным значением функции L(v). По основной формуле метода ДП для этих вершин

Ц1; 5) = 28 + Ы25) = 28 + 29 = 57, L(3; 3) = 46 + ЦЗ; 4) = 46 + 48 = 94.

Для вершины (2;4) имеются две дуги, соответствующие увеличению скорости и набору высоты и заходящие в вершины с уже известными значениями функции L(y) соответственно

1(2; 4) = min {27+ £(3; 4); 47+ £(2; 5)} = min {27 + 48; 47 + 29} = 75.

Найденный минимум достигается при управлении, отвечающем увеличению скорости самолета; данный факт будем отмечать двойной дугой на орграфе, см. рис. 3.21. Проводя аналогию с классическим методом ДП, можно сказать, что для вершины (2;4) увеличение скорости представляет собой условно-оптимальное управление, т. е. первый шаг условно-оптимальной траектории, начинающейся из вершины (2;4), имеет вид (2; 4) —> (3;4).

Поступая аналогичным образом, мы последовательно вычислим значения функции L(v) во всех вершинах орграфа; при этом расчеты ведутся, переходя от указанной выше «диагонали» к следующим нижестоящим. Последней вершиной, в которой будет вычислено значение функции L(v), является начальная вершина с координатами (0;0). Для нее

L(0;0) = min{l6 + L(l;0);31 +L(0;1)} = = min {16 + 245; 31 + 229} = 260,

причем минимум достигается при управлении, отвечающем набору высоты. Как обычно, данный факт отмечаем двойной дугой на орграфе. Таким образом, для начальной вершины (0;0) набор высоты представляет собой условно-оптимальное управление, а первый шаг оптимальной траектории имеет вид (0;0) —> (0;1).

Вычисление значения функции L{y) для начальной вершины означает завершение этапа условной оптимизации решения задачи. Результаты расчетов приведены на рис. 3.21 жирным шрифтом на месте соответствующих вершин. Отметим, что для вершины (0;3) имеется две двойные дуги, что означает наличие двух различных условно-оптимальных траекторий из этой вершины в конечную.

Приступаем к этапу безусловной оптимизации. Как видно из расчетов, оптимальное значение задачи, т. е. минимальные затраты топлива на выполнение маневра, составляют 260 усл. ед. Оптимальное управ 

Рис. 3.21

ление строится начиная с вершины (0;0) с использованием двойных дуг орграфа. При этом получаем последовательность вершин:

(0; 0) -> (0; 1) -> (1; 1) ^ (1; 2) ^ (1; 3) ^ (2; 3) (2; 4) -> (3; 4) -> (3; 5).

Решение задачи завершено. Полученный кратчайший путь, безусловно, имеет содержательную трактовку в терминах рассматриваемой задачи.

Ответ: минимальные затраты топлива на выполнение заданного маневра составляют 260 усл. ед. Оптимальное управление самолетом состоит в следующем:

подъем до высоты if о + Aif;

увеличение скорости до величины Vo + ДV;

подъем до высоты Щ + ЗАН;

увеличение скорости до величины Vo + 2Д V;

подъем до высоты if о + 4 Дії;

увеличение скорости до величины Vo + ЗДV = Vi;

подъем до высоты Щ + 5Дії = Н.

К постановке и решению данной задачи необходимо сделать ряд следующих замечаний.

Замечание 1. Иная подобная постановка задачи об управлении самолетом требует увеличить скорость и высоту полета таким образом, чтобы минимизировать не затраты топлива, а время выполнения заданного маневра. Решается такая задача полностью аналогично рассмотренной.

Замечание 2. Отметим, что по завершению решения задачи функция L(v) оказывается вычислена для всех вершин орграфа. Иными словами, минимальные затраты топлива на ускорение до скорости V и подъем до высоты Hi найдены не только для начальных значений Vo и Hq, но и для всех промежуточных значений, соответствующих вершинам орграфа. Тем самым мы решили не одну, а целый класс подобных задач, в котором исходная задача имеет самую высокую размерность. Такая особенность решения является характерным свойством метода ДП.

Замечание 3. Теоретически данную задачу можно было решить и методом перечисления путей. Проведем сопоставление трудоемкости расчетов данным методом и методом ДП. Сделаем это в общем виде, считая, что схема содержит m шагов по горизонтали и п шагов по вертикали. Обозначим через P(m,n) и P*(m,n) число операций сложения, которые необходимо выполнить для решения задачи соответственно методом перечисления путей и методом ДП, и вычислим эти функции.

Начнем с функции Р* (тп, п). Как показывает проведенное решение, для вычисления значений функции L(v) в «самых правых» и «самых верхних» вершинах за исключением конечной (таких вершин всего m+n) пришлось выполнить по одной операции сложения, а в остальных вершинах (таких вершин всего m-n) — по две операции. Таким образом, справедливо равенство

Р* (тп, п) = тп + п + 2mn.

Обратимся к функции Р(тп, п) и обозначим через W(m, п) число всех путей от начальной вершины к конечной. Каждый такой путь состоит из m + n дуг, и для расчета длины пути необходимо выполнить m + n —1 операцию сложения; следовательно, имеет место соотношение

P(m, п) = (тп + п — 1) • W(m, п).

Каждый путь однозначно определяется набором номеров (от 1 до m + n) тех шагов, на которых выбирается увеличение скорости полета. Поскольку увеличение скорости должно выбираться ровно m раз, то число всех путей вычисляется по формуле

W(m,n) = CZ+n,

где С™+п — число сочетаний из m + n элементов по т. Как известно из элементарной математики,

m ^ (т + п)! т+та т! • п! '

Таким образом,

Р(т,п) = (т + П-1)Щ±Щ.

Сопоставим вычисленные функции в наиболее простом случае, когда число шагов по обоим направлениям совпадает, т. е. m = п = к.

Т°ГДа (2кУ

Р(к,к) = (2к-1)^ф, Р*(к,к)=2к(к + 1).

Р(к,к) _ (2fc l)(2fe 1)!

Р*(к,к) (к + 1)(к)2 является показателем того, насколько метод ДП более экономичен в плане вычислений для задач данного типа, чем метод перечисления путей. Обозначим целую часть рассматриваемого отношения через Щк). Некоторые значения функции R(k) приведены в следующей таблице.

Как видно из таблицы, значения Щк) очень быстро растут с увеличением к. Степень роста можно проиллюстрировать следующим примером. Предположим, что. задача рассматриваемого типа с m = 20 и п = 20 решается на ЭВМ (отметим, что для реальных задач размерность 20 х 20 вовсе не является высокой). Для упрощения ситуации будем считать, что в ходе решения задач на ЭВМ затрачивается время только на выполнение операций сложения (затратами времени на доступ к памяти, выполнение логических операций, другими неизбежными «накладными» расходами мы пренебрегаем). Пусть решение задачи на ЭВМ по программе, составленной на основе метода ДП, заняло 0,001 с, т. е. с точки зрения человека прошло мгновенно. Тогда решение той же задачи на той же ЭВМ по программе, составленной на основе метода перечисления путей, займет около 2,5 месяцев. Понятно, что искомое оптимальное решение может полностью потерять свою актуальность задолго до окончания столь длительного срока. Для задач более высоких размерностей возникают еще более разительные соотношения. Безусловно, столь контрастные результаты получаются при сопоставлении двух «полярных» вариантов расчетов: близкого к наилучшему (метод ДП) и заведомо нерационального, «неразумного» варианта (перечисление, т. е. полный перебор). Тем не менее, данный пример еще раз показывает важность применения передовых математических методов для решения выдвигаемых экономической практикой задач.

Замечание 4. Данную задачу можно решить и классическим методом ДП. Рассмотрим, как в этом случае надлежит провести математическую формализацию задачи.

Число шагов N в данной задаче принимаем равным

m + n = 3 + 5 = 8.

В качестве фазовой переменной Х{ можно выбрать координаты (m';n') вершин орграфа, где m',n'— целые числа,

О ^ m' ^ т — 3, 0 ^ n' ^ п = 5,

номер і состояния равен m' + n', xq = (0;0). В данном случае мы встречаемся с новой для нас ситуацией, когда фазовая переменная является не числом, а вектором размерности 2.

В качестве управляющей переменной щ следует выбрать переменную, принимающую два значения, отвечающих увеличению скорости и набору высоты (коротко — ускорение или подъем). Это можно записать, например, в виде щ ^{«Ускорение», «Подъем»}. Конечно, для «самых правых» и «самых верхних» вершин допустимым будет только одно из двух значений управления.

Функция процесса Хі =/j(xj_i, гц) для данной задачи может быть представлена следующим образом. Если Хі= (m';n'), то

Ґ (m' + если щ =«Ускорение-»;

Xi = <

( (m ;n +1), если щ = «Подъем».

Функция Zi = Zi(xi-i,Ui) равна затратам топлива на выполнение

элементарной операции по управлению самолетом и полностью определяется числовыми данными задачи, приведенными на схеме: если

щ =« Ускорение», то Zi равна числу, расположенному справа от вершины = (m';n'); если же щ = «Подъем», то равна числу,

расположенному сверху от той же вершины.

Замечание 5. Естественным и логичным обобщением рассматриваемой задачи, приближающим ее к реальной ситуации, является допущение одновременного увеличения скорости и набора высоты самолетом. Одновременное ускорение и подъем соответствует перемещению

на схеме по восходящей диагонали от некоторой вершины к вершине (г + 1; j + І), где і = 0,1,2, j = 0,1,2,3,4. Затраты топлива на выполнение данного элемента пилотажа будем рассчитывать следующим образом. Обозначим через Qv(i',j) затраты топлива на увеличение скорости от значения Vo + iAV до Vo + (i + l)AV на постоянной высоте Hq + jAH (иными словами, при переходе на схеме от к (i + l;j)).

Аналогично, обозначим через Qh{v,J) затраты топлива на набор высоты от значения HQ+jAH до H0 + (j + l)AH при постоянной скорости Vo + iAV (при переходе на схеме от (i;j) к (г; j + 1)). Примем, что затраты топлива на одновременное ускорение и подъем от значений скорости и высоты, отвечающих вершине с координатами (i;j), до значений, отвечающих вершине с координатами (i + 1; j + 1), равны

0,4 • (Qv{i;j) +Qv(ij + l)+ QH{ij) +QH(i + l;j)).

Например, в соответствии с приведенными выше данными

<2v(0;2)=20, QH(1;4)=45,

а затраты топлива на одновременное ускорение и подъем от точки (1;3) до точки (2;4) равны

0,4 • (23 + 42 + 25 + 41) = 52,4 усл. ед.

Отметим, что в новой постановке задачи множество допустимых вариантов управления шире, чем в исходной постановке; в силу этого новые минимальные затраты топлива на выполнение заданного маневра должны получиться заведомо не большими значения 260 усл. ед., полученного для исходной постановки.

Задание. Провести решение задачи об управлении самолетом в новой постановке методом ДП.