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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (51)5 G 06 F 15 20

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

Н A BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4065206/24-24 (22) 08.05.86. (46) 15.02.90. Бюл. Р 6 (72) А.E. Рубцов, А.A. Поляков и Х.П. Самсонов (53) 681.333 (088.8) (56) Авторское свидетельство СССР

У 947871, кл, G 06 G 7/122, 1982.

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

У 1315993, кл. G 06 F 15/20, 1985. (54) УСТРОИСТВО ДЛЯ РЕШЕНИЯ ОПТИИИЗАЦИОННь1Х ЗАДАЧ (57) Изобретение относится к вычислительной технике и может быть использовано для решения многомерных оптимизационных задач, Целью изобретения

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

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

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

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

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

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

„„ЯО„„154 4f A l

2 является расширение функциональных возможностей устройства за счет решения задачи минимизации затрат на разработку и эксплуатацию элементов системы. С этой целью перед началом работы задают затраты на разработку элементов системы и затраты на эксплуатацию 11-го элемента (M = I,...,С, где С вЂ” количество элементов в системе) при реализации К-й функции (К

1,...,, где Ф вЂ” количество функций, выполняемых системой) . После пуска устройство включает в систему те элементы, затраты на эксплуатацию которых минимальны с учетом затрат на разработку каждого элемента системы.

5 ип.

10 и 11, элемента KIH-HE 12, элементов И 13 и 14, элементов ИЛИ-HF. 15 —, 17, элемента И-HE 18, элемента ИЛИ

19, элементов И 20 и 21, регистра 22, счетчиков 23 и 24, триггера 25. и усилителя 26.

Группу регистров 2 образуют регистры 27 и 28, первую группу элементов И-ИЛИ 3 — элемент И 29 и элемент

ИЛИ Зо, вторую группу элементов 4 элементы И 31 и 32, группу элементов

И 5 — элементы И 33 и 34.

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

5434 !6

К>пюч 7 включает в себя группы контактов 49 — .62, 1<роме того на функциональной схеме обозначено. позицией 63 — вход уП5 равления регистром 22 элемента 1 задержки первой строки второго столбца матрицы элементов задержки, 64 - информационные входы регистров 22 всех элементов задержки и регистров 27 и 28 группы регистров 2, 65 — вход управления регистром 22 элемента 1 задержки первой строки первого столбца матрицы элементов задержки, 66

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

47 и регистра 48 блока 8 счета, 76 — дешифратор, .77 †.выходной сигнал элемента 32.

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

Описание работы устройства покажем на числовом примере. Имеем систему из двух элементов, затраты на разработку и производство которых соответственно С, = 5 единиц стоимости и С o< = 4 единицы стоимости (ед,ст.), Заданы дв е функции, ко то рые должна решать система. Затраты на удовлетворение первым элементом первой требуемой Аункции С „, = 4 ед.ст., второй требуемой функции С = 3 ед.ст. Зат1 раты на удовлетворение вторым элемен55 том пе рв ой требуемой д>унк ции С вЂ” 2 ед.ст., второй С = 5 ед.ст.

Требуется определить набор элементов так, чтобы разрабатываемая-система могла решать все возложенные на нее функции > а велич ина с умма рных з а трат на разработку системы, ее производство и эксплуатацию бьша минимальной, Для решения задачи в режиме Устаtt новка в регистр 22 элемента 1 задержки первой строки первого столбца матрицы элементов задержки заносится число 4, в регистр 28 элемента 1 задержки первой строки второго столбца— число 3, в регистр 22 элемента 1 задержки второй строки первого столбца — число 2, в регистр 2 элемента 1 задержки второй строки второго столбца — число 5, в регистр 27 группы регистров 2 — ч исло 5, в рег ис тр 28 группы регистров 23 — число 4. В положении ключа 7 "Установка" на информационные входь. регистра 48 блока 8 счета поступают единичные сигналы и содержимое регистра принимает максимальное значение. Счетчик 47 блока 8 счета устанавливается в "0". Счетчик

43 блока 6 управления устанавливается в состояние "!1!0" счетчик 44 — в состояние "000tf. Единичный сигнал с выхода элемента 36 блока. 6 управления подается на элемент 9 всех элементов

1 задержки. По этому сигналу счетчик

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

22 элементов 1 задержки, а счетчики

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

При переключении ключа 7 в положеtI ft ние Пуск информационные входы регистра 48 блока 8 счета подключаются к выходам счетчика 47. Нулевой сигнал с контакта 62 ключа 7 подается на элементы 36 и 38 блока 6 управления °

Вход С счетчика 44 блока 6 управления отключается от выхода формирователя

41 и подключается к выходу элемента

35, С выхода элемента 38 ".1" подается на вход Б счетчика 44, разрешая работу счетчика на сложение ° Так как счетчик 43 блока 6 управления устанавливается в "1110", то на выходе элемента 35 имеется "0", на выходе элемента 36 также "О". Единичный сигнал с выхода элемента 37 открывает элементы .39 и 40. Так как счетчик 44

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

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

36 блока 6 управления поступает на элементы 9, )6 и 17 всех элементов задержки и одновременно запускает счетчик 47 блока 8 счета. Кдиничный сигнал с выхода элемента 39 блока 6 управления подается на вход элемента

1 0 элемента 11 задержки первой строки первого столбца матрицы элементов задержки. Тем самым этот элемент задержки как бы включается.

На входах S< и S< счетчика 23 элемента 1 задержки первой строки первого столбца устанавливается комбинация "lO" так как при установке в счетчик записано число 4 {в двоичном виде l00), на выходе элемента ll ииеется "1", Комбинация S

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

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

11 элемента 1 задержки первой строки .первого столбца матрицы элементов задержки (ИЭЗ) поступает также на элементы 14 и 15 данного элемента 1 задержки. Так как после установки на выходе элементов 29 и 33 имеется "!", то на выходе элемента 13 данного элемента 1 задержки присутствует "1, на выходах элементов 14 и 15 — "0". На входы Б S счетчика 24 данного элемента 1 задержки поступает комбинация

"10". Счетчик начинает работу на вычитание. Так как по условию примера в него записано число 5 (в двоичном виде 101), то входной сигнал задерживается еше на 5 тактов вычитания.

Как только содержимое счетчика станет равно нулю, на выходе элемента 19 элемента 1 задержки первой

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

:-,ервой строки МЭЗ. Этим обеспечивается однократное включение затрат на разработку x-ro средства при реализации алгоритма.

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

19 олемента 1 задержки первой строки первого столбца МЭЗ подается также иа вход элемента 20 данного элемента .1 задержки, инвертируется и поступает на вход элемента 21, на Л-вход триггера 25 данного элемента 1 задержки и на вход элемента 30 группы элементов 3. С выхода элемента 21 нулевой сигнал поступает на элемент 29 группы элементов 3 и с выхода элемента 29

25 подается на элементы 12 — 14 всех элементов 1 задержки первого столбца

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

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

1 задержки второго cTÎëáöa МЭЗ начинают одновременно операцию вычитания.

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

Следовательно, нулевой сигнал на выходе счетчика 23 элемента 1 задержки первой строки второго столбца по4> явится раньше. Так как работа счетчика 24 элемента 1 задержки первой строки второго столбца заблокирована нулевым сигналом с выхода элемента

33, то нулевой сигнал с выхода элемента 11 данного элемента 1 задержки, дважды проинвертированный элементами

15 и 18, поступает на вход элемента

20. На выходе элемента 20 устанавливается "1", которая поступает на вхо5 ды триггера 25, элементы 12 и 21 и элемент 32. На выходе элемента 21 устанавливается "O", который подается на К-входы триггера 25 и на вход эле-. мента 31 . Нулевой сигнал с выхода!

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

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

Единичный сигнал с выхода элемента 32 группы элементов 4 подается на вход S счетчика 43 блока 6 управления и на вход S< счетчика 47 блока 8 счета. Счетч ик 47 ус танавливается (S< S 11) . Счетчик 43 начинает oneрап вычитания (S! S = 10) . Одновременно "1" с выхода элемента 32 подается (сигнал 77) в блок сравнения и разрешает сравнение содержимых счет-. 20 чика 47 и регистра 48 блока 8 счета, которые подаются в блок сравнения по шине 75. Содержимое счетчика 47 равно времени задержки сигнала, т.е. числу

12 (1100). В регистре 48 в режиме "Ус-25 тановка было записано максимальное число 15 (1111). Так как содержимое счетчика 47 меньше содержимого регистра 48, то в блоке сравнения вырабатывается единичный сигнал, который 30 поступает в блок 8 счета (сигнал бб) через контакт 52 ключа 7,на вход элемента 46. Нулевой сигнал с выхода 46 элемента подается на входы S< S < регистра 48. Комбинация "00" на входах

S S регистра 48 соответствует уста,новке числа. Информация из счетчика

47 переписывается в регистр 48 через контакты 54, 56, 58 и 60 ключа 7, 40

Единичный сигнал 66 иэ блока сравнения поступает на С-входы триггеров

25 всех элементов l задержки ИЭЗ и устанавливает их в состояния, соответствующие сигналам на входах J и К. 45

В единичное состояние в данном случае устанавливаются триггеры 25 элементов

5 задержки первой строки М33. Выходы триггеров 25 через усилители 26 элементов задержки сигналами 71, 72, 73, 74 подаются на пульт управления на соответствующие светодиоды.

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

Счетчик 43 блока 6 управления при поступлении на его вход S! единичного сигнала с выхода элемента 32 группы элементов 4 работает в режиме вычитания, Как только содержимое счетчика

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

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

Единичный сигнал с выхода элемента 36 блока 6 управления устанавливает все элементы 1 задержки РЭЗ в исходное состояние. На выходе элемента

32 группы элементов 4 устанавливается

0 . На входах S< S счетчика 43 блока

6 управления устанавливается комбинация S S< = 01, соответствующая операции сложения. Как только содержимое счетчика 43 блока 6 управления станет больше нуля, то на. выхоце элемента 35 появится "0". Этот сигнал подается на вход S< счетчика 43, Комбинация < S< =

00 соответствует устачовке числа ° В счетчике 43 устанавливается исходное число !4 (!!10). На выходе элементов

35 и 36 устанавливается "0", иа выходе элемента 37 — "!". Этот единичный сигнал открывает элементы 39 и 40 блока б управления. Так как единичным выходом дешийратора 76 является выход

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

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

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

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

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

Однако так как работа счетчика 24 данного элемента задержки блокирована, то нулевой выходной сигнал счетчика 23 через элементы 11, 15 и !8 попадает на вход элемента 20-и на его выходе устанавливается l".

Таким образом„ общее время задержки входного сигнала элементом 1 задерж- 30 ки второй строки второго столбца .окажется равным 5 тактам вычитания. Так как счетчик 24 элемента 1 задержки первой строки второго столбца продолжает вычитание, то единичный сигнал с выхода элемента 20 элемента 1 задержки второй строки второго столбца

МЭЕ(З подается на вход элемента 21, о

J-вход триггера 25, на вход элемента

12 и на вход элемента 32 группы эле- 40 ментов 4, С выхода элемента 21 нулевой сигнал через элемент 31 группы элементов 4 поступает на элементы

12 - 14 элемента задержки первой строки второго столбца МЭЗ и останав- 45 ливает работу счетчика 24. На выходе элемента 20 данного элемента 1 задержки остается "0", Таким образом, в решение включается элемент 1 задержки второй строки второго столбца МЭЗ. 50

Суммарное время задержки управляю" щего сигнала двумя элементами 1 задержки второй строки МЭЗ составило

2 + 4 + 5 = 11 тактов вычитания, Соответственно, содержимое счетчика 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 подается на входы S< и Я< регистра

48, устанаЬливая режим приемки числа.

Из счетчика 47 в регистр 48 переписывается число 11. Одновременно сигнал

66 поступает на С-вход триггеров 25 всех элементов 1 задержки 1ЭЗ .

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

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

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

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

На выходе Р< счетчика 44 блока 6 управления появляется 1, которая, поступая на элемент 42 блока 6 управления, выключает формирователь 41.

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

МЭЗ, 154341б

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

На фиг.5 обозначено: позицией 78флементы памяти матрицы, 79 — сумматоры матрицы 80 — элементы памяти

Р

10 группы, 81 - блок выбора минимального

Мода, 82 - триггеры матрицы, 83 флементы ИЛИ первой группы, 84 — элементы ИЛИ второй группы и 85 — вход пуска устройства.

Ci 15

- Перед началом работы обнуляют триг еры 32, в элементы 80 памяти заносятМоды затрат íà разработку M-го элемента системы (М = 1, ° . °,С, где С— количество элементов в. системе), в

20 элементы 78 памяти заносят коды зат рат на эксплуатацво N-го элемента ищ реализации К-й функции (К = 1, . ° .,Ф, где Ф вЂ” количество функций 25 выполняемых системой) ° После подачи сигнала уровня "1" на вход 85 пуска, устройство асинхронно выбирает минимальный с учетом затрат на разработку элемент матрицы затрат на эксплуатаФпо, устанавливает в "1" соответствующий ему триггер 82 и нскюпочает (блокирует вьдачу информации элементами 78 и 80) затраты на разработку

Элемента и затраты на эксплуатацию

O 35 при реализации функции элемента.После завершения переходных процессов, установленные в "1" триггеры 82 представляют решение задачи оптимизации затрат на разработку и эксплуатацию 40

<".истемы.

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

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

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

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

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

N-й строки матрицы, выход которого подключен. к входам блокировки чтения всех элементов памяти I(-ro столбца матрицы, выход К-ro элемента памяти

M-й строки матрицы подкгпочен к входу первого слагаемого К-го сумматора

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

К-го триггера М-й строки матрицы, выход которого подключен,к К-му входу

M-го элемента ИЛИ второй группы, выход которого подключен к входу блокировки чтения M-ro элемента памяти. группы, выход которого подключен к входам вторых слагаемых всех сумматоров N-й строки матрицы, вход опроса блока выбора максимального кода под ключен к входу пуска устройства, 15434 j5

Фие.1

15434 ) Ь

15 i 34 16

1543416 о е е

Э

° Ф

9 ° ° °

° ° °

° ° °

° ° Ф ° . ° ° ° °

4 ° 1 °

° е

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

Редактор Л.Пчолинская Техред Л. Сердшкова Корректор А.Обручар

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

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

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

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