Динамическое программирование. Динамическое программирование
 Скачать 0.81 Mb.
|
Задача о наборе высоты и скоростиПостановка задачи.Пусть самолет, находящийся на высоте  , и имеющий скорость  , должен подняться на высоту  , и приобрести скорость . Известен расход горючего при подъеме с любой высоты  на любую высоту  при постоянной скорости, а также расход горючего на увеличение скорости от  до  при известной высоте. Согласно законам аэродинамики лучше разгоняться на большей высоте, где плотность воздуха и, следовательно, сопротивление меньше. Набирать же высоту лучше при большей скорости, так как подъемная сила крыла при этом больше. Таким образом, высота и скорость ‑ противоречивые цели.  Рис. 1.2. Расход горючего при наборе высоты и скорости  Пример 1.2. Пусть скорость может увеличиваться пятью шагами, а высота - тремя (рис.1.2). На горизонтальных линиях рисунка укажем затраты горючего на увеличение скорости, а на вертикальных - затраты горючего на набор высоты. Переход от начального состояния  к конечному состоянию  можно сделать многими путями. Нужно выбрать такой путь, которому соответствует минимальный расход топлива. Процесс перехода состоит из 8 шагов: 5 по горизонтали и 3 по вертикали. Рассмотрим последний, 8-й шаг. В положение можно перейти из двух узлов  и  (рис. 1.2). Если 8-й шаг будет из , то затраты составят 7, а если из , то 11. Эти значения запишем в кружках и стрелками покажем направления движения из узлов.Предпоследний, 7-й шаг может выполниться из трех узлов  (рис. 1.4). В кружках поместим минимальные затраты при переходе из каждого из узлов. Существует единственный вариант перехода из узлов  и  в узел . Для узла  есть два варианта, поэтому выбираем 7-й шаг так, чтобы вместе с 8-м шагом получился минимальный расход топлива. Путь из через  потребует затрат в количестве  , а через :  . Оптимальным вариантом перехода из в  оказывается путь через
То же самое проделаем со всеми узлами. Результат представлен на рис.1.5. Когда дойдем до узла , становится понятно, что минимальный расход топлива составит 70 и ясен оптимальный путь из в. На рис. 1.5 оптимальный путь отмечен двойными кружами.Если же непосредственно двигаться из в , выбирая при каждом шаге минимальный расход, получили бы  .Итак, решение задачи оптимизации методом динамического программирования состоит из двух этапов. На первом этапе процесс рассматривается от его конца к началу, и строятся условные оптимальные управления. На втором этапе процесс рассматривается от начала к концу и ищется безусловное оптимальное управление   Рис.1.5. Оптимальное решение |
