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

 

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

Соцналистнческнк

РЕспублик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВ ПЛЬСТВУ

l

1 (61) Дополнительное к авт. свнд-ву !т 708355 (22) Заявлено 1%1277 (2I) 2556813/18-24 с прнсоеднненнем заявки ЙУ— (23) Приоритет

Опубликовано 0 20281. Бюллетень Йо 5

Дата опубликования описания 1002.81 (51)М; Клз

G 06 F 15/20

Государственный комитет

СССР но делам изобретений и открытий (53) УДК 681.325 (088. 8) (72) Авторы изобретения! !

О.В. Власенко, Е.A. Проскурин и Э.З. Трайннн

Ордена Ленина институт кибернетики АН Украинской ССР (71) Заявитель (54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

ЗАДАЧИ ВЫПРАВКИ ЖЕЛЕЗНОДОРОЖНОГО ПУТИ

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных машин для реше. ния задач нелинейного программирования с двусторонними ограничениями на переменные, преимущественно задач расчета микроплана железнодорожного пути с целью управления работой путерихтовочного комплекса в реальном масштабе времени его продвижения ° По основному авт.св. !Е 708355 известно вычислительное устройство для решения задач выправки железнодорож-15 ного пути, содержащее арифметический блок, первый управляющий вход которого соединен с выходом блока управления, блок памяти, блок вывода, управляющие входы которых подключены к выходу блока 20 управления, блоки вывода-ввода, арифметический блок и блок памяти соединены двусторонними связями, регистр ограничения невязок, регистр Маски, группа элементов И, элемент ИЛИ, триггер, сдвиговый регистр и дополнительный запоминающий блок, первый вход группы элементов И соединен с первым выходом арифметического блока, втоло 1 вход попключен к выходу 30 регистра Маски, выход группы элементов И через элемент ИЛИ подключен к первому входу триггера, второй вход которого соединен с выходом блока управления, первый выход триггера подключен к первому управляющему входу регистра ограничения невязок, второй выход триггера соединен с вторым управляющим входом арифметического блока, второй выход которого подключен к второму входу регистра ограничения и к первому входу сдвигового регистра, управляющий вход дополнительного запомннающего блока и второй вход сдвигового регистра соединен с выходом блока управления, регистр ограничения невязок, сдвиговый регистр и дополнительный запоминающий блок подключены двусторонними связями к блоку ввода-вывода (1 .

При расчете микроплана железнодорожного пути решается специфическая задача нелинейного программирования с двусторонними ограничениями на зависимые переменные. Порядок задачи

m 10-15 обеспечивает необходимую точность решения.

В процессе расчета микроплана осуществляется регулирование зависимых

802967 переменных Х„ (величин сдвигов в расчетных точках деления пути) за счет изменения в допустимых пределах независимых переменных невязок Z, (величин разностей стрел в двух соседних точках деления пути). Укаэанное регулирование сводится к минимизации суммы модулей величин сдвигов до получения первого допустимого микроплана пути, т.е. такого решения, в котором все величины сдвигов Х„ удов- to летворяют своим ограничениям. В полученном решении величина первого сдвига фиксируется и подается в систему управления механизмами сдвига путерихтовочного комплекса на отработку.

Таким образом, выполняется рихтов- 1 ка (выправка) железнодорожного пути и процессе движения рихтовочного комплекса одновременно с замеров натурного состояния этого пути на фиксированном расстоянии, равном длине 20 рассчитываемого микроплана (100

150 м).

По мере прбдвижения путерихтовочного комплекса вдоль участка всего пути (макроплана длиной до 4 км) полученные в результате расчетов множества микропланов величины сдвигов

Х; вводятся последовательно один за другим на отработку в систему управления механизмом сдвига. Одновременно в вычислительное устройство также последовательно вводятся новые исход» ные данные о последующих точках пути. Расчет всего рихтуемого участка (макроплана) заменяется многократными расчетами множетсва микропланов (небольших участков на 10-15 точек деления пути с интервалом 10 м), Каждая новая точка приводит к новой задаче. Размерность самой задачи не меняется, так как ввод каждой новой неизвестной сопровождается выводом на отработку соответствующей зафиксированной величины сдвига в (I-15) точке деления пути.

Определение расчетных сдвигов непосредственно в процессе работы путерихтовочного комплекса предъявляет высокие требования к быстродействию вычислительного устройства.

Процесс минимизации суммы модулей величин Х„ происходит в устройствепрототипе за счет уменьшения всех составляющих вектора Х и в первую очередь больших по абсолютной величине.

При этом могут возникнуть ситуации, когда эти составляющие уже удовлетворяют своим ограничениям, в то время как другие, меньшие по абсолютной величине, выходят за рамки своих ограничений, и следовало бы в первую очередь минимизировать именно эти со- бО ставляющие. Иначе говоря, в описанных ситуациях отсутствует достаточная гибкость регулирования при решении задачи с помощью устройства-прототипа. Это приводит к лишним итерациям вычислительного процесса и затратам времени. Кроме того, происходит ухудшение качества решения за счет неизбежного возрастания вектора невязок Z. Целесообразно на каждой итерации уменьшать абсолютные значения только тех составляющих X., которые не удовлетворяют своим ограничениям.

Тогда решение будет получено быстрее и лучшего качества за счет меньшего отклонения вектора невязок 2 от своего нулевого (идеального с точки зрения качества пути) значения.

Этому устройству присуще снижение качества решения по критерию плавности пути и затраты времени на выполнение лишних итераций при минимизации суммы модулей всех составляющих векторов сдвигов.

Целью изобретения является повышение быстродействия и точности устройства.

Достигается это тем, что в устройство введены сдвигающий регистр штрафов, дополнительный триггер, два элемента И, второй элемент ИЛИ, причем вход дополнительного триггера и первый вход сдвигающего регистра штрафов соединены с выходом блока управления, второй и третий выходы арифметического блока соединены с первыми входами первого и второго элементов

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

Блок-схема устройства приведена на чертеже.

Устройство содержит арифметический блок 1, блок 2 памяти, блок 3 ввода-вывода, блок 4 управления, регистр 5 ограничения невязок, регистр

6 Маски, группа элементов И 7, элементы ИЛИ 8 и 9, триггеры 10 и 11, сдвиговый регистр 12, дополнительный блок 13 памяти, элементы И 14 и 15, сдвигающий регистр 16 штрафов.

Устройство работает следующим образом.

В процессе вычисления величины сдвигов Х, каждая из этих величин проверяется на допустимость по заданным ограничениям сверху (5„-) и снизу (5;). Вначале вычисленное значение Х; сравнивается с верхней границей „ путем анализа знака разности (Х -(;). При этом триггер 11 устанавливается по сигналу из блока 4 в состояние "1", открывая элемент

И 14. Если значение величины Х. ) ) „, то с прямого выхода знакового разряда арифметического блока 1 единичный сигнал, через элемент И 14 и элемент ИЛИ 9 поступает на вход сдвигающего регистра 16, где и бу - т запиoàí в его i-и разряд в к." . стве штраф802967 ной функции "1". Одновременно с этим абсолютное значение разности )Х; - j3;l будет прибавлено к содержимому соответствующей ячейки блока 2, в которой накапливается сумма модулей превышений "оштрафованных" величин Х,. над их ограничениями, так как вычис- ляется сумма

VA \11 д= À.ì.= : х -p„I „., где Ч вЂ” штрафная функция, причем

Ч „= 1, если Х„> Р;

М„= О, если Х„. с ф„

Операция накопления суммы А инициируется единичным сигналом с выхода элемента ИЛИ 9. Этот сигнал поступает в блок 4.

Если значение величины Х; (Р;, то на прямом выходе знакового разряда арифметического блока 1 будет нулевой сигнал. В этом случае в соответствующем i-ом разряде сдвигающего регистра 16 сохранится нулевое состояние, но возникает необходимость проверки полученного значения Х; на допустимость по ограничению сйизу. Теперь величина Х сравнивается со своей

1 нижней границей путем анализа знака разности (X — ф,). При этом триггер 11 устанавливается по сигналу из блока 4 в состояние "0", открывая элемент

И 15. Если значение величины Х„- не удовлетворяет ограничению снизу, то разность (X - ) — отрицательна и на

1 инверсном выходе знакового разряда арифметического блока 1 появляется единичный сигнал, который через элементы И 15 и ИЛИ 9 поступит на вход сдвигающего регистра 16 и будет записан в его i-ый разряд в качестве штафной функции "1". Одновременно этот сигнал поступит в блок 4, обеспечивая операцию прибавления к содержимому соответствующей ячейки блока 2 абсолютного значения разности 1Х„ — p,-l. (Если же и в этом случае значение сдвига Х не превышает ограничения

1 1 снизу ф„, то в соответствующем разряде сдвигающего регистра 16 сохранится нулевое состояние. Сдвиг кода в регистре 16 осуществляется путем подачи из блока 4 сдвигающего сигнала на тактовый вход регистра 16 при вычислении последующей величины Х

Таким образом, на каждой итерации вычислительного процесса происходит полный цикл проверки вычисленных значений Х„- на допустимость по ограничениям. Эта проверка осуществляется и в устройстве-прототипе, но только с целью фиксации момента получения первого допустимого решения. В устройстве используются результаты описываемой проверки для дальнейших вычислений с целью получения решения лучшего качества и за меньшее время.

Если все величины Х удовлетворяют заланним <>граниченинм, то в сдвигающем регистре 16 сохранится код, равный нулю, что является критерием получения допустимого решения. Аналогично и в соответствующей ячейке блока

2 накопленная сумма модулей А, будет равна нулю.

Если хотя бы один из Х; не удовлетворяет какому-либо из ограничений, то этот факт фиксируется путем записи штрафной сигнум-функции в соответствующий разряд сдвигающего регистра 16. Одновременно, сигнал с выхода элемента ИЛИ 9 поступает в блок 4 и запускает автомат, обеспечивающий выполнение операции прибавления абсолютного значения разности между Х„ и соответствующим ограничением к содержимому специальной ячейки памяти в блоке 2. Содержимое сдвигающего регистра 16 используется в дальнейшем при вычислении невязок Z„.

По завершению цикла вычисления и

"штрафования" величин сдвигов Х; осуществляется процесс расчета новйх невяэок по формуле обобщенного градиентного метода аХ"

«9Z» 1

20

25 где К вЂ” номер итерации;

Н +" — градиентный множитель, значение которого опреде30 ляется следующим выражением:

-р„). Ч„+ (X„. „ . )Ч, .) где А. = ((X.

Э Х"

a Zlc

1 частные производные вектора X no t приращениям вектора невязок 2, которые вычисляются по формулам

-- — — --2Яср Х Ц -65E+NW Ч-...-мт(си+ )Я(с иХ Ц ах

1з („х ц -ьэ4 х Ч вЂ”...- (m- )pi Х Ч

50 >

=-251 „X <4 s„ nX ° - -(-- - ) RgnX„V„Д2 Ъ j +s 3+1" 1

-,- - ---25Щ Хтп Фгр „ о-1 1., п - Х

Из приведенных формул видно, что

BX частные производные являются функциями не просто от знаков ранее

Я вычисленных Х„ сдвигов (как в устройстве-прототипе), но и соответствующих им штрафов Ч., значения которых

1 хранятся в сдвигающем регистре 16 и подаются в качестве разрешающих 5 сигналов в моменты вызова из допол802967 нительного блока 13 соответствующих постоянных коэффициентов L. приведен1 ных формул. Значение штрафной функции М„ в соответствующем разряде сдвигающего регистра 16 разрешает, либо запрещаЕт считывание с выхода дополнительного блока 13 соответствующего постоянного коэффициента

1 при формировании каждого члена алгебраической суммы парных произведений L; 51цпХ„ при вьчислении очередной частной производной (О

az, Таким образом„ процесс минимизации целевой функции будет осуществляться только за счет тех составляющих Х вектора сдвигов Х, для ко- 15 торых функции штрафов 9, = 1, т.е. которые не удовлетворяют своим ограничениям.

В изобретении совокупность новых элементов и связей реализует миними- щ зацию целевой функции следующего вида, п т и A = С А.= Е". «Х„-р,.)LL ;+(ÕÌ)Þ;)

1 =. " 1=.1

Структура такой целевой функции, благодаря введению штрафных сигнумфункций %„-переменная. Это обеспечивает большую гибкость процесса минимизации, т.е. этот процесс осуществляется за счет уменьшения именно .тех составляющих Х., которые выходят

1 за рамки своих ограничений (для них, соответствующие М,= 1).

Такая концепция позволяет получать решение значительно быстрее (процесс минимизации сходится за меньшее число итераций) и лучшего качества. В самом деле, первое допустимое решение фиксируется при достижении значения целевой функции A нулевого значения. При этом сумма модулей самих 40 сдвигов может оставаться достаточно большой, а значит сохранится "резерв" невязок 2;, т.е. отклонение вектора невязок 2 от своего нулевого (идеального с точки зрения качества пути) 4 значения минимально.

Методы штрафных функций широко применяются при решении задач математического программирования, s том числе и в сочетании с обобщенным гра- ® диентным методом. Однако при решении задачи расчета микроплана железнодорожного пути реализация этого метода программным путем требует непозволительных затрат времени.

Изобретение позволяет аппаратными средствами автоматически формировать на каждой итерации соответствующую структуру целевой функции с целью 6олее быстрого и качественного расчета микроплана пути. Формирование структу- 60 ры целевой функции и последующий расчет частных производных вектора сдвигов по приращениям невязок происходит одновременно с основными расчетами, не отнимая ни единого такта машинного времени. Это позволяет достичь цели предлагаемого изобретения — получения с помощью незначительных затрат оборудования повышения качества и уменьшения времени решения задачи расчета микроплана железнодорожного пути. Решение тестовых задач позволило получить усредненные данные о производительности предлагаемого устройства и качества получаемых решений. Время решения задач сократилось на 30% (в среднем), а качество решения по критерию плавности пути выше на 30-40% по сравнению с решением тех же задач с помощью устройствапрототипа. Проведенные испытания на специализированной вычислительной машине, разработанной и изготовленной по данному изобретению, подтверждает более высокую эффективность устройства, которое можно использовать в качестве бортового вычислителя, обеспечивающего повышенное качество и скорость решения задачи выправки железнодорожного пути в реальном масштабе времени работы путерихтовочного комплекса. Устройство может быть также использовано при построении специализированных вычислительных машин для решения больших систем линейных неравенств, задач управления технологическими процессами и задач исследования операций.

Формула изобретения

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

708355, кл. G 06 F 15/20, 21.07.77 (прототип).

802967

Тираж 756 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 10625/62

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Составитель Ю. Власенко

Редактор E. Гончар Техред Т. Маточка Корректор Е. Папп