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

Пусть, например, n предприятий используют некоторые ресурсы. Известно, что если «K»-ому предприятию выделить Х единиц ресурсов, то количество произведенной продукции будет равно φk(Х).

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

Обозначим через Хk количество ресурсов, которое нужно выделить к-ому предприятию, тогда математическая модель задачи запишется так:

φ11)+φ22)+…+φn (Xn) → max

при ограничениях

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

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

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

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

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

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

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

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

Итак,

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

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

Зная f1(X), находим f2(X), затем f3(X) и т.д.

Пример

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

Таблица 6.1

jк (x) x ед. ресурсов Продукция предприятий (усл. ед.)
j1 (x) j2 (x) j3 (x) j4 (x)

 

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

Решение.

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

(6.1)

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

при x=1 f1 (1) =φ1 (1) = 3,

при x=2 f1 (2) = φ1 (2) =5,

при x=3 f1 (3) = φ1 (3) =7,

при x=4 f1 (4) = φ1 (4) =8,

при x=5 f1 (5) = φ1 (5) 8,

т. е. f1 (x) = φ1 (x) и α1 (Х)=Х.

Результаты записываем в колонку f1(Х) иα1(Х) таблицы 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

 

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

(6.2)

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

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

(6.3)

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

f3(0)=0, α3 (0)=0;

f3(1)=4, α3 (1)=0;

f3(2)=7, α3 (2)=0 или 1;

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

f3(4)=13, α3 (4)=2;

f3(5)=15, α3 (5)=2 или 3

Таблица 6.3

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

X t X-t j2(t) f1(X-t) j2(t)+ f1(X-t) f2(X) a2(X)
1. 0+3 4+0
2. 0+5 4+3 5+0
3. 0+7 4+5 5+3 6+0
4. 0+8 4+7 5+5 6+3 8+0
5. 0+8 4+8 5+7 6+5 8+3 9+0 1,2

 

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

(6.4)

Получим:

F4(0)=0, α4 (0)=0;

F4(1)=4, α4 (1)=0 или 1;

F4(2)=8, α4 (2)=1;

F4(3)=11, α4 (3)=1;

F4(4)=14, α4 (4)=1;

F4(5)=17, α4 (5)=1.

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

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

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

Таблица 6.4

Предприятие Количество распределенного ресурса Самоконтроль
Количество продукции
Первое j1(1)=3
Второе j2(1)=4
Третье j3(2)=6
Четвертое j4(1)=4

Сумма равна 17

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

т.е. j1(1)=3; j2(1)=4; j3(2)=6; j4(1)=4.

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

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

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

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

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

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

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