Устройство для определения экстремальных путей на графе Советский патент 1980 года по МПК G06G7/122 

YcflpoftcTBO позволяет производить ран жирование Берлин направленного графа 2. Однако оно не позволяет определять экстремальные пути, Цель изобретения - расширение функциональных возможностей за счет определения экстремальных путей меяеду люйлми вершинами графа. Указанная цель достигается тем, что в устройство для определения экстремальных путей на графе, содержгицее элемент И, выход которого соединрн со счетным входом первого триггера и с входом счетчика, выход которого подключен к нулевому входу второго триггера, единичный выход KOTJoporo соединен с первым входом. эле|| ента И, второй вход которого явл{яется выходом устройства, нулевой выхЬд первого .триггера подключен к управляющему входу ключа, выход которрго соединен с входом блока регис рации, линию задержки, выход которой подключен к нулевой вершине модели графа, каждая модель други кото рог t состоит из последовательно соединённых формирователя импульса,, светодиода оптрона и линии задержки дугйг коммутатор, входы которого под клЕочены к соответствующим вершинам модели графа, введены сумматор, блок кодзаровання и блок памяти тестовых команд, выходы которого соединены черфз фотодиоды соответствующих оптронрв с соответствующими входами блока кодирования, выходы которого подключены к входам сумматора, выход которого соединен с входом ключа, управляющий вход сумматора подключен к выходу первого триггера, единичный выход которого соединен с вводом линии задержки и с управ. входом блока памяти тестовых команд, управляющий выход которого подключен к управляющему входу коммутатора . На чертеже приведена структурная схема устройства. Устройство содержит наборное пол 1 дЛя набора моделей графов, формирователи 2 импульсов,оптроны 3, ли нию задержки дуги 4,-./первый триггер 5, блок б памяти тестовых команд ЛИНИЮ задержки 7, ключ 8, коммутатор 9, блок 10 кодирования, состоящий и переключателей 11 и диодов 12, блок 13 регистрации, элемент 14 И, второй тЬиггер 15, счетчик 16, сумматор 17 и вход 18. Блок 10 кодирования служит для выражения продолжительности t-: работы ( Х|, xj) двоичным кодом Сумматор 17 осуществляет ксследо ватеяьное суммирование пачкк импуль зов Из одного, двух и 6anfee двоичны .кодов, поступающих на его входы с интервалами задержки дЬ, задаваемыми линиями 4. Двоичный счетчик 16 формирует импульс переполнения при отработке заданного числа управляющих тестовых команд, поступающих из блока 6 через выходные цепи оптронов на блок 10 кодирования. Работа устройства состоит в следующем . Ориентированный граф представляет сетевой график, на котором дуги графа выражают работы, т.е. некоторые мероприятия, требующие затрат времени и материальных средств, а вершины графа (х, X,, Xg... х,) выражают события, которые состоят в завершении одной или нескольких работ. Конечным событием считается завершение всего комплекса работ (проекта). СоОыт.ия на сетевом графике пронумерованы, т.е. для любой (к; , Xj ) работы, выполняется условие i г j и каждой (х| , Xj) работе задана ее продолжительность. В блок 6 памяти тестовых команд для каждой пары событий (Хо, х:) заносятся группы наборов, каждый из кото 1Ж1Х выделяет один из путей между XQ и Xj . Каждый набор выделения пути между сойлтиями X X формируется путем подстановки единиц в разряды, соотл ветствующие дугам, входящим в путь. Реализация любого набора в устройстве осуществляется путем подачи единичного сигнала через фотодиоды оптроноз 3 тех дуг модели, КОТОЕЖЛМ соответствуют единичные значения соответствующих переменных в наборе. Все остальные фотодиоды оптронов в дугах модели графа обеспечены. При этом единичный сигнал, пропускаемый через выходную обмотку любого оптрона, при прохождении через блок 10 преобразовывается в двоичный код, задаваелелй переключателями 11 при каждом очередном распределении ресурсов (например, рабочей силы). Формируемый двоичный код на выходе блока 10 равен длительности- . Поскольку по отдельному набору подключаются фотодиоды оптронов, составляющих только один путь из Хо в Xj событие, то на выходе блока 10 при каждом импульсном возбуждении начала (х) модели графа формируется серия параллельных двоичных кодов из одного, двух, трех и т.д. кодов,, следующих с интервалами д t , определенными линиями 4 задержки. Параллельные двоичные коды каждой серии последовательно суммируются сумматором 17 и по команде записываются в блоке 13 в виде десятичного (двоичного) числа. Формируется команда Исходное (Исх),по которой блок 6, счетчик 16, триггеры 5 и 15, сумматор 17, коммутатор 9 устанавливаются в исходное состояние, т.е. вершину графа X, подключает на минус, элемент 14 закрывается, на &ход 18 устройства подается последовательность импульсов частоты f.

В счетчик 16 вводится дополнение (D) , обеспечивающее вьлдачу импульса переполнения при отсчете всех наборов.

С помощью переключателей 11 набираются двоичные числа, соответствующие продолжительности работ t,-y ,

По команде Пуск триггер 15 переходит в единичное состояние и открывает элемент 14.

Первь й из импульсов частоты f поступает на вход счетчика 16 и счетный вход триггера 5. На единичном выходе триггера 5 формируется сигнал, который поступает на управляющий вход блока 6 и через линию 7 задержки на вход Хд (начало проекта) модел графа. При этом блок 6 выдает первый набор. Первый набор, пройдя через мо даль графа и блок 10 кодирования, поступает на ход сумматора 17 в виде двоичного числа, отражающего t,. продолжительность работы (первый операнд), и суммируется с нулем {второй операнд).

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

По второму импульсу частоты f триггер 5 переходитв нулевое состоя ние и формирует команду управления, по .которой начинается процесс суммирования, передачи полученного результата через ключ 8 на блок 13 и обнулние сумматора 17.

По третьему импульсу частоты f триггер 5 переводится в единичное состояние и начинается второй цикл реализации второго набора, при этом коммутатор 9 подключает вершину графа Xg к минусу источника питания,,

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

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

По значению чисел, зафиксированны на бумажной ленте блока 13, определяют Т (критическое время) - наибольшее из чисел полного множества зафиксированных чисел; S (критический путь) - соответствует дугам набора, на котором определено критическое время Т ; Тг (критическое (минимсшьное) время наступления собы тин в j-ой вершине графа) - наибольшее из чисел подмножества, соответствующего Xjj X: наборам; S; кpитический (максимальный) путь, соединял щий события XQ и х- ) - соответствует дугам набора, на котором определено Tj

Устройство при наличии новых элементов и новых связей поз.воляет существенно расширить функциональные возможности и вычислять критические пути Sf, и время Т завершения проекта в целом и в каждой j-ой вершине ориентированного графа (Tj , Sj). В процессе выполнения проекта периодически и большое число раз производится распределение ресурсов (например, рабочей силы) на сети работ.

Это приводит к необходимости вычисления большого объекта параметров S , Т, Sj , Tj и связано с большими, затратами времени и средств Устройство позволяет с высокой точ1ностью,оперативностью и быстродействием производить вычисления исходных параметров для распределения ресурсов на сети работ, при этом по отношению к ручным методам Олстродействие возрастает в зависимости от сложности графа на 2-4 порядка раз, исключаются субъективные ошибки и создаются условия для принятия объективных решений при распределени ресурсов.

Формула изобретения

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

которого соединены через фотодиоды соответствующих оптронов с соответCTBytoiAHMH входами блока кодирования, выходы которого подключеныК входам сумматора, выход которого соединен с входом ключа, управляющий вход сумматора подключен к нулевому выходу первого триггера, единичный выход которого соединен с входом линии за.Ц8ржки и с управляющим входом . .-4l ilA...jLMJii .L i/2. - V/2 Щ Ja/2 { /2 4/2

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

Источники информации, принятые во внимание при экспертизе

1.Авторское свидетельство СССР №424152, кл. G Об F 15/20, 1972.

2.Авторское свидетельство СССР по заявке № 2447952/18-24,

кл. G Об G 7/122,. 1-977 (прототип). fin 1 t. o, - Щ..