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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si)s G 06 F 15/20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 4

)Щ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4473552/24 (22) 20.06,88 (46) 07.02.92. Бюл. N.. 5 (72) О,Г.Алексеев, В.А.Буслаев, С.А,Васильковский и Н.И.Ячкула (53) 681,333(088.8) (56) Авторское свидетельство СССР

¹ 928372, кл. G 06 G 7/48, 1980.

Авторское свидетельство СССР

N 1619292, кл. G 06 F 15/20, 01.06.88. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ОПТИМИЗАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования. Целью изобретения является расширение функциональных возможностей устройства за счет решения задач покрытия. Устройство содержит блок 1 перечисления множеств элементов покрытия, регистр

„, Я,) „, 1711175А1

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

1711175

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

На фиг, 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 подключен к первому входу К-ro элемента И 14, М-й строки матрицы, выход которого подключен к

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

/ задания множества элементов покрытия;которого подключен к вторым входам всех элементов И 14 М-й строки матрицы, вход

20 опроса блока 4 подключен к второму входу элемента И 17.

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

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

Перед началом работы обнуляют накапливающий блок 6 выбора минимальной сум5

55 мы, устанавливают в исходное состояние блок 1 перечисления множеств элементов покрытия, в блок 7 заносят матрицу покрытий, а в блок 5 памяти — данные о расходах на каждого исполнителя, На вход 8 пуска устройства подают импульс уровня логической единицы. При этом блок 3 синхронизации формирует на своих выходах 11 — 13 последовательность сигналов уровня логической единицы, предусмотренную временной диаграммой его работы.

Блок 3 формирует импульс уровня логической единицы на своем выходе 11. Блок 1 формирует на своих выходах первое множество исполнителей. Блок 4 проверяет, может ли текущее множество исполнителей выполнить все операции. Через время, достаточное для окончания указанных операций, блок 3 формирует потенциал уровня логической единицы на своем выходе 12, При этом блок 4 вырабатывает значение признака обеспечения покрытия для текущего множества исполнителей. В том случае, если текущее множество исполнителей не может выполнить весь набор операций, значение признака равно нулю, Если текущее множество исполнителей может выполнить весь набор операций, значение признака становится равным единице. При этом блок 5 памяти формирует на своих выходах информацию, загруженную по каждому адресу из числа выбранных потенциалами уровня логической единицы (стоимости использования каждого исполнителя текущего множества). Через время, достаточное для окончания указанных операций, блок 3 формирует импульс уровня логической единицы на своем выходе 13. При этом блок 6 складывает все коды, присутствующие на его информационных входах (определяет стоимость использования текущего множества исполнителей), сравнивает полученную сумму со значением, накопленным в предыдущих тактах работы, в том случае, если текущая сумма не превышает ранее некопленной, запоминает ее и вырабатывает импульс уровня логической единицы на выходе признака не больше. При этом регистр 2 фиксирует информацию, присутствующую на его информационном входе (т,е. запоминает текущее множество исполнителей, использование которых требует наименьших затрат), Через время, достаточное для окончания указанных процессов, блок 3 снимает потенциал с выхода 12 и формирует импульс уровня логической единицы на своем выходе 11, Далее работа устройства повторяется до полного перебора (перечисления) всех множеств исполнителей, При этом на выходе 9 устройства сформирован оптимальный

1711175

50

55 состав исполнителей, а на выходе 10 — выход стоимости выполнения всех операций.

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

Устройство для решения задач оптимизации, содержащее блок синхронизации, блок перечисления множеств элементов покрытия, блок памяти и регистр, причем вход запуска устройства подключен к входу пуска блока синхронизации, о т л и ч а ю щ е ес я тем, что, с целью расширения функциональных возможностей устройства путем решения задач покрытия, в него введены блок задания матрицы покрытий, блок проверки условия покрытия и накапливающий блок выбора минимальной суммы, причем первый выход блока синхронизации подключен к тактовому входу блока перечисления множеств элементов покрытия, выход признака принадлежности М-го элемента текущему множеству которого (М = 1...„Э, где Э вЂ” количество элементов в полном множестве покрывающих элементаB) подключен к входу задания множества элементов покрытия блока проверки условия покрытия, к К-му адресному входу блока памяти и к M-му разряду информационного входа регистра, выход которого является выходом

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

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

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

1 /111 75

187 1 Щ 18 18>>

1817 183 т

191 о о о

192

Оо о a o о о о

a oo о оо о о о о о о о о

o o o о о о о o o

Ри з

35

45

Составитель А,Мишин

Редактор С.Патрушева Техред М.Моргентал Корректор Н.Король

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

Заказ 341 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб,, 4/5