Устройство для решения целочисленных задач математического программирования

СОЮЭ СОВЕТСНИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИК А 1 2 15/20 1)5 С ОПИСАНИЕ ИЗОБРЕТЕ ДЛЯ РЕШЕНИЯ ЦЕ,ПОЧ 1 АТИЧЕСКОГО ПРОГтносится к вычислиможет быт ия целочисл ь испольенных заграммирования тся повьппенне вля ключения и сч ГОсудАРстВенный нОмитетП 0 ИЗСБ ЕТЕНИйМ И О 1 РЫТИПРИ ГКНТ СССР(21) 4621097/24 (22) 16.12.88 (46) 2802.91.Бюл. Р 8 (72) АЛ.Веревкин и И.Н.Иаркова (53) 681.325 (088.8) (56) Авторское свидетельство СССР Р 1180925, кл. С 06 Р 15/20, 1984Авторское свидетельство СССР И 1534468, кл. С 06 Р 15/Зб, 198811(54) УСТРОЙСТВОЛЕННИХ ЗАЦАЧ МАТРАИИИРОВАН ИЯ(57) Изобретениетельной техникезовано для решендач математическ1 елью изобретенибыстродействия з1631552 50 рассмотрения заведомо непригодныхкомбинаций при сохранении полноты перебораПоставленная цель достигается тем, что в устройство для решения целочисленных задач математического программирования, содержащее регистр 1, схему сравнения 2, узел сумИзобретение относится к вычислительной технике и может быть использовано для решения целочисленных задач математического программирования,1 ель изобретения - повышение быстродействия за счет исключения из рассмотрения заведомо непригЬдных комбинаций с сохранением полноты пере-бора.На фиг.1 изображена структурная схема устройства; на фиг.2 - структурная схема блока анализа; на25 фиг.З - структурная схема узла суммирования; на фиг.4 - траектория движения при решении трехмерной задачи.Устройство содержит регистр 1, схему 2 сравнения, узел 3 суммирования, элемент И 4, группу регистров 5,30 коммутаторы 6, блоки 7 анализа, триггеры Я, селекторы 9, счетчики 10, тактовй вход 11, информационные вы-. ходы 12 и выход 13 окончания решения задачи.35Узлы 5 - 10 со своими связями образуют блоки 14 и 15 формирования комбинаций, Блок 7 анализа содержит элементы И 16-18, триггер 19 элементы ИЛИ 20 и 21, элемент 22 неравнозначности, информационный вход 23, тактовый вход 24, управляющие входы 25-27 и выходы 28 и 29.Узел 3 суммиРования содержит ком бинационный сумматор 30, регистр 31, информационньп вход 32, выход 33 первого знакового разряда, выход 34 старших разрядов, выход 35 младших разрядов, выход 36 второго знакового разряда и управляющий вход 37.Устройство предназначено для решения задач, математическая постановка которых имеет следующий вид; найти а = 1Т, удовлетворяющие условию; 0 с Ч, Ч,Т= Ч -,Р а,ч 0(а;И;, а; - целое. 1= мирования 3, элемент И 4, группы изТ регистров 5 (где Т - размерностьзадачи), Т коммутаторов 6, Т блокованализа 7, Ттриггеров 8, Т селекторов 9 и Т счетчиков 1 О, введены новые связи между блоками. 4 ил. Устройство работает следующим образом.В исходном состоянии все счетчики 10 обнулены, в регистры 5 записаны значения ч в регистр 1 - Д , в узел 3 суммирования - Ч, триггеры 19 находятся в нулевом состоянии (запрета изменения содержимого счетчика 10 нет), триггеры 8 - в нулевом состоянии (режим суммирования).Устройство работает в три этапа. Первьп этап происходит по переднему фронту тактового импульса. При этом изменяется (на единицу) одно из а и соответствующее ч в соот ветствующем коде подается на вход узла 3 суммирования. При возникновении переносов изменяются режимы работы блоков 15 (+ или -), т,е. триггеры 8 перебрасываются. На втором этапе происходит формирование очередного значения оЧ,на комбинационном сумматоре 30, а необходимые признаки подаются на входы блоков 7 анализа. На третьем этапе по заднему фронту тактового импульса происходит запись нового значения й Ч в регистр 31 и оценка в узлах 2 и 4 полученного значения, Кроме того, в необходимое состояние устанавливаются триггеры 19. которые определяют, какой из ае будет изменяться на следующем шаге. Рассмотрим работу устройства на примере решения трехмерной задачи (Т=З) со сАедующими начальными условиями: ч 1= ч= ч э = 1= Н 9 = 4, Ч = 4,5, Ь = 0,25. Данная задача является вырожденной и ее Решения не существует. На ней удобно продемонстрировать все основные режимы работы устройства.В начальный момент а= а = а= = 0 траектория движения находится в начале координат (фиг.4). Триггер 191631552 первого блока 7 анализа обнулен, поэтому первый тактовый импульс ьп Ф(передний фронт) поступает через первый коммутатор 6 навход первого счетчика 10,В узле 3 суммирования записано положительное число Ч = Чо,на выходах 33 и Зб знаковых разрядов - ноль. Поэтому сигнал с выхода 33 устанавливает суммируюций режим работы счетчика 10 и обеспечивает передачу ч., на вход узла 3 суммирования в обратном коде. Таким образом, по ь содержимое первого счетчика 10 увеличивается на единицу, первьп селектор 9 подключается к входу 32 узла суммирования и на комбинационном сумматоре 30 начинается формирование величины 3 Ч = Ч - ч 1. В результате осуществил ся переход в точку 1 фиг.4. Поскольку смены знака о Ч не произошло, то на выходе элемента 22 неравнозначности в первом блоке 7 анализа - ноль, элемент И 16 закрыт. По заднему фронту тактового импульса , оЧ 1 записывается в регистр 31 и появляется на выходах 33 - 35, Если в некоторый момент оказалось, что получено значение Ч (на выходе 33 - нуль), в ,старших разрядах Ч - нули (на выходах 34 - нули), а величина, записан ная в младших разрядах (выход 35), меньше , то на выходе схемы 2 сравнения и элемента И 4 появляются единицы. Последняя свидетельствует о том что решение найдено - выход 13. Поскольку после первого тактового импульса условия не изменились, то второй тактовый импульс выполняет те же действия с той лишь разницей, что в первом счетчике 10 оказывается двойка а в узле 3 суммирования - величина Ь = Ч - ч - ч(точка 2,фиг.4). Аналогичное увеличение апродолжается до тех пор, пока по очередному ,и в первом счетчике 10 не окакется а = М. При этом, поскольку )Ч) О, на выходе элемента И 18 первого блока анализа 7 появляется единица, свидетельствующая о том, что первый счетчик 10 не может выполнить операцию увеличения своего содержимого. Этот сигнал, пройдя элементы ИЛИ 21 и 20, поступает на установочньпЪ вход триггера 19 первого блока анализа 7 и по ь, поступающему с входа 24,и,Лустанавливает триггер 19 в единичное состояние. При этом в узле 3 суммирования накоплено значение о Ч 4 == Ч - М ч (точка 4, фиг. 4), Следующий тактовый импульс, не изменяяа, проходит через первый коммутатор 56. поступает на второй блок 15 и поп выполняет те же действия, но свеличинами аи ч. На втором этапево втором счетчике (а) оказываетсяединица в регистре 31 - о Ч ) 0а на выходе комбинационного сумматора 30 - 3 У с 0 (точка 5 фиг.4).Последнее приводит к тому, что навыходе элемента И 18 первого блокаанализа 7 оказывается ноль. Несмотря 15 на то, что произошла смена знака 3 Чи на выходе элемента 22 неравнозначности первого блока 7 анализа имеется единица, но из-за отсутствиятактового сигнала на входе 27 первогоблока 7 анализа, на выходе И 16 прилсутствует ноль. В результате по сутриггер 19 первого блока анализавновь устанавливается в нулевое сос-.тояние, а в регистр 31 записываетсядч - одч = оЧ,-" ч (О. Сигнал с выхода33 устанавливает вычитающий режим работы первого счетчика 10 и режим передачи через первый селектор 9 в прямом коде. Следующий тактовый импульс 30 вычитает единицу из аи формируетоЧ = Ч - И ч - ч,+ ч, )О (точка 6).Происходит смена знакаЧ, на выходе элемента 22 неравнозначности первого блока 7 анализа появляется еди- , 35 ница, а поскольку это изменение былосвязано с величиной а - на входе 27первого блока 7 анализа присутствуеттактовьп сигнал, то на выходе элемента И 16 появляется единица, кото рая, пройдя элемент ИЛИ 20, по сзлустанавливает триггер 19 в единичноесостояние. По следующему тактовомуимпульсу изменяется а и происходитпереход в точку 7 и т.д. Наконец на 45 12-м шаге (фиг.4) оказывается, чтоа -- И а= О, а 1 Ч)О, На выходе элементов Й 16 и 17 первогоблока 7 анализа имеются единицы,следовательно, триггер 19 по 2 ока зывается в единичном состояниии в следующем такте анеизменяется. Во втором блоке анализана выходе элемента И 1,8 имеетсяединица, поскольку режим работы вто рого счетчика 10 - суммирующий (состояние первого триггера 8) а а = М.Поэтому по . триггер 19 оказываетсяЛв едйничном состоянии и обеспечиваетпрохождение следуюцего тактового им 1631552пульса к следующему блоку 15 (а).Тринадцатый тактовый импульс,пройдя первый и второй коммутаторы,поперебрасывает первый триггер 8Пи переводит блок 15 в вычитающий режим работы счетчика 10 и в режим передачи прямым кодом % через второйселектор 9.Поступив на второй блок 15, 10тактовый импуЛьс увеличивает на еди. ницу аи Формирует суммуЧ (О(Ьиг.4). Так как 3 Ч с О, а = О, топоединица с выхода элемента И 17устанавливает триггер 19 первогоблока анализа в единицу, запретивизменение а на 14-м шаге. Вычитающий режим первого блока 15 (состояние триггера 8) и в ЧО приводятк тому, что.на выходе элемента 22 20неравнозначности и элемента И 16,а также на выходе элемента И 18 второго блока 7 анализа присутствуютнули, поэтому триггер 19 оказывается в нулевом состоянии и на 14-м шаге 25происходит уменьшение а (точка 14),По д этого импульса разрешаетсяизменение а 1 и происходит процесс,аналогичныи описанному.Наконец, последний вариант режима работы устройства возникает на29-м шаге, при котором а= О, а(ИЬс О и происходит смена знака РЧ,При этом поиз-за единицы на выходе элемента И 18 первого блока 7анализа триггер 19 запрещает изменение а,. Единица с выхода 29 первогоблока 7 анализа поступает на вход 27второго блока 7 анализа, Режим работыблока 15 - суммирующий (на выходе 40триггера 8 ноль), а если 1 Ч Ото на выходе элемента 22 неравнозначности и элемента И 16 второго блокаанализа 7 появялется единица, котораяустанавливает триггер 19 в ноль и 45запрещает изменение а. Таким образом, увеличение а до достижения И(а это в данном случае нецелесообразно) не происходит.сОстальная процедура поиска решения происходит аналогично.Признаками окончания работы устройства являются либо появление признака нахождения решения с выхода 13,либо возникновение переноса,из старшего блока 15, свидетельствующегооб отсутствии решения при заданныхусловиях. Формула изобретения Устройство для решения целочисленных задач математического программирования, содержащее регистр, схему сравнения, узел суммирования, элемент И, группу из Т регистров (где Т - размерность задачи), Т коммутаторов, Т блоков анализа, Ттриггеров, Т селекторов и Т счетчиков, причем счетный вход К-го (К =1Т) счетчика соединен с первым входом К-го коммутатора, информационный выход К-го счетчика подключен к информационному входу К-го блока анализа и является К-м инйормационным выходом. устройства, выход К-го регистра группы соединен с информационным входом К-го селектора, выход которого подключен к информационному входу узла суммирования, тактовый вход первого блока анализа соединен с управляющим входом узла суммирования и является тактовым входом устройства, выход млад - них разрядов узла суммирования подключен к первому входу схемы сравнения, управляющий вход М-го (М=2Т) селектора соединен с выходом (М)-го триггера, выход регистра подключен к второму входу схемы сравнения, выход которой соединен с первым входом элемента И, выход старших разрядов и выход первого знакового разряда узла суммирования подключены соответственно к второму и третьему входам элемента И, выход которого является выходом окончания решения задачи устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия за счет исключения из рассмотрения заведомо непригодных комбинаций при сохранении полноты переборй, выход второго знакового разряда узла суммирования соединен с первым управляющим входом К-го блока анализа, первый выход которого подключен к управляющему входу К-го коммутатора, первый выход К-го коммутатора соединен с входом подключения К-го селектора, второй выход Н-го (Н=1 Т) коммутатора соединен с информационным входом (Н+1)-го коммутатора и тактовым входом (Н+1)-го блока анализа, выход первого знакового разряда узла суммирования подключен к управляющему входу пррвого селектора, управляющему входу первого счетчика и второму управляющему входу первогоблока анализа, третий управляющий вход которого соединен с первым выходом первого коммутатора, информационный вход первого коммутатора подключен к тактовому входу первого блока анализа, второй выход Н-го блока анализа соединен с третьим управ 2 У ляющим входом (Н+1)-го блока анализа, второй выход М-го коммутатора подключен к счетному входу (М)-го 5триггера, выход которого соединен с управляющим входом М-го счетчика и, вторым управляющим входом М-го блока анализа.1631552 Составитель В.ЕсиповРедактор Л.Пчолинская Техред Л.Сердюкова. Корректор М.Иаксимишинец Заказ 547 Тираж 402 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 1 3035 р МоскваЖ, Раушская наб ., д, 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101