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



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

 


Владельцы патента RU 2446453:

Негосударственное образовательное учреждение высшего профессионального образования Московский институт предпринимательства и права (RU)

Изобретение относится к вычислительной технике. Технический результат заключается в повышении быстродействия работы устройства. Устройство для решения задач целочисленного линейного программирования содержит вход 1, элемент И 2, счетчики 31, 32, …, 3n (n - число возможных вариантов разрезания заготовки длиной L), регистры 41, 42, …, 4n, регистры 511, 522, …, 5mn, блоки умножения 611, 622, …, 6mn (m - общее число типов различных заготовок), сумматоры 71, 72, …, 7m, регистры 81, 82, …, 8m для хранения требуемых чисел различных заготовок, схемы сравнения 91, 92, …, 9m, элемент И 10, элемент И 11, элемент И 12, регистры 131, 132, …, 13n, блоки умножения 141, 142, …, 14n, сумматор 15, схему сравнения 16, регистр 17, элемент задержки 18, выход устройства 19, выходы устройства 201, 202, …, 20n. 1 ил.

 

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

Наиболее близким по технической сущности является устройство [1], содержащее группу из n счетчиков 31…3n, первый элемент И 2, первый вход которого соединен с пусковым входом устройства 1, а выход подсоединен к входу счетчика 31, группу из m первых сумматоров 71…7m, группу из m первых схем сравнения 91…9m, второй элемент И 10, вторую схему сравнения 16, выход каждого сумматора 7i (i=1…m) подсоединен к первому входу одноименной схемы сравнения 9i, выход которой подсоединен к одноименному входу второго элемента И 10.

Недостатками данного устройства являются низкое быстродействие из-за применения аналого-цифровых преобразователей и многочисленных блоков памяти, а так же решение только узкой задачи раскроя с минимальными остатками цельного единого материала длиной L на заготовки длиной Ii с потребным количеством каждого типа Ni: найти minδL, , при δL=L-(n1I1+n2I2+…+nkIn)≥0, где ni - целое, 0≅ni, ≅Ni; δL≅δ Lmax; L, Ii, Ni>0 - заданные величины [1].

Задача изобретения - создать устройство, обеспечивающее задачи разрезания набора заготовок длиной L с минимальными остатками на заготовки с длинами L1, L2,…Ln, где n - количество различных заготовок, то есть найти:

min dL=mL-(k1L1+k2L2+…+knLn),

где ki - искомое целое число требуемых заготовок;

m - потребное число исходных заготовок длиной L.

Сущность изобретения состоит в том, что в устройство для решения задач целочисленного линейного программирования, содержащее группу из n счетчиков 31…3n, первый элемент И 2, первый вход которого соединен с пусковым входом устройства 1, а выход подсоединен к входу счетчика 31, группу из m первых сумматоров 71…7m, группу из m первых схем сравнения 91…9m, второй элемент И 10, вторую схему сравнения 16, выход каждого сумматора 7i (i=1…m) подсоединен к первому входу одноименной схемы сравнения 9i, выход которой подсоединен к одноименному входу второго элемента И 10, дополнительно включены группы из m*n первых регистров 511…5mn, первых блоков умножения 611…6mn, m вторых регистров 81…8m, n третьих 41…4n регистров, n четвертых 131…13n регистров, n вторых блоков умножения 141…14n, второй сумматор 15, пятый регистр 17, элемент задержки 18, третий элемент И 11, четвертый элемент И 12, выход каждого счетчика 3j (j=1, 2,…n) подсоединен к первым входам первых блоков умножения 6ij, к первому входу регистра 4j и к первому входу второго блока умножения 14j, второй вход которого подсоединен к выходу четвертого регистра 13j, а выход - к одноименному входу второго сумматора 15, выход которого подсоединен к первым входам третьего элемента И 11 и второй схемы сравнения 16, второй вход которой подсоединен к выходу пятого регистра 17, а выход - к первому входу элемента И 12 и через элемент задержки 18 ко второму входу третьего элемента И 11, выход которого подсоединен к входу пятого регистра 17, выход каждого второго регистра 8i (i=1…m) подсоединен ко второму входу схемы сравнения 9i, второй вход каждого первого блока умножения 6ij подсоединен к выходу одноименного первого регистра 5ij, а выход - к одноименному входу сумматора 7i, выход второго элемента И 10 подсоединен к третьему входу элемента И 11 и ко второму входу четвертого элемента И 12, выход которого подсоединен ко вторым входам третьих регистров 4j, выход переполнения счетчика 3n подсоединен ко второму входу элемента И 2 и является первым выходом устройства 19, выходы третьих регистров 41…4n являются вторыми выходами третьих 201…20n устройства.

Проведенный поиск в известной научно-технической литературе не выявил наличие подобных технических решений.

Новизна предлагаемого устройства заключается в том, что новое техническое устройство отличается от прототипа тем, что дополнительно в него введены группы из m*n первых регистров 511…5mn, первых блоков умножения 611…6mn, m вторых регистров 81…8m, n третьих 41…4n регистров, n четвертых 131…13n регистров, n вторых блоков умножения 141…14n, второй сумматор 15, пятый регистр 17, элемент задержки 18, третий элемент И 11, четвертый элемент И 12, выход каждого счетчика 3j (j=1, 2,…n) подсоединен к первым входам первых блоков умножения 6ij, к первому входу регистра 4j и к первому входу второго блока умножения 14j, второй вход которого подсоединен к выходу четвертого регистра 13j, а выход - к одноименному входу второго сумматора 15, выход которого подсоединен к первым входам третьего элемента И 11 и второй схемы сравнения 16, второй вход которой подсоединен к выходу пятого регистра 17, а выход - к первому входу элемента И 12 и через элемент задержки 18 ко второму входу третьего элемента И 11, выход которого подсоединен к входу пятого регистра 17, выход каждого второго регистра 8i (i=1…m) подсоединен ко второму входу схемы сравнения 9i, второй вход каждого первого блока умножения 6ij подсоединен к выходу одноименного первого регистра 5ij, а выход - к одноименному входу сумматора 7i, выход второго элемента И 10 подсоединен к третьему входу элемента И 11 и ко второму входу четвертого элемента И 12, выход которого подсоединен ко вторым входам третьих регистров 4j, выход переполнения счетчика 3i (i=1, 2,…n-1) подсоединен к счетному входу счетчика 3i+1, выход переполнения счетчика 3n подсоединен ко второму входу элемента И 2 и является первым выходом устройства 19, выходы третьих регистров 41…4n являются вторыми выходами 201…20n устройства.

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

Предлагаемое устройство позволяет быстро решить задачу разрезания набора заготовок длиной L с минимальными остатками на заготовки с длинами L1, L2, … Ln, где n - количество различных заготовок.

Сущность изобретения поясняется чертежом (фиг.1), на котором приведена структурная схема заявленного устройства.

Устройство для решения задач целочисленного линейного программирования, показанное на фиг.1, содержит: вход 1, элемент И 2, счетчики 31, 32, …, 3n (n - число возможных вариантов разрезания заготовки длиной L), регистры 41, 42,…, 4n, регистры 511, 522, …, 5mn, блоки умножения 611, 622, …, 6mn (m - общее число типов различных заготовок), сумматоры 71, 72,…, 7m, регистры 81, 82, …, 8m для хранения требуемых чисел различных заготовок, схемы сравнения 91, 92, …, 9m, элемент И 10, элемент И 11, элемент И 12, регистры 131, 132, …, 13n, блоки умножения 141, 142, …, 14n, сумматор 15, схему сравнения 16, регистр 17, элемент задержки 18, выход устройства 19, выходы устройства 201, 202, …, 20n.

Разрядность регистров 4j и счетчиков 3j (j=1…n) выбирается из условия потребности максимального требуемого числа j-х заготовок.

Разрядность регистров 5ij (i=1…m, j=1…n) выбирается из условия хранения на них числа заготовок при разбиении исходной i-й заготовки по j-му варианту. Разрядность регистров 8i (i=1…m) выбирается из условия максимума требуемых чисел i-х заготовок, регистров 13j (j=1…m) из условия возможности хранения максимального числа остатка исходной заготовки при применении j-го варианта разбиения.

Разрядность сумматора 15 и регистра 17 выбирается из условия достаточности для размещения кода оптимизируемой функции.

Частота поступающих входных тактовых сигналов на входе 1 выбирается из условия суммарных задержек сигнала элементом И 2, счетчиками 3, блока умножения 6ij, сумматора 7i, схемы сравнения 9i, элементов И 10, И 11, И 12.

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

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

В исходном состоянии счетчики 31 32, …, 3n, регистры 41, 42, …, 4n (n - число возможных вариантов разрезания заготовки длиной L) находятся в нулевом состоянии. На регистре 17 хранится код максимального числа (все разряды регистра находятся в единичном состоянии). На выходе переполнения счетчика 3n находится логический ноль, который поступает на выход 19 устройства и на инверсный вход элемента И 2, тем самым элемент И 2 открыт для последующего прохождения тактовых импульсов по входу.

На регистрах 511, 522, …, 5mn хранятся числа изделий (заготовок) i-го типа по j-му варианту (i=1, 2, …m, j=1, 2, …n). На регистрах 81, 82, …, 8m хранятся коды требуемых чисел различных заготовок. На регистрах 131, 132, …, 13n хранятся коды длин остатков от разрезания заготовки по j-му варианту.

Работа устройства начинается после подачи на вход 1 тактовых импульсов с выхода генератора тактовых импульсов (на чертеже из-за громоздкости он не показан), которые через открытый элемент И 2 поступают на вход счетчика 31. Код с выхода переполнения счетчика 3j (j=1, 2, …n-1) поступает на счетный вход очередного счетчика 3j+1. С выхода счетчика 3j (j=1, 2, 3, …n) код поступает на первые входы блока умножения 14j, регистр 4j и блоков умножения 6ij (1=1, 2, …m, j=1, 2, …n).

На второй вход блока умножения 14 поступает код с выхода регистра 13j. Результат произведения с выхода блока умножения 14j поступает на одноименный вход сумматора 15, код с выхода которого поступает на первый вход схемы сравнения 16, на второй вход которой поступает код с выхода регистра 17 с текущим значением минимизируемой функции. На выходе схемы сравнения 16 появляется единичный сигнал только в том случае, если код на выходе сумматора 15 меньше кода с выхода регистра 17.

Единичный сигнал с выхода схемы сравнения 16 поступает на первый вход элемента И 12, а так же через элемент задержки 18 открывает элемент И 11, через который при наличии также единичного сигнала на другом его входе с выхода элемента И 10 новое значение с выхода сумматора 15 запомнится на регистре 17.

Одновременно результат произведения с выхода блока умножения 6ij поступает на одноименный вход сумматора 7i, код с выхода которого поступает на первый вход схемы сравнения 9i, на второй вход которой поступает код с выхода регистра 8i, со значением требуемого количества изделий i-го типа. На выходе схемы сравнения 9i появляется единичный сигнал только в том случае, если код на выходе регистра 8i не меньше кода с выхода сумматора 7i.

Сигнал с выхода схемы сравнения 9i поступает на одноименный вход элемента И 10, на выходе которого появляется единичный сигнал только при одновременном появлении единичных входных сигналов с выходов всех схем сравнения 9. Единичный сигнал с выхода элемента И 10 поступает на второй управляющий вход элемента И 11 и элемента И 12, с выхода которого единичный сигнал обеспечивает перезапись содержимого счетчиков 3j (j=1, 2, 3, …n) в одноименные регистры 4j (j=1, 2, 3, …n).

Сигналом окончания работы устройства является сигнал переполнения с выхода счетчика 3n, который поступает на выход 19 устройства и на инверсный вход элемента И 2, тем самым прекращается подача входных тактовых сигналов по входу 1 устройства.

Таким образом, в результате работы устройства выходной информацией являются: единичный сигнал на выходе 19 и коды на выходах 20j (j=1, 2, 3, …n).

Литература

1. Патент 2143729. Устройство для решения задач целочисленного линейного программирования. Опубликовано: 27.12.1999.

2. Г.Вагнер. Основы исследования операций. Том 3. - М.: Мир, 1973. - С.284-294.

Устройство для решения задач целочисленного линейного программирования, содержащее группу из n счетчиков 31…3n, первый элемент И 2, первый вход которого соединен с пусковым входом устройства 1, а выход подсоединен к входу счетчика 31, группу из m первых сумматоров 71…7m, группу из m первых схем сравнения 91…9m, второй элемент И 10, вторую схему сравнения 16, выход каждого сумматора 7i (i=1…m) подсоединен к первому входу одноименной схемы сравнения 9i, выход которой подсоединен к одноименному входу второго элемента И 10, отличающееся тем, что в него дополнительно включены группы из m*n первых регистров 511…5mn, первых блоков умножения 611…6mn, m вторых регистров 81…8m, n третьих 41…4n регистров, n четвертых 131…13n регистров, n вторых блоков умножения 141…14n, второй сумматор 15, пятый регистр 17, элемент задержки 18, третий элемент И 11, четвертый элемент И 12, выход каждого счетчика 3j (j=1, 2, …n) подсоединен к первым входам первых блоков умножения 6ij, к первому входу регистра 4 и к первому входу второго блока умножения 14j, второй вход которого подсоединен к выходу четвертого регистра 13j, a выход - к одноименному входу второго сумматора 15, выход которого подсоединен к первым входам третьего элемента И 11 и второй схемы сравнения 16, второй вход которой подсоединен к выходу пятого регистра 17, а выход - к первому входу элемента И 12 и через элемент задержки 18 ко второму входу третьего элемента И 11, выход которого подсоединен к входу пятого регистра 17, выход каждого второго регистра 8i (i=1…m) подсоединен ко второму входу схемы сравнения 9i, второй вход каждого первого блока умножения 6ij подсоединен к выходу одноименного первого регистра 5ij, а выход - к одноименному входу сумматора 7i, выход второго элемента И 10 подсоединен к третьему входу элемента И 11 и ко второму входу четвертого элемента И 12, выход которого подсоединен ко вторым входам третьих регистров 4j, выход переполнения счетчика 3i (i=1, 2, …n-1) подсоединен к счетному входу счетчика 3i+1, выход переполнения счетчика 3n подсоединен ко второму входу элемента И 2 и является первым выходом устройства 19, выходы третьих регистров 41…4n являются вторыми выходами третьих 201…20n устройства.



 

Похожие патенты:

Изобретение относится к области запуска приложений. .

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

Изобретение относится к области автоматизированного управления на объектах различного назначения. .

Изобретение относится к созданию журнала встреч с цифровым медиа контентом. .

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

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

Изобретение относится к средствам осуществления рабочего процесса. .

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

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

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

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

Изобретение относится к способу выполнения запросов к базам данных

Изобретение относится к области цифровой вычислительной техники и предназначено для моделирования комбинаторных задач при проектировании вычислительных систем (ВС)

Изобретение относится к вычислительным системам, информационным технологиям

Изобретение относится к области технической кибернетики и предназначено для обмена между базами данных системы с исключением повторной записи уже имеющихся данных

Изобретение относится к области технической кибернетики и предназначено для обмена между базами данных системы с исключением повторной записи уже имеющихся данных

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

Изобретение относится к вычислительной технике и может быть использовано для количественной оценки качественного показателя, состоящего из отдельных составных частей (факторов), в различных областях науки, техники и общественной жизни
Наверх