Вычислительное устройство для решениязАдАчи ВыпРАВКи жЕлЕзНОдОРОжНОгО пуТи Советский патент 1981 года по МПК G06F17/00 

(54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ ВЫПРАВКИ ЖЕЛЕЗНОДОРОЖНОГО ПУТИ

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных машин для реше ния задач нелинейного программирования с двусторонними ограничениями на переменные, преимущественно задач расчета микроплана железнодорожного пути с целью управления работой путерихтовочного комплекса в реальном масштабе времени его продвижения. По основному авт.св. № 708355 известно вычислительное устройство для решения задач выправки железнодоро ного пути,содержащее арифметический блок,первый управляющий вход которого соединен с выходом блока управления, блок памяти,блок вывода,управляющие в ды которых подключены к выходу блока управления, блоки вывода-ввода, ариф метический блок и блок памяти соединены двусторонними связями, регистр ограничения невязок, регистр Маски, группа элементов И, элемент ИЛИ, триггер, сдвиговый регистр и дополнительный запоминающий блок, первый вход группы элементов И соединен с первым выходом арифметического блока, втопой вход попключен к ВЫХОДУ регистра Маски, выход группы элементов И через элемент ИЛИ подключен к первому входу триггера, второй вход которого соединен с выходом блока управления, первый выход триггера подключен к первому управляющему входу регистра ограничения невязок, второй выход триггера соединен с вторым управляющим входом арифметического блока, второй выход которого подключен к второму входу регистра ограничения и к первому входу сдвигового регистра, управляющий вход дополнительного запоминакщего блока и второй вход сдвигового регистра соединен с выходом блока управления, регистр ограничения невяэок, сдвиговый регистр и дополнительный запоминающий блок подключены двусторюнними связями к блоку ввода-вывода 1. При расчете микроплана железнодорожного пути решается специфическая задача нелинейного программирования с двусторонними ограничениями на зависимые переменные. Порядок Зё1дачи m « 10-15 обеспечивает необходимую точность решения. В процессе расчета микроплана осуществляется регулирование зависимых переменних Х. (величин сдвигов в расчетных точках деления пути) за счет изменения в допустимых пределах независимых переменных невязок Z (величин разностей стрел в двух соседних точках деления пути}. Указанное регулирование сводится к минимизации суммы модулей величин сдвигов до получения первого допустимого микро-плана пути, т.е. такого решения, в котором все величины сдвигов Х- удов летворяют своим ограничениям. В полу ченном решении величина первого сдви га фиксируется и подается в систему управления механизмами сдвига путерихтовочного комплекса на отработку. Таким образом, выполняется рихтов ка (выправка) железнодорожного пути в процессе движения рихтовочного комплекса одновременно с замеров натурного состояния этого пути на фиксированном расстоянии, равном длине рассчитываемого микроплана (100 - 150 м). По мере продвижения путерихтовочного комплекса вдоль участка всего пути (макроплана длиной до 4 км) полученные в результате расчетов множества микропланов величины сдвигов X,- вводятся последовательно один за другим на отработку в систему управления механизмом сдвига. Одновременно в вычислительное -устройство также последовательно вводятся новые исход ные данные о последующих точках пути. Расчет всего рихтуемого участка (макроплана) заменяется многократными расчетами множетсва микропланов (небольших участков на 10-15 точек д ления пути с интервалом 10 м). Каждая новая точка приводит к новой задаче. Размерность самой задачи не меняется, так как ввод каждой новой, неизвестной сопровождается выводом на отработку соответствующей зафиксированной величины сдвига в (1-15) точке деления пути. Определение расчетных сдвигов непосредственно в процессе работы путе рихтовочного комплекса предъявляет высокие требования к быстродействию вычислительного устройства. Процесс минимизации суммы модулей величин Х происходит в устройствепрототипе за счет уменьшения всех со ставлякхцих вектора Хин первую оче редь больших по абсолютной величине. При этом могут возникнуть ситуации, когда эти составлякяцие уже удовлетворяют своим ограничениям, в то время как другие, меньшие по абсолютной величине, выходят за рамки своих ограничений, и следовало бы в первую очередь минимизировать именно эти со ставляющие. Иначе говоря, в описанны ситуациях отсутствует достаточная гибкость регулирования при решении задачи с помощью устройства-прототипа. Это приводит к лишним итерациям вычислительного процесса и затратам времени. Кроме того, происходит ухудшение качества решения за счет неизбежного возрастания вектора невязок Z. Целесообразно на каждой итерации уменьшать абсолютные значения только тех составляющих Х. , которые не удовлетворяют своим ограничениям. огда решение будет получено быстрее и лучшего качества за счет меньшего отклонения вектора невязок Z от своего нулевого (идеального с точки зрения качества пути) значения. Этому устройству присуще снижение качества решения по критерию плавности пути и затраты времени на выполнение лишних итераций при минимизации суммы модулей всех составляющих векторов сдвигов. Целью изобретения является повышение быстродействия и точности устройства. Достигается это тем, что в устройство введены сдвигающий регистр штрафов, дополнительный триггер, два элемента И, второй элемент ИЛИ, причем вход дополнительного триггера и первый вход сдвигающего регистра штрафов соединены с выходом блока управления, второй и третий выходы арифметического блока соединены с первыми входами первого и второго элементов И, выходы которых через второй элемент ИЛИ соединены с входом блока управления и через сдвигающий регистр штрафов с вторым входом дополнительного блока памяти, выходы дополнительного триггера соединены с вторыми входами двух элементов И. Блок-схема устройства приведена на чертеже. Устройство содержит арифметический блок 1, блок 2 памяти, блок 3 ввода-вывода, блок 4 управления, регистр 5 ограничения невязок, регистр б Маски, группа элементов И 7, элементы ИЛИ 8 и 9, триггеры 10 и 11, сдвиговый регистр 12, дополнительный блок 13 памяти, элементы И 14 и 15, сдвигакиций регистр 16 штрафов. Устройство работает следующим образом. В процессе вычисления величины сдвигов Х каждая из этих величин проверяется на допустимость по заданным ограничениям сверху (р.) и снизу ( pij ) . Вначале вычисленное значение X,- сравнивается с верхней границей 1Ь путем анализа знака разности (X, - (Ь-) . При этом триггер 11 устанавливается по сигналу из блока 4 в состояние 1, открывая элемент И 14. Если значение величины Х. Р i то с прямого выхода знакового разряда арифметического блока 1 единичный сигнал, через элемент И 14 и элемент ИЛИ 9 поступает на вход сдвигающего регистра 16, где и записан в его i-и разряд в стве и1трафной функции 1. Одновременно с эти абсолютное значение разности - (b будет прибавлено к содержимому соответствующей ячейки блока 2, в которой накапливается сумма модулей превышений оштрафованных величин над их ограничениями, так как вычис ляется сумма w m .|. , где Ч - штрафная функция, причем Ч ,- 1, если X,- Ч О, если : (Ь Операция накопления суммы А инициируется единичным сигналом с выхо да элемента ИЛИ 9. Этот сигнал посту пает в блок 4. Если значение величины Х,- Р , то на прямом выходе знакового разряда арифметического блока 1 будет нулево сигнал. В этом случае в соответствую щем i-ом разряде сдвигающего регистра 16 сохранится нулевое состояние, но возникает необходимость проверки полученного значения Х на допустимость по ограничению снизу. Теперь величина Х сравнивается со своей нижней границей путем анализа знака разности ((Ъ). При этом триггер 1 устанавливается по сигналу из блока в состояние О, открывая элемент И 15. Если значение величины не удовлетворяет ограничению снизу,, то разность (Х. - ) - отрицательна и на инверсном выходе знакового разряда арифметического блока 1 появляется единичный сигнал, который через элементы И 15 и ИЛИ 9 поступит на вход сдвигающего регистра 16 и будет запи сан в его i-ый разряд в качестве штафной функции 1. Одновременно этот сигнал поступит в блок 4, обеспечивая операцию прибавления к содер жимому соответствующей ячейки блока абсолютного значения разности Х - рЕсли же и в этом случае значение сдвига не превышает ограничения снизу j)I , то в соответствующем разряде сдвигающего регистра 16 сохранится нулевое состояние. Сдвиг кода в регистре 16 осуществляется путем подачи из блока 4 сдвигающего сигнала на тактовый вход регистра 16 при вычислении последующей величины Х Таким образом, на каждой итерации вычислительного процесса происходит полный цикл проверки вычисленных зна чений на допустимость по о:5раничениям. Эта проверка осуществляется и в устройстве-прототипе, но только с целью фиксации момента получения первого допустимого решения. В устройстве используются результаты описываемой проверки для дальнейших вычислений с целью получения решения лучшего качества и за меньшее время. Если все величины Х удовлетворяю чаданшлм ограничениям, то в сдвигающем регистре 16 сохранится код, равный нулю, что являет ся критерием получения допустимого решения. Аналогично и в соответствующей ячейке блока 2 накопленная сумма модулей А; будет равна нулю. Если хотя бы один из Х- не удовлетворяет какому-либо из ограничений, то этот факт фиксируется путем записи штрафной сигнум-функции в соответствующий разряд сдвигающего регистра 16. Одновременно, сигнгш с выхода элемента ИЛИ 9 поступает в блок 4 и запускает автомат, обеспечивающий выполнение операции прибавления абсолютного значения разности между и соответствующим ограничением к содержимому специальной ячейки памяти в блоке 2. Содержимое сдвигающего регистра 16 используется в дальнейшем при вычислении невязок 2 По завершению цикла вычисления и штрафования величин сдвигов осуществляется процесс расчета новых невязок по формуле обобщенного градиентного метода номер итерации; градиентный множитель, значение которого определяется следующим выражением: . Лэ25 где А. (,)-%+ (X.-1b)f; ГО при Х 4 , - 1 при X. р. X. р) - частные производные вектора X по t приращениям вектора невязок Z, которые вычисляются по формулам-lSAc5nX.,. ,Ч,(|пХзЧ5 -...-П1(т-1)31ф1 |-.-2SicjnX.4..4,S,(nX,,,4,-..-(-))%|- -25ЦпХтп т ,i,a,..., Из приведенных формул видно, что астные производные являются ункциями не просто от знаков ранее ычисленных Х сдвигов (как в устойстве-прототипе), но и соответствуюих им штрафов Ч ., значения которых ранятся в сдвигающем регистре 16 подсшзтся в качестве разрешающих игналов в моменты вызова из дополнительного блока 13 соответствующих постоянных коэффициентов L- приведен ных формул. Значение штрафной функции Ц в соответствующем разряде сдвигающего регистра 16 разрешает, либо запрещает считывание с выхода дополнительного блока 13 соответствующего постоянного коэффициента L при формировании каждого члена алгебраической суммы парных произведений Lj-SiqnX - при вычислении очередной частной производной -- . Таким образом, процесс минимизации целевой функции будет осуществляться только за счет тех составляющих Х вектора сдвигов X, для которых функции штрафов Ч, 1, т.е. которые не удовлетворяют своим ограничениям. В изобретении совокупность новых элементов и связей реализует минимизацию целевой функции следующего вида )ЧVP) irl Структура такой целевой функции, благодаря введению штрафных сигнумфункций Ч -переменная. Это обеспечивает большую гибкость процесса минимизации, т.е. этот процесс осущест вляется за счет уменьшения именно -тех составляющих Х, которые выходят за рамки своих ограничений (для них соответствующие Ч 1). Такая концепция позволяет получат решение значительно быстрее (процесс минимизации сходится за меньшее число итераций) и лучшего качества. В самом деле, первое допустимое решение фиксируется при достижении значения целевой функции А нулевого зна чения. При этом сумма модулей самих сдвигов может оставаться достаточно большой, а значит сохранится резерв невязок , т.е. отклонение вектора невязок Z от своего нулевого (идеального с точки зрения качества пути значения минимально. Методы штрафных функций широко применяются при решении задач математического программирования, в том числе и в сочетании с обобщенным гра диентным методом. Однако при решении задачи расчета микроплана железнодорожного пути реализация этого ме тода программным путем требует непозволительных затрат времени. Изобретение позволяет аппаратными средствами автоматически формировать на каждой итерации соответствующую структуру целевой функции с целью бо лее быстрого и качественного расчета микроплана пути. Формирование структ ры целевой функции и последующий ра чет частных производных вектора сдв гов по приращениям невязок происходит одновременно с основными расчетами, не отнимая ни единого такта машинного времени. Этопозволяет достичь цели предлагаемого изобретения - получения с помощью незначительных затрат оборудования повышения качества и уменьшения времени решения задачи расчета микроплана железнодорожного пути. Решение тестовьлх задач позволило получить усредненные данные о производительности предлагаемого устройства и качества получаемых решений. Время решения задач сократилось на 30% (в среднем), а качество решения по критерию плавности пути выше на 30-40% по сравнению с решением тех же задач с помощью устройствапрототипа. Проведенные испытания на специализированной вычислительной машине, разработанной и изготовленной по данному изобретению, подтверждает более высокую эффективность устройства, которое можно использовать в качестве бортового вычислителя, обеспечиваквдего повышенное качество и скорость решения задачи выправки железнодорожного пути в реальном масштабе времени работы путерихтовочного комплекса. Устройство может быть также использовано при построении специёшиэированных вычислительных машин для решения больших систем линейных неравенств, задач управления технологическими процессами и задач исследования операций. Формула изобретения Вычислительное устройство для решения задачи выправки железнодорожного пути по авт. св. 708355, отличающее с я тем, что, с целью повыиения быстродействия и повышения точности, в него введены сдвигающий регистр штрафов, дополнительный триггер, два элемента И и второй элемент ИЛИ, причем, вход дополнительного триггера и первый вход сдвигающего регистра штрафов соединены с выходом блока управления, второй и третий выход арифметического блока соединены с первыми входами первого и второго элемента И, выходы которых через второй элемент ИЛИ соединены с входом блока управления и через сдвигающий регистр штрафов с вторым входом дополнительного блока памяти, выходы дополнительного триггера соединены с вторыми входами двух элементов И. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР 708355, кл. G 06 F 15/20, 21.07.77 (прототип).