§2. Задача распределения ресурсов.

Постановка задачи. Имеется n технологических процессов, где используется дефицитное сырье, объем которого равен C. Получаемая прибыль на каждом технологическом процессе зависит от объема вложенного в него сырья. Общая прибыль – это суммарная прибыль от всех технологических процессов. Требуется так распределить сырья между технологическими процессами, чтобы общая прибыль была максимальной.

Решение задачи. Введем обозначения. Пусть

– объем сырья, выделенный i-тому технологическому процессу,

– прибыль, получаемая на i-том технологическом процессе.

Тогда

– суммарная прибыль от всех технологических процессов.

Очевидно, что на переменные накладываются ограничения:

,

.

Таким образом, имеем следующую математическую модель задачи:

(2.1)

где = [0; C], i =1.

Задачу (2.1) решим методом динамического программирования. Первый этап метода – погружение задачи в семейство аналогичных задач. Будем считать, что число технологических процессов равно k (ясно, что , ) и объем выделяемого сырья равен y (ясно, что ). Тогда имеем задачу

 max, , , i =1. (2.2)

Если k = n и y = C, то получим исходную задачу (2.1).

Введем функцию Беллмана – оптимальное (максимальное) значение целевой функции задачи (2.2), обозначив ее B_k(y). Заметим, что это функция двух аргументов k и y, будем считать, что при заданном натуральном значении k значения . В частности при k = 1 получаем

B₁(y) = , = . (2.3)

Перейдем ко второму этапу метода динамического программирования – составлению уравнения Беллмана. Рассуждаем следующим образом. Из общего объема y последнему k-тому технологическому процессу выделим объем, равный z, . При этом прибыль от k-того процесса согласно условию равна . На остальные от первого до (k1)-го технологические процессы остается сырье в объеме yz. Следуя принципу оптимальности, считаем, что оно между этими процессами распределено наилучшим образом. Полученная прибыль (максимально возможная) есть функция Беллмана B_k-1(yz), где yz Y_k-1 .Тогда общая прибыль от всех k технологических процессов равна

B_k-1(yz) + f_k(z). (2.4)

Далее для всех z  Y_k и (yz)  Y_k-1 требуется найти максимальное значение функции (2.4), т.е. значение B_k(y). Таким образом, получаем уравнение:

B_k(y) = max ;\s\do9(z(Y k , k =1. (2.5)

которое и есть уравнение Беллмана. Начальные условие для этого рекуррентного относительно аргумента k уравнения имеет вид (2.3).

Третий этап метода динамического программирования – поиск решение уравнения (2.5) с начальными условиями (2.3) и построение по нему решения исходной задачи.

В уравнении (2.5) положим k = 2:

B₂(y) = max ;\s\do9(z(Y2 , (2.6)

где f₂(z) – заданная функция, B₁(yz) – определено согласно (2.3), поэтому правая часть определена для всех y  [0; C], для которых yz Y₁. Множество таких значений y и есть множество Y₂ . Для каждого yY₂ найдем значение z, на котором достигается максимум в правой части (2.6): , а также значение B₂(y).

Далее полагаем в уравнении (2.5) k = 3, 4, … , n . После процесса оптимизации получим последовательность Combin, B₃(y), yY₃ ; Combin, B₄(y), yY₄ ; …, Combin, B_n(y), yY_n.

Если CY_n, то исходная задача не имеет решения. В противном случае B_n(C) – максимальная прибыль. Оптимальное распределение ресурсов по технологическим процессам определяем, начиная с x(; \s\do2(n= Combin. Затем x(; \s\do2(n-1= x(; \s\do2(n-1, … , x(; \s\do2(2, x(; \s\do2(1.

Алгоритм решения. Вычислительная схема решения задачи распределения ресурсов такова. Промежуток [0; C] разбиваем на n интервалов с шагом . Считаем, что функции и B_k(y) определены только в точках 0, , 2, … , n = C. Исходные данные заносим в таблицу 2.1.

Таблица 2.1.

x	0		2	…	n
				…
				…
…	…	…	…	…	…
				…

Далее составляем таблицу 2.2, которая заполняется значениями функции B_k(y) и значениями Combin.

Таблица 2.2.

y	0		2	…	n
				…
Combin				…
…	…	…	…	…
Combin				…

Первая строчка согласно (2.3) заполняется соответствующими значениями из табл.2.1. Зная значения , i =1, переходим к вычислению значений , i =1, согласно (2.6), при этом устанавливаем те значения Combin, , при которых максимальное значение достигается. Затем переходим к вычислению , Combin, , и т.д. Последняя строка заполняется значениями , Combin, , где = есть искомая максимальная прибыль, а значение x(; \s\do2(n = Combin– объем сырья на последний технологический процесс в оптимальном распределении ресурсов. Затем находим – объем сырья, который надо распределить между остальными n1 технологическими процессами. В предпоследней строке находим значение и значение x(; \s\do2( n-1и т.д. Продолжая процесс вычислений, определим x(; \s\do2(1 .

Пример 2.1. Пусть имеется 3 завода, между которыми надо распределить 300 единиц ресурса. Прибыль, получаемая от вложенного сырья на каждом заводе получена экспериментально, данные с шагом  = 60 приведены в табл. 2.3.

Таблица 2.3.

x	0	60	120	180	240	300
	0	20	46	104	130	158
	0	34	68	102	145	170
	0	28	75	120	148	166

Требуется найти оптимальное распределение ресурсов между заводами.

Вычисления будем записывать поэтапно в таблицы 2.4  2.6, затем составим результирующую таблицу 2.7.

Таблица 2.4 заполняется значениями согласно (2.3): B₁(0) , B₁(50) и т.д.

Таблица 2.4.

y	0	60	120	180	240	300
	0	20	46	104	130	158

Вычисления по заводу 2 поместим в таблицу 2.5.

= max ;\s\do9(z({0 = max =34 ,

Combin = 60;

= max ;\s\do9(z({0 = = 68 ,

Combin= 120;

B₂(180) {B₁(180) + f₂(0), B₁(120) + f₂(60), B₁(60) + f₂(120), B₁(0) + f₂(180)} = max {104 + 0, 46 + 34, 20 + 68, 0 + 102} = 104 ,

Combin=0;

B₂(240) =max ;\s\do9(z({0{B₁(240) + f₂(0), B₁(180) + f₂(60), B₁(120) + f₂(120), B₁(60) + f₂(180), B₁(0) + f₂(240)} = max {130 + 0, 104 + 34, 46 + 68, 20 + 102, 0 + 145} = 145 ,

Combin= 240;

B₂(300) = max ;\s\do9(z({0{B₁(300) + f₂(0), B₁(240) + f₂(60), B₁(180) + + f₂(120), B₁(120) + f₂(180), B₁(60) + f₂(240), B₁(0) + f₂(300)} = max{158 + 0, 130 + 34, 104 + 68, 46 + 102, 20 + 145, 0 + 170} = 172,

Combin= 120.

Таблица 2.5.

y	0	60	120	180	240	300
Combin	0 0	34 60	68 120	104 0	145 240	172 120

Вычисления по заводу 3 поместим в таблицу 2.6.

B₃(60) = max ;\s\do9(z({0{(B₂(60) + f₃(0), B₂(0) + f₃(60)} = max {34 + 0, 0 + 28} = 34,

Combin = 0;

B₃(120) = max ;\s\do9(z({0{(B₂(120) + f₃(0), B₂(60) + f₃(60), B₂(0) + f₃(120)} = = max{68 + 0, 34 + 28, 0 + 75} = 75 ,

Combin=120;

B₃(180) =max ;\s\do9(z({0{(B₂(180) + f₃(0), B₂(120) + f₃(60), B₂(60) + f₃(120), B₂(0) + f₃(180)} = max{104 + 0, 68 + 28, 34 + 75, 0+120} = 120,

Combin=180;

B₃(240) = max ;\s\do9(z({0 {B₂(240) + f₃(0), B₂(180) + f₃(60), B₂(120) + + f₃(120), B₂(60) + f₃(180), B₂(0) + f₃(240)} = max{145 + 0, 104 + 28, 68 + 75, 34 + 120, 0 + 148} = 154,

Combin=180;

B₃(300) = max ;\s\do9(z({0{B₂(300) + f₃(0), B₂(240) + f₃(60), B₂(180) + + f₃(120), B₂(120) + f₃(180), B₂(60) + f₃(240), B₂(0) + f₃(300)} = max{172 + 0, 145 + 28, 104 + 75, 68 + 120, 34 + 148, 0 + 166} = 188,

Combin= 240.

Таблица 2.6.

y	0	60	120	180	240	300
Combin	0 0	34 0	75 120	120 180	154 180	188 240

Составим общую таблицу 2.7.

Искомая максимальная прибыль равна 188, x(; \s\do2(3 = Combin= 240.

Далее = 300 –240 = 60, = 34, x(; \s\do2(2 = Combin= 60.

Итак, заводу 1 – 0 ед. ресурсов, заводу 2 – 60 ед. ресурсов, заводу 3 – 240 ед. ресурсов.

Таблица 2.7.

y	0	60	120	180	240	300
	0	20	46	104	130	158
Combin	0 0	34 60	68 120	104 0	145 240	172 120
Combin	0 0	34 0	75 120	120 180	154 180	188 240

Пример 2.2. В примере 1 изменим общее количество распределяемого ресурса. Пусть С = 240. Решение задачи можно найти по таблице 2.7.

Искомая максимальная прибыль равна 154, x(; \s\do2(3 = Combin= 180.

Далее = 240 –180 = 60, = 34, x(; \s\do2(2 = Combin= 60.

Таким образом, заводу 1 – 0 ед. ресурсов, заводу 2 – 60 ед. ресурсов, заводу 3 – 180 ед. ресурсов.