Задача о распределении ресурсов

Имеется некий запас ресурсов (средств) К, который нужно распределить между предприятиями А₁, А₂, ..., А_m. Каждое i-ое предприятие при вложении в него каких-то средств x приносит доход в виде функции . Все  заданы (пусть они неубывающие). Как распределить средства К между A_i (i =1,2,...,m), чтобы в сумме они дали максимальный доход?

Здесь нет параметра времени. Однако, операцию распределения средств можно мысленно развернуть в какой-то последовательности, считая за первый шаг вложение в предприятие А₁, за второй - вложение в предприятие А₂ и т.д.

Управляемая система S в данном случае - это ресурсы (средства). Состояние системы S перед каждым шагом характеризуется одним числом S -наличным запасом еще не вложенных средств.

Шаговыми управлениями являются средства х₁, x₂, ..., х_m, выделяемые конкретным предприятиям.

Требуется найти оптимальное управление, т.е. совокупность х₁, x₂, ..., х_m, при которой суммарный доход максимален:

.

Решение в общем виде

Находим для каждого i-го шага условный оптимальный выигрыш (от этого шага и далее до конца), если к данному шагу подошли с запасом средств S. Обозначаем условный оптимальный выигрыш wi(S), а соответствующее ему условное оптимальное управление - средства, вкладываемые в i-е предприятие, - xi(S).

Начинаем оптимизацию с последнего m-го шага.

Пусть подошли к этому шагу с остатком средств S. Вкладываем всю сумму S целиком в предприятие Аm. Следовательно, условное оптимальное управление на m-ом шаге: отдать последнему предприятию все имеющиеся средства S:

,

а условный оптимальный выигрыш:

.

Задаваясь последовательностью значений S (располагая их достаточно тесно), для каждого значения S будем знать xm(S) и wm(S). Последний шаг оптимизирован.

Переходим к предпоследнему (m-1)-му шагу. Пусть подошли к нему с запасом средств S. Обозначим wm-1(S) условный оптимальный выигрыш на двух последних шагах: (m-1)-ом и m-ом (последний оптимизирован). Если на (m-1)-ом шаге (m-1)-му предприятию выделим средств x, то на последний останется S-x. Выигрыш на двух последних шагах будет:

и нужно найти такое x, при котором этот выигрыш максимален:

Знак max означает, что берется максимальное значение по всем x, какие только возможны при x £ S (вложить больше, чем S нельзя) от выражения в { }. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а то значение x, при котором max достигается, - условное оптимальное управление на (m-1)-ом шаге.

Далее оптимизируем (m-2)-й, (m-3)-й и т.д. шаги. Для любого i-го шага условный оптимальный выигрыш за все шаги с этого и до конца находятся по формуле:

и соответствующее ему условное оптимальное управление xi(S) - то значение x, при котором этот максимум достигается.

Продолжая этот процесс, доходим до первого предприятия А1. Варьировать значениями S нет нужды, так как знаем, что запас средств перед первым шагом есть K, т.е.:

.

Итак, максимальный выигрыш (доход) от всех предприятий найден. Значение x, при котором достигается max в последнем соотношении и есть оптимальное управление  на первом шаге.

После того, как эти средства вложены в первое предприятие, остается . Читая рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств:

 и т.д. до конца.