ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ЗАДАЧАХ ЛИНЕЙНОГО УПРАВЛЕНИЯ: СИНТЕЗ ИСКУССТВЕННОГО БАЗИСА И ПРИНЦИПА ОПТИМАЛЬНОСТИ БЕЛЛМАНА

АННОТАЦИЯ

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

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

Введение

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

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

1. Принцип оптимальности

Беллмана Принцип Беллмана гласит: если мы выбрали наилучшее управление, то любое его продолжение, начатое с любого шага, также будет наилучшим для состояния на этом шаге.

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

2. Как ставится задача управления с линейным уравнением.

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

3. Сочетание метода искусственного базиса и динамического программирования

3.1. Искусственные переменные.

На каждом шаге добавляем искусственные переменные. Неравенства заменяем равенствами с новыми переменными. Это даёт дополнительный критерий на шаге - минимизируем сумму этих переменных.

3.2. Новое рекуррентное соотношение.

Получаем новую функцию стоимости, теперь она состоит из трёх частей: затраты на управление, сумма оптимальных затрат до конца и штраф за искусственные переменные. Новое уравнение такое же, как раньше, только с добавленным штрафом.

  – это число, которое показывает, как сильно нас беспокоит использование искусственных переменных.

3.3. Алгоритм действий.

 Сначала идём шаг за шагом назад. Для каждого состояния решаем задачу линейного программирования с искусственным базисом. Находим наилучшие решения и уравнения. Затем переходим к следующему состоянию - применяем найденные решения для начального состояния и пересчитываем состояние на каждом шаге по уравнению динамики.

4. Пример.

 Рассмотрим задачу на два шага с заданной целевой функцией и простым уравнением перехода. Управление ограничено. Начальное состояние равно нулю, конечное тоже должно быть равно нулю. Сначала решаем задачу с искусственной переменной. Получаем правильное значение. Затем подставляем найденные значения. Получаем, что на первом шаге управление равно единице, на втором - двум, а цель равна трём.

5. Обсуждение метода.

 Этот способ может помочь в тех случаях, когда допустимое управление не видно с самого начала. Он сохраняет главное свойство динамического программирования - находит наилучшее решение для всех шагов. Каждый шаг после этого можно представить, как обычную задачу линейного программирования, для которой существуют эффективные численные методы. К недостаткам можно отнести то, что с увеличением размерности состояния сильно возрастает количество вычислений; кроме того, параметр штрафа нужно выбирать для каждой задачи отдельно.

Заключение

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

Список литературы:

1. Беллман Р. Динамическое программирование / пер. с англ. О. В. Вишняковой. - М.: Издательство иностранной литературы, 1960. - 400 с.
2. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. - М.: Наука, 1961. - 392 с.
3. Красовский Н. Н. Теория управления движением. - М.: Наука, 1968. - 476 с.
4. Васильев О. В., Срочко В. А., Дыркин В. А. Методы оптимизации и их приложения. Ч. 2. Нелинейное программирование. - Новосибирск: Наука, 1988. - 144 с.
5. Моисеев Н. Н., Котельников В. Д. Задачи оптимального управления в технике. - М.: Высшая школа, 2010. - 318 с.