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

Союз Сфветсинк Соцналистнческнк РЕспублик(22) Заявлено 1 И 277 (21) 2556813/18-24с прнсоеднненнем заявки ЙУ -(51)М; Кл.з С 06 Г 15/20 Государственный комитет СССР но делам изобретений и открытий(72) Авторы изобретения О.В. Власенко, Е.А. Проскурин и Э.З. Трайннн Ордена Ленина институт кибернетики АН Украинской ССР.(54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ ВЫПРАВКИ ЖЕЛЕЗНОДОРОЖНОГО ПУТИ Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных машин для реше ния задач нелинейного программирования с двусторонними ограничениями на переменные, преимущественно задач расчета микроплана железнодорожного пути с целью управления работой путерихтовочного комплекса в реальном масштабе времени его продвиженияПо основному авт.св. Р 708355известно вычислительное устройстводля решения задач выправки железнодорож5ного пути, содержащее арифметическийблок, первый управляющий вход которогосоединен с выходом блока управления,блок памяти, блок вывода, управляющие входы которых подключены к выходу блока 20управления, блоки вывода-ввода, арифметический блок и блок памяти соединены двусторонними связями, регистрограничения невязок, регистр Маски,группа элементов И, элемент ИЛИ,триггер, сдвиговый регистр и дополнительный запоминающий блок, первыйвход группы элементов И соединен спервым выходом арифметического блока, втоловход попключен к выходу 30 регистра Маски, выход группы элементов И через элемент ИЛИ подключен к первому входу триггера, второй вход которого соединен с выходом блока управления, первый выход триггера подключен к первому управляющему входу регистра ограничения невязок, второй выход триггера соединен с вторым управляющим входом арифметического блока, второй выход которого подключен к второму входу регистра ограничения и к первому входу сдвигового регистра, управляющий вход дополнительного запомннающего блока и второй вход сдвигового регистра соединен с выходом блока управления, регистр ограничения невязок, сдвиговый регистр и дополнительный запоминающий блок подключены двусторонними связями к блоку ввода-вывода 11.При расчете микроплана железнодорожного пути решается специфическая задача нелинейного программирования с двусторонними ограничениями на зависимые переменные. Порядок задачи е в 10-15 обеспечивает необходимую точность решения.В процессе расчета микроплана осуществляется регулирование зависимыхпеременных Х (величин сдвигов в расчетных точках деления пути) за счет изменения в допустимых пределах независимых переменных невязок 2, (величин разностей стрел в двух соседних точках деления пути). Укаэанное регулирование сводится к минимизации суммы модулей величин сдвигов до получения первого допустимого микро- плана пути, т.е. такого решения, в котором все величины сдвигов Х удов- о летворяют своим ограничениям, В полученном решении величина первого сдвига фиксируется и подается в систему управления механизмами сдвига путерихтовочного комплекса на отработку.Таким образом, выполняется рихтов ка (выправка) железнодорожного пути и процессе движения рихтовочного комплекса одновременно с замеров натурного состояния этого пути на фиксированном расстоянии, равном длине 20 рассчитываемого микроплана (100150 м).По мере прбдвижения путерихтовочного комплекса вдоль участка всего пути (макроплана длиной до 4 км) полученные в результате расчетов множества микропланов величины сдвигов Х; вводятся последовательно один за другим на отработку в систему управления механизмом сдвига, Одновременно в вычислительное устройство такжепоследовательно вводятся новые исходные данные о последующих точках пути. Расчет всего рихтуемого участка (макроплана) заменяется многократными расчетами множетсва микропланов(небольших участков на 10-15 точек деления пути с интервалом 10 м), Каждая новая точка приводит к новой задаче. Размерность самой задачи не меняется, так как ввод каждой новой неизвестной сопровождается выводом на отработку соответствующей зафиксированной величины сдвига в -15) точке деления пути.Определение расчетных сдвигов непосредственно в процессе работы путерихтовочного комплекса предъявляет высокие требования к быстродействию вычислительного устройства.Процесс минимизации суммы модулей величин Х происходит в устройстве- прототипе за счет уменьшения всех составляющих вектора Х и в первую очередь больших по абсолютной величине.При этом могут возникнуть ситуации, когда эти составляющие уже удовлетворяют своим ограничениям, в то время как другие, меньшие по абсолютной величине, выходят за рамки своих ограничений, и следовало бы в первуюочередь минимизировать именно эти со- бОставляющие. Иначе говоря, в описанныхситуациях отсутствует достаточная гибкость регулирования при решении задачи с помощью устройства-прототипа, Это приводит к лишним итерациям вычислительного процесса и затратамвремени. Кроме того, происходит ухудшение качества решения за счет неизбежного возрастания вектора невязок 2. Целесообразно на каждой итерации уменьшать абсолютные значениятолько тех составляющих Х., которыене удовлетворяют своим ограничениям.Тогда решение будет получено быстрееи лучшего качества за счет меньшегоотклонения вектора невязок 2 от своего нулевого (идеального с точки зрения качества пути) значения,Этому устройству присуще снижениекачества решения по критерию плавности пути и затраты времени на выполнение лишних итераций при минимизациисуммы модулей всех составляющих векторов сдвигов.Целью изобретения является повышение быстродействия и точности устройства,Достигается это тем, что в устройство введены сдвигающий регистр штрафов, дополнительный триггер, два элемента И, второй элемент ИЛИ, причемвход дополнительного триггера и первый вход сдвигающего регистра штрафов соединены с выходом блока управления, второй и третий выходы арифметического блока соединены с первымивходами первого и второго элементовИ, выходы которых через второй элемент ИЛИ соединены с входом блока управления и через сдвигающий регистрштрафов с вторым входом дополнительного блока памяти, выходы дополнительного триггера соединены с вторымивходами двух элементов И.Блок-схема устройства приведенана чертеже.Устройство содержит арифметический блок 1, блок 2 памяти, блок 3ввода-вывода, блок 4 управления, регистр 5 ограничения невязок, регистр6 Маски, группа элементов И 7, элементы ИЛИ 8 и 9, триггеры 10 и 11,сдвиговый регистр 12, дополнительныйблок 13 памяти, элементы И 14 и 15,сдвигающий регистр 16 штрафов,Устройство работает следующим образом.В процессе вычисления величинысдвигов Х, каждая из этих величинпроверяется на допустимость по заданным ограничениям сверху ( Ь.) иснизу (ф;), Вначале вычисленное значение Х, сравнивается с верхней границейпутем анализа знака разности (Х 1 - 9;), При этом триггер 11 устанавливается по сигналу из блока 4в состояние "1", открывая элементИ 14. Если значение величины Х.),то с прямого выхода знакового разряда арифметического блока 1 единичный сигнал, через элемент И 14 и элемент ИЛИ 9 поступает на вход сдвигающего регистра 16, где и бу .:.т записан в его 1-и разряд в к";. стве штраф.ной функции "1". Одновременно с этим абсолютное значение разности )Х; - ; будет прибавлено к содержимому соответствующей ячейки блока 2, в которой накапливается сумма модулей превышений "оштрафованных" величин Х,. над их ограничениями, так как вычис- ляется сумма11А: :;А.Ч,=:С:Х,-РЯ где М - штрафная функция, причемЧ = 1, если Х 1) Р 1М= О, если Хс рОперация накопления суммы А инициируется единичным сигналом с выхода элемента ИЛИ 9, Этот сигнал поступает в блок 4.Если значение величины Х; (Ъ;, то на прямом выходе знакового разряда арифметического блока 1 будет нулевой сигнал. В этом случае в соответствующем 1-ом разряде сдвигающего регистра 16 сохранится нулевое состояние, но возникает необходимость пронерки полученного значения Х; на допустимость по ограничению сйизу. Теперь величина Х сравнивается со своей нижней границей путем анализа знака разности (Х, - М,). При этом триггер 11 устанавливается по сигналу из блока 4 в состояние "О", открывая элемент И 15. Если значение величины Х не удовлетворяет ограничению снизу то разность (Х -) - отрицательна и на инверсном выходе знакового разряда арифметического блока 1 появляется единичный сигнал, который через элементы И 15 и ИЛИ 9 поступит на вход сдвигающего регистра 16 и будет записан в его -ый разряд н качестве штафной функции "1", Однонременно этот сигнал поступит в блок 4, обеспечивая операцию прибавления к содержимому соответствующей ячейки блока 2 абсолютного значения разности 1 Х - ,.),( Если же и н этом случае значение сдвига Х не превышает ограничения1снизу ), то н соответствующем разряде сдвигающего регистра 16 сохранится нулевое состояние. Сдвиг кода в регистре 16 осуществляется путем подачи из блока 4 сдвигающего сигнала на тактовый вход регистра 16 при вычислении последующей величины ХТаким образом, на каждой итерации вычислительного процесса происходит полный цикл проверки вычисленных значений Х. на допустимость по ограничениям. Эта проверка осуществляется и в устройстве-прототипе, но только с целью фиксации момента получения первого допустимого решения. В устройстне используются результаты описываемой проверки для дальнейших вычислений с целью получения решения лучшего качества и за меньшее время.Если все величины Х 1 удовлетворяют .1 алаиим граничеинм, то в сдвигаю щем регистре 1 Ь сохранится код, равный нулю, что является критерием получения допустимого решения. Аналогично и в соответствующей ячейке блока 2 накопленная сумма модулей А, будет равна нулю.Если хотя бы один из Х; не удовлетворяет какому-либо из ограничений, то этот факт фиксируется путем записи штрафной сигнум-функции в соответствующий разряд сдвигающего регистра 16. Одновременно, сигнал с выхода элемента ИЛИ 9 поступает в блок 4 и запускает автомат, обеспечивающий выполнение операции прибавления абсолютного значения разности между Х и соответствующим ограничением к содержимому специальной ячейки памяти в блоке 2. Содержимое сдвигающего регистра 16 используется в дальнейшем при вычислении невязок 2.По завершению цикла вычисления и "штрафования" величин сдвигов Х; осуществляется процесс расчета новйх невяэок по формуле обобщенного градиентного методаНХ"дик10 20 25 где К - номер итерации;Н К+" - градиентный множитель,значение которого опреде- ЗОляется следующим выражением: д";(:Р 35 где А. = (Х. 40 частные производные вектора Х по 1 приращениям вектора ненязок 2, которые вычисляются по фор- мулам=-281 ЯЛХ. Я -6 Ч -,.,1 фМ)Яф 1 ХДМ 1 ф + 1% ф 1 д - 25 крХп 11 1=0, ,1 п 1-1ВХ55 Из приведенных формул видно, чтодХчастные производныеявляютсяфункциями не просто от знаков ранее 0 вычисленных Х сдвигов (как в устройстве-прототипе), но и соответствующих им штрафов Ч., значения которыххранятся в сдвигающем регистре 16и подаются в качестве разрешающихсигналов в моменты вызова из допол 802967нительного блока 13 соответствующих постоянных коэффициентовприведенных формул. Значение штрафной функции М в соответствующем разряде сдвигающего регистра 16 разрешает, либо запрещаЕт считывание с выхода дополнительного блока 13 соответствующего постоянного коэффициента1 при формировании каждого члена алгебраической суммы парных произведений ; 51 цпХ при вычислении очередной частной производнойОаг,Таким образом процесс минимизации целевой функции будет осуществляться только за счет тех составляющих Х 1 вектора сдвигов Х, для ко торых функции штрафов Ч, = 1, т.е. которые не удовлетворяют своим ограничениям.В изобретении совокупность новых элементов и связей реализует миними зацию целевой функции следующего вида1 п, пты д= С д. Е" (,Х.-Р)ц;+(Х-Р)Ю;1:1- 1Структура такой целевой функции,благодаря введению штрафных сигнумфункций Ю-переменная, Это обеспечивает большую гибкость процесса минимизации, т.е. этот процесс осуществляется за счет уменьшения именно.тех составляющих Х., которые выходятза рамки своих ограничений (для них,соответствующие М,= 1),Такая концепция позволяет получатьрешение значительно быстрее (процессминимизации сходится за меньшее число итераций) и лучшего качества. Всамом деле, первое допустимое решение фиксируется при достижении значения целевой функции А нулевого значения. При этом сумма модулей самих 40сдвигов может оставаться достаточнобольшой, а значит сохранится "резерв"невязок 2;, т.е. отклонение вектораневязок Е от своего нулевого (идеального с точки зрения качества пути) 4значения минимально.Методы штрафных функций широкоприменяются при решении задач математического программирования, в томчисле и в сочетании с обобщенным гра-диентным методом. Однако при решении задачи расчета микроплана железнодорожного пути реализация этого метода программным путем требует непозволительных затрат времени,Изобретение позволяет аппаратнымисредствами автоматически формироватьна каждой итерации соответствующуюструктуру целевой функции с целью более быстрого и качественного расчетамикроплана пути. Формирование структуры целевой функции и последующий расчет частных производных вектора сдвигов по приращениям невязок происходит одновременно с основными расчетами, не отнимая ни единого такта машинного времени. Это позволяет достичь цели предлагаемого изобретения - получения с помощью незначительных затрат оборудования повышения качества и уменьшения времени решения задачи расчета микроплана железнодорожного пути. Решение тестовых задач позволило получить усредненные данные о производительности предлагаемого устройства и качества получаемых решений. Время решения задач сократилось на 30 (в среднем), а качество решения по критерию плавности пути выше на 30-40 по сравнению с решением тех же задач с помощью устройства- прототипа. Проведенные испытания на специализированной вычислительной машине, разработанной и изготовленной по данному изобретению, подтверждает более высокую эффективность устройства, которое можно использовать в качестве бортового вычислителя, обеспечивающего повышенное качество и скорость решения задачи выправки железнодорожного пути в реальном масштабе времени работы путерихтовочного комплекса. Устройство может быть также использовано при построении специализированных вычислительных машин для решения больших систем линейных неравенств, задач управления технологическими процессами и задач исследования операций.формула изобретенияВычислительное устройство для решения задачи выправки железнодорожного пути по авт. св, Р 708355, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и повышения точности, в него введены сдвигающий регистр штрафов, дополнительный триггер, два элемента И и второй элемент ИЛИ, причем, вход дополнительного триггера и первый вход сдвигающего регистра штрафов соединены с выходом блока управления, второй и третий выход арифметического блока соединены с первыми входами первого и второго элемента И, выходы которых через второй элемент ИЛИ соединены с входом блока управления и через сдвигающий регистр штрафов с вторым входом дополнительного блока памяти, выходы дополнительного триггера соединены с вторыми входами двух элементов И.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 708355, кл. С 06 Г 15/20, 21.07.77802967 асен Составитель Ю. Вл коТехред Т. Маточка Коррект Па ктор Е. Гонча аказ 10625/62 4/ филиал ППП "Патент", г, Ужгород, ул. Проектна Тираж 75 ВНИИПИ ГосУд по делам 13035 МоскваПодписноественного комитета СССобретений и открытий