Устройство для решения двухкритериальных задач нелинейного программирования Советский патент 1986 года по МПК G06G7/122 

12

за счет возможности выбора оптимального варианта, одновременно учитывать требования двух критериев. Устройство содержит блок 1 выбора симплекса, блок 2 вычисления координат заменяющей вершины, блок 3 вычисления координат заменяемой веришны, блок 4 задания критериев оптимизации, элементы памяти 5, 8, 13, 15, 19, блок

1

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

Цель изобретения - повышение быст родейстБИЯ.

Выбор оптимального варианта осуществляется из области условно опти- ретс НиГ (облпстт, ITapcTci) и об. Шсти D, задаваемой ограничениями

; , - )

п n-icjio огггимизируем1 х параметров.

Задачи, сформулированные как мно- гокритериальные, требуют при своем решогпп: поиска экстремума вектордого критерия вида 7 F,(x ), F.(X), где F,(X) - f,(X), F.(X) f,,(X ) - составляняцие векторного критерия. Вид функций f,(X) и fj(X) определяет СП С1 о1 1ствамп исследуемой системт-.и Однако на практике часто встречаю7ся квадратичные зависимости критериев от параметров (например, стоимость и эффективность) вида

F fY - ь-v I -, F, (X) Г cijx. .

В дальнейшем экстремумом считаегся

-

максимум значения критерия F (X) - (F,(X), Р„()0. Решение , предпочтительнее X-j, если одно из неравенств системы

F,(X, ) F,(x,)

F (X, ) i F, (X,,)

(2)

2795

6 вычисления градиента, блок .7 вычисления координат центра ситглекса, блок 9 индика1щи, блок 10 вьтисления координат сдвига центра симплекса, блок 11 сравнения, элемент НЕ 12, блок 14 вычисления локального градиента, ключ 1б, илок 17 выбора шага поиска, блок 18 усилителей, блок 20 нормировки градиента. 11 ил.

0

5

0

5

будет строгим. При этом X, и Х, на- зивпют срав1 пм1лч по векторному кри- терию. Если в системе (2) неравенства различных знаков ( и ), то л и Xj несравнимы.

Цель оптимизашп - выделение клас са Парето (оптимальных решений), т.е. области D, состоящей из попарно несравнимых мо;кду собой векторов значений параметров X в области D.

Поиск точки, г.ринадлеж.чщей области , начинается из произвольно точки Л|а,, ..., ) в которой оп- ределшотся направления возрастания ii У,., дпн обеих функц1п F, (X) и К„ (X,). Если эти направления противоположны, то дачная точка прпнагую-лсит об. Dp , если жо суще. направление , с которым f, и V составляют острый угол, то двпжешве осу|;1,еетвляется п направлении F . Та

0

;гим образом, задача состоит в опреде- j)i: iiHH направленпп наибольшего возрастания функций F.(X) и FЛХ). Нап- i

p. iDJieHifH V, и Y,, совпадают с направ- ления -ш градиентов соответствую1 у1Х функ1у1Й. В силу того, что час2; ные кригерип, соответст1зую гие F (X), не всегда удается предс-1-авить в иидс аналитических зависимости, напрапленце градиента в точке X

Л

числяется с использованием значснпл F в окрестностях точки Х,, Для этого т-.округ Точки Хц строится много- гряннпк (симплекс) ненулевого объема, достаточно Ma.noi o размера, пмею- (п + 1) вершину. Длина ребра симплекса равна или близка к заранее выбранной Есличг.не h поиска.

Координаты k-i { вершины симплекса (k 1, ..., п + 1) образуются

смещения k-й координаты начальной точки на шаг h:

1-я вершина х,, а + h, х

«f

-а, .... ,

вершина х

4- h V я

т 11 , . . , , л 1 d ,

17 22 г

(3)

п-я вершина х,, i 24 5

а„ + h;

ttn

(п + 1)-я вершина х,,,.

X,

г(п«0 2

Mn.0 % В каждой из вершин определяются значения компонент векторного критерия F (Ю , F2(X). По этим значениям строится линейная локальная аппроксимация функции.

Коэффициенты ищутся из условия равенства аппроксимации в вершинах симплекса значениям критерия, т.е.

путем решения системы алгебраически

уравнений

1уИ-1 И П4; г

... + а,

+ а

1П+

относительно а .

Аналогичная система для критерия ).

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

о 1ГТ-Г .

nvi

,1: g

илиЗ. - .(i 1, ... n

01 П + 1

j 1, ..., (n + 1). (5)

Для того чтобы уменьшить влияние масштаба выбранных критериев, векторы градиентов следует нормировать

+ Х,.

hti

и

-12

Ml

п

2

in . -f

Т

- jg

|а, 11

(6)

Zn

)aw

где /а,/ . + а, +-..,+ а, , (7)

- jal+a /TTTT

2п

10

5 Таким образом, направления f, и f возрастания функций F, и F определены „

Существование направления, обеспечивающего улучшение обеих компонент векторного показателя, эквивалентно существовагд к вектора Р, удовлетворяющего уравнению

Г, , + 7, 0. (8)

Признаком того, что точка (центр симплекса) принадлежит множеству условно оптимальных решений, является вылолпеиие условия

х 20 .

ких

25

(4)

30

ия

и- 35 ие F - 40 в,. )

ti

45

IV.

Л,(9)

где л -ТТГ

/ I S - заданная точность вычисленияJ

Ч. С- - С (10

irj |Т, :,-... -ь ,(12)

-

Если полученная точка S не является Парето-оптимальной, то строится ювый симплекс. Он получается из старого путем замены одной из вер шин другой, координаты которой соответствуют сдвигу центра симплекса s p в направлении вектора на величину uiara h

,.м К ..(13)

Заменяемая вершина соответствует минимальному из скалярных произведений

(Х - р) f, (k 1, ..., п + О,

т.е.

min c,- J , где i - номер заменяемой верпгины;

с; (х, - х,о) f р, + (х, - + ... (х. - х„„) fon .

го ) (14)

Прежде, чем к повторному циклу поиска условно оптимальных решений, проверяется ямпо/гнение ограничений для новой верипиты

f,

8j.

(15)

в случае нарушения одного нз неравенств системы (15) значение j-й координаты центра симплекса определяется из выражений соответственно

12527956

шины; на фиг. 10 - функциональная схема блока выбора симплекс а; на фиг. 11 - функциональная схема блока вычисления координат заменяющей 5 вершины.

Устройство содержит блок 1 выбора симплекса, блок 2 вычисления координат заменяющей вершины, блок 3 после чего цикл решения повторяется. вычисления координат заменяемой верДля увеличения скорости сходимости 10 шины, блок 4 задания критериев оп- в случае сохранения направления гра- тимизации, первый элемент 5 памяти.

1

f j + 0,1h, при xj; fj g - 0,1h, при Xj- gj

(16)

диента на последовательных шагах шаг поиска увеличивается, при существенном изменении направления- уменьшается, т.е.

.k,j,(17)

где h - длина предыдущего шага; k ((, - KoaiM HiyieliT усиления. , при с ь о (« 1) k,

(18)

с

)с

f

+ I

1 , при с о (//1/с 1)

f

01 0(

Г

02 02

(19)

on

Д 0, 07 оп - ное направление на предыду1цем шаге. зо

Если найденная точка S принадле- D, то она запоминается (инди

цируется), а весь симплекс сдвигается на г eличи y шага h в напраилении f,

s:

7

5„ -ь hV

(20)

где S - новая точка центра симплекса.

1а фиг. 1 представлена блок-схема устро1 ства ,л,пя решения двухкрите- риальных задач нелинейного программирования i на фиг. 2 - функциональная схема блока усилителей; на фиг. 3 - функциональная схема блока вычисления координат сдвига симплек caj на фиг. А - функциональная схема блока вычисления координат центра симплекса; на фиг. 5 - функциональная схема блока задания критериев оптимизащ1и (один из возможных вариантов); на фиг, 6 - функ1и1ональ- ная схема блока выбора шага поиска; на фиг. 7 - функциональная схема блока вычисления локального градиента; на фиг. 8 - фyнкlI oнaльнaя схема блока нop шpoвки градиента; на фиг, 9 - функцио)1альная схема блока вычисления координат заменяемой вер

зо

блок 6 вычисления градиента, блок 7 вычисления координат центра симплекса, второй элемент 8 памяти, блок 15 9 индикации, блок 10 вычисления координат сдвига симплекса, блок 11 сравнения, элемент НЕ 12, третий элемент 13 памяти, блок 14 вычисле- иия ло1сального град11ента, четвертый

20 элемент 15 памяти, ключ 16, блок 17 выбора шага поиска, блок 18 усилите- лей, пятый элемент 19 памяти и блок 20 )10рмировки градиента. Блок 18 усилителей содержиг пороговый эле25 моит 21, первый элемент 22 памяти, элемент НЕ 23, второй элемент 24 па- ьшти и умножитель 25.

Блок 10 вычисления координат сдвига симплекса содержит группу 26 ум11ожитслей и группу 27 сумматоров. Блок 7 вычисления координат центра симплекса содержит группу 28 сумматоров, делитель 29, элемент 30 памяти, генератор 31 синхроимпульсов. Блок 4

35 задания критериев оптимизации содержит группу 32 квадраторов, первую группу 33 ум1гожителей, вторую группу 34 ум}южителей, первую группу 35 сумматоров, первьй элемент 36 памяти,

40 генератор 37 синхроимпульсов, второй элемент 38 памяти и вторую группу 39 сумматоров. Блок 17 выбора шага поиска содержит первый ключ 40, второй ключ 41, элемент НЕ 42, пороговый 45 элемент 43, инвертор 44, группу 45

сумматоров, группу 46 умножителей.

J

Блок 14 вычисления локального градиента содержит первую группу 47 сумматоров, группу 48 квадраторов, вто50 рую группу 49 сумматоров, группу 50 извлечения квадратного корня, первый элемент 51 памяти, делитель 52, генератор 53 синхроимпульсов и второи элемент 54 памяти. Блок 20 нормировки

55 градиента содержит группу 55 квадраторов, первый элемент 56 памяти, группу 57 сумматоров, элемент 58 из- |Влечения квадратного корня, группу 59

7

делителей, второй элемент 60 памяти и генератор 61 синхроимпульсов.

Блок 3 вычисления координат, заменяемой вершины содержит группу 62 вы читателей, группу 63 умножителей, группу 64 ci MMaTopOB, первьй 65 и втрой 66 ключи, коммутатор 67, первую группу 68 элементов памяти, первьш генератор 69 синхроимпульсов, группу 70 схем сравнения, первый элемент 71 памяти, группу 72 ключей, первый элемент ИЛИ 73, вторую группу 74 элементов памяти, второй генератор 75 синхроимпульсов, первый элемент НЕ 76, группу элементов 77 сравнения, второ элемент 78 памяти, второй элемент ИЛИ 79, второй элемент НР: ВО. Блок 1 выбора симплекса содержит группу 81 cy tмaтopoв, первую группу 82 элементов памяти, генератор 83 синхроим- пульсов, группу 84 ключей, группу 85 схем сравнения и вторую группу 86 элементов памяти. Блок 2 вычисления координат заменяющей вершины содержи группу 87 умножителей, первую группу 88 сумматоров, первую группу 89 ключей, первую группу 90 схем сравнения первую группу 91 элементов НЕ, втору группу 92 ключей, вторую группу 93 сумматоров, элементы 94 памяти, умножитель 95, группу 96 вычитателей, генератор 97 синхроимпульсов, третью группу 98 ключей, вторую группу 99 схем сравнения, вторую группу 100 элеме тов НЕ и четвертую группу 101 ключей.

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

Начальные зт ачения верши симплекса а

I

а

7

., а„ и шаг поиска

Ь подаются на первьй и второй входы блока 1 выбора симплекса. Группа 81 сумматоров оценивает вершины симплекса по формулам (3), причем значения вершин накапливаются в соответствующих элементах памяти группы 82. Затем значения каждой вершины выдаются по сигналу от генератора 83 синхроимпульсов последовательно на вььход блока 1 выбора симплекса и, следовательно, на первые входы блока 4 задания критериев оптимизации, первого элемента 5 памяти, блока 6 вычисления градиента и блока 7 вычисления координат центра симплекса.

На второй и третий входы блока 4 подаются с входа устройства значения постоянных Ь| и d;. Значения верши

ны симплекса х ; возводятся в квадрат группой 32 квадраторов, а затем засьшаются нд первую 33 и вторую 34 группы умножителей. Блоки 33 и 39, а также блоки 34 и 35 определяют j-e составляющие критериев в соответствии с (opмyлa ги ( О , которые накапливаются соответственно во втором элементе 38 памяти и первом элементе 36 памяти. После накопления всех (п + 1) составляющих по сигналам от генератора 37 синхроимпульсов величины критериев ) и F(X) подаются соответственно на второй и третий входы блока 6 вычисления градиента.

Блок 6 осуществляет решение системы линейных алгебраических уравнения (4) относительно величины а, и аналогичную систему уравнений, где в левых частях уравнений располагаютс;я составляю1Щ1е вектора F (X) от-

- носительно величины а„. Напряжения,

сос)тветствуюио1е величинам а, и а

юt5 20 25

30

5

0

5

5

0

и характеризующие локальные даправ- ления градиентов функций Fj(X) и Г (X) засылаются на первый и второй входы блока 20 нормировки градиента. Составляющие вектора а подаются на

квадратного 7i, / по форгруппу 55 квадраторов, которые совместно с группой 57 сумматоров и элементов 58 извлече 1Ия корня оценивают модуль муле (7), Эта величина засылается на вход первого элемента 56 памяти, с выхода KOTopoi 6 по сигналу от генератора 61 синхроимпульсов значение модуля поступает на первые входы группы 59 делителей. На вторые входы группы 59 подаются состазляюир-1е вектора л, , 1 руппа 59 осуществляет нормировку вектора а, по формуле (6) и направляет нормированные оставляющие па 1 руппу входов второго элемента 60 памяти.

CocTaiJJiniontue вектора aj засьшаются на группу входог первого элемента 56 памяти, с группы выходов которого они подаются на пход1.1 группы 55 квадраторов. Затем работа групп 55-59 прсзисходит так же, как и при нормировке а,. Вектор 1 нормированных состзвляющих поступает па первый вход блока 14 вычисления локального грааиента, а вектор Т, - на второй вхо;- блока 14 и трстиС БХОД блока 10 вычислеипя координат сдппг оииплекса.

Составляющие векторогз V, п 1 по- даготся на первые и BTopi.ic первой группы 47 сумматоров блока 14 вычисления локального градиента, а составляющие f, поступают также на группу входов второго элемента 54 памяти. Блок 47 оценивает суммарное

направление f в соответствии с формулой (8). Составляющие вектора f засылаются на входы четвертого элемента 15 памяти И ключа 16 устройст- вг, а также на входы группы 48 квадраторов блока 14, группы 48-50 определяют модуль вектора Vg по формура SP по сигналу от генератора 31 синхроимпульсов подаются на В,гход блока 7 вычисления координат центра cи fflлeкca,

10

Блок 2 вычисления координат заменяющей вeplш ны оценивает новьй симплекс в соответствии с формулой (13) при noMOL yi группы 87 умножителе (11), который подается на первый вход первого элемента 51 памяти,

С группы выходов второго элемента 5 -. первой группы 88 сумматоров, 54 памяти составляющие вектора Yf по затем осугцествляется проверка вы- сигналу от генератора 53 синхроимпульсов засылаются на входы группы 48 квадраторов. Группь 48-50 определяют модуль вектора f, по формуле 20 (12), которьц засыпается на первый вход первого элемента 51 памяти. Но сигналу генератора 53 синхроимпульсов вел1гчины / VP / и /V,/ направляют,ся на первый и второй входы делителя 25 составляющей (переменной) заменяющей 52, которьп оценивает точность и по вершины симплекса, Коли соблюдается

для k-й составляю1 (ей )3epxiiee iiepa- венство (15), то на выходе соответствующей схемы сравнения появляется сигнал, которий открывает соответствующий ключ rpynnh 89, и х. поступает на вторую группу У9 схем срав

полнения неравенства (15). С этой целью составляющие координаты заме- няюо;ей вершины симплекса зас длаштся на первые входы первой группы 90 схем сравнения и nepnoi i г руппы 89 ключей. Па вторые входы rpyinibi 90 схем сравнения с входа устройства подаются нижние границы 1. по каждой

30

Формуле (10), Величина Д поступает на второй вход блока 11 сравнения устройства, на первый вход которого с входа устройства подается значение заданной точности вычисления . В блоке 11 осуществляется проверка выполнения условия (9) .

Если это условие не соблюдается, т.е. Ь 7 , то на выходе блока 11 сравнения сигнал будет отсутствовать, а на выходе элемента НЕ 12 появится сигнал, который будет управляющргм для первого элемента 5 памяти, ключа 16 и пятого элемента 19 памяти. Тог- 40 да величина через ключ 16 поступает на первые входы блока 2 вычисления координат заменяющей верпшны, блока 3 вычисления координат заменяемой

35

нения для сопоставлсння с верхней границей g. Если XQ «- , то на пы- ходе k-й схемы сравнсни 1 rpyrini: 90 сигнапа не будет, а на выходе элемента НЕ гругп1ы 91 появится сигнал, который откроет k-й ключ группы 92 и f поступает в соответствуюгций сумматор группы 93, На второй вход этого сумматора с выхода умножителя 95 поступает величгшя О,1Ь (наличие одного входа блока 95 объясняется тем, что один из сомножителей - поснения для сопоставлсння с верхней границей g. Если XQ «- , то на пы- ходе k-й схемы сравнсни 1 rpyrini: 90 сигнапа не будет, а на выходе элемента НЕ гругп1ы 91 появится сигнал, который откроет k-й ключ группы 92 и f поступает в соответствуюгций сумматор группы 93, На второй вход этого сумматора с выхода умножителя 95 поступает величгшя О,1Ь (наличие одного входа блока 95 объясняется тем, что один из сомножителей - посвершины и блока 17 выбора шага поис- s тоянное число). Группой 93 сумматока. Величина р поступает на третий вход блока 17, составляющие х;; нер- uiiiH симплекса - на третий вход блока 3, а центр симплекса S - с первого выхода первого элемента 5 памяти на четвертый вход блока 2 и второй вход блока 3.

Центр симплекса 3 поступает на второй вход блока 5 с выхода блока 7 вычисления координат центра симплекса, 11оследш1Й осуществляет оце. ку i-й составляющей центра симп лекса в соответствии с формулой (5)

роз определяется k-я составляющая заменяющей вершины по (верхней) формуле (16), которая затем подается на первую группу входов элемента 94

50 памяа и,

Сопоставл иисг х, с вepxни уровнем g| осуществляется при помощи групп 99-101 аналогично. Если ньтол- няется )пта(нее неравенство (15), х,

55 1чоступает на третью группу входов элемента памяти 9-. В , когда tjk BK гп.гчисляется значение переменной по нижней формуле (16) при

125279510

при помоиц группы 28 сумматоров н делителя 29 (величина п 1 на нто- рой вход делителя подается с входа устройства). После накопления в эле менте 30 памяти составляющие вектора SP по сигналу от генератора 31 синхроимпульсов подаются на В,гход блока 7 вычисления координат центра cи fflлeкca,

Блок 2 вычисления координат заменяющей вeplш ны оценивает новьй симплекс в соответствии с формулой (13) при noMOL yi группы 87 умножите -. первой группы 88 сумматоров, затем осугцествляется проверка вы-

-. первой группы 88 сумматоров, затем осугцествляется проверка вы-

составляющей (переменной) заменяющей вершины симплекса, Коли соблюдается

полнения неравенства (15). С этой целью составляющие координаты заме- няюо;ей вершины симплекса зас длаштся на первые входы первой группы 90 схем сравнения и nepnoi i г руппы 89 ключей. Па вторые входы rpyinibi 90 схем сравнения с входа устройства подаются нижние границы 1. по каждой

нения для сопоставлсння с верхней границей g. Если XQ «- , то на пы- ходе k-й схемы сравнсни 1 rpyrini: 90 сигнапа не будет, а на выходе элемента НЕ гругп1ы 91 появится сигнал, который откроет k-й ключ группы 92 и f поступает в соответствуюгций сумматор группы 93, На второй вход этого сумматора с выхода умножителя 95 поступает величгшя О,1Ь (наличие одного входа блока 95 объясняется тем, что один из сомножителей - постоянное число). Группой 93 сумматороз определяется k-я составляющая заменяющей вершины по (верхней) формуле (16), которая затем подается на первую группу входов элемента 94

памяа и,

Сопоставл иисг х, с вepxни уровнем g| осуществляется при помощи групп 99-101 аналогично. Если ньтол- няется )пта(нее неравенство (15), х,

1чоступает на третью группу входов элемента памяти 9-. В , когда tjk BK гп.гчисляется значение переменной по нижней формуле (16) при

n

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

вой вершины Х.,„„ засылаются на

п О О

вход блока 1 выбора ройства.

симплекса

Дпя того, чтобы заменить вер1Ш1ну в блоке 1, необходимо определить ее номер. Эту задачу решает блок 3 вычисления координаты заменяемой вершины. С этой целью при помощи группы 62 вычитателей, группы 63 умножителей и группы 64 сумматоров определяется по формуле (14) величина с; для каг-кдой вершины, которая подается через коммутатор 67 на первые входы первой группы 68 элементов памяти и первые входы первого ключа 65 и второго ключа 66. Вначале сигнал на третьем выходе второго генератора 75 синхроимпульсов отсутствует, поэтому второй ключ 66 закрыт, а первый ключ 65 открыт, поскольку на выходе первого элемента НЕ 76 сигнал будет. Следовательно, на первьй вход блока 77 сравнения поступает с; для перво вершины. Затем на третЕ,ем выходе генератора 75 появляется сигнал, который открывает второй ключ 66 и закрывает первый ключ 65. Таким образом, величина С; для второй вершины симплекса поступает на второй вход групп 77 элементов сравнения.

Группа 77 элементов сравнения работает следуюпц1м образом. Если с на первом входе меньше, чем на втором, то на выходе группы 77 появляется сигн;1л; когда с на первом входе равно или больше, чем на втором, то на выходе группы 77 сигнал отсутствует. Такая работа группы 77 элементов сравнения, а также наличие первго элемента НЕ 80, второго элемен- та 78 памяти и второго элемента ИЛИ 79 позволяет зафиксировать в элементе 71 памяти наименьшее значе

иие с

мин

которое соответствует вери-ине симплекса. Это значение подает- 50 ся по сигналу генератора 75 синхроимпульсов на вторые входы второй 70 схем сравнения. На первые входы группы 70 с выходов первой группы 68 элементов паг-шти по сигна- 55 лу первого генератора 69 синхроимпульсов поступают с- для всех вершин. Если для k-и вершины будет име1ь ра12

o

5

0

5

0

0

0

венство с; л,им то. на выходе схемы сравнения группы 70 появится сигнал,, открьшающий k-й ключ группы 72 ключей. На вторые входы группы 72 с выходов второй группы 74 элементов памяти по сигналу от второго генератора Т синхроимпульсов подаются номера вершин симплекса. Но, Поскольку открыт только k-й ключ группы 72, через первый элемент НИИ 73 на блок 1 выбора симплекса поступит номер k-й, т.е. заменяемой вершины.

Номер заменяемой вершины подает- ся на входы группы 85 схем сравнения блока 1, где сравнивается со всеми номерами вершин. При этом k-я схема сравнения фиксирует равенство и на ее выходе появляется сигнал, который открывает k-й ключ группы 84 ключей. Этот ключ начинает пропускать на второй вход соответствующего k-ro элемента памяти группы 82 поступаю1 Д1е с выходов второй группы 86 элементов памяти по сигналу генератора 83 синхрои тульсов состав- ляюпще заменяющей вершины симплекса. Таким образом, осуществляется замена вершины на новую.

/i lH дальнейшей работы устройства необходимо также выбрать новый шаг поиска h. Эту задачу выполняют блок 17 выбора шага поиска и блок 18 усилителей. Группа 46 умножителей и группа 45 сумматоров блока 17 определяют величину е по формуле (19). Величина е подается на вход порогового элемента 43, где сравнивается с нулем. Если е i О, то на выходе элемента 43 будет сигнал, который откроет первый ключ 40, и величина h предыд щего шага через инвертор 44 будет направлена на блок 18 усилителей (в данном варианте h 0). Если е О, То на выходе порогового элемента 43 сигнал будет отсутствовать. Следовательно, первый ключ 40 булет закрыт, а второй ключ 41 откроется благодаря на;п1чию элемента НЕ 42. В этом случае величина li с положителып,1М знаком будет подаваться на вход блока 18 усипителеГ. Ес- хп1 h 0, то на вьсходе порогового элемента 21 появится сигнал и на вход умножителя 25 с вмхода первого элемента 22 памяти поступит коэ(|хЪи-

(i-. Если h О, 21 сигнала не бу-

циент усиления k То на выходе блокп

131

дет и благодаря элементу НЕ 23 сигнал поГщет на второй элемент 2А памяти, с выхода которого на умножитель 25 будет подаваться коэффициент усиления k.j, /3 . Таким образом об- рабатьшаются условия (18).

Блок 25 определяет шаг h в соответствии с формулой (17), который по дается для дальнейшей работы на вьоды блоков 1, 2 и 13, после чего цикл повторяется. Следует отметить, что наличие двух последовательно соединенных элементов 15 и 19 памяти обеспечивает подачу на блок 17 предыдущего суммарного направления с

Если неравенство выполняется, т.е погрешность меньше или равна допустимой , то на выходе блока 1 1 срав нения появляется сигнал, которьш оказывает управляющее воздействие на второй элемент 8 памяти и третий эле мент 13 памяти, а на выходе элемента НЕ 12 сигнал отсутствует. С выхода блока 8 координаты центра симплекса Sg поступают на вход блока 9 индикации и на nepBbtfi вход блока 10 вычисления коорд1П ат сдвига симплекса, а на второй вход блока 10 зас.и1ается с выхода блока 13 вшгичина h - шаг предыдущег о 1Ц1кла, В блоке 10 при noMoi 5i группы 26 умножителей и i-pyn- пы 27 сумматоров производится сдвиг симплекса в соответствии с формулой

(20) . овые значения координат центo tpa симплекса Ь подаются на второй

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

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

Устройство для решения двухкрите- риальшзгх задач нелинейного программирования, содержащее блок усилителей и блок вычисления градиентов, отличающиеся тем, что, с целью повьпиепия быстродействия, в него введены блок вычисления координат Сдвига симплекса, блок задания критериев оптиьгязащп, блок пычислен1 я коорди 1ат заменяемой вершит.,первый, второй, третий, четвертый и пятый элементы памяти, блок выбора шага поиска, блок вычисления координат центра симплекса, элемент НЕ, блок сравнения, блок нормирования градион5279514

тов, блок вычисления локального градиента, блок вычисления координат заменяющей верШ1П1Ы, ключ, блок инди- кащш и блок выбора симплекса, содер- 5 жалщй первую и вторую группы элементов памяти, генератор синхроимпульсов, группу ключей, группу сумматоров и группу схем сравнения, первые входы всех сумматоров группы блока

10 выбора симплекса объединены, подключены к выходу блока усилителей и входу задания начального шага поиска устройства, вторые входы всех сумматоров группы являются входом задания 15 начальных значений вершип симплекса устройства, второй вход каждого i-ro сумматора группы где i 1, 2, ,.., (п + 1),подключен к соотпетствую 1Ц{м . информационным входам всех элементов

20 памяти, кроме i-ro первой группы блока выбора ситтлекса, а также к выходу блока вычисления координат сдвига симплекса, выход каждох о сумматора первой группы подключен к

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

30 выбора симплекса объединены и подключены к первым информацио1п ым входам блока задания критериев оптпю1задии, блока нычислепия координат центра симплекса, первого элемепта памяти

35 и блока вычисления градиентов, выходы генератора синхроимпульсов блока Bhi6opa симплекса соответственно под- ключепы к тактируюшпм входам псех элементов памяти первой и второй

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

45 управляющий вход которого подключен к ВЬКОДУ одноименной схемы сравнения груптпз блока выбора симплекса, входы всех схем сравне}пш группы объединены и подключены к выходу блока вы50 числения координат заменяемой вер- пины, информационный вход каждого ключа группы блока выбора симплекса подключен к выходу одноименного элемента памяти второй группы блока

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

151

соответственно к группе в.гходов блок вычисления координат заменянхдей вершины, второй информационный вход блока вьписления координат центра cи шлeкca является входом задания числа вершин симтшекса устройства, а разрядные выходы блока определения координат центра симллекса соедине 1Ы с вторым информационным входом первого элемента памяти и с первым ин- формационным входом второго элемента памяти, выход которого подключен к входу блока индикации и к первому информационному входу блока вычисления сдвига симплекса, считываю1ций вход второго элемента памяти подключен к выходу блока сравнения, к входу элемента НЕ и к считывающему входу третьего элемента памятиf первый вход блока сравнения является входом заданной точности вьпгасления устройства, второй вход блока сравнения соединен с первьп-) информационным выходом блока вычисления локального градиента, второй информационный выход которого подключен к входу четвертого элемента памяти и к информа- 1Шониому входу ключа, выход которого соединен с первым информаилоиньм входом блока вычисления координат за меияемой вершины, с и 1формаиионным входом блока выбора гаага поиска и с информациоин1,гм входом блока вычисления координат заменяющей вер 1Ш1НЫ, второй и третий информационные входы которого являются входами задания граничных условий устройства, четвертый информационный вход подключен к первому ннформа11,иончому выходу первого этгемента памяти и к второму информационному входу блока вычисления координат заменяемой вершины, а пятый информационный вход - к выходу блока усилителей и к информационному входу третьего элемента памяти, выход которого подключен к вторым информационньм входам блоков вычисления координат сдвига симплекса и выбора гаага поиска, выход блока выбора шага поиска подключен к входу блока усилителей, а третий информа- ционпьп вход - к выходу пятого элемента памяти, считываюп1ий вход которого подключен к в 1ходу элемента ИЕ, считывающему входу первого эле- мента памяти и к управляющему входу ключа, информационный вход пятого элемента памяти подключен к выходу

ISIf)

четвпртпг о г лемента памяти, выход первого элемента памяти подключен к третьему информационному входу блока вычисления координат заменяемой вер- пошы, второй и третий информационные входы блока задания критериев оптимизации являются входом задания одноименных констант устройства, а информационные выходы подключены соответственно к второму и третьему ин- формационньм входам блока вычисления градиентов, первый и второй информационные выходы которого подключены к одноименным входам блока нормирования градиентов, первый и второй информационные выходы которого подключены к од оименн,гм входам блока вычислении лок;1лыю1 о градиента, второй ин- форманионн11 Й выход блока нормирования градиентов подключен к третьему информационг(ому входу блока вычисления координат сдвига симплекса, причем блок Вычисления координат сдвига. симплекса содержит группу умножителей и грутту сумматоров, первые входы всех cyм taтopoв группы являются пер- BbtM информационным входом блока, а второй вход каждого из сумматоров группы подключен к выходу одноименного умножителя группы, выходы сумматоров группы являются выходом блока, пераые входы всех умножителей группы объединены и являются вторым информационным входом блока, а вторые входы умножителей группы являются третьим и иЬормацпо1П1ьм входом блока, блок, вьпшсления координат центра снмплекса содержит элемент памяти, генератор синхроимпульсов; делитель и группу сумматоров, первые входы которых являются информационным входом блока, выход каждого сумматора, кроме последнего, подключен к второму входу последующего сумматора группы, выход последнего сумматора группы подключен к первому входу делителя, второй вход которого является вторым информационньгм входом блока, а выход делителя подключен к ииформапионному входу эле- менча памяти, к контактирующему входу которого подключен выход геиера- TODa сир{хроимт1ульсов, выходы элемента памяти являются разрядными выходами блока, блок задания критериев опти№1за1и1и содержит первую и вторую группы множителей, первую и вторую группы сумматоров, перпый и вто-

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

5

5 0

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

грутты, выход каждого сумматора второй группы и выход последнего суьма- тора второй группы подключены к входу элемента извлечения квадратного кор(я, выход которого подк;почен к ин|Ьормационному входу первого элемента памяти, информационные выходы ко- Topoi o подключены к одноименным входам дегп{теля, выход делителя является первым информационным выходом блока, тактирую 1у1е входы первого и второго элементов памяти подю1ючепы к соответствующим выходам генератора синхроимпульсов, блок F op a poвки гра;дпснтов содержит группу сумматоров, группу делителей, первый и второй элементы памяти, элемент извлечения квадратного корня, генератор

синхроимпульсов и группу квадраторов,

I

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

рого является вторым информационным входом блока, а выход подключен к вторым входам группы делителей, вых каждого делителя группы подключен к cooтвeтcтвyющe ry информационному входу второго элемента памяти, первая и вторая группы выходов которого являются соответстпенно первым и вторым информа1дионны да выxoдa и блока, тактирующие входы первого и второго элементов памяти подключены

к соответствую Щ1м выходам генератора синхроимпульсов, блок вычисления

координат заменяемой вершины содержит группу умножителей, группу cyr-i- маторов, первьй и второй ключи, коммутатор, первую и вторую группы зпе МСНТ05) памяти, группу схем сраяне- НИН, rpynriy ключей, первый и nTopoi элементы {-ШН, первый и второй гене- раторы синхроимпульсов, nepBbiii и второй элепенты памяти, первый и второй элементы НЕ, элемент сравнения и rpyruiy вьптитателе), выход каждого из котг)рих подключен к nepiioNfy входу о/т.иои(1енного умножите.пя груп

пы, вторые входы умножителе г руппы являются первьр-1 инфор 1аппонн -П 1 вхо- д,ом блока, nepBi.ie и пторыс входы делителей группы являются соответственно перпьгм и вторым информационными входами блока, выход каждого умножителя группы подключен к первому входу одноименного сумт-{атора группы второй вхолТ каждого из суг.тматоров rpyimfji, за исключением первого, подключен к выходу предьщупхего cyf-шато ра г рулпы, 3 выход последнего cybfMa тора гругигы сое;шиен с 1гнфориац1то - иыми входами первого и второго iuno- чей и с входами коммутато)5а, выходы которого подключены соответственно к информационному входу одноименного памяти первой грутппл, тг1ктирую1цпе входы элементов памяти первой 1 рупп л соединены с выходом nepBorfj генератора синхроимпульсов, а вьгло/1 каждого элемента памяти

групт 1 соед.ипен с входом од- I

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

j Ю

tS 20

5

0

5

0

5

5

0

20

пы подключен к первому, выходу второго гене.ратора синхроиг-тульсов, а выход - к односменному входу первого элсг5е гга ИЛИ, выход которого являе-г- си ги.кодом блока, второй выход вто- Р(1го генератора синхроимпульсов подключен к тактирующему входу riepBoro элемента памяти, первый информационный вход которого подключен к выходу элем : пта сравнения и к входу второго элемента НЕ, выход которого подключен к управляющему входу второго памяти, информационный вход которого подключен к выходу первого ключа и к первому входу элемента cpa нeFIИя, второй вход которого под- к.;11 1чен к выходу второго ключа, к вы- ,y ь:торого элемента или к второму . Ч Г ппионяог у входу nej)Boro элемента 11.ЧМЯТИ, второй информационны В11:;п , которого подключен к первому Bxtx iy второго элемента ИЛИ, второй iixo/ ,г торого подключен к выходу вто- рог о з.аегюнта памяти, третиГ выход второго генератора синхроиьиульсов под. к управляьлцему входу второго ключа и к входу элемента НЕ, выход которого подключен к управляклдему Bxo;i,y первого к.чюча, блок вычисления коо11ди1 :ат заменян1цей верпгины содержи первую и вторую г-руппы с тчмато- рои, первую и вторую группы схем сравнения, первую, вторую, третью и чет- вер 1 ук) труппы кл)11чей, первую и вторую гругплы злег ентон НЕ, группы вычита- теле, умножитель, генератор синхро- n.MTiyjiMxiH, элемент памяти и группу ум Чо ителкй, первые входы умножителей которой являются первг.пч информа- .м BxoJU M блока, вторые входы ,пянены и являются пятьм информа- циоь-цым нхолом блока, а выходы каждого умножителя группы подключены к пч:ри )му входу одноименног о с -мматора пел цой , пыход которого под- Kjno4en к первому входу одноименной схеГ Ы сравнения первой группы и к инф()ю. входу одноименного кль)ча пер/юй группы, вторые входы всех сумматоров первой группы являются чет()ерт.1,п. информационным входом 6ji(5i;a, выход каждой схемы сравнения nepBi ii rpyrnihi по/1ключе к управляющему н:-:олу одно мер1Ного ключа первой rpynnfii п к «ходу одноименного элемента . группы, выход которого пс. дклю-. чен к у пра :злян1|:1,ему и.чоду одноименно-

го КДК ЧЛ второй группы, .:5ЦИОМ Hi.ifj Плод :оторого объединен с вторым

21

входом одноименной схемы сравнения первой группы, вторые входы всех схем сравнения первой группы являются BTopbw информационным входом блока , выход каждого ключа второй группы подключен к первому входу одноименного сумматора второй группы, выход которого подключен к одноименному входу первой группы информацион ных входов элемента памяти, вторые входы всех сумматоров второй группы объединены и подключены к выходу умножителя и к первым входам вычитате- лей группы, выход каждого вычитате- ля группы подключен к одноименному входу второй группы информационных входов элемента памяти, выходы которого являются выходом блока, такти- руюпр й вход элемента памяти подключен к выходу генератора синхроимпульсов, вход умножителя под1слючен к вторым входам умножителей группы.

От дл. 20

5279522

второй вход каждого вычитателя груп- пы подключен к выходу одноименного ключа четвертой группы, управляющий вход которого под1спючен к выходу 5 одноименного элемента НЕ группы, вход которого подключен к управляющему входу одноименного ключа третьей группы и к выходу одноименной схемы сравнения второй группы, пер10 вый вход которой объединен с информационным входом одноименного ключа четвертой группы и является третьим информационным входом блока, выход каждого ключа первой группы подклю15 чен к информационному входу одноименного ключа третьей группы и к второму входу одноименной схемы сравнения второй группы, выход каждого ключа третьей группы подключен к

20 одноименному входу третьей группы информационных входов элемента памяти.

Фиг.2

От бл. 8

Фчг.З

От бл. 1

От Sfi. 7

- о

5

С Вмда устройства

Фцг.Ц

От Виода устройства

4i .§

Фиг.5

От Ул. 19

От Зл. 13

От $л. 20

Фил.6

Фиг. 7

Dm 5л. 6

От Sji. 6

Ш.

I

W

56

61

j J

ь

60

щ:

Фиг. в

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

Редактор В.Петраш

Составитель Т.Сапунова

Техред И.Верес Корректор Е.Сирохман

Заказ 4622/50Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4