2. Транспортные модели

2.1 Транспортная задача и ее особенности

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

В общем виде транспортная задача формулируется: имеется m поставщиков и n потребителей однородного груза. Запасы i-го поставщика обозначим a_i , спрос j-го потребителя – b_j. Если обозначить c_ij – стоимость перевозки единицы груза, а x_ij – количество перевозимого груза от i-го поставщика j-му потребителю, то математическая модель задачи будет иметь вид:

1) суммарные запасы на перевозку должны быть минимальные
	(2.1)
2) объем поставок i-го поставщика равен его запасу
	(2.2)
3) объем поставок j-му потребителю равен его спросу
	(2.3)
4) неотрицательность переменных
	(2.4)

Вместо матрицы затрат c_ij может задаваться матрица расстояний d_ij.

Если суммарный объем отправляемых грузов равен потребности в этих грузах, то ТЗ называется закрытой (сбалансированной) закрытой грузов равен потребности в этих грузах, то задача называ) , иначе – открытой.

Если имеет место открытая ТЗ, ее нужно свести к закрытой форме следующим образом:

1) если спрос > предложения, то вводят фиктивного поставщика с недостающим объемом спроса; тарифы c_ij , связывающие фиктивные пункты с реальными равны штрафам за недопоставку продукции;

2) если спрос < предложения, то вводят фиктивного потребителя с недостающим объемом потребления, элементы матрицы c_ij , связывающие фиктивные пункты с реальными, равны стоимости хранения единицы нераспределенного груза.

Если указанные в п. 1, 2 затраты неизвестны, то соответствующие элементы c_ij = 0.

Транспортная задача решается в два этапа. Сначала необходимо найти исходный опорный план, а затем производится последовательно его улучшение до получения оптимального плана. На первом этапе для распределения ресурсов можно использовать правило «северо-западного угла» (здесь не учитываются тарифы и план далек от оптимального) или правило «минимального элемента», при котором необходимо осуществлять максимальные поставки ресурсов в клетки с минимальными тарифами. На втором этапе можно применить распределительный метод или метод потенциалов.

2.2 Метод потенциалов

Каждому поставщику (ограничению по запасам) поставим в соответствие потенциал u_i (i = ), а каждому потребителю (ограничению по спросу) — потенциал v_j (j = ).

Согласно теореме о потенциалах, каждой занятой клетке будет соответствовать уравнение u_i + v_j = c_ij. Так как всех занятых клеток должно быть т+п– 1, т. е. на единицу меньше числа потенциалов, то для определения чисел u_i, v_j необходимо решить систему из т+п–1 уравнений с т+п неизвестными: u_i+ v_{j =} c_ij. Одному из потенциалов задают обычно значение, равное нулю.

Для исследования плана на оптимальность по каждой свободной клетке проверяется условие u_i+ v_j ≤ c_ij. Если хотя бы одна свободная клетка не удовлетворяет данному условию, то опорный план не является оптимальным, его можно улучшить за счет загрузки этой клетки. Если таких клеток несколько, то наиболее перспективной для загрузки является клетка, для которой разность (оценка) между тарифом клетки и суммой потенциалов наименьшая, т. е. S_ij = с_ij – (u_i + v_j) < 0.

Например, для клеток (i;k) и (i;t) имеем оценки: S_ik= -5, S_it= -10. Здесь наиболее потенциальной является клетка (i;t). Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные издержки от загрузки данной клетки единицей груза. Эффективность плана от загрузки потенциальной клетки грузом в λ единиц составит ΔF = S_ij · λ ден.ед. Если для всех свободных клеток оценки S_ij ≥ 0, то опорный план перевозок является оптимальным.

Итак, если для опорного плана перевозок указанное условие оптимальности не выполняется, то за счет загрузки свободной клетки с отрицательной оценкой план перевозок улучшается. Для наиболее перспективной свободной клетки строится замкнутый цикл с вершинами в загруженных клетках. Вершинам этого цикла условно приписываются знаки: свободной клетке – плюс, следующей по часовой или против часовой стрелки занятой клетке – минус, следующей – снова плюс и т. д. Из поставок в клетках цикла с «отрицательными» вершинами выбирается наименьшее количество λ груза, которое и перемещается по клеткам этого цикла: прибавляется к поставкам в положительных вершинах и вычитается из поставок в отрицательных вершинах, в результате чего баланс цикла не нарушится.

Сформулируем алгоритм решения ТЗ методом потенциалов:

1. построить опорный план по одному из правил;

2. вычислить потенциалы поставщиков и потребителей u_i и v_j (i = ),; (j = ), решив систему уравнений вида u_i+ v_{j =} c_ij;

3. вычислить оценки Sij для всех свободных клеток по формуле S_ij = с_ij – (u_i + v_j). Если все S_ij ≥ 0, то полученный план является оптимальным. При этом если все S_ij ≥ 0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка S_ij = 0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

ПРИМЕР 2.1: В трех хранилищах А₁, А₂, А₃ имеется соответственно 70, 90 и 50 т топлива. Требуется спланировать перевозку топлива четырем потребителям В₁, В₂, В₃, В₄, спрос которых равен соответственно 50, 70, 40 и 40 т, так, чтобы затраты на транспортировку были минимальны. Стоимость перевозки 1 т указана в табл. 2.1.

Таблица 2.1.

Хранилища	Потребители				Запас топлива, т
	B1	В2	В3	B4
	Стоимость перевозки 1 т топлива, ден.ед.
A1	5	2	3	6	70
А2	4	3	5	7	90
А3	2	4	1	5	50
Потребность в топливе, т	50	70	40	40	210 > 200

РЕШЕНИЕ: Поскольку запасы топлива в хранилищах превышают спрос потребителей, задача является открытой, вводится фиктивный потребитель, спрос которого b₅ = 210 – 200 = 10 т. Все затраты для фиктивного потребителя с_i5 = 0 (i = ). После введения фиктивного потребителя открытая модель задачи преобразовалась в закрытую, а распределительная таблица принимает вид таблицы 2.2.

Таблица 2.2.

Хранилища	Потребители					Запас топлива, т
	B1	В2	В3	В4	В5
	Стоимость перевозки 1 т топлива, ден. ед.
А1	5	2	3	6	0	70
А2	4	3	5	7	0	90
А3	2	4	1	5	0	50
Потребность в топливе, т	50	70	40	40	10	210

Исходный опорный план получим, например, по правилу «минимального элемента». Так как наименьшими являются нулевые тарифы для клеток (1; 5), (2; 5), (3; 5), то загрузим первой, например, клетку (1; 5), х₁₅= 10 т. Второй загружаем клетку (3; 3), х_зз = 40 т. Далее загружаем клетки (1; 2), (3; 1), (2; 2), (2; 4), полагая х₁₂ = 60 т, х₃₁ = 10 т, х₂₂ = 10 т, х₂₁ = 40 т, х₂₄= 10 т (таблица 2.3).

Таблица 2.3.

В А	B1		В2		В3		В4		В5		За-пас
А1		5	+	2		3		6		– 0	70	u1=0
			60						10
А2		4	–	3		5		7		+ 0	90	u2=1
	40		10				40
А3		2		4		1		5		0	50	u3=-1
	10				40
Спрос	50		70		40		40		10		210
	v1=3		v2=2		v3=2		v4=6		v5=0

В результате распределения топлива по потребителям получили невырожденный план: условие для занятых клеток m+n–1=3+5–1=7 выполняется.

Для определения потенциалов составляем уравнения для занятых клеток: u₁+ v₂ = 2, u₁ + v₅ = 0, u₂ + v₁ = 4, u₂ + v₂ =3, и₂ + v₄ =7, u₃ + v₁ = 2, u₃ + v₃ =1. Положим, например, u₁ = 0, тогда и₂ = 1, u₃ = –1, v₁ =3, v₂ = 2, v₃ = 2, v₄= 6, v₅ = 0.

Определим оценки свободных клеток:

S11 = 5 − (0 + 3) = 2 > 0, S23 = 5 − (1 + 2) = 2 > 0, S34 = 5 − (-1 + 6) = 0,

S13 = 3 − (0 + 2) = 3 > 0, S25 = 0 − (0 + 2) = -2 < 0, S35 = 0 − (-1 -0) = 2 > 0,

S14 = 6 − (0 + 6) = 0, S32 = 4 − (-1 + 2) = 3 > 0,

Определив потенциалы, устанавливаем, что среди оценок свободных клеток одна отрицательная: S₂₅ = –1, следовательно, план перевозок можно улучшить за счет загрузки клетки (2;5). Цикл для нее выделен линией в таблице 2.3.

Наименьшее количество топлива в отрицательных вершинах цикла равно 10 т. После смещения по циклу 10 т получаем новый план перевозок (таблица 2.4). Полученный план является вырожденным. Поставим число 0, например, в клетку (2; 2).

Таблица 2.4.

В А	B1		В2		В3		В4		В5		За-пас
А1		5		2		3		6		0	70	u1=-1
			70
А2		4		3		5		7		0	90	u2=0
	40		0				40		10
А3		2		4		1		5		0	50	u3=-2
	10				40
Спрос	50		70		40		40		10		210
	v1=4		v2=3		v3=3		v4=7		v5=0

Для нового плана определяем новые потенциалы и находим оценки свободных клеток: S₁₁ = 2 >0, S₁₃ = l >0, S₁₄ = 0, S₁₅ = 1 > 0, S₂₃ = 2 > 0, S₃₂ = 3 > 0, S₃₄=0, S₃₅ = 2 >0.

Оценки всех свободных клеток S_ij > 0, следовательно, получен оптимальный план. Поскольку среди оценок имеются равные нулю, то за счет загрузки клеток (1; 4), (3; 4) можно получить новые планы, но значение целевой функции не изменится. Это случай бесчисленного множества оптимальных планов.

Итак, в таблице 2.4 получили оптимальный план

Х^* = , для которого значение целевой функции равно

F(X^*) = 2 · 70 + 4 · 40 + 7 · 40 + 2 · 10 + 1 · 40 = 640.

Десять тонн топлива, находящегося в хранилище А₂, осталось нераспределенным.