Исследование операций на примере ОАО "АвиаМоторс"
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
?ртизация оборудования, стоимость ручного и машинного труда, стоимость ресурсов, технологий, инноваций и информации - всё это используется в процессе производства).
Рисунок 4.1 - Граф задания
Таблица 4.1 - Весовые коэффициенты дуг
n1,21,31,42,32,52,62,73,43,53,63,74,54,64,75,65,86,76,87,8120657N30352074920145где n = 12 и N = 3.
Требуется:
. Провести анализ структуры графа. Установить, будет ли неориентированный граф, соответствующий заданному графу, эйлеровым. Разбить граф произвольным образом на два несвязных графа. Путем удаления наименее загруженных дуг:
? избавиться от циклов (если они есть в графе);
? построить дерево графа.
. Составить матрицы смежности (для неориентированного графа) и инциденций (для орграфа).
. Упорядочить нумерацию вершин графа, использую алгоритм Фалкерсона.
. Считая пропускную способность рёбер графа равной заданным коэффициентам, определить максимальную мощность потока, проходящего через граф.
. Считая граф сетевым, определить его показатели:
критический путь;
ранние и поздние сроки свершения событий;
ранние и поздние сроки начала и окончание работ;
резервы свершения событий и выполнения работ.
Решение:
Рисунок 4.2 - Граф задания
. Анализ структуры графа
Граф, представленный на рисунке 4.2 не является эйлеровым, т.к. в нём не существует эйлерова цикла, т.е. данный граф нельзя нарисовать, не отрывая руки от бумаги и не повторяя линий. В этом графе не существует эйлерова цикла, в который бы входили все ребра графа без повторений.
Граф называется связным, если две любые его вершины связаны хотя бы одной цепью. Данный в задании граф - связный. Его необходимо разбить на два несвязных графа произвольным образом. Разобьем граф, изображенный на рис. 4.2, на два несвязных графа путём удаления наиболее загруженных вершин и инцидентных им дуг.
Рисунок 4.3 - Несвязные графы, полученные из графа задания.
Мы разбили граф на два несвязных путём удаления вершин 4, 6 и 7 и инцидентных им дуг.
Далее путём удаления наименее загруженных дуг избавимся от циклов и построим дерево графа.
Цикл - цепь, вершины начала и конца которой совпадают.
Цепь - маршрут, в котором все дуги попарно различны (нет двух узлов, соединённых различными дугами).
В заданном графе присутствует очень много циклов. Избавимся от них путём удаления наименее загруженных дуг.
Рисунок 4.4 - Граф, не имеющий циклов, полученный из графа задания.
Дерево - связный неориентированный граф, не содержащий циклов.
Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственным элементарным путём.
Точка сочленения - вершина графа, удаление которой повышает число компонентов связности. Под удалением вершины понимается удаление самой вершины и всех инцидентных ей дуг. Компонент связности графа - это его связный подграф.
Построим этот граф, опираясь на граф, изображенный на рис. 4.4.
Рисунок 4.5 - Дерево графа
Удаление вершины 5 из графа, представленного на рис. 4.5, превращает связный граф в два его компонента связности.
. Матрицы смежности и инциденций
Матрицей смежности вершин неориентированного графа, состоящего из n вершин, называется матрица А размера nхn, элементы которой определяются следующим образом:
Матрица смежности для неориентированного графа задания.
Но матрица смежности не дает полной информации о связях в ориентированном графе, так как единицы в этой матрице проставляются только в вершинах, из которых дуги исходят, Поэтому для ориентированных графов используют другой вид матриц.
Матрицей инцидентности ориентированного графа с вершинами и дугами (ребрами) называется прямоугольная матрица размера , элементы которой определяются следующим образом:
Таким образом, матрица инцидентности для ориентированного графа задания имеет вид:
. Упорядочение вершин графа. Алгоритм Фалкерсона
Изменение нумераций узлов и дуг графов, ровно, как и их конфигураций, не изменяет природной сущности явлений и процессов, которые графы описывают. В данной работе - процесс производства молочной продукции. Это свойство графов называется изоморфизмом. Решение задач с привлечением графов упрощается, если вершины и дуги графов расположить в определенном порядке.
Считается, что из пары вершин орграфа вершина i является предшествующей, а вершины j - последующей, если существует путь из i в j, а пути из j в i не существует.
Под упорядочением вершин орграфа понимают такую нумерацию его вершин, при которой:
вершины первой группы не имеют предшествующих, а вершины последней группы - последующих;
вершины любой другой группы не имеют предшествующих, а вершины последней группы - последующих;
вершины одних и тех же групп дугами не соединяются.
После упорядочения вершин получается граф, изоморфный исходному.
Упорядочение вершин орграфа можно осуществить, следуя алгоритму Фалкерсона, включающего в себя следующие шаги:
1.Находят вершины графа, в которые не входят дуги. Это первый уровень вершин. После нумерации они вместе с инцидентными им дугами мысленно удаляются из графа.
2.В оставшемся графе, как и в исходном, находят вершины, в которые не входят дуги. Эти вершины в произвольном порядке нумеруются натуральными числами, следующими после номеров вершин первого уровня. Это вер