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

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

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

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

Вместе с тем динамическому программированию свойственны и недостатки.

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

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

Постановку задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между несколькими предприятиями таким образом, чтобы результат от инвестирования был б максимальным. В результате управления инвестициями система последовательно переводится из начального состояния S₀ в конечное S_n. Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных – переменную состояния системы S_k и переменную управления x_k Переменная S_k определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге.

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

Пример. На развитие трех предприятий g₁, g₂, g₃ выделено 5 млн. руб. Известна эффективность капитальных вложений в каждое предприятие, заданная значением нелинейной функции g_i(x_i), представленной в таблице. Необходимо распределить выделенные средства между предприятиями таким образом, чтобы получить максимальный суммарный доход. Для упрощения решения задачи будем распределять средства в целых числах (0, 1, 2, 3, 4, 5 млн. руб.).

Решение.

Решение задачи проводится в два этапа:

I. Условная оптимизация.

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

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

Аналогично с ячейкой, расположенной на пересечении второй строки и второго столбца. От направления 1 млн. руб. на третье предприятие получим доход в объеме 2,8 млн. руб., следовательно запишем это значение в данную ячейку. Аналогично заполняются остальные ячейки.

Столбец F₃(c₃) заполняется максимальным значением по соответствующей строке.

Столбец x₃^* - количество денег, соответствующих максимальному значению по данной строке (то есть значение столбца, в котором находится максимальное значение строки).

с3	x3	0	1	2	3	4	5	F3(c3)	x3*
0		0	-	-	-	-	-	0	0
1		-	2,8	-	-	-	-	2,8	1
2		-	-	5,4	-	-	-	5,4	2
3		-	-	-	6,4	-	-	6,4	3
4		-	-	-	-	6,6	-	6,6	4
5		-	-	-	-	-	6,9	6,9	5

2-ой шаг. На данном шаге будем распределять средства между третьим и вторым предприятием и заполним аналогичную таблицу.

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

Рассмотрим заполнение строки, соответствующей наличию 1 млн. руб. Заполняя ячейку первого столбца (которому соответствует 0), мы рассуждаем, что на второе предприятие из имеющегося 1 млн. руб. направляется 0 млн. руб., что дает нам 0 млн. руб. дохода, следовательно, 1 млн. руб. направляется на третье предприятие, что дает доход в размере 2,8 млн. руб. (смотрим в первую таблицу в предпоследний столбец в строку, соответствующую 1 млн. руб.). Получаем 0+2,8.

Переходим в следующий столбец. Имеется 1 млн. руб. и на второе предприятие отправляется 1 млн. руб. Значит, на третье предприятие не отправляется ничего, и доход мы получим от вложения 1 млн. руб. во второе предприятие в объеме 2 млн. руб. То есть суммарно получим доход 2+0. Далее в этой строке заполняем ячейки прочерками, так как средств в наличии меньше, чем направляется.

Заполним строку, соответствующую 2 млн. руб. Заполняя ячейку с 0 значением распределения средств на второй предприятие. Следовательно, доход от второго предприятия будет равен 0, и 2 млн. руб. будут направлены на третье предприятие с доходом 5,4 млн. руб. суммарный доход получится 0+5,4.

Переходим в столбец, соответствующий 1 млн. руб., направляемому на второе предприятие. Имеется 2 млн. руб., на второе предприятие направляем 1 млн. руб. с доходом 2 млн. руб. Остается 1 млн. руб., который идет на третье предприятие с доходом 2,8 млн. руб. Суммарно получим доход 2+2,8.

Переходим в столбец, соответствующий 2 млн. руб., направляемым на второе предприятие. Имеется 2 млн. руб., на второе предприятие направляем 2 млн. руб. с доходом 3,2 млн. руб. Остается 0 млн. руб., который идет на третье предприятие с доходом 0 млн. руб. Суммарно получим доход 3,2+0. Далее в этой строке заполняем ячейки прочерками, так как средств в наличии меньше, чем направляется.

Аналогично заполняются все оставшиеся ячейки.

с2	x2	0	1	2	3	4	5	F2(c2)	x2*
0		0	-	-	-	-	-	0	0
1		0+2,8	2+0	-	-	-	-	2,8	0
2		0+5,4	2+2,8	3,2+0	-	-	-	5,4	0
3		0+6,4	2+5,4	3,2+2,8	4,8+0	-	-	7,4	1
4		0+6,6	2+6,4	3,2+5,4	4,8+2,8	6,2+0	-	8,6	2
5		0+6,9	2+6,6	3,2+6,4	4,8+5,4	6,2+2,8	6,4+0	10,2	3

Чтобы заполнить столбец F₂(c₂), в каждой строке рассчитаем полученные суммы и выделим наибольшее значение в строке. Столбец x₂^* соответствует значению столбца, в котором находится выделенная сумма.

3-ий шаг. На данном шаге будем распределять средства между первым предприятием и (вторым и третьим) предприятиями и заполним аналогичную таблицу.

Рассмотрим заполнение строки, соответствующей наличию 1 млн. руб. Заполняя ячейку первого столбца (которому соответствует 0), мы рассуждаем, что на первое предприятие из имеющегося 1 млн. руб. направляется 0 млн. руб., что дает нам 0 млн. руб. дохода, следовательно, 1 млн. руб. направляется на (второе и третье) предприятия, что дает доход в размере 2,8 млн. руб. (смотрим во вторую таблицу в предпоследний столбец в строку, соответствующую 1 млн. руб.). Получаем 0+2,8.

Переходим в следующий столбец. Имеется 1 млн. руб. и на первое предприятие отправляется 1 млн. руб. Значит, на (второе и третье) предприятие не отправляется ничего, и доход мы получим от вложения 1 млн. руб. в первое предприятие в объеме 2,2 млн. руб. То есть суммарно получим доход 2,2+0. Далее в этой строке заполняем ячейки прочерками, так как средств в наличии меньше, чем направляется.

Заполним строку, соответствующую 2 млн. руб. Заполняя ячейку с 0 значением распределения средств на первое предприятие. Следовательно, доход от вложения в первое предприятие будет равен 0, и 2 млн. руб. будут направлены на (второе и третье) предприятия с доходом 5,4 млн. руб. (смотрим во вторую таблицу в предпоследний столбец в строку, соответствующую 2 млн. руб.). Суммарный доход получится 0+5,4.

Переходим в столбец, соответствующий 1 млн. руб., направляемому на первое предприятие. Имеется 2 млн. руб., на первое предприятие направляем 1 млн. руб. с доходом 2,2 млн. руб. Остается 1 млн. руб., который идет на (второе и третье) предприятия с доходом 2,8 млн. руб. (смотрим во вторую таблицу в предпоследний столбец в строку, соответствующую 1 млн. руб.) Суммарно получим доход 2,2+2,8.

Переходим в столбец, соответствующий 2 млн. руб., направляемым на первое предприятие. Имеется 2 млн. руб., на первое предприятие направляем 2 млн. руб. с доходом 3 млн. руб. Остается 0 млн. руб., который идет на (второе и третье) предприятия с доходом 0 млн. руб. Суммарно получим доход 3+0. Далее в этой строке заполняем ячейки прочерками, так как средств в наличии меньше, чем направляется.

Аналогично заполняются все оставшиеся ячейки.

с1	x1	0	1	2	3	4	5	F1(c1)	x1*
0		0	-	-	-	-	-	0	0
1		0+2,8	2,2+0	-	-	-	-	2,8	0
2		0+5,4	2,2+2,8	3+0	-	-	-	5,4	0
3		0+7,4	2,2+5,4	3+2,8	4,1+0	-	-	7,6	1
4		0+8,6	2,2+7,4	3+5,4	4,1+2,8	5,2+0	-	9,6	1
5		0+10,2	2,2+8,6	3+7,4	4,1+5,4	5,2+2,8	5,9+0	10,8	1

Чтобы заполнить столбец F₁(c₁), в каждой строке рассчитаем полученные суммы и выделим наибольшее значение в строке. Столбец x₁^* соответствует значению столбца, в котором находится выделенная сумма.

II. Безусловная оптимизация.

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

1-ый шаг. В последней таблице максимальный доход, который можно будет получить от распределения 5 млн. руб. (с₁=5) между тремя предприятиями составляет 10,8 млн. руб. Соответствующий x₁^*=1. Это означает, что на первое предприятие следует направить 1 млн. руб.

2-ой шаг. 1 млн. руб. направлен на первое предприятие, следовательно, из 5 млн. руб. осталось 4 млн. руб. То есть с₂=с₁- x₁^*=5-1=4 млн. руб.

Смотрим во вторую таблицу в строку, соответствующую наличию 4 млн. руб. в последний столбец. Получаем, что x₂^*=2 млн. руб. То есть, на второе предприятие нужно направить 2 млн. руб.

3-ий шаг. Осталось 2 млн. руб. То есть с₃=с₂- x₂^*=4-2=2 млн. руб.

Смотрим в первую таблицу в строку, соответствующую наличию 2 млн. руб. в последний столбец. Получаем, что x₃^*=2 млн. руб. То есть, на третье предприятие нужно направить 2 млн. руб.

Проверим правильность расчетов:

F(5)=g₁(1)+g₂(2)+g₃(2)=2,2+3,2+5,4=10,8

Ответ. Оптимальный план инвестирования предприятий: на первое предприятие 1 млн. руб., на второе предприятие 2 млн. руб., на третье предприятие 2 млн. руб., что позволит получить максимальный доход в объеме 10.8 млн. руб.

Практическое занятие 10

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

2. Планируется распределение начальной суммы  млн. р. Между четырьмя предприятиями некоторого объединения. Средства выделяются только в размерах кратных  млн. р. Функции прироста продукции от вложенных средств на каждом предприятии заданы таблично. Требуется так распределить вложения между предприятиями, чтобы общий прирост продукции (в млн. р.) был максимальным.

Домашнее задание:

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