Вычислительное устройство для решения целочисленных задач математического программирования Советский патент 1985 года по МПК G06F17/10 G06F17/11 

11

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

min 6 L , i 1, k

(О

n:

приВь L - (n; , + ttj Ij + ... +

+ n IJ 0,

(2)

где n; - целое, N-, 8 L 6 ,

L, e; ,

N - заданные величины.

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

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

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

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

I

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

В исходном состоянии блоки 7 и 8 памяти Обнулены, на вход 19 подано напряжение, пропорциональное величине L, коэффициенты передачи сумматора 9 установлены пропорционально величинам f; . Для подготовки устройства к работе на i-й счетчик с входа . 1 3 записывается код,равный максимальному количеству отрезков t длины NJ, а на счетчик 2 с входа 14 - код, пропорциональньи 5Ьд,а ., после чего с входа 20 на вход записи блоков памяти подается импульс, обеспечиваю- .щий запись единицы в блоки 7 и 8 памяти, причем в i-й блок памяти единица записывается по адресу Nj, а в блок 8 памяти по адресу, равному

SL

где Л - вес единицы младшего Д

разряда счетчика 2. Таким образом, каждый счетчик и соответствувядий блок памяти образуют счетчик с заданным числом пересчета. После установки чисел пересчета счетчики 1 и 2 сбрасываются путем записи нулевого кода через установочные входы 13

9252

и 14. Устройство готово к решению задачи.

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

t , то на выходе сумматора 9 появляется сигнал, пропорхщональный pL L - n.f,. Сигнал с входа 20 задним фронтом читает содержимое первого блока 7 памяти и разрешает сравнение

на схеме 5. Так как выходное напря- i жение сумматора 9 больше нуля, то сигнала с выхода схемы 5 не будет, элемент И 11 открыт. По сигналу с него схема 6 сравнивает SL с текущим допустимым значением ошибки и вьщает сигнал на выход 17, если

SL , т.е. искомое решение

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

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

Если решение не найдено, то следующий импульс с входа 12 увеличит

на единицу содержимое первого счетчика 1 , процесс повторится. Пусть в некоторый момент на счетчике появится код nj N, , тогда единичный сиг-, нал с блока 7 памяти сбросит этот

счетчик 1, прибавит единицу к следующему счетчику 1 и прочтет содержимое соответствующей ячейки блока 7 памяти. При этом, если в следующем счетчике 1 пj + 1 Ni + 1, то сигнал переноса с блока 7 памяти сбросит этот счетчик и поступит на следующий счетчик. Таким образом, на счетчиках 1 будут последовательно перебираться всевозможные сочетания

. Если на некотором шаге оказалось, что SLi О, то сигнал с выхода схемы 5 закроет элемент И 11, запрещая работу схемы 6, и, проходя через элемент 1ШИ 10, вьтолнит те

же действия, что и сигнал с блока 7 памяти.

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

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