В корпоративных информационных системах алгоритмы теории графов могут применяться для автоматизации расчета себестоимости комплексных изделий.
Комплексное изделие имеет иерархическую структуру. Состоит из агрегатов, которые состоят из сборочных узлов, сборочные узлы состоят из других узлов и деталей и т.д.
Рассчитать себестоимость сложного изделия можно только по его структуре. Структуру комплексного изделия представляют в виде ориентированного графа и по графу вычисляют количество деталей в составе сборочных узлов и их себестоимость, количество сборочных узлов в составе изделия и их себестоимость и т.д.
В корпоративных информационных системах существуют средства для рисования структуры изделия. Эти средства не являются программой построения и обхода графа структуры изделия и не могут решать задачу автоматизации расчета себестоимости комплексных изделий.
Для автоматизации расчета себестоимости комплексных изделий нужно разработать алгоритмы и программы построения графа структуры изделия и вычислить по графу структуры изделия количество деталей в составе сборочных узлов и их себестоимость, количество сборочных узлов в составе изделия и их себестоимость и т.д.
Исходные данные - список деталей, сборочных улов и агрегатов в составе изделия и таблица отношений между деталями, сборочными узлами и агрегатами, где указано, какие детали и в каком количестве входят в состав сборочного узла, какие сборочные узлы и в каком количестве входят в состав агрегата и т.д. Значения элементов таблицы отношений aij, (j>i), равно количеству деталей номер i (сборочных узлов номер i) в составе сборочного узла номер j.
Для построения графа комплексного изделия и расчета себестоимости комплексного изделия множество деталей и сборочных узлов в составе изделия нужно упорядочить. Упорядочивание означает разбиение данного множества на классы. К первому классу относятся детали собственного изготовления. Ко второму классу относятся сборочные узлы, изготовленные из деталей первого класса. К третьему классу относятся сборочные узлы, изготовленные из деталей первого класса и сборочных узлов второго класса. К k-тому классу относятся сборочные узлы, изготовленные из деталей первого класса и сборочных узлов k-1-ого класса.
Для решения задачи упорядочивания состава сложного изделия используем таблицу отношений между деталями и сборочными узлами в составе сложного изделия. Обозначим матрицу отношений между деталями и сборочными узлами в составе сложного изделия A. Элементы первого класса - это заголовки нулевых столбцов матрицы A. Затем вычисляем степени матрицы An, (n>1), и в матрице An определяем «новые» нулевые столбцы, которые появляются в дополнение к матрице An-1. По номерам этих столбцов определяем их наименования и записываем в качестве элементов n- ого класса. Одновременно вычисляется количество данных столбцов и записывается в качестве элемента массива d(n). Значение элемента массива d(n) равно количеству элементов n – ой группы.
В программах расчета себестоимости сложных изделий вместо наименований комплектующих изделия используются их порядковые номера. В представлении структуры сложного изделия порядковые номера употребляются вместо наименования сборочного узла или детали. Поэтому нужно разработать алгоритм, устанавливающий соответствие порядковых номеров и наименований комплектующих. Точнее, нужно определить диапазон, в котором изменяются номера элементов n – ой группы, и по заданному номеру сборочного узла узнать номер группы, к которой принадлежит сборочный узел.
Номера элементов первой группы принимают значения от единицы до n(1), где n(1)- количество материалов первой группы. Номера элементов i-ой группы, (1<i ≤n), принимают значения xi, удовлетворяющие неравенствам:
,
где n(k)-количество элементов k-ой группы.
Обозначим
,
Тогда номера элементов i-ой группы, (1<i ≤n), принимают значения xi, удовлетворяющие неравенствам:
Построим граф представления структуры сложного изделия: определим множество дуг графа, определим допустимые пути графа и опишем алгоритм построения допустимых путей графа.
Множество вершин графа - множество номеров комплектующих. Все вершины графа распределяются по группам, соответствующим группам комплектующих сложного изделия.
Дуги графа соединяют вершины, соответствующие совместимым комплектующим из соседних групп. Начало дуги- вершина с меньшим номером, конец дуги- вершина с большим номером.
Путем, соединяющим вершину k- ой группы Vk с вершиной n- ой группы Vn, (n>k), называется последовательность попарно совместимых вершин (Vk, Vk+1, Vk+2….Vn) из групп k, k+1, k+2,…..n.
Задача расчета себестоимости сложного изделия сводится к построению всех путей, соединяющих вершины первой и последней группы и определению по каждому пути расхода комплектующих. Решение данной задачи получено на базе вычислительных сетей, мультипроцессорных вычислительных комплексов и распределенных кластеров. Задача решена с помощью параллельных алгоритмов теории графов. Параллельные алгоритмы теории графов применялись в [1] для решения задач оптимизации затрат материально – технического обеспечения строительно-монтажных работ.
Для реализации параллельного алгоритма построения путей графа последовательные группы материалов объединяются в блоки по n групп. При этом последняя группа k-ого блока совпадает с первой группой k+1-ого блока. Число n определяется производительностью кластера. На каждом кластере независимо от других и параллельно с другими кластерами определяются все пути, соединяющие вершины первой и последней группы блока. Поиск путей на кластере производится в параллельном режиме. На первом элементе кластера определяются пути, выходящие из вершины V1, на втором элементе определяются пути, выходящие из вершины V2, на i-ом элементе определяются пути, выходящие из вершины Vi. После построения путей на каждом блоке на k-ом кластере объединяются пути k-ого и k+1-ого блоков и получаются пути длины 2n. Затем в параллельном режиме объединяются пути двойных блоков и т.д. В результате получаются пути из вершин первой группы в вершины последней.
Пути, соединяющие фиксированную вершину первой группы с номером i с вершинами k- ой группы вычисляем последовательно. Вначале находим пути, соединяющие вершину i с совместимыми с ней вершинами второй группы, и записываем полученные пути в одномерный массив b, элементы которого b(n) являются символьными строками, где перечислены вершины пути, отделяемые друг от друга запятой. Например, для путей второй группы b(n)=i,m, где i- номер вершины из первой группы, m- номер вершины из второй группы. Пути k- ой группы записываются в одномерный массив b, элементы которого
b(n)=n1, n2,…. ni….. nk,
где ni- номер вершины из i - ой группы.
Начиная с группы номер три, достраиваем пути текущей k-ой группы до путей, заканчивающихся в вершинах следующей k+1-ой группы.
Для этого проверяем совместимость всех вершин k+1-ой группы с вершинами путей k-ой группы и добавляем совместимые вершины k+1-ой группы к соответствующим им путям k-ой группы. (Добавляем к символьной строке, определяющей значение пути k-ой группы, два символа: ”,” и номер вершины k+1-ой группы). Полученные новые значения массива путей записываем вместо текущих значений. Переходим к следующей группе и для нее повторяем описанные выше операции.
Для программирования процесса нужно формализовать описанные выше операции. Считаем, что на каждом шаге известны начальный номер элементов k-ой группы - ng количество вершин k-ой группы- n(k), количество путей k-ой группы - p(k) и значения массива путей k-ой группы- b(i), 1ip(k). Нужно пересчитать значения b(i) и определить значение p(k+1), равное числу путей k+1-ой группы.
Вначале текущую версию массива b записываем в массив c и пересчитываем значение начального номера: ng=ng+n(k)+1. Затем по значениям массива c вычисляем новую версию массива b. Для этого выбираем j - ую вершину k+1-ой группы, находим ее номер, равный j+ng, перебираем все пути b(i), находим вершины пути b(i), проверяем по матрице совместимости a совместимость вершин пути b(i) и вершины номер j+n(k)+1. Если все вершины пути b(i) совместимы с вершиной j+n(k)+1, то увеличиваем счетчик на единицу, добавляем к массиву c(i) запятую и номер j+n(k)+1 и получаем новое значение массива b(i). На последнем шаге полученный массив b записываем в файл, имя которого равно номеру вершины первой группы.
Для определения расхода детали (сборочного узла) Vi нужно найти все пути графа изделия, проходящие через вершину Vi. Точнее, нужно найти номера всех элементов массива путей графа изделия, проходящих через вершину Vi.
Решение данной задачи можно получить, если найти количество путей графа изделия, проходящих через вершину Vi.
Для нахождения количества путей графа изделия, проходящих через вершину Vi, нужно найти, сколько путей входит в вершину Vi, сколько путей выходит из вершины Vi.
Пусть вершина Vi принадлежит k–ой группе, 1<k<n. Обозначим D(k,i) –множество вершин k-1 –ой группы, совместимых с вершиной Vi, v(k,i)- количество путей графа изделия, входящих в вершину Vi, w(k,i)- количество путей графа изделия, выходящих из вершины Vi. Между элементами массива v(k,i) существуют следующие соотношения:
v(k,i) =
Используя эти соотношения, последовательно вычисляем v(k,i).
Значение w(k,i) вычисляется так же, как значение индикаторной переменной. Количество путей графа изделия, проходящих через вершину Vi, равно произведению v(k,i) и w(k,i).
Зная количество путей графа изделия, проходящих через вершину Vi, находим диапазон номеров данных путей и перебираем все пути с номерами из найденного диапазона. Другой способ определения путей графа изделия, проходящих через вершину Vi, заключается в просмотре всех путей графа и определении, есть ли среди вершин пути вершина Vi. Этот способ неэффективный, так как требует анализа всех путей графа.
Для расчета расхода детали (сборочного узла) Vi в каждом пути графа изделия, проходящем через вершину Vi, нужно найти значения номеров всех его вершин.
Вычисления номеров вершин графа выполняется по специальной программе обработки символьной строки, записывающей путь графа. В той строке номера вершин графа записываются между запятыми. Поэтому для вычисления номеров вершин графа определяются позиции запятых в символьной строке, записывающей путь графа, и находится последовательность цифровых символов, записанных между запятыми.
Расчет себестоимости сложного изделия производится в следующей последовательности:
Определяются себестоимости деталей собственного изготовления.
Последовательно вычисляют себестоимость сборочных узлов второго, третьего и т.д. класса.
Определяют расхода детали (сборочного узла) Vi по каждому пути графа изделия, проходящему через вершину Vi.
Определяют общий расход детали (сборочного узла) Vi как сумму расхода детали (сборочного узла) Vi по каждому пути графа изделия, проходящему через вершину Vi, и находят себестоимость изделия.
Расход детали (сборочного узла) Vi по каждому пути графа изделия, проходящему через вершину Vi, равен произведению значений таблицы отношений akm, где k, m – номера последовательных вершин графа, и k>m.
,
, 
