Оптимизация на графах Студент Гр. Пи-08 Пушной А.Б. КУРСОВАЯ РАБОТА

Введение Большинство возникающих задач удобно представлять для восприятия и анализа в виде сетей, которые позволяют ответить на два главных вопроса: до какого места необходимо дойти (цель) и какой путь следует избрать (как). Наглядность и логическая обоснованность методов сетевого анализа позволяет выбрать довольно естественный подход к решению задач. Сетевые модели для людей, не занимающихся научной работой, являются более понятными, чем другие модели, поскольку для них все же лучше один раз увидеть, чем сто раз услышать. В значительной степени методы сетевого анализа основаны на теории графов – области математики, началом развития которой явилась задача о кенигсбергских мостах, сформулированная швейцарским ученым Л. Эйлером в 1736 г. Через реку Прегель, на которой стоял город Кенигсберг, построено семь мостов, которые связывали с берегами и друг с другом два острова. Задача заключалась в том, чтобы пройти по всем мостам только один раз и вернуться обратно к началу маршрута. Эйлер доказал неразрешимость этой задачи. Позже Д.К. Максвелл и Г.Р. Кирхгоф на основе исследования электрических цепей сформулировали некоторые принципы сетевого анализа. Были разработаны методы расчета наибольшей пропускной способности телефонных линий. В 40-х годах в результате развития теории исследования операций был разработан ряд математических методов, необходимых для анализа больших систем. В 50–60-х годах проводились работы по построению новых сетевых моделей и разработке алгоритмов их решения на основе элементов теории графов.

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

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

Последовательные работы и события формируют цепочки ( пути ), которые ведут от исходного события сетевого графика к завершающему. Например, путь сетевого графика, показанного на рисунке 1, включает в себя события 0,1,2,3,4,5,6,7 и работы (0-1), (1-2), (2-5), (5-6), (6-7). Построенный таким образом сетевой график в терминах теории графов представляет собой направленный граф. Сетевой график есть ориентированный связный асимметрический граф с одним истоком, одним стоком и без циклов, то есть это направленный граф. При этом вершинами графа служат события сетевого графика, а дугами ( ребрами ) работы сетевого графика. Продолжительность работы представляет собой, в терминах теории графов, длину дуги. Следовательно, длина пути T это сумма длин всех дуг, образующих данный путь, то есть, где символом обозначается дуга, которая соединяет вершины i и j и направлена от вершины i к вершине j. Рисунок 1 – Пример сетевого графика

Алгоритм Беллмана Р. Беллман предложил вычислять кратчайшие пути по шагам. Матрица кратчайших переходов за два шага вычисляется следующим образом. Для любых городов i и j, чтобы вычислить кратчайший переход за 2 шага рассматривают все переходы из i в j через все промежуточные вершины. Очевидно, что минимальный из таких переходов ( а прямой переход тоже учитывается ) и будет кратчайшим переходом из i в j за два шага и менее ( менее, если не было пересчета, когда прямой переход короче всех остальных ). Вновь полученная таким образом матрица и будет матрицей кратчайших переходов за два шага ( и менее ). Используя ее и матрицу кратчайших переходов за один шаг можно получить матрицу кратчайших переходов за 3 шага ( и менее ). Введем следующие обозначения - матрица кратчайших переходов за a шагов. Легко доказать следующую рекуррентную формулу Беллмана :

Алгоритм Флойда

Эйлеровы и Гамильтоновы пути, циклы и контуры Интересные задачи связаны с построением полных обходов графа. В термин «полный обход» можно вкладывать различное содержание. Более простой из них является задача построения обхода, содержащего все дуги графа. Для примера сначала рассмотрим задачу о Кенигсбергских мостах. В городе Кенигсберге в 18 веке была схема мостов приведенная на рис. A,B,C и D - различные районы города. Районы B и D расположены на островах. Задача ставится так: выйдя из дома в одном из районов города обойти все мосты, пройдя по каждому только один раз, и вернуться домой. Очевидно, задача имеет эквивалентную постановку в терминах теории графов.

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

Заключение Использование оптимизации дает возможность увязать во вре ­ мени программу производства работ, планировать последовательность их выполнения, выявлять и устранять возникающие в процессе реализации нарушения. Позволяет : определить, от каких операций и в какой степени зависит срок выполнения всей программы ; предвидеть появление " узких мест "; выделить второстепенные, с точки зрения времени реализации программы, работы, сокращение продолжительности которых не только не приведет к уменьшению времени выполнения всей совокупности операций, но и может привести к увеличению стоимости работ и простоев рабочих и оборудования. Кроме того, оптимизация позволяет дать обоснованные, в том числе и с экономической точки зрения, ответы на вопросы организации выполнения работ программы.