Решение задачи коммивояжера

Введение.

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

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

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

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

- транспортную политику отдельных государств и международных союзов;

- законодательство стран, регулирующее деятельность в области грузоперевозок, международные соглашения и конвенции по перевозкам и транзиту, таможенное законодательство;

- технико-эксплуатационные характеристики различных видов транспорта;

- организацию и технику транспортных операций, упаковку, хранение, складирование;

- особенности отдельных транспортных направлений.

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

 

 

Цель курсовой работы.

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

Для этого в курсовой работе предлагается последовательно рассмотреть ряд задач.

Задачи:

- произвести расстановку воздушных судов на рейсы таким образом, чтобы суммарные затраты на транспортировку грузов были минимальными;

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

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

 

 

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 – в первом столбце, а значит элемент х₁₁ не входит в оптимальный план, т.е. х₁₁ = 0. Следующая по величине разность равна 36 (в третьем столбце). Тогда с₁₁ = 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 – в пятом столбце, а значит элемент х₁₅, не входит в оптимальный план, т.е. х₁₅ = 0. Следующая по величине разность равна - 182 (во втором столбце). Тогда с₁₅ = 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 – в первом столбце, а значит элемент х₁₁, не входит в оптимальный план, т.е. х₁₁ = 0. Следующая по величине разность равна -38 (в третьем столбце). Тогда с₁₁ = 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 – в первом столбце, а значит элемент х₁₁, не входит в оптимальный план, т.е. х₁₁ = 0. Следующая по величине разность равна 160 (в четвертом столбце). Тогда с₁₁= 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 – в четвертом столбце, а значит элемент х₂₄, не входит в оптимальный план, т.е. х₂₄ = 0. Следующая по величине разность равна -36 (в третьем столбце). Тогда с₂₄= 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 – в пятом столбце, а значит элемент х₂₅, не входит в оптимальный план, т.е. х₂₅ = 0. Следующая по величине разность равна 18 (во втором столбце). Тогда с₂₅= 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 – в третьем столбце, а значит элемент х₂₃, не входит в оптимальный план, т.е. х₂₃ = 0. Следующая по величине разность равна -588 (во втором столбце). Тогда с₂₃= 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 – в четвертом столбце, а значит элемент х₂₄, не входит в оптимальный план, т.е. х₂₄ = 0. Следующая по величине разность равна 112 (в первом столбце). Тогда с₂₄= 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 – в первом столбце, а значит элемент х₃₁, не входит в оптимальный план, т.е. х₃₁ = 0. Следующая по величине разность равна 301 (в четвертом столбце). Тогда с₃₁= 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 – в первом столбце, а значит элемент х₃₁, не входит в оптимальный план, т.е. х₃₁ = 0. Следующая по величине разность равна 133 (в четвертом столбце). Тогда с₃₁= 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– в четвертом столбце, а значит элемент х₃₄, не входит в оптимальный план, т.е. х₃₄ = 0. Следующая по величине разность равна 453 (в первом столбце). Тогда с₃₄= 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 – во втором столбце, а значит элемент х₄₂, не входит в оптимальный план, т.е. х₄₂ = 0. Следующая по величине разность равна 379 (в пятом столбце). Тогда с₄₂= 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 – во втором столбце, а значит элемент х₄₂, не входит в оптимальный план, т.е. х₄₂ = 0. Следующая по величине разность равна 352 (в пятом столбце). Тогда с₄₂= 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– в пятом столбце, а значит элемент х₅₅ не входит в оптимальный план, т.е. х₅₅ = 0. Следующая по величине разность равна -80 (во втором столбце). Тогда с₅₅= 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 – в третьем столбце, а значит элемент х₅₃ не входит в оптимальный план, т.е. х₅₃ = 0. Следующая по величине разность равна -320 (в первом столбце). Тогда с₅₃= 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– в третьей строке, а значит элемент х₁₃ не входит в оптимальный план, т.е. х₁₃ = 0. Следующая по величине разность равна 43 (во второй строке). Тогда с₁₃= 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– в четвертой строке, а значит элемент х₂₄ не входит в оптимальный план, т.е. х₂₄ = 0. Следующая по величине разность равна 153 (в пятой строке). Тогда с₂₄= 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– в пятой строке, а значит элемент х₂₅ не входит в оптимальный план, т.е. х₂₅ = 0. Следующая по величине разность равна 141 (в четвертой строке). Тогда с₂₅= 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– в третьей строке, а значит элемент х₃₃ не входит в оптимальный план, т.е. х₃₃ = 0. Следующая по величине разность равна -11 (в первой строке). Тогда с₃₃= 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– в третьей строке, а значит элемент х₃₃ не входит в оптимальный план, т.е. х₃₃ = 0. Следующая по величине разность равна -84 (в первой строке). Тогда с₃₃= 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– в первой строке, а значит элемент х₃₁ не входит в оптимальный план, т.е. х₃₁ = 0. Следующая по величине разность равна -133 (во второй строке). Тогда с₃₁= 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 *

Видно, что в третьем столбце все элементы, кроме х₄₃ равны нулю. Поэтому х₄₃ = 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 *

 

Видно, что во пятом столбце все элементы, кроме х₃₅ равны нулю. Поэтому х₃₅ = 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 – во втором столбце, а значит элемент х₁₂ не входит в оптимальный план, т.е. х₁₂ = 0. Следующая по величине разность равна 48 (в третьем столбце). Тогда с₁₁ = 260+48= 308.

 

Таблица 4

Столбцы   Строки
	601,351 *	424,308 *
			557,307 *
		344,336 *

 

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

 

Таблица 5.

Столбцы   Строки
	601,571,473,351 *

 

Итого получаю следующие отличные от нуля элементы: х₄₃ = 1; х₃₅ = 1;

х₂₂ = 1; х₅₄ = 1; х₁₄ = 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, не входит в оптимальный план, т.е. х₁₁ = 0. Следующая по величине разность равна 4138 (в пятом столбце). Тогда с₁₁ = 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 – в пятом столбце. Элемент х₁₅ не входит в оптимальный план. Следующая по величине разность, равна 5774(в первом столбце). Тогда новое значение с₁₅ = 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– в первом столбце. Но элемент х₁₁ и так не входит в оптимальный план. Поэтому для него только нахожу новое значение с₁₁. Следующая по величине разность, равна -1725 (во втором столбце). Тогда новое значение с₁₁ = 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 – в третьем столбце, а значит элемент х₁₃, не входит в оптимальный план, т.е. х₁₃ = 0. Следующая по величине разность равна 2143 (во втором столбце). Тогда с₁₃ =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 – во втором столбце, а значит элемент х₂₂, не входит в оптимальный план, т.е. х₂₂ = 0. Следующая по величине разность равна 3131 (в первом столбце). Тогда с₂₂ =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, не входит в оптимальный план, т.е. х₂₂ = 0. Следующая по величине разность равна 1977. Тогда с₂₂ =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 – в первом столбце. Но элемент х₂₁ и так не входит в оптимальный план. Поэтому для него только нахожу новое значение с₂₁. Следующая по величине разность, равна -1838.

Тогда новое значение с₂₁ = 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, не входит в оптимальный план, т.е. х₃₃ = 0. Следующая по величине разность равна 4610. Тогда с₃₃ = 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 – в третьем столбце. Но элемент х₃₃ и так не входит в оптимальный план. Поэтому для него только нахожу новое значение с₃₃. Следующая по величине разность, равна 1608. Тогда новое значение с₃₃ = 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, не входит в оптимальный план, т.е. х₃₁ = 0. Следующая по величине разность равна - 2025. Тогда с₃₁ = 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, не входит в оптимальный план, т.е. х₃₃ = 0. Следующая по величине разность равна 53. Тогда с₃₃ = 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 – в четвертом столбце, а значит элемент х₄₄ не входит в оптимальный план, т.е. х₄₄ = 0. Следующая по величине разность равна 6348. Тогда с₄₄ = 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, не входит в оптимальный план, т.е. х₄₅ = 0. Следующая по величине разность равна 5294. Тогда с₄₅ =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 – в третьем столбце, а значит х₄₃ не входит в оптимальный план, т.е. х₄₃ = 0_. Следующая по величине разность, равна 7271. Тогда с₄₃ = 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 – в третьем столбце, но элемент х₄₃ и так не входит в оптимальный план. Поэтому нахожу новое значение коэффициента. Следующая по величине разность, равна 3868.

Тогда с₄₃ = 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 – в четвертом столбце, а значит элемент х₅₄ не входит в оптимальный план, т.е. х₅₄ = 0. Следующая по величине разность равна 5126. Тогда с₅₄ = 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 – в пятом столбце. Элемент х₅₅ не входит в оптимальный план, т.е. х₅₅ = 0. Поэтому нахожу новое значение с₅₅ . Следующая по величине разность равна 5239.

Тогда новое значение с₅₅ = 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 – в пятом столбце. Элемент х₅₅ не входит в оптимальный план, т.е. х₅₅ = 0. Поэтому нахожу новое значение с₅₅ . Следующая по величине разность равна 5426.

Тогда новое значение с₅₅ = 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 – в первом столбце. Элемент х₅₁ и так не входит в оптимальный план, т.е. х₅₁ =0. Поэтому нахожу новое значение с₅₁ . Следующая по величине разность равна -1222

Тогда новое значение с₅₁ = 6365-1222=5143.

 

Из Таблицы 10 видно, что все элементы первого столбца равны нулю кроме х₄₁. Элемент х₄₁ = 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 – в первой строке. Элемент х₂₁ не входит в оптимальный план, т.е. х₂₁ = 0. Следующая по величине разность равна 1990. Тогда новое значение с₂₁ = 4627+1990=6617

 

Разность коэффициентов второго столбца с четвертым (2-4):

1 строка: 6617-6365=252

2 строка: 7658-9496=-1838

3 строка: 5681-10975=-5294

5 строка: 5628-11491=-5863

Наибольшая разность равна 252 – в первой строке. Элемент х₂₁ не входит в оптимальный план, т.е. х₂₁ = 0. Следующая по величине разность равна -1838. Тогда новое значение с₂₁ = 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 – в первой строке. Элемент х₃₁ не входит в оптимальный план, т.е. х₃₁ = 0. Следующая по величине разность равна -1838. Тогда новое значение с₃₁ = 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 – во второй строке. Элемент х₃₂ не входит в оптимальный план, т.е. х₃₂ = 0. Следующая по величине разность равна 40. Тогда новое значение с₃₂ = 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 видно, что все элементы третьего столбца равны нулю кроме х₅₃. Элемент х₅₃ = 1. Исключаем из рассмотрения столбец №3 и строку №5.

Таблица 12 преобразовывается в Таблицу 13.

Таблица 13.

	4527*		9425*
	13000,10902, 7658*

 

Таблица 14 примет вид:

		9425*

 

Анализируя данную таблицу, приходим к выводу, что решение не единственно. Годится и пара х₁₄, х₂₅ и пара х₁₅, х_24. Представим решение в виде таблицы. Будет либо 1.х, либо 1.у.

 

Таблица А:

1234Следующая ⇒ Поделиться с друзьями: Дата добавления: 2015-10-20; Мы поможем в написании ваших работ!; просмотров: 804 | Нарушение авторских прав Поиск на сайте: Лучшие изречения: Вы никогда не пересечете океан, если не наберетесь мужества потерять берег из виду. © Христофор Колумб ==> читать все изречения... 1471 - | 1382 - © 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.494 с.