Лекция 5. Динамическое программирование

 

Задача о распределении средств между предприятиями

 

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

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

Пусть  – количество ресурсов, выделенных - му предприятию ();  – функция полезности, величина дохода от использования ресурса x_i, полученного - м предприятием;  – наибольший доход, который можно получить при использовании ресурсов от первых k различных предприятий.

Сформулированную задачу можно записать в математической форме:

при ограничениях:

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

Обозначим через  количество ресурса, используемого k -м способом (), тогда для (k -1) способов остается величина ресурсов, равная (). Наибольший доход, который получается при использовании ресурса () от первых (k -1) способов, составит . Для максимизации суммарного дохода от k -го и первых (k -1) способов необходимо выбрать таким образом, чтобы выполнялись соотношения

 

       

 

Эти соотношения называются функциональными уравнениями Беллмана:

 

 

Пример решения задача о распределении средств между предприятиями

 

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

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

 

 

Выделяемые средства, млн.руб.	Прирост выпуска продукции, млн. руб.
	Предприятие № 1	Предприятие № 2	Предприятие № 3	Предприятие № 4
20	3	2	2	1
40	5	4	4	3
60	7	5	5	6
80	9	7	8	7
100	10	9	10	9

 

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

Решение будем проводить согласно рекуррентным соотношениям.

Этап 1. Инвестиции производим только первому предприятию. Тогда

f ₁(20)=3, f ₂(40)=5, f ₃(60)=7, f ₄(80)=9, f ₅(100)=10.

Этап 2. Инвестиции выделяем первому и второму предприятиям. Рекуррентное соотношение (1) примет вид:

f ₂(x)=max{ g ₂(x ₂)+ f ₁(x - x ₂)}.

Следовательно

f ₂(20)=max(3+0, 0+2)=max(3, 2)=3.

f ₂(40)=max(5+0, 3+2, 0+4)=max(5, 5, 4)=5.

f ₂(60)=max(7+0, 5+2, 3+4, 0+5)=max(7, 7, 7, 5)=7.

f ₂(80)=max(9+0, 7+2, 5+4, 3+5, 0+7)=max(9, 9, 9, 8, 7)=9.

f ₂(100)=max(10+0, 9+2, 7+4, 5+5, 3+7, 0+9)=max(10, 11, 11, 10, 10, 9)=11.

Этап 3. Финансируем второй этап и третье предприятие. В этом случае соотношение (1) принимает вид:

f ₃(x)=max{ g ₃(x ₃)+ f ₂(x - x ₃)}.

Тогда

f ₃(20)=max(3+0, 0+2)=max(3, 2)=3.

f ₃(40)=max(5+0, 3+2, 0+4)=max(5, 5, 4)=5.

f ₃(60)=max(7+0, 5+2, 3+4, 0+5)=max(7, 7, 7, 5)=7.

f ₃(80)=max(9+0, 7+2, 5+4, 3+5, 0+8)=max(9, 9, 9, 8, 8)=9.

f ₃(100)=max(11+0, 9+2, 7+4, 5+5, 3+8, 0+10)=max(11, 11, 11, 10, 11, 10)=11.

Этап 4. Инвестиции в объеме 100 млн.руб. распределяем между третьим этапом и четвертым предприятием. Соотношение (1) принимает вид:

f ₄(x)=max{ g ₄(x ₄)+ f ₃(x - x ₄)}.

Следовательно

f ₄(20)=max(3+0, 0+1)=max(3, 1)=3.

f ₄(40)=max(5+0, 3+1, 0+3)=max(5, 4, 3)=5.

f ₄(60)=max(7+0, 5+1, 3+3, 0+6)=max(7, 6, 6, 6)=7.

f ₄(80)=max(9+0, 7+1, 5+3, 3+6, 0+7)=max(9, 8, 8, 9, 7)=9.

f ₄(100)=max(11+0, 9+1, 7+3, 5+6, 3+7, 0+9)=max(11, 10, 10, 11, 10, 9)=11.

Максимальный прирост выпуска продукции в 11 млн.руб. получен на четвертом этапе как, например, 5+6, т.е. 6 млн.руб. соответствуют выделению 60 млн.руб. четвертому предприятию. Согласно третьему этапу 5 млн.руб. получено как 3+2, т.е. 2 млн.руб. соответствует выделению 20 млн.руб. третьему предприятию. Согласно второму этапу 3 млн.руб. получено как 3+0, те. 3 млн.руб. соответствует выделению 20 млн.руб. первому предприятию.

Таким образом, инвестиции в объеме 100 млн. руб. целесообразно выделить четвертому предприятию в объеме 60 млн.руб. и первому и второму предприятиям в объеме по 20 млн.руб. каждому, при этом прирост продукции будет максимальным и составит 11 млн.руб.

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

 

x
0	0	0	0	0	0	0	0	0
20	3	3	2		2		1
40	5	5	4		4		3
60	7	7	5		5		6
80	9	9	7		7		7
100	10	10	9		9		9

 

. Чтобы вычислить значения для столбца , надо по столбцу  двигаться от 0 вниз до заполняемой клетки, а по столбцу  двигаться вверх от заполняемой клетки до числа 0, образовывая сумм. Среди которых выбирают максимальную. Аналогично заполняют остальные столбцы. В итоге получаем таблицу:

 

x
0	0	0	0	0	0	0	0	0
20	3	3	2	3	2	3	1	3
40	5	5	4	5	4	5	3	5
60	7	7	5	7	5	7	6	7
80	9	9	7	9	7	9	7	9
100	10	10	9	11	9	11	9	11

 

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