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

12 содержит счетчики 1, 2, предназначен" ные для перебора всевозможных комби" наций и и текущей величины допуска о Ь, т.е. допустимой величины ошибки. Для поиска оптимального решения БЬ разбивается на М частей 8 Ь = 8 Ьр, /М. В счетчик 2 записывается код ш, пропорциональный бЬ р а в блок памяти по адресу М " единица. В счетчике 2 последовательно перебираются различные значения ЗЬ от БЬ,до 1 Ь . Блоки 3, 4 цамяти предназначены для формирования сигнала переноса из -го разряда в (+1)-йр если величина и; превысила И , и совместно со счетчиками 1, 2 образуют счетчики с программируемым числом пересчета, цифроаналоговьш преобразователи 5 и 6 предназначены для преобразования величин и; р 8 Ь в аналоговую форму. Сумматор 7 формирует сигнал, пропорциональный Я Ь, он может быть реализован на операци 47888онном усилителе, имеющем входныесопротивления, обеспечивающие коэффициент передачи от 1-го ЦАП, пропор,циональный 1; . Схемы 8, 9 сравненияпредназначены для сравнения сигнала,поступающего с сумматора 7, с нулеми с ЯЬсоответственно при наличииразрешающего сигнала, Элемент 10 Иразрешает работу схемы 9 сравнения,если есть сигнал со схемы 8 (БЬ ( 0).Элементы 11, 12 ИЛИ передают сигналпереноса из 1-го в (+1)-й разряд.Элемент 13 И запрещает подачу тактовых сигналов на первый счетчик 1,когда БЬО. Блок 15 формированияпереноса предназначен для формирования сигналов переноса из -го счетчика в (х+1)-йр обеспечивая при этомпропуск заведомо непригодных комбинаций и. Блок формирования переносасодержит элемент 16 НЕ-И, элемент17 НЕ, элементы 18, 19 И. 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 блоков формирования переноса.Устройство предназначено для реше ния задач типа найти шп БЬр =1 р Кр при 1 Ь (и Г +и рр++и 1 )Ор где и,. - целое, 0 с и сИ,.;ВЬ6 ЬЬр 1,рИ,)0 - заданные величины.Такие задачи возникают, например,при необходимости раскроя с минимальными остатками материала длиной Ь назаготовки длиной 7, с потребным ко"личеством каждого типа ИрУстройство работает следующим образом.В исходном состоянии все счетчики1, кроме последнего счетчика 2, обнулены. В счетчик 2 записан код ш, про порциональный минимальному значениюБЬ , с которым будет проводитьсяпоиск решения. В а-м блоке 3 памятизаписана единица по тому адресу, кодкоторого равен И (в последнем 2 О М Р Ь ). Запись этой информации,производится записью кода И; в соответствующий счетчик и подачей сигнаца. "Запись "1" на блоки 3 памяти (эти .Йходы с целью упрощения не показаны) .На вход 20 подан сигнал, пропорциональный величине Ь.На вход 25 устройства поступаеттактовый сигнал и, если элемент 13 И1247 20 открыт, увеличивает на единицу содержимое первого счетчика 1. Его кодпоступает на первый ЦАП 5, на выходекоторого появляется сигнал, пропорциональный и,. Поскольку коэффициентпередачи сумматора 7 по первому входуравен 1 , то на выходе сумматора 7появляется сигнал О Ь = Ь - и 1,).Тактовый сигнал 25 разрешает сравнение на схеме 8 сравнения. Если 0(Ь-и;1, )О, то выходной сигнал схемы 8, пройдя через элемент 10 И, разрешает сравнение на схеме 9 сравнения. Если 3 Ь - Я Ь (последнеепоступает со счетчика 2 через ЦАП 6), 15то сигнал на выходе 23 означает, чтоискомое решение найдено и с выходов21 может быть считано значение и ас выхода 24 - значение 8 Ь, при котором это решение найдено. Если решение не найдено, то к первому счетчику 1 вновь прибавляетсяединица и процесс повторяется. Пусть. в некоторый момент в д-м счетчике 125 величина и,Н;, тогда единица, считываемая из соответствующего блока 3 памяти, пройдя элементы 11 и 12 ИЛИ, сбрасывает этот д-й счетчик и прибавляет единицу к (1+1)-му счетчику. Таким образом, обеспечивается условие и .Б Если решение с1цЬ не найдено, то аналогичным обтекразом увеличивается содержимое счетчика 2, а следовательно, БЬ. При 6 Ь0 Ь, сигнал с блока 4 памяти 35 поступает на выход 24 устройства, что свидетельствует о невозможности на" хождения решения с заданным ЬмаксПусть в некоторый, момент времени зна"чение БЬ, полученное на выходе сум матора 7, меньше нуля, тогда сигнал с выхода схемы 8, пройдя через элемент 14, не закрывает элемент 13 И и прекращает подачу тактовых импульсов на первый счетчик 1 и блок 3 памяти, 45 Кроме того, он поступает на вх ц 27 нервого блока 15. Если в данный момент этот счетчик обнулен, то на выходе элемента И 16 появляется единица, которая открывает элемент 19 И 50 и пропускает сигнал переноса на вход 27 следующего блока формирования переноса. Таким образом, сигнал с элемента 14 НЕ минует все счетчики 1, в которых записан код"О".Наконец, дос тигнув "нулевого" счетчика, этот сигнал проходит элемент 18 И соответствующего блока 15 (который открыт 888 4сигналом с элемента 17 НЕ) и поступа:ет на элемент 11 ИЛИ. В результате его выходной сигнал сбрасывает первый нулевой счетчик 1 с номером 1, при. бавляет единицу к следующему (1+1)- му счетчику и считывает содержимое(1+1)-го блока памяти. Наконец, если причина того, что 8 ЬО, - ненулевое состояние (К)-го счетчика 1, или и ,Б , то выходной сигнал с (К)- . го элемента 12 ИЛИ, кроме указанных выше действий, устанавливает в некоторое состояние и первый счетчик 1. Последнее действие целесообразно произвести, поскольку в этот момент все счетчики 1 обнулены и поиск имеет смысл начинать только с некоторой комбинации пО О. В частности и, может быть равно Ьгде- целая часть е,Формула изобретения 1. Устройство для решения целочисленных задач математического программирования, содержащее К блоков памяти, К цифроаналоговых преобразователей, первую и вторую схемы сравне - ния, К счетчиков, выход каждого из которых подключен к входу соответствующего цифроаналогового преобразователя и к первому информационному выходу устройства, выход первой схемы сравнения является выходом сигнала окончания решения устройства, адресный вход каждого блока памяти соединен с выходом соответствующего счетчика, выходы цифроаналоговых преобразователей, кроме К-го, соединены соответственно с входами сумматора, один из входов которого соединен с информационным входом устройства, выход К-го цифроаналогового преобразователя соединен с первым информационным входом первой схемы сравнения, выход сумматора соединен с вторым информационным входом первой схемы сравнения и с информационным входом второй схемы сравнения, разрешающий вход которой и первый вход первого элемента Исоединены с тактовым входом устройства, выход первого элемента И соединен с разрешающим входом первой схемы сравнения, выход второй схемы сравнения соединен с вторым входом первого элемента И, первый147888 Составитель А. Жеренов Техред М,Ходанич Корректор Е.СирохманРедактор И. Рыбченко Заказ 4128/50 Тираж 671 ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Подписное Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 вход первого элемента ИЛИ соединен с выходом первого блока памяти, выход первого элемента ИЛИ соединен с входом сброса первого счетчика, с входом считывания второго блока памяти н со счетным входом второго счетчика, выход К-го блока памяти является вторым информационным выходом устройства, о т л и ч а ю щ е е с я тем, 10 что, с целью повышения быстродействия за счет исключения перебора заведомо непригодных комбинаций, в него введены элемент НЕ, Кэлементов ИЛИ, второй элемент И и Кблоков формирования переноса, первый вход каждого из которых, начиная с первого, соединен с выходом соответствующего счетчика, второй вход первого блока формирования переноса соединен с выходом элемента НЕ, второй вход 1-го2, К) блока формирования переноса соединен с первым выходом (х)- го блока формирования переноса, первый вход -го (д = 2, К) элемента 25 ИЛИ соединен с.выходом -го блока памяти, а выход соединен с входом сброса -го счетчика, со счетным входом (+1)-го счетчика и с входом считывания (+1)-го блока памяти, первый выход (К)-го блока формирования переноса соединен с вторым входом-го (д"1, К) блока формированияпереноса соединен с вторым входом-го элемента ИЛИ, выход (К)-гоэлемента ИЛИ соединен с установочнымвходом первого счетчика, первый входвторого элемента И соединен с тактовым входом устройства, второй входподключен к выходу элемента НЕ, выход второго элемента И соединен сосчетным входом первого счетчика и свходом считывания первого блока памяти, вход элемента НЕ соединен с выходом второй схемы сравнения,1 2. Устройство по п. 1, о т л и - ч а ю щ е е с я тем, что блок формирования переноса содержит два элемента И, элемент НЕ и элемент НЕ-И, вход которого является первым входом блока, а выход соединен с первым входом первого элемента И и через элемент НЕ - с первым входом второго элемента И, вторые входы первого и второго элементов И соединены с вторым входом блока, выходы первого и второго элементов И являются соответственно первым и вторым выходами блока.