tsvpis

4.2. Задача об оптимальном наборе самолетом скорости и высоты

Задача. Необходимо, имея стартовую нулевую скорость v и стартовую нулевую высоту h, набрать некоторую скорость V и высоту H, минимизировав при этом суммарные затраты топлива.

Если в какой-то момент времени t мы увеличиваем скорость на dv, а высоту на dh, то затраты горючего на это изменение могут быть определены по формуле:

C_v(v(t),h(t))dv + C_h(v(t),h(t))dh,

где v(t) и h(t) – скорость и высота в момент времени t;

C_v(v(t),h(t)) и C_h(v(t),h(t)) – коэффициенты пропорциональности затрат топлива.

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

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

Рисунок 4.4. – Дискретизация исходной задачи.

Заполняем стоимости, начиная с левого нижнего угла, и записываем их в левый сектор круга. Аналогично считаем стоимости вершин с правого верхнего угла и записываем их в правый сектор. Глядя на полученный стоимости, восстанавливаем оптимальный путь: 87 получили из 79 + 8; 79 из 70 + 9 и т.д.

Комментарии

В принципе, при восстановлении оптимального пути, возможно ветвление маршрута (когда минимум получен на пути не из одной, а из большего количества вершин).
Все вершины графа разбиваются на группы состояний по диагоналям. Но в группу S⁽ⁱ⁾ мы попадем не только из S⁽ⁱ^-1), но и из S⁽ⁱ^-2).
При проходе слева направо и справа налево, как и следовало ожидать, стоимость пути одинакова и равна 87. В каждом кружке сумма чисел больше либо равна 87. Причем сумма равна 87 в кружках, лежащих на оптимальном пути, а для остальных превышает 87. В каждом кружке – левое число – стоимость маршрута из левого нижнего угла до данного кружка. Правое число – стоимость маршрута из правого верхнего угла до данного кружка.

Содержание