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

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

Данные о затратах топлива на выполнение самолетом элементар­ных операций по увеличению скорости на постоянной высоте и по набору высоты при постоянной скорости получены при проведении летных испытаний и представлены в виде схемы на рис. 3.20, в кото­рой для определенности интервал изменения скорости (Уо, VI) разбит на три равных шага, а интервал изменения высоты (Н₀, Н\) — на пять равных шагов.

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

Решение. Данная задача является примером общей задачи о крат­чайшем пути на орграфе, в которой роль длины пути играют затраты топлива на выполнение соответствующего маневра. Представленная в условии задачи схема является взвешенным орграфом специаль­ного вида. Каждая вершина данного орграфа однозначно определя­ется парой координат, равных числу шагов от вершины, отвечающей начальным значениям (Уо,Но), по осям скорости V и высоты Н к рас­сматриваемой вершине. Например, вершина, отвечающая начальным значениям (Уо,#о), ^имеет координаты (0;0), а вершина, отвечающая конечным значениям (VI, Н\), имеет координаты (3;5). Шаг по скорости составляет                                _т, _т.

шаг по высоте                   „ „

_дя= Нг^Щ

5

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

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

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

Ь{3; 4) = 48 + Ь(3; 5) = 48 + 0 = 48.

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

значение функции / ((') вычислено уже для трех вер

шин.

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

L(l;5) — 28 + 1(2; 5) = 28 + 29 = 57, Ц 3; 3) = 46 + Ц 3; 4) = 46 + 48 = 94.

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

L(2; 4) = min {27 + L(Z\4); 47 + L(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;l)} = = min {16 + 245; 31 + 229} = 260,

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

Вычисление значения функции L(v) для начальной вершины озна­чает завершение этапа условной оптимизации решения задачи. Ре­зультаты расчетов приведены на рис. 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 усл. ед. Оптимальное управление самолетом состоит в следующем:

—               подъем до высоты Но + АН\

—               увеличение скорости до величины Уо + А V;

—               подъем до высоты Но + ЗАН\

—               увеличение скорости до величины Уо 4- 2Д V;

—               подъем до высоты Но + 4АН:

—               увеличение скорости до величины Уо + ЗА V = VI',

—               подъем до высоты Но + 5АН = Н\.

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

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

Замечание 2. Отметим, что по завершению решения задачи функ­ция Ь(у) оказывается вычислена для всех вершин орграфа. Иными словами, минимальные затраты топлива на ускорение до скорости У\ и подъем до высоты Н1 найдены не только для начальных значе­ний и Н₀, но и для всех промежуточных значений, соответству­ющих вершинам орграфа. Тем самым мы решили не одну, а целый класс подобных задач, в котором исходная задача имеет самую высо­кую размерность. Такая особенность решения является характерным свойством метода ДП.

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

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

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

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

Р(т, п) = (т + п — 1) • IV(т, п).

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

\¥(т,п) = С%_+п,

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

_т ^ (то + п)! ^т+п ш! • п! '

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

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

т\ ■ п\

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

^Т°^ГДа                            (2кУ

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

Отношение       _р{Кк) ^ _{2к__1){2к_₁₎₁

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

 

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

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

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

т + п = 3 + 5 = 8.

2.               В качестве фазовой переменной х, можно выбрать координаты (■т'\п') вершин орграфа, где т',п' — целые числа,

О ^ т' ^ т = 3, 0 ^ п' ^ п = 5,

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

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

4.               Функция процесса х^ = /_?(з;_?;_1, и,) для данной задачи может быть представлена следующим образом. Если х^-х = (ш';п'), то

Г (т' + 1;п'), если щ —« Ускорение»-,

Х{ = <

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

5.                 Функция 2, = 2, (х_г-1, и,) равна затратам топлива на выполнение элементарной операции по управлению самолетом и полностью опре­деляется числовыми данными задачи, приведенными на схеме: если щ =« Ускорение», то 2_Г равна числу, расположенному справа от вер­шины         = (ш';п'); если же и_г = «Подъем», то 2-, равна числу, расположенному сверху от той же вершины.

Замечание 5. Естественным и логичным обобщением рассматри­ваемой задачи, приближающим ее к реальной ситуации, является до­пущение одновременного увеличения скорости и набора высоты само­летом. Одновременное ускорение и подъем соответствует перемещению на схеме по восходящей диагонали от некоторой вершины (г; ]) к вер­шине (г + 1;.7 + 1), где г = О,1,2, ] = 0,1,2,3,4. Затраты топлива на вы­полнение данного элемента пилотажа будем рассчитывать следующим образом. Обозначим через С}у{цз) затраты топлива на увеличение скорости от значения Уо + г&У до Уо +         на постоянной высоте

Яо + ^'ДЯ (иными словами, при переходе на схеме от (г;^) к (г+1;^)).Аналогично, обозначим через С}н{г\з) затраты топлива на набор вы­соты от значения Н_(}+]АН до Я₀ + (^ + 1)ДЯ при постоянной скорости Уо + гДК (при переходе на схеме от (г,]) к (г\] + 1)). Примем, что затраты топлива на одновременное ускорение и подъем от значений скорости и высоты, отвечающих вершине с координатами (г;/), до зна­чений, отвечающих вершине с координатами (г + 1;^' + 1), равны

0,4 - (С)у(г,з) +ЯУ(цз + 1) + <Эн{ъ\Л + +

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

<2у(0;2)=20, <Эн(1; 4) = 45,

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

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

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

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