Устройство для решения двухкритериальных задач нелинейного программирования
Изобретение относится к обласчн вычислительной техники и может быть использовано при решении задач нелинейного программирования в случаях, когда оптимизация необходима одновременно по двум критериям. Изобретение позволяет повысить быстродействие
СОЮЗ СОБЕТСНИК
СОЦИАЛИСТИЧЕСНИК
РЕСПУБЛИК (l9) (И1 (5114 С 06 G 7 122
qrtiОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А ВТОРСКОМ .Ф СВИДЕТЕЛЬСТВУ
ГОСУДАРСТНЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3836674/24-24 (22) 07.01.85 (46) 23. 08. 86. Бкл. У 3 1 (72) С. В.Антонов, А.А. Бурба, А. B.Äâîрак, A,А.Кириченко и О.А.Сандалов (53) 68 1.333(088.8) (56) Авторское свидетельство CCCP . У 410409, кл. С 06 С 7/122, 1971.
Авторское свидетельство СССР
11 480090, кл. G 06 Г 7/122, 1974. (54) УСТРОЙСТВО ДЛЯ РЕШГНИЯ ДВУХКРИТЕ1 ИАЛВНЬ1Х ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАМИИР О ВА НИЯ (57) Изобретение относится к облас и вы 1ислительной техники и может быть использовано при решении задач нелинейного программирования в случаях, когда оптимизация необходима одновременно по двум критериям. Изобретение позволяет повысить быстродействие
12 72795
Г, (Х) 1
)7; Х;, (1) 30
F„(X) ct х, F (Х ) ) F,(X )
Г (Х,) F,,(Х ) (2) 4О за счет возможности выбора оптимального варианта, одновременно учитывать требования двух критериев. Устройство содержит блок 1 выбора симплекса, блок 2 вычисления координат заменяющей вершины, блок 3 вычисления координат заменяемой вершины, блок 4 задания критериев оптимизации, элементы памяти 5, 8, 13, 15, 19, блок
Изобретение относится к вычислит JII>)loA технике и может бытт использовано при решении задач нелинейного программирования н случаях, кагдл оптимизация необходима одновременно 5 па двум критериям, Цель изобретения — повышение быстPОДЕЙСТI31IЯ °
Выбор оптим..)ттьногс 13лрианта ао уществляется из области условно оптимлчьных реш-ний (облл» тт, Парето) аб.)лс Ги Р злдлт3лсHОЙ агрлнтlчениkt) tn х с-(Г;, .r; f, (i = t, ..., n), где
n — чист)о аптимиэ)Груемых плраметров.
Задачи, сформулированные как многакрптерплльные, требу)ог прп своем решенш: поиска экстремума векторного ф г — ъ ., кригер)тя вида Р Х) = (Г,(X), Г,(Х)), где-. Г, (Х) =. Гт (Х), Е, (Х) = ?,(Х) сост,3t»Jts)»n e векторно) о критерия.
Внд функций Гт (Х) и Г (Х) опреде.))яе3. т Я СнайСтт»ЛМП ИССЛЕДУЕМОЙ СИСТЕМЫ, 0цнзко на прлктике члсто встречанп ся, квлдратичные зависимости критериев от параметров (например, стоимость и 2 эффективность) вида
В дальнейшем экстремумом считаегся максимум значения критерия Е (X)
= (Е)(Х), Е„ (X)$ Решение Х, lip дпочтительнее Х< если одно иэ нерлветтстн системы
6 вычисления градиента, блок .7 вычисления координат центра сиплекса, блок
9 индикации, блок 10 вычисления координат сдвига центра симплекса, блок
11 сравнения, элемент НЕ 12, блок 14 вычисления локального градиента, ключ 16, uJioK 17 выбора шага поиска, блок 18 усилителей, блок 20 нормировки градиента. 11 ил. будет строгим. При этом Х, и Х, нлзывлют срлвттттгттт".1 по векторному критерию. Если в системе (2) неравенства различттых знаков () и (), то
Х, и Х несравнимы.
Цель оптимизации — выделение клас са Парето (оптигллльных решет)и)1), т.е. области Р„, состоящей из попарно несрат»нимых между собой векторов значений параметрон Х в облас.и Р.
Поиск точки, )цтн)тгтц3)еж,»щей области 1?„, нлчинаегт я из )траизвальной та Iки Л а, 3 а ° °,;t 33,r» ка rop.эll on
n7 ре)геля)отся напрлвттс ния во-»растлгнтя — Ъ вЂ” Ъ - -т
1 ., для обеих функцlill Е, (X) и
? (Х? а Есл)1 эти нат113лт)лен)lя trpoztrno
itr»1o+frFI, то тtnirttnlr точка прннл)тпсжит !
)t »: з< 3 Ir Dp, c:IH ik:n c $ l»tE. <-. TI3 y ). T Itnn»
=- -Ф равнение 1 с )от 7рьм ? и 1 сосо г тавлягот острый угол, то движение осущестн:гнется и )нп;рлвлении 1 . Тло
r.kf ..r образам, злдачл состоит в опреде 3»ii)fH iIn)lpl3I3JIoftiIя наибОльшега 13оп
Ф -. Ф рлстлння функции Г, (Х) и Г (Х) . Нлпр;) n тен)тя Ф, и 1, совпадают с нлттравленияии градиентов соответству)ощих фуttr -о 1 в окрестностях т очки Х „. Для этого :.Округ точки Х строигся мнага)» 1 р Ift)rlfK (cHMHJICKc) )тенJJIQBol 0 обьгт».л, достаточно млла) а размера, имеюттий (и + 1) вершину-. Длина ребра симплекса равна H IH близка к заранее ттыб17а ннОЙ P oëlr 1 )не ?) ЛОиска Координаты k-и r»c ptttkrtiri симплекса (k == 1, ..., n + 1) образуются путем 1252795 = „ а,, ;„, (7) г а„, + аг +. + <г где /а, / аг г! + а + ...+ гг + h, х, ° у хп< an < хг аг + l пг п1 1-я вершина х „= а, = аг, ° . 2 я Вершина х а ! + h, (3) 10! 20 (9) T ° E- ° 7 а1! 1а<( <и <и 6п агг у 2 /аг! а 1 г I 1г ! ° ° ° < а,1 55 г!
I аг< г х . 6, Jt х;, g (15) смещения k-й координаты начальной точки на lnal. h: пя вершинах„, =а,, х =а гп х„„=а„+h, (и + 1)-я вершина х (и „> = а,, ХII(n« = аg< ° ° °, х„„„= а„+ h. В каждой из вершин определяются значения компонент векторного критерия Г (Х), Г Ä (X) . По этим значениям 1<< строится линейная локальная аппроксимация функции. Коэффициенты ищутся из условия равенства аппроксимации в вершинах симплекса значениям критерия, т.е. путем решения системы алгебраических уравнений Fn =а х<< +à х + ... + 11 1г г< п< арпб! Г, =a„x«+a х, + .. ° + (4) ° ° ° ° ° ° 1 ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° 4 ° ° ° ° ° ° 1<<б 1! 1п б! 1г г пб + ... + а х + а <п ПП б! 1пб < относительно а Лналогичная система для критерия F,(Х). Найденные коэффициенты аппроксимации а дают локальное направление градиента функции. В силу малости размеров симплекса можно считать, что внутри него градиент функции F достаточно xopoIilo описывается найденным приближением а . Это направление приписывается одной точке центру симплекса
Таким образом, направления f u возрастания функций F, и Е определены„ Существование направления, обеспечивающего улучшение обеих компонент векторного показателя, эквивалентно существованию вектора удовлетворяющего уравнению ta E + 1 (8) Признаком того, что точка (центр симплекса) принадлежит множеству условно оптимальных решений, является выполнение условия /c,/ где /1) / ) (1O) заданная точность вычисления, (<-.l = . <,, " <...
Если полученная точка Яд не является Парето-оптимальной, то строится новый симплекс. Он получается из старого путем замены одной из вершин другой, координаты которой соответствуют сдвигу центра симплекса Б в направлении вектора t «a вели35 чину шага 1! (13) Заменяемая вершина соответствует мин!1мальному из скалярных произведе40 ний (X„— S ) Х, (k = 1, ..., n + 1), где 1 — номер заменяемой B< plIMHbl Прежде, чем перейти к повторному циклу поиска условно оптималт,ных решений, проверяется выполнение ограничешш для новой вер!ш1 ы с 5 х =f> +01h, прих3;Й; x, g -01h, прих,;)д, (16) после чего цикл решения повторяется. Для увеличения скорости сходимости !О в случае сохранения направления градиента на последовательных шагах шаг поиска увеличивается, при существенном изменении направления- уменьшается, т.е. t5 (17) h =h ° k. JiC 7 где и — длина предьгдущего шага, k — коэффициент усиления. jIC при с 0 (к>1) (20 p, IIpII с < 0 (lp/ с 1), с Г„ t„„,,f „Г, (19) 25 + ОП 0 ОГ ОП 7 ное направление на предыдущем шаге. ° Если найденная точка S принадлео жит Вц, то она запоминается (икди цируется), а весь симплекс сдвигается на величину шага h в направлении S(, = S +hg,, (20) ,г,б где S — - новая точка центра симплек о са. Иа фиг. 1 представлена блок-схема устройства для решения двухкрите- 4О риальных задач нелинейного программировапия, IIa фиг. 2 — функциональная схема блока усилителей, на фиг. 3 — функциональная схема блока вычисления координат сдвига симплек- 4 са, на фиг. 4 — функциональная схема блока вычисления координат центра симплекса; на фиг. 5 — функциональная схема блока задания критериев оптимизации (один иэ возможных вариантов), на фиг. 6 — функциональная схема блока выбора шага поиска, на фнг. 7 — функциональная схема блока вычисления локального градиента! «а фиг. 8 — функциональная схе- 55 гла блока нормировки градиента; на фнг. 9 — функциональная схема блока вычисления координат заменяемой верS 1252 В случае нарушения одного иэ неравенств системы (15) значение j-й координаты центра симплекса определяется из выражений соответственно 795 а шины, на фиг. 10 — функциональная схема блока выбора симплекса; на фиг. 11 — функциональная схема блока вычисления координат заменяющей вершины. Устройство содержит блок 1 выбора симплекса, блок 2 вычисления координат заменяющей вершины, блок 3 вычисления координат заменяемой вершины, блок 4 задания критериев оптимизации, первый элемент 5 памяти, блок 6 вычисления градиента, блок 7 вычисления координат центра симплекса, второй элемент 8 памяти, блок 9 индикации, блок 10 вычисления координат сдвига симплекса, блок !1 сравнения, элемент НЕ 12, третий элемент 13 памяти, блок 14 вычисления локального градиента, четвертый элемент 15 памяти, ключ 16, блок 17 выбора шага поиска, блок 18 усилителей, пятый элемент 19 памяти и блок ?О нормировки градиента. Блок 18 усилителей содержнг пороговый элемент 21, первый элемент 22 памяти, элемент HE 23, второй элемент 24 памяти и умножитель 25, Блок 10 вычисления координат сдвига симплекса содержит группу 26 умножителей и группу 27 сумматоров. Блок 7 вычисления координат центра симплекса содержит группу 28 сумма1 торов, делитель 29, элемент 30 памяти, генератор 31 синхроимпульсов. Блок 4 задания критериев оптимизации содержит группу 32 квадраторов, первую группу 33 умножителей, вторую группу 34 умножителей, первую группу 35 сумматоров, первый элемент 36 памяти, генератор 37 синхроимпульсов, второй злемект 38 памяти и вторую группу 39 сумматоров. Блок 17 выбора шага поиска содержит первый ключ 40, второй ключ 41, элемент HE 42, пороговый элемент 43, инвертор 44, группу 45 сумматоров, группу 46 умножителей. ! Блок 14 вычисления локального градиента содержит первую группу 47 сумматоров, группу 48 квадраторов, вторую группу 49 сумматоров, группу 50 извлечения квадратного корня, первый элемент 51 памяти, делитель 52, генератор 53 синхроимпульсов и второ элемент 54 памяти. Блок 20 нормировки градиента содержит группу 55 квадраторов, первый элемент 56 памяти, группу 57 сумматоров, элемент 58 из,влечения квадратного корня, группу 59 1252795 делителей, второй элемент 60 памяти и генератор 61 синхроимпульсов. Блок 3 вычисления координат. заменяемой вершины содержит группу 62 вычитателей, группу 63 умножителей, группу 64 сумматоров, первый 65 и второй 66 ключи, коммутатор 67, первую группу 68 элементов памяти, первый генератор 69 синхроимпульсов, группу 70 схем сравнения, первый элемент 71 памяти, группу 72 ключей, первый элемент ИЛИ 73, вторую группу 74 элементов памяти, второй генератор 75 синхроимпульсов, первый элемент НЕ 76, группу элементов 77 сравнения, второй 15 элемент 78 памяти, второй элемент ИЛИ 79, второй элемент НЕ 80. Блок выбора симплекса содержит группу 81 сумматоров, первую группу 82 элементов памяти, генератор 83 синхроимпульсов, группу 84 ключей, группу 85 схем сравнения и вторую группу 86 элементов памяти. Блок 2 вычисления координат заменяющей вершины содержит группу 87 умножителей, первую группу 88 сумматоров, первую группу 89 ключей, первую группу 90 схем сравнения, первую гру11пу 91 элементов НЕ, вторую группу 92 ключей, вторую группу 93 сумматоров, элементы 94 памяти, умножитель 95, группу 96 вычитателей, генератор 97 синхроимпульсов, третью группу 98 ключей, вторую группу 99 схем сравнения, вторую группу 100 элементов HE и четвертую группу 10 1 35 ключей. Устройство работает следующим об1зазом. Начальные значения вор«1ин симплекса а,, а,, ..., а „ и шаг поиска z < Ь подаются на первый и второй входы блока 1 выбора симплекса. Группа 81 сумматоров оценивает вершины симплекса по формулам (3), причем значения вери!1113 накапл<1ваются в соот вот- 4 ствующих элементах памяти группь. 82. Затем зна !ения каждо!< верш1<ны в1,1даются rlo сигналу n r ге11ератора 83 синхроимпульсов последовательно на выход блока 1 выбора симпз1<зкса и, следовательно, на первые входы блока 4 задания критериев оптимизаш!и, первого элемента 5 памяти, блока 6 вычисления градиента и блока 7 вычисления координат центра симплекса, . На второй и третий входы блока 4 подаются с входа устройства з1111чения постоянных h; и d;. Значения вершины симплекса х возводятся в квад1< рат группой 32 квадраторов, а затем засыпаются на первую 33 и вторую 34 группы умножителей. Блоки 33 и 39, а также блоки 34 и 35 определяют j-e составляющие критериев в соответствии с формула<си (1), которые накапливаются соответственно во втором элементе 38 памяти и первом элементе 36 памяти. После накопления всех (и + 1) составляюних по сигналам от генератора 37 синхроимпульсов величины критериев F (X) и F (Х) подаются соответственно на второй и третий входы блока 6 вычисления градиента. Блок 6 осуществляет решение сист:-..«,1 л1!нейпых алгебраических уравнен 1 нсэс1!те!11 но величины а . Напряжения, соответствующие величинам а, и а и характеризующие локальные направлен!!л< градиентов функций Р! (Х) и Г (Х) засы11аются на пЕрвый и второй входы блока 20 нормировки градиента. сос1а<зляющие вектора а подаются на 1 группу 55 квадраторов, которые совместно с группой 57 сумматоро1з и э:Ielieiiтов 58 извлечения квадратного кс<рня оценивают модуль / а / по формуле (7) . Эта величина засылается на !<ход 13ервого элемента 56 памяти, с «шкода которогб ио сигналу от генератора 61 синхроимпульсов значение модуля поступает на первые вхс ды гру<1пы 5Ч делителей. Иа вторые входы грy»III 59 подаются составляющие вектср-,,сэ<. Группа 59 осуществляет норм
II,l.-<ра«л.1ет нормированные оставляющие ца группу входов второго элемента 60 памяти. СС ОтС<13ПЛ1<11тИЕ ВЕ«тОРа Сзг ЗаСЫЛаштсч нс3 груп 1у входов первого элемента 56 памят1<, с группы выходов которого с «и подаютc51 1<а !!ход<-.1 группы 55 квадраторов, Затем работ» групп 55-59 происходит так жс, как и при нормиУ .h рслэке а < . Вектор 1 нормнрованнь1х составля,c,lrliê нос.ryII;Ieò на rlepIII:III Олока 14 выч11сз<с:111!я 3!О «аз<«ного --Ъ градиента, а ве«тор Г, — на второй вход бло«а 14 и третий ьход блока 10 в ы 1! 1 с. . 1 е 11! 1 Я «О 0 P 3 11 I I I л т с, 1 II I I г 11 с 1 "! I I л Р к с а ° Ф !, o c т 1 сз. 1 я 1<1 11 131 Р «с к 1 <э р сз 11 V i I 1 л о» г z3а1с<тcÿ Hа лep1311е 11 в 1 с)рьlс (<хо, 111 пер 1252 9 вой группы 47 сумматоров блока 14 вычисления локального градиента, а составляющие f< поступают также на группу входов второго элемента 54 памяти. Блок 47 оценивает суммарное 5 направление в соответствии с формулой (8). Составляющие вектора 1 „ засылаются на входы четвертого элемента 15 памяти и ключа 16 устройств;, а также на входы группы 48 квадраторов блока 14, группы 48-50 определяют модуль вектора К по формуле (11), который подается на первый вход первого элемента 51 памяти. С группы выходов второго элемента 54 памяти составляющие вектора Д, по сигналу от генератора 53 синхроимпульсов засыпаются на входы группы 48> квадраторов. Группы 48-50 определяют модуль вектора 1>, по формуле 20 (12), который засылается на первый вход первого элемента 51 памяти, По сигналу генератора 53 синхроимпульсов величины (1 и / 7, (направляют,ся на первый и второй входы делителя 52, который оценивает точность g no формуле (10). Величина Ь поступает на второй вход блока 11 сравнения устройства, на первый вход которого с входа устройства подается значение 30 заданной точности вычисления C . .В блоке 11 осуществляется проверка выполнения условия (9) . Если это условие не соблюдается, т.е. тт Е, то на выходе блока 11 сравнения сигнал будет отсутствовать, а на выходе элемента HE 12 появится сигнал, который будет управляющим для первого элемента 5 памяти, ключа 16 и пятого элемента 19 памяти. Тог- 4р да величина F через ключ 16 поступает на первые входы блока 2 вычисления координат заменяющей вершины, блока 3 вычисления координат заменяемой вершины и блока 17 выбора шага попс- 4 ка. Величина T поступает на третий вход блока 17 состанллющтте х " верУ 1) шин симплекса — на третий вход блока ф 3, а центр сттмттлекса S — с первого выхода первого элемента 5 памяти на четвертый вход блока 2 и второй вход блока 3.. Центр симплекса Я„ поступает на второй вход блока 5 с выхода блока 7 вычисления координат центра симп- 55 лекса. Последтптй осуществляет оценку i-й составлятощей Я, центра сими лекса в соответствии с формулой (5) 795 при помощи группы 28 сумматоров и делителя 29 (везтичитттт и + 1 на второй вход делителя подается с входа устройства). После накопления в эле менте 30 памяти составллтощпе вектора S„ no сигналу от генератора 31 синхроимпульсов подаются на выход блока 7 вычисления координат центра симплекса. Блок 2 вычисления координат заменяющей вертпины оценивает новьпт симплекс в соответствии с формулой (13) при помощи группы 87 умножителей и первой группы 88 сумматоров, а затем осутцествллется проверка выпо шения ттеравенсттта (15) . С э готт целью составляющие координаты заме. плющей вершины си" IIIJIcllc» засыпаются на первые входы пертзой группы 90 схем сравттения и первой группы 89 ключей. Нн тзторые ихлдт.т группы 90 схем сравнения с ихода устройства подаютсл нижние границы Г„, по каждой составляющей (переменной) заменяютчей вершины симплекса. Если соб.ттодается для k — и составляющей Iacp;a!ee нер»иепстио (1 )) то на выходе соответствуощей схемы сравнения появляетсл сигнал, Ко T0pEIEI открывает соотиетствуютттттй ключ группы 89, » x, ттоступает тта вторую группу 99 схетт сравнения длл сопостатзления с верхней граттттцетт g„. Если х t то на ттыходе k и схсмтт срнтзненил грунтты 90 сигнала не буде г, а на nl Ixnде k-ãî элемента НГ грушть> 91 полнится сигнал, который откроет k-й клич группы 92 и f поступает в сотттветстиуют>ттттт суттттатор группы 93. На второй вход этого сумматора с выхода умножитечя 95 поступает величина О, 11т (наличие одного входа блока 95 обьлсцяется TpEI что един из сомножителей — Iloc тоянное число) . Группой 93 сумматоров определяется k ë состаилятощая заменяющей иертштны по (верхней) формуле (16), которая затем подается тта первую группу входов эчемента 94 пстмл Гll . Сопоставление хо„c веРхним УРовттем 8,„ осуществляется при помощи групп 99-101 аналогично. Ес:ш иьпточняется ттттжттее неравенство (1 5), х„. ок ттоступает на третью группу входов :элемента пEIII!Iти 9 . В случае, когда х „„> 8 тн,тчислл TcsI значение переЗК У меняой по IIIw!Icl формуле (16) при 1252 11 помощи группы 96 вычитателей и подается на вторую rpynny входов элемен-I та памяти 94, После завершения.сравнений и вычислений по сигналу с блока 97 синхронизации составляющие новой вершины Х„ засылаются на третий ноа вход блока 1 выбора симплекса устройства. Для того, чтобы заменить вершину в блоке 1, необходимо определить ее номер. Эту задачу решает блок 3 вычисления координаты заменяемой вершины. С этой целью при помощи группы 62 вычитателей группы 63 умножитеУ 15 лей и группы 64 сумматоров определяется по формуле (14) величина с; для каждой вершины, которая подается через коммутатор 67 на первые входы первой группы 68 э.пементов памяти и 20 первые входы первого ключа 65 и второго ключа 66. Вначале сигнал на третьем выходе второго генератора 75 синхронмпульсов отсутствует, поэтому второй ключ бб закрыт, а первый 25 ключ 65 открыт, поскольку на выходе первого элемента HE 76 сигнал будет. Следовательно, на первый вход блока 77 сравнения поступает с для первой вершины. Затем на третьем выходе генератора 75 поянляется сигнал, который открывает второй ключ 66 и закры. вает первый ключ 65. Таким образом, величина с; для второй вершины симплекса поступает на второй вход группы 77 элементов сравнения. 35 Группа 77 элементов сравнения работает следующим образом. Если с I первом входе меньше, чем на втором, то на выходе группы 77 появляется сигнал, когда с на первом входе 40 равно или больше, чем на втором, то на выходе группы 77 сигнал отсутствует. Такая работа группы 77 элементов сравнения, а также наличие первого элемента НЕ 80, второго элемента 78 памяти и второго элемента И!И 79 позволяет зафиксировать в элементе 71 памяти наименьшее значенпе с.;„,, которое соответствует вер < мци шине спмплекса. Это значение подает- о ся по сигналу генератора 75 синхропмпульсов на вторые входы второй группы 70 схем сравнения. На первые входы группы 70 с выходов первой группы 68 элементов памяти по сигна- Ы лу первого генератора 69 синхроимпульсов поступают с; для всех вершин. Если для k-й вершины будет име1ь ра795 12 венство с ° = с; „,„„, то. на выходе k-й схемы сравнения группы 70 появится сигнал, открывающий k é ключ группы 72 ключей. На вторые входы группы 72 с выходон второй группы 74 элементов памяти по сигналу от второ. го генератора 7 синхроимпульсов подаются номера вершин симплекса. Но, поскольку открыт только k-й ключ группы 72, через первый элемент ИЛИ 73 на блок 1 выбора симплекса поступит номер k-й, т.е. заменяемой вершины. Номер заменяемой вершины подает- ся на входы группы 85 схем сравнения блока 1, где сравнивается со всеми номерами вершин. При этом k-я схема cpënnånèÿ AnKcHpJJF T равенство и на ее выходе появляется сигнал, который открывает 1 -й ключ группы 84 ключей. Этот ключ начинает пропускать на второй вход соответствующего k-го элемента памяти группы 82 поступающие с выходов второй группы 86 элементов памяти по сигналу генератора 83 синхроимпульсон составляющие заменяющей вершины симплекса. Таким образом, осуществляется замена вершины на новую. Лля дальнейшей работы устройства необходимо также выбрать новый шаг поиска h. Эту задачу выполняют блок 17 выбора шага поиска и блок 18 усилителей. Группа 46 умножителей и группа 45 сумматоров блока 17 определяют величину е по формуле (19). Величина е подается на вход порогового элемента 43, где сравнивается с нулем. Если е « О, то на выходе элемепгга 43 будет сигнал, который откроет первый ключ 40, и величина Ь предыдущего шага через инвертор 44 будет направлена на блок 18 у илителей (в данном варианте h О), Если е ) О, то на выходе порогового элемента 43 сигнал будет отсутство» вать. Следовательно, первый ключ 40 будет закрыт, а второй ключ 41 откроется благодаря наличию элемента НЕ 42. В этом случае величина h c полажптельньlM знаком будет подаваться и» вход блока 18 усилителей. Если Н -" О, то «а выходе порогового элемента 21 появится сигнал и на вход умножителя 25 с вькода первого элемента 22 памяти поступит кoaäìt>èциент усиления k = г(.. Если h О Ч" У то на выходе блока 21 сигнала не бу)252795 13 14 лет и благодаря элементу HE 23 сигнал пойдет на второй элемент 24 памяти, с выхода которого на умножитель 25 будет подаваться коэффициент усиления k = P . Таким образом об-! 1с рабатываются условия (18) . Блок 25 определяет шаг h в соот— Ветствии с формулой (17), который подается для дальнейшей работы на вьоды блоков 1, 2 и 13, после чего 10 цикл повторяется. Следует отметить, что наличие двух последовательно соединенных элементов 15 и 19 памя-. ти обеспечивает подачу на блок 17 предыдущего суммарного напРавления fo. 15 Если неравенство выполняется, т ° е. погрешность меньше или равна допустимой с, то на выходе блока 11 сравне! IIIH ПОЯВИ71 е f CH СИГНа1! I(OÒОРI lй ОКа зывлет управляющее воздействие на второй элемент 8 памяти и третий элемент 13 памяти, а на выходе элемента НЕ 12 сигнал отсутствует. С выхода блока 8 координаты центра симплекса Ъ Б поступают на вход блока 9 ипдикац(н(и на первьп(вход блока 10 вычисления коорд!Ин(т сдвига симплекса, а на вторсй вход блока 10 засылается с выхода блока 13 величина 11 — шаг предыдущего цикла. В блоке 10 нри помощи группы 26 умножителей и группы 27 c+tttlBTopoR и!Роиз вод(! Гся сдВиГ симплекса в соответствии с формулой (20) ° 11ОВ! !е значения координат центв ра симилекса Б „ подаются на второй вход блока 1 выбора симплекса, и в 35 дальнейшем цикл работы устройства повторяется. Таким образом, в результате решения нл блоке 9 индикации oTo(tражtlется Область условно oпти40 мальных значений параметров. Ф о р м у tt а и з о б р е т е н и я Устройство для решения двухкритериаль(п(х задач нелинейного программи- 4 рования, содержап(ее блок усилителей и блок вычисления грлдиентов, о т л и ч л К1 щ л е с я тем, что, с целью ttottbttt!e!fIIH быстродействия, в него Введены блок вычисления координат 5О сдвигn симплекса, блок задания критеpttcв Оптим (злц11и, блок гычислеьн(я косрд!Гнат заменяемой вер(нинь(,первый, второй, третий, четвертый и пятый sJt<.менты памяти, блок выбора шага поиска, блок вычисления координат центра симплекса, элемент HF., блок сравнения, блок нормирования градие„-. тов, блок вычисления локального градиента, блок вычисления кобрдинат заменя!ощей вершины, ключ, блок индикации и блок Выбора симплексл, содержащий перву!о и вторую группы элементов памяти, генератор синхроимпульсов, группу кл!очей, группу сумматоров и группу схем сравнения, первые входы всех сумматоров группы блока Выбора снмплекса объединены, подкл!очены к выходу блока усилителей и входу задания начального шага поиска устройства, вторые входы всех сумматоров группы являются входом задания начальных значений вершин симплекса устройства, второй вход каждого i-ro cóìEtHòoðH группы где 1 = 1, 2, (n + 1),пОдклю1ен к соответству1о!1((!и . Информационным входам Всех элементов памяти, кроме i-I o первой Группы блока выбора сими(!екса, а также к выходу блока вычисления координат сцвиГII симплекса ВllхОд кяждОГО суи ма гора первой группы подключен к соответствующему информационному входу одноименного элемента памяти в первой гругн1е блока выбора симплекса, Одноименные выходы всех элементов памяти первой группы блока выбора симплекса Объединены и подк1»оЧVНЬ(К 11ЕРВЫМ ИнфОРМЛЦИОН»1(?1 ВХОЦ<1М блока задания критериев онт!!1а(зации, блока вычисления коорд!(нлт центра симплекса, первого элеMcíòtt памяти и блока Il»vtttcJJCIIIIH градиентов, выходы генератора cltllхроимпульсов блока льtáopG с11мl!лекса соотве ГствоннО НОд ключены к тактиру!о:t;tw Входам Всех элс((ентов памяти первои и Второй групп блока выбора симплекса, вход перезаписи каждого элемента памяти первой группы блока выбора симплекса подключен к выходу Одиоименного ключа группы блока выбора симплекса, управляющий вход которого подключен к выходу одноименной схемы сравнения группы блока выбора симплекса, входы всех схем сравнен!(я группы объединены и подключены к вь(ходу блока вычисления координат злменяемой верпины, информационный вход каждого ключа группы блока выбора симплекса подключен к вьгходу одноименного элемента памяти Второй группы блока выбора сими(!екса, одноименные информационные входы каждого элемента памяти второй группы блока выбора симплекса объединены и подключены 125 7Ч ) соответственно к группе выходов блока вычисления координат заменян.щей вершины, второй информационный вход блока вьгчисления координат центра симплекса является входом задания 5 числа вершин симплекса устройства, а разрядные выходы блока определения координат центра симплекса соединены с вторым информационным входом первого элемента памяти и с первьпл ин- 10 формационным входом второго элемента памяти, выход которого подключен к входу блока индикации и к первому информационному входу блока вычисления сдвига симплекса, считыт»аютцт»й 15 вход второго элемента памяти подключен к выходу блока сравнения, к входу элемента КЕ и к считьтвяющеьгу входу третьего элемента. памяти, первый вход блока сравнения является 20 Входом заданной точности вьтчислет»ия устройства, второй вход блока сравнения соединен с первьттл информационным выходом блока вычислетн»я локального градиента, второй информационный 25 выход которого подключен к входу четнертогo элемента памяти и к информациОНЛОму Входу ключа Вттход KoòopÎÃÎ соединен с первым информационным входом блока вычисления координат за-30 мепяемой верптины, с информационным входом блока выбора шага поиска и с первь»м информационным входом блока вычисления координат заменяющей верпп»ны, второй и третий информационные 35 входы которого являются входами задания грани гных условий устройства, четвертый информяционнь»й Вход подкл»очек к первому информационному Выходу первого элемента памяти и к 40 второму информационному Входу блока вычислен»»я координат заменяемой вершины, а пятый информационньlf» вход— к выходу блока усилителей и к информационному входу третьего элемента памяти, выход которого подключен к вторым информационным входам блоков Вычисления координат сдвига симплекса и выбора шага поиска, Выход блока тзыбора шага поиска подключен к входу 50 блока усилителей, а третий информациониьп» вход — к выходу пятого элемента памяти, счцтывяющий вход которого подклточен к выходу элемента НЕ, счт»тьтяаю)пему входу первого эле) мента памяти и к управляющему входу ключа, информационный вход пятого ЭЛЕМЕНта ПЯМЯТИ ттОт»КЛЮЧЕН К ВЫХОДУ четят р гого элемента ттямят)», выход пере»ого злеf»E .flттl памяти подкнk!чt. и к третьему информацт»т)1»ному вхог»у блока тчпгпсления координат заменяемой веригины, второй и третий ин4)ормяционные входы блока задания критериев оптимизации являются входом задания одноименных констант устройства, а информационные выходы подключены соотВетстветтно к второму и третьему информационным входам блока вычисления градиентов, первый и второй информационные выходы которого подключены к одноименным входам блока нормирования градиентов, первый и второй информационные Выходы которого подключены к одноименным входам блока вычислелия локального градиента, второй инфор..f;1)lff(11»f»f, выход блока нормироватп»я грядттентов подключен к третьему информационному входу блока вычисления координат сдвига симплекса, причем олок вычисления координат сдвига. симплекся содержт»т группу умножителей и группу сумматоров, первые входы всех сумматоров группы являются перьч)м информационным входом блока, а второй вход каждого 1»з сумматоров груп»ты подключен к выходу одноименного умт»ожителя группы, выходы сумматоро3 Группеl ЯВлЯютсЯ ВыхОЛОМ блока ттерт»ые Входы всех умножителей группы объедттнены и являются вторым информационным входом блока, я вторые входы умножителей группы являются третьим ннформяцнонтнIE» входом блока, блок Ятгчисления координат центра симпл Eic .3 содержттт элемент памяти, генератор синхроимгтульсов, делитель и группу суммятAðoн, первые входы кот 12э?795 рой элементы памяти, генератор синхроимпульсов и группу квадраторов, входы которых являются первым информационным входом блока, выход каждого квадратора подкзг«очен к первым входам одноименных умножителей первой и второй групп, вторые входы умножителей первой группы являются вторым информационным входом блока, а вторые входы умножителей второй «О группы — третьим информационным входом блока, выход каждого умножителя второй группы подключен к первому входу одноименного сумматора первой группы, второй вход каждого сум- 15 матора первой группы подключен к выходу предыдущего сумматора группы, выход последнего сумматора первой группы подкл«» I&II к информационному входу первого элемента памяти, вы- 20 ходы которого являются первым информационным вьгходом блока, выход каждого умнож«гтеля первой группы подключен к первому входу одноименного сумматора второй группы, второ" вход 25 каждого сулгматора второй группы подключен к вьгходу предыдущего сумматора второй группы, выход послед него сумматора второй группы подключен к информационному входу вто- ЗО рого элемента памяти, выходы которого являются вторым информационным выходом блока, выходы генератора синхроимпульсов подключены соответственно к тактирующ«гм входам первого и второго элементов памяти, блок выбора шага поиска содержит группу умножителей, группу сумматоров, пороговый элемент, инвертор, элементы НЕ, первый и второй ключи, пер«зь«е 4«« входы умножителей группы являются первым информационным входом блока, вторые входы умножителей группы являются третьим и«« «ормацион««ь«м входом блока, выход каждого умножитехгя груп-45 пы подключен к первому входу одноименного сумматора групп, в которой вход каждого сумматора группы подключен к выходу предь«дущего сумматора, выход последнего сумматора груп- 5б пы через пороговый элемент подключен к входу элемента НЕ и к управляющему входу первого ключа, выход коI oporo подключен к входу инвертора, выход которого поди«юче««к выходу второго ключа и является выходом блока, управляющий вход второго ключа подключен к выходу элемента liE, информационные входы первого и второго ключей объединены и являются вторым информационным входом блока, блок вычисления локального грациента содержит первый и второй элементы памяти, генератор синхроимпульсов, делитель, элелге««т извлечения квадратного корня, первую и вторую группы сумматоров, группу квадраторов, первые входы сумматоров первой группы являются первым информационным входом блока, вторые входы сумматоров первой группы подключены к соответствующим входам второго элемента памяти и являются вторым информационным входом блока, выход каждого сумматора первой группы подключен к соответствующему вьглоду второго элемента и «!I«I I.II, к ««ходу Одноименного квадратора и является вторым информационным выходом блока, выход каждого «гг«адратора группы подключен к первому входу одноименного сумматора второй группы, выход каждогo сумматора второй группы и выход последнего сумматора второй группы ««Одключены к входу элемента извлечения квадратного «op««sr, выход которого подключен к информационному входу первого элемента памяти, информационные ««ь«ходь«которого подключены к Одноименным входам делителя, шгход делителя является первым информацио«гным выходом блока, тактирукнцие входы первого и второго элементов памяти подключены к соответствующим выходам генератора синх«эоимпульсОв блОк нормировки град««с ««тон содержит группу сумматоРов, группу делителей, первый и второй элеме.нты памяти, злеме IT извлече»II;I «<»aZ 125279 ) ;о рого ян:>яется вторым информационным входом блока, а выход подключен к вторым входам группы делителей, выход каждого делителя группы подключен к соответствующему информационному 5 входу второго элемента памяти, первая и вторая группы выходов которогo являются соответственно первым и нторым информационными вьеходами блока, тактирующие входы первогс и JO второго элементов памяти подключены к соответствующим тзыходлм генератора синхроимпульсов, блок вычисления координат эаменяемой вершины содержит группу умножителей, группу сум- 15 маторов, первьпт и второй ключи, коммутатор, первую и нторук> гру!тп>! эпеМситон 1!ЛЛ!?ттн, ГРУППУ СХЕМ С1>ас>!>Ел!IЯ > ГP<< >>it) КЛ!О<1ЕИ > II (т)ПЬП! И J)T<)PA>J элементы ИЛИ, первый и второй гене- 20 paTopI! сипхроимпульсов, перль>й и нторс>й эле!!виты плг<яти, первый и второй ->7ел!с >тты НЕ:, э ломе>зт с р л в и ения и группу вьтчитптелей, выход каждого иэ котс>рых !то>тк>тючен >< первому 25 t>xcbJJy oJkJt!?Iftt(IHtto! o умножитeля группы» В От>ы(з >зуОль> умножитс.зl(й Гj)) ïíüt Яв?тяются пертзь>м Jiff<1>и!Оинь>т! Bx<)дом блока, первые и BToðûr! П?сс?Де! д». тите)те!! группы лвлян>тся соответст- 3О лепно перин<и и вторь>м информационными !>х с?д;3 h>>f () >101(B !зь>хо>Е каждо т о ножителя группы подкнючен к п(рнсму входу Одноименного сумматора группы, второй «х<)д каждого иэ сумматоров 35 группы, эл исклютением первог<>, подключен к выходу прсдыдушего суммлтоpë груп!1ы> э ныхОд IТО(.лед!>е3 О (. Ммл торп грутпи! соединен с ипформппио
Ifh>hf>f B?(<)длл!и ITep130I О и !>TC>t)ol к;тю рр ЧЕЙ И С НХс»таМ>т К(ММУтатОРЛ, ВЫХОДЫ которого подклк>че>и К 1>1!<ЬОРМЛЦ>тfOH>f()II!IIten!< H v;l памяти первой груттпы, тактирующие входы элемеито!з тт:!мяти 4$ ПЕРВОЙ ГPyitttt f СОЕДИНЕИЫ r ВЬН(ОДОМ и< p Bo I" Г(Пер лтс?рл си!!Хт) Оигт>ту>1 beoB > а иьi>,"<>>I каждого элемеfITH плмяти группы соецпнсн r. пс pf тм f>xopoa Од> иоимештой схемы сравнен!>Я гpyttltt t, SO птс рь!с: вхо>ть! 1>сех схем срлвнепия ! р уппы подключ е Hhl к первому информаци<)иноглу выходу первого элемента памяти, л выход каждой схемы сравнения группы поцклк>чен к управляющему входу одноименного ключа группы, информационный вход которого черен Одноименный элемент !>лмяти второй группы т!с>з(кд — к одно!!л!енному входу первого элс-мента ИЛИ, выход которого являе > сл ньтходс>м блока, второй выход втор<>го генератора синхроимпульсов подкл! чен к тактирующел!у входу первого эпемента памяти, первый информациониь>й k>xoq которого подключен к выходу эл и нтл сравнения и к входу второго эзтсзг!ет<тл НЕ, выход которого подключен к управляющему входу второго эяс",<еитл памяти, информационный вход которого подключен к выходу первого к:п<чл и к первому входу элемента сравнения, второй вход которого подк. l! изторог о ключа, к Bhl» ?-.(1дv > торого элсл!ента или к второму J f f l, «) р!! <) L>! t V B X OI> <> П е 1) н О Г О э л ЕHe H тл и:> !яти, второй ш!формациониьп! н!!Х.) ... которого подключен к первому в", vtó второго элемс IITr ИЛИ, k>TopoA ! 3?;<.д к >тче!!Онтл памяти, третий выход ит .рого ген(зрлтс рл си!>х!?Оилтт!ульсов и(! J1!, 1!<>ч <.. н к y прав?1>тн?>>тсл!у вхОду втОрО го i,л>ячл и к входу элемента НЕ, выход которого подклю еtl к управляющему ВХОД, IlIOJ(ВЫЧИСЛЕИИЯ x()«f>I!If HOT элме>!яющей !>сре>!Иттьт содержит н-.>рную и нт<- рук группы сумматор )н, первук) и тзтopvx> груттпы с хем срлв— H< 1«ия, первую, J>T<>tpg><>> третьк> и четт>с:ртую Группы к.пye и BTop>?>þ ГP? tl>th! .>?1езл!с flToH IIE Г!) Уllпы нычитлтел -й, уг!Пожил сл1, Yeti ep;lтор сиихрои>1>!"!!Iт < О!» Эпсм(JIT и )M>! ТJ! JI груп!ту ул(ил)к ! е>тс:й, первые входы умножителей которои яв. !Яютсн !терн>)тл! Ииформацион>н >и «ходс>л! блока, вторь!е входы абсь J и Являются пя rt;fhf информа-! еы<>ни!.тл! 13холом б;! Ока, л ВыхОДы кажД<)1 О > Мl!O)t I>: .fi 1>ХОДУ ОДНОИМ(ННОГО C.VËf>f lTOPB ! If-!); <» t гpVI! J!11, ПЬIХО;>, тсс?Тс<рого Г>ОДкзпс <<с t Y. первому в) одv одноименной с: < >>1! срлнне>птя первой группы и к инф<)P>!(!Litl<>JIJIO?tp нх()ДУ Оцис>именнОГО клн)ч:! пс:рной груп!н i, вторые;зходы Bc(?: с умм;1т <>т> ОБ и (pB0! l Г р «>т!ть! е>вляют ся чет><ер)т>тг< ин<т>с>рмлцис !!! >м входом бл<)1:л, t>k>xolt каждой схемы cpBJ«teHII?t перв и Группы п<>дклн teil к управляющему н"..О l Одно>!Меиного ключл первой гр ll!!fl Jt к I 22 1252795 От дл. 8 Om Рл. 20 Om входом одноименной схемы сравнения первой группы, вторые входы всех схем сравнения первой группы являются вторым информационным входом блока, выход каждого ключа второй 5 группы подключен к первому входу од" ноименного сумматора второй группы, выход которого подключен к одноименному входу первой группы информационных входов элемента памяти, вторые 10 входы всех сумматоров второй группы объединены и подключены к выходу умножителя и к первым входам вычитателей группы, выход каждого вычитателя группы подключен к одноименному 15 входу второй группы информационных входов элемента памяти, выходы которого являются выходом блока, тактирующий вход элемента памяти подключен к выходу генератора синхроим- 20 пульсов, вход умножителя подключен к вторым входам умножителей группы, второй вход каждого вычитателя груп" пы подключен к выходу одноименного ключа четвертой группы, управляющий вход которого подключен к выходу одноименного элемента IIE группы, % вход которого подключен к управляющему входу одноименного ключа третьей группы и к выходу одноименной схемы сравнения второй группы, первый вход которой объединен с информационным входом одноименного ключа четвертой группы и является третьим информационным входом блока, выход каждого ключа первой группы подключен к информационному входу одноименного ключа третьей группы и к второму входу одноименной схемы сравнения второй группы, выход каждого ключа третьей группы подключен к одноименному входу третьей группы информационных входов элемента памяти. С Входа устройст8а От Входа устройспьВа )252795 (Риг. 7 1252795 1252795 Om &о а Ю am Иода gem- Аи 11 Составитель Т,Сапунова Техред И.Верес Корректор Е.Сирохман Редактор В.Петраш Тираж 671 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д. 4/5 Заказ 4622/50 Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4
