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

Тип работы:
Контрольная
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

В соответствии со сказанным выше, элемент х12 не входит в оптимальный план, т. е. х12=0. следующая по величине разность равна 110. Поэтому с12=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

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

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

131−411=-280

239−236=3

439−334=105

252−380=-128

655−671=-16

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

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

131−150=-19

239−335=-96

337−530=-193

252−458=-206

655−800=-145

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

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

511−54=457

355−239=116

329−337=-8

162−252=-90

715−655=60

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

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

170−112=58

355−143=212

329−343=-14

162−644=-482

715−670=45

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

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

170−411=-241

201−236=-35

329−334=-5

162−458=-296

715−671=44

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

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

170−150=20

236−335=-99

334−530=-196

380−458=-78

671−800=-129

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

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

112−54=58

143−239=-96

343−337=6

644−252=392

670−655=15

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

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

112−72=40

143−201=-58

343−329=14

310−162=148

670−655=15

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

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

112−411=-299

143−236=-93

343−334=9

202−380=-178

670−671=-1

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

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

112−150=-38

143−335=-192

333−530=-197

202−458=-256

671−800=-129

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

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

411−54=357

236−239=-3

334−337=-3

380−252=128

671−655=16

Элемент х41 не входит в оптимальный план, т. е. х41=0. следующая по величине разность равна 128. Поэтому с41=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

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

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

236−143=93

334−333=1

197−202=-5

671−670=1

Элемент х42 не входит в оптимальный план, т. е. х42=0. следующая по величине разность равна 1. Поэтому с42=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

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

Таблица 5

ГОРОДА САМОЛЁТЫ

4

5

1

252

151

655

2

162

715

666

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

252−655=-403

162−666=-504

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

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

Таблица 6

ГОРОДА САМОЛЁТЫ

1

2

3

4

5

1

1

2

1

3

1

4

1

5

1

Следовательно, отличные от нуля элементы: х15=1, х24=1, х32=1, х43=1, х51=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э), скорость передвижения (Vp), времени, затраченного в начальных и конечных пунктах (tнк) и времени ожидания (tож).

Nncв — количество посадочных мест в вагоне;

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

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

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

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

Nncав — количество посадочных мест в автобусе;

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

Рnoc,Pвыс — производительность обслуживания пассажиров при посадке и при высадке в автобус.

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

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

tож = (tmax+tmin)/2=0.5 tин,

где,

tmax; tmin — максимальное и минимальное время ожидания очередного автобуса (ч);

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

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

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

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

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

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

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

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

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

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

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

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

Сi=Cnc*Qi*Tn*Kmy;

где

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

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

Tn — коэффициент транспортной усталости пассажира при поездки (принять равным 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=Cnc*Qi*Tn*Kmy=1000*1*7,87*1,4=11 018 (руб.);

1−3: Сi=Cnc*Qi*Tn*Kmy=1000*1*6,57*1,4=9198 (руб.);

1−4: Сi=Cnc*Qi*Tn*Kmy =1000*1*3,97*1,4=5558 (руб.);

1−5: Сi=Cnc*Qi*Tn*Kmy =1000*1*9,57*1,4=13 398 (руб.);

2−3: Сi=Cnc*Qi*Tn*Kmy =1000*1*5,07*1,4=7098 (руб.);

2−4: Сi=Cnc*Qi*Tn*Kmy =1000*1*2,72*1,4=3808 (руб.);

2−5: Сi=Cnc*Qi*Tn*Kmy =1000*1*10,37*1,4=14 518 (руб.);

3−4: Сi=Cnc*Qi*Tn*Kmy =1000*1*9,37*1,4=13 118 (руб.);

3−5: Сi=Cnc*Qi*Tn*Kmy =1000*1*9,77*1,4=13 678 (руб.);

4−5: Сi=Cnc*Qi*Tn*Kmy =1000*1*9,77*1,4=13 678 (руб.).

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

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

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+11 018=11668 (руб.);

1−3: Зij= Змаm+ Сi=670+9198=9868 (руб.);

1−4: Зij= Змаm+ Сi =780+5598=6378 (руб.);

1−5: Зij= Змаm+ Сi =1000+13 398=14398 (руб.);

2−3: Зij= Змаm+ Сi =560+7098=7658 (руб.);

2−4: Зij= Змаm+ Сi =940+3808=4748 (руб.);

2−5: Зij= Змаm+ Сi =660+14 518=15178 (руб.);

3−4: Зij= Змаm+ Сi =1200+13 118=14878 (руб.);

3−5: Зij= Змаm+ Сi =930+13 678=14608 (руб.);

4−5: Зij= Змаm+ Сi =1150+13 678=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=Cnc*Qi*Tn*Kmy=1000*1*8,2*1,6=13 120 (руб.);

1−3: Сi=Cnc*Qi*Tn*Kmy =1000*1*6,9 *1,6=11 040 (руб.);

1−4: Сi=Cnc*Qi*Tn*Kmy =1000*1*4,5*1,6=7200 (руб.);

1−5: Сi=Cnc*Qi*Tn*Kmy =1000*1*9,8 *1,6 =15 580 (руб.);

2−3: Сi=Cnc*Qi*Tn*Kmy =1000*1*5,5 *1,6=8800 (руб.);

2−4: Сi=Cnc*Qi*Tn*Kmy =1000*1*3,3*1,6 =5280 (руб.);

2−5: Сi=Cnc*Qi*Tn*Kmy =1000*1*10,6*1,6=16 960 (руб.);

3−4: Сi=Cnc*Qi*Tn*Kmy =1000*1*9,7*1,6=15 520 (руб.);

3−5: Сi=Cnc*Qi*Tn*Kmy =1000*1*10*1,6 =16 000 (руб.);

4−5: Сi=Cnc*Qi*Tn*Kmy =1000*1*10*1,6=16 000 (руб.).

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

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

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+13 120=13190 (руб.);

1−3: Зij= Змаm+ С =75+11 040=11115 (руб.);

1−4: Зij= Змаm+ Сi =90+7200=7290 (руб.);

1−5: Зij= Змаm+ Сi =85+15 580=15655 (руб.);

2−3: Зij= Змаm+ Сi =100+8800=8900 (руб.);

2−4: Зij= Змаm+ Сi =80+5280=5360 (руб.);

2−5: Зij= Змаm+ Сi =95+16 960=17055 (руб.);

3−4: Зij= Змаm+ Сi =65+15 520=15585 (руб.);

3−5: Зij= Змаm+ Сi =100+16 000=16100 (руб.);

4−5: Зij= Змаm+ Сi =90+16 000=16090 (руб.).

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

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

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

1

2

3

4

5

1

Х

11 668

9868

6378

14 398

2

11 668

Х

7658

4748

15 178

3

9868

7658

Х

14 878

14 608

4

6378

4748

14 878

Х

14 828

5

14 398

15 178

14 608

14 828

Х

Автомобильный

транспорт

1

Х

13 190

11 115

7290

15 655

2

13 190

Х

8900

5360

17 055

3

11 115

8900

Х

15 585

16 100

4

7290

5360

15 585

Х

16 090

5

15 655

17 055

16 100

16 090

Х

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

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

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

Таблица 4

1

2

3

4

5

1

15 200

13 878, 13 298

12 718

11 668

11 088, 10 508

9868

9288

6378

14 398

14 100

2

11 668

11 088

15 200

12 746, 9458

8878

7658

4748

15 178

11 890

3

9868

9288

7658

15 200

14 620, 14 016

14 878

11 710

14 608

4

6378

4748

14 878

14 298, 14 236

11 106

15 200

11 388

14 828

5

14 398

15 178

12 768, 12 188

14 608

14 028

14 828

11 118

15 200

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

15 200−11 668=3532

11 668−15 200=-3532

9868−7658=2210

6378−4748=1630

14 398−15 178=-780

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

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

13 878−9868=4010

11 668−7658=4010

9868−15 200=-5332

6378−14 878=-8500

14 398−14 608=-210

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

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

13 878−6378=7500

11 668−4748=6920

9868−14 878=-5010

6378−15 200=-8822

14 398−14 828=-430

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

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

13 298−14 398=-1100

11 668−15 178=-3510

9868−14 608=-4740

6378−14 828=-8450

14 398−15 200=-802

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

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

11 668−13 298=-1630

15 200−11 668=3532

7658−9868=-2210

4748−6378=-1630

15 178−14 100=1078

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

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

11 668−9868=1800

12 746−7658=5088

7658−15 200=-7542

4748−14 878=-10 130

15 178−14 608=570

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

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

11 668−6378=5290

9458−4748=4710

7658−14 878=-7220

4748−15 200=-10 452

15 178−14 828=350

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

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

11 088−14 398=-3310

9458−15 178=-5720

7658−14 608=-6950

4748−14 828=-10 080

15 178−15 200=-22

Элемент х25 не входит в оптимальный план, т. е. х25=0. следующая по величине разность равна -3310. Поэтому с25=15 200+(-3310)=11 890.

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

9868−13 298=-3430

7658−11 668=-4010

15 200−9868=5332

14 878−6378=8500

14 608−14 100=508

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

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

9868−11 088=-1220

7658−9458=-1800

15 200−7658=7542

11 710−4748=6962

14 608−11 890=2718

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

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

9868−6378=3490

7658−4748=2910

14 620−14 878=-258

11 710−15 200=-3490

14 608−14 828=-220

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

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

9288−14 398=-5110

7658−15 178=-7520

14 620−14 608=12

11 710−14 828=-3118

14 608−15 200=-592

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

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

6378−13 298=-6920

4748−11 668=-6920

14 878−9868=5010

15 200−6378=8822

14 828−14 100=728

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

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

6378−11 088=-4710

4748−9458=-4710

14 878−7658=7220

11 388−4748=6640

14 828−11 890=2938

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

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

6378−9288=-2910

4748−7658=-2910

14 298−14 016=282

11 388−11 710=-322

14 828−14 608=220

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

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

6378−14 398=-8020

4748−15 178=-10 430

14 236−14 608=-372

11 388−14 828=-3440

14 828−15 200=-372

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

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

14 398−13 298=1100

15 178−11 668=3510

14 608−9868=4740

14 828−6378=8450

15 200−14 100=1100

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

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

14 398−11 088=3310

15 178−9458=5720

14 608−7658=6950

11 118−4748=6370

15 200−14 608=3310

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

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

14 398−9288=5110

15 178−7658=7520

14 028−14 016=12

11 118−11 710=-592

15 200−14 608=592

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

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

14 398−6378=8020

12 768−4748=8020

14 028−14 236=-208

11 118−11 388=-270

15 200−14 828=372

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

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

13 298−11 668=1630

11 088−9458=1630

9288−7658=1630

6378−4748=1630

14 398−12 768=1630

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

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

13 298−9868=3430

11 088−7658=3430

9288−14 016=-4728

6378−14 236=-7858

14 398−14 028=370

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

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

13 298−6378=6920

11 088−4748=6340

9288−11 710=-2422

6378−11 388=-5010

14 398−11 118=3280

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

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

12 718−14 100=-1382

11 088−11 890=-802

9288−14 608=-5320

6378−14 828=-8450

14 398−15 200=-802

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

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

11 668−12 718=-1050

9458−11 088=-1630

7658−9288=-1630

4748−6378=-1630

12 768−14 398=-1680

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

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

11 088−9868=1220

9458−7658=1800

7658−14 016=-6358

4748−14 236=-9488

12 768−14 028=-1260

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

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

11 088−6378=4710

8878−4748=4130

7658−11 710=-4052

4748−11 388=-6640

12 768−11 118=1650

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

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

10 508−14 100=-3592

8878−11 890=-3012

7658−14 608=-6950

4748−14 828=-10 080

12 768−15 200=-2432

Элемент х52 не входит в оптимальный план, т. е. х52=0. следующая по величине разность равна -3012. Поэтому с52=15 200+(-3012)=12 188.

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

9868−12 718=-2850

7658−11 088=-3430

14 016−9288=4728

14 236−6378=7858

14 028−14 398=-370

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

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

9868−10 508=-640

7658−8878=-1220

14 016−7658=6358

11 106−4748=6358

14 028−12 188=1840

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

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

9868−6378=3490

7658−4748=2910

14 016−11 710=2306

11 106−11 388=-282

14 028−11 118=2910

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

Таблица 5

1

2

4

5

1

15 200

13 878, 13 298

12 718

11 668

11 088, 10 508

6378

14 398

14 100

3

9868

9288

7658

14 878

11 710

14 608

4

6378

4748

15 200

11 388

14 828

5

14 398

15 178

12 768, 12 188

14 828

11 118

15 200

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

Таблица 6

1

2

5

3

9868

9288

7658

14 608

4

6378

4748

14 828

11 698

5

14 398

15 178

12 768, 12 188

15 200

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

14 608−9288=5320

14 828−6378=8450

15 200−14 398=802

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

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

14 608−7658=6950

11 698−4748=6950

15 200−12 188=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+14 828+15178+7658+9868=53 910.

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

Заключение

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

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

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

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

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

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

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

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

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

ПоказатьСвернуть
Заполнить форму текущей работой