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

О

ел

00

х| СО

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

Целью изобретения яетяется расширение функциональных ВОЗ.ОЖНОГТРЙ устрой- т в а за счет оптимизации ьыбора подмножества элементов множества при выполнении ограничений на множество их параметров.

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

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

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

Пусть, например, система включает в с.дбя Э различных элементов, каждый из кр- -орых может быть оздан в В вариантах Пусть Нк - номер варианта К-го элемента

системы (К 1Э . Известны срок службы

Тк(Нк), стоимость Ск(Нк) и вес Ек(Нк) К-го элемента системы.

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

min Гк(Нк)- при ограничениях

к - 1

Ск(Нк)С0

i

(2)

Ок(Нк) Е0 I

К 1

Ограничения (2) показывают, что стоимость и вес выбранного комплекта (набора вариантов исполнения элементов системы) не должны превышать заданных величин Со и Ео соответственно

Задача (1) решается методом наирзв- ленного перебора.

Перед началом работы нумерацию вариантов всех элементов системы упорядочивают по возрастанию величины

Тк(Нк) таким образом, чтобы Тк{1) ... Тк (В),

при этом предполагается, что С(1) ...

Ск(Вк) и Ьк(1) Вк(Вк), блок 3 нас I раивают на требуемый алгоритм перечис5 ления подмножеств элементов множества (дня данного примера такой, прои котором с ч- редное подмножество элементов матрицы // I //формируется из предыдущего путем замены наименьшего из его элементов

10 на элемент следующего по порядку варианта исполнения), блок 4 настраивают на проверку ограничений, заданных выражениями (2), по входам 10 и 12 задают элементы множества и их параметры (т. е в данном случае

15 матрицы //Т //,//С // и //Е //), блок 3 приводят в исходное состояние, при котором потенциалы уровня логической едини- ,„: m его выходах определяют первое из перечисляемых подмножеств (дпя данного

20 примера такое, при котором все элементы

набора исполняются по первому варианту).

Из вход 6 устройства подают сигнал

уровня логической единицы. При этом блок

2 синхронизации формирует на своих выхо25 дах 7-9 последовательность импульсов, предусмотренную временной диаграммой его работы

Бяок 2 синхронизации формирует им- пульс уровня логической единицы на своем

30 выходе 7 При этом блок 1 регистрации фиксирует установленное на его информационном входе значение (т. е. для данного примера код, определяющий подмножество выбранных вариантов исполнения элемен35 гив системы) и выдает его на свой информационный оыход.

иерез время, достаточное для выполнения указанной операции, блок 2 синхронизации формирует импульс уровня

40 логической единицы на своем выходе 8. При эюм блок 3 перечисления формирует по заданному алгоритму и фиксирует на своих выходах в виде набора потенциалов уровней логичяеского нуля и логической едини45 цы очередное подмножество множества элементов (гем самым выбирается очередной набор вариантов исполнения элементов системы, срок службы которого больше срока службы предыдущего набора).

50Через время, достаточное для окончания указанной операции блок 2 синхронизации формирует импульс уровня логической единицы на своем выходе 9. При GiOM блок 4 ыдает на свой выход результлт

55 проверки заданных ограничений

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

входах подключения, не приводят (т. е. если все критические параметры //С //и //Е // текущего набора вариантов исполнения элементов системы удовлетворяют заданным требованиям), блок 4 сохраняет потенциал уровня логического нуля на своем выходе признака нарушения ограничений. При этом через заранее определенное время ожидания (равное времени срабатывания блока 4) блок 2 синхронизации повторит цикл выдачи синхроимпульсов на выходах 7 - 9 и работа устройства повторится.

В том случае, если выбранные чистовые значения нарушают заданные ограничения (т. е. если стоимость и/или вес очередного набора вариантов исполнения элементов системы не удовлетворяют заданным требованиям), блок 4 формирует на своем выходе признака нарушения ограничения потенциал уровня логической единицы. При этом блок 2 синхронизации прекращает формирование синхроимпульсов (останавливается). Формула изобретения Устройство для решения задач оптимизации, содержащее блок регистрации, блок синхронизации и блок перечисления подмножеств элементов множества, при чем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к входу признака записи блока регистрации, второй выход блока синхронизации подключен к тактовому входу блока перечисления подмножеств элементов множества, выход признака принадлежности (К,М)-го элемента множества составу элементов подмножества (К 1

Э; М 1В, где Э и В - количество строк

и столбцов в матрице элементов множества) которого подключен к (К.М)-му разряду информационного входа блока регистрации,

(К,М)-й разряд информационного выхода которого является выходом признака принадлежности (К.М)-го элемента множества подмножеству оптимальных устройства, вход задания значения (К,М)-го элемента

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

за счет оптимизации выбора подмножества элементов множества при выоплнении ограничений на множество их параметров, в него введен блок проверки выполнения ограничений, причем выход признака принадлежности (К.М)-го элемента множества составу элементов подмножества блока перечисления подмножеств элементов множества подключен к входу подключения ( К,М)-х информационных входов группы

блока проверки выполнения ограничений, выход признака нарушения ограничений которого является выходом признака окончания работы устройства и подключен к входу останова блока синхронизации, третий выход которого подключен к входу опроса блока проверки выполнения ограничений, (К,М)-й информационный вход Р-й группы

которого (Р 1 П, где П - количество

параметров элементов множества, на которые наложены ограничения) является входом задания Р-ro параметра (К.М)-го элемента множества устройства.

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