Закрепление потребителей за поставщиками неоднородного взаимозаменяемого продукта

Во многих случаях перевозке подлежат разные, но взаимозаменяемые продукты (например, уголь, нефть, мазут или цемент разных марок). Рассмотрим постановку и метод решения такой задачи.

В пунктах а₁, А₂,..., А_i,..., А_m хранится соответственно а₁, а₂, …, а_i, …, а_m тонн топлива разных сортов, причем в каждом из них имеется топливо только одного сорта. Таким образом, число пунктов отправления и число сортов топлива в этой задаче совпадают. Под топливом разного сорта подразумевается не только горючее разных видов (например, уголь, нефть, мазут), но и топливо одного вида, но разного качества (например, уголь разных сортов). Предприятиям, расположенным в пунктах В₁, В₂,..., В_j,..., В_n, требуется соответственно b₁, b₂,..., b_j, …,b_n тонн условного топлива. Каждый из потребителей может использовать любой из имеющихся видов топлива. Коэффициенты приведения топлива разных сортов к условному топливу известны и составляют k₁, k₂, …, k_i, …,k_m. Известны также расстояния l_ij между пунктами А_i и В_j. Требуется составить план перевозок (закрепления потребителей топлива за поставщиками) так, чтобы полностью удовлетворить запросы всех потребителей при минимальном объеме транспортной работы.

Обозначим через x_ij количество топлива 1-го сорта (т. е. из i-го пункта), поставляемое j-му потребителю. Тогда рассматриваемая задача формально записывается следующим образом: минимизировать транспортную работу

x_ij l_ij (14)

при условиях

k_i x_ij = b_j, j = 1, 2, …, n (15)

x_ij < a_i, i = 1, 2, …, m (16)

x_ij > 0, I = 1, 2, …, m; j = 1, 2, …, n (17)

Ограничения (15) означают, что объем доставляемого в каждый пункт потребления топлива должен в условных единицах равняться спросу этого пункта. Условия (16) означают, что общий объем топлива, направляемый во все пункты потребления из i-гопункта, не должен превышать запасов топлива i-го сорта (имеющегося в i-м пункте).

Задача (14) -- (17) отличается от классической транспортной наличием в условиях (15) коэффициента k_i. Поэтому актуальной является проблема сведения подобной задачи к классической транспортной. Анализ показывает, что в данном случае это возможно.

Обозначим запасы топлива на складах в тоннах условного топлива (условных тоннах) через а`<sub>1</sub>, а`₂,..., а`<sub>i</sub>,..., а`_m. При этом а`<sub>i</sub> = а<sub>i</sub> k<sub>i</sub>. Поскольку произведение условных тонн и условного расстояния перевозки не дают теперь величины реальной транспортной работы (тонно-километров), заменим l<sub>ij</sub> на l`_ij = l_ij /k _i.

Нетрудно заметить, что произведение условных тонн и условного расстояния дает реальные тонно-километры, т. е.

l`<sub>ij</sub> x`_ij = l_ij x _ij,

где х` -- количество условного топлива, поставляемого из пункта А_i в пункт В _j).

В новых обозначениях задача принимает следующий вид: минимизировать линейную форму

l`<sub>ij</sub> x`_ij (18)

при условиях x`<sub>ij</sub> = b`_j , j = 1, 2, …, n; (19)

x`<sub>ij</sub> < a`_i, i = 1, 2, …, m; (20)

x`_ij >0, i = 1, 2, …, m, j = 1, 2, …, n. (21)

Задача (18) -- (21) является открытой моделью классической транспортной задачи, и, следовательно, для ее решения можно использовать алгоритм метода потенциалов. При этом процедуру вычислений можно представить в следующем виде.

1. Пересчитать матрицу расстояний || l_ij || на || l`_ij || = l_ij /k_i.

2. Выразить запасы топлива в пунктах А₁, А₂,..., А_i,..., А_m в тоннах условного топлива.

3. Составить матрицу условий, используя величины а`<sub>i</sub>, b<sub>j</sub> и l`_ij.

4. Решить поставленную задачу (найти оптимальный план перевозок топлива, выраженного в условных единицах) методом потенциалов.

5. Заменить величины а`<sub>i</sub>, х`_ij и l`_ij матрицы оптимального плана числами а_i, х_ij и l_ij, рассчитанными по формула

a _i = а`<sub>i</sub> / k<sub>i</sub> , x<sub>ij</sub> = x`_ij/ k_i , l _ij = l`_ij / k_i .

Оптимальный план перевозок топлива найден. Решение закончено.

Поясним процедуру вычислений на конкретном примере. Пусть в пунктах А₁ и А₄ имеется соответственно 30 и 20 т угля марки А, в пункте А₂ --50 т угля марки Бив пункте А₃-- 40 т угля марки В. Коэффициенты перевода угля в тонны условного топлива для марок А, Б и В соответственно 1,00; 1,20 и 1,25. Потребителям В₁, В₂, В₃ и В₄ требуется соответственно 40, 70, 40 и 10 т условного топлива, причем удовлетворять эту потребность можно углем любой марки. Расстояния между пунктами приведены в табл. 22. Требуется закрепить потребителей угля за поставщиками так, чтобы при полном удовлетворении спроса суммарный объем транспортной работы при перевозке угля был минимальным.

Поскольку в условии задачи дается неоднородная (по калорийности), но взаимозаменяемая продукция, то прежде чем составить матрицу условий, пересчитываем исходные данные следующим образом.

1. Расстояния в первой и четвертой строках таблицы (табл. 22) умножаем на 1,00, во второй -- на 1,20 и в третьей -- на 1,25; в результате получаем новую таблицу расстояний (табл. 23).

Таблица 22

Пункт отправления	Пункт назначения
	B1	B2	B3	B4
A 1	5	7	2	4
A2	9	9	6	6
A3	10	12	6	8
A4	5	4	1	2

2. Объемы угля в пунктах отправления выражаем в тоннах условного топлива, т.е. А₁=30 * 1=30 т, А₂=50 * 1,2=60 т, А₃=40 * 1,25=50 т и A₄=20* 1=20 т.

Используя полученные данные, обычным порядком составляем матрицу условий, после чего методом потенциалов находим оптимальную схему закрепления потребителей угля за поставщиками (табл. 24). Пересчитав условные объемы и расстояния в реальные, получаем оптимальный план перевозок угля (табл. 25), обеспечивающий минимум транспортной работы.

Таблица 23

Пункт отправления	Пункт назначения
	B1	B2	B3	B4
A 1	5	7	2	4
A2	7,5	7,5	5	5
A3	8	9,6	4,8	6,4
A4	5	4	1	2

Таблица 24

Пункт отправления	Вспомогательные коэффициенты	Пункт назначения				Наличие груза, т
		B1	B2	B3	B4
		5	5,9	1,8	3,4
A1	0	5 30	7	2	4	30
A2	1,8	7,5	7,5 50	5	510	60
A3	3	8 10	9,6	4,840	6,40	50
A4	-1,9	5	4 20	1	2	20
Потребность в грузе, т	40	70	40	10	160

Таблица 25

Пункт отправления	Пункт назначения