Единая транспортная система

Единая транспортная система

1. Задача 1

Из аэропорта должны вылететь пять воздушных судов (ВС) для доставки груза в пять городов. Затраты на полёт каждого из самолётов в каждый город представлены в табл. 1. Необходимо назначит ВС на рейсы таким образом, чтобы суммарные затраты на транспортировку грузов были минимальными.

Для создания математической модели обозначим назначение i-го самолёта для полёта в j-й город через х_ij. Так как количество самолётов равно количеству городов, и каждый самолёт может быть направлен только в один город, то х_ij принимает только два значения: единицу, если i-й самолёт направлен в j-й город, или нулю, в других случаях. Поэтому и . Суммарная стоимость полётов можно представить в виде суммы .

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

, , .

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

Введём некоторые определения. Нулевым элементом назовём переменную, которая равна нулю в оптимальном (или в оптимальных) решении. Основной строкой (столбцом) назовём строку (столбец), в которой определяется нулевой элемент. Базовой строкой (столбцом) назовём строку (столбец), с элементами которой сравниваются элементы основной строки при поиске нулевого элемента.

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

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

Более детально применение метода приведём на следующем примере. Представим условие задачи в виде таблицы с коэффициентами целевой функции (табл. 1).

Таблица 1. Затраты на полёт каждого из самолётов (тыс. руб.) в каждый из пяти городов

ГОРОДА САМОЛЁТЫ	1	2	3	4	5
1	131	530	439	252	655
2	511	355	329	162	715
3	112	143	343	644	670
4	411	236	334	380	671
5	150	335	530	458	800

Будем рассматривать разности коэффициентов первой строки со второй.

-511=-380

-355=175

-329=110

-162=90

-715=-60

В соответствии со сказанным выше, элемент х₁₂ не входит в оптимальный план, т.е. х₁₂=0. следующая по величине разность равна 110. Поэтому с₁₂=355+110=465. (Договоримся новые значения с_ij вписывать в ту же клеточку, но выделять их жирным шрифтом) (табл. 2)

Таблица 2

ГОРОДА САМОЛЁТЫ	1	2	3	4	5
1	131 54	530 465,239	439 337	252	655
2	511 170,72	355 201	329	162	715 666
3	112 21	143	343 333	644 310,202	670
4	411 182	236	334	380	671
5	150	335	530	458	800

Сравним первую строку с третьей.

-112=19

-143=322

-343=96

-644=-392

-670=-15

Элемент х₁₂ не входит в оптимальный план, т.е. х₁₂=0. следующая по величине разность равна 96. Поэтому с₁₂=143+96=239.

Теперь сравним первую строку с четвёртой.

-411=-280

-236=3

-334=105

-380=-128

-671=-16

Элемент х₁₃ не входит в оптимальный план, т.е. х₁₃=0. следующая по величине разность равна 3. Поэтому с₁₃=334+3=337.

Сравним первую строку с пятой.

-150=-19

-335=-96

-530=-193

-458=-206

-800=-145

Элемент х₁₁ не входит в оптимальный план, т.е. х₁₁=0. следующая по величине разность равна -96. Поэтому с₁₁=150+(-96)=54.

Перейдём ко 2 строке. Сравним её с 1.

-54=457

-239=116

-337=-8

-252=-90

-655=60

Элемент х₂₁ не входит в оптимальный план, т.е. х₂₁=0. следующая по величине разность равна 116. Поэтому с₂₁=54+116=170.

Сравним 2 строку с 3.

-112=58

-143=212

-343=-14

-644=-482

-670=45

Элемент х₂₂ не входит в оптимальный план, т.е. х₂₂=0. следующая по величине разность равна 58. Поэтому с₂₂=143+58=201.

Сравним 2 строку с 4.

-411=-241

-236=-35

-334=-5

-458=-296

-671=44

Элемент х₂₅ не входит в оптимальный план, т.е. х₂₅=0. следующая по величине разность равна -5. Поэтому с₂₅=671+(-5)=666.

Сравним 2 строку с 5.

-150=20

-335=-99

-530=-196

-458=-78

-800=-129

Элемент х₂₁ не входит в оптимальный план, т.е. х₂₁=0. следующая по величине разность равна -78. Поэтому с₂₁=150+(-78)=72.

Теперь сравним 3 строку с остальными строками.

-54=58

-239=-96

-337=6

-252=392

-655=15

Элемент х₃₄ не входит в оптимальный план, т.е. х₃₄=0. следующая по величине разность равна 58. Поэтому с₃₄=252+58=310.

Сравним 3 строку со 2.

-72=40

-201=-58

-329=14

-162=148

-655=15

Элемент х₃₄ не входит в оптимальный план, т.е. х₃₄=0. следующая по величине разность равна 40. Поэтому с₃₄=162+40=202.

Сравним 3 строку с 4.

-411=-299

-236=-93

-334=9

-380=-178

-671=-1

Элемент х₃₃ не входит в оптимальный план, т.е. х₃₃=0. следующая по величине разность равна -1. Поэтому с₃₃=334+(-1)=333.

Сравним 3 строку с 5.

-150=-38

-335=-192

-530=-197

-458=-256

-800=-129

Элемент х₃₁ не входит в оптимальный план, т.е. х₃₁=0. следующая по величине разность равна -129. Поэтому с₃₁=150+(-129)=21.

Перейдём к 4 строке. Сравним её с 1 строкой.

-54=357

-239=-3

-337=-3

-252=128

-655=16

Элемент х₄₁ не входит в оптимальный план, т.е. х₄₁=0. следующая по величине разность равна 128. Поэтому с₄₁=54+128=182. Отсюда пятая строка и первый столбец уходят. Табл. 2 вырождается в табл. 3.

Таблица 3

ГОРОДА САМОЛЁТЫ	2	3	4	5
1	530 465,239	439 337	252	655
2	355 201	329	162	715 666
3	143	343 333	644 310,202	670
4	236 144	334	380 197	671

Сравним 4 строку со 2.

-201=35

-329=5

-162=218

-666=5

Элемент х₄₄ не входит в оптимальный план, т.е. х₄₄=0. следующая по величине разность равна 35. Поэтому с₄₄=162+35=197.

Сравним 4 строку с 3.

-143=93

-333=1

-202=-5

-670=1

Элемент х₄₂ не входит в оптимальный план, т.е. х₄₂=0. следующая по величине разность равна 1. Поэтому с₄₂=143+1=144. Отсюда третья строка и второй столбец уходят. Табл. 3 вырождается в табл. 4.

Таблица 4

ГОРОДА САМОЛЁТЫ	3	4	5
1	439 337	252	655
2	329 299	162	715 666
4	334	380 197	671

Перейдём к столбцам. Сравним 3 столбец с 4.

-252=85

-162=167

-197=137

Элемент х₂₃ не входит в оптимальный план, т.е. х₂₃=0. следующая по величине разность равна 137. Поэтому с₂₃=162+137=299. Отсюда третий столбец и четвёртая строка уходят. Табл. 4 вырождается в табл. 5.

Таблица 5

ГОРОДА САМОЛЁТЫ	4	5
1	252 151	655
2	162	715 666

Сравним 4 столбец с 5.

-655=-403

-666=-504

Элемент х₁₄ не входит в оптимальный план, т.е. х₁₄=0. следующая по величине разность равна-504. Поэтому с₁₄=655+(-504)=151. Отсюда четвёртый столбец и вторая строка уходят.

Таким образом, решение имеет следующий вид:

Таблица 6

ГОРОДА САМОЛЁТЫ	1	2	3	4	5
1					1
2				1
3		1
4			1
5	1

Следовательно, отличные от нуля элементы: х₁₅=1, х₂₄=1, х₃₂=1, х₄₃=1, х₅₁=1. В результате проведенных расчетов получилось, что нужно назначить 5 самолет на рейс в 1 город, 3 самолет на рейс во 2 город, 4 самолет на рейс в 3 город, 2 самолет на рейс в 4 город и 1 самолет на рейс в 5 город. При таком расположении самолетов на рейсах затраты на транспортировку грузов будут минимальными. Значение целевой функции равно:

С =655+162+143+334+150=1444.

2. Задача 2

самолет затрата транспортировка маршрут

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

Первая часть посвящена формированию базы данных для решения задачи.

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

Будем считать, что расстояния (км) между пунктами представлены в табл. 1. каждый пункт имеет путь сообщения со всеми остальными, протяжённость между городами «туда и обратно» - одинаковая.

Расстояния (км) между пунктами

	1	2	3	4	5
1	Х	530	439	252	655
2	530	Х	329	162	715
3	439	329	Х	644	670
4	252	162	644	Х	671
5	655	715	670	671	Х

Затраты времени пассажира на поездку (Т_n) при использовании железнодорожного транспорта определяются исходя из протяжённости маршрута (L_э), скорость передвижения (V_p), времени, затраченного в начальных и конечных пунктах (t_нк) и времени ожидания (t_ож).

N_nc^в - количество посадочных мест в вагоне;

N_в - количество вагонов в железнодорожном составе;

К_исn - коэффициент использования посадочных мест;

Р_noc,P_выс - производительность обслуживания пассажиров при посадке и при высадке в вагон.

Затраты времени пассажира на поездку (Т_n) при использовании автомобильного транспорта определяются:

N_nc^ав - количество посадочных мест в автобусе;

К_исn - коэффициент использования посадочных мест;

Р_noc,P_выс - производительность обслуживания пассажиров при посадке и при высадке в автобус.

Время ожидания пассажиром очередного автобуса на остановочном пункте является функцией интервала движения между ними (t_ин).

В момент одновременного подхода пассажира и автобуса к остановке, время ожидания будет минимальным, т.е. t_ож = t_min. Когда пассажир подходит к остановке в момент отхода автобуса, время ожидания будет максимальным, т.е. t_ож = t_max= t_ин. Таким образом, среднее ожидание автобуса можно рассчитать:

t_ож = (t_max+t_min)/2=0.5 t_ин,

где,

t_max; t_min - максимальное и минимальное время ожидания очередного автобуса (ч);

t_ин- интервал движения автобуса (ч).

Время начальных и конечных операций рассчитывается исходя из количества пассажирских мест, коэффициента использования загрузки (0,7-0,8) и производительности обслуживания пассажиров при посадке или высадке.

Производительность обслуживания пассажиров:

. при посадке в транспортное средство:

автобус - 60 человек в час;

самолёт - 200 человек в час;

электропоезд - 3000 человек в час.

. при высадке пассажиров в конечном пункте:

автобус - 100 человек в час;

самолёт - 400 человек в час;

электропоезд - 4500 человек в час.

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

С_i=C_nc*Q_i*T_n*K_my;

где

C_nc - стоимость пассажирочаса (принять равным 500-1500 руб.),

Q_i - число пассажиров, следующих по i-му варианту перевозки;

T_n - коэффициент транспортной усталости пассажира при поездки (принять равным 1,1-1,9), в зависимости от полученных результатов аеализа технико-экономических характеристик рассматриваемых видов транспорта;

Эффективность маршрута может быть оценена разностью затрат:

где

З_ij(a) и З_ij(в) - абсолютные затраты на поездку по рассматриваемым вариантам (а - транспорт; в-транспорт).

З_ij= З_маm+ С_i,

где

Исходные данные для расчёта затрат на поездку

Вариант	Виды транспорта
	Железнодорожный				Автомобильный
	Кол-во вагонов	Время ожидания (мин.)	Кол-во мест в вагоне	Скорость (км/ч)	Интервал движения (мин.)	Кол-во мест в салоне	Скорость (км/ч)
10	11	12	62	72	28	48	75

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

Технико-экономические особенности и преимущества жд транспорта заключаются в следующем:

. массовость перевозок и высокая проводная способность

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

. возможность сооружения пути на любой сухопутной территории

. регулярность перевозок независимо от времени года, времени суток, климатических условий

. возможность создания прямой связи между крупными предприятиями по подъездным путям

. сравнительно невысокая себестоимость перевозок

Железнодорожный транспорт и далее будет оставаться ведущим видом транспорта страны.

Недостатки:

. Большая капиталоемкость сооружений

. большая металлоемкость

. низкий уровень качества транспортных услуг

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

Расчёт затрат времени пассажира на поездку при использовании железнодорожного транспорта:

Участки маршрута

t_нк = 0,16+0,11=0,27 ч

t_ож=12/60=0,2 ч

1-2:

-3:

-4:

-5:

-3:

-4:

-5:

-4:

-5:

-5:

Расчёт стоимости пассажиро-часов пребывания пассажира в пути:

Участки маршрута

-2: С_i=C_nc*Q_i*T_n*K_my=1000*1*7,87*1,4=11018 (руб.);

-3: С_i=C_nc*Q_i*T_n*K_my=1000*1*6,57*1,4=9198 (руб.);

1-4: С_i=C_nc*Q_i*T_n*K_my =1000*1*3,97*1,4=5558 (руб.);

-5: С_i=C_nc*Q_i*T_n*K_my =1000*1*9,57*1,4=13398 (руб.);

-3: С_i=C_nc*Q_i*T_n*K_my =1000*1*5,07*1,4=7098 (руб.);

-4: С_i=C_nc*Q_i*T_n*K_my =1000*1*2,72*1,4=3808 (руб.);

-5: С_i=C_nc*Q_i*T_n*K_my =1000*1*10,37*1,4=14518 (руб.);

-4: С_i=C_nc*Q_i*T_n*K_my =1000*1*9,37*1,4=13118 (руб.);

-5: С_i=C_nc*Q_i*T_n*K_my =1000*1*9,77*1,4=13678 (руб.);

-5: С_i=C_nc*Q_i*T_n*K_my =1000*1*9,77*1,4=13678 (руб.).

Расчёт материальных затрат на поездку согласно стоимости билета:

Участки маршрута

1-2: 650 (руб.);	2-4: 940 (руб.);
1-3: 670 (руб.);	2-5: 660 (руб.);
1-4: 780 (руб.);	3-4: 1200 (руб.);
1-5: 1000 (руб.);	3-5: 930 (руб.);
2-3: 560 (руб.);	4-5: 1150 (руб.).

Рассчитаем абсолютные затраты пассажира на поездку:

Участки маршрута

-2: З_ij= З_маm+ С_i=650+11018=11668 (руб.);

-3: З_ij= З_маm+ С_i=670+9198=9868 (руб.);

-4: З_ij= З_маm+ С_i =780+5598=6378 (руб.);

-5: З_ij= З_маm+ С_i =1000+13398=14398 (руб.);

-3: З_ij= З_маm+ С_i =560+7098=7658 (руб.);

-4: З_ij= З_маm+ С_i =940+3808=4748 (руб.);

-5: З_ij= З_маm+ С_i =660+14518=15178 (руб.);

-4: З_ij= З_маm+ С_i =1200+13118=14878 (руб.);

-5: З_ij= З_маm+ С_i =930+13678=14608 (руб.);

-5: З_ij= З_маm+ С_i =1150+13678=14828 (руб.).

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

Достоинства:

. высокая маневренность и подвижность

. способность обеспечивать доставку «от двери до двери» без дополнительных перевалок и пересадок в пути следования

. высокая скорость доставки, особенно на короткие дистанции

. широкий спектр применения по сферам сообщения и расстояниям перевозки

. необходимость меньших капиталовложений в строительство автодорог при малых потоках пассажиров

Недостатки:

. высока себестоимость перевозок

. высокий уровень загрязнения окружающей среды

. большая трудоемкость работ

. большая металлоемкость и энергоемкость

. высокая изношенность подвижного состава, невысокая грузоподъемность транспортных средств

Расчёт затрат времени пассажира на поездку при использовании автомобильного транспорта:

Участки маршрута

t_нк = 0,56+0,336=0,896 ч

t_ож=0,5*(28/60)=0,23 ч

1-2:

-3:

-4:

-5:

-3:

-4:

-5:

-4:

-5:

-5:

Расчёт стоимости пассажиро-часов пребывания пассажира в пути:

Участки маршрута

-2: С_i=C_nc*Q_i*T_n*K_my=1000*1*8,2*1,6=13120 (руб.);

-3: С_i=C_nc*Q_i*T_n*K_my =1000*1*6,9 *1,6=11040 (руб.);

1-4: С_i=C_nc*Q_i*T_n*K_my =1000*1*4,5*1,6=7200 (руб.);

-5: С_i=C_nc*Q_i*T_n*K_my =1000*1*9,8 *1,6 =15580 (руб.);

-3: С_i=C_nc*Q_i*T_n*K_my =1000*1*5,5 *1,6=8800 (руб.);

-4: С_i=C_nc*Q_i*T_n*K_my =1000*1*3,3*1,6 =5280 (руб.);

-5: С_i=C_nc*Q_i*T_n*K_my =1000*1*10,6*1,6=16960 (руб.);

-4: С_i=C_nc*Q_i*T_n*K_my =1000*1*9,7*1,6=15520 (руб.);

-5: С_i=C_nc*Q_i*T_n*K_my =1000*1*10*1,6 =16000 (руб.);

-5: С_i=C_nc*Q_i*T_n*K_my =1000*1*10*1,6=16000 (руб.).

Расчёт материальных затрат на поездку согласно стоимости билета:

Участки маршрута

1-2: 70 (руб.);	2-4: 80 (руб.);
1-3: 75 (руб.);	2-5: 95 (руб.);
1-4: 90 (руб.);	3-4: 65 (руб.);
1-5: 85 (руб.);	3-5: 100 (руб.);
2-3: 100 (руб.);	4-5: 90 (руб.).

Рассчитаем абсолютные затраты пассажира на поездку:

Участки маршрута

-2: З_ij= З_маm+ С_i=70+13120=13190 (руб.);

-3: З_ij= З_маm+ С =75+11040=11115 (руб.);

-4: З_ij= З_маm+ С_i =90+7200=7290 (руб.);

-5: З_ij= З_маm+ С_i =85+15580=15655 (руб.);

-3: З_ij= З_маm+ С_i =100+8800=8900 (руб.);

-4: З_ij= З_маm+ С_i =80+5280=5360 (руб.);

-5: З_ij= З_маm+ С_i =95+16960=17055 (руб.);

-4: З_ij= З_маm+ С_i =65+15520=15585 (руб.);

-5: З_ij= З_маm+ С_i =100+16000=16100 (руб.);

-5: З_ij= З_маm+ С_i =90+16000=16090 (руб.).

После проведённых расчётов заполняется рабочая табл. 3 исходных данных.

Затраты на поездку специалиста ремонтного завода (ден. ед.)

Железнодорожный транспорт		1	2	3	4	5
	1	Х	11668	9868	6378	14398
	2	11668	Х	7658	4748	15178
	3	9868	7658	Х	14878	14608
	4	6378	4748	14878	Х	14828
	5	14398	15178	14608	14828	Х
Автомобильный транспорт	1	Х	13190	11115	7290	15655
	2	13190	Х	8900	5360	17055
	3	11115	8900	Х	15585	16100
	4	7290	5360	15585	Х	16090
	5	15655	17055	16100	16090	Х

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

Составим матрицу коэффициентов целевой функции. Не допустимо, чтобы коммивояжер из некоторого города возвращался туда и обратно. Поэтому все диагональные элементы должны быть равны нулю. Чтобы добиться этого, достаточно положить их очень большими (ввести так называемые штрафные функции). Коэффициент при этих элементах должен быть больше любого другого элемента целевой функции. В нашем случае самое большое число - 15178, следовательно, диагональные элементы будут равны 15200.

Рассмотрим табл. 3, заменим диагональные коэффициенты штрафной функцией и решаем задачу о назначениях (табл. 4).

Таблица 4

	1	2	3	4	5
1	15200 13878, 13298 12718	11668 11088, 10508	9868 9288	6378	14398 14100
2	11668 11088	15200 12746, 9458 8878	7658	4748	15178 11890
3	9868 9288	7658	15200 14620, 14016	14878 11710	14608
4	6378	4748	14878 14298, 14236 11106	15200 11388	14828
5	14398	15178 12768, 12188	14608 14028	14828 11118	15200

Будем рассматривать разности коэффициентов первой строки со второй.

-11668=3532

-15200=-3532

-7658=2210

-4748=1630

-15178=-780

Элемент х₁₁ не входит в оптимальный план, т.е. х₁₁=0. следующая по величине разность равна 2210. Поэтому с₁₁=11668+2210=13878.

Сравним первую строку с третьей.

-9868=4010

-7658=4010

-15200=-5332

-14878=-8500

-14608=-210

Так как максимальная разница отмечается в нескольких столбцах, никакого вывода сделать нельзя.

Теперь сравним первую строку с четвёртой.

-6378=7500

-4748=6920

-14878=-5010

-15200=-8822

-14828=-430

Элемент х₁₁ не входит в оптимальный план, т.е. х₁₁=0. следующая по величине разность равна 6920. Поэтому с₁₁=6378+6920=13298.

Сравним первую строку с пятой.

-14398=-1100

-15178=-3510

-14608=-4740

-14828=-8450

-15200=-802

Элемент х₁₅ не входит в оптимальный план, т.е. х₁₅=0. следующая по величине разность равна -1100. Поэтому с₁₅=15200+(-1100)=14100.

Перейдём ко 2 строке. Сравним её с 1.

-13298=-1630

-11668=3532

-9868=-2210

-6378=-1630

-14100=1078

Элемент х₂₂ не входит в оптимальный план, т.е. х₂₂=0. следующая по величине разность равна 1078. Поэтому с₂₂=11668+1078=12746.

Сравним 2 строку с 3.

-9868=1800

-7658=5088

-15200=-7542

-14878=-10130

-14608=570

Элемент х₂₂ не входит в оптимальный план, т.е. х₂₂=0. следующая по величине разность равна 1800. Поэтому с₂₂=7658+1800=9458.

Сравним 2 строку с 4.

-6378=5290

-4748=4710

-14878=-7220

-15200=-10452

-14828=350

Элемент х₂₁ не входит в оптимальный план, т.е. х₂₁=0. следующая по величине разность равна 4710. Поэтому с₂₁=6378+4710=11088.

Сравним 2 строку с 5.

-14398=-3310

-15178=-5720

-14608=-6950

-14828=-10080

-15200=-22

Элемент х₂₅ не входит в оптимальный план, т.е. х₂₅=0. следующая по величине разность равна -3310. Поэтому с₂₅=15200+(-3310)=11890.

Теперь сравним 3 строку с остальными строками.

-13298=-3430

-11668=-4010

-9868=5332

-6378=8500

-14100=508

Элемент х₃₄ не входит в оптимальный план, т.е. х₃₄=0. следующая по величине разность равна 5332. Поэтому с₃₄=6378+5332=11710.

Сравним 3 строку со 2.

-11088=-1220

-9458=-1800

-7658=7542

-4748=6962

-11890=2718

Элемент х₃₃ не входит в оптимальный план, т.е. х₃₃=0. следующая по величине разность равна 6962. Поэтому с₃₃=7658+6962=14620.

Сравним 3 строку с 4.

-6378=3490

-4748=2910

-14878=-258

-15200=-3490

-14828=-220

Элемент х₃₁ не входит в оптимальный план, т.е. х₃₁=0. следующая по величине разность равна 2910. Поэтому с₃₁=6378+2910=9288.

Сравним 3 строку с 5.

-14398=-5110

-15178=-7520

-14608=12

-14828=-3118

-15200=-592

Элемент х₃₃ не входит в оптимальный план, т.е. х₃₃=0. следующая по величине разность равна -592. Поэтому с₃₃=14608+(-592)=14016.

Перейдём к 4 строке. Сравним её с 1 строкой.

-13298=-6920

-11668=-6920

-9868=5010

-6378=8822

-14100=728

Элемент х₄₄ не входит в оптимальный план, т.е. х₄₄=0. следующая по величине разность равна 5010. Поэтому с₄₄=6378+5010=11388.

Сравним 4 строку со 2.

-11088=-4710

-7658=7220

-4748=6640

-11890=2938

Элемент х₄₃ не входит в оптимальный план, т.е. х₄₃=0. следующая по величине разность равна 6640. Поэтому с₄₃=7658+6640=14298.

Сравним 4 строку с 3.

-9288=-2910

-7658=-2910

-14016=282

-11710=-322

-14608=220

Элемент х₄₃ не входит в оптимальный план, т.е. х₄₃=0. следующая по величине разность равна 220. Поэтому с₄₃=14016+220=14236.

Сравним 4 строку с 5.

-14398=-8020

-15178=-10430

-14608=-372

-14828=-3440

-15200=-372

Нельзя сделать вывода.

Перейдём к 5 строке. Сравним её с 1.

-13298=1100

-11668=3510

-9868=4740

-6378=8450

-14100=1100

Элемент х₅₄ не входит в оптимальный план, т.е. х₅₄=0. следующая по величине разность равна 4740. Поэтому с₅₄=6378+4740=11118.

Сравним 5 строку со 2.

-11088=3310

-9458=5720

-7658=6950

-4748=6370

-14608=3310

Элемент х₅₃ не входит в оптимальный план, т.е. х₅₃=0. следующая по величине разность равна 6370. Поэтому с₅₃=7658+6370=14028.

Сравним 5 строку с 3.

-9288=5110

-7658=7520

-14016=12

-11710=-592

-14608=592

Элемент х₅₂ не входит в оптимальный план, т.е. х₅₂=0. следующая по величине разность равна 5110. Поэтому с₅₂=7658+5110=12768.

Сравним 5 строку с 4.

-6378=8020

-4748=8020

-14236=-208

-11388=-270

-14828=372

Нельзя сделать вывод.

Перейдём к столбцам. Сравним 1 столбец со 2.

-11668=1630

-9458=1630

-7658=1630

-4748=1630

-12768=1630

Нельзя сделать вывода.

Сравним 1 столбец с 3.

-9868=3430

-7658=3430

-14016=-4728

-14236=-7858

-14028=370

Нельзя сделать вывод.

Сравним 1 столбец с 4.

-6378=6920

-4748=6340

-11710=-2422

-11388=-5010

-11118=3280

Элемент х₁₁ не входит в оптимальный план, т.е. х₁₁=0. следующая по величине разность равна 6340. Поэтому с₁₁=6378+6340=12718.

Сравним 1 столбец с 5.

-14100=-1382

-11890=-802

-14608=-5320

-14828=-8450

-15200=-802

Нельзя сделать вывод.

Перейдём ко 2 столбцу. Сравним его с 1.

-12718=-1050

-11088=-1630

-9288=-1630

-6378=-1630

-14398=-1680

Элемент х₁₂ не входит в оптимальный план, т.е. х₁₂=0. следующая по величине разность равна -1630. Поэтому с₁₂=12718+(-1630)=11088.

Сравним 2 столбец с 3.

-9868=1220

-7658=1800

-14016=-6358

-14236=-9488

-14028=-1260

Элемент х₂₂ не входит в оптимальный план, т.е. х₂₂=0. следующая по величине разность равна 1220. Поэтому с₂₂=7658+1220=8878.

Сравним 2 столбец с 4.

-6378=4710

-4748=4130

-11710=-4052

-11388=-6640

-11118=1650

Элемент х₁₂ не входит в оптимальный план, т.е. х₁₂=0. следующая по величине разность равна 4130. Поэтому с₁₂=6378+4130=10508.

Сравним 2 столбец с 5.

-14100=-3592

-11890=-3012

-14608=-6950

-14828=-10080

-15200=-2432

Элемент х₅₂ не входит в оптимальный план, т.е. х₅₂=0. следующая по величине разность равна -3012. Поэтому с₅₂=15200+(-3012)=12188.

Перейдём к 3 столбцу. Сравним его с 1.

-12718=-2850

-11088=-3430

-9288=4728

-6378=7858

-14398=-370

Элемент х₄₃ не входит в оптимальный план, т.е. х₄₃=0. следующая по величине разность равна 4728. Поэтому с₄₃=6378+4728=11106.

Сравним 3 столбец со 2.

-10508=-640

-8878=-1220

-7658=6358

-4748=6358

-12188=1840

Нельзя сделать вывод.

Сравним 3 столбец с 4.

-6378=3490

-4748=2910

-11710=2306

-11388=-282

-11118=2910

Элемент х₁₃ не входит в оптимальный план, т.е. х₁₃=0. следующая по величине разность равна 2910. Поэтому с₁₃=6378+2910=9288. Отсюда третий столбец и вторая строка уходят. Табл. 4 вырождается в табл. 5.

Таблица 5

	1	2	4	5
1	15200 13878, 13298 12718	11668 11088, 10508	6378	14398 14100
3	9868 9288	7658	14878 11710	14608
4	6378	4748	15200 11388	14828
5	14398	15178 12768, 12188	14828 11118	15200

Из табл. 5 уходят 4 столбец и первая строка и табл. 5 вырождается в табл. 6.

Таблица 6

	1	2	5
3	9868 9288	7658	14608
4	6378	4748	14828 11698
5	14398	15178 12768, 12188	15200

Сравним 5 столбец с 1.

-9288=5320

-6378=8450

-14398=802

Элемент х₄₅ не входит в оптимальный план, т.е. х₄₅=0. следующая по величине разность равна 5320. Поэтому с₄₅=6378+5320=11698.

Сравним 5 столбец со 2.

-7658=6950

-4748=6950

-12188=3012

Нельзя сделать вывод.

-3; 1-4; 4-5; 3-1; 5-2

Таблица 7

	1	2	3	4	5
1				1
2			1
3	1
4					1
5		1

Строим маршрут:

-4-5-2-3-1. Значение целевой функции равно

С =6378+14828+15178+7658+9868=53910.

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

Заключение

Подведем итоги по выполненной курсовой работе. Мы последовательно рассмотрели ряд задач:

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

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

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

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

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

1.   Большедворская Л.Г Единая транспортная система. Часть1.-М.:МГТУГА, 2007

2.      Большедворская Л.Г. Единая транспортная система. Часть 2.-М.:МГТУГА, 2008

.        Большедворская Л.Г., Петрунин С.В. Единая транспортная система и география транспорта. Пособие по выполнению курсовой работы - М.: МГТУГА, 2009