Динамическое программирование. Задача о распределении средств
Динамическое программирование – это способ решения некоторых сложных задач, в основном из области методов оптимизации и комбинаторики, путём их разбиения на несколько более простых подзадач с последующим объединением решений подзадач в общее решение основной задачи.
Термин “программирование” в данном определении означает составление оптимального алгоритма решения задачи, а не непосредственно написание кода программы.
При составлении алгоритма решения задачи важно учитывать следующее свойство – решение подзадач должно выполняться только один раз, а потом это решение должно использоваться для решения подзадач следующего уровня. Такой подход позволяет существенно уменьшить вычислительные ресурсы и время вычислений при решении задачи.
Методом динамического программирования эффективно решать задачи на нахождение максимумов и минимумов. К ним относятся задачи, связанные с определением кратчайшего пути, оптимальным вложением средств или загрузкой оборудования на заводе.
Понятие динамического программирования ввёл американский математик Ричард Беллман для решения задач из таких разделов математики как комбинаторика, методы оптимизации, исследование операций, вариационное исчисление и методы аппроксимации.
Именно в этих областях математики большинство задач обладают структурой перекрывающихся подзадач с меньшей сложностью. Также про такие задачи можно сказать, что они обладают свойством рекурсивности, то есть решение главной целевой задачи можно выполнить обращением к ней же самой, но при других начальных условиях.
Например, задачей обладающей свойством рекурсивности является задача вычисления ряда чисел Фибоначчи, где каждое следующее число ряда является суммой двух предыдущих, а начальные условия, то есть два первых числа 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_(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 тыс. р.
19. Динамическое программирование. Разбиение задачи на подзадачи, принцип оптимальности. Задача о маршруте из верхнего угла таблицы в нижний
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
В типичном случае динамическое программирование применяется к задачам оптимизации, которые не решаются простым перебором (из-за временных ограничений или слишком большого объема необходимой памяти) и жадными алгоритмами (из-за того, что они не дают оптимального результата), а более простой путь решения если и существует, то его нахождение неочевидно. У таких задач может быть много решений и в общем случае это определяет некий показатель (назовем его качеством решения), и требуется выбрать оптимальное, при котором данный показатель становится либо минимумом либо максимумом (или еще чем-то 🙂 — в зависимости от условия задачи). По своему принципу динамическое программирование напоминает метод разделяй и властвуй задача делится на подзадачи, которые либо являются очевидными, либо сводятся к своим подзадачам и т.д. Но есть и некоторые отличия например, таких подзадач обычно относительно немного, что позволяет решить каждую только один раз, а результат (то самое качество) занести в некий массив такой подход называется memoization (не бейте меня, это не я такое придумал! :))). Небольшое кол-во подзадач, многие из которых приходится решать много раз называется перекрытием подзадач и является характерным признаком динамического программирования. Вторым характерным признаком излагаемого метода является оптимальность для подзадач. Говорят, что задача обладает таким свойством, если оптимальное решение задачи содержит оптимальные решения ее подзадач. Общий рецепт построения алгоритмов по принципу динамического программирования следующий:
- Хорошо понять условие 🙂
- Найти такое разбиение задачи на две или более подзадач, чтобы оптимальное решение задачи содержало оптимальное решение всех подзадач, которые в нее входят.
- Написать рекуррентное соотношение (если мы разбиваем задачу на подзадачи, значит, можем выразить качество решения задачи либо через ее подзадачи, либо элементарным образом)
- Вычислить оптимальное значение параметра для всей задачи. Тут возможно два варианта если задачу решаем рекурсивно, значит процедура делит заданную ей задачу на подзадачи (предварительно выяснив, не является ли задача тривиальной и проверив, не решалась ли она ранее тогда нужно лишь взять уже готовое решение из соответствующего массива) и получив решение ставит флаг, что эта подзадача уже решена. Такое решение называется решением сверху вниз т.е. берем глобальную задачу, потом решаем только необходимые для нее подзадачи. Если же рекурсия невозможна по техническим или еще каким-нить причинам (может просто не любит какой программер рекурсию :)), то применяется такой подход: решаются сначала элементарные подзадачи, потом только те, которые требуют результатов уже решенных подзадач и т. д., пока не будет решена общая задача. Такой метод называется решением снизу вверх в большинстве случаев он оказывается быстрее, но менее понятным и простым, хотя есть и исключения
- Если необходимо получить не только значение качества оптимального решения, но и найти само решение, то на шаге 3 нужно также запоминать некоторую дополнительную информацию о ходе решения решение каждой подзадачи. Этот шаг иногда еще называют обратным ходом
Var fc: array [1..Nmax, 1.. Kmax] of integer; //перед вызовом f, f c-1;