1.2 Решение транспортной задачи

Задача на минимизацию транспортной работы состоит в определении оптимального варианта закрепления получателей за поставщиками однородной продукции.

Если обозначить объем выхода груза от некоторого поставщика через Q_i, требуемый объем завоза груза некоторому потребителю через Q_j, объем груза, перевозимого от i-го поставщика к j-му потребителю, через Q_ij и кратчайшее расстояние перевозки от i-го поставщика до j-го потребителя через l_ij, то поставленная задача в математической форме имеет вид:

(1.3)

(1.4)

(1.5)

(1.6)

В случае, если количество груза у поставщиков равно общему объему завоза груза всем потребителям, то имеет место условие:

(1.7)

Поставленная таким образом задача (ограничения (1.3), (1.4), (1.6), (1.7) и целевая функция (1.5)) является закрытой моделью классической транспортной задачи линейного программирования, в результате решения которой по известным значениям находятся неизвестные значения корреспонденций . Для составления транспортной задачи из исходных данных выбираются грузы, перевозимые одним типом подвижного состава. Таковыми являются овощи, фрукты и консервы, перевозимые фургонами (табл. 1.3).

Таблица 1.3 - Грузы, перевозимые одним типом подвижного состава

Грузопотоки		Род груза	Объем перевозок, т	Класс груза
из пункта	в пункт
А1	Б3	грунт	1500	1
А2	Б5	щебень	1250	1
А3	Б1	брикет	1000	1
А4	Б4	земля	500	1
А5	Б4	щебень	250	1
А2	Б2	песок	750	1

Для решения транспортной задачи объемы перевозок приводятся к грузам 1-го класса по следующей формуле:

(1.8)

где - объем перевозок, указанный в плане,

- коэффициент использования грузоподъемности (для 1-го класса – 1, для второго – 0,8, для третьего – 0,6, для четвертого – 0,5).

Подготовка исходных данных для их занесения в матрицу транспортной задачи проводится в табличной форме:

Таблица 1.4 – Подготовка исходных данных для маршрутизации перевозок грузов

Пункт отправ-ления	Пункт полу-чения	Перевозки по видам груза		Коэфф. исполь-зования грузо-подъемности для данного груза,	Объем перевозок приведенный к 1-му классу груза , т
		Вид груза	Объем перевозок Qijk,т
А1	Б3	грунт	1500	1	1500
А2	Б5	щебень	1250	1	1250
А3	Б1	брикет	1000	1	1000
А4	Б4	земля	500	1	500
А5	Б4	щебень	250	1	250
А2	Б2	песок	750	1	750

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

Для отыскания оптимального закрепления потребителей за поставщиками необходимо сделать в полученной таблице первоначальное закрепление, т. е. получить произвольный план закрепления (опорный), удовлетворяющий ограничениям (1.3), (1.4), (1.6), (1.7) при количестве загруженных клеток m+n-1 и отсутствии циклов (контуров). Такой план, содержащий ровно m+n-1 заполненных клеток без циклов, называется базисным.

Цикл (контур) в распределительной таблице - это замкнутая ломаная линия, образованная прямыми отрезками, углы между которыми равны 90, а вершины углов лежат в загруженных клетках. Контур может быть четырехугольным, шестиугольным, восьмиугольным и т. д. Если число загруженных клеток более m+n-1, то среди них есть цикл.

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

Распределение груза рекомендуется производить методом минимального элемента, как одним из наиболее простых и эффективных.

В соответствии с этим методом опорный план составляется по следующему правилу: выбирается минимальное расстояние, клетки загружаются объемами перевозок Q_ij, пока не будут удовлетворены ограничения по вывозу и завозу груза. Объем груза Q_ij, заносимый в клетку ij, определяется как минимум от объема вывоза по строке и объема завоза по столбцу с учетом ранее назначенных других перевозок. Выбор загрузки именно таким образом обусловлен тем, что, во-первых, необходимо переправить как можно больше груза по маршруту с наименьшим расстоянием, во-вторых, невозможно переправить груза больше, чем имеется у данного грузоотправителя, в-третьих, не должно пересылаться грузополучателю больше груза, чем ему требуется. Выбранное значение и будет представлять собой загрузку данной клетки.

Оставшиеся загрузки проставляются по возможности в клетки с наименьшими расстояниями. При проставлении загрузок необходимо соблюдать условия, оговоренные выше.

Таблица 1.5 - План перевозок грузов

Грузопо- лучатель	Грузоотправитель
	А1		А2		А3		А4		А5		∑получ
Б1		6		19		6		25		22	100
	100
Б2		24		9		14		24		29	75
			75
Б3		20		9		25		11		18	150
	0		125				25
Б4		10		12		22		15		3	75
	50								25
Б5		17		23		29		17		5	125
	0				100		25
∑отпр	100		75		150		75		125		525

Далее проверяется полученный план перевозок на оптимальность. В таблицу транспортной задачи вводятся вспомогательные строка и столбец, в которые заносятся специальные показатели, называемые потенциалами. Основан метод потенциалов на том, что если к расстояниям любой строки (столбца) таблицы прибавить или отнять произвольное одно и тоже число, то оценка оптимальности относительно не изменится. Если, например, от расстояний каждой i-ой строки отнимать число u_i и от расстояний каждого j-ого столбца – u_j, то тогда относительной оценкой любой клетки ij может служить параметр u_ij вместо l_ij, рассчитываемый по формуле:

(1.9)

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

Величина параметра u_ij характеризует общее увеличение пробега с грузом, достигаемое при включении в план единицы груза по корреспонденции ij по сравнению с рассматриваемым планом.

Е сли значение оценочного параметра свободной клетки будет меньше нуля то это значит, что перераспределение корреспонденций по клеткам таблицы с занесением объема перевозок в такую свободную клетку, называемую потенциальной, уменьшит значение целевой функции.

Отсутствие клеток со значением параметра U_ij<0, означает, что проверяемый план закрепления потребителей за постановщиками является оптимальным.

Таблица 1.6 - Уточненный план перевозок грузов

Грузопо- лучатель	Грузоотправитель
	А1		А2		А3		А4		А5		∑получ
Б1	-	6		19	-12	6		25		22	100
	100				+
Б2		24		9	-7	14		24		29	75
			75
Б3		20		9		25		11		18	150
	0		125				25
Б4		10		12		22		15		3	75
	50								25
Б5		17		23		29		17		5	125
	0 +				100 -		25
∑отпр	100		75		150		75		125		525

U₁ = -5

U₂ = 0

U₃ =0

U₄ = -1

U₅ = 6

V₁ = 11 V₂ = 9 V₃ =23 V₄ = 11 V₅ = 4

Z= 100*6+75*9+125*9+25*11+50*10+25*3+29*100+25*17=6575

Таблица 1.7 - Уточненный план перевозок грузов

Грузопо- лучатель	Грузоотправитель
	А1		А2		А3		А4		А5		∑получ
Б1		6		19		6		25		22	100
					100 +
Б2		24	-	9	-7	14		24		29	75
			75		+
Б3		20		9		25		11		18	150
	0		125 +				25 -
Б4		10		12		22		15		3	75
	50								25
Б5		17		23		29		17		5	125
	100				0 -		25 +
∑отпр	100		75		150		75		125		525

U₁ = -16

U₂ = 1

U₃ =1

U₄ = 0

U₅ = 7

V₁ = 10 V₂ = 8 V₃ =22 V₄ = 10 V₅ = 3

Z=100*6+75*9+125*9+25*11+50*10+25*3+17*100+25*17=5375

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

Таблица 1.8 - Оптимальный план перевозок грузов

Грузопо- лучатель	Грузоотправитель
	А1		А2		А3		А4		А5		∑получ
Б1		6		19		6		25		22	100
					100
Б2		24		9		14		24		29	75
			75		0
Б3		20		9		25		11		18	150
			125				25
Б4		10		12		22		15		3	75
	50								25
Б5		17		23		29		17		5	125
	100						25
∑отпр	100		75		150		75		125		525

U₁ = -8

U₂ = 0

U₃ =0

U₄ = -1

U₅ = 6

V₁ = 11 V₂ = 9 V₃ =14 V₄ = 11 V₅ = 4

Z=100*6+75*9+125*9+25*11+50*10+25*3+17*100+25*17=5375

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