Динамическое программирование: его преимущества и недостатки
Динамическое программирование – это раздел математики, который занимается методами решения многошаговых задач по оптимизации. Данный инструмент вычислений сегодня буквально незаменим во многих сферах человеческой деятельности.
Особенно он важен, когда требуется срочная оценка данных, поступивших из разных источников и значительно отличающихся как по объему, так и характеру. В подобных ситуациях динамическое программирование сложно чем-либо заменить.
Что такое динамическое программирование
Своим возникновением и утверждением в научной среде термин «динамическое программирование» обязан Ричарду Беллману, который впервые применил его в 1940 году для задач, решаемых поэтапно с использованием результатов каждого вычисления на следующем шаге. Впоследствии Беллман усовершенствовал это понятие, предложив общепринятую в настоящее время формулировку.
Сама история возникновения данного термина довольно любопытная. По словам Беллмана, когда он стал придумывать название, перед ним возникла проблема. Дело в том, что чиновник, осуществлявший над ним контроль, откровенно ненавидел математические термины и не пытался в них вникать. Весь коллектив постоянно приходил в ужас, сталкиваясь с насмешками и непониманием со стороны руководителя.
Как следствие, Беллману понадобилось немало времени, чтобы выбрать подходящее название. Вместо слова «планирование», которые вызывало ассоциации с тем, что в это время происходило в Советском Союзе, он предложил вариант «программирование».
А слово «динамическое» оказалось удачным не только потому, что передавало суть методики, но и потому, что оно было понятным и его сложно было подменить чем-либо другим. Для Беллмана было важно, чтобы его термин нельзя было неправильно интерпретировать, исказить смысл. Отсюда и возникло понятие «динамическое программирование».
Далее рассмотрим саму суть динамического программирования. Оно заключается в том, что при решении задачи та разбивается на несколько более мелких подзадач, непосредственно зависящих друг от друга.
«Более мелкие подзадачи» – это то же самое, что «более простые». Другими словами, это задачи, входные данные для которых имеют меньший размер. Входными данными могут быть число, массив, совокупность настраиваемых параметров и т.д. Как пример, можно привести последовательность чисел Фибоначчи, N-й член которой обозначается как Ф(N).
Чтобы найти пятое число Фибоначчи Ф(5), сначала нужно получить третье Ф(3) и четвертое Ф(4) числа в этой последовательности, то есть необходимо решить те самые мелкие подзадачи.
Задачи динамического программирования
Методы динамического программирования применяются при решении оптимизационных задач, в которых целевая функция или ограничения, или же и первое, и второе одновременно характеризуются нелинейными зависимостями.
- Задача распределения инвестиций. Распределении инвестиций между предприятиями П1, П2. Пn. Инвестируемая сумма E усл. ден. ед.
- Задача распределения ресурсов. Планируется работа двух предприятий на n лет. Начальные ресурсы равны s0 .
- Метод прогонки.
- Задача замены оборудования.
- Складская задача: составить оптимальную программу выпуска продукции X , которая минимизирует суммарные издержки предприятия.
- Задача Джонсона.
- Задача о рюкзаке (решение задачи о загрузке транспортного средства).
- Динамическая оптимизация в планировании работ
В условиях задачи производственного планирования найти оптимальные сроки начала строительства каждого из объектов так, чтобы суммарный срок строительства всех объектов был бы минимальным.
Объекты / Стадии №1 №2 №3 №4 A1 2 5 4 3 A2 1 4 2 6 A3 3 4 3 4
Задача распределения инвестиций
В задачах данного типа заданы сумма инвестиций (или сумма для распределения) и таблица планируемой прибыли. Если сумма для распределения явно не задана, то ее можно найти из таблицы — она равна максимальному значению xi (последняя строчка таблицы).
Таблицы могут иметь разный вид.
Таблица 1 — Первый вариант таблицы исходных данных
| x | f1(x) | f2(x) | f3(x) |
| 1 | 6.3 | 4 | 5 |
| 2 | 5.2 | 6 | 7 |
| 3 | 4.3 | 4.6 | 7.8 |
| 4 | 5 | 6 | 3 |
| 5* | 7 | 6.3 | 8.2 |
* — здесь значение 5 — максимальное значение (сумма для распределения).
Таблица 2 — Второй вариант таблицы исходных данных
| x | 0 | 10 | 20 | 30 | 40 |
| f1(x) | 0 | 4 | 5 | 7 | 8 |
| f2(x) | 0 | 3 | 3 | 4 | 6 |
| f3(x) | 0 | 4 | 4 | 5 | 6 |
Пример задачи.
Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f1(х), а доход от y единиц средств, вложенных во второе предприятие, равен f2(y). Остаток средств к концу года составляет g1(x) для первого предприятия и g2(y) для второго предприятия. Задачу решить методом динамического программирования.
При вводе данных первую нулевую строку можно не заполнять.
В сервисе Задача распределения инвестиций используется метод обратной прогонки.
Метод прогонки
Данная задача соответствует задаче распределения инвестиций. Разница состоит в оформлении результатов полученного решения и применения метода прямой прогонки.
В сервисе Метод прогонки необходимо также выбрать метод решения: процедура прямой или обратной прогонки.
Задача замены оборудования
Цель решения — определить на каких шагах алгоритма (в какие годы) необходимо заменить оборудование. Для этого вводятся Период эксплуатации (в годах) и Стоимость нового оборудования. После этого необходимо заполнить таблицу дохода r(t) и остаточной стоимости S(t).
Задача замены оборудования
Планирование производственной линии
Задача последовательной обработки на двух машинах N различных деталей, если известно время Ai и Bi обработки i -й детали на соответствующих машинах. Требуется найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Задача Джонсона