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

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

Иллюстрации

Показать все

Реферат

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

Наиболее близким по технической сущности является устройство [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_1…8_m, n третьих 4_1…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.

Устройство для решения задач целочисленного линейного программирования, содержащее группу из 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 устройства.