Применение теории графов при решении некоторых задач на оптимизацию

Содержание

Введение 3

Области применения теории графов

Основные определения, термины и теоремы 4

Методы нахождения гамильтонова цикла в графе 6

Практическое применение задачи коммивояжера 15

Заключение 17

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

ВВЕДЕНИЕ

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

Целью работы является формирование навыка построения гамильтонова цикла.

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

1. ОБЛАСТИ ПРИМЕНЕНИЯ ТЕОРИИ ГРАФОВ

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

• социограммы (в психологии);

• симплексы (в топологии);

• электрические цепи (в физике);

• диаграммы организации (в экономике);

• сети коммуникаций;

• генеалогические деревья.

Впервые задача из теории графов рассмотрена в работах Л. Эйлера («Задача о Кенигсбергских мостах»), Д.Кёниг - первый, кто предложил называть такие схемы "графами" и систематически изучать их свойства.

Перечислим некоторые типовые задачи теории графов и их приложения:

1. Задачи о кратчайшей цепи:

• замена оборудования;

• составления расписания движения транспортных средств;

• размещение пунктов скорой помощи;

• размещение телефонных станций сотовой связи.

1. Задача о максимальном потоке

• анализ пропускной способности коммуникационной сети;

• организация движения;

• оптимальный подбор интенсивностей выполнения работ.

2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ, ТЕРМИНЫ И ТЕОРЕМЫ

1. Граф - пара объектов G = ( X , Г ), где Х - конечное множество, а Г –конечное подмножество прямого произведения Х*Х. При этом Х называется множеством вершин, а Г - множеством дуг графа G.

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

3. Если во множестве Г все пары упорядочены, то такой граф называют ориентированным.

4. Дуга - ребро ориентированного графа.

5. Граф называется вырожденным, если у него нет рёбер.

6. Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной.

7. Подграфом G(V₁, E₁) графа G(V, E) называется граф с множеством вершин V₁ V и множеством ребер (дуг) E_  E, - такими, что каждое ребро (дуга) из E₁ инцидентно (инцидентна) только вершинам из V₁. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

8. Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U.

9. Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

10. Вершины называются смежными, если существует ребро, их соединяющее.

11. Два ребра G₁ и G₂ называются смежными, если существует вершина, инцидентная одновременно G₁ и G₂.

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

13. Доказано, что в 3-мерном пространстве любой граф можно представить в виде укладки таким образом, что линии, соответствующие ребрам (дугам) не будут пересекаться во внутренних точках. Для 2-х мерного пространства это, вообще говоря, неверно. Допускающие представление в виде укладки в 2-мерном пространстве графы называют плоскими (планарными). Другими словами, планарным называется граф, который может быть изображен на плоскости так, что его рёбра не будут пересекаться.

14. Гранью графа, изображенного на некоторой поверхности, называется часть поверхности, ограниченная рёбрами графа.

Данное понятие грани, по существу, совпадает с понятием грани многогранника. В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это можно наглядно представить следующим образом: одну из граней многогранника растягиваем, а сам многогранник «расплющиваем» так, чтобы он весь поместился внутри этой грани. В результате получим плоский граф. Грань, которую мы растягивали «исчезнет», но ей будет соответствовать грань, состоящая из части плоскости, ограничивающей граф.

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

 

1. Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные.

2. Конечная последовательность необязательно различных рёбер E₁,E₂,...E_n называется маршрутом длины n, если существует последовательность V₁, V₂, ... V_n необязательно различных вершин, таких, что E_i = (V_i-1,V_i ).

3. Если начальная и конечная вершины маршрута совпадают, то маршрут замкнутый.

4. Маршрут, в котором все рёбра попарно различны, называется цепью.

5. Замкнутый маршрут, все рёбра которого различны, называется циклом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми.

6. Маршрут, в котором все вершины попарно различны, называется простой цепью.

7. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

1. МЕТОДЫ НАХОЖДЕНИЯ ГАМИЛЬТОНОВА ЦИКЛА В ГРАФЕ

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

Полный перебор (или метод «грубой силы») — метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

Случайный перебор

Обычно выбор решения можно представить последовательностью выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать «рекорд», т. е. наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, т. е. комбинировать случайный поиск с эвристическим методом и методом локального поиска. Такие методы применяются, например, при составлении расписаний для Аэрофлота.

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. При решении задачи коммивояжера жадный алгоритм превратится в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть (рис. 1.1), представляющую узкий ромб. Коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба.

В результате получится не кратчайший, а длиннейший тур.

Рисунок 1.1

Метод минимального остовного дерева (деревянный алгоритм)

В основе алгоритма лежит утверждение: «Если справедливо неравенство треугольника, то для каждой цепи верно, что расстояние от начала до конца цепи меньше (или равно) суммарной длины всех ребер цепи». Это обобщение расхожего убеждения, что прямая короче кривой.

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

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

Метод генетических алгоритмов

«Отцом-основателем» генетических алгоритмов считается Джон Холланд, книга которого «Адаптация в естественных и искусственных системах» (1975) является основополагающим трудом в этой области исследований.

Генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

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

Метод ветвей и границ предложен в 1963 году группой авторов Дж. Литлом, К. Мурти, Д. Суини, К. Кэролом. Широко используемый вариант поиска с возвращением, фактически является лишь специальным частным случаем метода поиска с ограничениями. Ограничения в данном случае основываются на предположении, что на множестве возможных и частичных решений задана некоторая функция цены, и что нужно найти оптимальное решение, т.е. решение с наименьшей ценой. Для применения метода ветвей и границ функция цены должна обладать тем свойством, что цена любого частичного решения не превышает цены любого расширения этого частичного решения. (Заметим, что в большинстве случаев функция цены неотрицательна и даже удовлетворяет более сильному требованию).

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

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

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

Пусть Z(n) – множество всех гамильтоновых контуров , отвечающих матрице порядка n x n. Зафиксируем некоторую дугу (x_i,x_j) и разобьем множество Z(n) на два непересекающихся подмножества. Z₁⁽¹⁾(n-1) всех контуров, содержащих дугу (x_i,x_j) и Z₂⁽¹⁾(n-1) состоящее из контуров не содержащих дугу (x_i,x_j). Тогда получаем две задачи для этих подмножеств, которые с меньшим числом сравниваемых контуров. Для множества Z₁⁽¹⁾(n-1) соответствующая матрица расстояний А₁ получается из А зачеркиванием i–й строки и j-го столбца, дуга (x_i,x_j) исключается, этот процесс называется стягиванием дуги (x_i,x_j). Продолжаем процесс ветвления Z₁⁽¹⁾(n-1) и Z₂⁽¹⁾(n-1) пока не придем к подмножествам состоящим из одного гамильтонова контура, причем длина этого контура меньше или равна нижних границ всех ранее построенных подмножеств. Операция приведения над матрицей А состоит в следующем:

1. Из каждого элемента каждой строки вычитают минимальный элемент этой же строки (приведение по строкам).

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

Полученную в результате матрицу обозначим B и назовем приведенной.

B содержит в любой строке и столбце по крайней мере по одному нулевому элементу b_lm =0. Обозначим D = {(l,m) / b_lm =0}.

Очевидно, что длина оптимального контура ₀(B) связана с длиной оптимального контура ₀(А) в исходной матрице А соотношением ₀(А)= ₀(B) + (), где _к , к (1 ; n) минимальный элемент k-й строки А, _l, l (1 ; n) минимальный элемент l-го столбца матрицы А после приведения по строкам.

Величина = h – константа приведения.

Выбор дуги осуществляется так, чтобы величина а_lm, выражающая увеличение длины контура при невключении в него дуги (l,m), была бы максимальной по всем дугам (l, m), для которых в приведенной матрице B, b_lm = 0, т.е.

если , то выбирается дуга (i, j) и b_ml заменяем на бесконечность.

Алгоритм метода ветвей и границ.

А) Цикл.

1. Приведение матрицы А.

2. Получение границы множества Z(n): (z(n)) = h

3. Выбор дуги ветвления.

4. Оценка нижней границы множества Z₂: (z₂⁽ⁱ⁾) = h_i + a^/_ij . Оценка границы множества Z₁: (z₁⁽ⁱ⁾) = h_i-1 + h_i

5. Стягивание матрицы по дуге ветвления.

Процесс повторяем до тех пор, пока множество Z_i не будет содержать только один контур ₁

Б) Ветвление множества Z₂^(k), если (z₂^(k))(₁), тогда получаем контуры ₂, ₃,… _m, сравниваем их длины между собой и выбираем оптимальный контур.

Модифицированный метод ветвей и границ задачи о коммивояжере.

Пусть дана матрица расстояний С=(с_ij) порядка n. Обозначим через Ω множество всех маршрутов, при которых коммивояжёр, выезжая из города А₁, побывает во всех остальных городах по одному разу и вернется в А₁. Пусть Ω_{1,i1,i2,i3,…ik} 2≤k≤n-1 – подмножество множества Ω, состоящее из всех маршрутов, при которых коммивояжер, выезжая из А₁, последовательно посещает города A_i1,…ik.

Множество Ω можно разбить на непересекающиеся подмножества Ω_1,2 Ω_1,3 Ω_1,n. Вычисляем оценки каждого этого подмножества, выбираем наименьшую. Например, подмножество Ω_1,2 разбиваем на подмножества Ω_1,2,3 Ω_1,2,4 Ω_1,2,n и т.д. Множество Ω_{1,i1,i2,i3,…ik} при k=n-1 состоит из единственного маршрута и с помощью него ветвление не выполняется.

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

Решение. Применим модифицированный метод ветвей и границ задачи о коммивояжере

Практическое применение задачи коммивояжера

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

Кроме очевидного применения задачи коммивояжера на практике, существует ещё ряд задач, сводимых к решению задачи коммивояжера.

Задача о производстве красок. Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним процессором. Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке. Поскольку производство циклическое, то краски надо производить в циклическом порядке =(j₁,j₂,..,j_n,j₁). После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого требуется время C[i,j]. Очевидно, что C[i,j] зависит как от i, так и от j, и что, вообще говоря,C[i,j]≠C[j,i]. При некотором выбранном порядке придется на цикл производства красок потратить время

Где t_k - чистое время производства k-ой краски (не считая переналадок). Однако, вторая сумма в правой части постоянна, поэтому полное время на цикл производства минимизируется вместе с общим временем на переналадку.

Таким образом, задача о коммивояжёре и задача о минимизации времени переналадки – это просто одна задача, только варианты ее описаны разными словами.

Задача о дыропробивном прессе. Дыропробивной пресс производит большое число одинаковых панелей – металлических листов, в которых последовательно по одному пробиваются отверстия разной формы и величины. Схематически пресс можно представить в виде стола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, по периметру которого расположены дыропробивные инструменты разной формы и величины. Каждый инструмент присутствует в одном экземпляре. Диск может вращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает на подвешенный под него инструмент тогда, когда под инструмент подведена нужная точка листа.

Операция пробивки j-ого отверстия характеризуется четверкой чисел (x_j,y_j,z_j,t_j), где x_j,y_j- координаты нужного положения стола, z_j - координата нужного положения диска и t_j - время пробивки j-того отверстия.

Производство панелей носит циклический характер: в начале и конце обработки каждого листа стол должен находиться в положениях (x₀, y₀) диск в положении z₀ причем в этом положении отверстие не пробивается. Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами (x₀,y₀,z₀,0). Чтобы пробить j-тое отверстие непосредственно после i-того необходимо произвести следующие действия:

1. Переместить стол по оси x из положения x_i в положение x_j, затрачивая при этом время t^(x)(|x_i-x_j|)=t_i,j^(x).

1. Проделать то же самое по оси y, затратив время t_i,j^(y) .

2. Повернуть головку по кратчайшей из двух дуг из положения z_i в положение z_j, затратив время t_i,j^(z) .

3. Пробить j-тое отверстие, затратив время t_j.

Конкретный вид функций t^(x), t^(y), t^(z) зависит от механических свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости.

Действия 1-3 (переналадка с i-ого отверстия на j-ое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий, поэтому С[i,j] = max(t^(x), t^(y), t^(z)).

Теперь, как и в предыдущем случае, задача составления оптимальной программы для дыропробивного пресса сводится к ЗК (здесь - симметричной).

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ЛИТЕРАТУРЫ, РЕКОМЕНДУЕМОЙ ДЛЯ ИЗУЧЕНИЯ

1. Акимов О.Е. Дискретная математика: логика, группы, графы. – М. Лаборатория базовых знаний, 2001.

2. Гаврилов С.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1978.

3. Зубков А.М., Севастьянов Б.А., Чистяков В.П. Сборник задач по теории вероятностей. - М.: Наука, 1989.

4. Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям куpса «Дискpетная математика». - М.: МГТУ, 1995.

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

6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.

7. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.

8. Лекции по теории графов / Емеличев В.А., Мельников О.И. и др. - М.: Наука, 1990.

9. Липский В. Комбинаторика для программистов. - М.: Мир, 1988 .

10. Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981.

11. Hефедов В.H., Осипова В.А. Куpс дискpетной математики. - М.: МАИ, 1992.

12. Hечепуpенко М.И. Алгоритмы и пpогpаммы pешения задач на гpафах и сетях. - Hовосибиpск: Hаука, 1990.

13. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2001.

14. Оре О. Теория графов. – М.: Наука, 1980.

15. Романовский И.В. Алгоpитмы pешения экстpемальных задач. - М.: Hаука, 1977.

19