|
•гребность узла р°, распределяется между остальными этими узлами пропорционально их объемам. ■ В картах узлов, потребляющих услугу-номенклатуру р, этот узел заменяется узлами р1по одному для каждого потребителя. Граф Г', полученный из графа Г декомпозицией узла р, эквивалентен графу Г в том смысле, что граф Г однозначно восстанавливается по графу Г'. Для восстановления графа Г следует заменить в графе Г' все узлы p‘edec(p) одним узлом p=pnom(p% а все прошивки, идущие из каждого потребляемого узла-услуги s во все узлы р1, одной прошивкой, идущей из узла s в узел р; соответствующие изменения необходимо отразить в картах ресурсов потребляемых услуг. Рассмотрим далее алгоритм построения распределительного графа. Процедура декомпозиции одного узла детально описана. Из этого описания следует, что декомпозиция узла р (a) определяется общим списком потребителей•услуги р (списком использования основной номенклатуры и списком сопутствующих услуг), т.е. списком узлов последователей узла р; (b) изменяет, вообще говоря, в картах узлов-услуг, потребляемых услугой р, т.е. узлов —предшественников узла р, список потребителей; (c) отражается в карте узлов, потребляющих услугу р, т.е. узлов последователей узла р, лишь заменой узла р одним из узлов его декомпозиции. Сказанное означает, что декомпозиция узла, предшествующего узлу р, не может вызвать необходимость декомпозиции узла р, т.е. необходимость декомпозиции узла р может быть вызвана только самим узлом р или деком-' позицией какого-либо его узла-последователя, но не декомпозицией узла, предшествующего узлу р. Из предположения, что граф Г ’ацикличен, следует, что он допускает топологическую сортировку [143, 153, 156]. Алгоритм топологической сортировки приведен в [148, 149, 150]. Поскольку декомпозиции подлежат толь |
■ Пусть продукт s потребляется (возможно, частично) продуктом р. Если р имеет тип mix, то в списке использования основной номенклатуры или в списке сопутствующих продуктов узла s потребитель р заменяется всеми узлами р1из dec(p), а потребляемый узлом р объем разбивается пропорционально объемам этих узлов. Если же р имеет . тип new, то он в карте узла s заменяется только теми узлами р‘ из Щ dec(p), которые представляют основную номенклатуру узла р, а потребляемый узлом р объем продукта s, уменьшенный на потребность узла р°, распределяется между остальными этими узлами пропорционально их объемам. ■ В картах узлов, потребляющих продукт-номенклатуру р, этот узел заменяется узлами р' по одному для каждого потребителя. Граф Г', полученный из графа Г декомпозицией узла р, эквивалентен графу Г в том смысле, что граф Г однозначно восстанавливается по графу Г'. Для восстановления графа Г следует заменить в графе Г' все узлы p'edec(p) ^ одним узлом p=pnom(p'), а все прошивки, идущие из каждого потребляемого узла-продукта s во все узлы р1, одной прошивкой, идущей из узла s в узел р; соответствующие изменения необходимо отразить в картах ресурсов потребляемых продуктов. Рассмотрим далее алгоритм построения калькуляционного графа. Процедура декомпозиции одного узла детально описана. Из этого описания следует, что декомпозиция узла р (a) определяется общим списком потребителей продукта р (списком использования основной номенклатуры и списком сопутствующих продуктов), т.е. списком узлов последователей узла р; ♦ (b)изменяет, вообще говоря, в картах узлов-продуктов, потребляемых продуктом р, т.е. узлов предшественников узла р, список потребителей; (c) отражается в карте узлов, потребляющих продукт р, т.е. узлов последователей узла р, лишь заменой узла р одним из узлов его декомпозиции. 6 7 Сказанное означает, что декомпозиция узла, предшествующего узлу р, не может вызвать необходимость декомпозиции узла р, т.е. необходимость декомпозиции узла р может быть вызвана только самим узлом р или декомпозицией какого-либо его узла-последователя, но не декомпозицией узла, предшествующего узлу р. Из предположения, что граф Г ацикличен, следует, что он допускает топологическую сортировку [23], [71], [80]. Алгоритм топологической сортировки приведен в [52], [55], [56]. Поскольку декомпозиции подлежат только узлы-продукты, то сортировку можно применять лишь для узлов-продуктов, т.е. для строк матрицы инцидентности А, индекс которых больше числа платформ N q. После применения топологической сортировки все узлы (или как минимум узлы-продукты) графа пронумерованы в соответствии с последовательностью потребления. Пусть узел-продукт р имеет наибольший номер из всех узлов-продуктов; это означает, что он потребляется во внешней среде или / и узлами-платформами; иначе говоря, у него нет узлов-последователей, подлежащих декомпозиции. Граф, полученный декомпозицией узла р, обозначим через Г'; узлы из dec(p) оставим ненумерованными. Заметим, что каждый узел из dec(p) имеет не более одного узла-потребителя, и потому в силу условия (а) из вышеприведенного списка декомпозиции не подлежит. Пусть р’ узел-продукт с наибольшим номером в графе Г'. Этот узел не имеет уз* лов-последователей, подлежащих декомпозиции: действительно, он потребляется, возможно, во внешней среде, узлами из dec(p) (если потреблялся узлом р), узлами-платформами. Декомпозиция этого узла повлечет лишь изменения в картах этих узлов в соответствии с условием (с). Продолжая этот процесс, получим калькуляционный граф К. Таким образом, при условии ацикличности графа Г существует такой порядок последовательной декомпозиции всех узлов графа Г, что полученный в результате граф К, удовлетворяет условию (а) определения калькуля6 8 |