2. ЗАДАЧА О НАБОРЕ ВЫСОТЫ И СКОРОСТИ ЛЕТАТЕЛЬНЫМ АППАРАТОМ

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

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

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

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

Будем изображать состояние самолета точкой на плоскости VOH (рис. 3.2), где абсцисса — скорость самолета, а ордината — его высота.

Очевидно, существует множество возможных управлений — множество траекторий, по которым можно перевести точку S из

Рис. 3.2

Из всех этих траекторий нужно выбрать ту, на которой расход горючего будет минимальным.

Будем решать задачу методом динамического программирования. Для этого разделим интервал скоростей на равных частей:

а интервал высот — на равных частей:

Рис. 3.3

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

Например, для случая, изображенного на рис. 3.3,

Любая траектория, переводящая точку S из состоит из 14 шагов, или этапов.

Рис. 3.4

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

Любой траектории, переводящей S из соответствует вполне определенный расход горючего, равный сумме чисел, написанных на отрезках. Например, траектория, помеченная стрелками на рис. 3.4, дает расход горючего:

Нам нужно из всех траекторий выбрать ту, для которой расход горючего минимален. Можно было бы, конечно, перебрать все возможные траектории, но их слишком много. Гораздо проще будет решить задачу методом динамического программирования. Процесс состоит из 14 шагов; будем оптимизировать каждый шаг, начиная с последнего. Конечное состояние самолета (точка SM) нам задано; 14-й шаг непременно должен привести нас в эту точку.

Посмотрим, откуда мы можем переместиться в точку за один шаг, т. е. каковы возможные состояния самолета после предпоследнего, 13-го шага?

Рассмотрим отдельно правый верхний угол нашей прямоугольной сетки (рис. 3.5) с конечной точкой . В эту точку можно за один шаг переместиться из двух соседних точек: причем из каждой — только одним способом, так что выбора условного управления на последнем шаге у нас нет — оно единственно. Если предпоследний шаг привел нас в точку мы должны двигаться по горизонтали (набирать скорость) и тратить 17 единиц горючего; если в точку — идти по вертикали (набирать высоту) и тратить 14 единиц. Запишем эти минимальные (в данном случае просто неизбежные) расходы в специальных кружках, которые поставим в точках (рис. 3.6). Запись «17» в кружке у означает: «если мы пришли в , то минимальный расход горючего, переводящий нас в точку равен 17 единицам».

Рис. 3.5

Рис. 3.6

Аналогичный смысл имеет запись «14» в кружке у точки . Оптимальное управление, приводящее к этому расходу, помечено в каждом случае стрелкой, выходящей из кружка. Стрелка указывает то направление, по которому мы должны двигаться из данной точки, если в результате предыдущей нашей деятельности оказались в ней.

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

Перейдем к планированию предпоследнего, 13-го шага. Для этого рассмотрим все возможные результаты предпредпоследнего, 12-го шага. После этого шага мы можем оказаться только в одной из точек (рис. 3.7). Из каждой такой точки мы должны найти оптимальный путь в точку и соответствующий этому пути минимальный расход горючего.

Если мы оказались в точке то выбора нет: мы должны перемещаться по горизонтали и тратить единицы горючего. Этот расход мы запишем в кружке при точке а оптимальное (в данном случае единственное) управление из точки снова пометим стрелкой.

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

Значит, оптимальный путь из в начинается вертикальным участком (отметим это вертикальной стрелкой), а минимальный расход горючего равен 30 (это число мы запишем в кружке при точке ).

Наконец, для точки путь в опять единственный: по вертикали. Обходится он в единиц; эту величину (26) мы и запишем в кружке при а стрелкой пометим оптимальное управление.

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

Рис. 3.7.

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

В результате выполнения такой процедуры, из каждой узловой точки (см. рис. 3.8) проводится стрелка, указывающая условное оптимальное управление, а в кружке записывается минимальная стоимость перехода из этой точки в (условная минимальная стоимость). Рано или поздно процесс заканчивается, дойдя до исходной точки

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

При этом мы строим оптимальную траекторию точки S, перемещаясь по стрелкам из

На рис. 3.8 показан окончательный результат такой процедуры — оптимальная траектория отмечена жирными кружками и дополнительными стрелками. Число «139», стоящее у точки означает минимальный расход горючего , меньше которого нельзя получить ни на какой траектории.

Таким образом, поставленная задача решена, и оптимальное управление процессом найдено. Оно состоит в следующем:

— на первом шаге увеличивать только скорость, сохраняя неизменной высоту и довести скорость до ;

Рис. 3.8

— на втором и третьем шагах увеличить высоту до сохраняя скорость неизменной;

— на четвертом, пятом и шестом шагах снова набирать скорость, пока она не станет равной

— на седьмом и восьмом шагах набирать высоту и довести ее до

— на девятом, десятом, одиннадцатом и двенадцатом шагах снова набирать скорость и довести ее до заданного конечного значения

— на последних двух шагах (тринадцатом и четырнадцатом) набирать высоту до заданного значения На.

Нетрудно на ряде примеров убедиться, что найденное управление действительно является оптимальным и на любой другой траектории расход горючего будет больше (или, по крайней мере, не меньше).

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

Действительно, в нашей упрошенной постановке задачи на каждом шагу нам нужно выбирать только между двумя управлениями: «набирать высоту» и «набирать скорость». Именно в связи с таким элементарно простым набором управлений задача очень легко решается до конца.

Такая намеренно упрощенная постановка задачи не вполне соответствует действительности. Фактически летательный аппарат может набирать (а зачастую и набирает) высоту и скорость одновременно.

В этом случае для каждой точки на плоскости точка S может двигаться под любым углом в пределах некоторого сектора (рис. 3.9), причем каждому направлению соответствует свой расход горючего на единицу длины пройденного пути (разумеется, не реального пути, а условного — на плоскости ).

Рис. 3.9

Чтобы решить такую задачу динамического программирования, мы должны как-то установить «шаги» или «этапы» процесса. Нам здесь уже неудобно будет пользоваться тем разделением на этапы, которое мы выбрали для предыдущей задачи Удобнее будет разбить отрезок на частей, провести через точки деления ряд опорных прямых , перпендикулярных и предположить, что «шаг» состоит из перехода точки с одной из опорных прямых на другую (рис. 3.10). Если взять опорные прямые достаточно близкими, можно допустить, что каждый участок траектории, от одной опорной прямой до следующей, — прямолинеен. Разумеется, направление каждого такого участка не должно выходить за пределы «разрешенного сектора», определяемого «розой направлений» на рис. 3.10.

Расход горючего на прямолинейном участке определяется точкой, где он начинается, направлением участка и его длиной.

Схема решения такой задачи методом динамического программирования несколько сложнее, чем вышеописанная «ступенчатая» схема, но в принципе отличается от нее только тем, что на каждом шаге приходится выбирать не между двумя направлениями, а между несколькими.

Начинается процесс с последнего шага (рис. 3.11). Прежде всего, определяются возможные положения точки на прямой из которых она может прийти в за один шаг. Это, очевидно, все положения от А до В (так как выбранная нами роза направлений предполагает, что скорость и высота в процессе набора убывать не могут). Зададимся на отрезке А В рядом возможных положений точки S, для каждого из них построим прямолинейный участок пути к точке S и подсчитаем на этом участке расход горючего.

Рис. 3.10

Движение по этому участку и будет (вынужденным) оптимальным управлением, в расход — (неизбежным) минимальным расходом. Таким образом, условная оптимизация последнего шага выполнена. Перейдем к предпоследнему шагу. Зададимся рядом точек на отрезке прямой

Рис. 3.11

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

Далее переходим к оптимизации шага, и т. д. На каждом этапе ищется такое направление движения из каждой точки, для которого расход горючего на ближайшем шаге плюс (уже оптимизированный) расход горючего на всех оставшихся до конца шагах достигает минимума. Этот процесс условной оптимизации продолжается до тех пор, пока мы не дойдем до первого шага, начало которого уже не надо варьировать — оно известно. Таким образом определяется минимальный расход горючего на всю операцию, начиная от точки . Далее, двигаясь из каждой точки, начиная от по оптимальному пути, находим оптимальный режим набора высоты и скорости (отмечен на рис. 3.11 точками).

Заметим, что описанная методика построения оптимальной траектории точки S (оптимального управления) отнюдь не относится только к случаю набора высоты и скорости. По осям могут откладываться не высота и скорость, а любые другие величины, например:

— декартовы (полярные) координаты движущейся точки;

— вес и три составляющие скорости ракеты;

— количества средств, вкладываемые в разные отрасли производства и т. п.

Равным образом, максимизируемый (минимизируемый) показатель эффективности W может быть любой природы, например:

— расход материальных средств на систему мероприятий;

— время перемещения из точки ;

— доход, приносимый группой предприятий, и т. д.

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