Требования к содержанию и оформлению отчёта

Отчёт выполняется машинописным способом на листах формата А4, текст располагается с одной стороны. Титульный лист стандартной формы, с указанием темы работы, номера варианта, ФИО и номера группы студента, ФИО и должности преподавателя. Листы отчёта помещаются в скоросшиватель. Допускается скреплять листы степлером и помещать в полиэтиленовый файл.

Отчёт должен включать в себя следующие разделы:

1. номер варианта и матрицу, задающую взвешенный орграф;

2. графическое изображение взвешенного орграфа;

3. ход решения задачи с указанием промежуточных кратчайших путей:

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

Контрольные вопросы

1. В чём заключается задача о нахождении кратчайшего пути?

2. В каких сферах деятельности менеджера требуется решение задачи о кратчайшем пути?

3. Какую форму могут быть условия задачи о кратчайшем пути?

4. Что является решением задачи о кратчайшем пути?

Лабораторная работа №4

Решение задачи коммивояжера методом перебора Цель работы

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

Краткие теоретические сведения

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

Все возможные варианты перемещения из одного пункта к другому, а также расходы на перемещение можно иллюстрировать с помощью графа.

Задача коммивояжера называется также задачей о наименьшем покрытии.

Таким образом, исходные данные для решаемой задачи – это граф, дугам которого приписаны положительные числа - затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги - туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б - в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А. Каждая вершина может быть посещена не более одного раза.

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:

 - составить наиболее выгодный маршрут обхода наладчика в цехе (контролера, охранника, милиционера), отвечающего за должное функционирование заданного множества объектов (каждый из этих объектов моделируется вершиной графа);

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

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

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

Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра – методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time алгоритмы, то есть постепенно улучшающие некоторое текущее приближенное решение.

Задача коммивояжёра есть NP-полная задача⁷. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

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

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

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

Зависимость количества итераций от числа вершин не линейна. Например, для графа из трёх вершин общее количество маршрутов составит , из четырёх – , из пяти – и т.д.

Из приведённых данных следует, что средствами MS Excel, не прибегая к возможностям языка программирования, имеет смысл решать задачи с размерностью 3 и 4. Однако усвоение порядка работы алгоритма перебора на простых вариантах в дальнейшем облегчит решение задач большей размерности с помощью языков программирования.