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

гв":воюз Советскихоциалиствечвсккхреслублик ОП ИСАН ИЗОБРЕТЕН 11) 4450 К АВТОРСКОМУ СВИДВТ 1 вЛЬСТВ 1) Зависимое от2) Заявлено 10. авт. свидетельства5. 72(21783873/нием заявки 24 (51) Кл; 6 0 с нрисоедииПриоритет асударственньа нвинтетСвввтв Мнннстрав СССРвв деяак нзабретеевн вткрытнй Опубликовано 30. 09. 74 Бюллетень36 дата одубликования одисания 15712, 74 53) удк681.3 (088.8(72) Авторы изобретения 71) Заявитель ОМСКИМИ Филиал Специального конструкторского бюро о автоматике в нефтехимии и нефтеперераб(54) УСТРОЙСТВО ДЛЯ ОПТИМИЗ1 ДНТРОВ РАЗК 1Изобретение относится к об)ласти вычислительной техники и предназначено для электронного моделирования задачи оптимального размещения центров радиальной сети по минимуму суммарной стоимости линии связи.йзвестно устройство для оптимизации размещения центров радиальной сети, содержащее блок вычисления стоимости суммарной линии связи и блок вычисления стоимости по коэффициенту заполнения. Одйако круг задач, решаемых этйм устройством, ограничивается допустиМостью длин линиИ связи.Цель изобретения - расширение класса решаемых задач, т,е. нахождение оптимальных центров радиальной сети по минимуму суммарной стоимости линий связи с учетом ограничения по их длине и коэффициентам заполнения технических средств найденных центров.С этой целью устройство содержит блок памяти, олоки выборалиний связи с учетом ограничения поих длине, выполненные в виде первого и второго регистров, через пер вую схему сравнения подключенныхко входам первой и второИ схем нИвт,другие входы каждой из которыхсоединены с выходом первого регис 1- ра, блоки сравнения стоимости, вы 1 о полненные в виде третьего и четвертого регистров, соединенных с третьей схемой нИ", а через вторую схемч сравнения - с первой схемойиИЛИв, вторую схему ФИЛИ" четвер тую схему И", причем один выходблока памяти йодключен ко входампервых регистров, а другой - ковходам вторых регистров блоков выбора линий связи с учетом ограниче 2 о ний до их длине, один выход каждого из которых соединен со входомблока памяти, а другой - со входами блока вычйсления стоимости суммарной линии связи и блока нычис Бяения стоимости по коэффициенту за445046 -полнения, выход каждого из которыхсоединен со входом соответствующего третьего регистра, а один из выходов каждой второй схемы сравнения через четвертую схему ф " соединен с одним из входов второй схе.мы "ИЛИ", выход которой подключенк входу блока памяти, а другойвход через третью схему сравнениясоединен с выходом первых схемфИЛИ" .Устройство позволяет получитьрешение рассматриваемой задачи сбольшой точностью и обеспечиваетвозможность автоматического обнаружения количества центров радиальной сети.Задача оптимального расположения центров радиальной сети состоит в обнаружении таких центров,которые минимизируют функционалРЯ-Х 8, +Е-,":1- 37,тр= Кгде р - длина линии связи от-ой вершины радиальной сети к . -ому центРу- стоимость единицы длинылинии связи от-ой вершины.С - стоимость техническихсредств;Р - количество классов приборов;М, - количество соединенныхс-им центром вершинрадиальной сети по клас - ,р су РЯ - количество вершин датчиков класса Р, котороеможет быть подсоецинено техническим устройством этого же класса)Если число всевозможных местоположений центров радиальной сетиконечно, тоЙОФРп - З миФДля решения задачи применяется метод последовательного перебора всевозможных положений центроврадиальной сети. В зависимости оттого, что значейие 3 от точки кточно меняется, то нужно запоминать значение йаимоньшегоЖ из двухсравниваемых. На последнем шаге получено такое местоположение центрасети, в котором значение л = мин.Далее, вновь используя метод последовательного перебора, рассмат 9ривается центр, с которым соединяются вершины сети, не задействованные в предыдущих циклах, и такдалее до тех пор, пока не останет ся ни одной изолйрованной вершины.Приведенный итеррационныйпроцесс реализуется в описываемомустройстве.На чертеже изображена схема 1 о устройства.Оно состоит из регистров 1-4,схем 5-7 сравнения, схем фИ" 8-11,блока 12 вычисления стоимости суммарной линии связи, блока 13 вычисления стоимости по коэфйициентузаполнения, схем "ИЛИ" 14 15, блока 16 памяти. Регистры 1,1 совмест.но со схемами 5 сравнения и схемами 2 о ИИ" 8,9 образуют блоки выбора линий связи с учетом ограничениИ поих длине от выбранного радиального центра сети. Значения уставокпо линиям связи зависят от классов 25 Р и записываются в регистр 2,Число блоков для выбора линийсвязи с учетом ограничения по ихдлине от выбранного радиальногоцентра сети зависит от числа классово зо РРегистры 3,4 вместе со схемами б сравнения схемами "И" 10 исхемами "ИЛИ" 15 образуют блоксравнения стоимости и вместе сосхемой 7 сравнения предназначеныдля сравнения по стоимости выбранного центра радиальной сети и лучшего из ранее рассмотренных, Значение стоимости по выбранному центру записано в регистр 3, а по луч-, 4 о шему из ранее рассмотрейных - в ре,гистре 4. Схема ЧР 10,11 и схемыиИЛИ" 14,15 образуют блок обработки результатов сравнения, входыкоторого соединены со схемами б 7 45 сравнения, а выход - с блоком 16памяти.Для получения решения блокпамяти заносит в регистры 2 уставки на длины линий связи и выбран 5 о ной из матрицы положений центрасети точки, а регистры 1 - длинылиний связй.Число регистров 1 и 2 зависитот числа исследуемых классов. Ко,ды, записанные в этих регистрах,сравниваются в схеме 5 сравнения.В зависимости от результата срав,нения, если длина линии связибольше или равна уставке, то кодиз регистра 1 через схему "Ип 8 записывается в блок памяти. Если подлине линии связи удовлетворяютуставке, то код из регистра 1 че 44 ь 046 рез схему "И" 9 поступает на блоки 12 и 13, где происходит вычисление суммарной стоимости линий связи и стоимости центров сети с учетом коэффициента заполнения 5 соответственно.Исследовайия суммарной стоимости по длине линий связи и стоимости центра сети по коэффициенту заполнения производятся параллель о ноС выхода схем 12,1 З результаты вычисления записываются в регистры 3 и сравниваются с величинами, записанными в регистры 4. 15 В начале итеррационного процесса в регистры 4 записываются заведомо худшие величины стоимости.Если в результате сравнения о выяснилось, что величины, записанные в регистрах 3, лучше, чем в регистрах 4, то сигнал со схем б сравнения, йоступает на схему "ИЛИф 15 и через схему "ИЛИ" 14 воздействует на блок памяти, где происходит запоминание координат центра сети и вершин, с ним связанных, 0 то же время сигнал со схемы "ИЛИ" 14 воздействует на схему "И" 10 и происходит переза- зо пись кодов из регистров 3 в регистры 4. Если же при сравнении схема ЧР П не пропустила сигнал, то результат со схем б сравнения через схему логики "ИЛИ" 15 посту- з 5 пает на схему 7 сравнения. Если при сравнении выяснилось, что исследуемый центр лучше ранее найденного, то с выхода схемы 7 сравнения сигнал через схему "ИЛИф 14 воз о действует на блок 16 памяти, где происходит запоминание координат центра сети и вершин, с ним связан ных. В случае плохого результата из матрицы положений центра сети 45 выбирается новая точка. ПРЕДЯЕТ ИЗОБРЕТЕНИЯУстройство для оптимазации размещения центров радиальной сети, содержащее блок вычисления стоимости суммарной линии связи и блок вычисления стоимости по коэффициенту заполнения, отличающееся тем, что, с целы расширения класса решаемых задач, оно содержит блок памяти, блоки выбора линий связи с учетом ограничениИ по их длине, выполненные в виде первого и второго регистров, через первую схему сравнения йодключенных ко входам первой и второй схем "И", другие входы каждой из которых соединены с выходом первого регистра, блоки сравнения стоимости, выполненные в виде третьего и четвертого регистров соединенных с третьей схемар Ф , а через вторую схему сравнения - с первой схемой фИЛ", вторую схему "ИЛИ" и четвертую схему У", причем один выход блока памяти подключен к входам первых регистров, а другой - ко входам вторых регистров блока выбора линий связи с учетом ограничений по их длине, один выход каждого из которых соединен со входом блока памяти, а другой -со входами блока вычисления стоимости суммарной линии связи и блока вычисления стоимости по коэффициенту заполнения, выход каждого из которых соединей со входом соответствующего третьего регистра, а один из выходов каждой второй схемы сравнения через четвер тую схему "И" соединен с одним из входов второй схемы,"ИЛИ", выход которой подключен ко входу блока памяти, а другой вход через третью схему сравнения соединен с выходами первых схем "ИЛИ".Составитель Й С 63 МЕОИПИ Государственного комитета Совета Министров СССРпо делам изобретеиий и открытийМосква, 113035, Раушская наб 4тэ, Москва, Г.Я, Бережковская наб., 24Предприяти