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

Таблица 1.9. – Расчет кратчайших расстояний для пункта Б4

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(14,Б4)	(17, Б4)	(15, Б4)	(∞, −)	(20, Б4)	(15, Б4)	(∞, −)	(∞, −)	(0, −)*	(∞, −)
2	(14,Б4)*	(17, Б4)	(15, Б4)	(∞, −)	(20, Б4)	(15, Б4)	(33, А1)	(40, А1)		(∞, −)
3		(17, Б4)	(15, Б4)*	(∞, −)	(20, Б4)	(15, Б4)	(23, А1)	(40, А1)		(25, А3)
4		(17, Б4)		(30, Б1)	(20, Б4)	(15, Б4)*	(23, А1)	(40, А1)		(22, Б1)
5		(17, Б4)*		(30, Б1)	(20, Б4)		(23, А1)	(23, А2)		(22, Б1)
6				(30, Б1)	(20, Б4)*		(23, А1)	(23, А2)		(22, Б1)
7				(30, Б1)			(23, А1)	(23, А2)		(22, Б1)*
8				(30, Б1)			(23, А1)*	(23, А2)
9				(30, Б1)				(23, А2)*
10				(30, Б1)*

 

Таблица 1.10. – Расчет кратчайших расстояний для пункта Б5

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(10, Б5)	(14, Б5)	(22, Б5)	(∞, −)	(∞, −)	(∞, −)	(16, Б5)	(∞, −)	(∞, −)	(0, −)*
2	(10, Б5)*	(14, Б5)	(22, Б5)	(18, А1)	(∞, −)	(26, А1)	(16, Б5)	(34, А1)	(20, А1)
3		(14, Б5)*	(22, Б5)	(18, А1)	(23, А2)	(26, А1)	(16, Б5)	(32, А2)	(20, А1)
4			(20, Б2)	(18, А1)	(23, А2)	(26, А1)	(16, Б5)*	(32, А2)	(20, А1)
5			(20, Б2)	(18, А1)*	(23, А2)	(26, А1)		(32, А2)	(20, А1)
6			(20, Б2)*		(23, А2)	(26, А1)		(32, А2)	(20, А1)
7					(23, А2)	(26, А1)		(32, А2)	(20, А1)*
8					(23, А2)*	(26, А1)		(32, А2)
9						(26, А1)*		(32, А2)
10								(32, А2)*

Таблица 1.11. – Кратчайшие расстояния между пунктами транспортной сети (км)

 

	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
А1	0	22	18	27	26	12	19	26	14	19
А2	22	0	16	16	15	10	24	6	17	8
А3	18	16	0	18	20	6	8	20	15	10
А4	27	16	18	0	20	15	10	18	30	8
А5	26	15	20	20	0	14	28	9	20	12
Б1	12	10	6	15	14	0	14	16	15	7
Б2	19	24	8	10	28	14	0	28	23	18
Б3	26	6	20	18	9	16	28	0	23	10
Б4	14	17	15	30	20	15	23	23	0	22
Б5	19	8	10	8	12	7	10	10	22	0

 

 

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

 

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

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

      

      

     

                                        

      

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

                                       

     

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

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

 

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

Грузопотоки		Род груза	Объем перевозок, т	Класс груза
из пункта	в пункт
А4	Б1	кирпич	1000	I, навалом
А5	Б5	силик. кирпич	1250	I, навалом
А3	Б5	кирпич	1000	I, навалом
А2	Б4	кирпич	1250	I, навалом
А1	Б3	кирпич	1500	I, навалом
ИТОГО:			6000

 

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

      (1.8)

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

- грузоподъемность автомобиля;

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

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

 

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

Пункт отправления	Пункт получения	Перевозки по видам  груза		Коэфф. статического использования грузоподъемности для данного груза,	Число ездок, приведенных к 1-му классу груза
		Вид груза	Объем перевозок Qij,т
А4	Б1	кирпич	1000	1	100
А5	Б5	сил. кирпич	1250	1	125
А3	Б5	кирпич	1000	1	100
А2	Б4	кирпич	1250	1	125
А1	Б3	кирпич	1500	1	150

 

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

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