Автоматизация инженерно-строительных технологий

Министерство Общего Образования Российской Федерации.

Московский Государственный Строительный Университет.

Факультет: Механизация и автоматизация строительства Кафедра: Автоматизация инженерно-строительных технологий  

Содержание.

 

 

1. ВВЕДЕНИЕ.
1.1. Актуальность темы.
1.2 Цель работы.
1.3 Область применения.
1.4. Обзор других методов решения задачи коммивояжера.
2. ТЕОРИЯ ГРАФОВ.
2.1. Основные понятия теории графов. Определения.
2.2. Задача коммивояжера.
2.3. Метод ветвей и границ (МВГ).
3. ВЫБОР ОБЬЕКТА УПРАВЛЕНИЯ. АНАЛИЗ АСПЕКТОВ ЕГО РАБОТЫ.
4. ПОСТАНОВКА И РЕШЕНИЕ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ.
4.1. Выбор критерия оптимальности.
4.2. Выявление основных особенностей рассматриваемого объекта.
4.3. Пример решения задачи коммивояжера.
5. ВЫВОДЫ ПО КУРСОВОЙ РАБОТЕ.

 

 

ВВЕДЕНИЕ.

Актуальность темы.

Переборные алгоритмы не эффективны (в расчете на худшую задачу), поэтому успех в решении каждой конкретной задачи существенным образом зависит от… Знаменитая задача коммивояжера, поставленная еще в 1934 г., является одной из…

Цель работы.

Целью данной работы будет:

1. Познакомить читателя с основными понятиями теории графов.

2. Дать представление о задаче коммивояжера.

3. Описать метод ветвей и границ.

4. Привести пример использования метода ветвей и границ для решения задачи коммивояжера.

Область применения.

Задача коммивояжера является так называемой NP-трудной задачей, т.е. задачей, точное решение которой в общем случае может быть получено только за… Одним из подходов к ее решению является сокращение перебора методом ветвей и… Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного…

Обзор других методов решения задачи коммивояжера.

ТЕОРИЯ ГРАФОВ.

Основные понятия теории графов. Определения.

Граф G задается множеством точек или вершин x₁, x₂, …x_n (которое обозначается через X) и множеством линий или ребер a₁, a₂, …a_m (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается парой (X,A).

Если ребра из множества А ориентированны, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называют ориентированным графом. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Граф в этом случае обозначается парой G=(X, Г).

Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

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

Иногда дугам графа G сопоставляются (приписываются) числа - дуге (x_i,x_j) ставится в соответствие некоторое число c_{i j}, называемое весом, или длинной. Тогда граф G называется графом со взвешенными дугами. Иногда веса приписываются вершинам x_i графа, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. При рассмотрении пути , представленного последовательностью дуг, за его вес (или длину) принимается число , равное сумме весов всех дуг, входящих в , т.е. .

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

Если G = ( X, A ) – неориентированный граф с n вершинами, то остовным деревом ( или, короче, остовом) графа G называется всякий остовный подграф G, являющийся деревом (т.е. графом не имеющим циклов, в котором каждая пара вершин соединена одной и только одной простой цепью). Например, если G – граф, показанный на рис.1а, то графы на рис.1.б,в являются остовом этого графа.

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

Постановка задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3,4…n и вернуться… Задача коммивояжера является так называемой NP-трудной задачей, т.е. задачей,… Решение обобщенной задачи комми­вояжера

Метод ветвей и границ (МВГ).

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

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.

Описание метода ветвей и границ.

    Рис.2. Граф-дерево.

ВЫБОР ОБЬЕКТА УПРАВЛЕНИЯ. АНАЛИЗ АСПЕКТОВ ЕГО РАБОТЫ.

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

ПОСТАНОВКА И РЕШЕНИЕ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ.

Выбор критерия оптимальности.

Перечислим основные экономические показатели, связанные с работой робота: 1. Прямые затраты 1.1 Единовременные – по доставке машин.

Выявление основных особенностей рассматриваемого объекта.

    Таблица 1. *   …

Пример решения задачи коммивояжера.

Имеем «чисто» математическую задачу, которую решим, используя метод Ветвей и Границ.

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

Шаг 0. Значение. Пометим вершину 1 признаком

Шаг 1. Пометим вершину 3 признаками

Рис.3. Шаг З. Имеем .

Шаг 1. Пометим следующие вершины: вершину 4 –признаками вершину 5 –признаками

Шаг 3. Имеем .

Шаг 1. Пометим вершину 5 признаками

Шаг 3. Имеем .

Шаг 1. Пометим вершину 3 признаками

Шаг 3. Имеем .

Шаг 1. Пометим вершину 4 признаками

Шаг 1. Пометим вершину 2 –признаками так как , то искомый путь построен.

Шаг 2. Искомый путь составляет последовательность вершин 1, 5, 3, 4, 2.

Общее затрачиваемое время в пути составит 13.

 

ВЫВОДЫ ПО КУРСОВОЙ РАБОТЕ.

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

Еще раз отметим, что задача коммивояжера является одной из самых важнейших задач в теории графов. Возможность представления (записи) различных производственных процессов на языке теории графов и умение решить сформулированную математическую задачу позволяют найти оптимальную стратегию ведения хозяйства, сэкономить ресурсы, выполнить поставленную задачу в более короткие сроки. Очевидно, что изучение методов теории графов, методов математического программирования, системного анализа и пр. – является важным этапом подготовки инженеров в МГСУ.

 

 

Список литературы.

 

1. Н.М. Новикова «Основы оптимизации», курс лекций. М. 1998.

2. Н. Кристофидес «Теория графов. Алгоритмический подход», М., Мир, 1978.

3. С.Е. Канторер. «Методы обоснования эффективности применения машин в строительстве». М. 1969.

4. Институт математики им. С.Л. Соболева СО РАН Лаборатория "Математические модели принятия решений", статья «Метод ветвей и границ». Адрес в интернете : http://math.nsc.ru/AP/benchmarks/index.html.

5. Е.А.Тишкин «Эвристический алгоритм решения задачи коммивояжера». Публикация на сайте http://nit.itsoft.ru . Самарский государственный аэрокосмический университет, Россия.