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

Балтийский государственный технический университет БГТУ «ВОЕНМЕХ» им.Д.Ф.Устинова Методы оптимизации и модели в экономике Динамическое программирование Задача об одновременном наборе вы соты и скорости летательного аппарата Ст.преподаватель кафедры Р6 Соловьева Наталия Леонидовна Динамическое программирование Задача Летательны й аппарат движется со скоростью v0 на вы соте h0 и должен разогнаться до скорости vn и подняться на вы соту hn. Считается известны м расход горю чего для набора вы соты и скорости в каждой точке пространства*. Необходимо определить оптимальны й режим набора вы соты и скорости с минимальны ми расходами топлива. * Для расчета расхода горю чего пространство разделено на сектора, величина которы х кратна режимам набора вы соты и скорости, для которы х возможно определить расход горю чего. Поэтому трасса следования летательного аппарата может бы ть Динамическое программирование Динамическое программирование Для решения задачи можно комбинаторно рассмотреть все возможные варианты прохождения сетки, т.е. все возможные варианты маршрутов летательного аппарата, подсчитывая для каждого варианта расход горючего. Далее выбрать маршрут с наименьшими расходами горючего. Однако при увеличении ячеек сетки, задача становится все более трудоемкой и практически неосуществимой. Если считать, что n раз летательный аппарат должен набрать высоту и m раз – скорость, то количество маршрутов будет равно Динамическое программирование Динамическое программирование Решение задачи разобьем на этапы: 1 этап Условная оптимизация 2 этап Безусловная оптимизация 3 этап Запись оптимального решения Динамическое программирование На этапе условной оптимизации задача разбивается на шаги. Выбор шага зависит только от условий задачи. На каждом шаге определяется набор шаговы х управлений и изменение состояния системы под влиянием выбранного оптимального управления на каждом шаге. Условную оптимизацию начинают с (n+m)-1 шага, определяя оптимум для каждого конкретного шага. А заканчивают на первом шаге. За счет этого на первом шаге сразу получаем значение opt состояния системы или оптимальный выигрыш всей задачи. На этапе безусловной оптимизации определяют оптимальное управление всей системы в целом. Динамическое программирование Шагом разбиения может служить количество изменений состояния летательного аппарата от точки А(v 0, h 0) до точки В(v n, h n), т.е. изменение либо скорости, либо высоты летательного аппарата. Т.о. можно разбить задачу на n+m шагов. При этом шаговым управлением можно считать либо набор высоты, либо набор скорости. Динамическое программирование Динамическое программирование 48 40 23 13 51 41 33 22 12 60 49 40 32 23 70 58 49 39 35 Динамическое программирование В результате безусловной оптимизации было определено три альтернативных режима набора высоты и скорости летательного аппарата от начальных значений (v 0, h 0) до (v n, h n ), с минимальными затратами горючего. При этом оптимальный расход горючего составил: 70 ед. Режимы : 1 режим: ск, в, ск, ск, ск, в, в 2 режим: ск, в, в, ск, ск, ск, в 3 режим: ск, в, в, ск, в, ск, ск Можно убедиться просты м сложением, что для каждого режима расход горю чего составит 70 единиц Динамическое программирование 1 режим: ск, в, ск, ск, ск, в, в 12 + 9 + 9 + 8 + 9 + 11 + 12 = 70 единиц 2 режим: ск, в, в, ск, ск, ск, в 12 + 9 + 8 + 8 + 11 + 10 + 12 = 70 единиц 3 режим: ск, в, в, ск, в, ск, ск 12 + 9 + 8 + 8 + 10 + 10 + 13 = 70 единиц Динамическое программирование Предположим, что выбор на каждом шаге более широкий:  выбор в трех направлениях: либо на единицу сетки вверх, либо по диагонали на половину единицы, либо на единицу сетки вправо; либо имеем чрезвычайно много управлений («роза управлений») В этих случаях задача усложняется (перестает быть двумерной), но принцип решения остается прежним. 13