Решение задачи коммивояжера
Введение.
Транспорт является важной отраслью экономической деятельности страны, без которой продукция предприятий добывающей отрасли оставалась бы в местах ее добычи, продукция предприятий обрабатывающей отрасли не достигла бы мест производства, а продукция сельскохозяйственной отрасли никогда бы не нашла своего потребителя.
В условиях глобализации экономики и международного разделения труда транспортной системе отведена особая роль. От качества функционирования этой системы зависит развитие как внешних, так и внутренних экономических связей любой страны.
В настоящее время грузовладельцу, пассажиру становится все сложнее ориентироваться в транспортной обстановке. При выборе способа доставки необходимо учитывать ряд факторов, основными из которых являются:
- состояние международных и внутренних транспортных рынков ( рынков воздушных, автомобильных, железнодорожных перевозок, брокерских, страховых, транспортно-экспедиторских услуг);
- транспортную политику отдельных государств и международных союзов;
- законодательство стран, регулирующее деятельность в области грузоперевозок, международные соглашения и конвенции по перевозкам и транзиту, таможенное законодательство;
- технико-эксплуатационные характеристики различных видов транспорта;
- организацию и технику транспортных операций, упаковку, хранение, складирование;
- особенности отдельных транспортных направлений.
Таким образом, формирование отлаженной системы пассажирских и грузовых перевозок является стратегической целью развития транспорта на современном этапе.
Цель курсовой работы.
Целью курсовой работы является выбор и обоснование эффективных маршрутов и проведение экономической оценки взаимодействия различных видов транспорта при обслуживании пассажиропотоков и грузопотоков.
Для этого в курсовой работе предлагается последовательно рассмотреть ряд задач.
Задачи:
- произвести расстановку воздушных судов на рейсы таким образом, чтобы суммарные затраты на транспортировку грузов были минимальными;
- рассчитать материальные затраты специалиста авиаремонтного завода при последовательном посещении им пяти городов для заключения договоров на поставку запасных частей;
- построить оптимальный маршрут поездки для специалиста авиаремонтного завода, который для заключения договора о поставках запасных частей должен побывать в каждом из пяти городов по одному разу и вернуться в начальный пункт. Общие затраты на поездку при этом должны быть минимальными.
I. Основная (расчетная) часть.
Задача 1.
Из аэропорта должны вылететь пять воздушных судов (ВС) для доставки груза в пять городов. Затраты на полет каждого из самолетов (тыс.руб.) в каждый город представлены в таблице 1 (Приложение 1). Необходимо назначить ВС на рейсы таким образом, чтобы суммарные затраты на транспортировку грузов были минимальными.
Таблица 1.
Вариант 8.
| Столбцы Строки | |||||
1.Начнем со сравнения разности коэффициентов целевой функции основной и базовых строк.
Разности коэффициентов первой строки со второй (1-2):
1 столбец: 601-303=298
2 столбец: 424-260=164
3 столбец: 340-304=36
4 столбец: 355-557=-202
5 столбец: 575-307=268
Наибольшая разность равна 298 – в первом столбце, а значит элемент х11 не входит в оптимальный план, т.е. х11 = 0. Далее по величине разность равна 36 (в третьем столбце). Тогда с11 = 303+268=571.
Новое значение коэффициента вписываю в туже клетку (Таблица 2) и выделяю жирным шрифтом. Аналогично будут занесены и другие новые значения коэффициентов.
Таблица 2.
| Столбцы Строки | |||||
| 601,571,473, | 340, | 575, | |||
| 304, | 557,319, | 307, | |||
| 730,652,644 | 340,274, | 656, | |||
| 848,803,696, | |||||
| 344, | 227, | 388, |
Разность коэффициентов первой строки с третьей (1-3):
1 столбец: 571-730= -159
2 столбец: 424-242= 182
3 столбец: 340-340=0
4 столбец: 355-656= -301
5 столбец:575-179=396
Наибольшая разность равна 396 – в пятом столбце, а значит элемент х15, не входит в оптимальный план, т.е. х15 = 0. Далее по величине разность равна - 182 (во втором столбце). Тогда с15 = 179+182=361
Разность коэффициентов первой и четвертой строк (1-4):
1 столбец: 571-511=60
2 столбец: 424-848= -424
3 столбец:340-378= -38
4 столбец: 355-523= -168
5 столбец: 361-740= -379
Наибольшая разность равна 60 – в первом столбце, а значит элемент х11, не входит в оптимальный план, т.е. х11 = 0. Далее по величине разность равна -38 (в третьем столбце). Тогда с11 = 511+(-38)=473.
Разность коэффициентов первой и пятой строк (1-5):
1 столбец: 473-191=282
2 столбец: 424-344=80
3 столбец: 340-227=113
4 столбец: 355-195=160
5 столбец: 361-388= -27
Наибольшая разность равна 282 – в первом столбце, а значит элемент х11, не входит в оптимальный план, т.е. х11 = 0. Далее по величине разность равна 160 (в четвертом столбце). Тогда с11= 191+160=351.
Перейдем к строке 2. Сравним ее с 1.
Разность коэффициентов второй и первой строк (2-1):
1 столбец: 303-351= -50
2 столбец: 260-424 = -164
3 столбец:304-340 = -36
4 столбец: 557-355 = 202
5 столбец: 307-361= -54
Наибольшая разность равна 202 – в четвертом столбце, а значит элемент х24, не входит в оптимальный план, т.е. х24 = 0. Далее по величине разность равна -36 (в третьем столбце). Тогда с24= 355+(-36) =319.
Разность коэффициентов второй и третьей строк (2-3):
1 столбец: 303-730= -427
2 столбец: 260-242= 18
3 столбец:304-340 = -36
4 столбец: 319-656= -337
5 столбец: 307-179=128
Наибольшая разность равна 128 – в пятом столбце, а значит элемент х25, не входит в оптимальный план, т.е. х25 = 0. Далее по величине разность равна 18 (во втором столбце). Тогда с25= 179+18=197.
Разность коэффициентов второй и четвертой строк (2-4):
1 столбец: 303-511= -208
2 столбец: 260-848=-588
3 столбец: 304-378=-74
4 столбец:319-523=-204
5 столбец:197-740=-543
Наибольшая разность равна -74 – в третьем столбце, а значит элемент х23, не входит в оптимальный план, т.е. х23 = 0. Далее по величине разность равна -588 (во втором столбце). Тогда с23= 378+(-204) = 174
Разность коэффициентов второй и пятой строк (2-5):
1 столбец: 303-191=112
2 столбец: 260-344=-84
3 столбец:174-227=-53
4 столбец: 319-195=124
5 столбец:197-388=-191
Наибольшая разность равна 124 – в четвертом столбце, а значит элемент х24, не входит в оптимальный план, т.е. х24 = 0. Далее по величине разность равна 112 (в первом столбце). Тогда с24= 195+112 =307.
Теперь сравним 3 строку с остальными строками.
Разность коэффициентов третьей и первой строк (3-1):
1 столбец: 730-351=379
2 столбец:242-424=-182
3 столбец:340-340=0
4 столбец: 656-355=301
5 столбец: 179-361=-182
Наибольшая разность равна 379 – в первом столбце, а значит элемент х31, не входит в оптимальный план, т.е. х31 = 0. Далее по величине разность равна 301 (в четвертом столбце). Тогда с31= 351+301=652.
Разность коэффициентов второй и первой строк (3-2):
1 столбец: 652-303=349
2 столбец: 242-260=-18
3 столбец:340-174=166
4 столбец: 656-307=349
5 столбец: 179-197= -18
Так как максимальная разность отмечается в некоторых столбцах, никакого вывода сделать нельзя.
Разность коэффициентов третьей и четвертой строк (3-4):
1 столбец: 652-511=141
2 столбец: 242-848=-606
3 столбец:340-378=-38
4 столбец: 656-523= 133
5 столбец: 179-740= -561
Наибольшая разность равна 141 – в первом столбце, а значит элемент х31, не входит в оптимальный план, т.е. х31 = 0. Далее по величине разность равна 133 (в четвертом столбце). Тогда с31= 511+133= 644.
Разность коэффициентов третьей и пятой строк (3-5):
1 столбец: 644-191= 453
2 столбец:242-344=-102
3 столбец:340-227=113
4 столбец: 656-195=461
5 столбец: 179-388=-209
Наибольшая разность равна 461– в четвертом столбце, а значит элемент х34, не входит в оптимальный план, т.е. х34 = 0. Далее по величине разность равна 453 (в первом столбце). Тогда с34= 195+453=648.
Разность коэффициентов четвертой и первой строк (4-1):
1 столбец: 511-351=160
2 столбец: 848-424=424
3 столбец:378-340=38
4 столбец: 523-355=168
5 столбец: 740-361=379
Наибольшая разность равна 424 – во втором столбце, а значит элемент х42, не входит в оптимальный план, т.е. х42 = 0. Далее по величине разность равна 379 (в пятом столбце). Тогда с42= 424+379 =803.
Разность коэффициентов четвертой и второй строк (4-2):
1 столбец: 511-303=208
2 столбец: 803-260=543
3 столбец:378-174=204
4 столбец: 523-307=216
5 столбец: 740-197=543
Так как максимальная разность отмечается в некоторых столбцах, никакого вывода сделать нельзя.
Разность коэффициентов четвертой и третьей строк (4-3):
1 столбец: 511-644=-133
2 столбец: 803-242=561
3 столбец:378-340=38
4 столбец: 523-648=-125
5 столбец: 740-179=561
Так как максимальная разность отмечается в некоторых столбцах, никакого вывода сделать нельзя.
Разность коэффициентов четвертой и пятой строк (4-5):
1 столбец: 511-191=320
2 столбец: 803-344=459
3 столбец:378-227=151
4 столбец: 523-195=328
5 столбец: 740-388=352
Наибольшая разность равна 459 – во втором столбце, а значит элемент х42, не входит в оптимальный план, т.е. х42 = 0. Далее по величине разность равна 352 (в пятом столбце). Тогда с42= 344+352 =896.
Разность коэффициентов пятой и первой строк (5-1):
1 столбец: 191-351=-160
2 столбец: 344-424=-80
3 столбец:227-340=-113
4 столбец: 195-355=-160
5 столбец: 388-361=27
Наибольшая разность равна 27– в пятом столбце, а значит элемент х55 не входит в оптимальный план, т.е. х55 = 0. Далее по величине разность равна -80 (во втором столбце). Тогда с55= 361-80 =281.
Разность коэффициентов пятой и второй строк (5-2):
1 столбец: 191-303=-112
2 столбец: 344-260=84
3 столбец:227-174=53
4 столбец: 195-307=-112
5 столбец: 281-187=84
Так как максимальная разность отмечается в некоторых столбцах, никакого вывода сделать нельзя.
Разность коэффициентов пятой и третьей строк (5-3):
1 столбец: 191-644=-453
2 столбец: 344-242=102
3 столбец:227-340=-113
4 столбец: 195-648=-453
5 столбец: 281-179=102
Так как максимальная разность отмечается в некоторых столбцах, никакого вывода сделать нельзя.
Разность коэффициентов пятой и четвертой строк (5-4):
1 столбец: 191-511=-322
2 столбец: 344-696=-352
3 столбец:227-378=-151
4 столбец: 195-523=-328
5 столбец: 281-740=-459
Наибольшая разность равна -151 – в третьем столбце, а значит элемент х53 не входит в оптимальный план, т.е. х53 = 0. Далее по величине разность равна -320 (в первом столбце). Тогда с53= 378-320 =58.
Перейдем к столбцам. Рассмотрим 1 столбец.
Разность коэффициентов первого и второго столбца (1-2):
1 строка: 351-424=-73
2 строка: 303-260=43
3 строка:644-242=402
4 строка: 511-696=-185
5 строка: 191-344=-153
Наибольшая разность равна 402– в третьей строке, а значит элемент х13 не входит в оптимальный план, т.е. х13 = 0. Далее по величине разность равна 43 (во второй строке). Тогда с13= 242+43 =285.
Разность коэффициентов первого и третьего столбца (1-3):
1 строка: 351-340=11
2 строка: 303-174=129
3 строка:285-340=-55
4 строка: 511-378=133
5 строка: 191-58=133
Так как максимальная разность отмечается в некоторых строках, никакого вывода сделать нельзя.
Разность коэффициентов первого и четвертого столбца (1-4):
1 строка: 351-355=-4
2 строка: 303-307=-4
3 строка:285-648=-363
4 строка: 511-523=-12
5 строка: 191-195=-4
Так как максимальная разность отмечается в некоторых строках, никакого вывода сделать нельзя.
Разность коэффициентов первого и пятого столбца (1-5):
1 строка: 351-361=-10
2 строка: 303-197=106
3 строка:285-179=106
4 строка: 511-740=-229
5 строка: 191-281=-90
Так как максимальная разность отмечается в некоторых строках, никакого вывода сделать нельзя.
Разность коэффициентов второго и первого столбца (2-1):
1 строка: 424-351=73
2 строка:260-303=-43
3 строка:242-285=-43
4 строка: 696-511=185
5 строка: 344-191=153
Наибольшая разность равна 185– в четвертой строке, а значит элемент х24 не входит в оптимальный план, т.е. х24 = 0. Далее по величине разность равна 153 (в пятой строке). Тогда с24= 511+153 =664.
Разность коэффициентов второго и третьего столбца (2-3):
1 строка: 424-340=84
2 строка: 260-174=86
3 строка:242-340=-98
4 строка: 664-378=286
5 строка: 344-58=286
Так как максимальная разность отмечается в некоторых строках, никакого вывода сделать нельзя.
Разность коэффициентов второго и четвертого столбца (2-4):
1 строка: 424-355=69
2 строка:260-307=-47
3 строка:242-648=-406
4 строка: 664-523=141
5 строка: 344-195=149
Наибольшая разность равна 149– в пятой строке, а значит элемент х25 не входит в оптимальный план, т.е. х25 = 0. Далее по величине разность равна 141 (в четвертой строке). Тогда с25= 195+141 =336.
Разность коэффициентов второго и пятого столбца (2-5):
1 строка: 424-361=63
2 строка: 260-197=63
3 строка:242-179=63
4 строка: 664-740=-76
5 строка: 336-281=55
Так как максимальная разность отмечается в некоторых строках, никакого вывода сделать нельзя.
Разность коэффициентов третьего и первого столбца (3-1):
1 строка: 340-351=-11
2 строка:174-303=-129
3 строка:340-285=55
4 строка: 378-511=-133
5 строка: 58-191=-133
Наибольшая разность равна 55– в третьей строке, а значит элемент х33 не входит в оптимальный план, т.е. х33 = 0. Далее по величине разность равна -11 (в первой строке). Тогда с33= 285-11 =274.
Разность коэффициентов третьего и второго столбца (3-2):
1 строка: 340-424=-84
2 строка:174-260=-86
3 строка:274-242=32
4 строка: 378-664=-286
5 строка: 58-336=-278
Наибольшая разность равна 32– в третьей строке, а значит элемент х33 не входит в оптимальный план, т.е. х33 = 0. Далее по величине разность равна -84 (в первой строке). Тогда с33= 242-84 =158.
Разность коэффициентов третьего и четвертого столбца (3-4):
1 строка: 340-355=-15
2 строка:174-307=-133
3 строка:158-648=-490
4 строка: 378-523=-145
5 строка: 58-195=-137
Наибольшая разность равна -15– в первой строке, а значит элемент х31 не входит в оптимальный план, т.е. х31 = 0. Далее по величине разность равна -133 (во второй строке). Тогда с31= 355-133 =222.
Таблица 2
| Столбцы Строки | |||||
| 601,571,473, 351 * | 340, 222 * | 575, 361 * | |||
| 304, 174 * | 557,319, 307 * | 307, 197 * | |||
| 730,652,644, 285 * | 340,274, | 656, 648 * | |||
| 848,803,696, 664 * | |||||
| 344, 336 * | 227, 58 * | 388, 281 * |
Видно, что в третьем столбце все элементы, кроме х43 равны нулю. Поэтому х43 = 1, строка 4 и столбец 3 исключаются из дальнейшего рассмотрения.
Используя таблицу 2 сравним 2 столбец с остальными.
| Столбцы Строки | ||||
| 601,571,473, 351 * | 575,361 * | |||
| 557,319, 307 * | 307,197 * | |||
| 730,652,644, 285 * | 656,648 * | |||
| 344,336 * | 388,281 * |
Видно, что во пятом столбце все элементы, кроме х35 равны нулю. Поэтому х35 = 1, строка 3 и столбец 5 также исключаются из дальнейшего рассмотрения.
Таблица 3
| Столбцы Строки | |||
| 601,351 * | |||
| 557,307 * | |||
| 344,336 * |
Разности коэффициентов первой строки со второй (1-2):
1 столбец: 351-303=48
2 столбец: 424-260=164
4 столбец: 355-307=48
Наибольшая разность равна 164 – во втором столбце, а значит элемент х12 не входит в оптимальный план, т.е. х12 = 0. Далее по величине разность равна 48 (в третьем столбце). Тогда с11 = 260+48=308.
Таблица 4
| Столбцы Строки | |||
| 601,351 * | 424,308 * | ||
| 557,307 * | |||
| 344,336 * |
Видно, что во втором столбце все элементы, кроме х22 равны нулю. Поэтому х22 = 1, строка 2 и столбец 2 также исключаются из дальнейшего рассмотрения.
Таблица 5.
| Столбцы Строки | ||
| 601,571,473,351 * | ||
Итого получаю следующие отличные от нуля элементы: х43 = 1; х35 = 1;
х22 = 1; х54 = 1; х14 = 1
А значение целевой функции: С = 378+179+260+195+355=1367
Т.е. это и есть минимальные суммарные затраты на транспортировку грузов равные 1367 тыс. руб.
Решение данной задачи имеет следующий вид:
Таблица 6.
| № Города № ВС | |||||
Вывод: Для того чтобы суммарные затраты на транспортировку грузов были минимальными, необходимо назначить ВС на рейсы следующим образом:
· ВС1 в Город 4
· ВС2 в Город 2
· ВС3 в Город 5
· ВС4 в Город 3
· ВС5 в Город 4
При таком назначении ВС на рейсы минимальные суммарные затраты на транспортировку грузов равны 1367 тыс. руб.
Задача 2
Условие задачи: Специалисту авиаремонтного завода для заключения договора о поставке запасных частей из пяти городов необходимо побывать в каждом из них один раз и вернуться в исходный пункт маршрута.
Таблица 7. Исходные данные. Расстояния в км между городами.
| Столбцы Строки | |||||
| __ | |||||
| __ | |||||
| __ | |||||
| __ | |||||
| __ |
Таблица 8. Исходные данные для расчета затрат на поездку.
| Вариант | Виды транспорта | |||||||
| Железнодорожный | Автомобильный | |||||||
| Кол-во вагонов | Время ожидания (мин.) | Кол-во мест в вагоне | Скорость (км/ч) | Интервал движения (мин.) | Кол-во мест в салоне | Скорость (км/ч) | ||
Формирование базы данных:
Исходя из данных Таблицы 7, можно сделать вывод, что на данных маршрутах целесообразнее использовать либо железнодорожный транспорт, либо автомобильный.
Автомобильный транспорт (междугородние автобусы, личные автомобили и др.) имеет некоторые особенности и преимущества перед другими видами транспорта. Например:
- высокая маневренность и подвижность;
- способность обеспечивать доставку «от двери до двери» без дополнительных перевалок и пересадок в пути следования;
- высокая скорость доставки, особенно при перевозках на короткие расстояния;
Себестоимость перевозок на автомобильном транспорте, гораздо выше чем на железнодорожном.
Железнодорожный транспорт является основным звеном в единой транспортной системе России. Он играет важную роль в удовлетворении потребности населения в передвижении. Преимуществами данного вида транспорта являются, например:
- регулярность перевозок независимо от времени года, времени суток, климатических условий;
- большая скорость перевозки пассажиров и массивных грузов;
- сравнительно невысокая себестоимость перевозки
Пассажир стремится выбрать наиболее выгодное средство передвижения. Выбор производится с учетом особенностей транспорта и требований пассажиров к качеству обслуживания, а именно:
- безопасности;
- уровня организации движения транспортных средств во времени (частота, регулярность и т.д.);
- затрат времени на поездку с учетом ожидания или скорость передвижения пассажиров;
- комфортабельность и др.
Известно, что безопасность перевозок железнодорожным транспортом значительно выше, чем автомобильным.
Согласно Таблицы 2 (Приложение 3) видно, что скорость движения автомобильного транспорта выше скорости движения транспорта железнодорожного. Интервал движения у автомобильного транспорта выше.
1. Расчеты для железнодорожного транспорта.
1.1 Расчет затрат времени пассажира на поездку при использовании железнодорожного транспорта:
Затраты времени пассажира на поездку рассчитываются согласно формулы:
= 
+ 
, где
– протяженность маршрута;
– скорость передвижения;
– время, затраченное в начальных и конечных пунктах;
– время ожидания;
здесь: 
– количество посадочных мест в вагоне;
– количество вагонов в железнодорожном составе;
– коэффициент использования посадочных мест (принимаю равным 0,75);
, 
– производительность обслуживания пассажиров при посадке и высадке в (из) вагон (а).
Участки маршрута:
1-2: = 424/65 + 62*14*0,75/3000 + 62*14*0,75/4500 + 15/60 = 6,89 (ч);
1-3: = 340/65 + 62*14*0,75/3000 + 62*14*0,75/4500 + 15/60 = 5,59 (ч);
1-4: = 355/65 + 62*14*0,75/3000 + 62*14*0,75/4500 + 15/60 = 5,82 (ч);
1-5: = 575/65 + 62*14*0,75/3000 + 62*14*0,75/4500 + 15/60 = 9,21 (ч);
2-3: = 304/65 + 62*14*0,75/3000 + 62*14*0,75/4500 + 15/60 = 5,04 (ч);
2-4: = 557/65 + 62*14*0,75/3000 + 62*14*0,75/4500 + 15/60 = 8,93 (ч);
2-5: = 307/65 + 62*14*0,75/3000 + 62*14*0,75/4500 + 15/60 = 5,08 (ч);
3-4: = 656/65 + 62*14*0,75/3000 + 62*14*0,75/4500 + 15/60 = 10,45 (ч);
3-5: = 179/65 + 62*14*0,75/3000 + 62*14*0,75/4500 + 15/60 = 3,12 (ч);
4-5: = 740/65 + 62*14*0,75/3000 + 62*14*0,75/4500 + 15/60 = 11,75 (ч);
1.2 Расчет стоимости пассажиро-часов пребывания пассажира в пути:
Стоимость пассажиро-часов пребывания пассажира в пути ( 
- это показатель, который характеризует потенциальные потери пассажира из-за пассивного пребывания в пути. По величине затрат, которые можно рассматривать как упущенная выгода клиента или его работодателя, можно осуществлять выбор транспорта по целям поездки. Чем меньше потерь от пассивного пребывания в транспорте во время движения, тем выгоднее способ поездки.
Стоимость пассажиро-часов пребывания пассажира в пути ( рассчитывается по следующей формуле:
, где
– стоимость пассажиро-часа (принимаю равной 1000 руб);
– число пассажиров следующих по i-му варианту перевозки;
– продолжительность поездки пассажира (была рассчитана выше);
– коэффициент транспортной усталости пассажира при поездке (принимаю равным 1,3).
Участки маршрута:
1-2: 
= 1000 * 1 * 6,89 * 1,3 = 8957 (руб.);
1-3: = 1000 * 1 * 5,59 * 1,3 = 7267(руб.);
1-4: = 1000 * 1 * 5,82 * 1,3 = 7566 (руб.);
1-5: = 1000 * 1 * 9,21 * 1,3 = 11973 (руб.);
2-3: = 1000 * 1 * 5,04 * 1,3 = 6552 (руб.);
2-4: = 1000 * 1 * 8,93 * 1,3 = 11609 (руб.);
2-5: = 1000 * 1 * 5,08 * 1,3 = 6604 (руб.);
3-4: = 1000 * 1 * 10,45 * 1,3 = 13585 (руб.);
3-5: = 1000 * 1 * 3,12 * 1,3 = 4056 (руб.);
4-5: = 1000 * 1 * 11,72 * 1,3 = 15236 (руб.);
1.3 Расчет материальных затрат пассажира на поездку (согласно стоимости билета):
Участки маршрута:
1-2: 70 (руб.) 1-5: 77 (руб.) 2-5: 42 (руб.) 4-5: 56 (руб.)
1-3: 47 (руб.) 2-3: 48 (руб.) 3-4: 56 (руб.)
1-4: 49 (руб.) 2-4: 80 (руб.) 3-5: 31 (руб.)
1.4 Расчет абсолютных затрат пассажира на поездку:
Абсолютные затраты пассажира на поездку рассчитываются по формуле:
, где
– материальные затраты на поездку по рассматриваемому маршруту с использованием выбранных видов транспорта;
– ранее рассчитанная стоимость пассажиро-часов в пути.
Участки маршрута:
1-2: 
(руб.)
1-3: 
= 47 + 7267 = 7314 (руб.)
1-4: = 49 + 7566 = 7615 (руб.)
1-5: = 77 + 11973 = 12050 (руб.)
2-3: = 48 + 6552 = 6600 (руб.)
2-4: = 80 + 11609 = 11689 (руб.)
2-5: = 42 + 6604 = 6646 (руб.)
3-4: 
= 56 + 13585 = 13641 (руб.)
3-5: =31+ 4056 = 4087 (руб.)
4-5: = 56 + 15236 = 15292 (руб.)
2. Расчеты для автомобильного транспорта.
2.1 Расчет затрат времени пассажира на поездку при использовании автомобильного транспорта:
Расчет затрат времени как и в случае железнодорожного транспорта рассчитывается по формуле:
= + , где считается следующим образом:
, где
- максимальное и минимальное время ожидания очередного автобуса (ч);
- интервал движения автобуса (ч).
для расчета 
принимаю равным 0,75.
Участки маршрута:
1-2: = 424/85 + 34*0,75/60 + 34*0,75/100 + 0,5*30/60 = 5,92 (ч);
1-3: = 340/85 + 34*0,75/60 + 34*0,75/100 + 0,5*30/60 = 4,68 (ч);
1-4: = 355/85 + 34*0,75/60 + 34*0,75/100 + 0,5*30/60 = 4,85 (ч);
1-5: = 575/85 + 34*0,75/60 + 34*0,75/100 + 0,5*30/60 = 7,44 (ч);
2-3: = 304/85 + 34*0,75/60 + 34*0,75/100 + 0,5*30/60 = 4,26 (ч);
2-4: = 557/85 + 34*0,75/60 + 34*0,75/100 + 0,5*30/60 = 7,23 (ч);
2-5: = 307/85 + 34*0,75/60 + 34*0,75/100 + 0,5*30/60 = 4,29 (ч);
3-4: = 656/85 + 34*0,75/60 + 34*0,75/100 + 0,5*30/60 = 8,39 (ч);
3-5: = 179/85 + 34*0,75/60 + 34*0,75/100 + 0,5*30/60 = 2,78 (ч);
4-5: = 740/85 + 34*0,75/60 + 34*0,75/100 + 0,5*30/60 = 9,38 (ч);
2.2 Расчет стоимости пассажиро-часов пребывания пассажира в пути:
принимаю равным 1,3. Формула для расчета приведена выше:
Участки маршрута:
1-2: = 1000 * 1 * 5,92 * 1,3 = 7696 (руб.);
1-3: = 1000 * 1 * 4,68 * 1,3 = 6084 (руб.);
1-4: = 1000 * 1 * 4,85 * 1,3 = 6305 (руб.);
1-5: = 1000 * 1 * 7,44 * 1,3 = 9672 (руб.);
2-3: = 1000 * 1 * 4,26 * 1,3 = 5538 (руб.);
2-4: = 1000 * 1 * 7,23 * 1,3 = 9399 (руб.);
2-5: = 1000 * 1 * 4,29 * 1,3 = 5577 (руб.);
3-4: = 1000 * 1 * 8,39 * 1,3 = 10907 (руб.);
3-5: = 1000 * 1 * 2,78 * 1,3 = 3614 (руб.);
4-5: = 1000 * 1 * 9,38 * 1,3= 12194 (руб.);
2.3 Расчет материальных затрат пассажира на поездку (согласно стоимости билета):
Участки маршрута:
1-2: 75 (руб.) 1-5: 94 (руб.) 2-5: 51 (руб.) 4-5: 68 (руб.)
1-3: 51 (руб.) 2-3: 143 (руб.) 3-4: 68 (руб.)
1-4: 60 (руб.) 2-4: 97 (руб.) 3-5: 37 (руб.)
2.4 Расчет абсолютных затрат пассажира на поездку:
Формула для расчета приведена выше.
Участки маршрута:
1-2: 
75 + 7696 = 7771 (руб.)
1-3: = 51 + 6084 = 6135 (руб.)
1-4: = 60 + 6305 = 6365 (руб.)
1-5: =94 + 9672 = 9766 (руб.)
2-3: =143 + 5538 = 5681 (руб.)
2-4: = 97 + 9399 = 9496 (руб.)
2-5: = 51 + 5577 = 5628 (руб.)
3-4: =68 + 10907 = 10975 (руб.)
3-5: = 37 + 3614 = 3651 (руб.)
4-5: = 68 + 12194 = 12262 (руб.)
Все необходимые расчеты произведены. Заношу результаты расчетов в Таблицу 9.
Таблица 9. Абсолютные затраты пассажира на поездку с использованием железнодорожного и автомобильного транспорта (руб.).
| Железнодорожный транспорт | ||||||
| - | ||||||
| - | ||||||
| - | ||||||
| - | ||||||
| - | ||||||
| Автомобильный транспорт | ||||||
| - | ||||||
| - | ||||||
| - | ||||||
| - | ||||||
| - |
Анализируя расчеты и Таблицу 9 можно прийти к выводу, что для поездки специалиста авиаремонтного завода по выбранным маршрутам целесообразно использовать автомобильный транспорт. Так как стоимость билетов на автомобильном транспорте ниже. Также при использовании автомобильного транспорта меньше затраты времени на нахождение в пути, ниже стоимость пассажиро-часов пребывания пассажира в пути, а следовательно (что и видно в Таблице 9) ниже абсолютные затраты пассажира на поездку. Значит, для поездки специалиста авиаремонтного завода нужно выбрать автомобильный транспорт (автобус).
Теперь необходимо решить задачу коммивояжера. Коммивояжер должен побывать в каждом городе один раз и вернуться в исходный пункт маршрута, затратив при этом минимум денег. Для решения задачи необходимо использовать ПС-метод. Не допустимо, чтобы коммивояжер из некоторого города возвращался туда обратно. Поэтому все диагональные элементы должны быть равны нулю. Чтобы добиться этого, достаточно положить их очень большими (ввести так называемые штрафные функции). Коэффициент при этих элементах должен быть больше любого другого элемента целевой функции. Принимаю значение диагональных элементов равное 13 500. С учетом вышесказанного и Таблицы 9, составляю Таблицу 10 на основе которой, будет решаться задача о назначениях.
Таблица 10.
Начнем со сравнения разности коэффициентов целевой функции основной и базовых строк.
1) Разности коэффициентов первой строки со второй (1-2):
1 столбец: 13000-7771=5229
2 столбец: 7771-13000=-5229
3 столбец: 6135-5681=454
4 столбец: 6365-9496=-3131
5 столбец: 9766-5628=4138
Наибольшая разность равна 5229 – в первом столбце, а значит элемент х11, не входит в оптимальный план, т.е. х11 = 0. Далее по величине разность равна 4138 (в пятом столбце). Тогда с11 = 7771+4138=11909.
Новое значение коэффициента вписываю в туже клетку (Таблица 10) и выделяю жирным шрифтом. Аналогично будут занесены и другие новые значения коэффициентов.
2) Разности коэффициентов первой строки с третьей (1-3):
1 столбец: 11909-6135=5774
2 столбец: 7771-5681=2090
3 столбец: 6135-13000=-6865
4 столбец: 6365-10975=-4610
5 столбец: 9766-3651=6115
Наибольшая разность равна 6115 – в пятом столбце. Элемент х15 не входит в оптимальный план. Далее по величине разность, равна 5774(в первом столбце). Тогда новое значение с15 = 3651+5774=9425
3) Разности коэффициентов первой строки с четвертой (1-4):
1 столбец: 11909-6365=5544
2 столбец: 7771-9496=-1725
3 столбец: 6135-10975=-4840
4 столбец:6365-13000=-6635
5 столбец:9425-12262=-2837
Наибольшая разность равна 5544– в первом столбце. Но элемент х11 и так не входит в оптимальный план. Поэтому для него только нахожу новое значение с11. Далее по величине разность, равна -1725 (во втором столбце). Тогда новое значение с11 = 6365-1725=4640.
4) Разности коэффициентов первой строки с пятой (1-5):
1 столбец: 4640-9766=-5126
2 столбец: 7771-5628=2143
3 столбец: 6135-3651=2484
4 столбец: 6365-12262=-5897
5 столбец: 9425-13000=-3575
Наибольшая разность равна 2484 – в третьем столбце, а значит элемент х13, не входит в оптимальный план, т.е. х13 = 0. Далее по величине разность равна 2143 (во втором столбце). Тогда с13 =2484+2143=4627.
Теперь сравним вторую строку с остальными.
1) Разности коэффициентов второй строки с первой (2-1):
1 столбец: 7771-4640=3131
2 столбец: 13000-7771=5229
3 столбец: 5681-4627=1054
4 столбец: 9496-6365=3131
5 столбец: 5628-9425=-3797
Наибольшая разность равна 5229 – во втором столбце, а значит элемент х22, не входит в оптимальный план, т.е. х22 = 0. Далее по величине разность равна 3131 (в первом столбце). Тогда с22 =7771+3131=10902.
2) Разности коэффициентов второй строки с третьей (2-3):
1 столбец: 7771-6135=1636
2 столбец: 10902-5681=5221
3 столбец: 5681-13000=-7319
4 столбец: 9496-10975=-1479
5 столбец: 5628-3651=1977
Наибольшая разность равна 5221- во втором столбце, а значит элемент х22, не входит в оптимальный план, т.е. х22 = 0. Далее по величине разность равна 1977 . Тогда с22 =5681+1977=7658.
3) Разности коэффициентов второй строки с четвертой (2-4):
1 столбец: 7771-6365=1406
2 столбец: 7658-9496=-1838
3 столбец: 5681-10975=-5294
4 столбец: 9496-13000=-3504
5 столбец: 5628-12262=-6634
Наибольшая разность равна 1406 – в первом столбце. Но элемент х21 и так не входит в оптимальный план. Поэтому для него только нахожу новое значение с21. Далее по величине разность, равна -1838.
Тогда новое значение с21 = 6365-1838=4527.
4) Разности коэффициентов второй строки с пятой (2-5):
1 столбец: 4527-9766=-5239
2 столбец: 7658-5628=2030
3 столбец: 5681-3651=2030
4 столбец: 9496-12262=-2766
5 столбец: 5628-13000=-7372
Так как максимальная разность отмечается в некоторых столбцах, никакого вывода сделать нельзя.
Теперь сравним третью строку с остальными.
1) Разности коэффициентов третьей строки с первой (3-1):
1 столбец: 6135-4640=1495
2 столбец: 5681-7771=-2090
3 столбец: 13000-4627=8373
4 столбец: 10975-6365=4610
5 столбец: 3651-9425=-5774
Наибольшая разность равна 8373 – в третьем столбце, а значит элемент х33, не входит в оптимальный план, т.е. х33 = 0. Далее по величине разность равна 4610 . Тогда с33 = 6135+4610=10745.
2) Разности коэффициентов третьей строки со второй (3-2):
1 столбец: 6135-4527=1608
2 столбец: 5681-7658=-1977
3 столбец: 10745-5681=5064
4 столбец: 10975-9496=1479
5 столбец: 3651-5628=-1977
Наибольшая разность равна 5064 – в третьем столбце. Но элемент х33 и так не входит в оптимальный план. Поэтому для него только нахожу новое значение с33. Далее по величине разность, равна 1608. Тогда новое значение с33 = 5681+1608=7289.
3) Разности коэффициентов третьей строки с четвертой (3-4):
1 столбец: 6135-6365=-230
2 столбец: 5681-9496=-3815
3 столбец: 7289-10975=-3686
4 столбец: 10975-13000=-2025
5 столбец: 3651-12262=-8611
Наибольшая разность равна -230 – в первом столбце, а значит элемент х31, не входит в оптимальный план, т.е. х31 = 0. Далее по величине разность равна - 2025 . Тогда с31 = 6365-2025=4340.
4) Разности коэффициентов третьей строки с пятой (3-5):
1 столбец: 4340-9766=-5426
2 столбец: 5681-5628=53
3 столбец:7289-3651=3638
4 столбец: 10975-12262=-1287
5 столбец:3651-13000=-9349
Наибольшая разность равна 3638 – в третьем столбце, а значит элемент х33, не входит в оптимальный план, т.е. х33 = 0. Далее по величине разность равна 53. Тогда с33 = 3638+53=3691.
Теперь сравним четвертую строку с остальными.
1) Разности коэффициентов четвертой строки с первой (4-1):
1 столбец: 6365-4640=1725
2 столбец: 9496-7771=1725
3 столбец:10975-4627=6348
4 столбец: 13000-6365=6635
5 столбец: 12262-9425=2837
Наибольшая разность равна 6635 – в четвертом столбце, а значит элемент х44 не входит в оптимальный план, т.е. х44 = 0. Далее по величине разность равна 6348. Тогда с44 = 6365+6348=12713.
2) Разности коэффициентов четвертой строки со второй (4-2):
1 столбец: 6365-4527=1838
2 столбец: 9496-7658=1838
3 столбец: 10975-5681=5294
4 столбец: 12713-9496=3217
5 столбец: 12262-5628=6634
Наибольшая разность равна 6634 – в пятом столбце, а значит элемент х45, не входит в оптимальный план, т.е. х45 = 0. Далее по величине разность равна 5294 . Тогда с45 =5628+5294=10922.
1) Разности коэффициентов четвертой строки с третьей (4-3):
1 столбец: 6365-4340=2025
2 столбец: 9496-5681=3815
3 столбец: 10975-3691=7284
4 столбец: 12713-10975=1738
5 столбец: 10922-3651=7271
Наибольшая разность равна 7284 – в третьем столбце, а значит х43 не входит в оптимальный план, т.е. х43 = 0. Далее по величине разность, равна 7271 . Тогда с43 = 3691+7271=10962.
3) Разности коэффициентов четвертой строки с пятой (4-5):
1 столбец: 6365-9766=-3401
2 столбец: 9496-5628=3868
3 столбец: 10962-3651=7311
4 столбец: 12713-12262=451
5 столбец: 10922-13000=-2078
Наибольшая разность равна 7311 – в третьем столбце, но элемент х43 и так не входит в оптимальный план. Поэтому нахожу новое значение коэффициента. Далее по величине разность, равна 3868 .
Тогда с43 = 3651+3868=7519.
Теперь сравним пятую строку с остальными.
1) Разности коэффициентов пятой строки с первой (5-1):
1 столбец: 9766-4640=5126
2 столбец: 5628-7771=-2143
3 столбец: 3651-4627=-976
4 столбец: 12262-6365=5897
5 столбец: 13000-9425=3575
Наибольшая разность равна 5897 – в четвертом столбце, а значит элемент х54 не входит в оптимальный план, т.е. х54 = 0. Далее по величине разность равна 5126 . Тогда с54 = 6365+5126=11491.
2) Разности коэффициентов пятой строки со второй (5-2):
1 столбец: 9766-4527=5239
2 столбец: 5628-7658=-2030
3 столбец: 3651-5681=-2030
4 столбец: 11491-9496=1995
5 столбец: 13000-5628=7372
Наибольшая разность равна 7372 – в пятом столбце. Элемент х55 не входит в оптимальный план, т.е. х55 = 0. Поэтому нахожу новое значение с55 . Далее по величине разность равна 5239 .
Тогда новое значение с55 = 5628+5239=10867
3)Разности коэффициентов пятой строки с третьей (5-3):
1 столбец: 9766-4340=5426
2 столбец: 5628-5681=-53
3 столбец: 3651-3691=-40
4 столбец: 11491-10975=516
5 столбец: 10867-3651=7216
Наибольшая разность равна 7216 – в пятом столбце. Элемент х55 не входит в оптимальный план, т.е. х55 = 0. Поэтому нахожу новое значение с55 . Далее по величине разность равна 5426.
Тогда новое значение с55 = 3651+5426=9077.
4) Разности коэффициентов пятой строки с четвертой (5-4):
1 столбец:9766-6365=3401
2 столбец: 5628-9496=-3868
3 столбец: 3651-7519=-3868
4 столбец: 11491-12713=-1222
5 столбец: 9077-10922=-1845
Наибольшая разность равна 3401 – в первом столбце. Элемент х51 и так не входит в оптимальный план, т.е. х51 =0. Поэтому нахожу новое значение с51 . Далее по величине разность равна -1222
Тогда новое значение с51 = 6365-1222=5143.
Из Таблицы 10 видно, что все элементы первого столбца равны нулю кроме х41. Элемент х41 = 1. Исключаем из рассмотрения столбец №1 и строку №4. Таблица 10
| 13000,11909, 4640 * | 6135,4627 * | 9766,9425 * | |||
| 7771,4527 * | 13000,10902, 7658 * | ||||
| 6135, 4340 * | 13000,10745, 7289,3691 * | ||||
| 10975, 10962 7519 * | 13000,12713 * | 12262, 10922 * | |||
| 9766, 5143 * | 12262, 11491 * | 13000, 10867, 9077 * |
Далее рассматриваем таблицу 11.
Таблица 11
| 7771,6617* | 6135,4627 * | 9766,9425 * | ||
| 13000,10902, 7658 * | ||||
| 13000,10745,7289 3691 * | ||||
| 13000,10867, 9077 * |
Перейдем к рассмотрению разности коэффициентов в столбцах.
Разность коэффициентов второго столбца с третьим (2-3):
1 строка: 7771-4627=3144
2 строка: 7658-5681=1977
3 строка: 5681-3691=1990
5 строка: 5628-3651=1977
Наибольшая разность равна 3144 – в первой строке. Элемент х21 не входит в оптимальный план, т.е. х21 = 0. Далее по величине разность равна 1990. Тогда новое значение с21 = 4627+1990=6617
Разность коэффициентов второго столбца с четвертым (2-4):
1 строка: 6617-6365=252
2 строка: 7658-9496=-1838
3 строка: 5681-10975=-5294
5 строка: 5628-11491=-5863
Наибольшая разность равна 252 – в первой строке. Элемент х21 не входит в оптимальный план, т.е. х21 = 0. Далее по величине разность равна -1838. Тогда новое значение с21 = 6365-1838=4527.
Разность коэффициентов второго столбца с пятым (2-5):
1 строка: 4527-9425=-4898
2 строка: 7698-5628=2030
3 строка: 5681-3651=2030
5 строка: 5628-9077=-3449
Так как максимальная разность отмечается в некоторых столбцах, никакого вывода сделать нельзя.
Теперь сравним 3 столбец со вторым (3-2)
1 строка: 4627-4527=100
2 строка: 5668-7658=-1977
3 строка: 3691-5681=-1990
5 строка: 3651-5628=-1977
Наибольшая разность равна 100 – в первой строке. Элемент х31 не входит в оптимальный план, т.е. х31 = 0. Далее по величине разность равна -1838. Тогда новое значение с31 = 4527-1977=2550
Теперь сравним 3 столбец с четвертым (3-4)
1 строка: 2550-6365=-3815
2 строка: 5681-9496=-3815
3 строка: 3691-10975=-7884
5 строка: 3651-11491=-7840
Так как максимальная разность отмечается в некоторых столбцах, никакого вывода сделать нельзя.
Теперь сравним 3 столбец с пятым (3-5):
1 строка: 2550-9425=-6875
2 строка: 5668-5628=53
3 строка: 3691-3651=40
5 строка: 3651-9077=-5426
Наибольшая разность равна 53 – во второй строке. Элемент х32 не входит в оптимальный план, т.е. х32 = 0. Далее по величине разность равна 40. Тогда новое значение с32 = 5628+40=5668.
Таблица12.
| 7771, 6617 , 4527* | 6135,4627, 2550 * | 9766,9425 * | ||
| 13000,10902, 7658 * | 5681,5668* | |||
| 13000,10745,7289 3691 * | ||||
| 13000,10867, 9077 * |
Из Таблицы 12 видно, что все элементы третьего столбца равны нулю кроме х53. Элемент х53 = 1. Исключаем из рассмотрения столбец №3 и строку №5.
Таблица 12 преобразовывается в Таблицу 13.
Таблица 13.
| 4527* | 9425* | ||
| 13000,10902, 7658* | |||
Таблица 14 примет вид:
| 9425* | ||
Анализируя данную таблицу, приходим к выводу, что решение не единственно. Годится и пара х14, х25 и пара х15, х24 . Представим решение в виде таблицы. Будет либо 1.х, либо 1.у.
Таблица А: