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

Размещено на http://www.allbest.ru/

Белорусский национальный технический университет

Автотракторный факультет

Кафедра «Экономика и логистика»

Дипломная работа

по дисциплине «Автомобильные перевозки»

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

Исполнитель: _____________________________________

Студентка 3 курса группы 101031-13

Руководитель: Антюшеня Д.М.

Кандидат экономических наук, доцент

Минск 2015

СОДЕРЖАНИЕ

• Введение
• 1. Экономико-математическая модель транспортной задачи
• 1.1 Определение кратчайших расстояний между пунктами транспортной сети
• 1.2 Построение модели транспортной задачи для заданного варианта перевозок
• 2. Решение транспортной задачи
• 2.1 Построение начального опорного плана транспортной задачи
• 2.2 Нахождение оптимального плана транспортной задачи методом потенциалов
• 3. Маршрутизация перевозок
• 3.1 Разработка рациональных маршрутов перевозки методом совмещённых планов
• 3.2 Оптимальное закрепление маршрутов за АТП
• 4. Расчет маршрутов
• 4.1 Расчёт количества подвижного состава и технико-эксплуатационных показателей его работы для разработанных маршрутов
• 4.2 Расчет нерациональных маятниковых маршрутов для последующей сравнительной характеристики
• 5. Расчёт эффективности разработанного варианта перевозок
• 6. Построение эпюр и схем грузопотоков
• 7. Разработка маршрутов с помощью эпюр и схем
• заключение
• Список использованных источников
• Приложения

ВВЕДЕНИЕ

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

Транспорту принадлежит важная роль в процессе общественного производства, так как обязательным элементом его является перевозка сырья, материалов, полуфабрикатов и готовой продукции. В 2013 г. доля транспорта в валовом внутреннем продукте Республики Беларусь составила 6,4%.

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

Автомобильный транспорт имеет технико-экономические преимущества по сравнению с другими видами транспорта. Это высокая маневренность и способность перевозить грузы «от двери к двери»; высокая скорость доставки груза; срочность и регулярность перевозок; сравнительно малые капитальные вложения при организации перевозок; простая в любых географических и климатических условиях организация технического обслуживания и ремонта автомобилей.

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

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

В рамках поставленной цели решаются следующие задачи:

· определение оптимального варианта грузопотоков с помощью распределительного метода;

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

· расчёт технико-эксплуатационных показателей работы автомобилей на маршрутах;

· расчёт экономической эффективности предлагаемой маршрутной сети перевозки грузов.

Расчёт в курсовом проекте выполнен в соответствии с методическими указаниями, представленными в пособиях [1] и [2].

1. ЭКОНОМИКО-МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ТРАНСПОРТНОЙ ЗАДАЧИ

1.1 ОПРЕДЕЛЕНИЕ КРАТЧАЙШИХ РАССТОЯНИЙ МЕЖДУ ПУНКТАМИ ТРАНСПОРТНОЙ СЕТИ

транспортный задача грузопоток маршрут

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

Модель транспортной сети представляет собой чертеж-схему на плане местности с указанием вершин (пунктов) транспортной сети. Ее построение производится по заданной схеме расположения пунктов, по наличию звеньев сети, соединяющих два соседних пункта, и длине этих звеньев. В нашем курсовом проекте мы использовали готовую схему транспортной сети (вариант №22), которая приведена в Приложении 1.

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

Шаг 1. Начальному пункту, от которого требуется определить кратчайшие расстояния, присваивается потенциал Vi = 0.

Шаг 2. Просматриваются все звенья, начальные пункты i которых имеют потенциал Vi, а для конечных j потенциалы не присвоены. Затем определяются значения потенциалов конечных пунктов j по следующей формуле:

(1.1)

где Vj(i) - потенциал конечного пункта j звена i-j;

lij - длина звена i-j, т.е. расстояние между пунктами i и j.

Из всех полученных потенциалов выбирается потенциал c наименьшим значением, т.е. определяется ;

, (1.2)

где {Vj(i)} - множество значений потенциалов конечных пунктов j звеньев i-j, i-м начальным пунктом которых ранее присвоены потенциалы;

{Vj'(i')} - потенциал конечного пункта j' звена i'-j', являвшийся наименьшим по значению элементом множества {Vj(i)}.

Потенциал {Vj'(i')} присваивается соответствующему конечному пункту j', а звено i'-j' отмечается звездочкой.

В случае, если несколько значений потенциалов множества {Vj(i)} окажутся равными и наименьшими, то необходимо установить, относятся они к одному и тому же пункту или нет. Когда наименьшие равные значения потенциалов относятся к paзличным конечным пунктам j', то эти значения потенциалов присваивается всем соответствующим конечным пунктам j' и отмечаются звездочками соответствующие значения i'-j'. Если наименьшие равные значения потенциалов относятся к одному и тому же конечному пункту j', то пункту j' присваивается это наименьшее значение потенциала и отмечается звездочкой то звено i'-j', которому соответствует потенциал Vj'(i') с большим удельным весом в его составе длин звеньев с лучшими дорожными условиями (при одинаковых дорожных условиях отмечается стрелкой любое из звеньев ).

Шаг 2 повторяется до тех пор, пока всем вершинам заданной сети не будут присвоены потенциалы.

Ниже приведены таблицы расчета для пунктов А1 - Б5 транспортной сети.

Таблица 1.1- Расчет кратчайших расстояний для пункта А1

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(0, ?)*	(?, А1 )	(?, А1)	(?, А1)	(?, А1)	(10, А1)	(4, А1)	(3, А1)	(?, А1)	(14, А1)
2		(27, Б3)	(?, А1)	(8, Б3)	(?, А1)	(10, А1)	(4, А1)	(3, А1)*	(?, А1)	(14, А1)
3		(22, Б2)	(8, Б2)	(8, Б3)	(20, Б2)	(8, Б2)	(4, А1)*		(?, А1)	(14, А1)
4		(22, Б2)	(8, Б2)*	(8, Б3)	(20, Б2)	(8, Б2)			(15, А3)	(14, А1)
5		(22, Б2)		(8, Б3)*	(20, Б2)	(8, Б2)			(15, А3)	(14, А1)
6		(22, Б2)			(16, Б1)	(8, Б2)*			(15, А3)	(14, А1)
7		(22, Б2)			(16, Б1)				(15, А3)	(14, А1)*
8		(22, Б2)			(16, Б1)				(15, А3)*
9		(22, Б2)			(16, Б1)*
10		(22, Б2)*

Таблица 1.2- Расчет кратчайших расстояний для пункта А2

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(?, А2)	(0, - )*	(?, А2)	(?, А2)	(?, А2)	(?, А2)	(18, А2)	(24, А2)	(26, А2)	(14, А2)
2	(28, Б5)		(37, Б5)	(36, Б5)	(?, А2)	(?, А2)	(18, А2)	(24, А2)	(26, А2)	(14, А2)*
3	(22, Б2)		(22, Б2)	(32, Б2)	(34, Б2)	(22, Б2)	(18, А2)*	(24, А2)	(26, А2)
4	(22, Б2)*		(22, Б2)	(32, Б2)	(34, Б2)	(22, Б2)		(24, А2)	(26, А2)
5			(22, Б2)*	(32, Б2)	(34, Б2)	(22, Б2)		(24, А2)	(26, А2)
6				(32, Б2)	(30, Б1)	(22, Б2)*		(24, А2)	(26, А2)
7				(29, Б3)	(30, Б1)			(24, А2)*	(26, А2)
8				(29, Б3)	(30, Б1)				(26, А2)*
9				(29, Б3)*	(30, Б1)
10					(30, Б1)*

Таблица 1.3- Расчет кратчайших расстояний для пункта А3

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

Таблица 1.4- Расчет кратчайших расстояний для пункта А4

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(?, А4)	(?, А4)	(?, -)	(0, - )*	(?, -)	(14, А4)	(14, А4)	(22, А4)	(28, А4)	(22, А4)
2	(24, Б1)	(?, А4)*	(20, Б1)		(22, Б1)	(14, А4)*	(14, А4)	(22, А4)	(28, А4)	(22, А4)
3	(18, Б2)	(32, Б2)	(18, Б2)		(22, Б1)		(14, А4)*	(22, А4)	(28, А4)	(22,А4)
4	(18, Б2)*	(32, Б2)	(18, Б2)		(22, Б1)			(21, А1)	(28, А4)	(22,А4)
5		(32, Б2)	(18, Б2)*		(22, Б1)			(21, А1)	(25, А3)	(22,А4)
6		(32, Б2)			(22, Б1)			(21, А1)*	(25, А3)	(22,А4)
7		(32, Б2)			(22, Б)*				(25, А3)	(22,А4)
8		(32, Б2)							(25, А3)	(22,А4)*
9		(32, Б2)							(25, А3)*
10		(32, Б2)*

Таблица 1.5- Расчет кратчайших расстояний для пункта А5

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(?, -)	(?, А5)	(?, -)	(?, -)	(0, - )*	(8, А5)	(16, А5)	(?, А5)	(10, А5)	(?, -)
2	(18, Б1)	(?, А5)	(14, Б1)	(22 ,Б1)		(8, А5)*	(12, Б1)	(24, Б1)	(10, А5)	(?, -)
3	(18, Б1)	(36, Б4)	(14 ,Б1)	(22 ,Б1)			(12, Б1)	(24, Б1)	(10, А5)*	(?, -)
4	(16,Б2)	(30, Б2)*	(14 ,Б1)	(22 ,Б1)			(12, Б1)*	(24, Б1)		(28, Б2)
5	(16,Б2)	(30, Б2)	(14 ,Б1)*	(22 ,Б1)				(24, Б1)		(28, Б2)
6	(16,Б2)*	(30, Б2)		(22 ,Б1)				(19, А1)		(28, Б2)
7		(30, Б2)		(22 ,Б1)				(19, А1)*		(28, Б2)
8		(30, Б2)		(22 ,Б1)*						(28, Б2)
9		(30, Б2)*								(28, Б2)
10										(28, Б2)*

Таблица 1.6- Расчет кратчайших расстояний для пункта Б1

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(10, Б1)	(? , -)	(6, Б1)	(14, Б1)	(8, Б1)	(0, - )*	(4, Б1)	(?, -)	(?, -)	(?, -)
2	(8, Б2)	(22, Б2)	(6, Б1)	(14, Б1)	(8, Б1)		(4, Б1)	(?, -)	(?, -)	(20, Б2)
3	(8, Б2)	(22, Б2)	(6, Б1)*	(14, Б1)	(8, Б1)			(?, -)	(13, А3)	(20, Б2)
4	(8, Б2)*	(22, Б2)		(14, Б1)	(8, Б1)			(11, А1)	(13, А3)	(20, Б2)
5		(22, Б2)		(14, Б1)	(8, Б1)*			(11, А1)	(13, А3)	(20, Б2)
6		(22, Б2)		(14, Б1)				(11, А5)*	(13, А3)	(20, Б2)
7		(22, Б2)		(14, Б1)					(13, А3)*	(20, Б2)
8		(22, Б2)		(14, Б1)*						(20, Б2)
9		(22, Б2)								(20, Б2)*
10		(22, Б2)*

Таблица 1.7- Расчет кратчайших расстояний для пункта Б2

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(4, Б2)	(18, Б2)	(4,Б2)	(14, Б2)	(16, Б2)	(4, Б2)	(0, - )*	(?, -)	(?, Б2)	(16, Б2)
2	(4, Б2)*	(18, Б2)	(4,Б2)	(14, Б2)	(16,Б2)	(4, Б2)		(7, А1)	(?, Б2)	(16, Б2)
3		(18 ,Б2)	(4, Б2)*	(14, Б2)	(16,Б2)	(4, Б2)		(7, А1)	(11, А3)	(16, Б2)
4		(18, Б2)		(14, Б2)	(12 ,Б1)	(4, Б2)*		(7, А1)	(11, А3)	(16, Б2)
5		(18, Б2)		(12, Б3)	(12 ,Б1)			(7, А1)*	(11, А3)	(16, Б2)
6		(18, Б2)		(12, Б3)	(12 ,Б1)				(11, А3)*	(16, Б2)
7		(18, Б2)		(12, Б3)*	(12 ,Б1)					(16, Б2)
8		(18, Б2)			(12 ,Б1)					(16, Б2)
9		(18, Б2)								(16, Б2)*
10		(18, Б2)*

Таблица 1.8- Расчет кратчайших расстояний для пункта Б3

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(3,Б3)	(24, Б3)	(?, Б3)	(5, Б3)	(?, Б3)	(16, Б3)	(?, -)	(0, - )*	(?, -)	(?, -)
2	(3,А2)	(24, Б3)	(?, Б3)	(5, Б3)	(?, Б3)	(13, А1)	(7, А1)		(?, А2)	(17, А1)
3		(24, Б3)	(?, Б3)*	(5, Б3)*	(?, Б3)	(13, А1)	(7, А1)		(33,А4)	(17, А1)
4		(24, Б3)	(11, Б2)		(23, Б2)	(11, Б2)	(7, А1)*		(33,А4)	(17, А1)
5		(24, Б3)	(11, Б2)*		(23, Б2)	(11, Б2)			(18,А3)	(17, А1)
6		(24, Б3)			(19, Б1)	(11, Б2)*			(18,А3)	(17, А1)
7		(24, Б3)			(19, Б1)				(18,А3)	(17, А1)*
8		(24, Б3)			(19, Б1)				(18,А3)*
9		(24, Б3)			(19, Б1)*
10		(24, Б3)*

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

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(?, Б4)	(26, Б4)	(7, Б4)	(28, Б4)	(10, Б4)	(?, -)	(?, Б4)	(?, -)	(0, - )*	(?, -)
2	(?, Б4)*	(26, Б4)	(7, Б4)*	(28, Б4)	(10, Б4)	(13, А3)	(11, А3)	(?, -)		(30,А3)
3	(?, Б4)	(26, Б4)		(28, Б4)	(10, Б4)*	(13, А3)	(11, А3)	(?, -)		(30,А3)
4	(15, Б2)	(26, Б4)		(24, Б2)		(13, А3)	(11, А3)*	(?, -)		(27, Б2)
5	(15, Б2)	(26, Б4)		(24, Б2)		(13, А3)*		(29, Б1)		(27, Б2)
6	(15, Б2)*	(26, Б4)		(24, Б2)				(18, А1)		(27, Б2)
7		(26, Б4)		(23, Б3)				(18, А1)*		(27, Б2)
8		(26, Б4)		(23, Б3)*						(27, Б2)
9		(26, Б4)*								(27, Б2)
10										(27, Б2)*

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

№ шага	Пункты транспортной сети
	А1	А2	А3	А4	А5	Б1	Б2	Б3	Б4	Б5
1	(14, Б5)	(14, Б5)	(23, Б5)	(22, Б5)	(?, -)	(?, -)	(16, Б5)	(?, -)	(?, -)	(0, - )*
2	(14, Б5)*	(14, Б5)	(23, Б5)	(22, Б5)	(?, -)	(24, А1)	(16, Б5)	(17, А1)	(?, -)
3		(14, Б5)*	(23, Б5)	(22, Б5)	(?, -)	(24, А1)	(16, Б5)	(17, А1)	(40, А2)
4			(20,Б2)	(22, Б5)	(32, Б2)	(20, Б2)	(16, Б5)*	(17, А1)	(40, А2)
5			(20,Б2)	(22, Б5)	(32, Б2)	(20, Б2)		(17, А1)*	(40, А2)
6			(20,Б2)*	(22, Б5)	(32, Б2)	(20, Б2)			(27, А3)
7				(22, Б5)	(28, Б1)	(20, Б2)*			(27, А3)
8				(22, Б5)*	(28, Б1)				(27, А3)
9					(28, Б1)				(27, А3)*
10					(28, Б1)*

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

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

1.2 ПОСТРОЕНИЕ МОДЕЛИ ТРАНСПОРТНОЙ ЗАДАЧИ ДЛЯ ЗАДАННОГО ВАРИАНТА ПЕРЕВОЗОК

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

Если обозначить объем выхода груза от некоторого поставщика через Qi, требуемый объем завоза груза некоторому потребителю через Qj, объем груза, перевозимого от i-го поставщика к j-му потребителю, через Qij и кратчайшее расстояние перевозки от i-го поставщика до j-го потребителя через lij, то математическая модель поставленной задачи имеет вид:

(1.3)

(1.4)

(1.5)

(1.6)

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

(1.7)

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

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

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

Грузопотоки	Род груза	Объем перевозок, т	Класс груза
Из пункта	В пункт
А1	Б1	Грунт	500	1(навалом)
А2	Б2	Песок	1000	1(навалом)
А3	Б2	Щебень	250	1(навалом)
А4	Б3	Песок	1000	1(навалом)
А5	Б4	Песок	1000	1(навалом)

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

 (1.8)

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

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

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

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

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

Пункт отправления	Пункт получения	Перевозки по видам груза	Коэффициент статического использования грузоподъемности для данного вида груза, гс	Число ездок, приведенных к первому классу груза, ху
		Вид груза	Объем перевозок Qy, т
А1	Б1	Грунт	500	1,0	50
А2	Б2	Песок	1000	1,0	100
А3	Б2	Щебень	250	1,0	25
А4	Б3	Песок	1000	1,0	100
А5	Б4	Песок	1000	1,0	100

В клетках матрицы транспортной задачи указывается расстояние перевозки и приведенный к первому классу объём грузов в тоннах по отправителям и получателям. Таким образом завершается построение так называемой "специальной таблицы" транспортной задачи, представленной в виде таблицы 1.14.

Таблица 1.14 - Специальная таблица транспортной задачи

Грузополучатель	Грузоотправитель	Объем завоза, bi, т
	А1	А2	А3	А4	А5
Б1	8	22	6	14	8	500
Б2	4	18	4	12	12	1250
Б3	3	24	11	5	19	1000
Б4	15	26	7	23	10	1000
Объем вывоза аi, т	500	1000	250	1000	1000	3750

2. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

2.1 ПОСТРОЕНИЕ НАЧАЛЬНОГО ОПОРНОГО ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ

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

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

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

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

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

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

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

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

Грузополучатель	Грузоотправитель	Объем завоза, bi, т
	А1	А2	А3	А4	А5
Б1	- 8	- 22	- 6	- 14	50 8	500
Б2	- 4	50 18	25 4	50 12	- 12	1250
Б3	50 3	- 24	- 11	50 5	- 19	1000
Б4	- 15	50 26	- 7	- 23	50 10	1000
Объем вывоза аi, т	500	1000	250	1000	1000	3750

2.2 НАХОЖДЕНИЕ ОПТИМАЛЬНОГО ПЛАНА ТРАНСПОРТНОЙ ЗАДАЧИ МЕТОДОМ ПОТЕНЦИАЛОВ

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

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

(2.1)

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

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

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

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

Проверка исходного опорного плана перевозок на оптимальность представлена в таблице 2.2. Суммарный холостой пробег автомобилей составляет 3800 км. План не оптимален, т.к. имеются отрицательные оценки. В связи с этим для клетки с минимальным отрицательным потенциалом (А3, Б4) составлен цикл для перехода к следующему (улучшенному) опорному плану. Соответствующие клетки цикла помечаются попеременно "+" и "-", а их значения соответственно увеличиваются или уменьшаются.

Таблица 2.2 - Проверка начального опорного плана на оптимальность и переход к следующему плану перевозок.

Грузополучатель	Грузоотправитель	Потенциалы Vj
	А1	А2	А3	А4	А5
Б1	- 8	- 22	- 6	- 14	50 8	6
Б2	- 4	50 18	25 4	50 12	- 12	0
Б3	50 3	- 24	- 11	50 5	- 19	-7
Б4	- 15	50 26	- 7	- 23	50 10	0
Потенциалы ui	10	18	4	12	2

Полученный опорный план перевозок, а также его проверка на оптимальность представлены в таблице 2.3. Суммарный холостой пробег автомобилей составляет 3750 км. План снова не оптимален, т.к. всё ещё имеются отрицательные оценки. В связи с этим для клетки с минимальным отрицательным потенциалом (А1, Б1) составлен цикл для перехода к следующему (улучшенному) опорному плану.

Полученный опорный план перевозок, а также его проверка на оптимальность представлены в таблице 2.4. План снова не оптимален, т.к. всё ещё имеются отрицательные оценки. В связи с этим для клетки с минимальным отрицательным потенциалом (А1, Б2) составлен цикл для перехода к следующему (улучшенному) опорному плану.

Таблица 2.3 - Проверка улучшенного опорного плана на оптимальность и переход к следующему плану перевозок

Грузополучатель	Грузоотправитель	Потенциалы Vj
	А1	А2	А3	А4	А5
Б1	50 8	- 22	- 6	- 14	0 8	-2
Б2	- 4	100 18	25 4	0 12	- 12	0
Б3	0 3	- 24	- 11	100 5	- 19	-7
Б4	- 15	- 26	- 7	- 23	100 10	0
Потенциалы ui	10	8	4	12	10

Таблица 2.4 - Проверка улучшенного опорного плана на оптимальность и переход к следующему плану перевозок

Грузополучатель	Грузоотправитель	Потенциалы Vj
	А1	А2	А3	А4	А5
Б1	50 8	- 22	- 6	- 14	0 8	4
Б2	0 4	100 18	25 4	- 12	- 12	0
Б3	0 3	- 24	- 11	100 5	- 19	-1
Б4	- 15	- 26	- 7	- 23	100 10	6
Потенциалы ui	4	18	4	6	4

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

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

Грузополучатель	...

Подобные документы

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

  Применение математического метода линейного программирования для получения максимальной производительности автомобиля. Разработка маршрутов методом совмещенных планов. Расчет эффективности разработанного варианта перевозок. Построение схем грузопотоков.
  
  курсовая работа [582,6 K], добавлен 05.01.2015
  

• Разработка транспортного процесса на основе математических методов линейного программирования и построения эпюр грузопотоков

  Решение транспортной задачи методом линейного программирования, нахождение кратчайших расстояний. Закрепление маршрутов за АТП. Расчёт эффективности разработанного варианта перевозок. Построение эпюр и схем грузопотоков. Расчет тарифов на перевозку груза.
  
  курсовая работа [289,9 K], добавлен 30.12.2010
  

• Разработка транспортного процесса на основе математических методов линейного программирования и построения эпюр грузопотоков

  Решение транспортной задачи. Нахождение оптимального варианта организации транспортного процесса с помощью математического метода линейного программирования для получения максимальной производительности автомобиля и минимальной себестоимости перевозок.
  
  курсовая работа [341,7 K], добавлен 17.06.2015
  

• Разработка транспортного процесса перевозки грузов

  Маршрутизация перевозок с использованием экономико-математических методов. Решение задачи методом линейного программирования. Разработка маршрутов перевозок грузов. Расчет эффективности разработанного варианта. Построение эпюр и схем грузопотоков.
  
  курсовая работа [379,7 K], добавлен 30.12.2010
  

• Организация перевозок грузов автомобильным транспортом

  Экономические, организационные и технические задачи оптимизации грузопотоков. Разработка карты рациональных маршрутов перевозок. Расчет технико-эксплуатационных показателей работы подвижного состава. Создание и внедрение АСУ автомобильными перевозками.
  
  дипломная работа [2,5 M], добавлен 05.09.2016
  

• Методика определения технико-эксплуатационных показателей работы подвижного состава

  Методика расчета технико-эксплуатационных показателей работы подвижного состава. Определение производственной программы по перевозкам для транспортной сети, количества водителей для выполнения данного объема перевозок, ТЭП работы подвижного состава.
  
  контрольная работа [86,6 K], добавлен 25.12.2011
  

• Решение задачи поиска оптимального маршрута грузоперевозок. Сетевые задачи

  Вид сетевой транспортной задачи. Алгоритм решения: построение начального базисного сетевого потока, поиск потенциалов, проверка оптимальности, добавление дуг, поиск цикла, построение потока, формирование множества дуг. Графическое представление задачи.
  
  презентация [266,8 K], добавлен 07.03.2013
  

• Организация грузовых перевозок

  Анализ транспортной сети и обьема перевозок. Определение кратчайших расстояний между пунктами транспортной сети, минимизация груженных и холостых пробегов. Составление кольцевых маршрутов и подвижного состава; расчет его количества и показателей работы.
  
  курсовая работа [1,3 M], добавлен 14.03.2014
  

• Транспортный процесс и производительность подвижного состава

  Ознакомление с технико-эксплуатационными показателями работы автомобилей. Рассмотрение результатов решения задачи маршрутизации методом потенциалов. Анализ технологического расчета маршрутов. Характеристика сводных показателей сменно-суточного пробега.
  
  курсовая работа [462,7 K], добавлен 29.10.2017
  

• Эффективное использование автомобиля при перевозках груза

  Расчет количества поставщиков и потребителей, основанный на методах линейного программирования. Планирование рациональных маршрутов методом двойного предпочтения. Разработка маятникового и кольцевого маршрутов. Технические характеристики самосвала МАЗ.
  
  курсовая работа [52,8 K], добавлен 16.01.2011
  

• Организация автомобильных перевозок

  Характеристика заданных грузопотоков и составление маршрутов их перевозок. Выбор и обоснование подвижного состава. Выбор типа погрузо-разгрузочных машин и устройств. Разработка графика выпуска и возврата автомобилей, технико-эксплуатационных показателей.
  
  курсовая работа [348,9 K], добавлен 28.06.2011
  

• Технология и организация автомобильных перевозок

  Организация работы подвижного состава на линии. Характеристика дорожных условий. Шахматные таблицы грузопотоков. Построение маршрутов и привязка их к АТП для массовых перевозок. Расчет показателей работы автомобилей. График работы водителей на маршруте.
  
  курсовая работа [1,3 M], добавлен 28.09.2013
  

• Грузовые перевозки

  Выбор подвижного состава для перевозки груза. Определение кратчайших расстояний между пунктами транспортной сети. Разработка плана рациональных маршрутов. Расчет времени на выполнение погрузочно-разгрузочных работ. Маршрутная карта перевозок грузов.
  
  курсовая работа [907,3 K], добавлен 09.04.2011
  

• Технология автотранспортного производства

  Составление сводного плана грузопотоков, координация движения подвижного состава. Маятниковые передвижения транспорта при перевозке грузов. Составление схем двухзвенных и трехзвенных маршрутов, определение порожнего пробега, расчет потребности в машинах.
  
  контрольная работа [685,2 K], добавлен 16.04.2013
  

• Расчёт технико-эксплуатационных показателей работы подвижного состава

  Транспортная характеристика груза. Выбор подвижного состава и определение его технико-эксплуатационных показателей. Описание и выбор схемы маршрута перевозки. Определение количества водителей и рабочего времени для выполнения данного объёма перевозок.
  
  практическая работа [549,3 K], добавлен 10.04.2013
  

• Задачи и функции закупочной логистики. Выбор подвижного состава и организация маршрутов

  Анализ основ экономической эффективности закупочной логистики. Изучение рынка закупок товаров производственного назначения. Определение потребностей на основе заказов. Расчет работы подвижного состава на маршрутах, количества оборотов за время в наряде.
  
  контрольная работа [30,8 K], добавлен 26.10.2013
  

• Тенденции и перспективы транспортно-логистической системы Республики Беларусь

  Маршрутизация автомобильных и железнодорожных перевозок. Методика определения кратчайших расстояний между пунктами транспортной сети с использованием метода потенциалов. Проблемы при построении маршрутов перевозок и автоматизация транспортной логистики.
  
  курсовая работа [183,4 K], добавлен 01.10.2015
  

• Внедрение новых пассажирских маршрутов

  Проектирование транспортной сети и расчет времени, затрачиваемого пассажирами на перемещение. Описание предлагаемых маршрутов. Вычисление потребного количества автобусов на маршруте по часам суток. Конструкция и устройство подъемника гидравлического.
  
  дипломная работа [308,5 K], добавлен 02.10.2013
  

• Разработка технологического процесса перевозки скоропортящихся грузов (замороженная рыба) автомобильным транспортом

  Составление схемы маршрутов движения автомобилей. Построение эпюры грузопотоков. Выбор погрузочно-разгрузочных машин. Определение основных технико-эксплуатационных показателей по маршруту перевозки грузов. Требования по организации работы грузопунктов.
  
  курсовая работа [1,8 M], добавлен 08.04.2016
  

• Выбор рационального варианта грузоперевозок

  Формирование маршрутов перевозок, выбор типа подвижного состава и расчет грузооборота. Расчет времени и скорости доставки грузов. Расчет технико-эксплуатационных и экономических показателей использования транспортных средств различных видов транспорта.
  
  курсовая работа [997,7 K], добавлен 25.12.2010
  

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам