Построение совмещенного графика взаимодействия транспорта

СОДЕРЖАНИЕ

 

Введение                       3

Практическая часть                      3

1. Определение минимального расстояния методом ветвей и границ              5
2. Выбор экономически целесообразного способа поездки коммивояжера            12
3. Сравнительная оценка выбора транспорта                14
4. Построение совмещенного графика взаимодействия транспорта             18

Выводы                     19

Список литературы                    20 
  

Введение

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

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

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

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

- определить минимальное  расстояние методом ветвей и  границ,

- сделать выбор экономически  целесообразного способа поездки  коммивояжера,

- провести сравнительную  оценку выбора транспорта,

-  построить совмещенный  график взаимодействия транспорта.

 

 

Практическая часть

Постановка задачи

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

1. Используя метод ветвей и границ, определить в каком порядке следует объезжать пункты, чтобы расстояние было минимальным.
2. Выбрать экономически целесообразный способ поездки коммивояжера по рассчитанному маршруту, сравнив технико-экономические характеристики железнодорожного, воздушного и автомобильного транспорта.
3. Рассчитать и сравнить:

- продолжительность (время) следования коммивояжера по маршруту  при использовании различных  видов транспорта;

- материальные затраты  на поездку;

- стоимость пассажиро-часов пребывания коммивояжера в пути.

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

 

i j	1	2	3	4	5	6
1	Х	150	100	128	80	183
2	55	Х	108	71	96	157
3	70	45	Х	149	81	66
4	120	53	66	Х	88	87
5	68	76	75	38	Х	128
6	100	80	60	43	94	Х

 

 

1.1. Определение  минимального расстояния методом  ветвей и границ

 

 

Возьмем в качестве произвольного маршрута:

X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)

Тогда F(X0) = 150 + 108 + 149 + 88 + 128 + 100 = 723

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

di = min(j) dij

i  j	1	2	3	4	5	6	di
1	Х	150	100	128	80	183	80
2	55	Х	108	71	96	157	55
3	70	45	Х	149	81	66	45
4	120	53	66	Х	88	87	53
5	68	76	75	38	Х	128	38
6	100	80	60	43	94	Х	43

 

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i  j	1	2	3	4	5	6
1	Х	70	20	48	0	103
2	0	Х	53	16	41	102
3	25	0	Х	104	36	21
4	67	0	13	Х	35	34
5	30	38	37	0	Х	90
6	57	37	17	0	51	Х

 

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

dj = min(i) dij

i  j	1	2	3	4	5	6
1	Х	70	20	48	0	103
2	0	Х	53	16	41	102
3	25	0	Х	104	36	21
4	67	0	13	Х	35	34
5	30	38	37	0	Х	90
6	57	37	17	0	51	Х
dj	0	0	13	0	0	21

 

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.

 

i  j	1	2	3	4	5	6
1	Х	70	7	48	0	82
2	0	Х	40	16	41	81
3	25	0	Х	104	36	0
4	67	0	0	Х	35	13
5	30	38	24	0	Х	69
6	57	37	4	0	51	Х

 

Сумма констант приведения определяет нижнюю границу H:

H = ∑di + ∑dj

H = 80+55+45+53+38+43+0+0+13+0+0+21 = 348

Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.

Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij ≥ 0

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

Длина маршрута определяется выражением:

F(Хk) = ∑dij

Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.

Шаг №1.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

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

i  j	1	2	3	4	5	6	di
1	Х	70	7	48	0(42)	82	7
2	0(41)	Х	40	16	41	81	16
3	25	0(0)	Х	104	36	0(13)	0
4	67	0(0)	0(4)	Х	35	13	0
5	30	38	24	0(24)	Х	69	24
6	57	37	4	0(4)	51	Х	4
dj	25	0	4	0	35	13	0