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

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

Устройство для решения задач целочисленного линейного программирования, содержащее группу из 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, отличающееся тем, что в него дополнительно введены генератор тактовых импульсов (ГТИ) 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_m разделена на 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-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,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₁ соединен с входами разрешения работы третьим входом первого счетчика 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,р+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)-M каскаде 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, из группы 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.

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

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

Известно устройство для решения задач целочисленного линейного программирования (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₁ поступает на первый вход схемы сравнения 9₁, на второй вход которой поступает код модуля M₁=3 с выхода регистра 71. Единичный сигнал на первом выходе схемы сравнения 9₁ (в таблице 1 такт 3) формируется только в том случае, если суммарный код текущего количества заготовок на первом сумматоре 8₁ больше или равен коду допустимого количества заготовок, установленного на регистре 7₁. По данному единичному сигналу, на следующем такте ГТИ устанавливаются в нулевое состояние счетчик 4_1,1, регистры 14₁₁, , 14_m1 и регистр 21₁, разрешается увеличение счетчика 4_1,2 и сравнение на схеме 6 _1,1, а также проводится запись текущих значений количества i-x заготовок в регистры 14₁₁, , 14_m2, а в регистр 21₂ записывается текущее значение остатков во втором варианте разрезания при j=2.

Далее на следующих тактах ГТИ 1 увеличивается значение счетчика 4_1,1 и формирование значений текущих заготовок и остатков. Одновременно значения кодов счетчиков 4_1,1 и 4_1,2 суммируются на третьем сумматоре 8₁ . При значении суммы, равной коду на регистре 7₁ аналогично формируется единичный сигнал на первом выходе схемы сравнения 9₁ (в таблице 1 такты 6, 8, 9). Кроме того, на такте 9 единичный сигнал формируется и на выходе схемы сравнения 6 _1,1, по которому на следующем такте ГТИ устанавливаются в нулевое состояние счетчик 4_1,2, регистры 14 _1,2, , 14_m2 и регистр 21₂, разрешается увеличение счетчика 4_1,3 и сравнение на схеме 6 _1,2, а также проводится запись текущих значений количества i-x заготовок в регистры 14₁₃, , 14_m3, и остатков в регистр 21₃ для третьего варианта разрезания заготовок при j=3.

Далее на следующих тактах ГТИ 1, если суммарный код текущего количества заготовок на первом сумматоре 8₁ больше или равен допустимому количеству заготовок, установленному на регистре 7₁, аналогично вырабатываются единичные сигналы на выходах схем сравнения (в таблице 1 такты 12, 14-16, 18-25). Одновременно на втором выходе схемы сравнения 91 (колонка 6 в таблице 1) формируется единичный сигнал, если суммарное количество требуемых заготовок не превышает значение модуля M₁ =3 (в таблице 1 такты 0-15, 17-19, 22).

При достижении в первом каскаде 10₁ счетчиком 4_1,nt (4 _1,3 в таблице 1) значения модуля M_t на выходе третьей схемы сравнения 6_1,n1-1 (6_1,2 в таблице 1) формируется единичный сигнал, по которому разрешается работа второго каскада 10₂ - увеличение счетчика 4 _2,1 и работа схемы сравнения 9₂, а также проводится запись в первые элементы соответствующих седьмых регистров 14 текущих значений количества i-x заготовок при первом варианте разрезания заготовок j₂=1 во втором каскаде 10 ₂, а в соответствующий девятый регистр 21 записывается текущее значение остатков, которые вычисляются соответственно на четвертых сумматорах 13 и пятом сумматоре 20. Далее по тактам ГТИ 1 в каскаде 10₂ выполняются действия аналогично как для первого каскада 10₁.

При достижении во втором каскаде 10₂ счетчиком 4_2,n2 значения модуля M₂ на выходе третьей схемы сравнения 6 _2,n2-1 формируется единичный сигнал, по которому разрешается работа третьего каскада 10₃. Затем аналогично работают следующие каскады 10₃, , 10_k.

При достижении в k-м каскаде 10k счетчиком 4_k,nk (4_n) значения модуля M_k, на выходе третьей схемы сравнения 6_k,nk-1 формируется единичный сигнал, который поступает на синхронные вход установки в нулевое состояние триггера разрешения 2 и вход установки в единичное состояние триггера готовности результата 3, в результате чего на выходе устройства 27 формируется сигнал ГОТОВ об окончании работы устройства. Нулевое значение сигнала на выходе триггера 2 останавливает счетный режим счетчика 4 ₁, a следовательно, и других счетчиков 4₂, , 4_n.

В результате работы устройства будут установлены:

сигнал ГОТОВ окончания работы устройства на первом выходе 27;

коды y_j искомого количества исходных заготовок с длиной L при j-м варианте разрезания (j=1, ,n) на вторых выходах 28₁, 28₂, , 28_n;

коды количества полученных заготовок Z, по m различным типам (i=1, ,m) на третьих выходах 29₁, 29₂, , 29_m;

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

В предлагаемом устройстве вычисление текущих значений количества i-x заготовок и остатков в j-м варианте разрезания заготовок L проводится на четвертых сумматорах 13 и пятых сумматорах 20 сложением соответственно количества заготовок и остатков, полученных на предыдущем такте, и соответствующими значениями для одной заготовки j-го варианта разрезания заданных соответственно на первых регистрах 12 и четвертых регистрах 19, так как на каждом шаге моделирования текущие значения могут увеличиваться только на значения количества заготовок и остатков для одной исходной заготовки. В прототипе текущие значения количества i-x заготовок и остатков в j-м варианте разрезания заготовок L вычисляются в блоках умножения на каждом шаге, как произведение соответствующих значений для одной заготовки j-го варианта разрезания на текущее количество исходных заготовок задаваемых на счетчиках 4_j . При реализации блоков умножения необходимо значительно больше аппаратных и временных затрат на вычисление в сравнении с сумматорами 13, 20 и регистрами 14, 21 в заявляемом устройстве.

Кроме того, в предлагаемом устройстве в отличие от прототипа имеется возможность задания по каскадам 10₁, 10 ₂, , 10_k возможного допустимого количества исходных заготовок на шестых регистрах 7₁, 7₂, , 7_k.

В предлагаемом устройстве также сокращается перебор количества задаваемых входных комбинаций разрезания исходных заготовок и проверяется сумма исходных заготовок по каскадам на допустимое количество, что выполняется на сумматорах 8 и схемах сравнения 9. В предлагаемом устройстве количество входных комбинаций на входах t-го каскада определяется, как

N_tустр=(M_t+1)^nt-1 + N_nt,Mt,

где количество дополнительных входных комбинаций N_nt,Mt можно вычислить итерационно при суммировании предыдущих значений для n_t-1 и изменении модуля от 1 до M_t

,

В таблице 2 приведено количество дополнительных входных комбинаций N_nt,Mt в зависимости от модуля счета M_t+1 в t-м каскаде, где M_t возможное количество исходных заготовок в t-м каскаде, и количества вариантов n_t разрезания исходных заготовок в t-м каскаде. Для n_t =1 количество дополнительных входных комбинаций N_nt,Mt соответствует натуральном ряду чисел - значению M_t. Для n_t=2 количество дополнительных входных комбинаций N_nt,Mt соответствует арифметической прогрессии предыдущих значений натурального ряда M_t. Для следующих строк количество комбинаций N_nt,Mt равно сумме значений в предыдущей строке. Например, для M_t=3 и n_t=3 из таблицы 2 получим N_3,3=10 и, следовательно, N_tустр=16+10=26, что соответствует количеству входных комбинаций, приведенному в таблице 1. В таблице 3 приведено соотношение для t-го каскада между полным перебором входных комбинаций N_пер и количеством входных комбинаций Nустр, задаваемом в предлагаемом устройстве. Из таблицы 3 следует, что количество входных комбинаций в t-м каскаде при увеличении количества вариантов разрезания заготовок n_t сокращается в M_t раз. Соответственно для k каскадов сокращение входных комбинаций будет пропорционально произведению модулей каскадов M₁*M₂* *M_k.

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