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

;.Я ОПИСАНИЕ ИЗОБРЕТЕНК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 4 ОдГОСУДАРСТВЕННЫИ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетельство СССР% 1305705,кл. 6 06 Е 15/20, 1985,Авторское свидетельство СССРМ 1575201, кл. 6 06 Р 15/20, 1988,(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ(57) Изобретение относится к вычислительной технике и может быть использовано для многомерной оптимизации набора решений. Цель изобретения - расширение функциональных возможностей устройства за счет оптимизации выбора подмножества элементов множества при выполнении ограничений на множество их параметров, Устройство содержит блок 1 регистрации, блок 2 синхронизации, блок 3 перечисления подмножеств элементов множества, блок 4 проверки выполнения ограничений, выходы 5 признаков принадлежности элементов множества подмножеству оптимальных устройств, вход 6 пуска устройства, с первого по третий выходы 7 - 9 блока синхронизации, входы 10 задания значений элементов множества, выход 11 признака окончания работы устройства и входы 12 задания значений параметров элементов множества устройства. Перед началом работы устройство настраивают на заданный закон перечисления подмножеств элементов множества и систему ограничений, накладываемых на параметры элементов подмножества. На вход 6 пуска устройства подают импульс уровня логической единицы, При этом блок 2 синхронизации формирует на своих выходах 7 - 9 последовательность синхроимпульсов, предусмотренную временной диаграммой работы, под управлением которой на выходах 5 устройства формируется оптимальное подмножество элементов. 1 ил.(2) Изобретение относится к вычислительной технике и может быть использовано длямногомерной оп.имизации набора пешений,Целью изобретения является расширение функциональных возможностей устрой-тва за счет оптимизации ьыбораподмножества элементов множества привыполнении ограничений на множество ихпараметров.На чертеже представлена функциональная схема устройства,Устройство содержит блок 1 регис 1 ра) ии, бйок 2 синхронизации, блок 3 перечисления подмножеств элементов множества,блок 4 проверки выполнения ограничений,выходы 5 признаков принадлежности элементов множества подмножеству оптимальных, вход 6 пуска, с первого по трегийвыходы 7 - 9 блока синхронизации, входы10 задания значений элементов множества,выход 11 признака окончания работы и входы 12 задания значений параметров элементов множества,Устройство работает следующим образом,Пусть, например, система включает вс,бя Э различных элементов, каждый из которых может быть:-оздан в В вариантах.Русть Нк - номер варианта К-го элементасистемы (К = 1, , Э, Известны срок служоыТк(Н), стоимость С(Н) и вес Ек(Н,) К-гоэлемента системы,Требуется выбрать такой комплект эле.ментов, который будет обеспечивать максимально возможный срок службы всейсистемы при ограничении на ее стоимость ивес, т. е. для всех К необходимо найти такиеНк, чтобыгп)п Гк ( Нк ) -Нк(1)при ограничениях К=1Ограничения (2) показывают, что стоимость и вес выбранного комплекта (набора вариан ов исполнения элементов системы) не должны превышать заданных вели ин Со и Ео соответственно,Задача (1) решается методом напив- ленного перебора,Перед началом работы нумераци о вариантов всех элементов сисгемы упорядочивают по возрастанию величины 10 15 20 25 30 35 4) 45 50 Т(Нк) таким образом, чтобы Тк(1). Тк (Вк) при этом предполагается, что Ск(1) - С(Вк) и Ек(1)Ек(Вк), блок 3 настраиван.т на требуемыи алгоритм перечисления подмножеств элементов множества(для данного примера такой, прои котором ; ч- редное подмножество элементов матрицы // ) //форк;ируется из предыдущего путем замены наименьшего из его элементов на элемент следующего по порядку варианта исполнения), блок 4 настраивают на проверку ограничений, заданных выражениями (2), по входам 10 и 12 задают элементы множества и их параметры (т. е, в данном случае матрицы,/Т //,//С // и //Е //), блок 3 приводят в исходное сосояние, при котором потенциалы уровня логической едини.,ы нз его выходах определяют первое из перечи ляемых подмножеств (для данного примера такое, при котором все элементы набора исполняются по первому варианту).На вход 6 устройства подают сигнал уровня логической единицы, При этом блок 2 синхронизации формирует на своих выходах 7 - 9 последовательность импульсов, предусмотренную временной диаграммой его работыБлок 2 синхронизации формирует импул с уровня логической единицы на своем выходе 7. При этом блок 1 регистрации фиксирует установленное на его информационном входе значение (т, е, для данного примера код, определяющий подмножество выбранных вариантов исполнения элемен;ов системы) и выдает его на свой информа.ио н н ы й в ы ход.Через время, достаточное для выполнения укаэанной операции, блок 2 синхронизации формирует импульс уровня логической единицы на своем выходе 8. При эгом блок 3 перечисления формирует по заданному алгоритму и фиксирует на своих вьходах в виде набора потенциалов уровней логичяеского нуля и логической единицы очередное подмножество множества элементов (тем самым выбирается очеред) ой набор вариантов исполнения элементов системы, срок службы которого больше срока службы предыдущего набора),Через время, достаточное для окончания указанной операции, блок 2 синхронизации формирует импульс уровня логической единицы на своем выходе 9. При - ом блок 4;ыдает на свой выход результат проверки заданных ограничений,Б этом случае, если числовые значения .оступившие по его информационным ехо,;ам, выбранным пктенциалами уровня логической единиць на соответствующих имЗаказ 1714 Тираж 420 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 входах подключения, не приводят(т. е. если все критические параметры //С //и //Е // текущего набора вариантов исполнения элементов системы удовлетворяют заданным требованиям), блок 4 сохра гет потенциал уровня логического нуля на воем выходе признака нарушения ограничений, Гри этом ереэ заранее определенное время ожидания (равное времени срабатывания блока 4) блок 2 синхронизации по:торит цикл выдачи синхроимпульсов на выходах 7 - 9 и работа устройства повторится,В том случае, если выбранные числовые значения нарушают заданные ограничения (т, е, сели стоимость и/или вес очередного набора вариантов исполнения элементов системы не удовлетворяют заданным требованиям), блок 4 формирует на своем выходе признака нарушения ограничения потенциал уровня логической единицы. При этом блок 2 синхронизации прекращает формирование синхроимпульсов (останавливается).Формула изобретения Устройство для решения задач оп имизации, содержащее блок регистрации, блок синхронизации и блок перечисления подмножеств элементов множества, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к входу признака записи блока регистрации, второй выход блока синхронизации подключен к тактовому входу блока перечисления подмножеств элементов множества, выход признака принадлежности (К,М) - го элемента множества составу элементов подмножества (К =- 1,5 10 15 20 25 30 35 Э; М =- 1 В, где Э и В - количество строк и столбцов в матрице элементов множества) которого подключен к (К,М) - му разряду информационного входа блока регистрации, (К,М)-й разряд информационноо выхода которого является выходом признака принадлежности (К,М)-го элемента множества подмножеству оптимальных устройства, вход задания значения (К,М) - го элемента множества которого подключен к одноименному входу блока перечисления подмножеств элементов множества, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет оптимизации выбора подмножества элементов множества при выоплнении ограничений на множество их параметров, в него введен блок проверки выполнения ограничений, причем выход признака принадлежности (К,М) - го элемента множества составу элементов подмножества блока перечисления подмножеств элементов множества подключен к входу подключения ( К,М) - х информационных входов группы блока проверки выполнения ограничений, выход признака нарушения ограничений которого является выходом признака окончания работы устройства и подключен к входу останова блока синхронизации, третий выход которого подключен к входу опроса блока проверки выполнения ограничений, (К,М) - й информационный вход Р - й группы которого (Р = 1 П, где П - количество параметров элементов множества, на которые наложены ограничения) является входом задания Р - го параметра (К,М) - го элемента множества устройства.