Реферат Курсовая Конспект
Автоматизация инженерно-строительных технологий - раздел Строительство, Министерство Общего Образования Российской Федерации....
|
Министерство Общего Образования Российской Федерации.
Содержание.
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. ВЫВОДЫ ПО КУРСОВОЙ РАБОТЕ. |
ВВЕДЕНИЕ.
Цель работы.
Целью данной работы будет:
1. Познакомить читателя с основными понятиями теории графов.
2. Дать представление о задаче коммивояжера.
3. Описать метод ветвей и границ.
4. Привести пример использования метода ветвей и границ для решения задачи коммивояжера.
ТЕОРИЯ ГРАФОВ.
Основные понятия теории графов. Определения.
Граф G задается множеством точек или вершин x1, x2, …xn (которое обозначается через X) и множеством линий или ребер a1, a2, …am (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается парой (X,A).
Если ребра из множества А ориентированны, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называют ориентированным графом. Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Граф в этом случае обозначается парой G=(X, Г).
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Ориентированной цепью называется такой путь, в котором каждая дуга используется не больше одного раза. Простой цепью называется такой путь, в котором каждая вершина используется не более одного раза. Очевидно, что простая орцепь является также орцепью, но обратное уже неверно.
Иногда дугам графа G сопоставляются (приписываются) числа - дуге (xi,xj) ставится в соответствие некоторое число ci j, называемое весом, или длинной. Тогда граф G называется графом со взвешенными дугами. Иногда веса приписываются вершинам xi графа, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. При рассмотрении пути , представленного последовательностью дуг, за его вес (или длину) принимается число , равное сумме весов всех дуг, входящих в , т.е. .
Гамильтонов цикл в орграфе – это ориентированный цикл (контур), проходящий ровно один раз через каждую вершину графа (т.е. простая орцепь).
Если G = ( X, A ) – неориентированный граф с n вершинами, то остовным деревом ( или, короче, остовом) графа G называется всякий остовный подграф G, являющийся деревом (т.е. графом не имеющим циклов, в котором каждая пара вершин соединена одной и только одной простой цепью). Например, если G – граф, показанный на рис.1а, то графы на рис.1.б,в являются остовом этого графа.
Метод ветвей и границ (МВГ).
Представим, что необходимо обойти все города страны. Так как их много, то определить кратчайший путь затруднительно. Тогда можно выбрать некоторое разбиение множества городов, например, рассматривать республики, области или районы, и определить кратчайший путь, пересекающий каждое из выбранных подмножеств разбиения только один раз. Затем уже в пределах выбранных подмножеств достроить полученный путь до требуемого. Такой подход используется в методе ветвей и границ. Этот метод позволяет опознать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге отсекается целая ветвь. Тем не менее, удовлетворительных оценок быстродействию алгоритма Литтла, основанного на этом методе, и родственных алгоритмов нет, хотя практика показывает, что на современных ЭВМ они иногда позволяют решить задачу коммивояжера для графов с количеством вершин, меньшим 100.
Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.
ПОСТАНОВКА И РЕШЕНИЕ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ.
Пример решения задачи коммивояжера.
Имеем «чисто» математическую задачу, которую решим, используя метод Ветвей и Границ.
В симметричном графе, изображенном на рис.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 . Самарский государственный аэрокосмический университет, Россия.
– Конец работы –
Используемые теги: Автоматизация, инженерно-строительных, технологий0.064
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Автоматизация инженерно-строительных технологий
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов