Устройство для решения оптимизационных задач Советский патент 1990 года по МПК G06F17/00 

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

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

На фиг. 1 - 4 представлена схема устройства; на фиг. 5 - обобщенная структурная схема устройства.

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

Каждый элемент 1 задержки состоит из элемента ИЛИ-НЕ 9, элементов ИЛИ

10 и 11, элемента ИЛИ-НЕ 12, элементов И 13 и 14, элементов ИЛИ-НЕ 15 - 17, элемента И-НЕ 18, элемента ИЛИ 19, элементов И 20 и 21 , регистра 22, счетчиков 23 и 24, триггера 25 и усилителя 26.

Группу регистров 2 образуют регистры 27 и 28, первую группу элементов И-ИЛИ 3 - элемент И 29 и элемент ИЛИ 30, вторую группу элементов 4 - элементы И 31 и 32, группу элементов И 5 - элементы И 33 и 34 .

Блок 6 управления содержит элементы ИЛИ-НЕ 35, элемент ИЛИ 36, элементы И-НЕ 37 и 38, элементы И 39 и 40, формирователь 41, элемент ИЛИ-НЕ 42, счетчики 43 и 44, элементы ИЛИ-НЕ 45 и 46, счетчик 47 и регистр 48.

сл

Јь 00 Ј

Ключ 7 включает в себя группы контактов 49 - 62.

Кроме того на функциональной схеме обозначено: позицией 63 - вход уп- равления регистром 22 элемента 1 задержки первой строки второго столбца матрицы элементов задержки, 64 - информационные входы регистров 22 всех элементов 1 задержки и регистров 27 и 28 группы регистров 2, 65 - вход управления регистром 22 элемента 1 задержки первой строки первого столбца матрицы элементов задержки, 66 - С-вход триггеров (элемент 25) всех элементов 1 задержки, а также вход элемента 2ИЛИ-НЕ 46, 67 - вход управления регистром 22 элемента 1 задержки второй строки первого столбца матрицы элементов задержки, 68 - вход управления регистром 22 элемента 3 задержки второй строки второго столбца матрицы элементов задержки, 69 - вход управления регистром 27 группы регистров 2, 70 - вход управления регистром 28 группы регистров 2, 71 - выходной сигнал элемента 1 задержки первой строки первого столбца матрицу элементов задержки, 72 - выходной сигнал элемента 1 задержки первой строки второго столбца матрицы элементов задержки; 73 - выходной сигнал элемента 1 задержки второй строки второго столбца матрицы элементов задержки, 74 - выходной сигнал элемен- та 1 задержки второй строки первого столбца матрицы элементов задержки,

75- информационные выходы счетчика 47 и регистра 48 блока 8 счета,

76- дешифратор, 77 - выходной сих- нал элемента 32.

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

Описание работы устройства покажем на числовом примере. Имеем сие- тему из двух элементов, затраты на разработку и производство которых соответственно С01 - 5 единиц стоимости и С 0Ј - 4 единицы стоимости (ед.ст.). Заданы две Функции, которые должна репать система. Затраты на удовлетворение первым элементом первой требуемой (Ъуикции С f 4 ед.ст., второй требуемой функции С 3 ед.ст. Затраты на удовлетворение вторым элемен- том первой требуемой функции C;j. 2 ед.ст., второй Сг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 блока 6 управления устанавливается в состояние 1110, счетчик 44 - в состояние 000. Единичный сигнал с выхода элемента 36 блока 6 управления подается на элемент 9 всех элементов 1 задержки. По этому сигналу счетчик

23всех элементов I задержки устанавливается в состояния, соответствующие содержимому соответствующих регистров 22 элементов 3 задержки, а счетчики

24устанавливаются в состояния, соот- ветствующие содержимому регистра 27 (для первой строки) и содержимому регистра 28 (для второй строки), Триггеры, управляющие световой индикацией всех элементов 1 задержки, устанавливаются в О.

При переключении ключа 7 в положение Пуск информационные входы регистра 48 блока 8 счета подключаются к выходам счетчика 47. Нулевой сигнал с контакта 62 ключа 7 подается на элементы 36 и 38 блока 6 управления. Вход С счетчика 44 блока 6 управления отключается от выхода формирователя 41 и подключается к выходу элемента 35. С выхода элемента 38 1 подается на вход BЈ счетчика 44, разрежая работу счетчика на сложение. Так как счетчик 43 блока 6 управления устанавливается в П10, то на выходе элемента 35 имеется О, на выходе элемента 36 также О. Единичный сигнал с выхода элемента 37 открывает элементы 39 и 40. Так как счетчик 44

установлен в 000, на 0-выходе дешифратора 76 присутствует 1, на выходе элемента 39 также 1.

Нулевой сигнал с выхода элемента 36 блока 6 управления поступает на элементы 9, 16 и 17 всех элементов J задержки и одновременно запускает счетчик 47 блока 8 счет,а. Единичный сигнал с выхода элемента 39 блока 6 управления подается на вход элемента 10 элемента 11 задержки первой строки первого столбца матрицы элементов

та 9 элемента 1 задержки первой строки первого столбца ЮЗ устанавливается нуль, который поступает на g элемент 33 и с его выхода нулевой

сигнал подается на элементы 13-15 всех элементов 1 задержки первой строки МЭЗ. Происходит блокировка счетчиков 24 элементов 1 задержки 1C первой строки МЭЗ. Этим обеспечивается однократное включение затрат на разработку 1-го средства при реализации алгоритма.

Нулевой сигнал с выхода элемента

задержки. Тем самым этот элемент за- 15 элемента 1 задержки первой строки.

держки как бы включается.первого столбца МЭЗ подается также на

На входах S, и 5г счетчика 23 эле- вход элемента 20 данного элемента 1

мента 1 задержки первой строки перво- задержки, инвертируется и поступает

го столбца устанавливается комбина-на вход элемента 21, на J-вход тригция 10, так как при установке в20 геРа 5 данного элемента 1 задержки

счетчик записано число 4 (в двоичном

виде 100), на выходе элемента J1 име- Комбинация 5,(5г 10 соотПока

содержимое счетчика 23 элемента 1 за- 25 подается на элементы 12-14 всех

держки первой строки первого столбцаэлементов 1 задержки первого столбца

матрицы элементов задержки не равно

нулю, на выходе элемента П данного

элемента задержки присутствует 1,

т.е. входной сигнс.л (с-гнал с элемен- 30

та 39} как бы задерживается на время,

равное четырем тактам вычитания счетчика. Как только содержимое счетчика

23 данного элемента 1 задержки станет

равно нулю, на выходе элемента 11 1 задержки второго столбца МЭЗ начиго же элемента 1 задержки устанавли-нают одновременно операцию вычитания.

ется 1.

ветствует операции вычитания

и на вход элемента 30 группы элементов 3. С выхода элемента 21 нулевой сигнал поступает на элемент 29 группы элементов 3 и с выхода элемента 29

МЭЗ. Происходит блокировка работы элементов 1 задержки первого столбца МЭЗ.

С выхода элемента 30 группы элементов 3 единичный сигнал поступает одновременно на оба элемента 1 за- держки второго столбца МЭЗ (на элемент 10). Счетчики 23 обоих элементов

154 34 16

та 9 элемента 1 задержки первой строки первого столбца ЮЗ устанавливается нуль, который поступает на элемент 33 и с его выхода нулевой

сигнал подается на элементы 13-15 всех элементов 1 задержки первой строки МЭЗ. Происходит блокировка счетчиков 24 элементов 1 задержки первой строки МЭЗ. Этим обеспечивается однократное включение затрат на разработку 1-го средства при реализации алгоритма.

геРа 5 данного элемента 1 задержки

и на вход элемента 30 группы элементов 3. С выхода элемента 21 нулевой сигнал поступает на элемент 29 группы элементов 3 и с выхода элемента 29

МЭЗ. Происходит блокировка работы элементов 1 задержки первого столбца МЭЗ.

С выхода элемента 30 группы элементов 3 единичный сигнал поступает одновременно на оба элемента 1 за- держки второго столбца МЭЗ (на элемент 10). Счетчики 23 обоих элементов

Изобретение относится к вычислительной технике и может быть использовано для решения многомерных оптимизационных задач. Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи минимизации затрат на разработку и эксплуатацию элементов системы. С этой целью перед началом работы задают затроты на разработку элементов системы и затраты на разработку элементов системы и затраты на эксплуатацию M-го элемента (M=1,...,C, где C - количество элементов в системе) при реализации K-й функции (K=1,...Ф, где Ф - количество функций, выполняемых системой). После пуска устройство включает в систему те элементы, затраты на эксплуатацию которых минимальны с учетом затрат на разработку каждого элемента системы. 5 ил.

вается 0, который инвертируется элементом 9 и на входах S S счетчика 23 появляется комбинация 11, соответствующая остановке счета.

Нулевой сигнал с выхода элемента 11 элемента 1 задержки первой строки .первого столбца матрицы элементов задержки (МЭЗ) поступает также на элементы 14 и 15 данного элемента 1 за- 5 явится раньше. Так как работа счетчи- д ержки. Так как после установки на ка 24 элемента 1 задержки первой

выходе элементов 29 и 33 имеется 1, то на выходе элемента 13 данного элемента 1 задержки присутствует 1, на выходах элементов 14 и 15 - О. На входы S счетчика 24 данного элемента 3 задержки поступает комбинация 10. Счетчик начинает работу на вычитание. Так как по условию примера в него записано число 5 (в двоичном виде 101), то входной сигнал задерживается еше на 5 тактов вычитания. Как только содержимое счетчика станет равно нулю, на выходе элеменстроки второго столбца заблокирована нулевым сигналом с выхода элемента 33, то нулевой сигнал с выхода элс5Q мента 11 данного элемента 1 задержки, дважды проинвертированный элементами 15 и 18, поступает на вход элемента 20. На выходе элемента 20 устанавливается I, которая поступает на вхо55 ды триггера 25, элементы 12 и 21 и элемент 32. На выходе элемента 21 устанавливается 0м, который подается на К-входы триггера 25 и на вход элемента 31. Нулевой сигнал с выхода

В счетчик элемента 1 задержки первой строки второго столбца МЭЗ записано число 3, в аналогичный счетчик элемента 1 задержки второй строки второго столбца МЭЗ - число 6.

Следовательно, нулевой сигнал на выходе счетчика 23 элемента 1 задержки первой строки второго столбца построки второго столбца заблокирована нулевым сигналом с выхода элемента 33, то нулевой сигнал с выхода элсмента 11 данного элемента 1 задержки, . дважды проинвертированный элементами 15 и 18, поступает на вход элемента 20. На выходе элемента 20 устанавливается I, которая поступает на входы триггера 25, элементы 12 и 21 и элемент 32. На выходе элемента 21 устанавливается 0м, который подается на К-входы триггера 25 и на вход элемента 31. Нулевой сигнал с выхода

элемента 31 группы элементов 4 поступает на элементы 13, 14 и 12 всех элементов 1 задержки второго столбца ЮЗ и блокирует работу счетчиков 24 . этих элементов 1 задержки.

Таким образом в решение оказались включены элементы 1 задержки первой строки. Суммарное время задержки сигнала составило Т 12 ед.

Единичный сигнал с выхода элемента 32 группы элементов 4 подается на вход S, счетчика 43 блока 6 управления и на вход S, счетчика 47 блока 8 счета. Счетчик 47 устанавливается (,So И). Счетчик 43 начинает операцию вычитания (S(S/2. 10). Одновременно 1 с выхода элемента 32 подается (сигнал 77) в блок сравнения и разрешает сравнение содержимых счетчика 47 и регистра 48 блока 8 счета, которые подаются в блок сравнения по шине 75. Содержимое счетчика 47 равно времени задержки сигнала, т.е. числу 12 (1100). В регистре 48 в режиме Ус тановка было записано максимальное число 15 (1111). Так как содержимое счетчика 47 меньше содержимого регистра 48, то. в блоке сравнения вырабатывается единичный сигнал, который поступает в блок 8 счета (сигнал 66) через контакт 52 ключа 7.на вход элемента 46. Нулевой сигнал с выхода 46 элемента подается на входы регистра 48. Комбинация 00 на входах S4S4 регистра 48 соответствует уста- .новке числа. Информация из счетчика 47 переписывается в регистр 48 через контакты 54, 56, 58 и 60 ключа 7.

Единичный сигнал 66 из блока сравнения поступает на С-входы триггеров 25 всех элементов 1 задержки МЭЗ и устанавливает их в состояния, соответствующие сигналам на входах J и К. В единичное состояние в данном случае устанавливаются триггеры 25 элементов 5 задержки первой строки МЭЗ. Выходы триггеров 25 через усилители 26 элементов 1 задержки сигналами 71, 72, 73, 74 подаются на пульт управления на соответствующие светодиоды.

Содержимое регистра 48 блока 8 счета поступает также в блок дешифрации (сигнал 75). Выход блока дешифрации соединен со световой индикацией пульта управления.

Счетчик 43 блока 6 управления при поступлении на его вход S( единичного

и

20

-25

сигнала с выхода элемента 32 группы элементов 4 работает в режиме вычитания. Как только содержимое счетчика

, 43 блока 6 управления станет равным нулю, на выходе элементов 35 и 36 установится 1, содержимое счетчика 44 увеличится на 1, т.к. на С-вход поступает единичный сигнал с выхода

10 элемента 35. Следовательно, единичный сигнал появляется на выходе дешифратора 76 блока 6 управления.

Единичный сигнал с выхода элемента 36 блока 6 управления устанавлива15 ет все элементы 1 задержки N33 в исходное состояние. На выходе элемента 32 группы элементов 4 устанавливается О. На входах счетчика 43 блока 6 управления устанавливается комбинация S,S4 01, соответствующая операции сложения. Как только содержимое счетчика 43 блока 6 управления станет

больше нуля, то на выходе элемента 35 появится О. Этот сигнал подается на вход 5% счетчика 43. Комбинация S,Sa 00 соответствует установке числа. В счетчике 43 устанавливается исходное число 14 (1110). На выходе элементов 35 и 36 устанавливается О, на выходе элемента 37 - 1. Этот единичный сигнал открывает элементы 39 и 40 блока 6 управления. Так как единичным выходом де1чифратора 76 является выход 1, то на выходе элемента 39 - О, на

35 выходе элемента 40 - 1. Таким образом управляющий сигнал подается на элемент 10 элемента 1 задержки второй строки первого столбца МЭЗ. Его работа аналогична работе описанного выше элемента 1 задержки первой строки первого столбца МЭЗ, за исключением того, что после появления на выходе счетчика 24 элемента 1 задержки второй строки первого столбца нулевого сигнала с выходов элемента 19 данного элемента задержки нулевой сигнал подается на вход элемента 34 и с его выхода поступает на элементы 13-15 обоих элементов 1 задержки второй

50 строки. Этим производится блокирование работы счетчиков 24 обоих элементов 1 задержки второй строки, что обеспечивает однократное включение затрат на разработку второго элемен55 та системы в решение.

Суммарная задержка управляющего сигнала счетчика 43 и 24 элемента 1

30

40

45

задержки второй строки первого столб- ца Т 2 + 4 6 ед.

Единичный сигнал с выхода элемента 20 элемента 1 задержки второй , строки первого столбца поступает на выход элемента 30 группы элементов 3 и с его выхода подается на все элементы 1 задержки второго столбца КЭЗ, которые начинают одновременную работу аналогично описанному. Счетчик 23 элемента 1 задержки первой строки второго столбца задержки задержит входной сигнал (с выхода элемента 30) на 3 такта вычитания и начнет работу счетчик .24,содержимое которого равно 5. Суммарное время задержки данного элемента составит 8 тактов вычитания. Счетчик 23 элемента 1 задержки второй строки второго столбца задер- жит второй сигнал на 5 тактов вычитания .

Однако так как работа счетчика 24 данного элемента 1 задержки блокирована, то нулевой выходной сигнал - счетчика 23 через элементы 11, 15 и 18 попадает на вход элемента 20-и на его выходе устанавливается 1. Таким образом, общее время задержки входного сигнала элементом 1 задерж- ки второй строки второго столбца .окажется равным 5 тактам вычитания. Так как счетчик 24 элемента 1 задержки первой строки второго столбца продолжает вычитание, то единичный сигнал с выхода элемента 20 элемента 1 задержки второй строки второго столбца МЭЩЗ подается на вход элемента 21, J-вход триггера 25, на вход элемента 12 и на вход элемента 32 группы эле- ментов 4. С выхода элемента 21 нулевой сигнал через элемент 31 группы элементов 4 поступает на элементы 12-14 элемента 1 задержки первой строки второго столбца МЭЗ и останав- ливает работу счетчика 24. На выходе элемента 20 данного элемента 1 задержки остается О. Таким образом, в решение включается элемент 1 задержки второй строки второго столбца МЭЗ.

Суммарное время задержки управляющего сигнала двумя элементами 1 задержки второй строки МЭЗ составило 2 + 4 + -5 U тактов вычитания. Соответственно, содержимое счетчика 47 блока 8 счета равно 12.

Единичный сигнал с выхода элемен- та 32 группы элементов 4 подается на вход S( счетчика 43 блока 6 управления, включая его в режим вычитания, и на вход S(| счетчика 47 блока 8 счета, останавливая счет. Одновременно этот же сигнал поступает в блок сравнения (сигнал 77), разрешая сравнение содержимого счетчика 47 и регистра 48 блока 8 счета. Так как в предыдущем цикле в регистр 48 было записано число 12, а содержимое счетчика 47 блока 8 счета равно 11, то в блоке сравнения вырабатывается единичный сигнал (сигнал 66), который через контакт 52 ключа 7 подается на элемент 46 блока 8 счета. Нуль с выхода элемента 46 подается на входы S4 и S4 регистра 48, устанавливая режим приемки числа. Из счетчика 47 в регистр 48 переписывается число 11. Одновременно сигнал 66 поступает на С-вход триггеров 25 всех элементов 1 задержки МЭЗ.

Триггеры 25 элементов 1 задержки, включенные в решение (в нашем примере триггеры 25 элементов 1 задержки второй строки), переключаются в единичное состояние. С их выхода единичные сигналы, усиленные элементом 26, подаются на матрицу светодиодов пульта управления.

Содержимое регистра 48 блока 8 счета подается в блок дешифрации (в данном случае число J1). Информация , с блока дешифрации подается на световую индикацию пульта управления.

Как было отмечено выше, счетчик 43 при поступлении на его вход единичного сигнала с элемента 32 группы элементов 4 начал работать на вычитание. Как только содержимое счетчика 43 станет равно нулю, на выходе элемента 35 блока 6 управления появляется единица, которая, поступая через контакт 50 ключа 7 на С-вход счетчика 44, увеличивает его содержимое на единицу, то есть равна 2 (двоичная форма 10).

На выходе Д счетчика 44 блока 6 управления появляется 1, которая, поступая на элемент 42 блока 6 управления, выключает формирователь 41, Устройство переходит в останов. С индикации пульта управления считывается информация об элементах, включенных в решение, и значение целевой функции, полученное в результате решения. Значение целевой функции -11, элементы, включенные в решение, - элементы 1 задержки второй строки МЭЗ.

Следовательно, для удовлетворения Заданных Лункций в раэрае атываемую систему необходимо включить второй элемент.

На фиг.5 обозначено: позицией 78 - Элементы памяти матрицы, 79 сумматоры матрицы, 80 - элементы памяти Группы, 81 - блок выбора минимального кода, 82 - триггеры матрицы, 83 - Элементы ИЛИ первой группы, 84 - элементы ИЛИ второй группы и 85 - вход щуска устройства.

Перед началом раб о ты обнуляют триг- еры 82, в элементы 80 памяти заносят йоды затрат на разработку М-го эле- t Мента системы (М 1,...,С, где С - количество элементов в системе), в Элементы 78 памяти заносят коды зат- рат на эксплуатацию М-го элемента пои, реализации К-й функции (К 1, .,.,Ф, где Ф - количество функций выполняемых системой). После подачи Сигнала уровня 1 на вход 85 пуска, устройство асинхронно выбирает минимальный с учетом затрат на разработку элемент матрицы затрат на зксплуата- йию, устанавливает в 1 соответствующий ему триггер 82 и исключает (блокирует выдачу информации элементами 78 и 80) затраты на разработку Элемента и затраты на эксплуатацию при реализации функции элемента.Пос ле завершения переходных процессовs установленные в Л триггеры 82 представляют решение задачи оптимизации Эатрат на разработку и эксплуатацию Системы.

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

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

0

5 о

5

0

элементов памяти, где С - количество исследуемых элементов, систем, Ф - количество функии$ выполняемых элементами систем, .матрицу из СхФ триггеров и первую группу из Ф элементов ИЛИ, причем выход К-го триггера (К J,..., Ф) М-й строки (М 1,...,С) матрицы подключены к М-му входу К-го элемента ИЛИ первой груп-- пы, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет решения задачи минимизации затрат на разработку и эксплуатацию элементов систем, в него введены матрица из сумматоров, группа из С элементов памяти, блок выбора минимального кода и вторая группа элементов ИЛИ, причем выход К-го элемента ИЛИ первой группы подключен к входам блокировки чтения всех элементов памяти К-го столбца

матрицы, выход К-го элемента памяти

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

75

;

с

s

D

1rJ

г

С

и

Zf

P

:

(.,

ЦТ

з

ч

«

Г

LS

-Й

fT -.Ј)

2

Т|Г

JiL i (

to

.,0,-я

ч

а 41

I s

3

и W

г

(Г

«

Ш

«

и

4Т М

тх-

«а

щ|

ТГ

9i«7ei g

Фие.Ј

Фие.З