Оптимальное распределение ресурсов

Пример

Для модернизации производства четырем предприятиям выделены денежные средства По каждому из 4-х предприятий известен возможный прирост выпуска продукции в зависимости от выделенной ему суммы .

Требуется:

1) распределить средства между предприятиями так, чтобы суммарный прирост выпуска продукции на всех предприятиях достиг величины ;

2) используя данные пункта 1) найти оптимальное распределение 100 млн. руб. между тремя предприятиями;

3) найти оптимальное распределение 80 млн. руб. между тремя предприятиями.

Номер предприятия		0	20	40	60	80	100
1		0	9	20	35	44	57
2		0	12	25	34	46	57
3		0	11	20	32	48	61
4		0	14	23	40	50	58

Решение

Шаг 1.

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

Шаг 2.

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

Шаг 3.

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

Шаг 4.

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

Составим сводную таблицу на основе расчетов:

Выделяемые средства
0	0	0	0	0
20	9	12	12	14
40	20	25	25	26
60	35	35	36	40
80	44	47	48	52
100	57	60	61	65

Оптимальный план распределения между 4 предприятиями 100 единиц ресурса:

1-му предприятию:

2-му предприятию:

3-му предприятию:

4-му предприятию:

При этом суммарный прирост продукции достигнет максимальной величины, равной 65.

Оптимальный план распределения между 3 предприятиями 80 единиц ресурса:

1-му предприятию:

2-му предприятию:

3-му предприятию:

При этом суммарный прирост продукции достигнет максимальной величины, равной 48.