на тему- Прикладное применение задачи коммивояжера для специальностей- 230101 Вычислительные машины компл.html
Работа добавлена на сайт samzan.net:
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет имени М.Т. Калашникова»
(ФГБОУ ВПО «ИжГТУ имени М.Т. Калашникова»)
Сарапульский Политехнический Институт (филиал) ФГБОУ ВПО «ИжГТУ имени М.Т. Калашникова»
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к контрольной работе
по дисциплине «Логистика»
на тему: «Прикладное применение задачи коммивояжера»
для специальностей: 230101 «Вычислительные машины, комплексы, системы и сети», 210201 «Проектирование и технология радиоэлектронных средств», 080502 «Экономика и управление на предприятии (в машиностроении)», 080109 «Бухгалтерский учет, анализ и аудит»
очной и заочной форм обучения
|
Разработал: |
Галяутдинов Руслан Рамилевич, ст. преподаватель кафедры «Экономика и гуманитарные науки» |
Сарапул, 2014
СОДЕРЖАНИЕ
|
Теоретический материал ……………………………………………………. Задание к контрольной работе ……………………………………………... Варианты исходных данных ……………………………………………….. Приложения …………………………………………………………………. |
2 7 10 11 |
ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ
ВВЕДЕНИЕ
Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP). Также встречается название «задача о бродячем торговце». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута позволяющего коммивояжеру объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу, или минимальная длина пути.
Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ.
ОБЩИЙ ПЛАН РЕШЕНИЯ
Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующую последовательность действий:
1. Построение матрицы с исходными данными.
2. Нахождение минимума по строкам.
3. Редукция строк.
4. Нахождение минимума по столбцам.
5. Редукция столбцов.
6. Вычисление оценок нулевых клеток.
7. Редукция матрицы.
8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
9. Вычисление итоговой длины пути и построение маршрута.
ПОДРОБНАЯ МЕТОДИКА РЕШЕНИЯ
В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».
Итак, методика решения задачи коммивояжера:
1. Построение матрицы с исходными данными.
Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:
|
Город |
1 |
2 |
3 |
4 |
|
1 |
М |
5 |
11 |
9 |
|
2 |
10 |
М |
8 |
7 |
|
3 |
7 |
14 |
М |
8 |
|
4 |
12 |
6 |
15 |
М |
В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).
Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.
2. Нахождение минимума по строкам.
Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.
|
Город |
1 |
2 |
3 |
4 |
di |
|
1 |
М |
5 |
11 |
9 |
5 |
|
2 |
10 |
М |
8 |
7 |
7 |
|
3 |
7 |
14 |
М |
8 |
7 |
|
4 |
12 |
6 |
15 |
М |
6 |
3. Редукция строк.
Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).
|
Город |
1 |
2 |
3 |
4 |
di |
|
1 |
М |
0 |
6 |
4 |
5 |
|
2 |
3 |
М |
1 |
0 |
7 |
|
3 |
0 |
7 |
М |
1 |
7 |
|
4 |
6 |
0 |
9 |
М |
6 |
В итоге в каждой строке будет хотя бы одна нулевая клетка.
4. Нахождение минимума по столбцам.
Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку.
|
Город |
1 |
2 |
3 |
4 |
di |
|
1 |
М |
0 |
6 |
4 |
5 |
|
2 |
3 |
М |
1 |
0 |
7 |
|
3 |
0 |
7 |
М |
1 |
7 |
|
4 |
6 |
0 |
9 |
М |
6 |
|
dj |
0 |
0 |
1 |
0 |
5. Редукция столбцов.
Вычитаем из каждого элемента матрицы соответствующее ему dj.
|
Город |
1 |
2 |
3 |
4 |
di |
|
1 |
М |
0 |
5 |
4 |
5 |
|
2 |
3 |
М |
0 |
0 |
7 |
|
3 |
0 |
7 |
М |
1 |
7 |
|
4 |
6 |
0 |
8 |
М |
6 |
|
dj |
0 |
0 |
1 |
0 |
В итоге в каждом столбце будет хотя бы одна нулевая клетка.
6. Вычисление оценок нулевых клеток.
Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.
|
Город |
1 |
2 |
3 |
4 |
|
1 |
М |
0 (4) |
5 |
4 |
|
2 |
3 |
М |
0 |
0 |
|
3 |
0 |
7 |
М |
1 |
|
4 |
6 |
0 |
8 |
М |
И так по всем нулевым клеткам:
|
Город |
1 |
2 |
3 |
4 |
|
1 |
М |
0 (4) |
5 |
4 |
|
2 |
3 |
М |
0 (5) |
0 (1) |
|
3 |
0 (4) |
7 |
М |
1 |
|
4 |
6 |
0 (6) |
8 |
М |
7. Редукция матрицы.
Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).
|
Город |
1 |
2 |
3 |
4 |
|
1 |
М |
0 (4) |
5 |
4 |
|
2 |
3 |
М |
0 (5) |
0 (1) |
|
3 |
0 (4) |
7 |
М |
1 |
|
4 |
6 |
0 (6) |
8 |
М |
Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).
|
Город |
1 |
2 |
3 |
4 |
|
1 |
М |
0 (4) |
5 |
4 |
|
2 |
3 |
М |
0 (5) |
М |
|
3 |
0 (4) |
7 |
М |
1 |
|
4 |
6 |
M |
8 |
М |
8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
Если мы еще не нашли все отрезки пути, то возвращаемся ко второму пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д.
Если все отрезки пути найдены (или найдены еще не все отрезков, но оставшаяся часть пути очевидна) – переходим к пункту 9.
9. Вычисление итоговой длины пути и построение маршрута.
Найдя все отрезки пути, остается только соединить их между собой и рассчитать общую длину пути (стоимость поездки по этому маршруту, затраченное время и т.д.). Длины дорог соединяющих города берем из самой первой таблицы с исходными данными.
В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4.
Общая длина пути: L = 30.
ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ
Применение задачи коммивояжера на практике довольно обширно. В частности ее можно использовать для поиска кратчайшего маршрута при гастролях эстрадной группы по городам, нахождения последовательности технологических операций обеспечивающей наименьшее время выполнения всего производственного цикла и пр.
ЗАДАНИЕ К КОНТРОЛЬНОЙ РАБОТЕ
Цель контрольной работы: научиться на практике применять знания и навыки решения оптимизационных задач, полученные при прохождении курса дисциплины «Логистика», на примере «Travelling salesman problem» («Задача коммивояжера»).
Структура контрольной работы:
1. Титульный лист (1 стр.).
2. Бланк рецензии (1 стр.).
3. Введение (1 стр.).
4. Исходные данные – матрица цен и скриншоты (2-3 стр.).
5. Произвольный вариант маршрута – описание, граф, расчет стоимости (1 стр.).
6. Вычисленный вариант маршрута – ход решения, граф, общая стоимость (2-3 стр.).
7. Вывод (1 стр.).
Содержание контрольной работы: следуйте приведенным ниже рекомендациям при решении контрольной работы:
1. Напишите к контрольной работе введение, в котором кратко обозначьте ее цель, задачи, актуальность.
2. В таблице с исходными данными найдите те, что соответствуют Вашему варианту. Это будут названия семи городов мира, один из них (начальная и конечная точка пути) одинаков для всех – Москва. Моделируемая ситуация – туристическое путешествие по этим городам.
3. Воспользовавшись любым онлайн-сервисом заказа билетов на авиарейсы (примеры приведены в приложениях) составьте матрицу цен на перелеты из каждого города во все остальные на конкретную дату (в целях упрощения примем любую ближайшую дату за опорную). В итоге у Вас получится таблица, аналогичная изображенной ниже:
|
Город |
Город А |
Город B |
Город C |
Город D |
Город E |
Город F |
Город G |
|
Город А |
М |
8 200 |
9 500 |
12 855 |
8 780 |
5 550 |
12 500 |
|
Город B |
8 200 |
М |
7 550 |
6 250 |
4 700 |
14 500 |
8 245 |
|
Город C |
11 250 |
3 250 |
М |
3 650 |
11 450 |
7 800 |
9 650 |
|
Город D |
5 850 |
6 600 |
10 720 |
М |
4 400 |
12 500 |
12 300 |
|
Город E |
11 450 |
7 200 |
5 500 |
9 840 |
М |
11 050 |
3 580 |
|
Город F |
4 500 |
7 450 |
12 550 |
7 800 |
13 570 |
М |
9 580 |
|
Город G |
8 900 |
4 700 |
5 655 |
4 500 |
5 470 |
15 950 |
М |
Перелеты из города в этот же город, обозначим символом «M», как нецелесообразные.
Обратите внимание, что цены на билеты одного направления, но разных авиакомпаний будут отличаться. Поэтому в матрицу цен вносите либо средние значения, либо стоимость самого дешевого билета (рассматриваем эконом-класс).
Сделайте выборочные скриншоты веб-страниц с ценой на билеты любых 5-7 направлений (например: Москва - Париж, Пекин – Дели, и т.д.). Добавьте эти скриншоты в контрольную работу.
4. Предложите свой вариант маршрута, который позволит посетить все семь городов по одному разу и вернуться в исходную точку. На этом этапе не ставьте себе цель найти самый дешевый маршрут. Пока что просто составьте маршрут путешествия исходя из своего вкуса и предпочтений, и изобразите его в виде графа.
Опишите последовательность перелетов, рассчитайте стоимость всего маршрута.
5. Решите задачу коммивояжера о нахождении (в данном случае) самого дешевого маршрута на основе данных Вашей матрицы цен. Отразите основные этапы решения в контрольной работе. Постройте граф найденного маршрута, рассчитайте его общую стоимость.
6. Сделайте вывод. Сравните первый маршрут, составленный по наитию, и второй – найденный в рамках решения задачи коммивояжера. Оказался ли второй маршрут дешевле? Если да, то какую сумму позволило сэкономить применение данной оптимизационной задачи логистики?
Также подумайте, какие могут быть недостатки у второго оптимального маршрута? Какие факторы не были учтены при решении задачи о нахождении самого дешевого маршрута?
Изложите Ваши выводы, наблюдения и предложения в контрольной работе.
ВАРИАНТЫ ИСХОДНЫХ ДАННЫХ
|
ВАРИАНТ |
ИСХОДНЫЕ ДАННЫЕ |
||||||
|
1 город |
2 город |
3 город |
4 город |
5 город |
6 город |
7 город |
|
|
1 |
Москва |
Пекин |
Буэнос-Айрес |
Лондон |
Сидней |
Венеция |
Бангкок |
|
2 |
Москва |
Рим |
Рио-де-Жанейро |
Вена |
Сеул |
Париж |
Сидней |
|
3 |
Москва |
Дубай |
Берлин |
Бангкок |
Токио |
Венеция |
Стамбул |
|
4 |
Москва |
Прага |
Лондон |
Сидней |
Рим |
Буэнос-Айрес |
Дели |
|
5 |
Москва |
Каир |
Стамбул |
Париж |
Сидней |
Рио-де-Жанейро |
Дубай |
|
6 |
Москва |
Токио |
Буэнос-Айрес |
Сеул |
Венеция |
Прага |
Пекин |
|
7 |
Москва |
Рим |
Дели |
Берлин |
Лондон |
Вена |
Стамбул |
|
8 |
Москва |
Рио-де-Жанейро |
Париж |
Дубай |
Каир |
Бангкок |
Токио |
|
9 |
Москва |
Прага |
Лондон |
Пекин |
Дубай |
Стамбул |
Сидней |
|
10 |
Москва |
Берлин |
Каир |
Бангкок |
Буэнос-Айрес |
Париж |
Сеул |
|
11 |
Москва |
Сидней |
Венеция |
Вена |
Лондон |
Рио-де-Жанейро |
Дели |
|
12 |
Москва |
Пекин |
Стамбул |
Париж |
Прага |
Берлин |
Рим |
|
13 |
Москва |
Буэнос-Айрес |
Токио |
Сидней |
Каир |
Венеция |
Сеул |
|
14 |
Москва |
Дели |
Дубай |
Берлин |
Вена |
Бангкок |
Сидней |
|
15 |
Москва |
Прага |
Лондон |
Дели |
Буэнос-Айрес |
Токио |
Каир |
|
16 |
Москва |
Сеул |
Рим |
Рио-де-Жанейро |
Пекин |
Сидней |
Стамбул |
|
17 |
Москва |
Вена |
Париж |
Венеция |
Дубай |
Берлин |
Прага |
|
18 |
Москва |
Токио |
Буэнос-Айрес |
Бангкок |
Лондон |
Рим |
Дели |
|
19 |
Москва |
Стамбул |
Берлин |
Каир |
Вена |
Пекин |
Сидней |
|
20 |
Москва |
Рио-де-Жанейро |
Лондон |
Прага |
Сеул |
Токио |
Венеция |
|
21 |
Москва |
Пекин |
Дубай |
Рим |
Париж |
Буэнос-Айрес |
Дели |
|
22 |
Москва |
Вена |
Бангкок |
Токио |
Стамбул |
Каир |
Берлин |
|
23 |
Москва |
Каир |
Венеция |
Буэнос-Айрес |
Лондон |
Дубай |
Сеул |
|
24 |
Москва |
Рим |
Лондон |
Дели |
Прага |
Рио-де-Жанейро |
Бангкок |
|
25 |
Москва |
Париж |
Сеул |
Вена |
Берлин |
Токио |
Венеция |
|
26 |
Москва |
Каир |
Стамбул |
Рио-де-Жанейро |
Рим |
Париж |
Пекин |
|
27 |
Москва |
Прага |
Токио |
Венеция |
Бангкок |
Вена |
Дели |
|
28 |
Москва |
Рио-де-Жанейро |
Дели |
Пекин |
Буэнос-Айрес |
Сеул |
Дубай |
|
29 |
Москва |
Вена |
Берлин |
Сеул |
Париж |
Прага |
Стамбул |
|
30 |
Москва |
Пекин |
Дубай |
Бангкок |
Рим |
Каир |
Рио-де-Жанейро |
* Сидней (Австралия)
ПРИЛОЖЕНИЯ
Онлайн-сервисы для заказа авиабилетов:
- Яндекс. Авиабилеты. - http://ticket.yandex.ru/
- Skyscanner. Дешевые авиабилеты. - http://www.skyscanner.ru/
- ТуТу. Заказа авиабилетов и расписание. - http://avia.tutu.ru/
- Связной Travel. Авиабилеты онлайн. - https://www.svyaznoy.travel/
Дополнительная литература и Интернет-источники:
- Задача коммивояжера – метод ветвей и границ. [Электронный ресурс] - http://galyautdinov.ru/post.php?id=6&n=zadacha-kommivoyazhera
- Просветов Г. Математические методы в логистике. Задачи и решения. М.: Альфа-Пресс, 2008. – 304 с.
- Хэмди А. Таха. Введение в исследование операций. Киев.: Вильямс, 2007. – 912 с.
Образец титульного листа
МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Ижевский государственный технический университет имени М.Т. Калашникова»
(ФГБОУ ВПО «ИжГТУ имени М.Т. Калашникова»)
Сарапульский Политехнический Институт (филиал) ФГБОУ ВПО «ИжГТУ имени М.Т. Калашникова»
КОНТРОЛЬНАЯ РАБОТА
на тему: «Прикладное применение задачи коммивояжера»
по дисциплине «Логистика»
|
Выполнил: |
студент группы Б01-111-1, Иванов Петр Аркадьевич |
|
Проверил: |
ст. преподаватель кафедры «ЭГН», Галяутдинов Руслан Рамилевич |
Сарапул, 2013
Образец бланка рецензии
РЕЦЕНЗИЯ НА КОНТРОЛЬНУЮ РАБОТУ
Дата: ____________ Рецензент: ______ / Р.Р. Галяутдинов
2. купность приемов способов правил познавательной теоретической и практической преобразующей деят
3. ZSuit
4. тями эстет мышля писля
5. Лабораторная работа по дисциплине Теория автоматического управления Тема работы- расчет оптимального.html
6. Реферат- Роберт Винер - основатель кибернетики
7. Регистрации актов гражданского состояния
8. Гомельский государственный университет имени Франциска Скорины Геологогеографический факультет
9. Северные монастыри и их деятельность по хозяйственному освоению русского севера
10. Византия Современность 8 экскурсий Салоники ~ Касторья Корфу Метеора Дельфы Арголида Афины Сал
11. Приближенное значение корня начальное приближение может быть найдено различными способами- из физических
12. Задание 1 Ученый Онтология Аксиология
13. Центросоюз маркетинг вариант 15
14. ПОСОБИЕ ПО ОТЕЧЕСТВЕННОЙ ИСТОРИИ
15. Реферат на тему- Творча майстерність як основа підтримки саморозвиваючої особистості Проблема педагог
16. Тюменская государственная медицинская академия Министерства здравоохранения Российской Федерации ГБ
17. Административно-правовые нормы
18. Теория и поведение Раскольникова в романе ФДостоевского Преступление и наказание
19. здравого смысла
20. Исповедь на заданную тему