Решение транспортной задачи с помощью метода линейного программирования

Контур может быть четырехугольным, шестиугольным и восьмиугольным и т.д. Если число загруженных  клеток более m+n-1, то среди них есть цикл.

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

Полученный методом наименьшего  элемента начальный опорный план транспортной задачи представлен в  таблице 1.14.

Таблица 1.14 – Начальный опорный  план перевозок грузов

Грузоотправитель	Грузополучатель								Объем вывоза
	Б1			Б3	Б4	Б5
А1	12		26		125 14		25 19		150
А2	10		125 6		17		8		125
А3	6		20		15		100 10		100
А4	15		18		30		100 8		100
А5	100 4		25 9		20		12		125
Объем завоза	100	150			125	225		600

 

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

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

                                       

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

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

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

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

Поскольку в нашем случае равенство m+n-1 не выполняется, вводится нуль в незагруженную клетку, в данном случае в клетку (B5, A2). Уточненный план перевозок грузов представлен в таблице 1.15.

 

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

Грузоот-прав.	Грузополучатель								Объем вывоза
	Б1			Б3	Б4	Б5
А1	12		26		125 14		25 19		150	19
А2	10		125 6		17		0 8		125	8
А3	6		20		15		100 10		100	10
А4	15		18		30		100 8		100	8
А5	100 4		25 9		20		12		125	11
Объем завоза	100	150			125	225		600
	-7	-2			-5	0

 

 

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

 

2 РАЗРАБОТКА МАРШРУТОВ

2.1 Разработка рациональных маршрутов перевозки методом совмещенных планов

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

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

В тех клетках полученной таблицы совмещенных планов, где  имеются две цифры (выделенная и  невыделенная), получаются маятниковые  маршруты, количество ездок на которых равно минимуму {X_ij, X_ji}, где X_ij - количество ездок с грузом и X_ji – количество ездок без груза. Включенное в маршрут количество ездок с грузом или без груза из дальнейшего рассмотрения исключается.

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

Применим метод совмещенных  планов для данных из таблицы 2.1.

 

 

Таблица 2.1 - Совмещенный план гружёных и порожних ездок

 

Грузоотправители	Грузополучатели
	Б1	Б3		Б4	Б5
А1				125	25
		150
А2		125
				125
А3					100
					100
А4					100
	100
А5	100	25				125

 

Как видно из табл. 2.1, для  данных планов перевозок имеется  один маятниковый маршрут с обратным порожним пробегом А3Б5-Б5А3 (100 ездок).

С помощью построения контуров образуется 3 рациональных кольцевых  маршрута:

 

Таблица 2.2 – Рациональные кольцевые  маршруты

Грузоотправители	Грузополучатели
	Б1	Б3		Б4	Б5
А1				125	25
		150
А2		125
				125
А3					100
					100
А4					100
	100
А5	100	25				125

 

Грузоотправители	Грузополучатели
	Б1	Б3		Б4	Б5
А1				125	25
		150
А2		125
				125
А3					100
					100
А4					100
	100
А5	100	25				125

 

 

Грузоотправители	Грузополучатели
	Б1	Б3		Б4	Б5
А1				125	25
		150
А2		125
				125
А3					100
					100
А4					100
	100
А5	100	25				125

 

После того, как получены маршруты движения при перевозке  груза условными однотонными  автомобилями, разрабатываются схемы  маршрутов перевозки грузов с  указанием конкретных видов грузов и объемом их перевозки, порожних пробегов от пунктов разгрузки в  пункты погрузки. При этом фактическое  количество k-го груза Q_ijk, перевозимого между двумя пунктами, определяется по формуле:

      (2.1)

где X_ijk – количество ездок автомобилей с k-м грузом между этими пунктами.

Так как между двумя  пунктами транспортной сети могут перевозиться несколько видов грузов, то возможен случай, когда будет необходимо маршрут  движения разбить на два или более  маршрутов перевозки грузов, на каждом участке, которого перевозится один вид груза. Для такого маршрута перевозки  грузов должно соблюдаться условие:

      (2.2)

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

Составленные маршруты приведены  в таблицах 2.3 и 2.4.

Таблица 2.3. - Маршруты перевозки заданных грузов

№ маршрута	Наименование маршрута	∑nоб	ze	∑ne	lгр	lx	lобщ	βм
М1	А3Б5-Б5А3	100	1	100	10	10	20	0,5
Р1	А5Б5-Б5А4-А4Б1-Б1А5	100	2	200	27	22	49	0,55
Р2	А5Б5-Б5А1-А1Б3-Б3А5	25	2	50	38		42	0,5
Р3	А1Б3-Б3А2-А2Б4-Б4А1	125	2	250	43	20	63	0,68