Тема 5 Задачи сетевого планирования и управления.

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг/

Графами были названы схемы, состоящие из точек (вершины графа) и соединяющих эти точки отрезков прямых или кривых (ребра графа)

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

С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети.

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

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

Граф- это фигура, состоящая из точек и соединяющих данные точки линий. Граф - пара множеств V и X G = (V,X)

Точки называются вершинами графа. V - множество вершин

Линии, соединяющие точки, называются ребрами графа. X – множество ребер

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

v₁x₁v₂x₂v₃...x_kv_k+1.

Цепь - незамкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

Cтепень вершины - количество ребер графа, исходящих из вершины.

Четные вершины- это вершины, в которых сходится четное число ребер.

Нечетные вершины- это вершины, в которых сходится нечетное число ребер.

Если степень вершины равна 1, то эта вершина висячая

Если степень вершины равна 0, то эта вершина изолированная

Полустепенью исхода (захода) вершины v орграфа D называется d ^- (v) - число

дуг, исходящих из v (d⁺ (v) - число дуг, заходящих в v).

Эйлеровый граф – это граф, у которого все вершины четны.

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

Цепь-это маршрут, в котором каждое ребро графа встречается только один раз.

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

Цикл- это цепь, начальная и конечная вершины которой совпадают.

Цикл (контур) - замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

Эйлеровый цикл- это цикл, в котором каждое ребро участвует только один раз.

Гамильтонов цикл- это цикл, в котором каждая вершина участвует только один раз.

Простая цепь - цепь, в которой все вершины попарно различны

Простой цикл (контур) - цикл (контур), в котором все вершины попарно различны.

Петля - ребро вида (v,v).

Кратные рёбра - одинаковые пары в X.

• Ориентированный граф (орграф D) - граф, для которого пары в X упорядочены. Ребра в орграфе называются дугами и обозначаются (vi, vj).

Петля - ребро вида (v,v).

Кратные рёбра - одинаковые пары в X.

• Ориентированный граф (орграф D) - граф, для которого пары в X упорядочены. Ребра в орграфе называются дугами и обозначаются (vi, vj).

Граф называется нагруженным, если каждой дуге (i, j) поставлено в соответствие число l(i, j), называемое длиной дуги.

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

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

Сетевое планирование и управление включает три основных этапа:

Дата добавления: 2017-02-01