Рассмотрим разность коэффициентов третьей строки с пятой
В 1 столбце: 13562-7140=6422
В 2 столбце: 4166-15666=-11500
В 3 столбце: 17000-8110=8890
В 4 столбце: 11708-5820=5888
В 5 столбце: 8110-17000=-8890
Отсюда Х33= 0, поэтому С33 8110+6422=14532
Рассмотрим разность коэффициентов четвертой строки с первой:
В 1 столбце: 13378-12592=786
В 2 столбце: 1186-2506=-1320
В 3 столбце: 14020-13562=458
В 4 столбце: 17000-9712=7288
В 5 столбце: 5820-7140=-1320
Отсюда Х44 = 0, поэтому С44 = 9712+786=10498
Рассмотрим разность коэффициентов четвертой строки со второй:
В 1 столбце: 13378-5508=7870
В 2 столбце: 1186-3750=2564
В 3 столбце: 14020-6478=7542
В 4 столбце: 10498-1186=9312
В 5 столбце: 5820-8383=-2564
Отсюда Х44= 0, поэтому С44 =186+7870=9056
Рассмотрим разность коэффициентов четвертой строки с третьей:
В 1 столбце: 13378-13562=-184
В 2 столбце: 1186-4166=-2980
В 3 столбце: 14020-14532=-512
В 4 столбце: 9056-11708=-2652
В 5 столбце: 5820-8110=-2290
Отсюда Х41 = 0, поэтому С41 = 13562-512=13050
Рассмотрим разность коэффициентов четвертой строки с пятой:
В 1 столбце: 13050-7140=5910
В 2 столбце: 1186-15666=-14480
В 3 столбце: 14020-8110=5910
В 4 столбце: 9056-5820=3236
В 5 столбце: 5820-17000=-11180
Х
Рассмотрим разность коэффициентов пятой строки с первой:
В 1 столбце: 7140-12592=-5452
В 2 столбце: 15666-2506=13160
В 3 столбце: 8110-13562=-5452
В 4 столбце: 5820-9712=-3892
В 5 столбце: 17000=7140-9860
Отсюда Х52 = 0, поэтому С52 = 2506+9860=12366
Видно, что во2толбце все элементы, кроме Х42авны 0. Поэтому Х42= 1, строка 4 и столбец 2 исключаются из рассмотрения.
Рассмотрим разность коэффициентов пятой строки со второй:
В 1 столбце: 7140-5508=1632
В 2 столбце: 8110-6478=1632
В 3 столбце: 5820-1186=4634
В 5 столбце: 17000-8384=8616
Отсюда Х55 = 0, поэтому С55 = 8384+4634=13018
Рассмотрим разность коэффициентов пятой строки с третьей:
В 1 столбце: 7140-13562=-6422
В 2 столбце:8110-14532=-6422
В 3 столбце: 5820-11708=-5888
В 5 столбце: 13018-8110=4908
Отсюда Х52 = 0, поэтому С52 = 8110-5888=2222
Столбцы:
Перейдем к столбцам.
Рассмотрим 1 столбец:
С 3олбцом: вывод сделать нельзя
С 4 столбцом: Х21 =0, С21=1186+2888=4066
С 5 столбцом: вывод сделать нельзя
Рассмотрим 3столбец:
С 1 столбцом: вывод сделать нельзя
С 5столбцом: вывод сделать нельзя
Рассмотрим 5столбец:
С 1 столбцом: вывод сделать нельзя
С 3 столбцом: вывод сделать нельзя
Таким образом, табл. 7 переходит в табл. 8
Табл. 8
| Строки Столбцы | 1 | 3 | 5 |
| 1 | 17000 12592 | 13562 | 7140 |
| 3 | 13562 | 17000 14532 | 8110 |
| 5 | 7140 | 8110 | 2222 1688 |
Таким образом, задача имеет 2 варианта решения:
Табл. 11
| Строки Столбцы | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | ||||
| 2 | 1 | ||||
| 3 | 1 | ||||
| 4 | 1 | ||||
| 5 | 1 |
1-3-5-1 и 2-4-2
Табл. 12
| Строки Столбцы | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | ||||
| 2 | 1 | ||||
| 3 | 1 | ||||
| 4 | 1 | ||||
| 5 | 1 |
1-5-3-1 и 2-4-2
Для решения рассчитываем 1 цельный маршрут путем приращения. Рассчитываем величину приращения нового маршрута с учетом вводимого пункта. Критерием для размещения очередного пункта является минимальное увеличение затрат.
L123=5508+10758-13562=2704
l326=10758+1566-8110=18314
L521=15666+5508-7140=14034
L142=13378+1186-5508=9056
L243=1186+14020-10758=4448
L345=14020+5820-8110=11730
L541=5820+13378-7140=12058
Решение имеет вид: 1-5-3-2-4-1
| Строки Столбцы | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | ||||
| 2 | 1 | ||||
| 3 | 1 | ||||
| 4 | 1 | ||||
| 5 | 1 |
Это и будет решением коммивояжера.
Затраты на поездку будут равны:
С= 7140+8110+5778+1186+10290=32504(р).
Заключение.
В данной курсовой работе были решены задачи:
- проведена расстановка ВС на рейсы таким образом, чтобы суммарные затраты на транспортировку грузов были минимальны, С= 1208(тыс.р.);
- рассчитаны материальные затраты специалиста авиаремонтного завода при последовательном посещении им пяти городов для заключения договоров на поставку запасных частей, 2-4-3-5-1-2 ;
- построен оптимальный маршрут поездки для специалиста авиаремонтного завода, который для заключения договоров о поставках запасных частей должен побывать в каждом из пяти городов по одному разу и вернуться в начальный пункт. Общие затраты на поездку при этом минимальны, 1-5-3-2-4-1, С = 32504(р).
Из двух видов транспорта выбрали автомобильный, т.к. по затратам на маршруте он меньше железнодорожного.
Данные задачи транспортного типа носят название задач о назначениях. В работе для ее решения мы воспользовались методом ПС, предложенный Петруниным С.В. Применение метода к задаче о назначении состоит из 2 этапов:
3. нахождение элемента, не входящего в оптимальный план (т.е., равного нулю);
4. изменение коэффициента этого элемента в целевой функции.
Была решена задача относящиеся к часто встречающимся задачам в экономике, которые носят название задачи коммивояжера. Постановки задачи такова: имеется n городов, расстояния или стоимость заданы матрицей. │cij│, I = 1, n; j = 1,n. Коммивояжер должен побывать в каждом городе один раз и вернуться в исходный пункт маршрута, затратив при этом минимум денег.
Для ее решения использовали тот же ПС – метод.
Решение задачи коммивояжера состоит из двух этапов:
1. решается задача о назначениях;
2. ищется собственно решение исходной задачи.
Список рекомендуемой литературы
1. Болшедворская Л.Г. Пособие по практическим занятиям по дисциплине «Единая транспортная система и география транспорта» для студентов специальности 080507 всех форм обучения. – М.: МГТУГА,2009.
2. Большедворская Л.Г. Единая транспортная система. Учебное пособие. - М.: МГТУГА,2008.
3. Петрунин С.И. Организационные и логические методы повышения эффективности производственной деятельности авиакомпаний. – М.: Авиа Безнес Групп, 2006.