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

СОДЕРЖАНИЕ

Введение                       3

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

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

Выводы                     19

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

dj = min(i) dij

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

Сумма констант приведения определяет нижнюю границу 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*).

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

d(1,5) = 7 + 35 = 42; d(2,1) = 16 + 25 = 41; d(3,2) = 0 + 0 = 0; d(3,6) = 0 + 13 = 13; d(4,2) = 0 + 0 = 0; d(4,3) = 0 + 4 = 4; d(5,4) = 24 + 0 = 24; d(6,4) = 4 + 0 = 4; 

Наибольшая сумма констант приведения равна (7 + 35) = 42 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).

Исключение ребра (1,5) проводим путем замены элемента d15 = 0 на Х, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.

Нижняя граница гамильтоновых циклов этого подмножества:

H(1*,5*) = 348 + 42 = 390

Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d51 заменяем на Х, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 0

Нижняя граница подмножества (1,5) равна:

H(1,5) = 348 + 0 = 348  ≤  390

Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут с новой границей H = 348

Шаг №2.

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

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

d(2,1) = 16 + 25 = 41; d(3,2) = 0 + 0 = 0; d(3,6) = 0 + 13 = 13; d(4,2) = 0 + 0 = 0; d(4,3) = 0 + 4 = 4; d(5,4) = 24 + 0 = 24; d(6,4) = 4 + 0 = 4; 

Наибольшая сумма констант приведения равна (16 + 25) = 41 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).

Исключение ребра (2,1) проводим путем замены элемента d21 = 0 на Х, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.

Нижняя граница гамильтоновых циклов этого подмножества:

H(2*,1*) = 348 + 41 = 389

Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d12 заменяем на Х, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 0

Нижняя граница подмножества (2,1) равна:

H(2,1) = 348 + 0 = 348  ≤  389

Чтобы исключить подциклы, запретим следующие переходы: (5,2), 

Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 348

Шаг №3.

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

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

d(3,2) = 0 + 0 = 0; d(3,6) = 0 + 13 = 13; d(4,2) = 0 + 0 = 0; d(4,3) = 0 + 4 = 4; d(5,4) = 24 + 0 = 24; d(6,4) = 4 + 0 = 4; 

Наибольшая сумма констант приведения равна (24 + 0) = 24 для ребра (5,4), следовательно, множество разбивается на два подмножества (5,4) и (5*,4*).

Исключение ребра (5,4) проводим путем замены элемента d54 = 0 на Х, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,4*), в результате получим редуцированную матрицу.

Нижняя граница гамильтоновых циклов этого подмножества:

H(5*,4*) = 348 + 24 = 372

Включение ребра (5,4) проводится путем исключения всех элементов 5-ой строки и 4-го столбца, в которой элемент d45 заменяем на Х, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

Сумма констант приведения сокращенной матрицы:

∑di + ∑dj = 4

Нижняя граница подмножества (5,4) равна:

H(5,4) = 348 + 4 = 352  ≤  372

Чтобы исключить подциклы, запретим следующие переходы: (4,1), (4,2), 

Поскольку нижняя граница этого подмножества (5,4) меньше, чем подмножества (5*,4*), то ребро (5,4) включаем в маршрут с новой границей H = 352

Шаг №4.

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

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