Построение матрицы с исходными данными

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К контрольной работе

по дисциплине «Логистика»

на тему: «Прикладное применение задачи коммивояжера»

для специальностей: 230101 «Вычислительные машины, комплексы, системы и сети», 210201 «Проектирование и технология радиоэлектронных средств», 080502 «Экономика и управление на предприятии (в машиностроении)», 080109 «Бухгалтерский учет, анализ и аудит»

очной и заочной форм обучения

Разработал:

Галяутдинов Руслан Рамилевич, ст. преподаватель кафедры «Экономика и гуманитарные науки»

Сарапул, 2014

СОДЕРЖАНИЕ

Теоретический материал ……………………………………………………. Задание к контрольной работе ……………………………………………... Варианты исходных данных ……………………………………………….. Приложения ………………………………………………………………….

ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ

ВВЕДЕНИЕ

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP). Также встречается название «задача о бродячем торговце». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута позволяющего коммивояжеру объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу, или минимальная длина пути.

Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ.

ОБЩИЙ ПЛАН РЕШЕНИЯ

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

1. Построение матрицы с исходными данными.

2. Нахождение минимума по строкам.

3. Редукция строк.

4. Нахождение минимума по столбцам.

5. Редукция столбцов.

6. Вычисление оценок нулевых клеток.

7. Редукция матрицы.

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.

9. Вычисление итоговой длины пути и построение маршрута.

ПОДРОБНАЯ МЕТОДИКА РЕШЕНИЯ

В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».

Итак, методика решения задачи коммивояжера:

Построение матрицы с исходными данными.

Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:

Город
	М
		М
			М
				М

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.