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

 

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

СОЮЗ СО8ЕТСНИХ

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

РЕСПУБЛИН

„„SU„„12478 (gg 4 С 06 F 15/32, 15/20

А1

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3848567/24-24 (22) 28 ° 01.85 (46) 30.07.86. Бюл. Р 28 (71) Ленинградский ордена Трудового

Красного Знамени институт текстильной и легкой промьппленности им.С.М.Кирова (72) И.Н. Маркова, А.Ю. Веревкин, Ю.С. Мануйлов и О.А. Мишенин (53) 681.325(088 8) (56) Грэм Дж. и др. Проектирование и применение операционных усилителей.

N.: Мир, 1974, с. 369.

Авторское свидетельство СССР

Р 1180925, кл. G 06 F 15/32, 6 06 F 15/20, 1984. (54) УСТРОЙСТВО. ДЛЯ РЕШЕНИЯ ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ (57) Изобретение относится. к вычислительной технике и может быть исполь. зовано, например, для раскроя материала с минимальными остатками. Недостатком известных устройств является низкое быстродействие, связанное со значительными затратами времени на перебор заведомо непригодных комбинаций, возникаюшими при определенных условиях. Целью изобретения является .повышение быстродействия за счет исключения перебора заведомо непригодных комбинаций. Устройство

12 содержит счетчики 1, 2, предназначен" ные для перебора всевозможных комбинаций и и текущей величины допуска

b L т.е. допустимой величины ошибки. Для поиска оптимального решения Б .„,„, разбивается на И частей

b L„„„= 6 L<Ä /И. В счетчик 2 записывается код m пропорциональный

SL а в блок памяти по адресу M " единица. В счетчике 2 последовательно перебираются различные значения

8Е от Б L и„до L . Блоки 3, 4 цамяти предназначены для формирования сигнала переноса из i-ro разряда в (i+1)-й, если величина и; превысила М, и совместно со счетчиками 1, 2 образуют счетчики с программируемым числом пересчета, цифроаналоговые преобразователи 5 и 6 предназначены для преобразования величин n;,SLÄ,„, в а11алоговую форму. Сумматор 7 формирует сигнал, пропорциональный Я1, он может быть реализован на операци47888 онном усилителе, имеющем входные сопротивления, обеспечивающие коэффициент передачи от i-ro ЦАП, пропор.циональный 1; . Схемы 8, 9 сравнения предназначены для сравнения сигнала, поступающего с сумматора 7, с нулем и с SL„ „ соответственно при наличии разрешающего сигнала. Элемент 10 И разрешает работу схемы 9 сравнения, если есть сигнал со схемы 8 (SL О).

Элементы 11, 12 ИЛИ передают сигнал переноса из i-ro в (i+1)-й разряд.

Элемент 13 И запрещает подачу тактовых сигналов на первый счетчик 1, когда 6L с О. Блок 15 формирования переноса предназначен для формирования сигналов переноса из i-го счетчика в (i+1)-й, обеспечивая при этом пропуск заведомо непригодных комбинаций п„. Блок формирования переноса содержит элемент 16 НЕ-И, элемент

17 НЕ, элементы 18, 19 И. 1 з.пуф-ль1

1 ил.

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

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

На чертеже представлена схема устройства.Устройство содержит счетчики 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, i=1, К, при

$1+ L (и f +n>1 +а ° в+n ) Ъ р где п, — целое, 0 с и «аИ";

SL < 6 „„

L,Õ;,N,>0 — заданные величины. !

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

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

В исходном состоянии все счетчики

1, кроме последнего счетчика 2, обнулены. В счетчик 2 записан код m, про1 порциональный минимальному значению

SLM„„, с которым будет проводиться поиск решения. В i-м блоке 3 памяти записана единица по тому адресу, код которого равен N,, (в последнем о N S L„,„, ). Запись этой информации ,производится записью кода И; в соответствующий счетчик и подачей сигнаца. "Запись "1" на блоки 3 памяти (эти .

Йходы с целью упрощения не показаны) .

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

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

1247

rain (N, ()) 20 открыт, увеличивает на единицу содержимое первого счетчика 1. его код поступает на первый ЦАП 5, на выходе которого появляется сигнал, пропорциональный и,. Поскольку коэффициент передачи сумматора 7 по первому входу равен У, то на выходе сумматора 7

1 появляется сигнал 5 L = )L — n F, ) .

Тактовый сигнал 25 разрешает сравнение на схеме 8 сравнения. Если f0 (L-n;F, ) > О, то выходной сигнал схемы 8, пройдя через элемент 10 И, разрешает сравнение на схеме 9 сравнения. Если 8L - 5 Ь„„ (последнее поступает со счетчика 2 через ЦАП 6), fg то сигнал на выходе 23 означает, что искомое решение найдено и с выходов

21 может быть считано значение n,: а с выхода 24 — значение оL, при котором это решение найдено.

Если решение не найдено, то к первому счетчику 1 вновь прибавляется единица и процесс повторяется. Пусть. в некоторый момент в i-м счетчике 1

25 величина n . .> N;, тогда единица, считываемая из соответствующего блока 3 памяти, пройдя элементы 11 и

12 ИЛИ, сбрасывает этот i-й счетчик и прибавляет единицу к (i+1)-му счетчику. Таким образом, обеспечивается условие n . . N.. Если решение с

5Ь не найдено, то аналогичным обтек разом увеличивается содержимое счетчика 2, а следовательно, БЬ „ . При

6Ь 0 Ь сигнал с блока 4 памяти35 поступает на выход 24 устройства, что свидетельствует о невозможности на" хождения решения с заданным L „,. макс

Пусть в некоторый .момент времени значение БЬ, полученное на выходе сум- 40 матора 7, меньше нуля, тогда сигнал с выхода схемы 8, пройдя через элемент 14, не закрывает элемент 13 И и прекращает подачу тактовых импульсов на первый счетчик 1 и блок 3 памяти. 4>

Кроме того, он поступает на вх:g 27 нервого блока 15. Если в данный момент этот счетчик обнулен, то на выходе элемента И 16 появляется единица, которая открывает элемент 19 И и пропускает сигнал переноса на вход 27 следующего блока формирования переноса. Таким образом, сигнал с элемента 14 НЕ минует все счетчики 1, в которых записан код"0".Наконец, достигнув "нулевого" счетчика, этот сигнал проходит элемент 18 И соответствующего блока 15 (который открыт

888 4 сигналом с элемента 17 HE) и поступа.ет на элемент 11 ИЛИ. В результате

его выходной сигнал сбрасывает первый нулевой счетчик 1 с номером i при, бавляет единицу к следующему (i+1)му счетчику и считывает содержимое (i+1)-ro блока памяти. Наконец, если причина того, что SL О, — ненулевое состояние (К вЂ” 1)-го счетчика 1, или

n > N то выходной сигнал с (К-1) — .

ro элемента 12 ИЛИ, кроме указанных выше действий, устанавливает в некоторое состояние и, первый счетчик 1 °

Последнее действие целесообразно произвести, поскольку в этот момент все счетчики 1 обнулены и поиск имеет смысл начинать только с некоторой комбинации n„0 ...О. В частности и, может быть равно

L где ()- целая часть е, Формула изобретения

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

И соединен с разрешающим входом первой схемы сравнения, выход второй схемы сравнения соединен с вторым входом первого элемента И, первый

1?47888

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

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

Редактор И. Рыбченко

Заказ 4128/50 Тираж 671

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

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

Подписное

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

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

i-го (i""1, К-2) блока формирования переноса соединен с вторым входом

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

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