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

Если φ₁, …, φ_n – линейные функции, то задача решается методами линейного программирования.

Если φ₁, …, φ_n – нелинейные дифференцируемые функции, то задача решается методами нелинейного программирования.

Если функции φ₁, …, φ_n заданы таблично, то задача решается методами динамического программирования.

При решении задачи о распределении ресурсов введём функцию Беллмана f_k(Х) – максимальное количество продукции, которое могут выпустить К предприятий, при этом α_k(Х) – количество ресурса, получаемое к-ым предприятием при оптимальном распределении ресурса между первыми предприятиями.

Предположим, что f_k(Х) известно, тогда вычислим f_k+1(Х).

Пусть к+1-ое предприятие получает t единиц (0≤t≤X) ресурса, тогда оно выпускает φ_k+1(t) единиц продукции. На долю же первых к предприятий останется Х – t единиц ресурса.

В силу принципа оптимальности: чтобы получить больше продукции, необходимо распределить оптимально оставшиеся Х – t единиц ресурса между остальными к предприятиями. Тогда общий выпуск продукции будет равен φ_k+1(t) + f_k(X – t).

Но, чтобы этот общий выпуск продукции был максимальным, необходимо tподобрать так, чтобы эта сумма достигла наибольшего значения, т.е. f_k+1(Х). [14].

Итак,

– функциональное

уравнение Беллмана.

Зная f₁(X ), находим f₂(X ), затем f₃(X ) и т.д.

Пример

Известно, что К-ое предприятие, получив Х_k единиц ресурсов, выпускает φ_k(Х_k) единиц продукции (таблица 6.1).

Таблица 6.1

Требуется распределить 5 единиц некоторого ресурса между 4-мя предприятиями так, чтобы общий выпуск продукции всеми предприятиями был максимальным.

Решение.

Функциональное уравнение Беллмана для оптимального распределения ресурсов имеет вид:

Найдем f₁(x) – максимальный выпуск продукции одним предприятием, например, первым. Если предприятие не имеет ресурса (x=0), то и нет выпуска продукции, т. е. j_к(0)=0, а значит и f₁(0)=0.

при x=1 f₁ (1) =φ₁ (1) = 3,

при x=2 f₁ (2) = φ₁ (2) =5,

при x=3 f₁ (3) = φ₁ (3) =7,

при x=4 f₁ (4) = φ₁ (4) =8,

при x=5 f₁ (5) = φ₁ (5) 8,

т. е. f₁ (x) = φ₁ (x) и α₁ (Х)=Х.

Результаты записываем в колонку f₁(Х) иα₁(Х) таблицы 6.2.

Таблица 6.2

Расчетная матрица

Ресурсы

Исходная информация

f1(х)

a1(х)

f2(х)

a2(х)

f3(х)

a3(х)

f4(х)

a4(х)

X

φ1(x)

φ2(x)

φ3(x)

φ4(x)

0

0

0,1

0,1

1,2

1,2

2,3

Для вычисления f₂ (Х) и α₂ (Х)составим таблицу 6.3., исходя из формулы:

(6.2)

Полученные значения f₂(Х) и α₂ (Х) записываем соответственно в колонки таблицы 6.2. Следует заметить, что в формуле 6.2 первое слагаемое φ₂ (t) возрастает «сверху вниз», а второе слагаемое f₁ (x-t) убывает «снизу вверх» (отмечено стрелками в таблице 6.2), что позволяет без дополнительной таблицы 6.3. находить максимальную сумму для каждого .

Найдем f₃(Х) и α₃ (Х) по формуле

(6.3)

Можно снова составить таблицу для каждого значения Хи возможных значений t (аналогично таблице 6.3) или же воспользоваться указанным выше замечанием. Вычисленные значения f₃(Х) и α₃ (Х) записываем в таблице 6.2

f₃(0)=0, α₃ (0)=0;

f₃(1)=4, α₃ (1)=0;

f₃(2)=7, α₃ (2)=0 или 1;

f₃(3)=10, α₃ (3)=1 или 2;

f₃(4)=13, α₃ (4)=2;

f₃(5)=15, α₃ (5)=2 или 3

Таблица 6.3

Расчет функции Беллмана

Затем вычислим f₄(Х) и α₄ (Х ) по формуле

(6.4)

Получим:

F₄(0)=0, α₄ (0)=0;

F₄(1)=4, α₄ (1)=0 или 1;

F₄(2)=8, α₄ (2)=1;

F₄(3)=11, α₄ (3)=1;

F₄(4)=14, α₄ (4)=1;

F₄(5)=17, α₄ (5)=1.

Заполняем столбцы f₄(Х) и α₄ (0)=0 таблицы 6.2 и делаем вывод, что при распределении 5 единиц ресурсов между первым, вторым, третьим и четвертым предприятиями, получим максимальный выпуск продукции всеми предприятиями 17 единиц, при этом четвертому предприятию следует выделить одну единицу ресурса, т.к. α₄ (5)=1. Осталось 5-1=4 ед. ресурса и три предприятия, поэтому в таблице 6.2 находим α₃ (4)– количество ресурса, необходимое третьему предприятию, α₃(4)=2

После этого осталось на два предприятия 5-1-2=2 ед. ресурса. Находим из той же таблицы α₂ (2)=1, т.е. второму предприятию следует выделить одну единицу ресурса. Тогда первому предприятию останется одна единица ресурса, что и указано в таблице: α₁ (1)=1. Если нет ошибок в вычислениях, то это совпадение единиц ресурса обязательно.

Итак, получим:

Таблица 6.4

Сумма равна 17

Для проверки правильности расчетов (самоконтроль) найдем количество выпускаемой продукции при данном распределении ресурсов между предприятиями по исходной информации,

т.е. j₁(1)=3; j₂(1)=4; j₃(2)=6; j₄(1)=4.

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

Вопросы для самоконтроля

1. Особенности задач, решаемых методом динамического программирования (ДП).

2. Каков смысл функции Беллмана в задаче оптимального распределения ресурсов?

3. Зачем составляется функциональное уравнение Беллмана?

4. Какова суть принципа оптимальности, положенного в основу вывода функционального уравнения Беллмана в задаче оптимального распределения ресурсов?

5. Что является исходной информацией для задачи оптимального распределения ресурсов?