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

 

ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ РЕЫЕНШ ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ, содержащее К цифроаналоговых преобразователей , первую и вторую схемы сравнения , К счетчиков, выходы разрядов каждого из которых подключены к входу соответствукицего цифроаналогового преобразователя и к первому информационному выходу устройства, счетный вход первого счетчика соединен с тактовым входом устройства, выход первой схемы сравнения является выходом сигнала окончания решения , отличающееся тем, что, с цепью повышения точности, в него введены сумматор, К - 1 1 фроаналоговых преобразователей, К -1 схем сравнения и К - 1 счетчиков, элемент И, элемент ШШ и If - 2 блоков памяти, адресный вход каждого из которых соединен с выходами разрядов соответствукяцего счетчика. вход записи соединен с входом разрешения записи устройства, установочные входы счетчиков соединены с установочным входом устройства, выход i -го ( 1 2, К - 1) блока памяти соединен с входом сброса i -го счетчика, со счетным входом (i + + 1)-го счетчика и с входом считывания ( + 1)-го блока памяти, выход К-го блока памяти соединен с входом сброса К -го счетчика и с вторым информационным выходом устройства, входы сумматора соединены с выходами цифроаналоговых преобразователей, кроме последнего, и информационным входом устройства, выход последнего (/) цифроаналогового преобразователя соединен с первым информационным входом первой схемы сравнения, выход сумматора соединен с вторым информационным входом первой схемы сравнения и с информационным входом второй схемы сравнения, разрешакжщй вход которой, первый вход элемента И и вход считывания первого блока памяти соединен с тактовым входом устройства, выход элемента И соединен с разрешающим входом первой схемы сравнения, выход второй схемы сравнения соединен с вторым входом элемента И и с первым входом элемента ИЛИ, второй вход которого соединен с выходом первого блока памяти, выход элемента ШШ соединен с входом сброса первого счетчика, с входом считывания второго блока памяти и со счетным входом второго счетчика, выходы разрядов К - 1 счетчиков подключены к входу соответствующего цифроаналогового преобразователя и к первому информационному выходу ycTpojicTBa.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (! 9) (}1) (51)4 G 06 F 15/32 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPGHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3726261/24-24 (22) 10. 04 ..84 (46) 23.09.85. Вюл. Ф 35 (72) И.Н.Маркова, А.10.Веревкин и О.А.Иишенин (71) Ленинградский ордена Трудового

Красного Знамени институт текстильной и легкой промышленности им. С.М.Кирова (53) 681.325(088.8) (56) Авторское свидетельство СССР

)(» 970381, кл. Cj 06 F 15/324, 1980.

Грем Дж. и др. Проектирование и применение операционных усилителей.

M.: Мир, 1974, с. 369. (54)(57) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО

ДЛЯ РЕШЕНИЯ ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ, содержащее K цифроаналоговых преобразователей, первую и вторую схемы сравнения,. K счетчиков, выходы разрядов каждого из которых подключены к входу соответствующего цифроаналогового преобразователя и к первому информационному выходу устройства, счетный вход первого счетчика соединен с тактовым входом устройства, выход первой схемы сравнения является выходом сигнала окончания решения, о т л и ч а ю ц е е с я тем, что, с целью повышения точности, в него введены сумматор, K — 1 цифроаналоговых преобразователей, К -1 схем сравнения и K — 1 счетчиков, элемент И, элемент ИЛИ и »(— 2 блоI ков памяти, адресный вход каждого из которых соединен с выходами разрядов соответствуюцего счетчика, вход записи соединен с входом разрешения записи устройства, установочные входы счетчиков соединены с установочным входом устройства, выход » -го (» = 2, K — 1) блока памя1 ти соединен с входом сброса » -го счетчика, со счетным входом (» +

+ 1)-ro счетчика и с входом считывания (» + 1)-го блока памяти, выход

K-ro блока памяти соединен с входом сброса К -ro счетчика и с вторым информационным выходом устройства, входы сумматора соединены с выходами цифроаналоговых преобразователей, кроме последнего, и информационным входом устройства, выход последнего цифроаналогового преобразователя соединен с первым информационным входом первой схемы сравнения, выход сумматора соединен с вторым информационным входом первой схемы сравнения и с информационным входом второй схемы сравнения, разрешаюций вход которой, первый вход элемента И и вход считывания первого блока памяти соединен с тактовым входом устройства, выход элемента И соединен с разрешаюцим входом первой схемы. сравнения, выход второй схемы сравнения соединен с вторым входом элемента И и с первым входом элемента

ИЛИ, второй вход которого соединен с выходом первого блока памяти, выход элемента ИЛИ соединен с входом сброса первого счетчика, с входом считывания второго блока памяти и со счетным входом второго счетчика, выходы разрядов К вЂ” 1 счетчиков подключены к входу соответствуюцего цифроаналогового преобразователя и к первому информационному выходу устройства.

1180925 г

Изобретение относится к вычислительной технике и может быть использовано для решения целочисленных задач математического программирования типа: найти 5

mingy, i = 1, k (1) и!

npH SL = Ь (n;P! + n + ° ° ° +

„1„) О, (2) !О где п1 — целое, 0 п И;, 8 Ь 81„

Ь, N — заданные величины.

Такие задачи возникают, например, 15 при необходимости раскроя с минимальными остатками материала длины Ь на заготовки, длины которых, и потребное количество каждого типа И .

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

На чертеже представлена схема устройства.

Устройство содержит счетчики 1 и

2, цифроаналоговые преобразователи (ЦАП) 3 и 4, схемы 5 и 6 сравнения, 25 блоки 7 и 8 памяти, сумматор 9, элемент ИЛИ 10, элемент И 11, входы 1214 устройства, выходы 15-18 устройства, входы 19 и 20 устройства.

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

В исходном состоянии блоки 7 и 8 памяти Обнулены, на вход 19 подано напряжение, пропорциональное величи- З5 не L коэффициенты передачи сумматора 9 установлены пропорционально величинам Р . Для подготовки устройст1 ва к работе íà i-й счетчик с входа

13 записывается код,равный максималь- 40 . ному количеству отрезков t длины

N<, а на счетчик 2 с входа 14 — код, пропорциональный 3Ь„„„., после чего с входа 20 на вход записи блоков памяти подается импульс, обеспечивающий запись единицы в блоки 7 и 8 па-, мяти, причем в i-й блок памяти единица записывается по адресу И(, а в блок 8 памяти rto адресу, равному, ЯЬ„,„ 50 где — вес единицы младшего разряда счетчика 2. Таким образом, каждый счетчик и соответствуюций блок памяти образуют счетчик с заданным числом пересчета. После установ- 55 ки чисел пересчета счетчики 1 и 2 сбрасываются путем записи нулевого кода через установочные входы 13 и 14. Устройство готово к решению з адачи.

На вход 12 поступает тактовый импульс, он увеличивает на единицу содержимое первого счетчика. его код поступает. на первый ЦАП, на выходе которого появляется сигнал, пропорциональный п<. Поскольку коэффициент передачи сумматора 9 равен то на выходе сумматора 9 появляется сигнал, пропорциональный gL =

= Ь вЂ” и P! . Сигнал с входа 20 задним фронтом читает содержимое первого блока 7 памяти и разреыает сравнение на схеме 5. Так как выходное напряжение сумматора 9 больше нуля, то сигнала с выхода схемы 5 не будет, элемент И 11 открыт. По сигналу с него схема 6 сравнивает K L с текущим допустимым значением ошибки и выдает сигнал на выход 17, если Ь < 8L, т. е. искомое решение

111ЕК найдено, при этом коды со счетчиков

1 на выходах 15 представляют собой значения и;, а коды на выходе 16 ошибку решения задачи (1), т.е. g L.

Если решение не найдено, то следуюций импульс с входа 12 увеличит на единицу содержимое первого счетчика 1, процесс повторится. Пусть в некоторый момент на счетчике появится код п ) И;, тогда единичный сиг-. нал с блока 7 памяти сбросит этот счетчик 1, прибавит единицу к сле— дующему счетчику 1 и прочтет содержимое соответствующей ячейки блока 7 памяти. При этом, если в следующем счетчике 1 п, + 1 > И; + 1, то сигнал переноса с блока 7 памяти сбросит этот счетчик и поступит на следующий счетчик. Таким образом, на счетчиках 1 будут последовательно перебираться всевозможные сочетания и И.. Если на некотором. шаге ока1 1 залось, что Я Ь О, то сигнал с выхода схемы 5 закроет элемент И 11, запрецая работу схемы 6, и, проходя через элемент ИЛИ 10, выполнит те же действия, что и сигнал с блока 7 памяти.

Если после полного перебора комбинации на счетчиках 1 решение не было найдено, то сигнал переноса с последнего блока 7 памяти увеличит допуск на счетчике 2 и процесс по- ° иска повторится. Когда код ча счетчике 2 превысит максимум, то сигнал

Составитель А.Жеренов

Редактор P.Öèöèêà Техред А.Бабииец Корректор С.Черни

Заказ 5928/49

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

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

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

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

3 11 с выхода блока 8 памяти поступит на выход 18 и будет свидетельствовать о невозможности решения задачи с заданными ограничениями, Таким образом, устройство реализует алгоритм полного перебора вариантов решения с последовательным уменьшением точности решения. Если решение задачи (1) существует, то оно будет гарантированно найдено, причем с наилучшей точностью. Не изменяя структурную схему устройства можно получить другой, более быстрый алго- ритм решения задачи (1). Дпя этого

80925 4 в исходном состоянии на счетчик 2 . записывается 5 Ь и обеспечивается

его работа в режиме вычитания. В результате, если решение задачи (1)

5 существует, то оно получается более быстро.

Дальнейшая работа устройства обеспечит поиск решения с меньшим 8 L.

10 . Если решение с 6 Ь „ не получено (не появился сигнал .на выходе 17), то сигнал на счетном входе счетчика

2 свидетельствует о невозможности решения задачи (1).