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

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

Устройство для решения задач целочисленного линейного программирования, содержащее группу из n счетчиков 3₁ 3_n, первый элемент И 2, первый вход которого соединен с пусковым входом устройства 1, а выход подсоединен к входу счетчика 3₁, группу из m первых сумматоров 7₁ 7_m, группу из m первых схем сравнения 9 ₁ 9_m, второй элемент И 10, вторую схему сравнения 16, выход каждого сумматора 7_i (i=1 m) подсоединен к первому входу одноименной схемы сравнения 9_i, выход которой подсоединен к одноименному входу второго элемента И 10, отличающееся тем, что в него дополнительно включены группы из m*n первых регистров 5₁₁ 5_mn, первых блоков умножения 6₁₁ 6_mn, m вторых регистров 8₁ 8_m, n третьих 4₁ 4_n регистров, n четвертых 13₁ 13_n регистров, n вторых блоков умножения 14 ₁ 14_n, второй сумматор 15, пятый регистр 17, элемент задержки 18, третий элемент И 11, четвертый элемент И 12, выход каждого счетчика 3_j (j=1, 2, n) подсоединен к первым входам первых блоков умножения 6_ij, к первому входу регистра 4 и к первому входу второго блока умножения 14_j, второй вход которого подсоединен к выходу четвертого регистра 13_j, a выход - к одноименному входу второго сумматора 15, выход которого подсоединен к первым входам третьего элемента И 11 и второй схемы сравнения 16, второй вход которой подсоединен к выходу пятого регистра 17, а выход - к первому входу элемента И 12 и через элемент задержки 18 ко второму входу третьего элемента И 11, выход которого подсоединен к входу пятого регистра 17, выход каждого второго регистра 8 _i (i=1 m) подсоединен ко второму входу схемы сравнения 9_i , второй вход каждого первого блока умножения 6_ij подсоединен к выходу одноименного первого регистра 5_ij , а выход - к одноименному входу сумматора 7_i, выход второго элемента И 10 подсоединен к третьему входу элемента И 11 и ко второму входу четвертого элемента И 12, выход которого подсоединен ко вторым входам третьих регистров 4_j, выход переполнения счетчика 3_i (i=1, 2, n-1) подсоединен к счетному входу счетчика 3_i+1 , выход переполнения счетчика 3_n подсоединен ко второму входу элемента И 2 и является первым выходом устройства 19, выходы третьих регистров 4₁ 4_n являются вторыми выходами третьих 20 ₁ 20_n устройства.

Описание изобретения к патенту

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

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

Недостатками данного устройства являются низкое быстродействие из-за применения аналого-цифровых преобразователей и многочисленных блоков памяти, а так же решение только узкой задачи раскроя с минимальными остатками цельного единого материала длиной L на заготовки длиной I_i с потребным количеством каждого типа N_i: найти min L, , при L=L-(n₁I₁+n₂I ₂+ +n_kI_n) 0, где n_i - целое, 0 n_i, N_i; L L_max; L, I_i, N_i>0 - заданные величины [1].

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

min dL=mL-(k₁L₁ +k₂L₂+ +k_nL_n),

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

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

Сущность изобретения состоит в том, что в устройство для решения задач целочисленного линейного программирования, содержащее группу из n счетчиков 3₁ 3_n, первый элемент И 2, первый вход которого соединен с пусковым входом устройства 1, а выход подсоединен к входу счетчика 3₁, группу из m первых сумматоров 7₁ 7_m, группу из m первых схем сравнения 9 ₁ 9_m, второй элемент И 10, вторую схему сравнения 16, выход каждого сумматора 7_i (i=1 m) подсоединен к первому входу одноименной схемы сравнения 9_i, выход которой подсоединен к одноименному входу второго элемента И 10, дополнительно включены группы из m*n первых регистров 5₁₁ 5_mn, первых блоков умножения 6₁₁ 6_mn, m вторых регистров 8₁ 8_m, n третьих 4₁ 4_n регистров, n четвертых 13₁ 13_n регистров, n вторых блоков умножения 14 ₁ 14_n, второй сумматор 15, пятый регистр 17, элемент задержки 18, третий элемент И 11, четвертый элемент И 12, выход каждого счетчика 3_j (j=1, 2, n) подсоединен к первым входам первых блоков умножения 6_ij, к первому входу регистра 4_j и к первому входу второго блока умножения 14_j, второй вход которого подсоединен к выходу четвертого регистра 13_j, а выход - к одноименному входу второго сумматора 15, выход которого подсоединен к первым входам третьего элемента И 11 и второй схемы сравнения 16, второй вход которой подсоединен к выходу пятого регистра 17, а выход - к первому входу элемента И 12 и через элемент задержки 18 ко второму входу третьего элемента И 11, выход которого подсоединен к входу пятого регистра 17, выход каждого второго регистра 8 _i (i=1 m) подсоединен ко второму входу схемы сравнения 9_i , второй вход каждого первого блока умножения 6_ij подсоединен к выходу одноименного первого регистра 5_ij , а выход - к одноименному входу сумматора 7_i, выход второго элемента И 10 подсоединен к третьему входу элемента И 11 и ко второму входу четвертого элемента И 12, выход которого подсоединен ко вторым входам третьих регистров 4_j, выход переполнения счетчика 3_n подсоединен ко второму входу элемента И 2 и является первым выходом устройства 19, выходы третьих регистров 4₁ 4_n являются вторыми выходами третьих 20 ₁ 20_n устройства.

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

Новизна предлагаемого устройства заключается в том, что новое техническое устройство отличается от прототипа тем, что дополнительно в него введены группы из m*n первых регистров 5₁₁ 5_mn, первых блоков умножения 6₁₁ 6_mn, m вторых регистров 8₁ 8_m, n третьих 4₁ 4_n регистров, n четвертых 13₁ 13_n регистров, n вторых блоков умножения 14 ₁ 14_n, второй сумматор 15, пятый регистр 17, элемент задержки 18, третий элемент И 11, четвертый элемент И 12, выход каждого счетчика 3_j (j=1, 2, n) подсоединен к первым входам первых блоков умножения 6_ij, к первому входу регистра 4_j и к первому входу второго блока умножения 14_j, второй вход которого подсоединен к выходу четвертого регистра 13_j, а выход - к одноименному входу второго сумматора 15, выход которого подсоединен к первым входам третьего элемента И 11 и второй схемы сравнения 16, второй вход которой подсоединен к выходу пятого регистра 17, а выход - к первому входу элемента И 12 и через элемент задержки 18 ко второму входу третьего элемента И 11, выход которого подсоединен к входу пятого регистра 17, выход каждого второго регистра 8 _i (i=1 m) подсоединен ко второму входу схемы сравнения 9_i , второй вход каждого первого блока умножения 6_ij подсоединен к выходу одноименного первого регистра 5_ij , а выход - к одноименному входу сумматора 7_i, выход второго элемента И 10 подсоединен к третьему входу элемента И 11 и ко второму входу четвертого элемента И 12, выход которого подсоединен ко вторым входам третьих регистров 4_j, выход переполнения счетчика 3_i (i=1, 2, n-1) подсоединен к счетному входу счетчика 3_i+1 , выход переполнения счетчика 3_n подсоединен ко второму входу элемента И 2 и является первым выходом устройства 19, выходы третьих регистров 4₁ 4_n являются вторыми выходами 20₁ 20_n устройства.

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

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

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

Устройство для решения задач целочисленного линейного программирования, показанное на фиг.1, содержит: вход 1, элемент И 2, счетчики 3₁, 3₂, , 3_n (n - число возможных вариантов разрезания заготовки длиной L), регистры 4₁, 4₂, , 4_n, регистры 5₁₁, 5₂₂ , , 5_mn, блоки умножения 6₁₁, 6 ₂₂, , 6_mn (m - общее число типов различных заготовок), сумматоры 7₁, 7₂, , 7_m, регистры 8₁, 8₂, , 8_m для хранения требуемых чисел различных заготовок, схемы сравнения 9₁, 9₂, , 9_m, элемент И 10, элемент И 11, элемент И 12, регистры 13₁, 13₂, , 13_n, блоки умножения 14₁, 14 ₂, , 14_n, сумматор 15, схему сравнения 16, регистр 17, элемент задержки 18, выход устройства 19, выходы устройства 20₁, 20₂, , 20_n.

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

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

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

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

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

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

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

На регистрах 5₁₁, 5₂₂ , , 5_mn хранятся числа изделий (заготовок) i-го типа по j-му варианту (i=1, 2, m, j=1, 2, n). На регистрах 8₁, 8₂, , 8_m хранятся коды требуемых чисел различных заготовок. На регистрах 13₁, 13₂, , 13_n хранятся коды длин остатков от разрезания заготовки по j-му варианту.

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

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

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

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

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

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

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

Литература

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

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