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

Для расширения производства совет директоров выделяет средства в объеме 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

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