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

СОДЕРЖАНИЕ

Введение

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

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

2. Выбор экономически целесообразного способа поездки коммивояжера

3. Сравнительная оценка выбора транспорта

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

Выводы

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



ВВЕДЕНИЕ

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

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

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

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

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

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

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

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



ПОСТАНОВКА ЗАДАЧИ

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

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

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

3. Рассчитать и сравнить:

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

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

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

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. ОПРЕДЕЛЕНИЕ МИНИМАЛЬНОГО РАССТОЯНИЯ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ

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

X₀ = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)

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

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

d_i = min(j) d_ij

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

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

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	Х



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

d_j = min(i) d_ij

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

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

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 = ?d_i + ?d_j

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

Элементы матрицы d_ij соответствуют расстоянию от пункта i до пункта j. Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d_ij ? 0

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

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

F(Х_k) = ?d_ij

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

Шаг №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

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) проводим путем замены элемента d₁₅ = 0 на Х, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.

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

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

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

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

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

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

i j	1	2	3	4	6	di
2	0	Х	40	16	81	0
3	25	0	Х	104	0	0
4	67	0	0	Х	13	0
5	Х	38	24	0	69	0
6	57	37	4	0	Х	0
dj	0	0	0	0	0	0

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

?d_i + ?d_j = 0

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

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

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

Шаг №2.

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

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

i j	1	2	3	4	6	di
2	0(41)	Х	40	16	81	16
3	25	0(0)	Х	104	0(13)	0
4	67	0(0)	0(4)	Х	13	0
5	Х	38	24	0(24)	69	24
6	57	37	4	0(4)	Х	4
dj	25	0	4	0	13	0

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) проводим путем замены элемента d₂₁ = 0 на Х, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.

i j	1	2	3	4	6	di
2	Х	Х	40	16	81	16
3	25	0	Х	104	0	0
4	67	0	0	Х	13	0
5	Х	38	24	0	69	0
6	57	37	4	0	Х	0
dj	25	0	0	0	0	41

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

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

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

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

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

i j	2	3	4	6	di
3	0	Х	104	0	0
4	0	0	Х	13	0
5	38	24	0	69	0
6	37	4	0	Х	0
dj	0	0	0	0	0

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

?d_i + ?d_j = 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*).

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

i j	2	3	4	6	di
3	0(0)	Х	104	0(13)	0
4	0(0)	0(4)	Х	13	0
5	Х	24	0(24)	69	24
6	37	4	0(4)	Х	4
dj	0	4	0	13	0

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) проводим путем замены элемента d₅₄ = 0 на Х, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,4*), в результате получим редуцированную матрицу.

i j	2	3	4	6	di
3	0	Х	104	0	0
4	0	0	Х	13	0
5	Х	24	Х	69	24
6	37	4	0	Х	0
dj	0	0	0	0	24

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

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

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

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

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

i j	2	3	6	di
3	0	Х	0	0
4	0	0	13	0
6	37	4	Х	4
dj	0	0	0	4

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

?d_i + ?d_j = 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*).

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

i j	2	3	6	di
3	0(33)	Х	0(13)	0
4	Х	0(13)	13	13
6	33	0(33)	Х	33
dj	33	0	13	0

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

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

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

i j	2	3	6	di
3	Х	Х	0	0
4	Х	0	13	0
6	33	0	Х	0
dj	33	0	0	33

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

H(3*,2*) = 352 + 33 = 385

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

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

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

i j	3	6	di
4	0	13	0
6	0	Х	0
dj	0	13	13

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

?d_i + ?d_j = 13

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

H(3,2) = 352 + 13 = 365 ? 385

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

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,6) и (6,3).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(1,5), (5,4), (4,6), (6,3), (3,2), (2,1),

Длина маршрута равна F(Хk) = 365

2. ВЫБОР ЭКОНОМИЧЕСКИ ЦЕЛЕСООБРАЗНОГО СПОСОБА ПОЕЗДКИ КОММИВОЯЖЕРА

На основании данных таблицы 2 произведем выбор транспорта для объезда коммивояжером шести пунктов по рассчитанному ранее маршруту.

Таблица 1. Характеристики транспортных средств

Виды транспорта
Воздушный	Железнодорожный	Междугородний автобус
Тип	Vp	К-во кресел	Vp	К-во мест в вагоне	Тип	Vp	К-во мест
Ил-96-300	820	300	92	62	КАВЗ-685	92	21

Примечание. Количество вагонов в пассажирском составе 10-16.

Коэффициент использования загрузки 0,7-0,8.

Воздушный транспорт

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

Железнодорожный транспорт

«+»	«-»
массовость перевозок и высокая провозная способность железных дорог	низкий уровень обслуживания
возможность использования для перевозок массовых грузов и пассажиров с большой скоростью
сравнительно невысокая себестоимость перевозки
регулярность перевозок независимо от времени года, времени суток, климатических условий

Автомобильный транспорт

«+»	«-»
высокий уровень маневренности	высокая себестоимость перевозок (в 10 раз выше, чем на железнодорожном транспорте)
высокая скорость доставки пассажиров и грузов на короткие расстояния	низкий уровень производительности труда из-за малой вместимости пассажиров в автотранспорт
высокая степень мобильности
способность быстро реагировать на изменение спроса

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

3. СРАВНИТЕЛЬНАЯ ОЦЕНКА ВЫБОРА ТРАНСПОРТА

Произведем расчет и сравнение времени следования коммивояжера при использовании различных видов транспорта.

Затраты времени пассажира на поездку при использовании того или иного вида транспорта определяются исходя из протяженности маршрута, скорости передвижения, времени, затраченного в начальных и конечных пунктах и времени ожидания:

, где:

- скорость передвижения;

- протяженность маршрута;

- время, затраченное в начальных и конечных пунктах;

- время ожидания, которое равно половине интервала.

Среднее время ожидания автобуса рассчитывается по формуле:

tож = 0,5* tин , где

tин - интервал движения автобуса (tин = 31 мин=0,52 ч).

Получаем: tож=0,5*0,52 ч = 0,26 ч

Для железнодорожного транспорта = 20 минут.

Для авиа транспорта tож=2ч

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

Вид транспорта	Производительность обслуживания, чел/час
Посадка пассажиров в ТС
Автобус	60
Самолет	200
Электропоезд	3000
Высадка пассажиров
Автобус	100
Самолет	400
Электропоезд	4500

Продолжительность начальных операций для автобусного транспорта рассчитывается по формуле:

Tн=n*K/Прн=21*0,8/60=0,28

n - количество мест;

К - коэффициент использования загрузки (К = 0,8);

Прн - производительность посадки

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

tк=n*K/Прн=21*0,8/100=0,168

n - количество мест;

К - коэффициент использования загрузки (К = 0,8);

Прк - производительность высадки

Продолжительность начальных операций для железнодорожного транспорта рассчитывается по формуле:

nв - количество вагонов;

nм - количество мест в вагоне;

К - коэффициент использования загрузки (К = 0,8);

Прн - производительность начальной операции (посадки)

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

nв - количество вагонов;

nм - количество мест в вагоне;

К - коэффициент использования загрузки (К = 0,8);

Прк - производительность конечной операции (высадки)

Для авиатранспорта:

Tн =Nмест*Кзагр/Рпос=300*0,8/3000=0,08

Tк =Nмест*Кзагр/Рвыс=300*0,8/400=0,6

Таким образом, время начально-конечных операций составит:

Tнк(авто)=0,28+0,168=0,448ч

Tнк(жд)=0,26+0,18=0,44ч

Tнк(авиа)=0,08+0,6=0,68

Рассчитаем время следования коммивояжера на каждом из участков маршрута автобусом и электропоездом.

Расстояния между городами
Участок маршрута	1-5	5-4	4-6	6-3	3-2	2-1
Протяженность, км	80	38	87	60	45	55

1) Автобус (ч):

2) ж/д (ч):

3) авиа (ч):

Таким образом, сложив всё время по участкам, мы получим продолжительность следования коммивояжера при использовании транспорта:

На авто=8,2ч

На жд=8,6ч

На авиа=16,5ч

Стоимость пассажиро-часов пребывания в пути рассчитывается по формуле:

, где

Спч - стоимость пассажиро-часа (Спч = 46 руб );

Кту - коэффициент транспортной усталости пассажира при поездке

(принимаем Кту = 1).

Для каждого вида транспорта, получим стоимость пассажирочасов пребывания пассажира в пути:

С^ав=377,94 руб/п-ч

С^жд=395,232 руб/п-ч

С^авиа=760,43 руб/п-ч

Все полученные результаты расчетов представлены в таблице.

Вид транспорта	Переезд	Дальность поездки	Время ожидания	Время начально-конечных операций	Материальные затраты на поездку	Продолжительность следования	Стоимость пассажиро-часов пребывания
						По отрезкам пути	Общая	По отрезкам пути	Общая
ВТ	1 5	80	2 часа	0,68 часа	-	2,78	16,531	127,88	760,426
	5 4	38			-	2,73		125,58
	4 6	87			-	2,786		128,156
	6 3	60			-	2,753		126,638
	3 2	45			-	2,735		125,81
	2 1	55			-	2,747		126,362
ЖД	1 5	80	0,33 часа	0,44 часа	136	1,64	8,592	75,44	395,232
	5 4	38			64,6	1,183		54,418
	4 6	87			147,9	1,72		79,12
	6 3	60			102	1,422		65,412
	3 2	45			76,5	1,259		57,914
	2 1	55			93,5	1,368		62,928
Авто	1 5	80	0,26 часа	0,448 часа	136	1,578	8,22	72,588	377,94
	5 4	38			64,6	1,121		51,566
	4 6	87			147,9	1,654		76,084
	6 3	60			102	1,36		62,56
	3 2	45			76,5	1,197		55,062
	2 1	55			93,5	1,306		60,076

4. ПОСТРОЕНИЕ СОВМЕЩЕННОГО ГРАФИКА ВЗАИМОДЕЙСТВИЯ ТРАНСПОРТА

t,час	2	4	6	8	10	12	14
1
2
3
4
5
6



ВЫВОДЫ

В данной работе мы реализовали полученные теоретические знания по курсу «Единая транспортная система и география транспорта» на примере практической задачи выбора пассажирского транспорта. Используя метод ветвей и границ для выбора кратчайшего маршрута для коммивояжера, мы выбрали оптимально короткий маршрут равный 365 км, который проходит в следующей последовательности через города: 1 5 4 6 3 2 1. Сравнивая технико-экономические характеристики трех видов транспорта: железнодорожного, воздушного и автомобильного, определили наиболее эффективное взаимодействие двух видов транспорта: автомобильный и железнодорожный. Воздушный транспорт на данном маршруте использовать нецелесообразно. Для того, чтобы это определить мы рассчитали и сравнили:

Продолжительность следования коммивояжера по маршруту.

Материальные затраты на поездку.

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



СПИСОК ЛИТЕРАТУРЫ

1. Фомин Г.П. Математические методы и модели в коммерческой деятельности. Учебник. - М.: Финансы и статистика, 2001 г.

2. Степочкина С.А. Курс лекций по вычислительной математике. - 2004 г.

3. Практикум по логистике Уч. Пособие под ред. Аникина Б.А. М.: ИНФРА-М, 2003, 2006

Размещено на Allbest.ru

...