Устройство для моделирования сетей

Номер патента: 1506452

Авторы: Табунщик, Тонкаль, Федотов

Есть еще 4 страницы.

Смотреть все страницы или скачать ZIP архив

Текст

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 19) 111 51)4 С 06 Г 1 САНИЕ ИЗОБРЕТЕНИ ЕПЬСТВУ ироваьч Тонкаль о СССР 1985.ССР 1986ВАНИЯ ычислиет бы испол ь изиротв для роении специа ельных устрой а сетях. Цель рение функцио достигается т зовано ли ванных решени ретени- расстей альны м, чт зм Изобелькой жет быт ь исполь хнике и постро ии специализирох устройств для овано анньм числитель задач на с 1 показан На фиг,схема модел ройства; на схема блока Модель 1 с первого п первый 9 ише тях.я является расных возможносте ционал ьная ью изобре ветви предл иг. 2 - фун гаемого устциональная ункционал а эа счет рение тройс управления, ветви (фиг,шестой триг ия задачивязанных и реше аимо) с од ержитеры 3-8, чики импульоптимизации двух ия такого пу пре ел токов се анной парой о пропускна ному потоку торои 10 сче 1 индикации, атый элемент шин сети, особность между заду которо ов, схе с первого И 12-25,ты ИЛИ 26 четырнад ервого п удовлетворяет ьшей (наибольо первисловиюей) про пятыи элеме ути с наимускной спо стью, а ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР К АВТОРСКОМУ Сви(71) Институт проблем моделв энергетике АН УССР(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРСЕТЕЙ(57) Изобретение относитсятельной технике и мож т ение относится к вычисли в устроиство, содержащее модели ветвей, содержащие с первого по четвертый триггеры, первый счетчик импульсов, схему индикации, с первогоно двенадцатый элементы И, с первого по третий элементы ИЛИ и блок управления, содержащий с первого пошестой триггеры, первый счетчик импульсов, с первого по девятый элементы И, элемент НЕ, первый и второйэлементы ИЛИ, и генератор импульсов,дополнительно введены в модели ветвей пятый и шестой триггеры, второйсчетчик импульсов, тринадцатый и четырнадцатый элементы И, четвертый ипятый элементы ИЛИ, а в блок управления введены с седьмого по девятыйтриггеры, второй счетчик импульсов,с десятого по четырнадцатый элементы ИЛИ и первый и второй многовходовые элементы ИЛИ. 2 ил. пускная способность по вторичн потоку больше (равна) некоторо мал ь ной д опус тимой велич и не .10 15 20 25 30 35 40 45 50 55 тл И ц вхдом уставнки в второго триггс рл, выход устлцонки в "0" третьегс трпг герд соедицс н с вьгходом десятого 1 лемецтл И, первый и второй входы кстор го соединены ссотцетствеццо са счетным входом первого счетчика импульсов и инверсным выходом четвертого триггера, прямой выход которого соединен с вторыми входами первого и второго элемецтов И, нход устлнонки в "1" гетвертог о триггера сое 1 гинец с выходом одиццлдцлтого элемента И, второй вход которого соединен с третьим входом модели ветви, вьгсод девятого элемента И является вторым вьсходом модели ветви, третий вход всех моделей ветвей соединен с третьим выходом блока упрлглепил н блоке управления третьим выходомявляется выход первого элемента ИП 1 первый и второй вхсды которого соединены соответственно с выходами пер - ного и второго элементов И, первый вход второго элемцтл И соедицец с прямым входом шестого триггерл, вход установки в О к торого есединец с выходом второго лно;. входовог о элемента ИЛИ, вход ус;лцонки в единицу шестого триггера соединен " выходом второго элемента ЛИ и первым входом пятого элемента И, вьцс,дкторого1 1 соединен с входом установки в 0 второго триггера, прямой выход которого соединен с первым нсодом четвертого элементл И, второй вход и выход которого соединены соответстнснцо с первым выходом генератора импульсон и первыми входами шестого, восьмого, девятого элементов И, второй вход шестого элемента И соединец с прямым выходом триггера, инверсный выход которого соединен с вторым входом восьмого элемента И, выход которого соедин н с первым входом второго элемента ,ЛИ,втор.й вхоп котсрого соединен с вьжслом переполнения первогс счетчика импу."ьсогз вход установки в "1" третьегс триггера соединен с выходом третьего э.емента И, первый вход которого соединен с ныхолом второго элемецтл ИЛИ и входом элемента НЕ выход которого соединен с первым входом первого элемента И, второй вход которого соединен с инверсным выходом первого триггера, прямой выход которого соединен с вторым входом второго элементл И, вы - ход седьмого элемента И соединен с входом установки в "1" четвертогогриггера, прямой выход которого соединен с вторыми входами пятого идевятого элементов И, первый входседьмого элемента И соединен с входом установки в "1" пятого триггера, прямой выход которого соединенс вторым входом седьмого элемента Ии третьим входом девятого элементаИ, инверсный ныход пятого триггерасоединен с вторым входом третьегоэлемента И и третьим входом шестого элемента И, инверсный выход четвертого триггера соединен с третьимвходом восьмого элемента И и является денятым выходом блока управления,инверсный выход пятого триггера является первым выходом блока управления, прямой ныход четвертого триггера является восьмым ныходом блокауправления, вьжод шестого элементаИ является вторым выходом блока управления, выходы второго элемента ИЛИи девятого элемента И являются пергым и вторым полюсами блока управления и соединены с теми полюсамимодели сети, составленной из моделен ветвеи, между которыми отыскивается путь с заданной пропускной способностью первые, нторые, восьмые идевятые выходы всех моделей ветвейсоединены соответственно с одноименцылги ньжодлми блока упранления, первый, второй, восьмой, девятый нходыи первый, второй выходы моделейветвей соединены соответственно с третьими входами пятого и седьмогоэлементов И, первым входом десятогоэлемента И, третьим входом восьмогоэлемента И и третьим входом шестогоэлемента И о т л и ч а ю щ е е с ятем, что, с целью расширения функциональных возможностей, в устройствовведены в модель ветви пятый и шестой триггеры, второй счетчик импульсон, тринадцатый и четырнадцатый элементы И, четвертый и пятый элементыИЛИ, третьи входы первого и второгоэлементов И соединены с четвертымивходами третьего и четвертого элементов И и соединены с четвертымивходами с пятого по восьмой элементовИ и инверсным выходом пятого триггера, вход установки в "1" которого соедицец с выходом тринадцатого элемента И, первый и второй входы которогосоединены соответствецйо с выходомпереполнения второго счетчика импуль 1506452212210 15 20 25 30 35 40 сов и инверсным выходом шестого триггера, входы установки в "1" и "О"которого являются пятым и шестым входами модели ветви, причем последнийсоединен с первыми входами четвертого и пятого элементов ИЛИ, второйвход четвертого элемента ИЛИ соединенс первым входом двенадцатого элементаИ, выход которого является первым выходом модели ветви, выход четвертогоэлемента ИЛИ соединен с входом установки в "О" второго триггера, инверсный выход третьего триггера соединенс вторым входом девятого элемента И,выход которого является вторым выходом модели ветви, вторые входы пятогоэлемента ИЛИ и одиннадцатого элемента И являются соответственно четвертым и третьим выходами модели ветви,выход пятого элемента ИЛИ соединенс входом установки в "О" четвертоготриггера, прямой выход которого соединен с вторыми входами первого и четырнадцатого элементов И, счетныйвход второго счетчика соединен свыходом четырнадцатого элемента И,первый вход которого является седьмымвходом модели ветви, с третьего поседьмой входы всех моделей ветвейсоединены с соответствующими выходамиблока управления, в который дополнительно введены с седьмого по девятыйтриггеры, второй счетчик импульсов,с девятого по четырнадцатый элементыИЛИ, второй выход генератора импульсов соединен с первым входом одиннадцатого элемента И, второй и третийвходы и выход которого соединены соответственно с прямым и инверсным выходом восьмого и девятого триггераи первым входом четвертого элементаИЛИ, второй вход которого соединен спрямыми входами пятого и выходом девятаго триггеров и выходом четырнад цатого элемента И, первый и второй входы которого соединены соответственно с прямым выходом восьмоготриггера и выходом девятого элемента И, второй вход и выход которого соединены соответственно с инверсным выходом восьмого триггера и входом установки в "1" седьмого триггера, вход установки в "О" которого соединен с выходом переполнения первого счетчика импульсов, входом генератора импульсов и первым входом двенадцатого элемента И, второй вход которого соединен с входом десятого элеменга И и прямым выходом седьмого триггера, инверсный выход которого соединен с третьими входами второго и четвертого элементов И, первый выход генератора импульсов соединен с вторым входам десятого элемента И, выход которого является седьмым выходом блока управления и соединенс первым входом третьего элемента ИЛИ и счетным входом второго счетчика импульсов, выход переполнения которого является пятым выходом блока управления, второй вход и выход третьего элемента ИЛИ соединены соответственно с выходом шестого элемента И и счетным входом первого счетчика импульсов, входы установки в " 1" и "О" третьего триггера соединены соответственно с выходами третьего элемента И и четвертого элемента ИЛИ, входы установки в " 1" и "О" восьмого триггера соединены соответственно с выходами двенадцатого и одиннадцатого элементов И, причем выход последнего является шестым выходом бло" ка управления, прямые выходы пятого и четвертого триггеров являются четвертым и восьмым выхадамц блока управления.15064 52 Фиг,1 1 б г.1 оставитель О.ехред М,Морген Редактор В. Петраш Корректор баци 668 писное 7роиэводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 аказ 5440/51НИИПИ Государ венного коми 113035, Моск а по изобретениям Ж, Раушская на рытиям при ГКНТ СССР 4/5150Блок 2 управления ( фиг. 2) содержит с первого по девятый триггеры31-39, первый 40 и второй 4 1 счетчики импульсов, с первого по четырнадцатый элементы И 42-55, элементНЕ 56, с первого по четвертый элементы ИЛИ 51-60, генератор 61 импульсов.Кроме того, устройство содержитпервый 62 и второй 63 многовходовыеэлементы ИЛИ (фиг. 2). Число входовмноговходовых элементов ИЛИ 62 и 63соответствует числу моделей ветвей,Устройство имеет полюсы 64-18, изкоторых полюсы 64 и 65 у модели 1ветви служат для коммутации их между собой согласно конфигурации моделируемой сети. Полюсы 66 и 67 блока 2 управления служат соответственно для подключения этого блока кполюсам 64 и 65 тех моделей 1 ветвей,между которыми отыскивается указанный путь. Остальные полюсы каждоймодели ветви служат для подключенияих к блоку управления, что обеспечивает синхронную работу всего устройства,ш 1 п шах(Ч; )К т х х е К(4) Исходными данными задачи оптимизации двух взаимосвязанных потоков является коммутация моделей 1 ветвей полюсами 64 и 65 между собой согласно конфигурации модепируемой сети, подключение полюсов 66 и 67 блока 2 управления к полюсам тех моделей ветвей, между которыми отыскивается требуемый путь. Кроме того, в счетчики 9 и 10 моделей ветвей соответственно заносят число импульсов, равное И; и И-Ь; , а в счетчик 4 1 блока управления заносят число импульсов, равное Б-Ъ, где И - емкость счетчиков 9 и 10 импульсов моделей 1 ветвей и счетчиков 40 и 4 1 блока 2 управления.Суть решения задачи оптимизации двух взаимосвязанных потоков заклю" чается в определении такого пути между заданной парой вершин сети, у которого пропускная способность Р по первичному и вторичному потокам удовлетворяет условиям: 6452где Ь. - величина вторичного потока1по ветви (х;х );Ь - заданная минимальная допусстимая величина вторичного потока каждой ветви сети;о- величина первичного потокапо ветви (х х,).Согласно этим условиям процесс решения задачи на данном устройствеможно представить в виде трех этапов.Первый этап состоит в выделении иэвсего множества ветвей сети такихветвей, пропускная способность первичного потока которых удовлетворяет следующим условиям в зависимостиот того, какое условие,(1) или (2)является основным для оптимизации: ш 1 п т ппп(с 1; )25 К хх еК где К - любой (Б-Г.) разрез (на множестве ветвей), где Я исоответственно начальная и 30 конечная вершины сети, междукоторыми определяется путь;х и х - -я и 1-я вершины сети9Ч - пропускная способность ветвимежду х -й и х .-й вершинами.35 Этот этап включает циклически повторяющиеся операции: нахождение(х;-х;) разреза из множества разрезовК, выбор ветви разреза (х,.-х .) сш 1 птЧ, ) или шах Ч;(зависйт от 40 выбранного условия (1) или (2; выделение ветвей сети, у которых пропускная способность меньше или равнапропускной способности выбранной ветви разреза (согласно условиям (1) 45 и (3 или больше или равна пропускной спесобности выбранной ветви разреза (согласно условиям (2) и (4.Вторая и третья операции выполняютсяустройством одновременно. Послекаждого цикла выполнения операцийпервого этапа число проверяемых ветвей сети уменьшается эа счет эакорачивания между собой полюсов 64 и 65моделей, которые удовлетворяют задан ному условию. Выполнение операций нерпервого этапа повторяется до тех пор,пока полюсы, между которыми отыскивается путь, не будут эакорочены5064.2 Второй этап состоит в проверкевыполнения условия () ипи (2) папропускной способцости вторичногопотока ветвей, которые выбраны цапервом этапе и проверке существованипути между заданными вершинами, состоящего из ветвей, пропускные способности которых удовлетворяют условию (1) или (2), Если пропускныеспособности по вторичному потокувсех выбранных на первом этапе ветвей удовлетворяют заданному условию (Ь, ), Ь ), та устройство производит выделение ветвей пути междузаданными вершинами сети. Выделениеветвей искомого пути является третьим этапом работы устройства.В противном случае, если и втором этапе будут найдены ветви, пропускная способность по вторичномупотоку которых не удовлетворяет заданному условию, та эти ветви исключаются из дальнейшего процесса решения задачи, Исключение ветвейосуществляется за счет разрыва цепейпрохождения каких-либо сигналов атполюса 64 на полюс 65, и наобар т,что осуществляется блокировкой входаи выхода в модели ветви. После удаления ветвей устройство проверяетналичие пути между заданными вершинами сети, который проходит только паветвям, удовлетворяющим условию (1)или (2). Если такого пути нет, гоустройство переходит опять к выполнению шагов первого этапа. При этомв качестве исходной сети выступаетсеть, в которой исключены ветви цавтором этапеВыполнение операцийпервого и второго этапов устройство.производит до тех пар, пока не будет найден путь, пропускные способности ветвей по первичному ц вторичному потокам которого це будут удовлетворять условию (1) илц (2),Выбор условия оптимизации (1) ипи(2) определяется састаянием триггера 3 1 блока 2 управления (фиг. 2),Если триггер 31 находится в нулевомсостоянии, то основным условием оптимизации двух взаимосвязанных потоковв сети является условие (1). Еслитриггер 31 находится в единичномсостоянии, то основным условием выступает условие (2).Перед началом работы устройстватриггеры 3-8 всех моделей 1 ветвейи триггеры 32-39 и счетчик 40 импуль 6О Ов бл Ока 2 упра вп ения уста на влива-ются в нулевое состояние (шины занесения исходных дацных и установочные шццы не показаны),5я Рассмотрим рабату устройства,когда основным условием оптимизациидвух взаимосвязацних потоков является условие (2). В этом случае триг 1 О гер 31 блока 2 управления установленв единичном состоянии.Рабоз а устройства начинаетсяс момента установки триггера 32 ве;шцичное ссстояние. Единичное состояние триггера 32 блока управления (фиг. 2) выдает разрешение навход элемента И 45, на другой входк, торого поступает разрешение с нулевого выхода триггера 37. В резуль 2 тате импульсы от генератора 61 проходят через элемент И 45. С выходаэлемента И 45 эти импульсы поступают ца вход элементов И 47, 49 и 50,Через элементы И 47 и 50 импульсы не25 проходят, так как цет разрешения навходы этих элементов с триггеров 33и 34 (ани находятся в нулевом состоянии), через элемент И 4 С 1 мпульсы генератара проходят и чер:-э элемент ИЛИ5 г поступают ца цспюс 66 блока 2 управления. Одновременна : этим первыйимпульс из всей серии, к горая поступает через элемент ИПИ 58, устанавливает триггер э 6 в еп;цичцае састая 35ние. Единично;" состояние триггеэа36 выдаег ра,решение на вход элемента И 43, на другой ьхад которого поступает разрешение . единичного выхода триггера 31 (этат триггер пав4 О ходится в единичном с 1 стаянии, таккак основное условие оптимизацииусловие (2,В результате на выходеэлемента И 43 появляется игнал, который через элемент ИГП 1 57 поступает45 на полюс 71 блока 2 управления.С папюса 71 блока 2 управлениясигнал поступает на вход элемента И 22всех моделейветвей, чта обеспечивает прохождение сигналов черезэтОт элемент,Импульсы с папюса 66 блока 2 управления поступают на полюсы 64 или65 моделей 1 ветвей, которые в результате коммутации этих полюсов между собой образуют вершину сети, изкоторой отыскивается путь, удовлетворяющий условию (2),В указанных моделяхветвейлают на вход элементов И 13 и 15-17. Через элементы И 13, 15 и 17 импульсы не проходят, так как на других входах у пих нет разрешения. На всех входах элемента И 16 есть разрешение, поэтому с выхода этого элемента импульсы через элемент ИЛИ 28 поступают на единичный вход тригг ера 3, По первому импульсу из всей серии импульсов, поступивших в модель 1 ветви на полюс 64, триггер 3 устанавливается в единичное состояние. Всепоследующие импульсы подтверждаютэто состояние триггера 3. Аналогично, если импульсы поступают на полюс 65 модели 1 ветви, они проходят только через элементы И 18 и ИЛИ 27 и устанавливают триггер ч в единичное состояние.Единичное состояние триггера 3 или 4 выдает разрешение на вход элемента И 20 через элемент ИЛИ 26 и свидетельствует о том, что данная модель 1 ветви принадлежит выбранному разрезу (х, - х ) из множества разрезов К. Это соответствует первой операции первого этапа решения задачи.Разрешение с выхода элемента И 20 поступает на полюс 70 модели 1 ветви. Это возможно потому, что на другом входе элемента И 20 есть разрешение, снимаемое с нулевого выхода тригге - ра 5С полюса 70 модели 1 ветви разрешение поступает на соответствующий вход 70 многовходового элемента ИЛИ 62 (фиг. 2). Причем на входы 70 многовходового элемента ИЛИ 62 поступают разрешения только от тех моделеи 1 ветвей, триггеры .3 или 4 которых находятся в единичном состоянии,Выбор модели ветви, принадлежащей сформированному разрезу, с пропускной способностью первичного потока, равного папс, , а также моделей ветвей, пропускная способность первичного потока которых меньше или равна пропускной способности выбранной ветви, происходит по разрешению, которое появляется на выходе многовходового элемента ИЛИ 62. Это разрешение поступает на вход элементов НЕ 56 и И 44.На выходе элемента НЕ 56 исчезает разрешение, которое поступает на вход элемента И 42. Однако другой вход элемента И 42 заблокирован единичным состоянием триггера 31 и,следовательно, изменение сигнала наполюсе 71 блока 2 управления не про 5исходит. Через элемент И 44 разрешение проходит, так как на другомего входе есть разрешение с нулевого выхода триггера 35, и поступаетна единичный вход триггера 33. В результате триггер 33 устанавливаетсяв единичное состояние. Единичное состояние триггера 33 запрещает прохождение импульсов через элементы И 49и ИЛИ 58 на полюс 66 блока 2 управления и разрешает прохождение импульса генератора 61 с выхода элемента И 45 через элемент И 4 7. Единичное состояние триггера 33 свидетельствует о том, что устройство начинает выполнять вторую и третью операции первого этапа. С выхода элемента И 47 импульсы генератора 61поступают на полюс 69 и через элементИЛИ 59 на вход счетчика 40 импульсов25 до его переполнения,В каждой модели 1 ветви импульсыс полюса 69 поступают на вход элеменга И 21 и счетчика 9 импульсов доего переполнения. Импучьс переполне 30 пия счетчика 9 модели ветви устанавливает триггер 5 в единичное состояние. Одновременно этот импульсчерез элемент И 23 поступает на полюс 76 тех моделей 1 ветвей 1 которыепринадлежат выбранному разрезу. Кроме того, этот импульс через элементИЛИ 29 поступает на нулевые входытриггеров 3 и 4,40 Единичное состояние триггера 5через элемент И 22 устанавливаеттриггер 6 в единичное состояние. Вэтом случае триггер 5 остается в единичном состоянии, так как единичное 4 состояние триггера 6 запрещает прохождение очередного импульса с полюса 69 через элемент И 21 на нулевойвход триггера 5.Импульс, поступивший на нулевыевходы триггеров 3 и 4 с выхода счетчика 6 импульсов, устанавливает их внулевое состояние, если один из нихранее был установлен в единичное состояние импульсами, которые поступилина полюс 64 или 65 модели ветви. В 55результате установки триггеров 3 или4 в нулевое состояние снимаются всесигналы с полюсов 70 многовходовогоэлемента ИЛИ 62 и, следовательно,15064 52 30 50 снимается сигнал с выхода этого эле мента.С полюса 76 модели 1 ветви импульс поступает на соответствующий этой модели ветви вход 76 многовходово 5 го элемента ИЛИ 63 и, пройдя этот многовходовый элемент, поступает на нулевой вход триггера 36. В результате триггер 36 устанавливается в ну- О левое состояние. Первый импульс, появившийся на одном из входов 76 многовходового элемента ИЛИ 63, определяет модель ветви, у которой наименьшая пропускная способность по первичному потоку ш 1 п 1 с 1,и которая принадлежит выбранному разрезу (х- х ). Нулевое состояние триггера 36 сйимает разрешение с входа элемента И 43 и, соответственно, через эле мент ИЛИ 57 с полюса 71 всех моделей 1 ветви.Единичное состояние триггера 6 выдает разрешение на входы элементовИ 12 и 13, что обеспечивает закорачивание полюсов 64 и 65 модели ветви.Закорачивание полюсов 64 и 65 модели ветви исключает ветвь иэ дальнейших проверок, которые выполняютсяна первом этапе, Таким образом, вмоделях 1 ветвей сети, у которыхпропускная способность меньше илиравна пропускной способности моделиветви разреза, триггеры 5 и 6 устанавливаются в единичное состояние,триггеры 3 и 4 - в нулевое и их полюсы 64 и 65 закорачиваются. Это происходит потому, что в моделях 1ветвей, у которых импульс переполнения счетчика 9, появившийся после40того, как будет снято разрешение сполюса 71 и входа элемента И 22,триггер 5 устанавливается в единичное состояние, а затем этот триггер устанавливается в нулевое состояние очередным импульсом, поступившим на полюс 69, Это происходит в результате того, что единичное состояние триггера 5 выдает сигнал на входэлемента И 22, Через этот элементсигнал не проходит, и триггер 6 остается в нулевом состоянии, что позволяет проходить через элемент И 21очередному импульсу, который поступает на полюс 69 из блока 2 управления от генератора 61 импульсов.Импульс переполнения счетчика 40блока 2 управления поступает черезэлемент ИЛИ 58 на полюс 66. Далее 1 Оэтот импульс поступает на полюс 64или 65 моделей ветвей и весь процесс работы устройства повторяетсяаналогично описанному выше, т.е, устройство повторяет операции первогоэтапа.Такие процессы повторяются до техпор, пока очередной импульс переполнения счетчика 40 блока 2 управления,поступающий на полюс 66, не появитсяна полюсе 67. Это происходит потому, что импульс с полюса 66 поступает на полюс 64 или 65 моделей 1 ветвей и, проходя соответственно элементы И 13 и 12, появляется на полюсе 65 или 64 соответственно модели 1 ветви.Момент появления импульса на полюсе 67 блока 2 управления свидетельствует об окончании выполнения устройства второй и третьей операций первого этапа, К этому моменту все множество ветвей моделируемой сети разбито на два подмножества. Одно подмножество содержит ветви, пропускная способность по первичному потоку Ч, которых удовлетворяет условию (4), и в соответствующих им моделях 1 ветвей триггера 5 и 6 находятся в единичном состоянии. Другое подмножество содержит ветви с пропускными способностями, которые не удовлетворяют условию (4), и их триггеры 5 и 6 находятся в нулевом состоянии. Эти модели в процессе выполнения следующего этапа работы устройства не участвуют. Кроме того, к этому моменту в счетчиках 9 всех моделей 1 ветвей восстанавливается информация об их пропускной способности по первичному потоку, т.е. происходит регенерация. Роль регенерационного счетчика для счетчиков 9 всех моделей 1 ветвей выполняет счетчик 40 импульсов блока 2 управления, который начинает счет с "0" и его емкость равна И. Счетчики 9 всех моделей 1 ветвей начинают счет с И-с11Импульс с полюса 67 в блоке 2 управления поступает на вход элементов И 54 и 55, Через элемент И 55 этот импульс не проходит, так как триггер 38 находится в нулевом состоянии, а через элемент И 54 импульс проходит на единичный вход триггера 37, В результате этот триггер устанавливается в единичное состояние. Единичное состояние триггера 37 выдает разрешение на вход элементов И 51 и 53 иснимает ра ьрешсцие с входа элемента И 45, 1;дццичцое состояние триггера 37 свидетельствует о том, что устройство начинает выполнять операци 1 второго этапа. При этом импульсы генератора 61 проходят через элемент И 51, Лалее оци поступают на полюс 75 и через элемент ИЛ 11 59 ца вход счетчика 40, С полюса 75 эти импульсы по%ступают в каждой модели 1 ветви на вход элемента И 25. Кроме того, импульсы с выхода элемента И 51 поступают на вход счетчик 41.В каждой модели 1 ветви ти импульсы проходят череэ элемент И 25 только в тех моделях ветвей, триггер б которых находится в единичном состоянии, и далее поступают на вход счетчика 10 импульсов до его переполнения. Импульс переполнения счетчика 10 поступает на вход элемента И 24. Через этот элемент импульс переполнения счетчика 10 может пройти в том случае, если триггер 8 находится в нулевом состоянии, Состояние триггеров 8 всех моделей ветвей определяется работой счетчика 4 1 импульсов блока 2 управления. Импульс переполнения счетчика 4 1 поступает на полюс 73 всех моделей 1 ветвей и устанавливает триггер 8 в еЯничное состояние, что запрещает прохождение импульсов переполнения счетчика 10 через элемент И 24.Единичное состояние триггера 7 в моделях ветвей свидетельствует о том, что пропускная способность по вторичному потоку в данных моделях не удовлетворяет условию (2), т.е. Ь с Ь , Такие модели ветвей и,оследовательно, соответствующие им ветви моделируемой сети из дальнейшего процесса решения задачи исключаются. Исключение моделей ветвей иэ дальнейшего процесса решения задачи осуществляется за счет съема разрешения с входов элементов И 12- 19 в модели ветви, что запрещает прохождение си налов с полюса 64 на полюс 65 и наоборот, через модель ветви.Выполнецие второго этапа работы устройства продолжается до момента появления импульса переполнения счетчика 40 импульсов блока 2 управления (фиг. 2). К -тому моменту все подмножество ветвей, которое выбрано на первом этапе и пропускная спос.об 5055 Кроме того, этот импульс переполне - ния счетчика 40 поступает на вход генератора 6 1 импульсов и, соответственно, на единичный вход триггера 38 через элемент И 53 и на нулевой вход триггера 37, В результате триггер 38 устанавливается в единичное состояние, а триггер 37 - в нулевое.Рулевое состояние триггера 37 снимает разрешение с выхода элемента И 51, что прекращает поступление импульсов генератора 61 на полюсы 69 ность по первичному потоку которыхудовлетворяет условию (4), еще раз -бинается на два подмножества. Одноподмцожестно содержит ветви моделируемой сети, которые полностью удовлетворяют условию (2), т.е, их пропускные способности по первичному потоку и цо вторичному соответствуюттребованиям, которые предъявляютсяк искомому пути. В соответствующихэтим ветвям моделях триггеры 5 и 6должны находиться в единичном состоянии, а триггер 7 - в нулевом, Для 15 другого подмножества пропускные способности ветвей по первичному потокуудовлетворяют условию (4).и, следовательно, условию (2), а по вторичномупотоку их пропускные способности не 20 удовлетворяют условию (2), т,е. Условие (2) полностью не выполняется. Всоответствующих этим ветвям моделяхтриггеры 5 и 6 находятся в единичномсостоянии, а также в единичном состоянии находится триггер 7.Проверка существования пути в сети между заданными вершинами, состоящего иэ ветвей, которые удовлетворяют полностью условию (2), устрой.тво производит следующим образом. Импульс переполнения счетчика40 импульсов через элемент ИЛИ 58поступает на полюс 66 блока управления,. К этому моменту в счетчике 1 Овсех моделей 1 ветвей и в счетчике 355 41 импульсов блока 2 управления восстанавливается информация о Ь; и,Чсоответственно, о Ь . Роль регенерациоццого счетчика в этом случае, также как и в предыдущем, выполняетсчетчик 40 импульсов блока 2 управления, который начинает счет с "0" иего емкость равна И, Счетчики 10всех моделей ветвей и счетчик 4 1 блока управления начинают счет соответственно с И-Ь;, и И-Ь,.506452 Единичное состояние триггера 35 снимает разрешение с полюсов 68 всех моделей 1 ветвей и выдает разрешение на полюсы 72. В результате в каждой модели ветви блокируются элементы И 16 и 18, а на входе элемента ИЛИ 30 появляется сигнал, который устанавливает триггер 6 в нулевое состояц ие. Нулевое состояние триггера 6 снимает разрешение с входов элементов И 12 и 13, чем блокирует входы 13и 75 и входы счетчиков ч 0 ц ч 1 блока2 управления.Единичное состояние триггера 38выдает разрешецие ца вход элементовИ 52 и 55, что обеспечивает прохожде 5цие сигналов через эти элементы, Одновременно с этим импульс переполнения счетчика 40, поступивший ца полюс66 блока управления, опять поступаетна полюс 64 или 65 моделей 1 ветвей,который в результате коммутации этихполюсов между собой образует вершинусети, из которой отыскивается путь,удовлетворяющии полностью условию(2). В моделях ветвей этот импульс сполюса 64 поступает через элемент И 1313 на полюс 65. Аналогично, если этотимпульс поступает на полюс 65, то онпроходит через элемент И 12 на полюс 64 .Таким образом, распространяясьпо сети с полюса 64 на полюс 65 илис полюса 65 на полюс 64 от модели кмодели, этот импульс появляется цаполюсе 67 блока управления. Распространение импульсов переполнениясчетчика 40 на втором этапе возможнотолько по тем моделям ветвей, триггеры 5 и 6 которых находятся в едицичцом 30состоянии, а триггер 7 - в нулевом,Появление импульса на полюсе 67блока 2 управления свидетельствует отом, что путь, пропускная способностьветвей которого полностью удовлегворяет условию (2), найден и устройство в этом случае переходит к выполнению заключительного этапа работывыделению ветвей искомого пути. Впротивном случае, если импульс ца полюсе 67 не появляется, что свидетель 40ствует об отсутствии искомого пути,устройство переходит опять к выполнению операций первого этапа, и весьпроцесс работы устройства повторитсяаналогично описанному выше,Переход устройства к выполнениюопераций первого этапа происходитследующим образомПо импульсу переполнения счетчи 50ка 40 блока 2 управления, который поступает на вход генератора 61 импульсов в конце второго этапа работы устройства, генератор импульсоввыдает импульс, сдвинутый относительно входного, на вход элемента И 52.55Этот импульс проходит через элементИ 52 и поступает на нулевой входтриггера 38, на вход элемента ИЛИ 60 и ца полюс 74 всех моделей 1 ветвейПри этом в каждой модели ветви импульс с полюса 74 поступает на нулевой вход триггера 8 и через элементы И 1 И 30 и 29 на нулевые вхсды триггеров 6, 3 и 4, устанавливая этитриггеры в нулевое состояние. Одноцременцо с этим устанавливается в нулевое состояние триггер 38, что запрещает прохождение дальнейших сигналов через элементы И 52 и 55, и внулевое состояние триггер 33. Нулевое состояние триггера 33 разрешаетпрохождение импульсов генератора 6 1через элементы И 49 и ИЛИ 58 на полюс66 блока 2 управления. Это приводитк тому, что весь описанный вышепроцесс повторяется. То есть устройство перейдет к выполнению операций первого и второго этапов. Приэтом из моделируемой сети исключаются ветви, которые не удовлетворяютусловию (2). В соответствующих этимветвям моделях триггер 7 находится вединичном состоянии, чем обеспечивается исключение таких моделей издальнейшего процесса решения задачи.Выделение ветвей искомого пути,что соответствует последнему этапуработы устройства, происходит следующим образом.Импульс, поступивший на полюс 67блока 2 управления, поступает на входэлементов И 54 и 55. Через элемент И54 импульс не проходи"., так как триггер 38 в этом случае находится вединичном состоянии, а через элементИ 55 он проходит на единичный входтриггера 35 и через элемент ИЛИ 60на нулевой вход триггера 33. В результате триггеры 35 и 33 соответственно устанавливаются в единичноеи нулевое состояния. Кроме Того, этотимпульс устанавливает триггер 39 вединичное состояние, что блокируетвход элемента И 52,1506452В результате импульсы генератора61 с выхода элемента И 45 черезэлемент И 50 и начинают поступатьна полюс 67 блока управления и далеена полюсы 65 тех моделей ветвей, которые полюсом 65 подключены к полюсу67 блока 2 управления. В моделях ветвей импульсы с полюса 65 через эле 10 менты И 19 и ИЛИ 27 поступают наединичный вход триггера 4. По первому импульсу из всей этой серии импульсов триггер 4 устанавливаетсяв единичное состояние, что обеспечивает прохождение остальных импульсов этой серии с полюса 65 черезэлемент И 14 на полюс 64 модели ветви, Таким образом, импульсы, распространяясь по сети с полюса 65 на по 20 люс 64 от модели к модели, устанавливают триггер 4 в единичное состояние и появляются на полюсе 66 блока2 управления, Следует заметить, чтораспространение импульсов с полюса 6725 блока управления через модели ветвейна полюс бб происходит только по теммоделям ветвей, у которых триггеры 5и 7 находятся соответственно в единичном и нулевом состоянии. Эти моде 30 ли соответству.от ветвям, пропускныеспособности которых полностью удовлетворяют условию (2). 15 этих элементов и не позволяет проходить сигналам через них.Одновременно с этим, нулевое состояние триггера 33 разрешает прохождение импульсов генератора 61 черезэлементы И 49 и ИЛИ 58 на полюс Ьбблока 2 управления. Эти импульсы генератора 61 с полюса 66 поступают наполюсы 64 моделей ветвей, которыеэтим полюсом подключены к полюсу ббблока управления и образуют вершину, из которой отыскивается необходимый путь,В модели ветви импульсы с полюса64 через элементы И 17 и ИЛИ 28 поступают на единичный вход триггера 3.По первому импульсу из всей этой серии импульсов триггер 3 устанавливается в единичное состояние. Единичное состояние триггера 3 выдаетразрешение на вход элемента И 15,чем обеспечивается прохождение остальных импульсов этой серии с полюса 64 через элемент И 15 на полюс 65модели ветви (фиг. 1). Таким образом, импульсы, распространяясь по сети от модели к модели, устанавливают триггеры 3 в единичное состояние и появляются на полюсе 67 блока 2 управления. Причем эти импуль -сы распространяются топько по теммоделям ветвей, у которых триггер 5находится в единичном состоянии, атриггер 7 - в нулевом. Эти моделисоответствуют ветвям исследуемойсети, пропускные способности каждойиз которых полностью удовлетворяютусловию (2) . По первому импульсу, появившемуся на полюсе 67 блока 2 управления, триггер 34 устанавливается в единичное состояние, так как этот импульс проходит через элементы И 55 и 48 на единичный вход триггера 34 (в этот момент триггеры 38 и 35 находятся в единичном состоянии)Единичное состояние триггера 34 снимает разрешение с входа элемента И 49 и полюса 78. В результате прекращается поступление импульсов генератора 61 через элемент И 49 на полюс 66, а во всех моделях 1 ветвей снимаетгч разрешение с входа элемента И 17. Кроме того, единичное состояние триггера 34 выдает разрешение на вход элементов И 46 и 50 и полюсы 77 всех моделей 1 ветвей. Появление первого импульса этой 35серии на полюсе 66 блока 2 управленияприводит к тому, что триггер 32 устанавливается в нулевое состояние.Это происходит в результате того,что импульс с полюса 66 проходит 4 О через элемент И 46 на нулевой входтриггера 32. Нулевое состояние триггера 32 Свидетельствует о том, чтоискомый путь найден и его ветви индицируются схемой 11 индикации. В 45этих моделях триггеры 3-5 одновременно находятся в единичном состоянии,а остальные триггеры - в нулевом.Индицируемый путь полностью удовлетворяет условию (2), т,е. пропуск О ная способность каждой ветви такогопути по первичному потоку удовлетворяет пути с наименьшей пропускнойспособностью, а пропускная способность по вторичному потоку этих ветвей больше или равна некоторой минимальной допустимой величине.При решении задачи оптимизациидвух взаимосвязанных потоков, основ"ным условием которой является усло15 О 652 17 вие (1), устройства работает анало,гично.Отличие заключается только в том, что среди ветвей разреза х - х выбирается ветвь, у которой шах 1 Ч, С величиной пропускной способности этой ветви сравнивают пропускные способности остальных ветвей оси. Таким образом, по окончании второго этапа все множество ветвей исследуемой сети разбивается на два подмножества. Первое подмножество ветвей содержит ветви, пропускные способности которых по первичному потоку удовлетворяют условию (3). Это обеспечивается тем, чта триггеры 5 и 6 в моделях, соответствующих этим ветвям, устанавливаются в единичное состояние. Достигается это с помощью сигнала, который 22 появляется на полюсе 71 блока 2 управления, Сигнал формируется тогда, когда снимается последний сигнал с многовходового элемента ИЛИ 62, что происходит в момент переполнения пас леднего счетчика 9 импульсов иэ моделей ветвей разреза. В результате появляется сигнал на выходе элемента НЕ 56, который через элементы И 42 и ИЛИ 57 поступает на полюс 71, Прохождение сигнала через элемент И ч 2 обеспечивает нулевое состояние триггера 31. При решении этой задачи триггер 31 должен находиться в нулевом состоянии.Появление сигнала на полюсе 7135 всех моделей ветвей разрешает проходить сигналам через элемент И 22 и устанавливает триггер 6 в единичное состояние.42Выполнение всех остальных операций и этапов работы устройства происходит аналогичным образом, т.е. как и при решении первой задачи. 45Формула изобретения Устройства для моделирования сетей, содержащее модели ветвей, количество которых равно количеству 52 ветвей в моделируемой сети, каждая из которых содержит с первого пачетвертый триггеры, первый счетчик импульсов, схему индикации, с первого по двенадцатый элементы И, с пер 55 ваго по третий элементы ИЛИ, блок управления, содержащий с первого по шестой триггеры, первый счетчик импульсов, с первого по девятый элемен 18ты И, элемент НЕ, первый и второй1 элементы ИЛИ и генератор импульсов, первый и второй многовходовые элементы ИЛИ, количество входов каждого из которых равно количеству моделей ветвей, каждый вход первого и второго мнаговхадовога элементд ИЛИ соединен соответственна с первым и вторым выходами соответствующей модели ветви, первый и второй полюсы моделей ветви соединяются в оответствии с гопалогией исследуемой сети, первый полюс модели ветви соединен с первыми входами второго, четвертого, пятого и шестого элементов И и выходами первого и третьего элементов И,второй полюс модели ветви соединен спервыми входами первого, третьегоседьмого и восьмого элементов И и с выходами второго и четвертого элементов И, второй вход четвертогоэлемента И соединен с первым входомодиннадцатого, вторыми входами третьего, шестого и восьмога элементов Ии прямым выходом третьего триггера,вход установки в 1 которого соединен с выходом переполнения первогосчетчика импульсов и первым входомдвенадцатого элемента И, второй входкатарог э соединен с первым входомдевятого элемента И и выходом первогс элемента ИЛИ, второй вход девятого элемента И соединен с инверснымвьгхадом третьего триггера, первыйвход первого элемента ИЛИ соединенс прямым выходом первого триггера,третьим выходом четвертого элемента Ии первым входом схемы индикации,второй вход которой соединен с вторым входом первого элемента ИЛИ, третьим входом третьего элемента И ипрямым выходам второго триггера, входустановки в "О" которого соединен свходом установки в "О" первого триггера, инверсный выход второго триггера соединен с вторым входомпятого элемента И, выкал которогосоединен с первым входом второго элемента ИЛИ, второй вход и выходкоторого соединены соответственно свыходом шестого элемента И и входомустановки в "1" первого триггера,инверсный выход которого соединен свторым входом седьмого элементаИ, выход которого соединен с первымвходом третьего элемента ИЛИ, второйвход и выход которого соединены соответственно с выходам восьмого элемен

Смотреть

Заявка

4257569, 05.06.1987

ИНСТИТУТ ПРОБЛЕМ МОДЕЛИРОВАНИЯ В ЭНЕРГЕТИКЕ АН УССР

ТАБУНЩИК ИВАН АНДРЕЕВИЧ, ТОНКАЛЬ ЕЛЕНА ВЛАДИМИРОВНА, ФЕДОТОВ НИКОЛАЙ ВАСИЛЬЕВИЧ

МПК / Метки

МПК: G06F 15/173

Метки: моделирования, сетей

Опубликовано: 07.09.1989

Код ссылки

<a href="https://patents.su/12-1506452-ustrojjstvo-dlya-modelirovaniya-setejj.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для моделирования сетей</a>

Похожие патенты