Распределение ресурсов с помощью метода динамического программирования.
Динамическое программирование (ДП) – это метод, приспособленный для решения оптимизационных задач, связанных с многошаговыми процессами. В задачах динамического программирования находится ряд оптимальных решений последовательно для каждого этапа, обеспечивающих оптимальное развитие всего процесса в целом.
Многошаговый процесс можно интерпретировать так: весь цикл разбить на несколько этапов и на каждом этапе требуется принять то или иное решение.
При решении задач методом ДП вводят функцию Беллмана fk, которая представляет собой максимальную эффективность многошагового процесса, состоящего из К шагов. Для вычисления функции Беллмана составляется так называемое функциональное уравнение Беллмана, позволяющее находить значения функции Беллмана fк+1, если известно fk.
При выводе уравнения Беллмана используется та или иная форма принципа оптимальности.
Если на первом шаге принято решение, то дальнейшее решение должно приниматься таким образом, чтобы за оставшееся число шагов достичь максимального (минимального) результата. Пусть, например, n предприятий использует некоторые ресурсы. Известно, что, если “K” –ому предприятию выделить X единиц ресурсов, то количество произведенной продукции будет равно φk(X).
Требуется распределить A единиц ресурсов между всеми предприятиями так, чтобы выпуск продукции был максимальным. Обозначим через Xk количество ресурсов, которое нужно выделить K - му предприятию, тогда математическая модель задачи запишется так:
φ1(X1)+φ2(X2)+…+φn(Xn)→max
при ограничениях
X1+X2+…+Xn=A
X1≥0, X2≥0,…,Xn≥0.
Если φ1, … φn – заданы таблично, то задача решается методами динамического программирования.
Рассмотрим оптимальное распределение ресурсов с помощью метода динамического программирования.
При решении задачи о распределении ресурсов введем функцию Беллмана fk(X) – максимальное количество продукции, которое могут выпустить K предприятий, при этом αk(X) – количество ресурса, получаемое K - ым предприятием при оптимальном распределении ресурса между первыми предприятиями.
Предположим, что fk(X) известно, тогда вычислим fk+1 (X).
Пусть К+1 – ое предприятие получает t единиц (0 ≤ t ≤ X) ресурса, тогда оно выпускает φk+1 (t) единиц продукции. На долю же первых K предприятий останется X – t единиц ресурса.
В силу принципа оптимальности: чтобы получить больше продукции, необходимо распределить оптимально оставшиеся (X – t) единиц ресурса между K предприятиями. Тогда общий выпуск продукции будет равен
φk+1(t)+fk(X – t).
Но, чтобы этот общий выпуск продукции был максимальным, необходимо t подобрать так, чтобы эта сумма достигала наибольшего значения, т.е. fk+1 (X). Функциональное уравнение Беллмана:
Зная f1(X), находим f2(X), затем f3(X) и т.д
Нагляднее этот метод рассмотрим на примере.
Пример.
Известно, что K – ое предприятие, получив Xk единиц ресурсов, выпускает φk(Xk) единиц продукции (рис.1)
Рисунок 1
Требуется распределить 5 единиц некоторого ресурса между 4 – мя предприятиями так, чтобы общий выпуск продукции всеми предприятиями был максимальным.
Решение.
Функциональное уравнение Беллмана для оптимального распределения ресурсов имеет вид:
Найдем fк(X) – максимальный выпуск продукции одним предприятием, например первым. Если предприятие не имеет ресурса (Х=0), то и нет выпуска продукции, т.е φk(0)=0, а значит и f1(0)=0.
При Х=1 f1(1)= φ1(1)=3,
При Х=2 f1(2)= φ1(2)=5,
При Х=3 f1(3)= φ1(3)=7,
При Х=4 f1(4)= φ1(4)=8,
При Х=5 f1(5)= φ1(5)=8,
Т.е. f1(X)=φ1(Х) и α1(Х)=Х.
Результаты записываем в колонку f1(X) и α1(Х) (рис. 2).
Рисунок 2
Для вычисления f2(X) и α2(Х) составим таблицу, исходя из формулы:
Полученные значения f2(X) и α2(Х) записываем соответственно в колонки таблицы (рис. 2).
Следует заметить, что в формуле первое слагаемое φ2(t) возрастает “сверху вниз”, а второе слагаемое f1(X-t) убывает “снизу вверх” (отмечено стрелками в таблице), что позволяет без дополнительной табл. находить максимальную сумму для каждого t є [0,5].
Найдем f3(X) и α3(Х) по формуле:
Рисунок 3.
Вычисленные значения f3(X) и α3(Х) записываем в табл.
f3(0)=0, α3(0)=0;
f3(1)=4, α3(1)=0;
f3(2)=7, α3(2)=0;
f3(3)=10, α3(3)=1;
f3(4)=13, α3(4)=2;
f3(5)=15, α3(5)=2 или 3.
Затем вычислим f4(X) и α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(X) и α4(Х) таблицы (рис. 3), делаем вывод: при распределении 5 единиц ресурсов между первым, вторым, третьим и четвертым предприятиями получим максимальный выпуск продукции всеми предприятиями 17 единиц, при этом четвертому предприятию следует выделить 1 ед. ресурса, т.к. α4(5)=1.
Осталось 5 – 1 = 4 ед. ресурса и три предприятия, поэтому в таблице (рис. 3). находим α3(4) – количество ресурса, необходимое третьему предприятию, α3(4)=2. После этого осталось на два предприятия 5 – 1 – 2 = 2 ед. ресурса.
Находим из той же таблицы α2(2)=1, т.е. второму предприятию следует выделить одну единицу ресурса. Тогда первому предприятию останется одна единица ресурса, что и указано в таблице: α1(1)=1. Если нет ошибок в вычислениях, то это совпадение единиц ресурса обязательно.
Итого получим:
Рисунок 4
Сумма равна 17.
Для проверки правильности расчетов (самоконтроль) найдем количество выпускаемой продукции при данном распределении ресурсов между предприятиями по исходной информации, т.е.
φ1(1)=3; φ2(1)=4; φ3(2)=6; φ4(1)=4.
Суммарный выпуск продукции составляет 17 единиц, что подтверждает правильность расчета распределения ресурсов.
Категория: Научные статьи | Добавил: Катерина (16.08.2010) | Автор: Местецкая Е.В., ТюмГУ МИФУБ
