Общие сведения о динамическом программировании
Динамическое программирование – это способ решения некоторых сложных задач, в основном из области методов оптимизации и комбинаторики, путём их разбиения на несколько более простых подзадач с последующим объединением решений подзадач в общее решение основной задачи.
Термин “программирование” в данном определении означает составление оптимального алгоритма решения задачи, а не непосредственно написание кода программы.
При составлении алгоритма решения задачи важно учитывать следующее свойство – решение подзадач должно выполняться только один раз, а потом это решение должно использоваться для решения подзадач следующего уровня. Такой подход позволяет существенно уменьшить вычислительные ресурсы и время вычислений при решении задачи.
Методом динамического программирования эффективно решать задачи на нахождение максимумов и минимумов. К ним относятся задачи, связанные с определением кратчайшего пути, оптимальным вложением средств или загрузкой оборудования на заводе.
Понятие динамического программирования ввёл американский математик Ричард Беллман для решения задач из таких разделов математики как комбинаторика, методы оптимизации, исследование операций, вариационное исчисление и методы аппроксимации.
Именно в этих областях математики большинство задач обладают структурой перекрывающихся подзадач с меньшей сложностью. Также про такие задачи можно сказать, что они обладают свойством рекурсивности, то есть решение главной целевой задачи можно выполнить обращением к ней же самой, но при других начальных условиях.
Например, задачей обладающей свойством рекурсивности является задача вычисления ряда чисел Фибоначчи, где каждое следующее число ряда является суммой двух предыдущих, а начальные условия, то есть два первых числа 0 и 1 известны. Формула для вычисления n-го члена ряда известна: $Fib(n) = Fib (n-1) + Fib (n-2)$. Для решения этой задачи методом динамического программирования надо начинать решение с наименьших слагаемых ряда и самое главное – хранить их в памяти для предотвращения повторных вычислений.
Важным моментом является использование выполненного решения для малой подзадачи при решении большей подзадачи на каждом очередном шаге алгоритма.
В общем случае, алгоритм решения задачи методом динамического программирования состоит из следующих шагов:
- разбиение задачи на подзадачи;
- составление рекуррентного отношения;
- определение порядка выполнения подзадач;
- реализация рекуррентного отношения, решение подзадач по порядку с сохранением только нужных результатов.
Пример решения задачи о распределении средств
Методом динамического программирования можно решить и задачу о распределении средств между предприятиями. Суть задачи состоит в том, сколько средств надо вложить в несколько предприятий для получения наибольшей прибыли, то есть это тоже задача о нахождении максимума.
Например, имеется известное количество средств, которые надо оптимальным образом распределить между группой предприятий, чтобы за год получить максимальную сумму прибыли.
При этом выполняются следующие условия:
- известна прибыль каждого предприятия на единицу вложенных средств, и она не зависит от суммы средств, вложенных в другие предприятия;
- суммарная прибыль равна сумме прибылей от каждого предприятия.
Теперь рассмотрим решение задачи о распределении средств на конкретном примере, применяя метод динамического программирования.
Задача. Пусть планируется распределение начальной суммы $x_0$ = 400 млн. р. Между четырьмя предприятиями некоторого объединения. Будем считать, что средства выделяются только в размерах кратных 80 млн. р. Функции прироста продукции от вложенных средств на каждом предприятии заданы в Таблице 1. Требуется распределить вложения между предприятиями таким образом, чтобы общий прирост продукции (в млн. р.) был максимальным.
Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ
Решение. Будем решать задачу на основе функционального уравнения Беллмана:
$F_n(x_0) = max(f_n(x)+F_{n-1}(x_0-x))$, где $ max $ вычисляется по всем $x: 0\leq x\leq x_0;\quad n=1,\dots,4\quad$ и $\quad F_1(x)=f_1(x)$.
Посмотрим, как эта формула будет работать на каждом шаге алгоритма.
Шаг первый. Вычисляем значения функции $F_2(x_0)$ по формуле:
$F_2(x_0) = max(f_2(x)+F_1(x_0-x))$, где $0\leq x\leq x_0$.
Таким образом, сначала решается задача только для двух предприятий.
После проведения вычислений по указанной формуле записываем в Таблицу 2 все полученные результаты:
Рисунок 2. Таблица. Автор24 — интернет-биржа студенческих работ
Здесь через $x_2$ и $x_1 = x_0 - x_2$ обозначены количества средств, вложенных во второе и первое предприятия, соответственно.
Таблица 2 сформирована так, что на её левом и верхнем крае задаются исходные данные из Таблицы 1, а центральные ячейки заполняются следующим образом: в них записывается сумма значений из ячеек шапки (которые находятся во 2 столбце и 2 строке таблицы), на пересечении которых оказывается заполняемая ячейка.
Заметим, что правый нижний угол в центре таблицы остаётся пустым, так как этим ячейкам отвечает сумма $x_1+x_2>x_0$, т.е. недопустимое по условию задачи значение, превышающее начальную сумму $x_0 = 400$.
Далее в таблице заполняется столбец значений функции $F_2$. Они получаются путём выбора максимального значения по каждой из диагоналей заполненной на этом шаге части таблицы. Именно такой набор значений (расположенных по диагонали) отвечает той ситуации, когда $x_1+x_2=x_0$ (это соотношение уже было указано выше), где для каждой следующей строки выбирается последовательно, $x_0=0$, $x_0=80$, ..., $x_0=400$.
Шаг второй. Теперь распределим вложения между тремя предприятиями.
Для этого будем использовать формулу Беллмана для нахождения значений функции $F_3(x_0)$ при значениях $x_0\leq400$ и кратных числу $80$ (по условию задачи).
При формировании новой Таблицы 3 будем использовать значения функции $F_2$, полученные на предыдущем шаге (записаны в предпоследнем столбце Таблицы 2), а также значения функции прироста продукции для третьего предприятия $f_3$, указанные в Таблице 1. Действуя по аналогии с первым шагом, записываем в новую таблицу полученные на этом шаге результаты, учитывая, что здесь $x0 - x3 = x1 + x2$.
Рисунок 3. Таблица. Автор24 — интернет-биржа студенческих работ
Шаг третий. Продолжая процесс алгоритма, на основе данных из предыдущих таблиц вычисляем значения функции $F_4(x_0)$.
В итоге получаем Таблицу 4, где в крайнем правом столбце записаны всевозможные оптимальные комбинации распределения средств между четырьмя предприятиями:
Рисунок 4. Таблица. Автор24 — интернет-биржа студенческих работ
Таким образом, получили, что наибольший прирост при вложении 400 тыс. рублей составит 74 тыс. р. (соответствует значению функции $F_4(400)$).
При этом возможно два варианта инвестирования (они записаны в правой нижней ячейке итоговой Таблицы 4), а именно:
- Вложить в третье предприятие 240 тыс. р и в четвёртое – 160 тыс. р.
- Вложить во второе предприятие 80 тыс. р, а в третье и четвёртое – по 160 тыс. р.
