Устройство для решения целочисленных задач математического программирования Советский патент 1986 года по МПК G06F17/00 

12

содерш1т счетчики 1, 2, предназначенные для перебора всевозможных комбинаций ttj и текущей величины допуска накс т.е. допустимой величины ошибки. Для поиска оптимального решения (5 Ь„д разбивается на М частей

мим йакс В счетчик 2 записывается код т, пропорциональный 5Ь„ 3 в блок памяти по адресу М- единица. В счетчике 2 последовательно перебираются различные значения 5L от 5Ь,„ до L,. Блоки 3, 4 памяти предназначены для формирования сигнала переноса из i-ro разряда в (1+1)-й, если величина Uj превысила NJ, и совместно со счетчиками 1, 2 образуют счетчики с программируемым числом пересчета, цифроаналоговые преобразователи 5 и 6 предназначены для преобразования величин п- .,Ь„

I f МцКС

в айалоговую форму. Сумматор 7 формирует сигнал, пропорциональный SL, он может быть реализован на операциИзобретение относится к вычислительной технике и может быть использовано, например, для раскроя материала с минимальными остатками.

Целью исключения является повышение быстродействия за счет исключения перебора i з.аведомо непригодных комбинаций.

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

Устройство содержит счетчики 1 и 2, блоки 3 и 4 памяти, цифроаналоговые преобразователи (ЦАП) 5 и 6, сумматор 7, схемы 8 и 9 сравнения, зле- мент 10 И, элементы 11 и 12 ИЛИ, элемент 13 И, элемент 14 НЕ, блок 15 формирования переноса, элемент 16 НЕ-И элемент 17 НЕ, элементы 18 и 19 И, информационный вход 20, выходы 21-24, тактовый вход 25 устройства, входы 26 27 и выходы 28, 29 блоков формирования переноса.

Устройство предназначено для решения задач типа найти min SL, ,Tr, при

I -bkn ,t. + ...). О,

888

онном усилителе, имеющем входные сопротивления, обеспечивающие Коэффициент передачи от i-ro ЦАП, пропор- .циональньй I; . Схемы 8, 9 сравнения предназначены для сравнения сигнала, поступающего с сумматора 7, с нулем и с SL.. соответственно при наличии

Мокс

разрешающего сигнала. Элемент 10 И разрешает работу схемы 9 сравнения, если есть сигнал со схемы 8 (SL 0). Элементы 11, 12 ИЛИ передают сигнал переноса из i-ro в (i+1)-й разряд. Элемент 13 И запрещает подачу такто- вых сигналов на первый счетчик 1, когда , Блок 15 формирования переноса предназначен для формирования сигналов переноса из i-ro счетчика в (i+1)-й, обеспечивая при зтом пропуск заведомо непригодных комбинаций п . Блок формирования переноса содержит элемент 16 НЕ-И, элемент 17 НЕ, элементы 18, 19 И. 1 з.п.ф-лы, 1 ил.

где П; - целое, ..; 5Ь 5L,; . L,I j,N(0 - заданные величины.

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

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

В исходном состоянии все счетчики 1, кроме последнего счетчика 2, обнулены. В счетчик 2 записан код т, пропорциональный минимальному значению LMHH которым будет проводиться поиск решения. В i-м блоке 3 памяти записана единица по тому адресу, код которого равен №; (в последнем

М Ь„акс ) Запись этой информации .производится записью кодэ N,- в соответствующий счетчик и подачей сигна- 34- Запись 1 на блоки 3 памяти (эти йходы с целью упрощения не показаны).

На вход 20 подан сигнал, пропорциональный величине L.

На вход 25 устройства поступает тактовый сигнал и, если элемент 13 И

открыт, увеличивает на единицу содержимое первого счетчика 1. Его код поступает на первый ЦАП 5, на выходе которого появляется сигнал, пропорциональный п,. Поскольку коэффициент передачи сумматора 7 по первому вход равен I , то на выходе сумматора 7 появляется сигнал SL - п Г) . Тактовьй сигнал 25 разрешает сравнение на схеме 8 сравнения. Если (L-n,I ) О , то выходной сигнал схемы 8, пройдя через элемент 10 И, разрешает сравнение на схеме 9 сравнения. Если 6L - 5 (последнее . поступает со счетчика 2 через ЦАП 6) то сигнал на выходе 23 означает, чт искомое решение найдено и с выходов 21 может быть считано значение п , а с выхода 24 - значение SL , при котором это решение найдено.

Если решение не найдено, то к первому счетчику 1 вновь прибавляется единица и процесс повторяется. Пусть. в некоторый момент в i-м счетчике 1 величина п N,- , тогда единица, считьшаемая из соответствующего блока 3 памяти, пройдя элементы 11 и 12 ИЖ, сбрасывает этот i-й счетчик и прибавляет единицу к (1+1)-му счетчику. Таким образом, обеспечива- ется условие п- 6N.. Если решение с 5Ъ не найдено, то аналогичным образом увеличивается содержимое счетчика 2, а следовательно, SL. При т5 сигнал с блока 4 памяти поступает на выход 24 устройства, что свидетельствует о невозможности нахождения решения с заданным L Пусть в некоторый .момент времени значение 5L, полученное на выходе сум- матора 7, меньше нуля, тогда сигнал с выхода схемы 8, пройдя через элемент 14, не закрывает элемент 13 И и прекращает подачу тактовых импульсов на первый счетчик 1 и блок 3 памяти. Кроме того,он поступает на вхгд 27 первого блока 15. Если в данный момент этот счетчик обнулен, то на выходе элемента И 16 появляется единица, которая открывает элемент 19 И и пропускает сигнал переноса на вход 27 следующего блока формирования переноса. Таким образом, сигнал с элемента 14 НЕ минует все счетчики 1, в которых записан код О.Наконец, дос- тигнув нулевого счетчика, этот сигнал проходит элемент 18 И соответствующего блока 15 (который открыт

сигналом с элемента 17 НЕ) и поступа- ет на элемент 11 ИЛИ. В результате его выходной сигнал сбрасывает первый нулевой счетчик 1 с номером i, при- бавляет единицу к следующему (i+1)- ry счетчику и считывает содержимое , . (i+1)-ro блока памяти. Наконец, если причина того, что SL « О, - ненулевое состояние (К-1)-го счетчика 1, или п., N , то выходной сигнал с (К-1)- го элемента 12 ИЛИ, кроме указанных выше действий, устанавливает в некоторое состояние гГ первый счетчик 1. Последнее действие целесообразно произвести, поскольку в этот момент все счетчики 1 обнулены и поиск имеет смысл начинать только с некоторой комбинации ...0. В частности п, может быть равно

{«J-TT-JJ

i. I

целая часть

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

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

вход первого элемента ИЛИ соединен с выходом первого блока памяти, выход первого элемента ИЛИ соединен с входом сброса первого счетчика, с вхо- дом считывания второго блока памяти И со счетным входом второго счетчика, выход К-го блока памяти является вторым информационным выходом ус трой- ства, отличающееся тем, что, с целью повьппения быстродействия за счет исключения перебора заведомо непригодных комбинаций, в него введены элемент НЕ, К-2 элементов ИЛИ, второй элемент И и К-2 блоков форми- рования переноса, первый вход каждо- го из которых, начиная с первого, соединен с выходом соответствующего счетчика, второй вход первого блока формирования переноса соединен с вы- ходом элемента НЕ, второй вход i-ro (i 2, К-2) блока формирования переноса соединен с первым выходом (i-1)- го блока формирования переноса, пер пьш вход -го (, К-1) элемента ИЛИ соединен с. выходом i-ro блока памяти, а выход соединен с входом сброса i-ro счетчика, со счетным входом (1+1)-го счетчика и с входом считывания (i+1)-ro блока памяти, первый выход (К-2)-го блока формирования

Редактор И. Рыбченко Заказ 4128/50

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

Техред М.Ходанич Корректор Е.Сирохман

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

ВНИИГШ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

переноса соединен с вторым входом (К-1)-го элемента ИЛИ, второй выход i-ro (i-1, К.-2) блока формирования переноса соединен с вторым входом i-ro элемента ИЛИ, выход (К-1)-го элемента ИЛИ соединен с установрчным входом первого счетчика, первый вход второго элемента И соединен с тактовым входом устройства, второй вход подключен к выходу элемента НЕ, выход второго элемента И соединен со счетным входом первого счетчика и с входом считывания первого блока памяти, вход элемента НЕ соединен с выходом второй схемы сравнения. I

2. Устройство по п. 1, отличающееся тем, что блок формирования переноса содержит два элемента И, элемент НЕ и элемент НЕ-И, вход которого является первым входом блока, а выход соединен с первым входом первого элемента И и через элемент НЕ - с первым входом второго элемента И, вторые входы первого и второго элементов И соединены с вторым входом блока, выходы первого и второго элементов И являются соответственно первым и вторым выходами блока.

Изобретение относится, к вычислительной технике и может быть использовано, например, для раскроя материала с минимальными остатками. Недостатком известных устройств является низкое быстродействие, связанное , со значительными затратами времени на перебор заведомо непригодных комбинаций, возникающими при определенных условиях. Целью изобретения является повышение быстродействия за счет исключения перебора заведомо непригодных комбинаций. Устройство (Л с го 4 00 00 00