Вычислительное устройство для решения задачи выправки железнодорожного пути

Союз Соввтскня Социалистических Республик(22) Заявлено 1801,78 (21) 2569054/18-24 (51)М. КЛ. с присоединением заявки НоЯ 06 Р 15/20 ГосударетаеяяыА яомятет СССР яо делам язобретеяяА я отярытяАОпубликовано 3011 Я 1, бюллетень И 944 Дата опубликования описания 301 ,81 2) Авторыизобретени ко и;Э.З.Трайнив В.Вл) Заявите ена Левина институт кибернети(,5 ИСЛИТЕЛЬНОЕ УСТРОЙСТВОЗАДАЧИ ВЫПРАВКИ ЖЕЛЕЗНПУТИ Я РЕШЕНИЯРОЖНОГО Изобретение относится к вычислительной технике н может бытьиспользовано при построении специализированных вычислительных машин для ре" шввия задач нелинейного и линейного программирования с двусторонними ограничениями на переменные, преимущественно задач расчета оптимальных микропланов железнодорожного пути с целью автоматического управления работой путерехтовочвых комплексов (на пример ВПО) в реальном масштабе времени выполнения процесса рихтовки ж.-д, пути.Задача определения оптимального микроплана железнодорожного пути является спецнфической задачей нелинейного программирования с двусторонними ограничениями на зависиьеее и на независимые переменные. Порядок задачи т =10-15 обусловлен количеством точек деления пути через 10 м) в пределах расчетного микроплана пути длиной 100-150 и. Число точек микроплана обеспечивает необходимую точность решения, что позволяет заменить громоздкий расчет микроплана пути длиной до 4 км расчетами множества мнкропланов длиной по 150 м. По основному авт,св. я 802967 азвестио вычислительное устройство дпя решения задачи выправки железнодорожного пути, содержадее сдвигащдий регистр штрафов, второй триггер, два элемента И, второй элемент ИЛИ, причем вход второго триггера и первый вход сдвигакщего регистра штрафов соединены с выходом блока управления, 10 второй и третий выходы арифметического блока соединены с первыми вхо дами первого и второго элементов И, выходы которых через второй элемент ИЛИ соединены со входом блока управ ления и через сдвигакщий регистрштрафов - со вторым входом дополнительного блокапамяти, выходы второго триггера соединены со вторыми входами двух элементов И 11.20 Однако известное устройство характеризуется недостаточным быстродействием.Цель изобретения - повышениебыстродействия устройства.25 Поставленная цель достигаетсятем, что в устройство дополнительно введены счетчик итераций, триггер фиксации штрафной функции, третий элемент И, третий элемент ИЛИ, при чем первый вход триггера фиксацииштрафной Функции соединен с выходом второго элемента ИЛИ, нулевой выход . триггера фиксации штрафной функции через последовательно соединенные третьи элементы И, ИЛИ соединен со вторым входам блока управления, выход которого соединен со вторым входом триггера фиксации штрафной Функции и о входами третьего элемента И и счетчика итераций, выходы которого соеди-. нены со входом третьего элемента ИЛИ и вторым входом регистра ограничения невязок и со вторым входом регистра- маски.На чертеже представлена блок-схема предлагаемого устройства.устройство содержит арифметический 15 блок 1, блок 2 памяти, блок 3 ввода-. вывода, блок 4 управления, регистр 5 ограничения невязок, сдвиговый регистр 7 маски, группу элементов И 8, элементы ИЛИ 9-11, дополнительный 20 блок 12 памяти, сдвигающий регистр 13 штрафов, элементы И 14-16, триггеры17 и 18, триггер 19 фиксации штрафной Функции счетчик 20 итераций.Устройство работает следукщим об- Я 5 разом.В процессе ввода в .ячейки блока 2 из блока 3 заносится информация об ограничениях на сдвиги в соответствующих.точках деления пути и о свободных членах неравенств решаемой системы (вычисленных во время ввода как Функции от значений стрел кривизны в соответствующих точках деления пути) . В регистр 5 заносится код, равный абсолютной величине ограничения. М, на невязки Х, , В регистр 7 заносится код, содержащий единицы во всех разрядаж, кроме фиксированного числа младших разрядов, куда заносят нули. Число нулевых разрядов соответствует 40 ближайшему к 1 числу А =2", причем 1 (Таким образом, регистр 7 маскирует нулями некоторое заданное множест во разрядов арифметического блока 1. Если в процессе вычисления иевяэки ее значение по абсолютной величине превышает установленное ограничение, то по крайней мере в одном из незамаскированных старших разрядов арифметического блока 1 появляется единица, которая через элемент ИЛИ 9 переключает триггер 17 в единичное состояйие. При этом информация об абсолютнм значении невязки поступает в блок 2 иэ регистра 5. Информация о знаке невяэки 1 поступает на вход знакового разряда регистра 5 непосредственно с выхода знакового разряда арифметического блока 1. Триггер 60 17 перед началом. вычисления очередной невязки предварительно устанавливается в состояние "0" управлякщим сигналом на соответствующем выходе блока 4. 65 Коды, записанные в регистры 5 и 7,уменьшаются, например, в 8 раз путемвыполнения операции трехкратногосдвига в сторону младших разрядов.Таким образом, вначале ищется решение задачи при искусственно уменьшенных (по сравнению с заданными) ограничениях на невяэки. На это отводится, например, шестнадцать итераций.По завершении шестнадцатой итерациина выходе четвертого разряда счетчика 20 появляется управляющий сигнал,по которому происходит однократныйсдвиг кодов в регистрах 5 и 7 в сторону старших разрядов. При этом ограничение на невяэки с возрастает вдва раза. Если в последующие шестнадцать итераций решение не будет обнаружено, то зта операция повторяетсявновь . (через каждые шестнадцатьитераций на выходе четвертого разряда счетчика 20 появляется управляющий сигнал) . Описанная операция сдвига кодов в регистрах 5 и 7 повторяется до трех раз, т.е. до тех пор,пока не будет получено решение либоне исчерпается минимум допустимогочисла итераций (64) . В последнем случае в счетчике 20 устанавливаетсякод 64 и единичный сигнал с выхода.старшего разряда этого счетчика проходит через элемент ИЛИ 11 на входсхемы останова устройства в блоке 4.По завершении ввода информации начинается процесс решения задачи путем реализации обобщенного градиентного метода с использованием методаштрафных функций. При этом решаетсяитерационная задача минимизации суммы модулей составляющих вектора сдвига Х эа счет изменения в допустимыхпределах управляющего вектора невязок 2В процессе вычисления величинсдвигов Х; каждая из этих величинприбавляется к содержимому специальной ячейки блока 2 памяти, в которойнакапливается сумма модулей сдвиговЩЯ:Ег 1 Х 1,Телпроверяется на допустимость по заданным ограничениям сверху (;) иснизу, т.е. проверяется справедливость неравенств Эта проверка осуществляется путем анализа знака разности (х - ) , азатем (М -Ъ;)Если вычисленный сдвиг Х, не удовлетворяет какому-либо иэ ограничений, то этот факт Фиксируется путем записи штрафной функции (единичного сигнала) в соответствующий 1 -ый разряд сдвигающего регистра 13,Одновременно сигнал с элемента ИЛИ 10 переключает в единичное сос886004 гов осуществляется за счет всех составляющих вектора сдвигов, т.е. всем сдвигам Х приписывается штраф Ч, = =10 =1,2,,)Таким образом, минимизируемая целевая Функция равна8ВР=Д Ю+ ц ч фх,-В Ч;+1 х;-В,Ч+ ЧХ 1 10 Ч= 0 при Х 4 Ьто минимизация целевой, функции осуществляется только эа счет тех составляющих Х вектора сдвигов, которые выходят за рамки своих локальных 60 ограничений и для которых штрафы М; =1. Если же Б 5 К, то всепоследующие значения суммыЗ(5; Д Вс) и подавно будут большеббу, В этом случае минимизация суммы сдви где Р -тояние триггер 19, обеспечивая этим запрет на прохождение (в конце итерации) управляющего сигнала на вход схемы останова устройства, поступает в блок 4, инициируя выполнение операции сложения содержимого специальной ячейки в блоке 2 с абсолютным значением разности-) либо (Х,. - 9), т.е. выполнение операций накопления следующей суммы:а:а Д,.Е а,.: 1 Х;.Р, ,. и,при Х ъ (;1 при ХрПолученная сумма А записывается снова в специальную ячейку блока 2, предназначенную для хранения теку щего значения минимизируемой целевой Функции А. (В дальнейшем для определенности будем называть эту ячейку регистром целевой функции А) . Содержимое регистра целевой Функции А ис пользуется при вычислении нового векк+1тора невязок 2 , который обеспечивает на последующей итерации уменьшение величины этой целевой функции.В устройстве требуется, чтобы и З 0 сумма модулей всех сдвигов Х (как оштрафованных, так и неоштрафованных) не превышала установленное для данно. го микроплана ограничение 5 , . Эта сумма накапливается по мере вйчисления величин сдвйгов Х; в специальной ячейке блока памяти, которую для определенности назовем регистром суюы модулей сдвигов.Текущее значение накоплений суммы равно405.=5, +(Х 11=1,2в Ни одно из текущих значений суммы модулей сдвигов не должно превышать ог раничение 5 к , величина которого хранится в одной из рабочих ячеек блока 25 ф,СХ 45 тюок: 1, г Если это требование выполняется доконца расчета всех сдвигов Х;, т.е.сумма 0 при 5,Зцк51 при 5 , ,соСравнение текущего значения сумм 4 модулей сдвигов со своим ограничением происходит путем анализа знака разности (5 - 5) . Еспи 5; 5 то этот факт фиксируется путем зайиси штрафной функции (единичного сигнала) во все разряды сдвигающего регистра 13. Таким образом, будут оштрафованы все слагаемые Х; суммы 3, ВОдновременно сигнал с элемента ИЛИ 10 переключает в единичное состояние триггер 19, обеспечивая этим запрет на прохождение ,в конце итерации) управляющего сигнала из блока 4 на схему останова устройства через элементы И 16 и ИЛИ 11, поступает в блок 4, обеспечивая вычисление всех последующих сдвигов Х;+ .Хбез проверки их на допустимость по локальным ограничениям, что экономит время решения. При этом выполняется только операция накопления суммы модулей всех сдвигов. По завершении вычисления всех сдвигов и накопления суммы 5 лс-",х 1 зта сумма переписывается в регистр целевой функции А и используется при вычислении нового вектора невязки гНовые невязки вычисляются по основной формуле обобщенного градиентного метода. кф 1 к +1 ахк1. =2+Наг,. номер итерации,градиентный множитель, значение которого определяетсявыражениемкч рн( 1значение минимизируемой целевой функции, записанной в;регистр целевой Функции А1 блока 2,частные производные векторасдвигов Х"по 1 -иым приращениям вектора невязок 2", коФормула изобретения 35 40 45 50 55 торые вычисляются по формулам:ЗХ Щк = -УсрХ "Ч32,0,1,2 ю -1,где-ю постоянных коэффициентов,которые хранятся в ячейкахдополнительного блока 12,810 пХ - знаки ранее вычисленных величин сдвигов, которые хранятся в соответствующих разрядах сдвигового регистра 6.(сдвиги этого регистра исдвигающвго регистра 13 осуществляются синхронно в моменты вызова .из дополнительного блока 12 очередного коэффициента 5),Ч - штрафные Функции, значениякоторых хранятся в соответствующих разрядах сдвигающего. регистра 13.Штрафныв Функции 9 принимают еди-.ничное значение в случаях, еслисоответствующий М. не удовлетворяеткакому-либо из своих локальных ограничений, сумма модулей сдвигов превышает свое ограничение 6 ах , Вэтом случае всв Ч 1, что обеспечивавтья путем зааисй единичного сигнала с элемента ИЛИ 10 во эсе разрядысдвигающего регистра 13.Значения штрафов Ч .подаются в ка честве разрешающих сигналов в моменты вызова иэ дополнительного блока12 соответствующих постоянных коэффициентов 5 приведенных Формул, Значение Ч в соответствующем разрядесдвигающего регистра 13 разрешаетМ яЦ либо запрещает (,ЧзО) считывание с выхода. дополнительного блока12 соответствующего постоянного коэфФициента Ь в момент формированиякаждого члена суммы парных произведений при вычислении очередной частной производной. Порченные новыезначения невязок ЕзаписываютсяФв подблок .невязок блока 2 и используются при расчете на следующей итерации нового вектора сдвигов Х.Если все величины сдвигов Х;удовлетворяют заданным ограничениями при этом сумма модулей сдвигов, также не превышает свое ограничение, то это является признаком почения искомого решения. В этом случ " триггер 19, установленный вначале итерации в нулевое состояние сигналом из блока 4, сохраняет это состояние до конца итерации. Нулевоесостояние триггера 19 поддерживаетединичный потенциал на элементе И 16.В конце итерации в блоке 4 вырабатывается управляющий сигнал, которыйпоступает на счетный вход счетчика20 и на элемент И 16. Этот сигнал через элемент И 16 н через элемент ИЛИ11 поступает на вход схемы остановаустройства в блоке 4. Процесс вычислений заканчивается. В счетчике 20зафиксирован код числа итераций. Еслив течение 64 итераций решение не получено, то останов, устройства происходит по завершении 64-й итерациивычислительного процесса импульсом 15 переполнения счетчика 20. Этот импульс поступает непосредственно с выхода старшего разряда счетчика 20на элемент ИЛИ 11 и затем иа входсхемы останова устройства. щ Описанный процесс минимизации целевой Функции предусматривает поискрешения в более узких (по сравнениюс первоначально заданными) границахйзмвнения невязок ,что повышает 25 скорость обработки. Этим осуществля-ется-оптимизация целевой -функции качества пути (суммы невязок г;) Вычислительное устройство для решения задачи выправки железнодорожного пути по авт,св. В 802967, о т -л и ч а ю щ е е с я тем, что, сцелью повышения быстродействия, внего дополнительно введены счетчикИтераций, триггер Фиксации штрафнойфункции, третий элемент И, третийэлемент ИЛИ, причем первый вход триггера Фиксации штрафной функции соенеи с выходом второго элемента ИЛИ,нулевой выход триггера фиксации штрафной Функции через последовательносоединенные третьи элементы И, ИЛИсоединен со вторым входом блока управления, выход которого соединенсо вторым входом триггера Фиксацииштрафной Функции и со входами третьего элемента И и счетчика итераций,выходы которого соединены со входомтретьего элемента ИЛИ и вторым входом регистра ограничения невязок исо вторым входом регистра-маски.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 802967, кл. О 06 Р 15/20, 1977прототип).886004 тавитель Ю.Власред И. Гайду едактор И.Михеева орректор С.Щома аказ 10560/78 ТирВНИИПИ Госупо делам и 113035, Мос ж 748арственного комитета ССобретений и открытийва, Ж, Раушская наб,Подписи д. 5 илиал ППП фПатент", г.ужгород, ул.Проектна