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

 

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств для решения задач на сетях. Цель изобретения - расширение функциональных возможностей-достигается тем, что в устройство, содержащее модели ветвей, содержащие с первого по четвертый триггеры, первый счетчик импульсов, схему индикации, с первого по двенадцатый элементы И, с первого по третий элементы ИЛИ и блок управления, содержащий с первого по шестой триггеры, первый счетчик импульсов, с первого по девятый элементы И, элемент НЕ, первый и второй элементы ИЛИ и генератор импульсов, дополнительно введены в модели ветвей пятый и шестой триггеры, второй счетчик импульсов, тринадцатый и четырнадцатый элементы И, четвертый и пятый элементы ИЛИ, а в блок управления введены с седьмого по девятый триггеры, второй счетчик импульсов, с десятого по четырнадцатый элементы ИЛИ и первый и второй многовходовые элементы ИЛИ. 2 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (II) 452 А1 (51)4 G 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИ4ЕТЕПЬСТВУ

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ

00 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4257569/24-24 (22) 05.06.87 (46) 07.09.89. Бюл. N - 33 (71) Институт проблем моделирования в энергетике АН УССР (72) И.А. Табунщик, Е.В. Тонкаль и Н.В. Федотов (53) 68 1 ° 325 (088.8) (56) Авторское свидетельство СССР

У 1138806, кл . G 06 F 15/20, 1985.

Авторское свидетельство СССР

Ф 1179365, кл. G 06 F 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЕТЕЙ (57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств для решения задач на сетях. Цель изобретения — расширение функциональных возможностей — достигается тем, что

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

Целью изобретения является расширение функциональных возможностей устройства эа счет решения задачи оптимизации двух взаимосвязанных потоков сети: определения такого пути между заданной парой вершин сети, у которого пропускная способность по первичному потоку удовлетворяет условию пути с наименьшей (наибольшей) пропускной способностью, а про2 в устройство, содержащее модели ветвей, содержащие с первого по четвертый триггеры, первый счетчик импульсов, схему индикации, с первого по двенадцатый элементы И, с первогп по третий элементы ИЛИ и блок управления, содержащий с первого по шестой триггеры, первый счетчик импульсов, с первого по девятый элементы И, элемент НЕ, первый и второй элементы ИЛИ. и генератор импульсов, дополнительно введены в модели ветвей пятый и шестой триггеры, второй счетчик импульсов, тринадцатый и четырнадцатый элементы И, четвертый и пятый элементы ИЛИ, а в блок управления введены с седьмого по девятый триггеры, второй счетчик импульсов, с десятого по четырнадцатый элементы ИЛИ и первый и второй многовходовые элементы ИЛИ. 2 ил. пускная способность по вторичному потоку больше (равна) некоторой минимал ьной допустимой величине .

На фиг. 1 показана функциональная схема модели ветви предлагаемого устройства; на фиг. 2 — функциональная схема блока управления.

Модель 1 ветви (фиг. 1) содержит с первого по шестой триггеры 3-8, первый 9 и второй 10 счетчики импульсов, схему 11 индикации, с первого по четырнадцатый элементы И 12-25, с первого по пятый элементы ИЛИ 2630.

Блок 2 управления (фиг. 2) содержит с первого по девятый триггеры

31-39, первый 40 и второй 41 счетчики импульсов, с первого по четырнадцатый элементы И 42-55, элемент

НЕ 56, с первого по четвертый элементы ИЛИ 57-60, генератор 61 импульсов.

Кроме того, устройство содержит первый 62 и второй 63 многовходовые элементы ИЛИ (фиг. 2). Число входов многовходовых элементов ИЛИ 62 и 63 соответствует числу моделей ветвей.

Устройство имеет полюсы 64-78, из которых полюсы 64 и 65 у модели 1 ветви служат для коммутации их между собой согласно конфигурации моделируемой сети. Полюсы 66 и 67 блока 2 управления служат соответствен- 20 но для подключения этого блока к полюсам 64 и 65 тех моделей 1 ветвей, между которыми отыскивается укаэанный путь. !стальные полюсы каждой модели ветви служат для подключения их к блоку управления, что обеспечивает синхронную работу всего устройства.

min(max(q, )(К хх еК), (3) (4) Исходными данными задачи оптимизации двух взаимосвязанных потоков является коммутация моделей 1 ветвей полюсами 64 и 65 между собой согласно конфигурации модепируемой сети, подключение полюсов 66 и 67 блока 2 управления к полюсам тех моделей ветвей, между которыми отыскивается требуемый путь. Кроме того, в счетчики 9 и 10 моделей ветвей соответственно заносят число импульсов, равное N-q u N-b;, а в счетчик 41 блока управления заносят число импульсов, равное N-Ъ, где N— емкость счетчиков 9 и 10 импульсов моделей 1 ветвей и счетчиков 40 и 41 блока 2 управления. !

Суть решения задачи оптимизации двух взаимосвязанных потоков заклю" чается в определении такого пути между заданной парой вершин сети, у которого пропускная способность Р по первичному и вторичному потокам удовлетворяет условиям:

Р, Ь,, Ь. Ъ Ь (1) ! j

6452 где Ь., — величина вторичного потока

1! по ветви (х; х );

Ь вЂ” заданная минимальная допусC тимая величина вторичного по5 тока каждой ветви сети;

q „ — величина первичного потока

Ij по ветви (х х,) . ! )

Согласно этим условиям процесс решения задачи на данном устройстве ! можно представить в виде трех этапов.

Первый этап состоит в выделении иэ всего множества ветвей сети таких ветвей, пропускная способность первичного потока которых удовлетворяет следующим условиям в зависимости от того, какое условие,(1) или (2) является основным для оптимизации:

minт min(q;. )

25 К (хх.еК где К вЂ” любой (S-t) разрез (на множестве ветвей), где S u соответственно начальная и

30 конечная вершины сети, между которыми определяется путь; х и х — i-я и j-я вершины сети

Ф

q.. — пропускная способность ветви

1J между х -й и х .-й вершинами. I !

35 Этот этап включает циклически повторяющиеся операции: нахождение (х;-х;) разреза из множества разрезов

К, выбор ветви разреза (х,.-х .) с

min(q,. ) или max tq; (зависйт от

40 выбранного условия (1) или (2)); выделение ветвей сети, у которых пропускная способность меньше или равна пропускной способности выбранной ветви разреза (согласно условиям (1)

45 и (3)) или больше или равна пропускной спесобности выбранной ветви разреза (согласно условиям (2) и (4)).

Вторая и третья операции выполняются устройством одновременно. После каждого цикла выполнения операций первого этапа число проверяемых ветвей сети уменьшается эа счет закорачивания между собой полюсов 64 и 65 моделей, которые удовлетворяют задан55 ному условию. Выполнение операций нерпервого этапа повторяется до тех пор, пока полюсы, между которыми отыскивается путь, не будут эакорочены (т,е. не совпадут).! 506-

Второй этап состоит в проверке выполнения условия (1) ипи (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. В резуль20 тате импульсы от генератора 61 проходят через элемент И 45. С выхода элемента И 45 эти импульсы поступают на вход элементов И 47, 49 и 50.

Через элементы И 47 и 50 импульсы не

25 проходят, так как нет разрешения на входы этих элементов с триггеров 33 и 34 (они находятся в пулевом состоянии), через элемент И4С! .мпульсы re нератора проходят и чер:- з элемент ИЛИ

5Н поступают на полюс 56 блока 2 управления. Одновременно = этим первый импульс из всей серии, к горая поступает ч рез элемент ШП1 58, устанав IHíàåт триггер >5 в ед:пичíQå состc!ÿ35 ние. Единично;" состояние триггера

36 выпае." ра,решение на вход элемента И 43, на другой ьхсд которого поступает разрешение единичного выхода триггера 3 1 (этот риггер на4р ходится в единичном с стоянии, так как основное условие оптимизации условие (2)).В результате на выходе элемента И 43 появляется игнал, который через элемент ИГПИ 57 поступает

45 на полюс 71 блока 2 управления.

С полюса 71 блока 2 управления сигнал поступает на вхо элемента И 22 всех моделей ветвей. что обеспечивает прохождение сигналов через этот элемент.

Импульсы с полюса 65 блока 2 управления поступают на полюсы 64 или

65 .оделей 1 ветвей, которые в результате коммутации этих полюсов между собой образуют вершину сети, из которой отыскивается путь, удовлетворяющий условию (2) °

В указанных моделях 1 ветвей (фиг. 1) импульсы с полюса 64 посту15064 52 лают на вх< л элементов И 13 и 15-17.

Через: >.ë ементы И 13, 15 и 17 импульсы не проходят, так как на других входах у пих нет разрешения. На всех входах элемента И 16 есть разрешение, и ээтому с выхода этого элемента импульсы через элемент ИЛИ 28 поступают на единичный вход триггера 3.

По первому импульсу из всей серии импульсов, поступивших в модель 1 ветви на полюс 64, триггер 3 устанавливается в единичное состояние. Все последующие импульсы подтверждают это состояние триггера 3. Аналогично, если импульсы поступают на полюс 65 модели 1 ветви, они проходят только через элементы И 18 и

ИЛИ 27 и устанавливают триггер ч в единичное состояние.

Единичное состояние триггера 3 или 4 выдает разрешение на вход элемента И 20 через элемент ИЛИ 26 и свидетельствует о том, что данная модель 1 ветви принадлежит выбранному разрезу (x; — х ) из множества разрезов К. Это соответствует первой операции первого этапа решения задачи.

Разрешение с выхода элемента И 20 поступает на полюс 70 модели 1 ветви.

Это возможно потому, что на другом входе элемента И 20 есть разрешение, снимаемое с нулевого выхода тригге— ра 5 °

С полюса 70 модели 1 ветви разрешение поступает на соответствующий вход 70 многовходово, о элемента ИЛИ

62 (фиг. 2) . Причем на входы 70 многовходового элемента ИЛИ 62 поступают разрешения только от тех моделеи

1 ветвей, триггеры .3 или 4 которых находятся в единич ном с остоя нии °

Выбор модели ветви, принадлежащей сформированному разрезу, с пропускной способностью первичного потока, равного min (q;; ), а -.акже моделей ветвей, пропускная способность первичного потока которых меньше или равна пропускной способности выбранной ветви, происходит по разрешению, которое появляется на вь:ходе многовходового элемента ИЛИ 62. Это разрешение поступает на вход элементов НЕ 56 и

И 44.

На выходе элемента НЕ 56 исчезает разрешение, которое поступает на вход элемента И 42. Однако другой вход элемента И 42 заблокирован единичным состоянием триггера 31 и, следовательно, изменение сигнала на полюсе 71 блока 2 управления не про5 исходит. Через элемент И 44 разрешение проходит, так как на другом его входе есть разрешение с нулевого выхода триггера 35, и поступает на единичный вход триггера 33. В результате триггер 33 устанавливается в единичное состояние. Единичное состояние триггера 33 запрещает прохождение импульсов через элементы И 49 и ИЛИ 58 на полюс 66 блока 2 управления и разрешает прохождение импульса генератора 61 с выхода элемента И 45 через элемент И 4 7. Единичное состояние триггера 33 свидетельствует о том, что устройство начинает выполнять вторую II третью операдии первого этапа. С выхода элемента И 47 импульсы генератора 61 поступают на полюс 69 и через элемент

ИЛИ 59 на вход счетчика 40 импульсов

25 до его переполнения.

В каждой модели 1 ветви импульсы с полюса 69 поступают на вход элеменга И 21 и счетчика 9 импульсов до его ереполнения. Импучьс переполне30 пия счетчика 9 модели ветви устанавливает триггер 5 в единичное состояние. Одновременно этот импульс через элемент И 23 поступает на полюс 76 тех моделей ветвей1 которые принадлежат выбранному разрезу. Кроме того, этот импульс через элемент

ИЛИ 29 поступает на нулевые входы триггеров 3 и 4.

40 Единичное состояние триггера 5 через элемент И 22 устанавливает триггер 6 в единичное состояние ° В этом случае триггер 5 остается в единичном состоянии, так как единичное

4 состояние триггера 6 запрещает прохождение очередного импульса с полюса 69 через элемент И 21 на нулевой вход триггера 5.

Импульс, поступивший на нулевые входы триггеров 3 и 4 с выхода счет50 чика 6 импульсов, устанавливает их в нулевое состояние, если один из них ранее был установлен в единичное состояние импульсами, которые поступили на полюс 64 или 65 модели ветви. В

55 результате установки триггеров 3 или

4 в нулевое состояние снимаются все сигналы с полюсов 70 многовходового элемента ИЛИ 62 и, следовательно, 15064 52

50 снимается сигнал с выхода этого эле° мента.

С полюса 76 модели 1 ветви импульс поступает на соответствующий этой модели ветви вход 76 многовходово5 го элемента ИЛИ 63 и, пройдя этот многовходовый элемент, поступает на нулевой вход триггера 36. В результате триггер 36 устанавливается в ну- !О левое состояние. Первый импульс, появившийся на одном из входов 76 многовходового элемента ИЛИ 63, определяет модель ветви, у которой наименьшая пропускная способность по первичному потоку min(q; и которая принадлежит выбранному разрезу (х — х ). Нулевое состояние триггера 36 сйимает разрешение с входа элемента

И 43 и, соответственно, через эле- 20 мент ИЛИ 57 с полюса 71 всех моделей 1 ветви.

Единичное состояние триггера 6 выдает разрешение на входы элементов

И 12 и 13, что обеспечивает закорачивание полюсов 64 и 65 модели ветви.

Закорачивание полюсов 64 и 65 модели ветви исключает ветвь иэ дальнейших проверок, которые выполняются на первом этапе. Таким образом, в моделях 1 ветвей сети, у которых пропускная способность меньше или равна пропускной способности модели ветви разреза, триггеры 5 и 6 устанавливаются в единичное состояние, триггеры 3 и 4 — в нулевое и их полюсы 64 и 65 закорачиваются. Это происходит потому, что в моделях 1 ветвей, у которых импульс переполнения счетчика 9, появившийся после

40 того, как будет снято разрешение с полюса 71 и входа элемента И 22, триггер 5 устанавливается в единичное состояние, а затем этот триггер устанавливается в нулевое состоя- 45 ние очередным импульсом, поступившим на полюс 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 управления свидетельствует об окончании выполнения устройства второй и третьей операций первого этапа. К этому моменту все множество ветвей моделируемой сети разбито на два подмножества. Одно подмножество содержит ветви, пропускная способность по первичному потоку q., 1 которых удовлетворяет условию (4), и в соответствующих им моделях 1 ветвей триггера 5 и 6 находятся в единичном состоянии. Другое подмножество содержит ветви с пропускными способностями, которые не удовлетворяют условию (4), и их триггеры 5 и 6 находятся в нулевом состоянии. Эти модели в процессе выполнения следующего этапа работы устройства не участвуют. Кроме того, к этому моменту в счетчиках 9 всех моделей 1 ветвей восстанавливается информация об их пропускной способности по первичному потоку, т.е. происходит регенерация.

Роль регенерационного счетчика для счетчиков 9 всех моделей 1 ветвей выполняет счетчик 40 импульсов блока

2 управления, который начинает счет с "0" и его емкость равна N. Счетчики 9 всех моделей 1 ветвей начинают счет с N-q

1)

Импульс с полюса 67 в блоке 2 управления поступает на вход элементов

И 54 и 55. Через элемент И 55 этот импульс не проходит, так как триггер

38 находится в нулевом состоянии, а через элемент И 54 импульс проходит на единичный вход триггера 37. В результате этот триггер устанавливается в единичное состояние. Единичное состояние триггера 37 выдает разрешение на вход элементов И 51 и 53 и

15064 52

12 си мает ра. ðåøåíèñ с входа элемента 11 45. Единичное состояние триггера 37 свидетельствует о том, что устройство íà(HHë T выполнять операци 1 второго этапа. При этом импульсы генератора 61 проходят через элемент

H 51. Далее они поступают на полюс 75 и чере элемент ИЛ1 59 на вход счетчика 40. С полюса 75 эти импульсы по% ступают в каждой модели 1 ветви на вход элемента И 25. Кроме того, импульсы с выхода элемента И 51 поступают на вход счетчик» 41.

В каждой модели 1 ветви .=ти импульсы проходят череэ элемент И 25 только в тех моделях ветвей, триггер

6 которых находится в единичном состоянии, и далее поступают на вход счетчика 10 импульсов до его переполнения. Импульс переполнения счетчика 10 поступает на вход элемента

И 24. Через этот элемент импульс переполнения счетчика 10 может пройти в том случае, если триггер 8 находится в нулевом состоянии. Состояние триггеров 8 всех моделей ветвей определяется работой счетчика 41 импульсов блока 2 управления. Импульс переполнения счетчика 41 поступает на полюс 73 всех моделей 1 ветвей и устанавливает триггер 8 в еЯ ничное состояние, что запрещает прохождение импульсов переполнения счетчика 10 через элемент И 24.

Единичное состояние триггера 7 в моделях ветвей свидетельствует о том, что пропускная способность по вторичному потоку в данных моделях не удовлетворяет условию (2), т.е. b (b, Такие модели ветвей и, о следовательно, соответствующие им ветви моделируемой сети из дальнейшего процесса решения задачи исключаются. Исключение моделей ветвей иэ дальнейшего процесса решения задачи осуществляется за счет съема разрешения с входов элементов И 1219 в модели ветви, -)то запрещает прохождение си) налов с полюса 64 на полюс 65, и наоборот, через модель ветви.

Выполнение второго этапа работы устройства продолжается до момента появления импульса переполнения счетчика 40 импульсов блока 2 управления (фиг. 2). К тому моменту все подмножество ветвей, которое выбрано на первом этапе и пропускная способ50

Кроме того, этот импульс переполне— ния счетчика 40 поступает на вход генератоpa 61 импульсов и, соответственно, на единичный вход триггера 38 через элемент И 53 и на нулевой вход триггера 37. В результате триггер

38 устанавливается в единичное состояние, а триггер 37 — в нулевое.

Иулевое состояние триггера 37 снимает разрешение с выхода элемента И

51, что прекращает поступление импульсов генератора 61 на полюсы 69 ность 11о первичному потоку которых удовлетворяет условию (4), еще раз— бина ется на два подмножества. Одно подмножество содержит ветви моделируемой сети, которые полностью удовлетворяют условию (2), т.е. их пропускные способности по первичному потоку и по вторичному соответствуют требованиям, которые предъявляются к искомому пути. В соответствующих этим ветвям моделях триггеры 5 и 6 должны находиться в единичном состоянии, а триггер 7 — в нулевом. Для другого подмножества пропускные способности ветвей по первичному потоку удовлетворяют условию (4).и, следовательно, условию (2), а по вторичному потоку их пропускные способности не

2р удовлетворяют условию (2), т,е. условие (2) полностью не выполняется. В соответствующих этим ветвям моделях триггеры 5 и 6 находятся в единичном состоянии, а также в единичном состоянии находится триггер 7.

)1роверка существования пути в сети между заданными вершинами, состоящего иэ ветвей, которые удовлетворяют полностью условию (2), устройство производит следующим обра30 зом. Импульс переполнения счетчика

40 импульсов через элемент ИЛИ 58 поступает на полюс 66 блока управления,. К этому моменту в счетчике 10 всех моделей 1 ветвей и в счетчике

5 41 импульсов блока 2 управления восстанавливается информация о Ь; и, 1) соответственно, о b . Роль регенерационного счетчика в этом случае, так же как и в предыдущем, выполняет счетчик 40 импульсов блока 2 управления, который начинает счет с "0" и его емкость равна N. Счетчики 10 всех моделей ветвей и счетчик 4 1 блока управления начинают счет соответственно с N-b;, и N-b,.! 506452

Единичное состояние триггера 35 снимает разрешение с полюсов 68 всех моделей 1 ветвей и выдает разрешение на полюсы 72. В результате в каждой модели ветви блокируются элементы

И 16 и 18, а на входе элемента ИЛИ 30 появляется сигнал, который устанавливает триггер 6 в нулевое состояц ие. Нулевое состояние триггера 6 снимает разрешение с входов элементов И 12 и 13, чем блокирует входы

13 и 75 и входы счетчиков 40 и 41 б гока

2 управления.

Единичное состояние триггера 38 выдает разрешение на вход элементов

И 52 и 55, что обеспечивает прохожде5 цие сигналов через эти э:гементы. Одновременно с этим импульс переполнения счетчика 40, поступивший ца полюс

66 блока управления, оггять поступает на полюс 64 или 65 моделей 1 ветвей, который в результате коммутации этих полюсов между собой c,áðà з ует нершиггу сети, из которой отыскивается путь, удовлетворяющии полностью условию (2). В моделях ветвей этот импульс с полюса 64 поступает через элемент И 13

13 на полюс 65. Аналогично, если этот импульс поступает на полюс 65, то он проходит через элемент И 12 на полюс 64 .

Таким образом, распространяясь по сети с полюса 64 на полюс 65 или с полюса 65 на полюс 64 от модели к модели, этот импульс появляется на полюсе 67 блока управления. Распространение импульсов переполнения счетчика 40 на втором этапе возможно только по тем моделям ветвей, триггеры 5 и 6 которых находятся в единичном30 состоянии, а триггер 7 — в нулевом.

Появление импульса на полюсе 67 блока 2 управления свидетельствует о том, что путь, пропускная способность ветвей которого полностью удовлегворяет условию (2), найден и устройство в этом случае переходит к выполнению заключительного этапа работы выделению ветвей искомого пути. В противном случае, если импульс ца полюсе 67 не появляется, что свидетель40 ствует об отсутствии искомого пути, устройство переходит опять к выполнению операций первого этапа, и весь процесс работы устройства повторится аналогично описанному выше.

Переход устройства к выполнению операций первого этапа происходит слсдующим образом.

По импульсу переполнения счетчи50 ка 40 блока 2 управления, который поступает на вход генератора 61 импульсов в конце второго этапа работы устройства, генератор импульсов выдает импульс, сдвинутый относительно входного, на вход элемента И 52.

Этот импульс проходит через элемент

И 52 и поступает на нулевой вход триггера 38, на вход элемента ИЛИ 60 и ца полюс 74 всех моделей 1 ветвей

При этом в каждой модели ветви импульс с полюса 74 поступает на нулевой вход триггера 8 и через элементы 1ШИ 30 и 29 на нулевые вхсды триггеров 6, 3 и 4, устанавливая эти триггеры в нулевое состояние. Одновременно с этим устанавливается в нуленое состояние триггер 38, что запрещает прохождение дальнейших сигналов через элементы И 52 и 55, и в нулевое состояние триггер 33. Нулевое состоягггге триггера 33 разрешает прохождение импульсов генератора 61 через элементы И 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 через эле1п менты И 19 и ИЛИ 27 поступают на единичный вход триггера 4. По первому импульсу из всей этой серии импульсов триггер 4 устанавливается в единичное состояние, что обеспечивает прохождение остальных импульсов этой серии с полюса 65 через элемент И 14 на полюс 64 модели ветви. Таким образом, импульсы, распространяясь по сети с полюса 65 на по20 люс 64 от модели к модели, устанавливают триггер 4 в единичное состояние и появляются на полюсе 66 блока

2 управления, Следует заметить, что распространение импульсов с полюса 67

25 блока управления через модели ветвей на полюс 66 происходит только по тем моделям ветвей, у которых триггеры 5 и 7 находятся соответственно в единичном и нулевом состоянии. Эти моде3р ли соответству.от ветвям, пропускные способности которых полностью удовлетворяют условию (2).

15 этих элементов и не позволяет проходить сигналам через них.

Одновременно с этим, нулевое состояние триггера 33 разрешает прохождение импульсов генератора 61 через элементы И 49 и ИЛИ 58 на полюс 66 блока 2 управления. Эти импульсы генератора 61 с полюса 66 поступают на полюсы 64 моделей ветвей, которые этим полюсом подключены к полюсу 66 блока управления и образуют вершину, из которой отыскивается необходимый путь, В модели ветви импульсы с полюса

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), т,е. пропуск5О ная способность каждой ветви такого пути по первичному потоку удовлетворяет пути с наименьшей пропускной способностью, а пропускная способность по вторичному потоку этих ветвей больше или равна некоторой мини55 мальной допустимой величине.

При решении задачи оптимизации двух взаимосвязанных потоков, основным условием которой является усло1506452

17 вие (1), устройства работает анало,гично.

Отличие заключается только в том, что среди ветвей разреза х — х выI бирается ветвь, у которой max

С величиной пропускной сгасобнасти этой ветви сравнивают пропускные способности остальных ветвей оси. Таким образом, по окончании второго этапа все множество ветвей исследуемой сети разбивается на два подмножества ° Первое подмножество ветвей содержит ветви, пропускные способности которых по первичному потоку удовлетворяют условию (3). Это обеспечивается тем, чта триггеры 5 и 6 в моделях, соответствующих этим ветвям, устанавливаются в единичное состояние. Достигается это с помощью сигнала, который 20 появляется на полюсе 71 блока 2 управления. Сигнал формируется тогда, когда снимается последний сигнал с многовходового элемента ИЛИ 62, ч-,о происходит в момент переполнения пас- 25 леднего счетчика 9 импульсов иэ моделей ветвей разреза. В результате появляется сигнал на выходе элемента

НЕ 56, который через элементы И 42 и

ИПИ 57 поступает на полюс 71. Прохождение сигнала через элемент И 42 обеспечивает нулевое состояние триггера

31. При решении этой задачи триггер

31 должен находиться в нулевом состоянии, Появление сигнала на полюсе 71

35 всех моделей ветвей разрешает проходить сигналам через элемент И 22 и устанавливает триггер 6 в единичное состояние.

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

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

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

1 элементы ИЛИ и генератор импульсов, первый и второй многовходовые элементы ИЛИ, количество входов каждого из которых равно количеству моделей ветвей, каждый вход первого и второго мнаговхадовога элементд ИЛИ соедиffef» соответственна с первым и вторым выходами соответствующей модели ветви, первый и второй полюсы моделей ветви соединяются в оответствии с гопалогией исследуемой сети, первый полюс модели ветви соединен с первыми входами второго, четвертого, пятого и шестого элементов И и выходами первого и третьего элементов И, . торой полюс модели ветви соединен с первыми входами первого, третьего седьмого и восьмого элементов И и с выходами второго и четвертого элементов И, второй вход четвертого элемента И соединен с первым входом одиннадцатого, вторыми входами третьег0, шестого и восьмога элементов И и прямым выходом третьего триггера, вход установки в "1" которого соединен с выхадом переполнения первого с гетчика импульсов и »ервым входом две»адцатаго элемента И, второй вход катарог э соединен с первым входом девятого элемента И и выходом первогс элемента K(I(второй вход девятого элемента И соединен с инверсным вьгхс дом третьего триггера, первый вход пер ваго эл еме нта ИЛИ соединен с прямым выходом первсгго триггера, третьим выходом четвертого элемента И и первым входом схемы индикации, второй вход которой соединен с вторым входом первого элемента ИЛИ, третьим входом третьего элемента И и прямым выходом второго триггера, вход установки в "О" которого соединен с входом установки в "О" первого триггера, инверсный выход второго триггера соединен с вторым входом пятого элемента И, вьгхал которого соединен с первым входом второго элемента ИЛИ, второй вхсд If вь.хад которого соединены соответственна с выходом шестого элемента И и входом установки в "1" первого триггера, инверсный выход котораг а соединен с вторым входом седьмого элемента

И, выход которого соединен с первг, входом третьего элемента ИЛИ, второй вход и выход которого соединены соотВрТс TBBHHo с вьгхадам восьмого элемен1506452

55 та И II вх >дом устац цки в "1" второго триггс .ра, выход установки в 0" третьего триггера соедицс ц с выходом десятого элемента И, первый и вторс>й входы кс>торс>го соединены сс>отцетстценно со счетным входом ilk>ðâàãо счетчика импульсов и инверсным выходом четвертого триггера, прямой выход которого соединен с вторыми входами первого и второго элементов И, нход устанонки в "1" гетвертог о триггера соединен с выходом одиннадцатого эле— мента И, второй вход которого соединен с третьим входом модели ветви, вьгход девятого элемента И является вторым выходом модели ветви, третий вход всех моделей ветвей соединен с третьим выходом блока управления, н блоке управления третьим выходом ! является выход первого элемента HsiH, первый и второй вхс>ды которого соединены соответственно с выходами пер— ного и второго элементов И, первый вход второго элем нта И соединен с прямым входом шестого триггера, вход установки в 0> к торого с >единец с выходом второго мно>;. вхоцовог.> элемента ИЛИ, вход ус;ацонки в единицу шестого триггера соединен " выходом второго элемента 1!ЛИ и первым входом пятого элемента И, выход к >торого

1! >>I соединен с входом установки в О второго триггера, прямой выход которого соединен с первым н>:одом четвертого элемента И, второй вход и выход которого соединены соответстн HH0 с первым выходом генератора импульсон и первыми входами шестого, восьмого, девятого элементов И, второй вход шестого элемента И соединец с прямым выходом триггера, инверсный выход которого соединен с вторым входом восьмого элемента И, вь»сод которого соедин н с первым входом второго элемента ИЛИ, втор. и вхоп котсрого соединен с»ьжолом переполнения перво-. гс счетчика импу."ьсон, вход установки в "1" третьего триггера соединен с выходом трегьего э»емента И, первый вход которого соединен с ныхолом второго элемента ИЛИ и входом элемента НЕ, выход которого соединен r. первым входом первого элемента И, второй вход которогv соединен с инверсным вьгходом первого триггера, прямой выход которого соединен с вторым входом второго элемента И, вы— ход седьмогo элемента И соединен с входом установки в "1" четвертого григгера, прямой выход которого соединен с вторыми входами пятого и девятого элементов И, первый вход седьмого элемента И соединен с входом установки в "1" пятого триггера, прямой выход которого соединен с вторым входом седьмого элемента И и третьим входом девятого элемента

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

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

ИЛИ, третьи входы первого и второго элементов И соединены с четвертыми входами третьего и четвертого элементов И и соединены с четвертыми входами с пятого по восьмой элементов

И и инверсным выходом пятого триггера, вход установки в "1" которого соединен с выходом тринадцатого элемента И, первый и второй входы которого соединены соответственйо с выходом переполнения второго счетчика импуль1506452

2I

40 сов и инверсным выходом шестого триггера, входы установки в "1" и "0" которого являются пятым и шестым входами модели ветви, причем последний соединен с первыми входами четверто— го и пятого элементов ИЛИ, второй вход четвертого элемента ИЛИ соединен с первым входом двенадцатого элемента

И, выход которого является первым выходом модели ветви, выход четвертого элемента ИЛИ соединен с входом установки в "0" второго триггера, инверсный выход третьего триггера соединен с вторым входом девятого элемента И, выход которого является вторым выходом модели ветви, вторые входы пятого элемента ИЛИ и одиннадцатого элемента И являются соответственно четвертым и третьим выходами модели ветви, выход пятого элемента ИЛИ соединен с входом установки в "0" четвертого триггера, прямой выход которого соединен с вторыми входами первого и четырнадцатого элементов И, счетный вход второго счетчика соединен с выходом четырнадцатого элемента И, первый вход которого является седьмым входом модели ветви, с третьего по седьмой входы всех моделей ветвей соединены с соответствующими выходами блока управления, в который дополнительно введены с седьмого по девятый триггеры, второй счетчик импульсов, с девятого по четырнадцатый элементы

ИЛИ, второй выход генератора импульсов соединен с первым входом одиннадцатого элемента И, второй и третий входы и выход которого соединены соответственно с прямым и инверсным выходом восьмого и девятого триггера и первым входом четвертого элемента

ИЛИ, второй вход которого соединен с прямыми входами пятого и выходом девятаго триггеров и выходом четырнад. цатого элемента И, первый и второй входы которого соединены соответственно с прямым выходом восьмого триггера и выходом девятого элемента И, второй вход и выход которого соединены соответственно с инверсным выходом восьмого триггера и входом установки в "1" седьмого триггера, вход установки в "0" которого соединен с выходом переполнения первого счетчика импульсов, входом генератора импульсов и первым входом двенадцатого элемента И, второй вход которого соединен с входом десятого элеменга 11 и прямым выходом седьмого триггера, инверсный выход которого соединен с третьими входами второго и четвертого элементов И, первый выход генератора импульсов соединен с вторым входам десятого элемента И, выход которого является седьмым выходом блока управления и соединен с первым входом третьего элемента

ИЛИ и счетным входом второго счетчика импульсов, выход переполнения которого является пятым выходом блока упра вл ения, вт арий вход и выход третьего элемента ИЛИ соединены соответственно с выходом шестого элемента

И и счетным входом первого счетчика импульсов, входы установки в "1" и

"0" третьего триггера соединены соответственно с выходами третьего элемента И и четвертого элемента ИЛИ, входы установки в " 1" и "0" восьмого триггера соединены соответственно с выходами двенадцатого и одиннадцатого элементов И, причем выход последнего является шестым выходом блока управления, прямые выходы пятого и четвертого триггеров являются четвертым и восьмым выходами блока управления.

15064 52

Фиг, 1

Тираж 668

Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101

Редактор В. Петраш

Заказ 5440/51 бб 77% б! 11 бб

Фиг.2

Составитель О. Гречухнна

Техред М,Моргентал Корректор В. Кабаций