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

(088. 8)е свидетельств С 06 С 7/122,СССР1982,ССР 1985 етельство06 Р 15/20 РЕШЕНИЯ ОПТИИИ осится к вычислижет быть испольмногомерных оптиелью изобретения ИПИ-НЕ 12,ементов ИЛИ 18, элемеО и 21, рег триггера элемен-НЕ 15нта ИЛИистра 22,25.и усик вычисли -быть испольто 17 19 ме ных оп л регемен элементов 4ементов тров и 4, равле ки состоит ентов ИПИ Е 9 из элемента ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР Н АВТОРСКОМУ(57) Изобретение оттельной технике и мзовано для решениямизапионных задач,Изобретение относит тельной технике и мо зовано для решения много р тимизационных задач.11 елью изобретения является расширение функциональных возможностей устройства за счет решения задачи ми нимизации затрат на разработку и эксплуатацию элементов систем.На фиг, 1 - 4 представлена схема устройства; на фиг. 5 - обобщенная структурная схема устройства.Устройство содержит матрицу элементов 1 задержки, группу регис 2, две группы элементов И-ИПИ 3 группу элементов И 5, блок 6 уп ния, ключ 7 и блок 8 счета.Каждый элемент 1 задерж является расширение функциональных возможностей устройства за счет решения задачи минимизации затрат на разработку и эксплуатацию элементов системы, С этой целью перед началом работы задают затраты на разработку элементов системы и затраты на эксплуатацию М-го элемента (М = 1С, где С - количество элементов в системе) при реализации К-й функции (К1б, где Ф - количество функций, выполняемых системой) . После пуска устройство включает в систему те элементы, затраты на эксплуатацию которых минимальны с учетом затрат на разработку каждого элемента системы.5 ип. и 11, элемента в И 13 и 14, эл элемента И-НЕ элементов И 2 етчиков 23 и 24 теля 26. Группу регистров 2 образую ры 27 и 28, первую группу в И-ИЛИ 3 - элемент И 29 и И 30, вторую группу элемен лементы И 31 и 32, группу э 5 - элементы И 33 и 34.Блок 6 управления содержит элемен ты ИЛИ-НЕ 35, элемент ИПИ 36, элемен ты И-НЕ 37 и 38,. элементы И 39 и 40, формирователь 41, элемент ИЛИ-НЕ 42, счетчики 43 и 44, элементы КПИ-НЕ 45 и 46, счетчик 47 и регистр 48.15434 6фффф Составитель А.МишинЛ.Пчолинская Техред Л. Сердюкова Обручар орре Подписноеизобретениям и открытиямКо 1 ч 7 вкгпочает в себя группыконтактов 49 - ,62,1 роме того на функциональной схеме обозначено: позицией 63 - вход уП 5равления регистром 22 элемента 1 задержки первой строки второго столбцаматрицы элементов задержки, 64 - информационные входы регистров 22 всехэлементовзадержки и регистров 27и 28 группы регистров 2, 65 - входуправления регистром 22 элемента 1задержки первой строки первого столбца матрицы элементов задержки, ббС-вход триггеров (элемент 25) всех 15элементов 1 задержки, а также входэлемента 2 ИЛИ-НЕ 46, 67 - вход управления регистром 22 элемента 1 задержки второй строки первого столбца матрицы элементов задержки, 68 - вход 20управления регистром 22 элементазадержки второй строки второго столбиа матрицы элементов задержки, 69вход управления регистром 27 группырегистров 2, 70 - вход управления регистром 28 группы регистров 2, 71выходной сигнал элемента 1 задержкипервой строки первого столбца матрицы элементов задержки, 2 - выходнойсигнал элемента 1 задержки первойстроки второго столбца матрицы эле -ментов задержки; 73 - выходной сигналэлементазадержки второй строкивторого столбца матрицы элементов задержки, 74 - выходной сигнал элемен 35та 1 задержки второй строки первогостолбца матрчцы элементов зацержки,,75 - информационные выходы счетчика47 и регистра 48 блока 8 счета,76 - дешвЪратор, .77 - выходной сигнал элемента 32.Устройство работает следующим образом.Описание работы устройства покажем на числовом примере. Имеем систему из двух элементов, затраты наразработку и производство которых соответственно С, = 5 единиц стоимостии Со = 4 единицы стоимости (ед,ст,),Заданы две Функции которые,цолжнарешать система. Затраты на удовлетворение первым элементом первой требуемой Аункции С , = 4 ед,ст., второйтребуемой Функции С = 3 ед,ст. Зат 1раты на удовлетворение вторым элемен 55том первой требуемой дункции С- 2 ед,ст второй С= 5 ед.ст.Требуется определить набор элементовтак, чтобы разрабатываемая система могла решать все возложенные на нее функции, а велич ина с умма рных з а трат на разработку системы, ее производство и эксплуатацию была минимальной,Для решения задачи в режиме Установка в регистр 22 элемента 1 задержки первой строки первого столбца матрицы элементов задержки заносится число 4, в регистр 28 элемента 1 задержки первой строки второго столбца - число 3, в регистр 22 элемента 1 задеркки второй строки первого столбца - число 2, в регистр 2 элемента 1 задержки второй строки второго столбца - число 5, в регистр 27 группы регистров 2 - ч исло 5, в рег ис тр 28 группы регистров 23 - число 4. В положении ключа 7 "Установка на информационные входь. регистра 48 блока 8 счета поступают единичные сигналы и содержимое регистра принимает максимальное значение. Счетчик 47 блока 8 счета устанавливается в О". Счетчик 43 блока б управления устанавливается в состояние "1110", счетчик 44 - в состояние 000, Единичный сигнал с выхода элемента 36 блока. 6 управления подается на элемент 9 всех элементов 1 задержки. По этому сигналу счетчик 23 всех элементов 1 задержки устанавливается в состояния, соответствующие содержимому соответствующих регистров 22 элементов 1 задержки, а счетчики 24 устанавливаются в состояния, соот ветствующие содержимому регистра 27 (для первой строки) и соцержимому регистра 28 (для второй строки), Триггеры, управляющие световой индикацией всех элементов 1 задержки, устанавливаются в "О".При переключении ключа 7 в положе-ние Пуск информационные входы регистра 48 блока 8 счета подклочаются к выходам счетчика 47. Нулевой сигнал с контакта 62 ключа 7 подается на элементы 36 и 38 блока 6 управленияВход С счетчика 44 блока б управления отключается от выхода формирователя 41 и подключается к выходу элемента 35, С выхода элемента 38 ".1" подается на вход Б счетчика 44, разрешая работу счетчика на сложение. Так как счетчик 43 блока 6 управления устанавливается в "11 О", то на выходе элемента 35 имеется О , на выходе элемента Зб также "0". Единичный сигнал с выхода элемента 37 открывает элементы .39 и 40. Так как счетчик 4443416,5 15 установлен в000", на 0-выходе дешаЪратора 76 присутствует "1", на выходе элемента 39 также ,Нулевой сигнал с выхода элемента36 блока 6 управления поступает наэлементы 9, 16 и 17 всех элементовзадержки и одновременно запускаетсчетчик 47 блока 8 счета. Гдиничныйсигнал с выхода элемента 39 блока 6управления подается на вход элемента1 О элемента 11 задержки первой строки первого столбца матрицы элементовзадержки. Тем самым этот элемент задержки как бы включается,На входах Б и Б,2 счетчика 23 элемента 1 задержки первой строки первого столбца устанавливается комбинация "10", так как при установке всчетчик записано число 4 (в двоичномвиде 100), на выходе элемента 1 имеется "1", Комбинация ББ= 10 соответствует операции вычитания. Покасодержимое счетчика 23 элемента 1 задержки первой строки первого столбцаматрицы элементов задержки не равнонулю, на выходе элемента 11 данногоэлемента задержки присутствует "1",т.е, входной сигнал;л 1 с гнал с элемента 39) как бы задерживается на время,. равное четырем тактам вычитания счетчика. Как только содержимое счетчика23 данного элемента 1 задержки станетравно нулю, на выходе элемента 11 этого же элемента 1 задержки устанавливается 0, который инвертируетсяэлементом 9 и на входах Б Б счетчика 23 появляется комбинация "11", соответствующая остановке счета.Нулевой сигнал с выхода элемента11 элемента 1 задержки первой строки.первого столбца матрицы элементов задержки (ИЭЗ) поступает также на элементы 14 и 15 данного элемента 1 задержки. Так как после установки навыходе элементов 29 и 33 имеется ,то на выходе элемента 3 данного элемента 1 задержки присутствует "1", навыходах элементов 14 и 15 - "0", Навходы БЯ счетчика 24 данного элемента 1 задержки поступает комбинация"10", Счетчик начинает работу на вычитание. Так как по условию примерав него записано число 5 в двоичномвиде 101), то входной сигнал задерживается еше на 5 тактов вычитания.Как только содержимое счетчикастанет равно нулю, на выходе элемента 19 элемента 1 задержки первойстроки первого столбца МЭЗ устанавливается нуль, который поступает наэлемент 33 и с его выхода нулевойсигнал подается на элементы 3 - 1 5всех элементов 1 задержки первойстроки МЭЗ. Происходит блокировкасчетчиков 24 элементов 1 задержкипервой строки МЭЗ. Этим обеспечивает"ся однократное включение затрат наразработку 1-го средства при реализации алгоритма,Нулевой сигнал с выхода элемента19 олемента 1 задержки первой строкипервого столбца МЭЗ подается также иавход элемента 20 данного элемента .1задержки, инвертируется и поступаетна вход элемента 21, на Л-вход триггера 25 данного элемента 1 задержкии на вход элемента 30 группы элементов 3. С выхода элемента 21 нулевойсигнал поступает на элемент 29 группы элементов 3 и с выхода элемента 2925 подается на элементы 12 - 14 всехэлементов 1 задержки первого столбцаМЭЗ. Происходит блокировка работыэлементов 1 задержки первого столбца МЭЗ.С выхода элемента 30 группы элементов 3 единичный сигнал поступаетодновременно на оба элемента 1 задержки второго столбца МЭЗ (на элемент 10), Счетчики 23 обоих элементов1 задержки второго столбца МЭЗ начи"нают одновременно операцию вычитания.В счетчик элемента 1 задержки первойстроки второго столбца МЭЗ записаночисло 3, в аналогичный счетчик элемента 1 задержки второй строки второго столбца МЭЗ - число 6.Следовательно, нулевой сигнал навыходе счетчика 23 элемента 1 задержки первой строки второго столбца по 45 явится раньше. Так как работа счетчика 24 элемента 1 задержки первойстроки второго столбца заблокировананулевым сигналом с выхода элемента33, то нулевой сигнал с выхода элемента 11 данного элемента 1 задержки,дважды проинвертированный элементами15 и 18, поступает на вход элемента20. На выходе элемента 20 устанавливается "1", которая поступает на вхо 5 ды триггера 25, элементы 12 и 21 иэлемент 32. На выходе элемента 21 устанавливается О, который подаетсяна К-входы триггера 25 и на вход эле-.мента 31 . Нулевой сигнал с выходаэлемента 31 группы элементов 4 поступает на элементы 13, 14 и 12 всехэлементов 1 задержки второго столбцаМЭЗ и блокирует работу счетчиков 24,этих элементов 1 задержки.Таким образом в решение оказалисьвключены элементы 1 задержки первойстроки. Суммарное время задержки сигнала составило Т12 ед. 1 ОЕдиничный сигнал с выхода элемента 32 группы элементов 4 подается навход Я, счетчика 43 блока 6 управления и на вход Я счетчика 47 блока 8счет а. Счетч ик 47 ус танавливает с я(Я Я11). Счетчик 43 начинает операцпо вычитания (ЯЯ = 10). Одновременно "1" с выхода элемента 32 подается (сигнал 77) в блок сравнения иразрешает сравнение содержимых счет-. 20чика 4 и регистра 48 блока 8 счета,которые подаются в блок сравнения пошине 75. Содержимое счетчика 47 равновремени задержки сигнала, т,е. числу12 (1100). В регистре 48 в режиме "Ус тановка было записано максимальноечисло 15 (1111). Так как содержимоесчетчика 47 меньше содержимого ре".гистра 48, то. в блоке сравнения вырабатывается единичный сигнал, который 30поступает в блок 8 счета (сигнал 66)через контакт 52 ключа 7,на вход элемента 46, Нулевой сигнал с выхода 46элемента подается на входы Б Я регистра 48. Комбинация "ОО" на входахЯЯ регистра 48 соответствует уста,новке числа, Информация из счетчика47 переписывается в регистр 48 черезконтакты 54, 56, 58 и 60 ключа 7,40Единичный сигнал 66 иэ блока сравнения поступает на С-входы триггеров25 всех элементов 1 задержки МЭЗ иустанавливает их в состояния, соответствующие сигналам на входах 1 и К. 45В единичное состояние в данном случаеустанавливаются триггеры 25 элементов5 задержки первой строки МЭЗ, Выходытриггеров 25 через усилители 26 элементовзадержки сигналами 71, 72,73, 74 подаются на пульт управленияна соответствующие светодиоды.Содержимое регистра 48 блока 8счета поступает также в блок дешиЬрации (сигнал 75), Выход блока деший 55рации соединен со световой индикациейпульта управления,Счетчик 43 блока 6 управления припоступлении на его вход Я единичного сигнала с выхода элемента 32 группы элементов 4 работает в режиме вычитания, Как только содержимое счетчика 43 блока 6 управления станет равным нулю, на выходе элементов 35 и 36 установится 1", содержимое счетчика 44 увеличится на "1", т,к, на С-вход поступает единичный сигнал с выхода элемента 35. Следовательно, единичный сигнал появляется на выходе дешийратора 76 блока 6 управления.Единичный сигнал с выхода элемента 36 блока 6 управления устанавлива" ет все элементы 1 задержки 1 фЭЗ в исходное состояние. На выходе элемента 32 группы элементов 4 устанавливается 0. На входах ЯЯ счетчика 43 блока 6 управления устанавливается комбинация ББ = 01, соответствующая операции сложения. Как только содержимое счетчика 43 блока 6 управления станетбольше нуля, то на. выхоце элемента 35 появится Оп. Этот сигнал подается на вход Б счетчика 43, Комбинация Б,Я =00 соответствует установке числаВ счетчике 43 устанавливается исходное число 14 (1110). На выходе элементов 35 и 36 устанавливается "0", на выходе элемента 37 - "1". Этот единичный сигнал открывает элементы 39 и 40 блока 6 управления. Так как единичным выходом дешиЬратора 76 являетсявыход 1, то на выходе элемента 39 - "0", на выходе элемента 40 - "1". Таким образом управляющий сигнал подается на элемент 10 элемента 1 задержки второй строки первого столбца МЭЗ. Его работа аналогична работе описанного выше элемента 1 задержки первой строки . первого столбца ИЭЗ, за исключением того, что после появления на выходе счетчика 24 элемента 1 задержки второй строки первого столбца нулевого сигнала с выходов элемента 19 данно го элемента задержки нулевой сигнал подается на вход элемен га 34 и с его выхода поступает на элементы 13 - 15 обоих элементов 1 задержки второй строки. Этим производится блокирование работы счетчиков.24 обоих элементов 1 задержки второй строки, что обеспечивает однократное включение затрат на разработку второго элемента системы в решение. Суммарная задержка .управляющегосигнала счетчика 43 и 24 элемента 1задержки второй строки первого столбцаТ=2+4 =бед,Единичный сигнал с выхода элемента 20 элемента 1 задержки второйстроки первого столбца поступает навыход элемента 30 группы элементов 3и с его выхода подается на все элементы 1 задержки второго столбца МЭЗ,которые начинают одновременную работу 1 Оаналогично описанному. Счетчик 23элемента 1 задержки первой строкивторого столбца задержки задержитвходной сигнал (с выхода элемента 30)на 3 такта вычитания и начнет работусчетчик 24,содержимое которого равно 5, Суммарное время задержки данного элемента составит 8 тактов вычитания, Счетчик 23 элемента 1 задержкивторой строки второго столбца задержит второй сигнал на 5 тактов вычитания.Однако так как работа счетчика 24данного элемента 1 задержки блокирована, то нулевой выходной сигналсчетчика 23 через элементы 11, 15и 8 попадает на вход элемента 20.ина его выходе устанавливается 1",Таким образом общее время задержкивходного сигнала элементом 1 задержки второй строки второго столбца,окажется равным 5 тактам вычитания. Таккак счетчик 24 элемента 1 задержкипервой строки второго столбца продолжает вычитание, то единичный сигналс выхода элемента 20 элемента 1 задержки второй строки второго столбцаМЭЕЗ подается на вход элемента 21,о3-вход триггера 25, на вход элемента12 и на вход элемента 32 группы элементов 4, С выхода элемента 21 нулевой сигнал через элемент 31 группыэлементов 4 поступает на элементы12 - 14 элемента 1 задержки первойстроки второго столбца МЭЗ и останавливает работу счетчика 24. На выходеэлемента 20 данного элемента 1 задержки остается "О", Таким образом, врешение включается элемент 1 задержки второй строки второго столбца МЭЗ. 50Суммарное время задержки управляю"щего сигнала двумя элементами 1. задержки второй строки МЭЗ составило2 + 4 + 5 = 11 тактов вычитания, Соответственно, содержимое счетчика 47блока 8 счета равно 12,Единичный сигнал с выхода элемента 32 группы элементов 4 подается.навход Я счетчика 43 блока 6 управления, включая его в режим вычитания,и на вход Я счетчика 47 блока 8 счета, останавливая счет. Одновременноэтот же сигнал поступает в блок срав"нения (сигнал 77), разрешая сравнениесодержимого счетчика 47 и регистра 48блока 8 счета, Так как в предыдущемцикле в регистр 48 было записано число 12, а содержимое счетчика 47 блока 8 счета равно 11, то в блоке сравнения вырабатьвается единичный сигнал(сигнал 66), который через контакт 52ключа 7 подается на элемент 46 блока8 счета. Нуль с выхода элемента 46подается на входы Я и Я 4 регистра48, устанаЬливая режим приемки числа.Из счетчика 47 в регистр 48 переписывается число 11. Одновременно сигнал66 поступает на С-вход триггеров 25всех элементов 1 задержки ИЭЗ .Триггеры 25 элементов 1 задержки,включенные в решение (в нашем примере триггеры 25 элементов 1 задержкивторой строки), переключаются в единичное состояние. С их выхода единичные сигналы, усиленные элементом 26,подаются на матрицу светодиодов пульта управления,Содержимое регистра 48 блока 8счета подается в блок дешифрации (вданном случае число 11) . ИнФормацияс блока дешифрации подается на световую индикацию пульта управления.Как было отмечено вьппе, счетчик 43при поступлении на его вход Я, единичного сигнала с элемента 32 группыэлементов 4 начал работать на вычитание. Как только содержимое счетчика43 станет равно нулю, на вьходе элемента 35 блока 6 управления появляется единица, которая, поступая черезконтакт 50 ключа .7 на С-вход счетчика 44, увеличивает его содержимое наединицу, то есть равна 2 (двоичнаяформа 10) .На выходе Д счетчика 44 блока 6управления появляется 1 , которая,поступая на элемент 42 блока 6 управления, выкгдочает формирователь 41.Устройство переходит в останов. Синдикации пульта управления считьвается информация об элементах, включенных в решение, и значение целевойфункции, полученное в результате решения. Значение целевой Функции - 11,элементы, включенные в решение,элементы 1 задержки второй строкиМЭЗ,15434Следовательно, для удовлетворения Заданных Фувкций в разрабатываемую систему необходимо включить второй Элемент,На фиг.5 обозначено: позицией 78- Элементы памяти матрицы, 79 - сумматоры матрицы 80 - элементы памяти10 Группы, 81 - блок выбора минимального йода, 82 - триггеры матрицы, 83 Элементы ИЛИ первой группы, 84 - элементы ИЛИ второй группы и 85 - вход 11 уска устройства,С 15Перед началом работы обнуляют триг- еры 32, в элементы 80 памяти заносят. Моды затрат на разработку М-го эле-Мента системы (М = 1,.,С, где С -20 количество элементов в. системе), в Элементы 78 памяти заносят коды зат рат на эксплуатацию М-го элемента пщ реализации К-й функции (К = 1,,Ф, где Ф - количество Функций 25 выполняемых .системой)После подачи. сигнала уровня "1" на вход 85 пуска, устройство асинхронно выбирает минимальный с учетом затрат на разработку Элемент матрицы затрат на эксплуатаФпо, устанавливает в "1" соответствующий ему триггер 82 и исключает блокирует выдачу информации элемен 1 ами 78 и 80) затраты на разработку Элемента и затраты на эксплуатацию Ю 35 при реализации функции элемента.После завершения переходных процессов, установленные в "1" триггеры 82 представляют решение задачи оптимизации Эатрат на разработку и эксплуатациюСистемы.Формула изобретенияУстройство для решения оптимизационных задач, содержащее матрицу из 1 б;12СВФ элементов памяти, где С " количество исследуемых элементов. систем, Ф - количество функци 11 .выполняемых элементами системматрицу из Схф триггеров и первую группу из Ф элементов ИЛИ, причем выход К-го григгера (К =1 Ф) М-й строки (М = = 1С) матрицы. подключены к М-му входу К-го элемента ИЛИ первой группы, отлич ающееся тем, что, с целью расширения функциональных возможностей устройства за счет решения задачи минимизации затрат на разработку и эксплуатацию элементов оистем, в него введены матрица из Сф сумматоров, группа из С элементов памяти, блок выбора минимального кода и вторая группа элементов ИЛИ, причем выход К-го элемента ИЛИ первой группы подключен к входам блокировки чтения всех элементов памяти К-го столбпа матрицы, выход К-го элемента памятиМ-й строки матрицы подключен к входу первого слагаемого К-го сумматора М-й строки матрицы, выход которого подключен к входам блокировки чтения всех элементов памяти К-го столбца матрицы, выход К-го элемента памяти М-й строки матрицы подключен к входу первого слагаемого К-го сумматора М-ой строки матрицы, выход которого подключен к (К, М) -му входу блока выбора минимального кода, (К, М)-й выход позиции минимального кода которого подключен к входу установки в "1" К-го триггера М-й строки матрицы, выход которого подключен,к К-му входуМ-го элемента ИЛИ второй группы, выход которого подключен к входу блокировки чтения М-го элемента памяти. группы, выход которого подключен к входам вторых слагаемых всех сумматоров М-й строки матрицы, вход опроса блока выбора максимального кода под ключен к входу пуска устройства, 15434 6