XV Международная студенческая научная конференция Студенческий научный форум - 2023

Само понятие «динамическое программирование» впервые былоиспользовано в 1940-х годах Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения ряда предшествующих ей задач. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

Термин «программирование» в словосочетании «динамическое программирование» к «традиционному» программированию (написанию программного кода) почти никакого отношения не имеет, это скорее составление программы некоторых действий по решению задачи. Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, составление расписания событий на выставке это некоторая программа действий. Программа в данном случае понимается как последовательность событий, ведущих к результату.

Динамическое программирование. Основные понятия.

Динамическое программирование (ДП)  в  теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи, которые связаны между собой. Самым простым примером будут числа Фибоначчи — чтобы вычислить некоторое число в этой последовательности, нам нужно сперва вычислить третье число, сложив первые два, затем четвёртое таким же образом на основе второго и третьего, и так далее.

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

Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

Решение задачи динамическим программированием должно содержать следующее:

Зависимость элементов динамики друг от друга. Такая зависимость может быть прямо дана в условии (так часто бывает, если это задача на числовые последовательности). В противном случае вы можете попытаться узнать какой-то известный числовой ряд (вроде тех же чисел Фибоначчи), вычислив первые несколько значений вручную.

Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям (как в случае с Фибоначчи — заранее определены первые два члена), либо к задаче, решаемой элементарно.

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

Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.
Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.

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

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

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

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

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

В основу метода динамического программирования положен принцип оптимальности, сформулированный в 1957 г. американским математиком Ричардом Беллманом: «Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальные состояние и решение в начальный момент времени, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения».

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

Рассматривается следующая общая задача. Имеется некоторая физическая система, в которой происходит какой-то процесс, состоящий из n шагов. Эффективность процесса характеризуется некоторым показателем W, который называют выигрышем. Пусть общий выигрыш W за все n шагов процесса складывается из выигрышей на отдельных шагах

             (1)

где w_i — выигрыш на i-м шаге. Если W обладает таким свойством, то его называют аддитивным критерием.

Процесс, о котором идет речь, представляет собой управляемый процесс, т.е. имеется возможность выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге. Это решение называется шаговым управлением. Совокупность всех шаговых управлений представляет собой управление процессом в целом. Обозначим его буквой U, а шаговые управления — буквами  . Тогда

Шаговые управления  в общем случае не числа, а, как правило, векторы, функции и т.п.

В модели динамического программирования процесс на каждом шаге находится в одном из состояний s множества состояний S. Считается, что всякому состоянию сопоставлены некоторые шаговые управления. Эти управления таковы, что управление, выбранное в данном состоянии при любой предыстории процесса, определяет полностью следующее состояние процесса. Обычно выделены два особых состояния: s₀ — начальное и s_w — конечное.

Итак, пусть каждому состоянию  поставлено множество допустимых шаговых управлений  , и каждому шаговому управлению  , соответствует   — состояние, в которое процесс попадает из s_i в результате использования шагового управления u. Пусть процесс находится в начальном состоянии s₀. Выбор  переводит процесс в состояние s₁ = σ(s₀,u₁), выбор   — в состояние s₂ = σ(s₁,u₂) и т.д. В результате получается траектория процесса, которая состоит из последовательности пар

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

             (2)

             (3)

конечны и U_s для различных s не пересекаются.

В общем виде задача динамического программирования формулируется следующим образом: найти такую траекторию процесса, при которой выигрыш (1)будет максимальным.

То управление, при котором достигается максимальный выигрыш, называется оптимальным управлением. Оно состоит из совокупности шаговых управлений

             (4)

Тот максимальный выигрыш, который достигается при этом управлении обозначим W_max:

W_max = max_U{W(u)}.             (5)

Рассмотрим на примере задачи о рюкзаке, что понимается под шагом, состоянием, управлением и выигрышем.

Загрузку рюкзака можно представить себе как процесс, состоящий из n шагов. На каждом шаге требуется ответить на вопрос: взять данный предмет в рюкзак, или нет? Таким образом, шаг процесса — присваивание переменной x_i значения 1 или 0.

Теперь определим состояния. Очевидно, что текущее состояние процесса характеризует остаточная грузоподъёмность рюкзака — вес, который остался в нашем распоряжении до конца (до полной укладки рюкзака). Следовательно, под состоянием перед i-м шагом понимается величина

             (6)

при этом s₀ является начальным состоянием, которому соответствует величина b — исходная грузоподъемность рюкзака.

Управление на i-м шаге означает присваивание двоичной переменной x_i значения 0 или 1. Значит, на каждом шаге имеем всего два управления. Причем допустимость управления u_i, устанавливающего x_i = 1, определяется условием

             (7)

Далее везде вместо переменных  будем использовать соответствующие управления  . Тогда формулы (6), (7) примут следующий вид:

             (8)

             (9)

Шаговый выигрыш можно определить как  . Поэтому

             (10)

Требуется найти оптимальное управление  , при котором величина выигрыша (10) обращается в максимум.

Пример решения задачи методом динамического программирования.

Задание. Инвестор выделяет средства в размере 5 тыс. ден. ед., которые должны быть распределены между тремя предприятиями.

Требуется, используя принцип оптимальности Беллмана, построить план распределения инвестиций между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств x тыс. ден. ед. приносит прибыль p;(x) тыс. ден. ед. (i=1, 2 и 3) по следующим данным:

 

Инвестирование средств (тыс. ден. ед.)	Прибыль (тыс. ден. ед.)
x	pi(x)	p2 (x)	p3(x)
1	3,22	3,33	4,27
2	3,57	4,87	7,64
3	4,12	5,26	10,25
4	4	7,34	15,93
5	4,85	9,49	16,12

Решение. Составим математическую модель задачи.

Число шагов равно 3.

Пусть s - количество средств, имеющихся в наличии перед данным шагом, и характеризующих состояние системы на каждом шаге.

Управление на i-ом шаге (i=1,2,3) выберем x_i - количество средств, инвестируемых в i- ое предприятие.

Выигрыш p_i(x_i) на i-ом шаге - это прибыль, которую приносит i-ое предприятие при инвестировании в него средств xi. Если через выигрыш в целом обозначить общую прибыль W, то W=p₁(x₁)+ p₂(x₂)+ p₃(x₃).

Если в наличии имеются средства в количестве s тыс. ден. ед. и в i-ое предприятие инвестируется x тыс. ден. ед, то для дальнейшего инвестирования остается (s-x) тыс. ден. ед. Таким образом, если на i-ом шаге система находилась в состоянии s и выбрано управление x, то на (i+1)-ом шаге система будет находится в состоянии (s-x), и, следовательно, функция перехода в новое состояние имеет вид: f_i(s, x) = s-x.

На последнем (i=3) шаге оптимальное управление соответствует количеству средств, имеющихся в наличии, а выигрыш равен доходу, приносимым последним предприятием: x₃(s)=s, W₃(s)=p₃(s).

Согласно принципу оптимальности Беллмана, управление на каждом шаге нужно выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге. Основное функциональное уравнение примет вид

W₂ (s) = max{p₂ (x) + W₃(s - x)}

x< s

Проведем пошаговую оптимизацию, по результатам которой заполним таблицу.

 

s	i=3		i=2		i=1
	x3(s)	W3(s)	x2(s)	W2(s)	xi(s)	Wi(s)
1	1	4,27	0	4,27
2	2	7,64	0	7,64
3	3	10,25	1	10,97
4	4	15,93	0	15,93
5	5	16,12	1	19,26	0	19,26

 

В первой колонке таблицы записываются возможные состояния системы, в верхней строке - номера шагов с оптимальным управлением и выигрышем на каждом шаге, начиная с последнего. Так как для последнего шага i=3 функциональное уравнение имеет вид x₃(s)=s, W3(s)=p3(s), то две колонки таблицы, соответствующие i=3, заполняются автоматически по таблице исходных данных.

 

На шаге i=2 основное функциональное уравнение имеет вид

W₂ (s) = max{p₂ (x) + W₃(s - x)}

x≤s

Поэтому для проведения оптимизации на этом шаге заполним таблицу для различных состояний s при шаге i=3.

 

s	x	s-x	p2(x)	W3(s-x)	p2(x)+W3(s-x)	W2(s)
1	0	1	0	4,27	4,27	4,27
	1	0	3,33	0	3,33
2	0	2	0	7,64	7,64	7,64
	1	1	3,33	4,27	7,6
	2	0	4,87	0	4,87
3	0	3	0	10,25	10,25	10,97
	1	2	3,33	7,64	10,97
	2	1	4,87	4,27	9,14
	3	0	5,26	0	5,26
4	0	4	0	15,93	15,93	15,93
	1	3	3,33	10,25	13,58
	2	2	4,87	7,64	12,51
	3	1	5,26	4,27	9,53
	4	0	7,34	0	7,34
5	0	5	0	16,12	16,12	19,26
	1	4	3,33	15,93	19,26
	2	3	4,87	10,25	15,12
	3	2	5,26	7,64	12,9
	4	1	7,34	4,27	11,61
	5	0	9,49	0	9,49

На шаге i=1 основное функциональное уравнение имеет вид

W_x( s) = max{ p_x( x) + W₂( s - x)}

x ≤s

а состояние системы перед первым шагом s=5, поэтому для проведения оптимизации на этом шаге заполним таблицу.

s	x	s-x	pi(x)	W2(s-x)	pi(x)+W2(s-x)	Wi(s)
5	0	5	0	19,26	19,26	19,26
	1	4	3,22	15,93	19,15
	2	3	3,57	10,97	14,54
	3	2	4,12	7,64	11,76
	4	1	4	4,27	8,27
	5	0	4,85	0	4,85

Видно, что наибольшее значение выигрыша составляет 19,26. При этом оптимальное управление на первом шаге составляет x₁(s₁)=0 (s₁=5), на втором шаге x₂(s₂) =1 (s₂=s₁-x₁=5) и на третьем шаге x₃(s₃) =4 (s₃=s₂-x₂=4).

Это означает, что (0, 1, 4) - оптимальный план распределения инвестиций между предприятиями.

Таким образом, для получения наибольшей общей прибыли в размере 19,26 тыс. ден. ед., необходимо вложить 1 тыс. ден. ед. во второе предприятие и 4 тыс. ден. ед. в третье предприятие

Код для цитирования: Скопировать