Задача о коммивояжере

Задача о коммивояжере

Оглавление

Введение

Постановка задачи

Алгоритм решения .

Математическая модель задачи .

Описание программной реализации алгоритма .

Описание программного интерфейса

Описание программы .

Литература .

В настоящее время быстро развивается научно-техническая революция. Появившись в 40-х годах нашего столетия компьютеры и компьютерные технологии прошли за это время путь от ламповых систем с прямым заданием кодов операций до сверхбыстрых персональных компьютеров на монокристальной технологии, использующих при работе многопользовательские операционные системы с графическим интерфейсом. Наиболее бурное развитие компьютерных технологий произошло за последние 10-15 лет, после того как была разработана технология производства СБИС, а на их основе микрочипов. Также в начале 80-х годов начала развиваться концепция персональной ЭВМ, которая со временем выразилась в существовании двух наиболее распространенных аппаратных платформ: Macintosh (производится фирмой Apple, процессоры фирмы Motorola) и IBM PC (производится фирмой IBM, процессоры фирмы Intel).

Каждая из этих платформ имеет свою направленность и особенности. Компьютеры Macintosh в основном ориентированы на работу в глобальных сетях и обработку информации, как бы внешнего восприятия, то есть графической и звуковой. Их главными особенностями являются встроенная в ПЗУ (ROM) графическая операционная система и несовместимость различных моделей этой фирмы, однако за счет этого достигнут очень быстрый рост производительности процессоров и системы в целом.

Фирма IBM, в отличие от Apple, придерживается концепции открытой системы, что выражается в том, что, во-первых, IBM не имеет эксклюзивного права на производство и продажу IBM-совместимых компьютеров (их производит множество фирм, таких как Hewlett Packard, AT&T, Compaq и другие), а также полной совместимости поздних моделей с более ранними, что позволяло IBM долгое время удерживать рынок сбыта, несмотря на то, что в начале 90-х годов Macintosh-и заметно превосходили PC по производительности (сейчас, с появлением Pentium и PowerPC, Macintosh-и потеряли безоговорочное лидерство по производительности).

Персональные компьютеры сейчас в основном используются в четырех областях:

· обработка текстов и компьютерная верстка;

· хранение баз данных с возможностью быстрой их обработки;

· управление производственными процессами;

· анализ сложных процессов;

Также сейчас интенсивно развиваются еще несколько областей применения ПЭВМ, таких как компьютерные игры (в 1994 году 43% рынка программных продуктов составляли игровые программы), гео-информационные системы, обучающие системы и системы мультимедиа.

Программа данной курсовой работы входит в раздел "анализ сложных процессов". Данная область начала развиваться в середине 80-х годов, когда производительность ПЭВМ достигла достаточного уровня для обработки необходимых объемов информации в реальном масштабе времени, что позволило начать применение компьютеров в областях, связанных с контролем сложных процессов и их анализом. Одной из таких проблем стала оптимизация систем со многими неизвестными, когда некоторый параметр было необходимо свести к какому-либо значению или просто максимизировать.

Наиболее ярким и характерным примером применения задачи "О коммивояжере" стала оптимизация операций на конвейере: в 1984 году, после того как был проведен анализ последовательности и временных затрат на операции на конвейерах заводов компании "General Motors" и приняты рекомендованные меры, удалось увеличить общую производительность почти на 13% при неизменном числе рабочих и том же оборудовании. Расчеты производились на компьютерах IBM 360gr, которые в то время являлись одними из самых производительных систем в мире. Просчет и оптимизация 200 основных и 87 вспомогательных операций занял около 230 часов. Считается, что это было первое коммерческое применение компьютерных технологий в области управления производством в целом.

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

Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место.

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

Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

· маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;

· в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.

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

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

Общая схема метода такова (данная программная реализация):

1. Все множество разбивается на N-1 подмножеств, каждое из которых оценивается верхней и нижней оценками.

2. Производится отсев неоптимальных множеств по следующему критерию: если нижняя оценка (решение релаксированной задачи) больше минимальной из верхних оценок (решений нерелаксированной задачи), то множество считается очевидно неоптимальным и отсекается, иначе остается до следующей итерации.

3. Находится множество с лучшей нижней оценкой (прогнозом) и дробится на количество равное размерность исходной матрицы минус количество уже пройденных (фиксированных для данного множества) городов.

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

N - число городов.

Ci j , i, j=1 N - матрица затрат, где Ci j - затраты на переход из i-го города в j-й.

Xi j - матрица переходов с компонентами:

Xi j = 1, если коммивояжер совершает переход из i-го города в j-й,

Xi j = 0, если не совершает перехода,

где i, j = 1 N и i¹j.

Критерий:

(1)

Ограничения:

, i = 1 N (2)

, j = 1 N (3)

Ui - Uj + N × Xi j £ N-1, i, j = 1 N, i ¹ j. (4)

Доказательство, что модель (1-4) описывает задачу о коммивояжере:

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.

Рассмотрим условие (4). Применим метод доказательства от противного, то есть предположим, что условие (4) выполняется для некоторого подцикла T из R городов, где R<N. Сложив все неравенства (4) вдоль этого подцикла получим