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

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

(4.1.4)

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

Предположим, что распределение ресурса осуществляется по шагам: сначала выделяется некоторое количество ресурса одному предприятию, затем другому и т.д. Введем переменную – количество ресурса, выделенное -му предприятию (в динамическом программировании соответствует количеству ресурса, выделенному в -й момент времени или на -м шаге). Тогда прибыль, даваемая -м предприятием, составит . Количество ресурса, остающегося не распределенным к -му моменту времени, обозначим через . В результате вместо задачи (4.1.4) получим следующую задачу динамического программирования:

В такой постановке интерпретируются как управления, а – как значения параметра состояния системы.

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