Устройство для оптимизации размещения центров радиальной сети

 

Союз Советских

Соцкалкст1ечвсккх

1ееслублик

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДВТЙЛЬСТВУ (1 1) 445046 (61) Зависимое от авт. свидетельства (22) Заявлено?О. 05» 72(21)7783873/I8-24 (51) М. Кл;

С 06 I5/20 с нрисоедииением заявки

Гаеударстеенный намнтет Сената Мнннстраа СССР

N леяак нзабретеннй н етнрытнй (32) Приоритет

Опубликовано30. 09. 74 Бюллетень № 36 дата опубликования описания I57I2, 74 (53) удк

68I.3 (088.8) (72) Авторы В.П. Пустобаев, Б.В.Железняков,Я. 1 .Некрасов иэобретения (71)з,„,„„„ Омский филиал Специального конструкторского бюро по автоматике в нефтехимии и нефтепереработке

{ 54) УСТРОЙСТВО ДЛН ОПТИМИЗАЦИИ РАЗМЕЩЕНИЯ

ЦЕНТРОВ РАДИАПЫ10И СЕТИ

2

Изобретение относится к об1пас-1 жит блок памяти, блоки выбора лити вычислительной техники и пред- ний связи с учетом ограничения по назначено для электронного модели- их длине, выполненные в виде перворования задачи оптимального разме- го и второго регистров, через перщения центров радиальной сети по 5 вую схему сравнения подключенных минимуму суммарной стоимости линии ко входам первой и второИ схем "Иет, связи. другие входы каждой из которых йзвестно устройство для опти- соединены с выходом первого регис1мизации размещения центров ради- ра, блоки сравнения стоимости, выальной сети, содержащее блок вычис- <р полненные в виде третьего и четверления стоимости суммарной линии того регистров, соединенных с треть связи и блок вычисления стоимости ей схемой "к", а через вторую схепо козффициенту заполнения. Одйа- му сРавнения — с первой схемой

ko круг задач, решаемых зтйм уст- и ЛИ, вторю схему иИЛИ" четверройством, ограничивается допусти- д тую схему р, причем один выход мостью длин линий связи. . блока памяти подключен ко входам

Цель изобретения - расширение первых регистров, а другой - ко класса решаемых задач, т.е. нахож- входам вторых регистров блоков выдение оптимальных центров радиаль- бора линий связи с учетом ограниченой сети по минимуму суммарной сто- 2р ний по их длине, один выход каждоимости линий связи с учетом огра- ro из которых соединен со входом ничения по их длине и коэффициен- блока памяти, а другой - со входатам заполнения технических средств ми блока вычисления стоимости сумнайденных центров. марной линии связи и блока вычисI С этой целью устройство содер-25 яения стоимости по коэффициенту за445046 полнения, выход каждого из которых соединен со входом соответствующего третьего регистра, а один из выходов каждой второй схемы сравнения через четвертую схему " " соединен с одним из входов второй схемы «ИЛИ«, выход которой подключен к входу блока памяти, а другой вход через третью схему сравнения соединен с выходом первых схем

«ИЛИ«.

Устройство позволяет получить решение рассматриваемой задачи с большой точностью и обеспечивает возможность автоматического обнару. жения количества центров радиальной сети.

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

Р

g=g8„"с, +Х вЂ”,":

1- pt,,/= -. т. р= -.. к где р — длина линии связи от -ой вершины радиальной сети -к - -ому цент ру — стоимость единицы длины линии связи от -ой вер шины.

С - стоимость технических средств;

P — количество классов приборов;

» — количество соединенных с j- -им центром вершин радиальной сети по клас—,р су Р

2 - количество вершин (датчиков класса Р, которое может быть подсоецинено техническим устройством этого же класса}

Если число всевозможных место. положений центров радиальной сети конечно, то

Ronm м

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

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

Приведенный итеррационный процесс реализуется в описываемом устройстве.

На чертеже изображена схема

1о устройства.

Оно состоит из регистров I-4, схем 5-7 сравнения, схем «И« 8-П, блока I2 вычисления стоимости суммарной линии связи, блока 13 вычис. ления стоимости по коэффициенту заполнения, схем "ИЛИ« 74 I5, блока 16 памяти. Регистры I, совместно со схемами 5 сравнения и схемами

2о "И" 8,9 образуют блоки выбора линий связи с учетом ограничений по их длине от выбранного радиального центра сети. Значения уставок по линиям связи зависят от классов

ы Р и записываются в регистр 2.

Число блоков для выбора линий связи с учетом ограничения по их длине от выбранного радиального центра сети зависит от числа классо> зо РРегистры 3,4 вместе со схемами 6 сравнения схемами «И« IQ u схемами «ИЛИ« Ь образуют блок сравнения стоимости и вместе со схемой 7 сравнения предназначены для сравнения по стоимости выбранного центра радиальной сети и лучшего из ранее рассмотренных. Значение стоимости по выбранному центру записано в регистр 3, а по луч-, 4о шему из ранее рассмотрейных — в ре; гистре 4. Схема «И« IU,Ï и схемы

«ИЛИ" I4,?5 образуют блок обработки результатов сравнения, входы которого соединены со схемами 6 7

45 сравнения, а выход - с блоком k6 памяти.

Для получения решения блок памяти заносит в регистры 2 уставки на длины линий связи и выбран5о ной из матрицы положений центра сети точки, а регистры 1 — длины линий связй.

Число регистров 1 и 2 зависит от числа исследуемых классов. Кобб,ды, записанные в этих регистрах, сравниваются в схеме 5 сравнения.

В зависимости от результата срав.нения, если длина линии связи больше или равна уставке, то код из регистра I через схему «И« 8 за писывается в блок памяти. Если по длине линии связи удовлетворяют уставке, то код из регистра I че44 046 рез схему "И" 9 поступает на блоки I2 и I3, где происходит вычисление суммарной стоимости линий связи и стоимости центров сети с учетом коэффициента заполнения ь соответственно.

Исследовайия суммарной стоимости по длине линий связи и стоимости центра сети по коэффициенту заполнения производятся параллель- >о

H0 °

С выхода схем I2,IH результаты вычисления записываются в регистры 3 и сравниваются с величинами, записанными в регистры 4.

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

Если в результате сравнения о выяснилось, что величины, записанные в регистрах 3, лучше, чем в регистрах 4, то сигнал со схем

6 сравнения, йоступает íà схем

"ИЛИ" I5 и через схему "ИЛИ" 14 воздействует на блок памяти, где происходит запоминание координат центра сети и вершин, с ним связанных. 8 то же время сигнал со схемы "ИЛИ" I4 воздействует на схему "И" I0 и происходит переза- зо пись кодов из регистров 3 в регистры 4. Если же при сравнении схема "M" П не пропустила сигнал, то результат со схем б сравнения через схему логики "ИЛИ" I5 посту- з5 пает на схему 7 сравнения. Если при сравнении выяснилось, что исследуемый центр лучше ранее найденного, то с выхода схемы 7 сравнения сигнал через схему "ИЛИ" ?4 воз- 4о действует на блок Iá памяти, где происходит запоминание координат центра сети и вершин, с ним связан ных. В случае плохого результата из матрицы положений центра сети 45 выбирается новая точка.

ПРЕДМЕТ ИЗОБРЕТЕНИЯ

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

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

Составитель Й» С6 3МКО3

ЦИНИПИ Государственного комитета Совета Мнннстров СССР по делам изобретений и открытий

Москва, ll3035, Раушская наб., 4

Предприятие «Патент», Москва, Г-59, Бережковская наб., 24