Иерархические графы деревья определение

29. Иерархические графы и их разновидности (дерево целей, организационная структура, дерево решений, причинно-следственная диаграмма и т.Д.)

«ДЕРЕВО ЦЕЛЕЙ» — развернутая, распределенная по уровням совокупность целей и задач, построенная по логической схеме: «цели программы — задачи, которые надо решить для достижения этих целей, — мероприятия, обеспечивающие решение задач, — ресурсы, необходимые для проведения мероприятий».

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

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

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

Общие принципы построения организационных структур управления проектами:

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

Дерево принятия решений — это дерево, на ребрах которого записаны атрибуты, от которых зависит целевая функция, в листьях записаны значения целевой функции, а в остальных узлах — атрибуты, по которым различаются случаи. Ситуация, в которой стоит применять деревья принятия решений, обычно выглядит так: есть много случаев, каждый из которых описывается некоторым конечным набором дискретных атрибутов, и в каждом из случаев дано значение некоторой (неизвестной) булевой функции, зависящей от этих атрибутов. Задача — создать достаточно экономичную конструкцию, которая бы описывала эту функцию и позволяла классифицировать новые, поступающие извне данные. Располагаются «деревья» слева направо. «Ветви» обозначают возможные альтернативные решения, которые могут быть приняты, и возможные исходы, возникающие в результате этих решений. На схеме мы используем два вида «ветвей»:

первый — пунктирные линии, соединяющие квадраты возможных решений,

второй — сплошные линии, соединяющие кружки возможных исходов.

Квадратные «узлы» обозначают места, где принимается решение,

круглые «узлы» — появление исходов.

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

Когда все решения и их исходы указаны на «дереве», просчитывается каждый из вариантов, и в конце проставляется его денежный доход. Все расходы, вызванные решением, проставляются на соответствующей «ветви».

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

В основу первых диаграмм был положен принцип «4М», т.е. основных факторов, от которых зависит качество:

· Мen – люди;· Machine – оборудование;· Method – методы и технология;· Material – сырье

Позже к «4M» добавились еще два: Measure – средства измерения и контроля и Milieu – среда, рабочее окружение. И сегодня при составлении диаграммы К.Исикавы обычно сразу строят 4-6 главных стрелок, последовательно добавляя к ним дополнительные факторы методом мозгового штурма.

Стрелки, обозначающие факторы, действительно отдаленно напоминают кости в рыбьем скелете. Стрелки, которые сразу рисуют на новой диаграмме (из числа 4 или 6 «М»), называют «большими костями», стрелки, которые направлены на них – «средними костями». Стрелки, направленные на «средние кости» называют «малыми костями». Таким образом, можно углубиться в причины на 3 уровня и дальше. Существует принципиальная возможность добавлять стрелки и к «малым костям», но в этом случае диаграмма теряет удобство в использовании.

Методика построения диаграмм К.Исикавы включает следующие шаги.

1. Формирование рабочей группы. Построение диаграммы Исикавы дает важное преимущество: с ней будут согласны все участники этой группы. Рекомендуется, чтобы в группу вошли все сотрудники, от которых будет зависеть дальнейшая работа по данному направлению, хотя идеальное количество участников обсуждения – 5-9 человек. Общее время на построение диаграммы Исикавы желательно сделать ограниченным, например, 20 минут.

2. Выбор показателя качества и написание его названия в прямоугольнике справа на чистом листе бумаги. Затем к прямоугольнику проводится прямая горизонтальная линия – «хребет» диаграммы, к которому пририсовываются «большие кости», обычно по принципу «4М» или «6М». Соответственно, мы добавляем в диаграмму названия факторов по принципу «4М» и соединяем их стрелками с «хребтом».

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

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

30. Сетевое планирование и управление (СПУ). Основные понятия и определения СПУ: сетевая модель, работа, событие, путь. Виды сетевых моделей, работ, событий и путей. Правила построения сетевых моделей. Критический путь. Подкритический путь.

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

Работа – процесс, в результате которого наступает какое-либо событие.

— действительная работа – трудовой процесс, требующий затрат времени, трудовых и материальных ресурсов.

— работа ожидания – процесс, не требующий затрат ресурсов, но отнимающий время.

— фиктивная работа – логическая связь между событиями, не требующая затрат времени и ресурсов, но показывающая зависимость одного события от другого.

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

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

Критический путь – от начального до конечного события, имееющий большую продолжительность.

Подкритический путь – полный путь, ближайший по длительности к критическому пути.

Путь бывает полный(от исходного события до завершающего) и неполный.

Правила построения сетевых моделей:

1. В сетевом графике должно быть одно начальное и конечное события.

2. Каждая работа должна иметь уникальный номер

3. Не должно быть замкнутых контуров.

Источник

1.3 Графическое представление иерархической структуры системы

1.3.1 Графы и деревья. Основные понятия, формализация информации в виде матриц смежности и инцидентности.

Материальная система, которая состоит из двух множеств: точек (вершин, узлов, блоков, мест) и линий (связей, рёбер), которые находятся между собой в каком-либо отношении называется графом. Множество точек соответствует множеству вершин

Множество линий, соединяющих пары вершин, называется множеством ребер или дуг

Граф, содержащий только ориентированные линии, называется ориентированным графом или орграфом. Граф, содержащий только неориентированные линии, называется неориентированным графом. Граф, у которого существует хотя бы одна пара вершин, соединяемых m ребрами (m >= 2), называется мультиграфом, а наибольшее число m называется мультичислом графа.

Ребра, соединяющие одну и ту же пару вершин, называются кратными. Ребро, соединяющее две вершины называется инцидентным, а вершины инцидентны ребру. Смежными называют две вершины, если есть соединяющее их ребро; два ребра инцидентны одной вершине.

Конечный граф – граф, включающий конечное множество узлов и связей (X и U). Нулевой граф – граф, в котором вершины не соединены ребрами, при этом множество U пустое U = <>. Полный граф — граф, в котором каждая пара вершин соединена ребром.

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

Квадратная матрица R[n, n] называется матрицей смежности, если ее столбцы и строки образованы вершинами графа (i = 1, … i = n; j = 1, … j = n), а значения в ячейках таблицы R[i, j] показывают наличие связей между вершинами. Если R[i, j] = 1 то X_i смежно с X_j а если вершины не соединены R[i, j] = 0. Если граф неориентированный то R[i, j] =R[j, i].

Прямоугольная матрица S[n, m] называется матрицей инцидентности, если ее строки образованы вершинами графа (i = 1, … i = n), а столбцы — связями (j = 1, … j = m) или наоборот. Элементы в ячейках образуются по правилу S_ij = 1, если связь (ребро) U_j выходит из X_i ; S_ij = — 1, если связь U_j входит в X_i.. Если ребро U_j не связано с вершиной X_i , то S_ij = 0.

1.3.2 Особенности выделения уровней иерархии

Для описания иерархической структуры конкретных систем (изделий) обычно применяются И – деревья. Эти деревья представляют собой совокупность вершин и связывающих их ребер, сгруппированных на различных иерархических уровнях (ярусах). Каждый иерархический уровень представляет собой проектируемую систему с различной степенью детализации. Нулевой иерархический уровень (система) является наиболее абстрактным, а последний – наиболее детализированным.

Количество уровней декомпозиции должно соответствовать поставленной задаче. Минимальная неделимая часть в рамках задачи называется элементом. Дерево не всегда отражает чисто конструктивную декомпозицию объекта.

Применение иерархической декомпозиции помогает формировать словарь предметной области, в которой существует рассматриваемая система, и позволяет выделить базовые понятия (абстракции) предметной области, которые необходимы при ее анализе, в том числе и при создании САПР [3]. Кроме того, на каждом уровне абстракции применяются свои принципы и методики описания системы, соответствующие степени ее декомпозиции.

Таким образом, разбиение объекта находится в рамках блочно — иерархического подхода к структурному описанию объектов. Вершины отображают составные части проектируемого объекта. Рёбра отражают всевозможные связи между вершинами (механические, тепловые, электрические). При создании программных продуктов указывают, например, потоки данных между блоками, модулями. Вершины (элементы) самого нижнего яруса (иерархического уровня) в рамках принятого представления сложной системы – (например автомобиля) называются базовыми элементами или листьями. Таким образом И – дерево является представлением конкретной системы, в котором элементы объединены связями в узлах И, в соответствии с иерархической декомпозицией системы (рис. 8). Поскольку все узлы одинаковы (имеют тип И), их иногда на рисунках не показывают.

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

Источник