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



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

 


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

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

Изобретение относится к автоматике и вычислительной технике. Техническим результатом является увеличение быстродействия и надежности устройства, уменьшение аппаратных затрат, расширение функциональных возможностей в части возможности задания допустимого количества исходных заготовок в каждом каскаде. Устройство для решения задач целочисленного линейного программирования содержит генератор тактовых импульсов 1, триггеры разрешения 2, готовности результата 3, группы из n счетчиков 41, 42, …, 4n (n - число возможных вариантов разрезания заготовок длиной L), n третьих регистров 51, 52, …, 5n, n третьих схем сравнения 61, 62, …, 6n, k шестых регистров 71, 72, …, 7k, k третьих сумматоров 81, 82, …, 8k, k четвертых схем сравнения 91, 92, …, 9k, k каскадов 101, 102, …, 10k (k - количество типов различных исходных заготовок), элемент И 11, группы из m*n первых регистров 1211, …, 12mn (m - общее число типов требуемых различных типов заготовок), m*n четвертых сумматоров 1311, …, 13mn, m*n седьмых регистров 1411, …, 14mn, m первых сумматоров 151, 152, …, 15m, m первых схем сравнения 161, 162, …, 16m, m вторых регистров 171, 172, …, 17m, m восьмых регистров 181, 182, …, 18m, n четвертых регистров 191, 192, …, 19n, n пятых сумматоров 201, 202, …, 20n, n девятых регистров 211, 212, …, 21n, второй сумматор 22, пятый регистр 23, вторую схему сравнения 24, входы пуска 25 и сброса 26 устройства, первый 27, вторые 281, 282, …, 28n, третьи 291, 292, …, 29n и четвертые 30 выходы устройства. 1 ил., 3 табл.

 

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

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

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

К причинам, препятствующим достижению указанного ниже технического результата, относится решение узкой задачи раскроя с минимальными остатками цельного материала длиной L на заготовки длиной Ii с потребным количеством каждого типа Ni: найти min δL=L-(N1I1+N2I2+…+N2I2+…+NkIn)≥0, где L, Ii, Ni - заданные целые величины, 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 счетчиков 41, 42, …, 4n (n - число возможных вариантов разрезания заготовок длиной L), группу из m*n первых регистров 1211, …, 12mn (m - общее число типов различных типов заготовок), группу из m вторых регистров 171, 172, …, 17m, группу из n третьих регистров 51, 52, …, 5n, группу из n четвертых регистров 191, 192, …, 19n, пятый регистр 23, группу из m первых сумматоров 151, 152, …, 15m, второй сумматор 22, группу из m первых схем сравнения 161, 162, …, 16m, вторую схему сравнения 24, элемент И 11, первый выход устройства 27, вторые выходы устройства 281, 282, …, 28n, причем выход каждого счетчика 4j (j=1,2,…,n) подсоединен к первому входу одноименного третьего регистра 5j, выходы третьих регистров 51, 52, …, 5n являются вторыми выходами устройства 281, 282, …, 28n, выход каждого первого сумматора 15i (i=1,2,…,m) подсоединен к первому входу одноименной первой схемы сравнения 16i, второй вход которой подсоединен к выходу одноименного второго регистра 17i, выход каждой первой схемы сравнения 16i подсоединен к соответствующему входу первой группы входов элемента И 11, выход второго сумматора 22 подсоединен к первым входам второй схемы сравнения 24, второй вход которой подсоединен к выходу пятого регистра 23.

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

min dL=YL-(k1L1+k2L2+…+kmLm)≥0,

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

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

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

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

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

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

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

группу из n счетчиков 41, 42, …, 4n (n - число возможных вариантов разрезания заготовок длиной L), группу из m*n первых регистров 1211, …, 12mn (m - общее число типов различных типов заготовок), группу из m вторых регистров 171, 172, …, 17m, группу из n третьих регистров 51, 52, …, 5n, группу из n четвертых регистров 191, 192, …, 19n, пятый регистр 23, группу из m первых сумматоров 151, 152, …, 15m, второй сумматор 22, группу из m первых схем сравнения 161, 162, …, 16m, вторую схему сравнения 24, элемент И 11, первый выход устройства 27, вторые выходы устройства 281, 282, …, 28n, причем выход каждого счетчика 4j (j=1,2,…,n) подсоединен к первому входу одноименного третьего регистра 5j, выходы третьих регистров 51, 52, …, 5n являются вторыми выходами устройства 281, 282, …, 28n, выход каждого первого сумматора 15i (i=1,2,…,m) подсоединен к первому входу одноименной первой схемы сравнения 16i, второй вход которой подсоединен к выходу одноименного второго регистра 17i, выход каждой первой схемы сравнения 16i подсоединен к соответствующему входу первой группы входов элемента И 11, выход второго сумматора 22 подсоединен к первым входам второй схемы сравнения 24, второй вход которой подсоединен к выходу пятого регистра 23, дополнительно введены генератор тактовых импульсов (ГТИ) 1, триггер разрешения 2, триггер готовности результата 3, группа из (n-k) третьих схем сравнения 61, 62, …, 6n-k, группа из k шестых регистров 71, 72, …, 7k, группа из k третьих сумматоров 81, 82, …, 8k группа из k четвертых схем сравнения 91, 92, …, 9k, k каскадов 101, 102, …, 10k, группа из m*n четвертых сумматоров 1311, …, 13mn, группа из m*n седьмых регистров 1411, …, 14mn, группа из m восьмых регистров 181, 182, …, 18m, группа из n пятых сумматоров 201, 202, …, 20n, группа из n девятых регистров 211, 212, …, 21n, вход пуска устройства 25, вход сброса устройства 26, третьи выходы устройства 291, 292, …, 29n, четвертые выходы устройства 30, причем вход сброса устройства 26 соединен с входами синхронной установки в нулевое состояние вторым входом триггера разрешения 2, вторым входом триггера готовности результата 3, вторыми входами группы из n счетчиков 41, 42, …, 4n, третьими входами группы из n третьих регистров 51, 52, …, 5n, вторыми входами группы из m*n седьмых регистров 1411, …, 14mn, вторыми входами группы из n девятых регистров 211, 212, …, 21n, вторым входом синхронной установки в единичное состояние пятого регистра 23, выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 41, 42, …, 4n, вторыми входами группы из n третьих регистров 51, 52, …, 5n, первыми входами группы из m*n седьмых регистров 1411, …, 14mn, первыми входами группы из n девятых регистров 211, 212, …, 21n, первыми входами группы из m восьмых регистров 181, 182, …, 18m, первым входом пятого регистра 23, группа из n счетчиков 41, 42, …, 4n разделена на k каскадов 10k по nt (t=1,2,…,k) счетчиков в каждом, при этом n1+n2+…+nk=n, в каждый каскад 10t также включены nt соответствующих третьих регистров 5t,1, …, 5t,nt, (nt-1) третьих схем сравнения 6t,1, …, 6t,nt, (nt-1), шестой регистр 7t, третий сумматор 8t, четвертая схема сравнения 9t, m*nt соответствующих первых регистров 12, m*nt соответствующих четвертых сумматоров 13, m*nt соответствующих седьмых регистров 14, nt соответствующих четвертых регистров 19t, m*nt соответствующих пятых сумматоров 20, nt соответствующих девятых регистров 21, причем в каждом t-м каскаде 10t выходы каждого счетчика 4t,2, …, 4t,nt подсоединены ко второй группе входов соответствующей третьей схемы сравнения 6t,1, …, 6t,nt-1, первая группа входов которых подсоединена к выходам соответствующего шестого регистра 7t, выходы каждого счетчика 4t,2, …, 4t,nt подсоединены к соответствующим одноименным входам третьего сумматора 8t, выход которого подсоединен ко вторым входам четвертой схемы сравнения 9t, первые входы которой подсоединены к выходам соответствующего шестого регистра 7t, второй выход четвертой схемы сравнения 9t подсоединен к соответствующему входу второй группы входов элемента И 11, вход пуска устройства 25 соединен с третьим входом разрешения работы триггера разрешения 2, выход которого в первом каскаде 101 соединен с входами разрешения работы третьим входом первого счетчика 411, третьим входом первой схемы сравнения 91 из группы k четвертых схем сравнения 91, 92, …, 9k, третьими входами первых регистров 1411, 1421, …, 14m1 из группы m*n седьмых регистров 1411, …, 14mn, третьим входом первого регистра 211 из группы n девятых регистров 211, 212, …, 21n, в каждом t-м каскаде 10t первый выход каждой из четвертых схем сравнения 9t соединен с входом синхронной установки в нулевое состояние четвертым входом соответствующих первых счетчиков 4t,1, четвертыми входами первых регистров 1411, 1421, …, 14m1, из группы седьмых регистров 14, четвертым входом первого регистра 211 из группы n девятых регистров 21, а также входами разрешения работы третьим входом первой схемы сравнения 6t,1 из группы третьих схем сравнения 6 и третьим входом второго счетчика 4t,2, в каждом t-м каскаде 10t выходы схем сравнения 6t,p (p=1,3,…,nt-2) соединены с входами разрешения третьим входом следующего счетчика 4t,р+2, третьим входом следующей схемы сравнения 6t,p+1, третьими входами соответствующих следующих седьмых регистров 14t,p+2, третьим входом соответствующего следующего девятого регистра 21t,р+2, а также соединены с входами синхронной установки в нулевое состояние четвертым входом соответствующего счетчика 4t,p+1, четвертыми входами соответствующих седьмых регистров 14t,p+1 и четвертым входом соответствующего девятого регистра 21t,p+1 каскада 10t, выход последней схемы сравнения 6t,nk-1 в каждом каскаде 10t(t=1,2,…,k-1) соединен с входом синхронной установки в нулевое состояние четвертым входом соответствующего счетчика 4t,nk, четвертыми входами соответствующих седьмых регистров 14t,nk и четвертым входом соответствующего девятого регистра 21t,nk каскада 10t, а также подсоединен в следующем (t+1)-м каскаде 10t+1 к входам разрешения работы третьим входом первого счетчика 4t+1,1, третьим входом схемы сравнения 9t+1, третьими входами соответствующих седьмых регистров 141,t+1, 142,t+1, …, 14m,t+1, третьим входом соответствующего девятого регистра 211,t+1, в последнем k-м каскаде 10k выход последней схемы сравнения 6k,nk-1 соединен с входом синхронной установки в нулевое состояние четвертым входом соответствующего счетчика 4k,nk, четвертыми входами соответствующих седьмых регистров 141,nk, 142,nk, …, 14m,nk и четвертым входом соответствующего девятого регистра 21n из каскада 10k, а также подсоединен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и третьему входу синхронной установки в единичное состояние триггера готовности результата 3, выход триггера готовности результата 3 является первым выходом устройства 27, выход каждого регистра 12ij из группы m*n первых регистров 1211, …, 12mn (i=1,2,…,m, j=1,2,…,n) подсоединен к первым входам соответствующего сумматора 13ij из группы m*n четвертых сумматоров 1311, …, 13mn, выходы которых подсоединены к информационным входам соответствующего регистра 1411 из группы m*n седьмых регистров 1411, …, 14mn, выходы которого соединены со вторыми входами соответствующего сумматора 13ij и одноименными входами соответствующего сумматора 15i из группы m первых сумматоров 151, 152, …, 15m, выходы которых подсоединены к третьим информационным входам одноименных регистров 18i из группы m восьмых регистров 181, 182, …, 18m, выходы которых являются третьими выходами устройства 291, 292, …, 29m, выходы регистров 19j из группы n четвертых регистров 191, 192, …, 19n соединены с первыми входами одноименных сумматоров 20j из группы n пятых сумматоров 201, 202, …, 20n, выходы которых подсоединены к информационным входам соответствующего регистра 21j из группы n девятых регистров 211, 212, …, 21n, выходы которых соединены со вторыми входами соответствующего сумматора 20j и одноименными входами второго сумматора 22, выходы которого подсоединены к информационным входам пятого регистра 23, выходы которого являются четвертыми выходами устройства 30, выход второй схемы сравнения 24 подключен к третьему входу элемента И 11, выход которого соединен с входами разрешения записи четвертыми входами группы из n третьих регистров 51, 52, …, 5n, третьим входом пятого регистра 23 и вторыми входами регистров из группы m седьмых регистров 181, 182, …, 18m.

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

На фиг.1 приняты следующие обозначения: генератор тактовых импульсов (ГТИ) 1, триггер разрешения 2, триггер готовности результата 3, группа из n счетчиков 41, 42, …, 4n (n - число возможных вариантов разрезания заготовок длиной L), группа из n третьих регистров 51, 52, …, 5n, группа из n третьих схем сравнения 61, 62, …, 6mn, группа из k шестых регистров 71, 72, …, 7k, группа из k третьих сумматоров 81, 82, …, 8k группа из k четвертых схем сравнения 91, 92, …, 9k, k каскадов 101, 102, …, 10k, элемент И 11, группа из m*n первых регистров 1211, …, 12mn (m - общее число типов различных типов заготовок), группа из m*n четвертых сумматоров 1311, …, 13mn, группа из m*n седьмых регистров 1411, …, 14mn, группа из m первых сумматоров 151, 152, …, 15m, группа из m первых схем сравнения 161, 162, …, 16m, группа из m вторых регистров 171, 172, …, 17m, группа из m восьмых регистров 181, 182, …, 18m, группа из n четвертых регистров 191, 192, …, 19n, группа из n пятых сумматоров 201, 202, …, 20n, группа из n девятых регистров 211, 212, …, 21n, второй сумматор 22, пятый регистр 23, вторая схема сравнения 24, вход пуска устройства 25, вход сброса устройства 26, первый выход устройства 27, вторые выходы устройства 281, 282, …, 28n, третьи выходы устройства 291, 292, …, 29n, четвертые выходы устройства 30.

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

Внешний вход сброса устройства 26 соединен с входами синхронной установки в нулевое состояние вторым входом триггера разрешения 2, вторым входом триггера готовности результата 3, вторыми входами группы из n счетчиков 41, 42, …, 4n, третьими входами группы из n третьих регистров 51, 52, …, 5n, вторыми входами группы из m*n седьмых регистров 1411, …, 14mn, вторыми входами группы из n девятых регистров 211, 212, …, 21n, вторым входом синхронной установки в единичное состояние пятого регистра 23.

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

Вход пуска устройства 25 соединен с третьим входом разрешения работы триггера разрешения 2, выход которого в первом каскаде 10t соединен с входами разрешения работы третьим входом первого счетчика 4t,1, третьим входом первой схемы сравнения 91 из группы k четвертых схем сравнения 91, 92, …, 9k, третьими входами первых регистров 1411, 1421, …, 14m1 из группы m*n седьмых регистров 1411, …, 14mn, третьим входом первого регистра 211 из группы n девятых регистров 211, 212, …, 21n.

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

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

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

В последнем k-м каскаде 10k выход последней схемы сравнения 6k,nk-1 соединен с входом синхронной установки в нулевое состояние четвертым входом соответствующего счетчика 4k,nk, четвертыми входами соответствующих седьмых регистров 141,nk, 142,nk, …, 14m,nk и четвертым входом соответствующего девятого регистра 21n из каскада 10k, a также подсоединен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и третьему входу синхронной установки в единичное состояние триггера готовности результата 3, выход триггера готовности результата 3 является первым выходом устройства 27. Выходы третьих регистров 51, 52, …, 5n являются вторыми выходами устройства 281, 282, …, 28n.

Выход каждого регистра 12ij из группы m*n первых регистров 1211, …, 12mn (i=1,2,…,m, j=1,2,…,n) подсоединен к первым входам соответствующего сумматора 13ij из группы m*n четвертых сумматоров 1311, …, 13mn, выходы которых подсоединены к информационным входам соответствующего регистра 1411 из группы m*n седьмых регистров 1411, …, 14mn, выходы которого соединены со вторыми входами соответствующего сумматора 13ij и одноименными входами соответствующего сумматора 15, из группы m первых сумматоров 151, 152, …, 15m, выходы которых подсоединены к третьим информационным входам одноименных регистров 18, из группы m восьмых регистров 181, 182, …, 18m, выходы которых являются третьими выходами устройства 291, 292, …, 29m.

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

Выходы регистров 19j из группы n четвертых регистров 191, 192, …, 19n соединены с первыми входами одноименных сумматоров 20j из группы n пятых сумматоров 201, 202, …, 20n, выходы которых подсоединены к информационным входам соответствующего регистра 21j из группы n девятых регистров 211, 212, …, 21n, выходы которых соединены со вторыми входами соответствующего сумматора 20j и одноименными входами второго сумматора 22.

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

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

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

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

min S=(y1L1+y2L2+…+ykLk)-(v1Z1+v2Z2+…+vmZm)≥0

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

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

yt - искомое число исходных заготовок с длиной Lt (t=1,…,k), при этом (y1+y2+…+yk)=Y,

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

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

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

В устройстве введено k каскадов 10t (t=1,2,…,k), в соответствии с количеством k-типов различных исходных заготовок длины Lt. В каждый каскад 10t введено nt счетчиков (nt - число возможных вариантов разрезания заготовок длиной Lt на требуемые заготовки с длиной Zi (i=1,…,m)). При этом общее число n возможных вариантов разрезания исходных заготовок составляет n=n1+n2+…+nk. В каждом каскаде 10t задается модуль счета каждого счетчика 4t, который соответствует возможному количеству исходных заготовок длиной Lt (t=1,…,k). В каждом каскаде 10t также выполняется проверка, чтобы суммарное значение задаваемых кодов исходных заготовок на всех счетчиках 4 каскада 10t не превышало значение модуля в каскаде 10t, а при превышении модуля младший счетчик 41,t каскада 10t синхронно устанавливается в нулевое состояние. Введенная проверка суммарного модуля каждого каскада 10t позволяет контролировать количество исходных заготовок и уменьшает задаваемый перебор входных комбинаций.

В исходном состоянии в каждом регистре в группе m*n первых регистров 1211, …, 12mn устанавливается код количества i-x заготовок (i=1,…,m) в j-м варианте разрезания (j=1,…,n, где n - число всех возможных вариантов разрезания заготовок), в группе из m вторых регистров 171, 172, …, 17m устанавливается код vi числа требуемых заготовок с длиной Zi, в группе из n четвертых регистров 191, 192, …, 19n устанавливается код sj длины остатка в j-м варианте разрезания, в группе из k шестых регистров 71, 72, …, 7k устанавливается код Mt возможного количества исходных заготовок длиной Lt (t=1,…,k), при этом число (Mt+1) является модулем счетчика в каждом каскаде 10t (t=1,…,k).

Группа счетчиков 41, 42, …, 4n предназначена для задания текущих значений количества исходных заготовок из числа возможных Mt в соответствующем каскаде 10t. В процессе решения задачи в группе из m*n седьмых регистров 1411, …, 14mn накапливаются текущие количества i-x заготовок в j-м варианте разрезания, а в группе из n девятых регистров 211, 212, …, 21n накапливаются текущие значения остатков Sj заготовок в j-м варианте разрезания. В группе из n третьих регистров 51, 52, …, 5n фиксируется код yt требуемого числа исходных заготовок с длиной Lt, в группе из m восьмых регистров 181 182, …, 18m фиксируется полученный код количества требуемых заготовок с длиной Zi (i=1,…,m), а в пятом регистре 23 фиксируется общее суммарное значение остатка S.

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

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

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

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

Аналогично в n группах, состоящих из элементов четвертых регистров 191, 192, …, 19n, пятых сумматоров 201, 202, …, 20n, девятых регистров 211, 212, …, 21n и соответствующих связях, реализуется последовательное вычисление суммарных остатков Sj в j-м варианте разрезания и фиксации этих значений на девятых регистрах 211, 212, …, 21n.

В m группах, состоящих из элементов первых сумматоров 151, 152, …, 15m, первых схем сравнения 161, 162, …, 16m, вторых регистров 171, 172, …, 17m, восьмых регистров 181, 182, …, 18m и соответствующих связях, реализуется вычисление суммарного текущего количества i-x заготовок всех вариантов разрезания на первых сумматорах 151, 152, …, 15m, сравнение значения суммы с требуемым количеством vi с длиной Zi (i=1,…,m), установленном на вторых регистрах 17i, и фиксации значения суммы i-x заготовок на восьмых регистрах 181, 182, …, 18m при соответствии критериям решения задачи, т.е. при min S. На выходах первых схем сравнения 16i формируется единичный сигнал, если суммарное количество i-x заготовок всех вариантов разрезания превышает или равно требуемому количеству заготовок vi с длиной Zi.

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

Сигналы с выходов первых схем сравнения 161, 162, …, 16m, второй схемы сравнения 24 и вторых выходов четвертых схем сравнения 91, 92, …, 9k поступают на соответствующие входы элемента И 11, на выходе которого единичный сигнал EN=1 формируется в случае всех единичных входных сигналов. В этом случае в устройстве получены минимальные текущие остатки Sтек, суммарное количество i-x заготовок всех вариантов разрезания превышает или равно требуемому количеству заготовок vi с длиной Zi и требуемые количества yt исходных заготовок не превышают заданных возможных количеств исходных заготовок различной длины Lt.

Единичный сигнал EN=1 на выходе элемента И 11 разрешает запись в группу третьих регистров 51, 52, …, 5n с выходов счетчиков 41, 42, …, 4n текущих значений требуемые количества yj исходных заготовок в j-м варианте разрезания, запись текущего минимального остатка Sтек в пятый регистр 23 и запись в регистры 181, 182, …, 18m полученного суммарного количества i-x заготовок всех вариантов разрезания.

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

При подаче сигнала на вход сброса устройства 26 синхронно по фронту импульса с ГТИ 1 в нулевое состояние устанавливаются триггер разрешения 2, триггер готовности результата 3, все счетчики 41, 42, …, 4n, третьи регистры 51, 52, …, 5m, пятый регистр 23, седьмые регистры 1411, …, 14mn, девятые регистры 211, 212, …, 21n.

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

На следующих тактах ГТИ 1 в первом счетчике 41 задается текущее значение количества исходных заготовок из числа возможных M1, в первые седьмые регистры 1411, …, 14m1 из группы седьмых регистров 14 записываются текущие значения количества i-x заготовок при первом варианте разрезания заготовок j=1, а в первый девятый регистр 211 записывается текущее значение остатков S в первом варианте разрезания, которые вычисляются соответственно на четвертых сумматорах 1311, …, 13m1 и пятом сумматоре 201.

В таблице 1 по тактам ГТИ 1 для каскада 101, состоящего из трех счетчиков (при n1=3 - три варианта разрезания заготовок) с модулем счета Mt+1=4 (код Mt=3, соответствующий возможному количеству исходных заготовок длиной L1, установлен на регистре 71), приведены значения кодов 0, 1, 2 или 3 (в двоичном и десятичном виде) на счетчиках 41, 42, 43 (счетчик 41 младший), суммарное значение кодов счетчиков на сумматоре 81 и единичные сигналы на выходах схем сравнения 611 612 и 91.

В первом каскаде 101 при достижении первым счетчиком 41,1 значения модуля M1=3, записанного в регистре 71, на выходе третьего сумматора 81 тоже будет установлен код, равный M1=3, так как на остальных счетчиках каскада установлены нулевые значения. Код с выхода сумматора 81 поступает на первый вход схемы сравнения 91, на второй вход которой поступает код модуля M1=3 с выхода регистра 71. Единичный сигнал на первом выходе схемы сравнения 91 (в таблице 1 такт 3) формируется только в том случае, если суммарный код текущего количества заготовок на первом сумматоре 81 больше или равен коду допустимого количества заготовок, установленного на регистре 71. По данному единичному сигналу, на следующем такте ГТИ устанавливаются в нулевое состояние счетчик 41,1, регистры 1411, …, 14m1 и регистр 211, разрешается увеличение счетчика 41,2 и сравнение на схеме 61,1, а также проводится запись текущих значений количества i-x заготовок в регистры 1411, …, 14m2, а в регистр 212 записывается текущее значение остатков во втором варианте разрезания при j=2.

Далее на следующих тактах ГТИ 1 увеличивается значение счетчика 41,1 и формирование значений текущих заготовок и остатков. Одновременно значения кодов счетчиков 41,1 и 41,2 суммируются на третьем сумматоре 81. При значении суммы, равной коду на регистре 71 аналогично формируется единичный сигнал на первом выходе схемы сравнения 91 (в таблице 1 такты 6, 8, 9). Кроме того, на такте 9 единичный сигнал формируется и на выходе схемы сравнения 61,1, по которому на следующем такте ГТИ устанавливаются в нулевое состояние счетчик 41,2, регистры 141,2, …, 14m2 и регистр 212, разрешается увеличение счетчика 41,3 и сравнение на схеме 61,2, а также проводится запись текущих значений количества i-x заготовок в регистры 1413, …, 14m3, и остатков в регистр 213 для третьего варианта разрезания заготовок при j=3.

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

При достижении в первом каскаде 101 счетчиком 41,nt (41,3 в таблице 1) значения модуля Mt на выходе третьей схемы сравнения 61,n1-1 (61,2 в таблице 1) формируется единичный сигнал, по которому разрешается работа второго каскада 102 - увеличение счетчика 42,1 и работа схемы сравнения 92, а также проводится запись в первые элементы соответствующих седьмых регистров 14 текущих значений количества i-x заготовок при первом варианте разрезания заготовок j2=1 во втором каскаде 102, а в соответствующий девятый регистр 21 записывается текущее значение остатков, которые вычисляются соответственно на четвертых сумматорах 13 и пятом сумматоре 20. Далее по тактам ГТИ 1 в каскаде 102 выполняются действия аналогично как для первого каскада 101.

При достижении во втором каскаде 102 счетчиком 42,n2 значения модуля M2 на выходе третьей схемы сравнения 62,n2-1 формируется единичный сигнал, по которому разрешается работа третьего каскада 103. Затем аналогично работают следующие каскады 103, …, 10k.

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

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

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

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

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

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

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

Кроме того, в предлагаемом устройстве в отличие от прототипа имеется возможность задания по каскадам 101, 102, …, 10k возможного допустимого количества исходных заготовок на шестых регистрах 71, 72, …, 7k.

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

Ntустр=(Mt+1)nt-1+ΔNnt,Mt,

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

,

В таблице 2 приведено количество дополнительных входных комбинаций ΔNnt,Mt в зависимости от модуля счета Mt+1 в t-м каскаде, где Mt возможное количество исходных заготовок в t-м каскаде, и количества вариантов nt разрезания исходных заготовок в t-м каскаде. Для nt=1 количество дополнительных входных комбинаций ΔNnt,Mt соответствует натуральном ряду чисел - значению Mt. Для nt=2 количество дополнительных входных комбинаций ΔNnt,Mt соответствует арифметической прогрессии предыдущих значений натурального ряда Mt. Для следующих строк количество комбинаций ΔNnt,Mt равно сумме значений в предыдущей строке. Например, для Mt=3 и nt=3 из таблицы 2 получим ΔN3,3=10 и, следовательно, Ntустр=16+10=26, что соответствует количеству входных комбинаций, приведенному в таблице 1. В таблице 3 приведено соотношение для t-го каскада между полным перебором входных комбинаций Nпер и количеством входных комбинаций Nустр, задаваемом в предлагаемом устройстве. Из таблицы 3 следует, что количество входных комбинаций в t-м каскаде при увеличении количества вариантов разрезания заготовок nt сокращается в Mt раз. Соответственно для k каскадов сокращение входных комбинаций будет пропорционально произведению модулей каскадов M1*M2*…*Mk.

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

Устройство для решения задач целочисленного линейного программирования, содержащее группу из n счетчиков 41, 42, …, 4n (n - число возможных вариантов разрезания заготовок длиной L), группу из m*n первых регистров 1211, …, 12mn (m - общее число типов различных типов заготовок), группу из m вторых регистров 171, 172, …, 17m, группу из n третьих регистров 51, 52, …, 5n, группу из n четвертых регистров 191, 192, …, 19n, пятый регистр 23, группу из m первых сумматоров 151, 152, …, 15m, второй сумматор 22, группу из m первых схем сравнения 161, 162, …, 16m, вторую схему сравнения 24, элемент И 11, первый выход устройства 27, вторые выходы устройства 281, 282, …, 28n, причем выход каждого счетчика 4j (j=1,2,…,n) подсоединен к первому входу одноименного третьего регистра 5j, выходы третьих регистров 51, 52, …, 5n являются вторыми выходами устройства 281, 282, …, 28n, выход каждого первого сумматора 15i (i=1,2,…,m) подсоединен к первому входу одноименной первой схемы сравнения 16i, второй вход которой подсоединен к выходу одноименного второго регистра 17i, выход каждой первой схемы сравнения 16i подсоединен к соответствующему входу первой группы входов элемента И 11, выход второго сумматора 22 подсоединен к первым входам второй схемы сравнения 24, второй вход которой подсоединен к выходу пятого регистра 23, отличающееся тем, что в него дополнительно введены генератор тактовых импульсов (ГТИ) 1, триггер разрешения 2, триггер готовности результата 3, группа из (n-k) третьих схем сравнения 61, 62, …, 6n-k, группа из k шестых регистров 71, 72, …, 7k, группа из k третьих сумматоров 81, 82, …, 8k, группа из k четвертых схем сравнения 91, 92, …, 9k, k каскадов 101, 102, …, 10k, группа из m*n четвертых сумматоров 1311, …, 13mn, группа из m*n седьмых регистров 1411, …, 14mn, группа из m восьмых регистров 181, 182, …, 18m, группа из n пятых сумматоров 201, 202, …, 20n, группа из n девятых регистров 211, 212, …, 21n, вход пуска устройства 25, вход сброса устройства 26, третьи выходы устройства 291, 292, …, 29n, четвертые выходы устройства 30, причем вход сброса устройства 26 соединен с входами синхронной установки в нулевое состояние вторым входом триггера разрешения 2, вторым входом триггера готовности результата 3, вторыми входами группы из n счетчиков 41, 42, …, 4n, третьими входами группы из n третьих регистров 51, 52, …, 5n, вторыми входами группы из m*n седьмых регистров 1411, …, 14mn, вторыми входами группы из n девятых регистров 211, 212, …, 21n, вторым входом синхронной установки в единичное состояние пятого регистра 23, выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 41, 42, …, 4n, вторыми входами группы из n третьих регистров 51, 52, …, 5n, первыми входами группы из m*n седьмых регистров 1411, …, 14mn, первыми входами группы из n девятых регистров 211, 212, …, 21n, первыми входами группы из m восьмых регистров 181, 182, …, 18m, первым входом пятого регистра 23, группа из n счетчиков 41, 42, …, 4m разделена на k каскадов 10k по nt (t=1,2,…,k) счетчиков в каждом, при этом n1+n2+…+nk=n, в каждый каскад 10t также включены nt соответствующих третьих регистров 5t,1, …, 5t,nt, (nt-1) третьих схем сравнения 6t,1, …, 6t,nt-1, шестой регистр 7t, третий сумматор 8t, четвертая схема сравнения 9t, m*nt соответствующих первых регистров 12, m*nt соответствующих четвертых сумматоров 13, m*nt соответствующих седьмых регистров 14, nt соответствующих четвертых регистров 19, nt соответствующих пятых сумматоров 20, nt соответствующих девятых регистров 21, причем в каждом t-м каскаде 10t выходы каждого счетчика 4t,2, …, 4t,nt подсоединены ко второй группе входов соответствующей третьей схемы сравнения 6t,1, …, 6t,nt-1, первая группа входов которых подсоединена к выходам соответствующего шестого регистра 7t, выходы каждого счетчика 4t,1, …, 4t,nt подсоединены к соответствующим одноименным входам третьего сумматора 8t, выход которого подсоединен ко вторым входам четвертой схемы сравнения 9t, первые входы которой подсоединены к выходам соответствующего шестого регистра 7t, второй выход четвертой схемы сравнения 9t подсоединен к соответствующему входу второй группы входов элемента И 11, вход пуска устройства 25 соединен с третьим входом разрешения работы триггера разрешения 2, выход которого в первом каскаде 101 соединен с входами разрешения работы третьим входом первого счетчика 411, третьим входом первой схемы сравнения 91 из группы k четвертых схем сравнения 91, 92, …, 9k, третьими входами первых регистров 1411, 1421, …, 14m1 из группы m*n седьмых регистров 1411, …, 14mn, третьим входом первого регистра 211 из группы n девятых регистров 211, 212, …, 21n, в каждом t-м каскаде 10t первый выход каждой из четвертых схем сравнения 9t соединен с входом синхронной установки в нулевое состояние, четвертым входом соответствующих первых счетчиков 4t,1, четвертыми входами первых регистров 1411, 1421, …, 14m1, из группы седьмых регистров 14, четвертым входом первого регистра 211 из группы n девятых регистров 21, а также входами разрешения работы третьим входом первой схемы сравнения 6t,1 из группы третьих схем сравнения 6 и третьим входом второго счетчика 4t,2, в каждом t-м каскаде 10t выходы схем сравнения 6t,p (p=1,3,…,nt-2) соединены с входами разрешения третьим входом следующего счетчика 4t,р+2, третьим входом следующей схемы сравнения 6t,p+1, третьими входами соответствующих следующих седьмых регистров 14t,р+2, третьим входом соответствующего следующего девятого регистра 21t,р+2, а также соединены с входами синхронной установки в нулевое состояние, четвертым входом соответствующего счетчика 4t,p+1, четвертыми входами соответствующих седьмых регистров 14t,p+1 и четвертым входом соответствующего девятого регистра 21t,p+1 каскада 10t, выход последней схемы сравнения 6t,nk-1 в каждом каскаде 10t (t=1,2,…,k-1) соединен с входом синхронной установки в нулевое состояние, четвертым входом соответствующего счетчика 4t,nk, четвертыми входами соответствующих седьмых регистров 14t,nk и четвертым входом соответствующего девятого регистра 21t,nk каскада 10t, а также подсоединен в следующем (t+1)-M каскаде 10t+1 к входам разрешения работы третьим входом первого счетчика 4t+1,1, третьим входом схемы сравнения 9t+1, третьими входами соответствующих седьмых регистров 141,t+1, 142,t+1, …, 14m,t+1, третьим входом соответствующего девятого регистра 211,t+1, в последнем k-м каскаде 10k выход последней схемы сравнения 6k,nk-1 соединен с входом синхронной установки в нулевое состояние, четвертым входом соответствующего счетчика 4k,nk, четвертыми входами соответствующих седьмых регистров 141,nk, 142,nk, …, 14m,nk и четвертым входом соответствующего девятого регистра 21n из каскада 10k, а также подсоединен к четвертому входу синхронной установки в нулевое состояние, триггера разрешения 2 и третьему входу синхронной установки в единичное состояние триггера готовности результата 3, выход триггера готовности результата 3 является первым выходом устройства 27, выход каждого регистра 12ij из группы m*n первых регистров 1211, …, 12mn (i=1,2,…,m, j=1,2,…,n) подсоединен к первым входам соответствующего сумматора 13ij из группы m*n четвертых сумматоров 1311, …, 13mn, выходы которых подсоединены к информационным входам соответствующего регистра 1411 из группы m*n седьмых регистров 1411, …, 14mn, выходы которого соединены со вторыми входами соответствующего сумматора 13ij и одноименными входами соответствующего сумматора 15, из группы m первых сумматоров 151, 152, …, 15m, выходы которых подсоединены к третьим информационным входам одноименных регистров 18i из группы m восьмых регистров 181, 182, …, 18m, выходы которых являются третьими выходами устройства 291, 292, …, 29m, выходы регистров 19j из группы n четвертых регистров 191, 192, …, 19n соединены с первыми входами одноименных сумматоров 20j из группы n пятых сумматоров 201, 202, …, 20n, выходы которых подсоединены к информационным входам соответствующего регистра 21j из группы n девятых регистров 211, 212, …, 21n, выходы которых соединены со вторыми входами соответствующего сумматора 20j и одноименными входами второго сумматора 22, выходы которого подсоединены к информационным входам пятого регистра 23, выходы которого являются четвертыми выходами устройства 30, выход второй схемы сравнения 24 подключен к третьему входу элемента И 11, выход которого соединен с входами разрешения записи четвертыми входами группы из n третьих регистров 51, 52, …, 5n, третьим входом пятого регистра 23 и вторыми входами регистров из группы m седьмых регистров 181, 182, …, 18m.



 

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано для оценки предпочтительного уровня унификации технических систем (ТС) с целью минимизации затрат на проектирование и изготовление ТС при достаточном уровне их эффективности. Технический результат заключается в повышении точности оценки предпочтительного уровня унификации ТС за счет учета разницы времени использования различных ее элементов. Эту оценку можно осуществить с помощью обобщенного критерия, учитывающего эффективность ТС и объем финансирования их проектирования и изготовления. Устройство содержит шесть групп входных регистров, четыре группы блоков умножения, входной регистр, блок деления, группу сумматоров, группу блоков вычитания, группу элементов задержки, группу блоков деления, группу входных регистров, группу блоков индикации, генератор тактовых импульсов, два распределителя импульсов, переключатель и накопительный сумматор. 3 ил., 2 табл.

Изобретение относится к медицине, а именно к способам и системам субтракционной ангиографии. Способ заключается в генерации первой последовательности изображений маски субъекта, подлежащего обследованию, генерации первого контрастного изображения в первой фазе контрастности, в соответствии с чем в первом контрастном изображении часть субъекта имеет контраст, отличный от контраста первой последовательности изображений, вычитании изображения маски из первого контрастного изображения для генерации первой последовательности изображений DSA, вычитании изображения DSA первой последовательности изображений DSA из первого контрастного изображения в пределах первой фазы для генерации последовательности уточненных изображений маски. Также генерируют второе контрастное изображение во второй фазе контрастности, причем упомянутая вторая фаза отделена от первой фазы предварительно заданным временным пределом разделения фаз, вычитают изображения последовательности уточненных изображений маски из второго контрастного изображения для генерации второй последовательности изображений DSA и отображают изображения DSA второй последовательности изображений на дисплее. Первая фаза является артериальной фазой фазы контрастности, вторая фаза является перфузионной фазой фазы контрастности, и временной предел разделения фаз является временным пределом коронарных артерий. Система визуализации содержит устройство генерации изображений, блок обработки данных, дисплей и машиночитаемый носитель, содержащий программный элемент, выполненный с возможностью при исполнении блоком обработки данных выполнять способ субтракционной ангиографии. Использование изобретения обеспечивает подавление эффекта остаточных движений в течение перфузионной фазы, уменьшение артефактов движения. 3 н. и 7 з.п. ф-лы, 5 ил.
Изобретение относится к области организации обмена информацией между компьютерными информационными системами. Техническим результатом является упрощение способа передачи данных между информационными системами, повышение точности и надежности передачи данных. Раскрыт способ обмена информацией между информационными системами, заключающийся в том, что в каждой информационной системе - клиент (ИС-клиент) обеспечивают хранение информации об индивидуальных сущностях, которая сформирована в соответствии с установленными для конкретной ИС-клиент структурой данных и с типами метаданных о категориях индивидуальных сущностей, категориях дополнительных сведений, относящихся к индивидуальным сущностям, и категориях отношений между индивидуальными сущностями и дополнительными сведениями, хранящуюся в ИС-клиент информацию об индивидуальной сущности перед ее передачей преобразуют в данной ИС-клиент в пакеты данных об индивидуальной сущности, при этом каждый пакет данных формируют из трех записей, первая запись представляет собой идентифицирующую характеристику индивидуальной сущности, третья запись представляет собой дополнительную информацию, относящуюся к индивидуальной сущности, вторая запись представляет собой информацию о категории отношения между первой и третьей записью. 2 з.п. ф-лы.

Изобретение относится к вычислительной технике и может быть использовано для количественной оценки качественного показателя, состоящего из отдельных составных частей (факторов). Техническим результатом является повышение надежности устройства за счет существенного сокращения аппаратных затрат. Устройство для количественной оценки качественного показателя содержит матрицы из m∗n первых 1ij и вторых регистров 6ij (i=1, …, m, j=1, …, n), n третьих регистров 2j (j=1, …, n), n первых блоков умножения 5j, n вторых блоков умножения 9j (j=1, …, n), первый 10, второй 11 и третий 12 сумматоры, четвертый 15 и пятый 16 регистр, генератор тактовых импульсов (ГТИ) 17, третий блок умножения 14, блок деления 13, первый 22, второй 23, третий 24 и четвертый 25 элементы задержки, первую и вторую матрицы из m*n первых 3ij и вторых 7ij элементов И (i=1, …, m, j=1, …, n), n первых 4j и n вторых 8j элементов ИЛИ (j=1, …, n), третий элемент И 18, счетчик 19, схему сравнения 20, дешифратор 21. 1 ил.

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

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

Изобретение относится к области создания и редактирования визуальных представлений. Техническим результатом является повышение эффективности визуализации графики. Раскрыты способ и система для представления графики, основываясь на пользовательских настройках в прикладной компьютерной программе для работы с графикой. Настройки касаются различных свойств одного или более графических элементов в графике. Такие свойства включают в себя позиционирование, размер, форматирование и другие визуальные атрибуты, связанные с графическими элементами. Эти свойства могут быть определены или как семантические свойства, или как свойства представления. Семантические свойства постоянны для всех графических определений. Свойства представления являются специфичными для графического определения, которому принадлежит каждая специфическая графика. Таким образом, настройка к семантическому свойству отображаемой графики сохраняется в памяти для приложения не только для отображаемой в настоящее время графике, но также и ко всем другим графическим определениям, которые могут быть отображены в будущем. Напротив, настройка к свойству представления сохраняется только для отображаемой в настоящее время графики, и таким образом не сохраняется для всех других графических определений. 3 н. и 12 з.п. ф-лы, 8 ил.

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

Изобретение относится к вычислительным распределенным системам. Технический результат заключается в повышении точности и достоверности определения уязвимых элементов в составе распределенных систем. Система содержит, по меньшей мере, два автоматизированных рабочих места (АРМ) пользователей, коммутатор локальной вычислительной сети (ЛВС), сервер обмена информацией, блок сопряжения, блок интерфейсов программы, блок формирования системы показателей и критериев, блок формирования задачи и задания условий моделирования, диспетчер математических моделей (ММ) и информационно-расчетных задач (ИРЗ), диспетчер работы с базой данных (БД) и базой знаний (БЗ), блок базы данных (БД) по состоянию системы и объектам оборудования, блок базы знаний (БЗ), блок решения информационно-расчетных задач (ИРЗ), блок формирования прогнозных оценок состояния системы, блок ранжирования и фильтрации критически важных объектов (КВО), блок учета КВО, данные о которых поступили от других систем, блок выбора группы КВО и формирования комплексной оценки, блок агрегирования и представления результатов расчетов и моделирования, блок анализа результатов расчетов. 1 ил.

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