Устройство для решения задач оптимизации Советский патент 1992 года по МПК G06F15/20 

VI СП

Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства за счет решения задач покрытия. Устройство содержит блок 1 перечисления множеств элементов покрытия, регистр 2, блок 3 синхронизации, блок 4 проверки условия покрытия, блок 5 памяти, накапливающий блок 6 выбора минимальной суммы, блок 7 задания матрицы покрытий, вход 8 пуска устройства, выход 9 оптимального состава покрытия, выход 10 стоимости покрытия и с первого по третий выходы 11-13 блока 3 синхронизации. Перед началом работы блок 6 устанавливает в исходное состояние блок 1, в блок 7 заносят матрицу покрытий, в блок 5 - данные о расходах на каждого исполнителя. На вход 8 пуска устройства подают импульс уровня логической единицы. При этом блок 3 формирует на своих выходах 11-13 последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой на выходе 9 устройства формируется оптимальный состав исполнителей (элементов покрытия) и на выходе 10 - стоимость покрытия. 3 ил. СО с

Фиг.

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

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

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

Устройство содержит блок 1 перечисления множеств элементов покрытия, регистр 2, блок 3 синхронизации, блок 4 проверки условия покрытия, блок 5 памяти, накапливающий блок 6 выбора минимальной суммы, блок 7 задания матрицы покрытий, вход 8 пуска устройства, выход 9 оптимального состава покрытия, выход 10 стоимости покрытия и с первого по третий выходы 11-13 блока 3 синхронизации.

Блок 4 проверки условия покрытия содержит матрицу из Э х Т элементов И 14, где Э - количество в полном множестве покрываемых элементов. Т- количество покрываемых элементов, группу из Т элементов ИЛИ 15 и элементы И 16 и 17, причем вход 18 признака наличия (К, М)-го элемента (К 1,

..., Т; М 1 Э) блока 4 подключен к

первому входу К-го элемента И 14, М-й строки матрицы, выход которого подключен к М-му входу К-го элемента ИЛИ 15 группы, выход которого подключён к К-му входу элемента И 16, выход которого подключен к первому входу элемента И 17, выход которого является выходом признака обеспечения покрытия блока 4, М-й разряд 19 входа задания множества элементов покрытия/которого подключен к вторым входам всех элементов И 14 М-й строки матрицы, вход 20 опроса блока 4 подключен к второму входу элемента И 17.

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

Пусть имеется Т операций, для выполнения которых можно использовать Э исполнителей. Задана матрица покрытий,(К, М)-й элемент которой равен единице, если М-й исполнитель может выполнить К-ю операцию и расходы,связанные с использованием М-го исполнителя. Необходимо выбрать такое множество исполнителей (множество элементов покрытия или покрывающее множество), которое минимизировало бы общие расходы при условии выполнения всех операций.

Перед началом работы обнуляют накапливающий блок 6 выбора минимальной суммы, устанавливают в исходное состояние блок 1 перечисления множеств элементов покрытия, в блок 7 заносят матрицу покрытий, а в блок 5 памяти - данные о расходах

на каждого исполнителя.

На вход 8 пуска устройства подают импульс уровня логической единицы. При этом блок 3 синхронизации формирует на своих выходах 11-13 последовательность сигна0 лов уровня логической единицы, предусмотренную временной диаграммой его работы. Блок 3 формирует импульс уровня логической единицы на своем выходе 11. Блок 1 формирует на своих .выходах первое множе5 ство исполнителей. Блок 4 проверяет.может ли текущее множество исполнителей выполнить все операции. Через время, достаточное для окончания указанных операций, блок 3 формирует потенциал уровня логиче0 ской единицы на своем выходе 12. При этом блок 4 вырабатывает значение признака обеспечения покрытия для текущего множества исполнителей. В том случае, если текущее множество исполнителей не может

5 выполнить весь набор операций, значение признака равно нулю. Если текущее множество исполнителей может выполнить весь набор операций, значение признака становится равным единице. При этом блок 5 па0 мяти формирует на своих выходах информацию, загруженную по каждому адресу из числа выбранных потенциалами уровня логической единицы (стоимости использования каждого исполнителя текуще5 го множества). Через время, достаточное для окончания указанных операций, блок 3 формирует импульс уровня логической единицы на своем выходе 13. При этом блок 6 складывает все коды, присутствующие на

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

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

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

5 потенциал с выхода 12 и формирует импульс уровня логической единицы на своем выходе 11. Далее работа устройства повторяется до полного перебора (перечисления) всех множеств исполнителей. При этом на выхо- де 9 устройства сформирован оптимальный

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

текущему множеству которого (М 1Э,

где Э - количество элементов в полном множестве покрывающих элементов) подключен к входу задания множества элементов

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

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

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

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