Оптимальное распределение ресурсов
Пусть, например, n предприятий используют некоторые ресурсы. Известно, что если «K»-ому предприятию выделить Х единиц ресурсов, то количество произведенной продукции будет равно φk(Х).
Требуется распределить А единиц ресурсов между n предприятиями так, чтобы суммарный выпуск продукции был максимальным.
Обозначим через Хk количество ресурсов, которое нужно выделить к-ому предприятию, тогда математическая модель задачи запишется так:
φ1(Х1)+φ2(Х2)+…+φ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 единиц ресурсов, выпускает φk(Хk) единиц продукции (таблица 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. Что является исходной информацией для задачи оптимального распределения ресурсов?