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

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

Иллюстрации

Показать все

Реферат

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

Известно устройство для решения задач целочисленного линейного программирования (RU №2143729 С1, МПК G06F 17/00, G06F 17/10, заявлено 17.03.1998, опубликовано 27.12.1999), содержащее К блоков памяти (К≥2), К счетчиков, (К-1) элементов ИЛИ, (К-2) блоков формирования переноса, сумматор, (К+1) цифроаналоговых преобразователей, два элемента И, два блока сравнения, инвертор.

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

К причинам, препятствующим достижению указанного ниже технического результата, относится решение узкой задачи раскроя с минимальными остатками цельного материала длиной L на заготовки длиной I_i с потребным количеством каждого типа N_i: найти min δL=L-(N₁I₁+N₂I₂+…+N₂I₂+…+N_kI_n)≥0, где L, I_i, N_i - заданные целые величины, i=1,…,k.

Известно устройство для решения задачи о рюкзаке (RU №2461060 С1, МПК G06F 17/00, G06F 7/00, заявлено 25.05.2011, опубликовано 10.09.2012, Бюл. №25), содержащее генератор тактовых импульсов (ГТИ), триггер разрешения, триггер готовности результата, группу из m счетчиков, группы из m первых, вторых и третьих регистров, четвертый и пятый регистры, группы из m шестых, седьмых и восьмых регистров, девятый регистр, первый и второй сумматоры, группы из m третьих и четвертых сумматоров, первую и вторую схемы сравнения, группу из m третьих схем сравнения, элемент И, вход пуска устройства, вход сброса устройства, первый выход устройства, группу из m вторых выходов устройства, третьи выходы устройства, четвертые выходы устройства.

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

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство для решения задач целочисленного линейного программирования (RU №2446453 С1, МПК G06N 7/00, заявлено 08.12.2010, опубликовано 08.12.2010, Бюл. №9), содержащее группу из n счетчиков 4₁, 4₂, …, 4_n (n - число возможных вариантов разрезания заготовок длиной L), группу из m*n первых регистров 12₁₁, …, 12_mn (m - общее число типов различных типов заготовок), группу из m вторых регистров 17₁, 17₂, …, 17_m, группу из n третьих регистров 5₁, 5₂, …, 5_n, группу из n четвертых регистров 19₁, 19₂, …, 19_n, пятый регистр 23, группу из m первых сумматоров 15₁, 15₂, …, 15_m, второй сумматор 22, группу из m первых схем сравнения 16₁, 16₂, …, 16_m, вторую схему сравнения 24, элемент И 11, первый выход устройства 27, вторые выходы устройства 28₁, 28₂, …, 28_n, причем выход каждого счетчика 4_j (j=1,2,…,n) подсоединен к первому входу одноименного третьего регистра 5_j, выходы третьих регистров 5₁, 5₂, …, 5_n являются вторыми выходами устройства 28₁, 28₂, …, 28_n, выход каждого первого сумматора 15_i (i=1,2,…,m) подсоединен к первому входу одноименной первой схемы сравнения 16_i, второй вход которой подсоединен к выходу одноименного второго регистра 17_i, выход каждой первой схемы сравнения 16_i подсоединен к соответствующему входу первой группы входов элемента И 11, выход второго сумматора 22 подсоединен к первым входам второй схемы сравнения 24, второй вход которой подсоединен к выходу пятого регистра 23.

Данное устройство позволяет решить задачу разрезания набора из Y заготовок с одинаковой длиной, равной L, на заготовки с длинами L₁, L₂, …, L_m, с минимальными остатками, то есть найти:

min dL=YL-(k₁L₁+k₂L₂+…+k_mL_m)≥0,

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

k_i - искомое число требуемых заготовок с длиной L_i (i=1,…,m),

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

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

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

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

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

группу из n счетчиков 4₁, 4₂, …, 4_n (n - число возможных вариантов разрезания заготовок длиной L), группу из m*n первых регистров 12₁₁, …, 12_mn (m - общее число типов различных типов заготовок), группу из m вторых регистров 17₁, 17₂, …, 17_m, группу из n третьих регистров 5₁, 5₂, …, 5_n, группу из n четвертых регистров 19₁, 19₂, …, 19_n, пятый регистр 23, группу из m первых сумматоров 15₁, 15₂, …, 15_m, второй сумматор 22, группу из m первых схем сравнения 16₁, 16₂, …, 16_m, вторую схему сравнения 24, элемент И 11, первый выход устройства 27, вторые выходы устройства 28₁, 28₂, …, 28_n, причем выход каждого счетчика 4_j (j=1,2,…,n) подсоединен к первому входу одноименного третьего регистра 5_j, выходы третьих регистров 5₁, 5₂, …, 5_n являются вторыми выходами устройства 28₁, 28₂, …, 28_n, выход каждого первого сумматора 15_i (i=1,2,…,m) подсоединен к первому входу одноименной первой схемы сравнения 16i, второй вход которой подсоединен к выходу одноименного второго регистра 17_i, выход каждой первой схемы сравнения 16_i подсоединен к соответствующему входу первой группы входов элемента И 11, выход второго сумматора 22 подсоединен к первым входам второй схемы сравнения 24, второй вход которой подсоединен к выходу пятого регистра 23, дополнительно введены генератор тактовых импульсов (ГТИ) 1, триггер разрешения 2, триггер готовности результата 3, группа из (n-k) третьих схем сравнения 6₁, 6₂, …, 6_n-k, группа из k шестых регистров 7₁, 7₂, …, 7_k, группа из k третьих сумматоров 8₁, 8₂, …, 8_k группа из k четвертых схем сравнения 9₁, 9₂, …, 9_k, k каскадов 10₁, 10₂, …, 10_k, группа из m*n четвертых сумматоров 13₁₁, …, 13_mn, группа из m*n седьмых регистров 14₁₁, …, 14_mn, группа из m восьмых регистров 18₁, 18₂, …, 18_m, группа из n пятых сумматоров 20₁, 20₂, …, 20_n, группа из n девятых регистров 21₁, 21₂, …, 21_n, вход пуска устройства 25, вход сброса устройства 26, третьи выходы устройства 29₁, 29₂, …, 29_n, четвертые выходы устройства 30, причем вход сброса устройства 26 соединен с входами синхронной установки в нулевое состояние вторым входом триггера разрешения 2, вторым входом триггера готовности результата 3, вторыми входами группы из n счетчиков 4₁, 4₂, …, 4_n, третьими входами группы из n третьих регистров 5₁, 5₂, …, 5_n, вторыми входами группы из m*n седьмых регистров 14₁₁, …, 14_mn, вторыми входами группы из n девятых регистров 21₁, 21₂, …, 21_n, вторым входом синхронной установки в единичное состояние пятого регистра 23, выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 4₁, 4₂, …, 4_n, вторыми входами группы из n третьих регистров 5₁, 5₂, …, 5_n, первыми входами группы из m*n седьмых регистров 14₁₁, …, 14_mn, первыми входами группы из n девятых регистров 21₁, 21₂, …, 21_n, первыми входами группы из m восьмых регистров 18₁, 18₂, …, 18_m, первым входом пятого регистра 23, группа из n счетчиков 4₁, 4₂, …, 4_n разделена на k каскадов 10_k по n_t (t=1,2,…,k) счетчиков в каждом, при этом n₁+n₂+…+n_k=n, в каждый каскад 10_t также включены n_t соответствующих третьих регистров 5_t,1, …, 5_t,nt, (n_t-1) третьих схем сравнения 6_t,1, …, 6_t,nt, (n_t-1), шестой регистр 7_t, третий сумматор 8_t, четвертая схема сравнения 9_t, m*nt соответствующих первых регистров 12, m*n_t соответствующих четвертых сумматоров 13, m*n_t соответствующих седьмых регистров 14, n_t соответствующих четвертых регистров 19_t, m*n_t соответствующих пятых сумматоров 20, n_t соответствующих девятых регистров 21, причем в каждом t-м каскаде 10_t выходы каждого счетчика 4_t,2, …, 4_t,nt подсоединены ко второй группе входов соответствующей третьей схемы сравнения 6_t,1, …, 6_t,nt-1, первая группа входов которых подсоединена к выходам соответствующего шестого регистра 7_t, выходы каждого счетчика 4_t,2, …, 4_t,nt подсоединены к соответствующим одноименным входам третьего сумматора 8_t, выход которого подсоединен ко вторым входам четвертой схемы сравнения 9_t, первые входы которой подсоединены к выходам соответствующего шестого регистра 7_t, второй выход четвертой схемы сравнения 9_t подсоединен к соответствующему входу второй группы входов элемента И 11, вход пуска устройства 25 соединен с третьим входом разрешения работы триггера разрешения 2, выход которого в первом каскаде 10₁ соединен с входами разрешения работы третьим входом первого счетчика 4₁₁, третьим входом первой схемы сравнения 9₁ из группы k четвертых схем сравнения 9₁, 9₂, …, 9_k, третьими входами первых регистров 14₁₁, 14₂₁, …, 14_m1 из группы m*n седьмых регистров 14₁₁, …, 14_mn, третьим входом первого регистра 21₁ из группы n девятых регистров 21₁, 21₂, …, 21_n, в каждом t-м каскаде 10_t первый выход каждой из четвертых схем сравнения 9_t соединен с входом синхронной установки в нулевое состояние четвертым входом соответствующих первых счетчиков 4_t,1, четвертыми входами первых регистров 14₁₁, 14₂₁, …, 14_m1, из группы седьмых регистров 14, четвертым входом первого регистра 21₁ из группы n девятых регистров 21, а также входами разрешения работы третьим входом первой схемы сравнения 6_t,1 из группы третьих схем сравнения 6 и третьим входом второго счетчика 4_t,2, в каждом t-м каскаде 10_t выходы схем сравнения 6_t,p (p=1,3,…,n_t-2) соединены с входами разрешения третьим входом следующего счетчика 4_t,р+2, третьим входом следующей схемы сравнения 6_t,p+1, третьими входами соответствующих следующих седьмых регистров 14_t,p+2, третьим входом соответствующего следующего девятого регистра 21_t,р+2, а также соединены с входами синхронной установки в нулевое состояние четвертым входом соответствующего счетчика 4_t,p+1, четвертыми входами соответствующих седьмых регистров 14_t,p+1 и четвертым входом соответствующего девятого регистра 21_t,p+1 каскада 10_t, выход последней схемы сравнения 6_t,nk-1 в каждом каскаде 10_t(t=1,2,…,k-1) соединен с входом синхронной установки в нулевое состояние четвертым входом соответствующего счетчика 4_t,nk, четвертыми входами соответствующих седьмых регистров 14_t,nk и четвертым входом соответствующего девятого регистра 21_t,nk каскада 10_t, а также подсоединен в следующем (t+1)-м каскаде 10_t+1 к входам разрешения работы третьим входом первого счетчика 4_t+1,1, третьим входом схемы сравнения 9_t+1, третьими входами соответствующих седьмых регистров 14_1,t+1, 14_2,t+1, …, 14_m,t+1, третьим входом соответствующего девятого регистра 21_1,t+1, в последнем k-м каскаде 10_k выход последней схемы сравнения 6_k,nk-1 соединен с входом синхронной установки в нулевое состояние четвертым входом соответствующего счетчика 4_k,nk, четвертыми входами соответствующих седьмых регистров 14_1,nk, 14_2,nk, …, 14_m,nk и четвертым входом соответствующего девятого регистра 21_n из каскада 10_k, а также подсоединен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и третьему входу синхронной установки в единичное состояние триггера готовности результата 3, выход триггера готовности результата 3 является первым выходом устройства 27, выход каждого регистра 12_ij из группы m*n первых регистров 12₁₁, …, 12_mn (i=1,2,…,m, j=1,2,…,n) подсоединен к первым входам соответствующего сумматора 13_ij из группы m*n четвертых сумматоров 13₁₁, …, 13_mn, выходы которых подсоединены к информационным входам соответствующего регистра 14₁₁ из группы m*n седьмых регистров 14₁₁, …, 14_mn, выходы которого соединены со вторыми входами соответствующего сумматора 13_ij и одноименными входами соответствующего сумматора 15_i из группы m первых сумматоров 15₁, 15₂, …, 15_m, выходы которых подсоединены к третьим информационным входам одноименных регистров 18_i из группы m восьмых регистров 18₁, 18₂, …, 18_m, выходы которых являются третьими выходами устройства 29₁, 29₂, …, 29_m, выходы регистров 19_j из группы n четвертых регистров 19₁, 19₂, …, 19_n соединены с первыми входами одноименных сумматоров 20_j из группы n пятых сумматоров 20₁, 20₂, …, 20_n, выходы которых подсоединены к информационным входам соответствующего регистра 21_j из группы n девятых регистров 21₁, 21₂, …, 21_n, выходы которых соединены со вторыми входами соответствующего сумматора 20_j и одноименными входами второго сумматора 22, выходы которого подсоединены к информационным входам пятого регистра 23, выходы которого являются четвертыми выходами устройства 30, выход второй схемы сравнения 24 подключен к третьему входу элемента И 11, выход которого соединен с входами разрешения записи четвертыми входами группы из n третьих регистров 5₁, 5₂, …, 5_n, третьим входом пятого регистра 23 и вторыми входами регистров из группы m седьмых регистров 18₁, 18₂, …, 18_m.

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

На фиг.1 приняты следующие обозначения: генератор тактовых импульсов (ГТИ) 1, триггер разрешения 2, триггер готовности результата 3, группа из n счетчиков 4₁, 4₂, …, 4_n (n - число возможных вариантов разрезания заготовок длиной L), группа из n третьих регистров 5₁, 5₂, …, 5_n, группа из n третьих схем сравнения 6₁, 6₂, …, 6_mn, группа из k шестых регистров 7₁, 7₂, …, 7_k, группа из k третьих сумматоров 8₁, 8₂, …, 8_k группа из k четвертых схем сравнения 9₁, 9₂, …, 9_k, k каскадов 10₁, 10₂, …, 10_k, элемент И 11, группа из m*n первых регистров 12₁₁, …, 12_mn (m - общее число типов различных типов заготовок), группа из m*n четвертых сумматоров 13₁₁, …, 13_mn, группа из m*n седьмых регистров 14₁₁, …, 14_mn, группа из m первых сумматоров 15₁, 15₂, …, 15_m, группа из m первых схем сравнения 16₁, 16₂, …, 16_m, группа из m вторых регистров 17₁, 17₂, …, 17_m, группа из m восьмых регистров 18₁, 18₂, …, 18_m, группа из n четвертых регистров 19₁, 19₂, …, 19_n, группа из n пятых сумматоров 20₁, 20₂, …, 20_n, группа из n девятых регистров 21₁, 21₂, …, 21_n, второй сумматор 22, пятый регистр 23, вторая схема сравнения 24, вход пуска устройства 25, вход сброса устройства 26, первый выход устройства 27, вторые выходы устройства 28₁, 28₂, …, 28_n, третьи выходы устройства 29₁, 29₂, …, 29_n, четвертые выходы устройства 30.

Выход ГТИ 1 соединен с входами синхронизации группы счетчиков и соответствующих групп регистров.

Внешний вход сброса устройства 26 соединен с входами синхронной установки в нулевое состояние вторым входом триггера разрешения 2, вторым входом триггера готовности результата 3, вторыми входами группы из n счетчиков 4₁, 4₂, …, 4_n, третьими входами группы из n третьих регистров 5₁, 5₂, …, 5_n, вторыми входами группы из m*n седьмых регистров 14₁₁, …, 14_mn, вторыми входами группы из n девятых регистров 21₁, 21₂, …, 21_n, вторым входом синхронной установки в единичное состояние пятого регистра 23.

В устройстве введено k каскадов 10₁, 10₂, …,10_k элементов, при этом каждый каскад 10_t содержит по n_t (t=1,2,…,k) счетчиков, при этом n₁+n₂+…+n_k=n. В каждый каскад 10_t также включены n_t соответствующих третьих регистров 5_t,1,…,5_t,nt, (n_t-1) третьих схем сравнения 6_t,1, …, 6_t,nt-1, шестой регистр 7_t, третий сумматор 8_t, четвертая схема сравнения 9_t, m*n_t соответствующих первых регистров 12, m*n_t соответствующих четвертых сумматоров 13, m*n_t соответствующих седьмых регистров 14, n_t соответствующих четвертых регистров 19, n_t соответствующих пятых сумматоров 20, n_t соответствующих девятых регистров 21. При этом в каждом t-м каскаде 10_t выход каждого счетчика 4_t,1, …, 4_t,nt подсоединен к первым входам одноименного третьего регистра 5_j, кроме того, выходы каждого счетчика 4_t,2, …, 4_t,nt подсоединены ко второй группе входов соответствующей третьей схемы сравнения 6_t,1, …, 6_t,nt-1, первая группа входов которых подсоединена к выходам соответствующего шестого регистра 7_t, выходы каждого счетчика 4_t,1, …, 4_t,nt подсоединены к соответствующим одноименным входам третьего сумматора 8_t, выход которого подсоединен ко вторым входам четвертой схемы сравнения 9_t, первые входы которой подсоединены к выходам соответствующего шестого регистра 7_t, второй выход четвертой схемы сравнения 9_t подсоединен к соответствующему входу второй группы входов элемента И 11.

Вход пуска устройства 25 соединен с третьим входом разрешения работы триггера разрешения 2, выход которого в первом каскаде 10_t соединен с входами разрешения работы третьим входом первого счетчика 4_t,1, третьим входом первой схемы сравнения 91 из группы k четвертых схем сравнения 9₁, 9₂, …, 9_k, третьими входами первых регистров 14₁₁, 14₂₁, …, 14_m1 из группы m*n седьмых регистров 14₁₁, …, 14_mn, третьим входом первого регистра 21₁ из группы n девятых регистров 21₁, 21₂, …, 21_n.

Первый выход каждой из четвертых схем сравнения 9_t в каскаде 10_t соединен с входом синхронной установки в нулевое состояние четвертым входом соответствующих первых счетчиков 4_t,1, четвертыми входами соответствующих первых регистров 14₁₁, 14₂₁, …, 14_m1, из группы седьмых регистров 14, четвертым входом первого регистра 21₁ из группы n девятых регистров 21, а также входами разрешения работы первым входом соответствующих схем сравнения 6_t,1 из группы третьих схем сравнения 6 и третьим входом соответствующего второго счетчика 4_t,2.

В каждом t-м каскаде 10_t выходы схем сравнения 6_t,р (р=1,3,…,n_t-2) соединены с входами разрешения третьим входом следующего счетчика 4_t,р+2, первым входом следующей схемы сравнения 6_t,p+1, третьими входами соответствующих следующих седьмых регистров 14_1,p+2, …, 14_m,р+2, третьим входом соответствующего следующего девятого регистра 21_t,р+2, а также соединены с входами синхронной установки в нулевое состояние четвертым входом соответствующего счетчика 4_t,р+1, четвертыми входами соответствующих седьмых регистров 14_1,p+1, …, 14_m,p+1 и четвертым входом соответствующего девятого регистра 21_t,p+1 каскада 10_t.

Выход последней схемы сравнения 6_t,nk-1 в каждом t-м каскаде 10_t (t=1,2,…,k-1) соединен с входом синхронной установки в нулевое состояние четвертым входом соответствующего счетчика 4_t,nk, четвертыми входами соответствующих седьмых регистров 14_1,nk, …, 14_m,nk и четвертым входом соответствующего девятого регистра 21_t,nk каскада 10_t, а также подсоединен в следующем (t+1)-м каскаде 10_t+1 к входам разрешения работы третьим входом первого счетчика 4_t+1,1, третьими входами соответствующих седьмых регистров 14_1,t+1, 14_2,t+1, …, 14_m,t+1, третьим входом соответствующего девятого регистра 21_1,t+1.

В последнем k-м каскаде 10_k выход последней схемы сравнения 6_k,nk-1 соединен с входом синхронной установки в нулевое состояние четвертым входом соответствующего счетчика 4_k,nk, четвертыми входами соответствующих седьмых регистров 14_1,nk, 14_2,nk, …, 14_m,nk и четвертым входом соответствующего девятого регистра 21_n из каскада 10_k, a также подсоединен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и третьему входу синхронной установки в единичное состояние триггера готовности результата 3, выход триггера готовности результата 3 является первым выходом устройства 27. Выходы третьих регистров 5₁, 5₂, …, 5_n являются вторыми выходами устройства 28₁, 28₂, …, 28_n.

Выход каждого регистра 12_ij из группы m*n первых регистров 12₁₁, …, 12_mn (i=1,2,…,m, j=1,2,…,n) подсоединен к первым входам соответствующего сумматора 13_ij из группы m*n четвертых сумматоров 13₁₁, …, 13_mn, выходы которых подсоединены к информационным входам соответствующего регистра 14₁₁ из группы m*n седьмых регистров 14₁₁, …, 14_mn, выходы которого соединены со вторыми входами соответствующего сумматора 13_ij и одноименными входами соответствующего сумматора 15, из группы m первых сумматоров 15₁, 15₂, …, 15_m, выходы которых подсоединены к третьим информационным входам одноименных регистров 18, из группы m восьмых регистров 18₁, 18₂, …, 18_m, выходы которых являются третьими выходами устройства 29₁, 29₂, …, 29_m.

Выход каждого первого сумматора 15_i (i=1,2,…,m) подсоединен к первому входу одноименной первой схемы сравнения 16_i, второй вход которой подсоединен к выходу одноименного второго регистра 17_i, выход каждой первой схемы сравнения 16_i подсоединен к соответствующему входу первой группы входов элемента И 11.

Выходы регистров 19_j из группы n четвертых регистров 19₁, 19₂, …, 19_n соединены с первыми входами одноименных сумматоров 20_j из группы n пятых сумматоров 20₁, 20₂, …, 20_n, выходы которых подсоединены к информационным входам соответствующего регистра 21_j из группы n девятых регистров 21₁, 21₂, …, 21_n, выходы которых соединены со вторыми входами соответствующего сумматора 20_j и одноименными входами второго сумматора 22.

Выходы второго сумматора 22 подсоединены к информационным входам пятого регистра 23 и к первым входам второй схемы сравнения 24, вторые входы второй схемы сравнения 24 подсоединены к выходу пятого регистра 23, выходы которого являются четвертыми выходами устройства 30.

Выход второй схемы сравнения 24 подключен к третьему входу элемента И 11, выход которого соединен с входами разрешения записи четвертыми входами группы из n третьих регистров 5₁, 5₂, …, 5_n, третьим входом пятого регистра 23 и вторыми входами регистров из группы m седьмых регистров 18₁, 18₂, …, 18_m.

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

Данное устройство позволяет решить задачу разрезания набора из Y исходных заготовок с различной длиной L_t на требуемые заготовки с длинами Z_i, с минимальными суммарными остатками S и задавать в группах возможное количество исходных заготовок различной длины L_t, то есть найти:

min S=(y₁L₁+y₂L₂+…+y_kL_k)-(v₁Z₁+v₂Z₂+…+v_mZ_m)≥0

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

v_i - число требуемых заготовок с длиной Z_i (i=1,…,m),

y_t - искомое число исходных заготовок с длиной L_t (t=1,…,k), при этом (y₁+y₂+…+y_k)=Y,

k - количество типов различных исходных заготовок,

Y - общее суммарное потребное количество исходных заготовок,

S - суммарные остатки после разрезания исходных заготовок.

В устройстве введено k каскадов 10_t (t=1,2,…,k), в соответствии с количеством k-типов различных исходных заготовок длины L_t. В каждый каскад 10_t введено n_t счетчиков (n_t - число возможных вариантов разрезания заготовок длиной L_t на требуемые заготовки с длиной Z_i (i=1,…,m)). При этом общее число n возможных вариантов разрезания исходных заготовок составляет n=n₁+n₂+…+n_k. В каждом каскаде 10_t задается модуль счета каждого счетчика 4_t, который соответствует возможному количеству исходных заготовок длиной L_t (t=1,…,k). В каждом каскаде 10_t также выполняется проверка, чтобы суммарное значение задаваемых кодов исходных заготовок на всех счетчиках 4 каскада 10_t не превышало значение модуля в каскаде 10_t, а при превышении модуля младший счетчик 4_1,t каскада 10_t синхронно устанавливается в нулевое состояние. Введенная проверка суммарного модуля каждого каскада 10_t позволяет контролировать количество исходных заготовок и уменьшает задаваемый перебор входных комбинаций.

В исходном состоянии в каждом регистре в группе m*n первых регистров 12₁₁, …, 12_mn устанавливается код количества i-x заготовок (i=1,…,m) в j-м варианте разрезания (j=1,…,n, где n - число всех возможных вариантов разрезания заготовок), в группе из m вторых регистров 17₁, 17₂, …, 17_m устанавливается код v_i числа требуемых заготовок с длиной Z_i, в группе из n четвертых регистров 19₁, 19₂, …, 19_n устанавливается код s_j длины остатка в j-м варианте разрезания, в группе из k шестых регистров 7₁, 7₂, …, 7_k устанавливается код M_t возможного количества исходных заготовок длиной L_t (t=1,…,k), при этом число (M_t+1) является модулем счетчика в каждом каскаде 10_t (t=1,…,k).

Группа счетчиков 4₁, 4₂, …, 4_n предназначена для задания текущих значений количества исходных заготовок из числа возможных M_t в соответствующем каскаде 10_t. В процессе решения задачи в группе из m*n седьмых регистров 14₁₁, …, 14_mn накапливаются текущие количества i-x заготовок в j-м варианте разрезания, а в группе из n девятых регистров 21₁, 21₂, …, 21_n накапливаются текущие значения остатков S_j заготовок в j-м варианте разрезания. В группе из n третьих регистров 5₁, 5₂, …, 5_n фиксируется код y_t требуемого числа исходных заготовок с длиной L_t, в группе из m восьмых регистров 18₁ 18₂, …, 18_m фиксируется полученный код количества требуемых заготовок с длиной Z_i (i=1,…,m), а в пятом регистре 23 фиксируется общее суммарное значение остатка S.

В каждом t-м каскаде 10_t (t=1,…,k) на n_t элементах счетчиков 4_t,1, …, 4_t,nt, третьих регистрах 5_t,1, …, 5_t,nt третьих схемах сравнения 6_t,1, …, 6_t,nt-1, шестом регистре 7_t, третьем сумматоре 8_t, четвертой схеме сравнения 9_t и соответствующих связях реализуется счетчик с модулем (M_t+1), где M_t соответствует допустимому количеству исходных заготовок в t-м каскаде 10_t.

В каждом каскаде 10_t схемы сравнения 6_t,h (h=1,…,nt-1) сравнивают значения кодов счетчиков 4_t,h+1 с модулем M_t, установленным на шестых регистрах 7_t и при достижении каждым счетчиком 4_t,h+1 допустимого значения на выходе соответствующей третьей схемы сравнения 6_t,h формируется единичный сигнал. По данному единичному сигналу, на выходе третьей схемы сравнения 6_t,h (h=1,…,n_t-1), проводится синхронная установка в нулевое состояние счетчика 4_1,h+2, разрешается увеличение следующего счетчика 4_t,h+2, разрешается работа следующей третьей схемы сравнения 6_t,h+1, а также проводится синхронная установка в нулевое состояние значения текущего количества i-х заготовок в j-м варианте разрезания в соответствующих седьмых регистрах 14 и синхронная установка в нулевое состояние текущего значения остатка S_j в соответствующем девятом регистре 21.

Одновременно значения кодов всех счетчиков 4 в каждом t-м каскаде 10_t (t=1,…,k) суммируются на третьих сумматорах 8_t, значение суммы сравнивается на четвертых схемах сравнения 9_t с модулем M_t возможного количества исходных заготовок длиной L_t, и на первом выходе соответствующей схемы сравнения 9_t формируется единичный сигнал, если значение модуля M_t меньше или равно суммарному значению количества требуемых исходных заготовок. По данному единичному сигналу проводится синхронная установка в нулевое состояние первого счетчика 4_t,1, значения текущего количества i-x заготовок в j-м варианте разрезания в первых регистрах 14₁₁, …, 14_m1 из группы седьмых регистров 14 и синхронная установка в нулевое состояние текущего значения остатка S_j в первом девятом регистре 21₁ из девятых регистров 21, а также разрешается увеличение следующего счетчика 4_t,2 и разрешается работа первой схемы сравнения 6_t,1 из третьих схем сравнения 6. На втором выходе соответствующей схемы сравнения 9_t формируется единичный сигнал, если значение модуля M_t на шестых регистрах 7_t равно или больше значения суммы на третьих сумматорах 8_t.

В m*n группах, состоящих из элементов первых регистров 12₁₁, …, 12_mn, четвертых сумматоров 13₁₁, …, 13_mn, седьмых регистров 14₁₁, …, 14_mn и соответствующих связях, реализуется последовательное накопление суммарного текущего количества i-x заготовок в j-м варианте разрезания, которое вычисляется за счет увеличения предыдущего количества заготовок на седьмых регистрах 14₁₁, …, 14_mn на количество i-x заготовок в j-м варианте, заданном на первых регистрах 12₁₁, …, 12_mn, на четвертых сумматорах 13₁₁, …, 13_mn и фиксации значения этого суммарного текущего количества заготовок на седьмых регистрах 14₁₁, …, 14_mn.

Аналогично в n группах, состоящих из элементов четвертых регистров 19₁, 19₂, …, 19_n, пятых сумматоров 20₁, 20₂, …, 20_n, девятых регистров 21₁, 21₂, …, 21_n и соответствующих связях, реализуется последовательное вычисление суммарных остатков S_j в j-м варианте разрезания и фиксации этих значений на девятых регистрах 21₁, 21₂, …, 21_n.

В m группах, состоящих из элементов первых сумматоров 15₁, 15₂, …, 15_m, первых схем сравнения 16₁, 16₂, …, 16_m, вторых регистров 17₁, 17₂, …, 17_m, восьмых регистров 18₁, 18₂, …, 18_m и соответствующих связях, реализуется вычисление суммарного текущего количества i-x заготовок всех вариантов разрезания на первых сумматорах 15₁, 15₂, …, 15_m, сравнение значения суммы с требуемым количеством v_i с длиной Z_i (i=1,…,m), установленном на вторых регистрах 17_i, и фиксации значения суммы i-x заготовок на восьмых регистрах 18₁, 18₂, …, 18_m при соответствии критериям решения задачи, т.е. при min S. На выходах первых схем сравнения 16_i формируется единичный сигнал, если суммарное количество i-x заготовок всех вариантов разрезания превышает или равно требуемому количеству заготовок v_i с длиной Z_i.

Аналогично на втором сумматоре 22, пятом регистре 23, второй схеме сравнения 24 и соответствующих связях, реализуется вычисление суммарного остатка S и фиксация этого значения на пятом регистре 23 при min S. На выходе второй схемы сравнения 24 формируется единичный сигнал, если текущий суммарный остаток S_тек на втором сумматоре 23 меньше или равен ранее зафиксированного остатка S на пятом регистре 23.

Сигналы с выходов первых схем сравнения 16₁, 16₂, …, 16_m, второй схемы сравнения 24 и вторых выходов четвертых схем сравнения 9₁, 9₂, …, 9_k поступают на соответствующие входы элемента И 11, на выходе которого единичный сигнал EN=1 формируется в случае всех единичных входных сигналов. В этом случае в устройстве получены минимальные текущие остатки S_тек, суммарное количество i-x заготовок всех вариантов разрезания превышает или равно требуемому количеству заготовок v_i с длиной Z_i и требуемые количества y_t исходных заготовок не превышают заданных возможных количеств исходных заготовок различной длины L_t.

Единичный сигнал EN=1 на выходе элемента И 11 разрешает запись в группу третьих регистров 5₁, 5₂, …, 5_n с выходов счетчиков 4₁, 4₂, …, 4_n текущих значений требуемые количества y_j исходных заготовок в j-м варианте разрезания, запись текущего минимального остатка S_тек в пятый регистр 23 и запись в регистры 18₁, 18₂, …, 18_m полученного суммарного количества i-x заготовок всех вариантов разрезания.

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

При подаче сигнала на вход сброса устройства 26 синхронно по фронту импульса с ГТИ 1 в нулевое состояние устанавливаются триггер разрешения 2, триггер готовности результата 3, все счетчики 4₁, 4₂, …, 4_n, третьи регистры 5₁, 5₂, …, 5_m, пятый регистр 23, седьмые регистры 14₁₁, …, 14_mn, девятые регистры 21₁, 21₂, …, 21_n.

Работа устройства начинается после подачи сигнала ПУСК на вход устройства 25, по которому синхронно с импульсом от ГТИ 1 устанавливаются в единичное состояние выход триггера разрешения 2, который соединен с входом разрешения счета первого счетчика 4_1,1, входом разрешения первой схемы сравнения 9₁ из группы четвертых схем сравнения 9 и входами разрешения записи в первые регистры 14₁₁, …, 14_m1 из группы седьмых регистров 14 и первый регистр 21₁ из группы девятых регистров 21.

На следующих тактах ГТИ 1 в первом счетчике 4₁ задается текущее значение количества исходных заготовок из числа возможных M₁, в первые седьмые регистры 14₁₁, …, 14_m1 из группы седьмых регистров 14 записываются текущие значения количества i-x заготовок при первом варианте разрезания заготовок j=1, а в первый девятый регистр 21₁ записывается текущее значение остатков S в первом варианте разрезания, которые вычисляются соответственно на четвертых сумматорах 13₁₁, …, 13_m1 и пятом сумматоре 20₁.

В таблице 1 по тактам ГТИ 1 для каскада 10₁, состоящего из трех счетчиков (при n₁=3 - три варианта разрезания заготовок) с модулем счета M_t+1=4 (код M_t=3, соответствующий возможному количеству исходных заготовок длиной L₁, установлен на регистре 7₁), приведены значения кодов 0, 1, 2 или 3 (в двоичном и десятичном виде) на счетчиках 4₁, 4₂, 4₃ (счетчик 4₁ младший), суммарное значение кодов счетчиков на сумматоре 81 и единичные сигналы на выходах схем сравнения 6₁₁ 6₁₂ и 9₁.

В первом каскаде 10₁ при достижении первым счетчиком 4_1,1 значения модуля M₁=3, записанного в регистре 7₁, на выходе третьего сумматора 8₁ тоже будет установлен код, равный M₁=3, так как на остальных счетчиках каскада установлены нулевые значения. Код с выхода сумматора 8₁ поступает на первый вхо