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

)4 С 06 Р 15/32 15/2 ОПИСАНИЕ ИЗОБРЕТЕНИЯ ТЕЛЬСТВ К АВТОРСКОМУ.10. Ве к Трудового текстильи о ститупавленко етельство СССР Е 15/324, 1980. 56) Авторское с970381, кл. очности,1 цифГОСУДАРСТВЕННЫЙ НОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ Грем Дж. и др. Проектирование и применение операционных усилителей. М.: Мир, 1974, с. 369.(54) (57) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВОДЛЯ РЕШЕНИЯ ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ ИАТЕИАТИЧЕСКОГО 11 РОГРАММИРОВАНИЯ, содержашее К цифроаналоговых преобразователей, первую и вторую схемы сравнения,. К счетчиков, выходы разрядовкаждого из которых подключены квходу соответствующего цифроаналогового преобразователя и к первому информационному выходу устройства,счетный вход первого счетчика соединен с тактовым входом устройства,выход первой схемы сравнения является выходом сигнала окончания решения, о т л и ч а ю ц е е с ятем, что, с целью повышения тв него введены сумматор, К -роаналоговьпс преобразователей, К -1схем сравнения и 1( - 1 счетчиков,элемент И, элемент ИЛИ и К - 2 блоков памяти, адресный вход каждогоиз которьос соединен с выходамиразрядов соответствуюцего счетчика,вход записи соединен с входом разрешения записи устройства, установочные входы счетчиков соединены с установочным входом устройства, выход-го (= 2, К - 1) блока памя 1 ти соединен с входом сброса-го счетчика, со счетным входом (+ + 1)-го счетчика и с входом считывания (+ 1)-го блока памяти, выход 1-го блока памяти соединен с входом сброса К -го счетчика и с вторым информационным выходом устройства, входы сумматора соединены с выходами цифроаналоговых преобразователей, кроме последнего, и информационнымФ входом устройства, выход последнего цифроаналогового преобразователя соединен с первым информационным входом первой схемы сравнения, выход сумматора соединен с вторым информационным входом первой схемы сравнения и с информационным входом второй схемы сравнения, разрешаюнийвход которой, первый вход элемента И и вход считывания первого блока памяти соединен с тактовым входом устройства, выход элемента И соединен с разрешаюцим входом первой схемы. сравнения, выход второй схемы сравнения соединен с вторым входом элемента И и с первым входом элемента ИЛИ, второй вход которого соединен с выходом первого блока памяти, выход элемента ИЛИ соединен с входом сброса первого счетчика, с входом считывания второго блока памяти и со счетным входом второго счетчика, выходы разрядов К - 1 счетчиков подключены к входу соответствуюцего цифроаналогового преобразователя и к первому информационному выходу устройства.Изобретение относится к вычислительной технике и может быть использовано для решения целочисленных задач математического программирования типа: найти 5пппб., 1 = 1, 1 с (1) при ВЬ = Ь - (и;Р, + и,.Р +++ п 1)О, (2) О где п - целое, 0и1;, 8 Ь31, Б- заданные величины.Такие задачи возникают, например, при необходимости раскроя с минималь 15 ными остатками материала длины Ь на заготовки, длины которых , и потребное количество каждого типа И.Цель изобретения - повышение точности работы устройства.20На чертеже представлена схема устройства.Устройство содержит счетчики 1 и 2, цифроаналоговые преобразователи (ЦАП) 3 и 4, схемы 5 и 6 сравнения,25 блоки 7 и 8 памяти, сумматор 9, элемент ИЛИ 10, элемент И 11, входы 12- 14 устройства, выходы 15-18 устройства, входы 19 и 20 устройства.30Устройство работает следуюцим образом.В исходном состоянии блоки 7 и 8 памяти Обнулены, на вход 19 подано напряжение, пропорциональное величи не Ь, коэффициенты передачи сумматора 9 установлены пропорционально величинам ь; . Для подготовки устройства к работе на -й счетчик с входа 13 записывается код,равный максимальному количеству отрезковдлины И;, а на счетчик 2 с входа 14 - код, пропорциональный 3 Ьм , после чего с входа 20 на вход записи блоков памяти подается импульс, обеспечиваю щий запись единицы в блоки 7 и 8 па-, мяти, причем в -й блок памяти единица записывается по адресу И, а в блок 8 памяти по адресу, равному з БфМауС. 50мак где д - вес единицы младшего разряда счетчика 2. Таким образом, каждый счетчик и соответствуюций блок памяти образуют счетчик с заданным числом пересчета. После установ ки чисел пересчета счетчики 1 и 2 сбрасываются путем записи нулевого кода через установочные входы 13 и 14. Устройство готово к решению з адачи.На вход 12 поступает тактовый импульс, он увеличивает на единицу содержимое первого счетчика. Его код поступает. на первый ЦАП, на выходе которого появляется сигнал, пропорциональный п. Поскольку коэффициент передачи сумматора 9 равенто на выходе сумматора 9 появляется сигнал, пропорциональный 3 Ь = = Ь - п 1. Сигнал с входа 20 задним фронтом читает содержимое первого блока 7 памяти и разреыает сравнение на схеме 5. Так как выходное напряжение сумматора 9 больше нуля, то сигнала с выхода схемы 5 не будет, элемент И 11 открыт. По сигналу с него схема 6 сравнивает о Ь с текущим допустимым значением ошибки и выдает сигнал на выход 17, еслиЬ, т. е. искомое решениемекфнайдено, нри этом коды со счетчиков 1 на выходах 15 представляют собой значения и;, а коды на выходе 16 ошибку решения задачи (1), т.е. о 1" Если решение не найдено, то следуюций импульс с входа 12 увеличит на единицу содержимое первого счетчика 1, процесс повторится. Пусть в некоторый момент на счетчике появится код п ) И;, тогда единичный сиг-. нал с блока 7 памяти сбросит этот счетчик 1, прибавит единицу к следующему счетчику 1 и прочтет содержимое соответствующей ячейки блока 7 памяти. При этом, если в следующем счетчике 1 п , + 1М, + 1, то сигнал переноса с блока 7 памяти сбросит этот счетчик и поступит на следующий счетчик, Таким образом, на счетчиках 1 будут последовательно перебираться всевозможные сочетания п ь И . Если на некотором. шаге оказалось, что 6 Ь с О, то сигнал с выхода схемы 5 закроет элемент И 11, запрецая работу схемы 6, и, проходя через элемент ИЛИ 10, выполнит те же действия, что и сигнал с блока 7 памяти.Если после полного перебора комбинации на счетчиках 1 решение не было найдено, то сигнал переноса с последнего блока 7 памяти увеличит допуск на счетчике 2 и процесс по-иска повторится. Когда код ча счетчике 2 превысит максимум, то сигнал80925 4 в исходном состоянии на счетчик 2 записывается 5 Ь и обеспечивается его работа в режиме вычитания. В результате, если решение задачи (1)5 существует, то оно получается более быстро. Дальнейшая работа устройства обеспечит поиск решения с меньшим оЬ, 10 . Если решение с 6 Ьне получено(не появился сигнал .на выходе 17),то сигнал на счетном входе счетчика2 свидетельствует о невозможностирешения задачи (1). Составитель А.ИереяР.Цицика Техред А.Бабииец едак ректор С.Чер каэ 5928/49 Тираж 709 ВНИИПИ Государств по делам изобре 113035, Москва, Ж, Подписноеного комитета СССРний и открытийаушская наб., д. 4/ ППП "Патент Фил з 11 с выхода блока 8 памяти поступит на выход 18 и будет свидетельствовать о невозможности решения задачи с заданными ограничениями, Таким образом, устройство реализует алгоритм полного перебора вариантов решения с последовательным уменьшением точности решения. Если решение задачи (1) существует, то оно будет гарантированно найдено, причем с наилучшей точностью. Не изменяя структурную схему устройства можно получить другой, более быстрый алго- ритм решения задачи (1). Для этого Ужгород, ул. Проектная, 4