книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов

де логической функции. В этой функции последовательному про­ хождению дуг пути соответствует их конъюнктивная связь, а па­ раллельному— дизъюнктивная связь.

Назначением задачи является ежемесячное наблюдение за свое­ временным и полным получением предприятиями управления со­ ответствующего оборудования.

При составлении текущей сводки о реализации фондов (CP') в любом из отделов в качестве одного из исходных документов ис­ пользуется книга фондов (КФ).

Вторым исходным до­ кументом является свод­ ка о реализации фондов за прошлый период (CP). При этом состав рекви­ зитов, участвующих в об­ разовании сводки о реа­ лизации фондов за теку­ щий период, постоянен и не зависит от состава и структуры сводки о реа­ лизации за прошлый пе­ риод, отражающей специ­ фику того или иного от­ дела. К числу этих рек­ визитов относятся: дата, наименование материала, единица измерения, реа­ лизация с начала года, реализация с начала квар­ тала.

Третьим исходным до­ кументом служит отчет о реализации фондов. Для транспортного отдела это форма ОРт, а для отдела оборудования — Ф-2. Не­ зависимо от формы отче­ та и его содержания при составлении сводки о реа­ лизации за текущий пе­ риод используются сле­ дующие его реквизиты: дата, наименование мате­

риала, количество за от­

Рис. 21. Граф алгоритма отдела обору- четный период. дования

112

Форма и структура документов, используемых при решении задачи, приведены ниже.

114

носильно нахождению подобных членов в соответствующих им ло­ гических функциях.

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

Вних можно выделить пять равных подпутей. Это начальный подпуть Я ь представляющий собой следующую совокупность дуг:

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

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

Установив наличие в алгоритмах одинаковых частей, можно

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

Впроцессе присоединения на базе графов равные подпути сов­ мещаются, а неравные присоединяются введением дополнительных вершин графа, т. е. путем расширения графа. Назначение этих вершин — разветвление алгоритма в соответствии со спецификой решения задач. Поскольку вершинами графа, представляющего алгоритм, являются операции, очевидно, дополнительной вершине графа будет соответствовать операция сравнения.

Впроцессе присоединения могут иметь место следующие три случая:

1)присоединяются равные подпути;

116

Вслучае присоединения равных подпутей конец уже присоеди­ ненного подпути и начало присоединяемого подпути должны сов­ падать. Другими словами, их общая вершина изображается одно­ кратно.

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

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

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

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

Второй вариант — когда изображенная часть алгоритма закан­ чивается вершиной, представляющей любую из операций, кроме сравнения. После этой вершины вводится дополнительная верши­ на, обеспечивающая разветвление алгоритма. Непосредственно с этой вершиной соединяются конечные вершины начальных дуг присоединяемых неравных подпутей. Общий вид графа, представ­ ляющего составной алгоритм задачи составления сводки о реали­ зации фондов в отделе оборудования и транспортном отделе, изоб­ ражен на рис. 23.

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

117

В процессе присоединения с использованием логических функ­ ций могут встречаться те же три случая, что и при использовании графов:

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

Первый вариант — когда равный подпуть заканчивается вер­ шиной, представляющей операцию сравнения. Тогда эта операция принимается за дополнительную вершину. К каждому из нерав­ ных подпутей в конъюнктивной связи прибавляется начальный подпуть единичной длины, отражающий связь этой дополнитель­ ной вершины и конечной вершины равного подпути. Иными сло­ вами, в качестве начальной дуги неравных подпутей вводится дуга

СрСр.

Второй вариант — когда равный подпуть заканчивается опе­ рацией, отличной "от операции сравнения. В этом случае после конечной вершины равного подпути предполагается наличие до­ полнительной вершины, отражающей операцию сравнения.

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

Первый вариант — когда длина каждого из неравных подпутей больше нуля. В этом случае равный подпуть присоединяется с по­ мощью конъюнктивной связи.

пути предполагается наличие дополнительной вершины, отражаю­ щей операцию сравнения.

В логической функции этому будет соответствовать продление равного подпути на дугу единичной длины, связывающую конеч­ ную вершину с дополнительной. Кроме того, каждый неравный подпуть удлиняется на одну дугу за счет укорочения последующе­ го равного подпути. Подпуть, длина которого не равна нулю, до­ полняется непосредственным добавлением в конъюнктивной связи первой дуги последующего равного подпути. Подпуть, длина ко­ торого равна нулю, дополняется видоизмененной первой дугой последующего равного подпути таким образом, что конечная вер-

119