Лекция. Тема Применяемость в задачах управления машиностроительным предприятием
 Скачать 177.66 Kb.
|
|
1 2 3 4 5 6 7 8 9 10 11 12 13 Тема 2. Применяемость в задачах управления машиностроительным предприятием. 2.1. Матричные методы упорядочения операций проекта Структура проекта может быть представлена матрицей смежности. Элемент матрицы смежности, стоящий на пересечении i-й строки и j-ro столбца, равен единице, если из вершины i в вершину j идет дуга и равен нулю в противном случае. Единичные элементы i-й строки матрицы смежности определяет ближайших потомков вершины i, а единичные элементы j-ro столбца - ближайших предков вершины j. Пример такого представления изображен на рис.3. Рис. 3.1 Рис. 3.2. Рис.3. Представление исходного орграфа 3.1. – графически 3.2. – матрицей смежности 1 2 3 4 5 6 7 8 9 10 11 12 13 1 1 1 2 1 1 1 3 1 4 1 5 1 6 M 7 1 8 1 9 10 11 1 12 1 1 1 13 1 1 3 Упорядочение сети является первоочередным условием для ее последующего анализа. Если топологическая схема сетевого графа не удовлетворяет условию разбиения его вершин на систему непересекающихся классов (слоев), то это свидетельствует о наличии контуров, образовавшихся при неправильном задании взаимосвязей между операциями комплекса. Процедуру разбиения орграфа на слои состоит в следующем: 1) каждая вершина графа принадлежит только одному слою; 2) вершины первого слоя не имеют предков, а вершины последнего - потомков; 3) все вершины данного слоя не имеют предков, в следующих слоях; 4) вершины одного слоя неупорядочены, т.е. между ними отсутствует взаимосвязь. Известно, что отсутствие в графе контуров является необходимым и достаточным условием для его последующего упорядочения. Рассмотрим метод, позволяющий достаточно Простым способом определить слои исследуемого графа. Чтобы не вводить дополнительные обозначения, будем считать, что вершины орграфа пронумерованы в соответствии с натуральным рядом чисел (сквозная нумерация вершин). В этом случае обозначение вершины Х г совпадает с ее индексом L Очевидно, что эти понятия изоморфны. Из определения матрицы смежности следует, что ее столбцы, образованные одними нулевыми элементами, определяют вершины первого слоя. В нашем примере 11, 12 и 13 вершины не имеют предков. Исключение выделенных элементов из дальнейшего рассмотрения на всех последующих этапах разбиения достигается аннулированием их взаимосвязей с другими вершинами графа. Эта операция эквивалентна обращению в нуль элементов матрицы, расположенных в строках с 4 номерами выделенных столбцов. После проведения указанных преобразований соответствующие вершины графа становятся изолированными (отделенными). В преобразованной матрице М 2 вновь образовавшиеся столбцы из нулевых элементов образуют второй слой разбиения (вершины 1, 2 и 3). Отделив вершины второго слоя, получим матрицу М 3 . Продолжая описанный процесс нужное число раз, выделяя при этом вновь образовавшиеся нулевые столбцы матрицы, мы последовательно выделим слои исследуемого орграфа. При этом в вершины первого слоя не входят дуги, в вершины второго слоя входят дуги только из первого слоя, в вершины третьего слоя входят дуги из первого и второго слоев и т.д. 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 1 1 1 2 1 1 1 2 3 1 3 4 1 4 1 5 1 5 1 6 6 M 2 7 1 М 3 7 1 8 1 8 1 9 9 10 10 11 11 12 12 13 13 5 После отделения вершин последнего слоя преобразованная матрица смежности состоит из одних нулевых элементов. В нашем примере матрица М 3 определяет четвертую, пятую, шестую, седьмую и восьмую вершины третьего слоя, а матрица М 4 - девятую и десятую четвертого. Упорядоченный по слоям исследуемый орграф изображен на рис.4.1. В общем случае полученное разбиение не является единственным. Проведя указанные вычисления для транспонированной матрицы к матрице Mi , получим слои орграфа, начиная с последнего. В данном преобразовании каждая итерация исключает вершины, не имеющие потомков. Это разбиение представлено на рис.4.2. Примечание.Чтобы отличить вершины данного слоя от своих предшественников, можно воспользоваться репрезентативной матрицей смежности, которая получается добавлением единиц по главной диагонали к матрице смежности. Тогда отделяемую вершину определяет столбец, содержащий единственный единичный элемент. После изолирования выделенной вершины определяющий столбец целиком состоит из нулевых элементов. Если на очередном шаге разбиения не удается выделить вершины данного слоя и матрица смежности содержит единичные элементы, то это означает, что исследуемый орграф содержит контур. 6 Пользуясь результатами разбиения графа без контуров на слои, легко убедиться, что ненулевые элементы его матрицы смежности после введения определенной нумерации вершин графа могут быть размещены по одну сторону от главной диагонали. Например, матрицу можно привести к треугольному виду, если последовательно рассматривать слои орграфа в порядке их определения, присваивая при этом элементам каждого слоя номера из натурального ряда чисел. Порядок присвоения номеров элементам одного слоя может быть произвольным, так как между его вершинами отсутствует взаимосвязь. Сформулированное нами правило триангуляции матрицы смежности справедливо как для разбиения, при котором первый выделенный слой содержит элементы, не имеющие предков, так и для разбиения, начинающегося с определения вершин, не имеющих потомков. В первом случае все ненулевые элементы матрицы находятся над главной диагональю, во втором - под ней. Для доказательства этого утверждения отметим такой факт, что для каждого элемента m ц триангулированной матрицы смежности М, расположенного над главной ее диагональю, выполняться условие i < j, а под диагональю - условие i > j. Следуя правилу нумерации вершин графа и принимая во внимание требования к определению его слоев, можно сделать вывод о том, что в 11 3 12 7 5 8 4 13 1 9 6 10 2 11 3 7 5 8 4 13 1 9 6 10 2 12 Рис 4.1. Рис 4.2. Рис 4. Упорядоченные по слоям вершины орграфа 4.1. - упорядочение, начиная с вершин первого слоя 4.2. - упорядочение, начиная с вершин последнего сдоя 7 зависимости от способа разбиения каждой вершине будет присвоен меньший номер, чем ее "потомку" ("предку"). Таким образом, применяемая сквозная нумерация вершин графа позволяет триангулировать его матрицу смежности, так как при первом способе разбиения для всех ненулевых элементов матрицы выполняется условие i < j, а при втором способе - условие i > j. Верхняя оценка количества связей в орграфе без контуров есть (n 2 -n)/2, где n - число вершин орграфа. Учитывая, что между вершинами одного слоя отсутствует взаимосвязь, данная оценка сильно завышена. Например, для большинства средних и крупных проектов, количество взаимосвязей менее чем вдвое превышает число операций. Во многих прикладных задачах "нагруженные" орграфы без контуров могут содержать несколько тысяч вершин. Например, это проявляется в задачах разузлования, расчета применяемости, расчета производственных программ, в планировании и управлении объектами новой техники и т.д. Поэтому автоматизация рассмотренных нами методов упорядочения потребовала бы значительного места для размещения матрицы смежности исходного графа. Кроме того, наличие параллельных нагруженных дуг, характеризующих длительности, стоимости, применяемости и другие ресурсные и финансовые характеристики, не позволяет использовать квадратные матрицы для идентификации нагруженной дуги. Учитывая, что эта матрица является слабозаполненной, воспользуемся алгоритмами, использующими компактное представление структуры орграфа. 2.3. Контроль сетевых структур Практическое использование систем сетевого планирования и управления предполагает наличие эффективных методов контроля состава, взаимосвязей и параметров операций моделируемых объектов. Чтобы обнаружить возможные ошибки на стадиях создания и обновления сетевой модели проекта, необходимо проверить данные исходного планового документа на соответствие некоторым обязательным требованиям. Этот 8 исходный документ содержит: перечень работ, их характеристики, подсписки непосредственно предшествующих работ каждой операции проекта. В зависимости от постановки задачи планирования оценка временных, ресурсных или стоимостных характеристик операций производится на основе накопленного статистического материала о ранее выполненных работах, а также, исходя из опыта экспертов и участников разработки. В списковом представлении структуры исходного сетевого графа "работы-вершины" с помощью формализованных правил могут быть обнаружены следующие ошибки: 1) перечень операций комплекса содержит одинаковые элементы; 2) подсписок непосредственно предшествующих операций содержит одинаковые элементы; 3) подсписки предков содержат элементы, отсутствующие в перечне операций проекта; 4) подсписок некоторой операции содержит ее обозначение; 5) наличие контуров в исходной сети. При обнаружении в исходной сети перечисленных типов ошибок необходимо устранить их путем пересмотра состава и взаимосвязей операций проекта. Сеть, получившаяся в результате коррекции, должна быть проконтролирована еще раз. Формализованные правила обнаружения ошибок, перечисленных в первых четырех пунктах, достаточно просты и здесь рассматриваться не будут. Присутствие контуров в сети означает, что результаты некоторых работ предшествуют своему выполнению. Автоматизировать процесс построения сети типа "работы-дуги" невозможно до тех пор, пока не удастся устранить все контуры в исходном графе. Их отсутствие является необходимым и достаточным условием для его последующего упорядочения. 9 Если на очередном шаге разбиения не удается определить вершины, не имеющие предков, и преобразованная матрица смежности содержит ненулевые компоненты, то исходный граф содержит контуры. В этом случае, повторяя описанный выше процесс для строк этой матрицы, отыщем (пока это возможно) вершины исходного орграфа, принадлежащие слоям, начиная с последнего. При этом выделенные ранее вершины из дальнейшего рассмотрения исключаются, а отделение вершин, не имеющих потомков, обеспечивается приравниванием нулю элементов одноименных столбцов. Ненулевые компоненты преобразованной матрицы определяют подграф, образованный контурами исходного графа, а также вершинами (путями или дугами) их соединяющими. В выделенном подграфе поиск одного контура производится по следующей схеме: 1) фиксируем произвольную вершину Х 0 ; 2) так как каждая вершина имеет предков и потомков, то определяем для Х 0 , например, любую непосредственно следующую вершину X 1 , и записываем ее обозначение после Х 0 ; 3) продолжаем выписывать элементы последовательности непосредственно следующих вершин Х0, X1,..., Xi ;Xk-1, Xk, пока не повторится одно из выписанных ранее обозначений; 4) если обозначения вершин Xi и Хк совпадают, то найденный контур определяет путь (Xj, Xi+1 ,...,Xk-1 ,Xk). Из вышеизложенного следует, что в графе, все N вершин которого имеют предков и потомков, любой контур содержит не более N связей. Первый и второй алгоритмы упорядочения могут быть использованы при обнаружении контуров в списковом представлении проекта. Как было отмечено выше, алгоритмы используют различные способы задания структуры проекта. При наличии контуров последовательное применение списковых алгоритмов к заданной определенным образом структуре комплекса эквивалентно использованию матричных алгоритмов 10 упорядочения к матрице смежности вершин ориентированного графа и к матрице, к ней транспонированной. После устранения одного контура рассмотренную процедуру контроля следует повторить до полного исключения всех контуров в исходном сетевом графе. Рассмотрим работу алгоритма на конкретном примере. На рис.10 представлен сетевой граф и его матрица смежности. 11-я, 12-я и 13-я вершины образуют первый слой разбиения. 1 2 3 4 5 6 7 8 9 10 11 12 13 1 1 1 2 1 1 1 3 1 4 1 5 1 6 M1 7 1 8 1 9 1 11 10 1 11 1 12 1 1 1 13 1 1 Рис. 10. После их изолирования получим матрицу М2, 3-й столбец которой определяют одноименную компоненты 2-го слоя. Приравняем нулю элементы 3-ей строки матрицы М2. Получим матрицу М3, определяющую 3- й слой исходного графа, состоящего из 8-й вершины. 12 После ее отделения в матрице М4 нельзя выделить вершины, не имеющие предков, что указывает на наличие контуров в исходном орграфе. Рассмотрим строки матрицы М4. Шестая вершина графа не имеет потомков. Ее отделения обеспечивается приравниванием нулю элементов 6- го столбца матрицы. В матрице М5 нельзя выделить вершины, не имеющих потомков. Ненулевые элементы матрицы определяют подграф, все вершины которого имеют предков и потомков. Графическое представление данного подграфа изображено на рисунке 11. 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 1 1 1 1 1 1 2 1 1 1 2 1 1 1 3 1 3 4 1 4 1 13 5 1 5 1 6 6 M2 7 1 М3 7 1 8 1 8 1 9 1 9 1 10 1 10 1 11 11 12 12 13 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 1 1 2 1 1 1 3 4 1 5 1 6 M4 7 1 8 9 1 10 1 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 15 1 1 2 1 1 3 4 1 5 1 6 M5 7 1 8 9 1 10 1 11 12 13 16 Рис. 11. Для выделения контура выберем, например, вершину 1. Эта вершина предшествует вершине 4, являющейся, в свою очередь, предком вершины 9. Потомок вершины 9 определяет искомый контур (1, 4, 9, 1). После его устранения, например, посредством удаления в матрице М5 связи (4, 9), процесс отделения вершин, не имеющих предков (потомков), должен быть продолжен. В нашем примере в обновленной матрице М5 нельзя выделить вершины, не имеющие предков. Анализ ее строк позволяет определить 4-ю вершину, не имеющую потомков. Последовательное изолирование 4-й, 1-й, 9-й и 5-й вершин определяет подграф, образованный контуром (2, 7,10, 2). Таким образом, исследуемый исходный граф содержит два контура и связывающую их вершину 5. Алгоритм преобразования сетевого графа "работы-вершины" в сетевую модель "работы-дуги" исключает в искомой сети ошибки, для указания которых можно указать формальные правила их обнаружения, при условии, что исходный сетевой граф предварительно проконтролирован. 17 При задании графа "работы-вершины" для каждой работы комплекса следует указать операции, непосредственно за ней следующие. Поэтому в каноническом представлении модели "работы-дуги" все события, за исключением исходного и завершающего, имеют как входящие так и выходящие дуги. Из начального события выходят исходные работы комплекса, не имеющие предков. В конечное событие входят завершающие операции проекта, у которых отсутствуют непосредственно следующие работы. Следует подчеркнуть, что отсутствие в искомой сети тупиков предъявляет высокие требования к процедурам контроля графа "работы- вершины". В противном случае тупиковые операции исходной сети будут восприняты как исходные или завершающие операции комплекса. В частности, с помощью алгоритмов упорядочения и выделения связных компонентов ("букетов") операций проекта могут быть выявлены тупики, изолированные работы, а также непрерывные последовательности операций, не оказывающие влияния на конечную цель разработки. |