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

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

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

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

131-511=-380

530-355=175

439-329=110

252-162=90

655-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

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

131-112=19

465-143=322

439-343=96

252-644=-392

655-670=-15

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

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

131-411=-280

239-236=3

439-334=105

252-380=-128

655-671=-16

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

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

131-150=-19

239-335=-96

337-530=-193

252-458=-206

655-800=-145

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

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

511-54=457

355-239=116

329-337=-8

162-252=-90

715-655=60

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

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

170-112=58

355-143=212

329-343=-14

162-644=-482

715-670=45

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

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

170-411=-241

201-236=-35

329-334=-5

162-458=-296

715-671=44

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

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

170-150=20

236-335=-99

334-530=-196

380-458=-78

671-800=-129

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

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

112-54=58

143-239=-96

343-337=6

644-252=392

670-655=15

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

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

112-72=40

143-201=-58

343-329=14

310-162=148

670-655=15

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

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

112-411=-299

143-236=-93

343-334=9

202-380=-178

670-671=-1

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

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

112-150=-38

143-335=-192

333-530=-197

202-458=-256

671-800=-129

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

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

411-54=357

236-239=-3

334-337=-3

380-252=128

671-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.

236-201=35

334-329=5

380-162=218

671-666=5

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

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

236-143=93

334-333=1

197-202=-5

671-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.

337-252=85

329-162=167

334-197=137

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

Таблица 5

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

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

252-655=-403

162-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) и производительности обслуживания пассажиров при посадке или высадке.

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

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

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

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

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

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

- автобус - 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,

где

З_маm - материальные затраты на поездку по рассматриваемому маршруту с использованием выбранных видов транспорта.

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

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

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

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

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

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

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

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

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

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

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

Недостатки:

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

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

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

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

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

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

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

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

1-2:

1-3:

1-4:

1-5:

2-3:

2-4:

2-5:

3-4:

3-5:

4-5:

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

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

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

1-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 (руб.);

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

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

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

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

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

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

4-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 (руб.).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Недостатки:

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

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

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

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

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

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

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

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

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

1-2:

1-3:

1-4:

1-5:

2-3:

2-4:

2-5:

3-4:

3-5:

4-5:

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

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

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

1-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 (руб.);

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

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

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

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

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

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

4-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 (руб.).

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

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

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

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

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

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

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

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

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

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

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

4-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

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

15200-11668=3532

11668-15200=-3532

9868-7658=2210

6378-4748=1630

14398-15178=-780

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

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

13878-9868=4010

11668-7658=4010

9868-15200=-5332

6378-14878=-8500

14398-14608=-210

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

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

13878-6378=7500

11668-4748=6920

9868-14878=-5010

6378-15200=-8822

14398-14828=-430

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

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

13298-14398=-1100

11668-15178=-3510

9868-14608=-4740

6378-14828=-8450

14398-15200=-802

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

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

11668-13298=-1630

15200-11668=3532

7658-9868=-2210

4748-6378=-1630

15178-14100=1078

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

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

11668-9868=1800

12746-7658=5088

7658-15200=-7542

4748-14878=-10130

15178-14608=570

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

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

11668-6378=5290

9458-4748=4710

7658-14878=-7220

4748-15200=-10452

15178-14828=350

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

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

11088-14398=-3310

9458-15178=-5720

7658-14608=-6950

4748-14828=-10080

15178-15200=-22

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

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

9868-13298=-3430

7658-11668=-4010

15200-9868=5332

14878-6378=8500

14608-14100=508

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

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

9868-11088=-1220

7658-9458=-1800

15200-7658=7542

11710-4748=6962

14608-11890=2718

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

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

9868-6378=3490

7658-4748=2910

14620-14878=-258

11710-15200=-3490

14608-14828=-220

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

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

9288-14398=-5110

7658-15178=-7520

14620-14608=12

11710-14828=-3118

14608-15200=-592

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

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

6378-13298=-6920

4748-11668=-6920

14878-9868=5010

15200-6378=8822

14828-14100=728

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

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

6378-11088=-4710

4748-9458=-4710

14878-7658=7220

11388-4748=6640

14828-11890=2938

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

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

6378-9288=-2910

4748-7658=-2910

14298-14016=282

11388-11710=-322

14828-14608=220

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

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

6378-14398=-8020

4748-15178=-10430

14236-14608=-372

11388-14828=-3440

14828-15200=-372

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

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

14398-13298=1100

15178-11668=3510

14608-9868=4740

14828-6378=8450

15200-14100=1100

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

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

14398-11088=3310

15178-9458=5720

14608-7658=6950

11118-4748=6370

15200-14608=3310

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

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

14398-9288=5110

15178-7658=7520

14028-14016=12

11118-11710=-592

15200-14608=592

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

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

14398-6378=8020

12768-4748=8020

14028-14236=-208

11118-11388=-270

15200-14828=372

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

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

13298-11668=1630

11088-9458=1630

9288-7658=1630

6378-4748=1630

14398-12768=1630

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

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

13298-9868=3430

11088-7658=3430

9288-14016=-4728

6378-14236=-7858

14398-14028=370

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

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

13298-6378=6920

11088-4748=6340

9288-11710=-2422

6378-11388=-5010

14398-11118=3280

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

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

12718-14100=-1382

11088-11890=-802

9288-14608=-5320

6378-14828=-8450

14398-15200=-802

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

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

11668-12718=-1050

9458-11088=-1630

7658-9288=-1630

4748-6378=-1630

12768-14398=-1680

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

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

11088-9868=1220

9458-7658=1800

7658-14016=-6358

4748-14236=-9488

12768-14028=-1260

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

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

11088-6378=4710

8878-4748=4130

7658-11710=-4052

4748-11388=-6640

12768-11118=1650

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

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

10508-14100=-3592

8878-11890=-3012

7658-14608=-6950

4748-14828=-10080

12768-15200=-2432

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

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

9868-12718=-2850

7658-11088=-3430

14016-9288=4728

14236-6378=7858

14028-14398=-370

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

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

9868-10508=-640

7658-8878=-1220

14016-7658=6358

11106-4748=6358

14028-12188=1840

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

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

9868-6378=3490

7658-4748=2910

14016-11710=2306

11106-11388=-282

14028-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.

14608-9288=5320

14828-6378=8450

15200-14398=802

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

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

14608-7658=6950

11698-4748=6950

15200-12188=3012

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

2-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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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