Аналоговое вычислительное устройство для нахождения экстремума функций многихпеременных

 

Взамен ранее изданного

326590

О П И С А Н И Е

ИЗОБРЕТЕНИЯ

k АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Респчблик

Зависимое от авт. свидетельства №

М. Кл. G 06@ 7/38

Заявлено 18.Х|.1969 (№ 1375464/18-24) с присоединением заявки №

Приоритет

Опубликовано 19.|.1972. Бюллетень ¹ 4

Дата опубликования описания 21.XII.1972

Комитет по делам изобретений и открытий при Совете Министров

СССР

УДК 681.332.6 (088.8) Авторы изобретения

Л, М. Бойчук и Ю. В. Костенко

Заявитель

АНАЛОГОВОЕ ВЪ|ЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО

ДЛЯ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИЙ МНОГИХ

ПЕРЕМЕННЫХ вой и второй структур управления соответственно.

Устройство (фиг. 1) предназначено для определения экстремума функции у от переменной х;, заданной в неявном виде:

Функцию F=F(x;, у) в дальнейшем будем называть заданной функцией, а у — оптимизируемой функцией. Функция F должна быть выпукла и иметь непрерывные частные производные первого порядка.

На область изменения переменных и функции у наложены ограничения в виде неравенств:

Функции g, (х;, у) должны иметь непрерывные частные производные первого порядка и определять некоторую выпуклую область.

Уравнение, связывающее те значения переменных, которые удовлетворяют одновременно уравнению (1) и ограничениям (2), можно представить в виде:

Ф(х,, у) =!Р(хт, у) I+ —.a,(х, у) =.О, (3) 1

Изобретение относится к аналоговой вычислительной технике.

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

Однако известные устройства имеют недостаточную точность и быстродействие.

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

Это позволяет повысить точность и быстродействие устройства.

На фиг. 1 приведена общая схема устройства; на фиг. 2 — схема функционального преобразователя; на фиг. 3 и 4 — схемы перР(хт, у) = О, т = 1, 2,...., и. (1) gJ(х,, у)=.0, j=1, 2,..., т. (2) 326590 и

„„ дх;

l — I и

Я 1 дР . дР х,+ — у— : О, дх; ду

c=i где и д (х„у) = 3 (I g j (х,, у)! — д (х,, у)) = О. (4)

j=l

В аналоговых вычислительных устройствах искомые значения переменных фиксируют на выходах интеграторов. В рассматриваемом случае число таких интеграторов ,(l — 8 на фиг. 1) равно n+1, т. е. соответственно числу переменных и оптимизируемой функции.

Значение функции (х;, у) может быть только либо положительным, если значения переменных на выходах интеграторов 1 — 8 не удовлетворяют одновременно уравнению (1) и ограничениям (2), либо равным нулю, если значения переменных удовлетворяют одновременно уравнению (1) и ограничениям (2).

На первом этапе закон управления интеграторами 1 — 8 основан на методе градиента и взят в виде — дР OF

К =х = = — sign Fâ дх; дх, дФ OF 1 = у = — = — sign F— ду ду

m — — (sign g j — 1), (6)

1 %E Ogj

i 1 что определяет такое изменение рассматриваемых переменных во времени, при котором они достигают значений, удовлетворяющих уравнению (3). На втором этапе закон управления интеграторами 1 — 8 взят в виде

U, = х; = + sign, i = 1, 2,..., и, (7) и дР дР

dy дх; что определяет такое изменение рассматриваемых переменных во времени, при котором их значения удовлетворяют уравнению (1), а оптимизируемая функция у в зависимости от знака выражения (8) только увеличивается или только уменьшается. Действительно, при управлении по закону, определяемому формулами (7) — (8), скорость изменения функции F равна нулю при любых значениях этой функции и ее частных производных т. е. значения переменных удовлетворяют уравнению (1), а скорость изменения оптимизируемой функции У знакопостоянная, 5

15 го

Зо

5О

Искомые значения переменных и оптимизируемой функции фиксируют на выходах интеграторов 1 — 8, выполненных, например, на операционных усилителях с емкостной обратной связью. На входы интеграторов 1 — 8 подаются напряжения из блока 4 узла управления (первая структура) на первом этапе решения задачи или блока 5 (вторая структура) на втором этапе. Переключение структур производится контактами реле б, управляемого от функционального преобразователя 7, который реализует зависимость

Ф (х;, у). Если напряжение на входе реле 6 положительно или равно нулю, то его контакты находятся в исходном положении. При поступлении на вход реле б отрицательного напряжения он переключает свои контакты.

С целью упрощения преобразователя 7 его схема составлена таким образом, что он вычисляет значения функции Ф (х;, у) с обратным знаком. Вследствие этого напряжение на выходе преобразователя 7 может быть либо только отрицательным, либо равным нулю.

Это изменение знака функции Ф (х;, у) учтено при выборке характеристики реле б. Если напряжение на выходе преобразователя 7 отрицательно, то реле 6 срабатывает и подает напряжения с выходов блоков частных производных 8 — 10, реализующих частные производные заданной неявной функции

OF дР на выход первой структуры дх; ду управления с помощью контактов 11 — 18. Если же указанное выше напряжение равно нулю, то напряжение с выходов блоков частных производных 8 — 10 подают на вход второй структуры управления через контакты

14 — 16. Схемы блоков 4, 5 построены таким образом, что они вырабатывают сигналы управления интеграторами 1 — 8 только в том случае, если на их вход поступают напряжения с выходов блоков частных производных 8 — 10.

Схема функционального преобразователя

7 показана на фиг. 2. Выходные напряжения интеграторов 1 — 8 поступают на входы функциональных преобразователей 17 — 20, которые определяют значения заданной функции

F (преобразователь 17) и функции ограничений g (преобразователи 18 — 20). Выходные напряжения преобразователей 17 — 20 поступают на выходы двухпозиционных реле

21 — 24 и на их контакты 25 — 28. Выходное напряжение преобразователя 17 подают также на вход инвертора 29, а с его выхода— на контакты 80 реле 21, При положительном напряжении на выходе преобразователя 17 срабатывает реле 21, замыкает нормально разомкнутые контакты 80, и напряжение с выхода инвертора 29 поступает на вход сумматора 81, при отрицательном значении оно поступает на вход сумматора 81 через нормально замкнутые контакты 25. Если выходные напряжения преобразователей 18 — 20 отрицательны, то через нормально замкнутые

326590

5 контакты 26 — 28 они поступают на вход сумматора 81. Если же они положительны, то срабатывают соответствующие реле 22 — 24, размыкают контакты 26 — 28 и отключают выходы этих блоков от сумматора 31. На выходе сумматора 81 получаем, таким образом, напряжение, величина которого равна отрицательному значению функции Ф (х;, у).

Схема первой структуры управления показана на фиг. 3. На входы блоков управления 32 — 84 подают напряжения с выходов интеграторов 1 — 8, а также с выходов блоков 8 — 10. На выходах блоков 82 — 84 получают управляющие напряжения для интеграторов 1 — 8 на первом этапе управления. На фиг. 3 раскрыта также схема блока 88, структура которого одинакова для всех блоков 82 — 84. Выходные напряжения интеграторов 1 — 3 поступают на входы блоков 85 — 37, напряжения на выходах которых равны частным производным функций ограничений рт)д;)д„по соответствующей переменной (в данном случае по х;). Выходные напряжения блоков 85 — 87 поступают на вход силителя 88 через контакты 89 — 41 реле 22 — 24.

Выходное напряжение блока 9 подают на вход суммирующего усилителя 88 через нопмально замкнутые контакты 42 реле 21 или через инвертор 48 и термально разомкнутые контакты 44. На выходе усилителя 88 получаем напряжение, соответствующее зат<ону уппавления (5).

На вход схемы второй структуры управления (фиг. 4) поступают напряжения с выходов блоков 8 — 10. Напряжения с вы одов блоков 8 — 9 подают на входы инверторов 45.

46, нормально замкнутые контакты 47, 48 двухпозиционных реле 49, 50 и контакты 51, 52 переключателя знака. Этим переключателем подключают реле 49, 50 к выходам блоков 8, 9 (чепез контакты 51, 52) ппи поиске максимума или к выходам инверторов 45, 46 (чепез контакты 58, 54) IIDH поиске минимума. При подаче на входы реле 49, 50 положительных напряжеттий эти r ë<. вклточяются и замыкают свои контат<ты 55, 56. Через эти контакты няппяжения с выходов инверторов

45, 46 подают на вход усилителя 57. При подаче на реле 49, 50 отрицательных напряжений эти реле не включаются, а напряжения с выходов блоков 8, 9 через контакты 47, 48 подают на вход усилителя 57, Напряжение с выхода усилителя 57, которое является управляющим напряжением для интегпатопа 3. подают на инвертор 58 и контакты 59. 60 переключателя знака. Выхо.т усилителя 57 полт<лючают «интегратору 3 чепез т<онтякт 60 (при поиске мя«симумя) или через инвертоп

58 и контакт 59 (при поиске минимума). Управляющие напряжения по остальным переменным получают с выхода или входа инвертора 61 в зависимости от положения контактов 62 — 65 реле 49, 50.

В качестве элементов устройства используют, например, операционные усилители, 5

15 гю

25 зо

65 двухпозиционные электромагнитные реле и функциональные преобразователи, выполненные, например, на диодах и резисторах.

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

Пусть в начальный момент времени значения переменных на выходах интеграторов

1 — 8 не удовлетворяют уравнению (1) и ограничениям. Тогда напряжения на выходах преобразователей 18 — 20 отрицательны, и соответствующие реле 22 — 24 своими контактами 26 — 28 подключают выходы преобразователей 18 — 20 ко входам сумматора 31. На выходе преобразователя 17 получают напряжение, равное значению функции F. Если это напряжение положительное, то оно включает реле 21, контакты 80 которого подключают выход инвертора 29 ко входу сумматора 81.

Если же это напряжение отрицательное, то контакты 25 подключают выход преобразователя 17 ко входу сумматора 81. В любом случае на вход усилителя 81 подают абсолютную величину заданной функции со знаком минус. На выходе сумматора 31 получают напряжение, отличное от нуля. Это напряжение включает реле б, которое своими контактами 11 — 18 подключает выходы блоков 8 — 10 ко входам первой структуры. Выходные напряжения блоков 8 — 10, равные частным производным заданной функции по переменным х;, у, подают на вход соответствующих блоков управления 82 — 84. Напряжение, например, в блоке 83 поступает на вход инвертора 43 и на контакты 42 реле 21.

Если значение заданной функции положительное, то это напряжение включает реле 21, и его контакты 44 подключают выход инвертора 43 ко входу усилителя 88. Если же значение функции F отрицательно, то контакты

42 подключают ко входу усилителя 38 вход инвертора 48. На выходе усилителя 88 получают управляющее напряжение для интегратора. Управляющие напряжения с выходов блоков 32 — 34 подают на выходы соответствующих интеграторов 1 — 8. При этом переменные на выходах интеграторов 1 — 8 приближаются к значениям, соответствующим заданной функции и ограничениям.

По мере того, как переменные достигают значений, соответствующих ограничениям, на выходах преобразователей 18 — 20 напряжения становятся положительными и включают реле 22 — 24, которые размыкают контакты

26 — 28 и отключают входы сумматора 81 от выходов преобразователей 18 — 20, Аналогичные переключения происходят на входе усилителя 88.

Дальнейшее изменение переменных происходит таким образом, что пх величины приближаются к значениям, удовлетворяющих уравнению (1). При этом одна или несколько переменных могут снова выйти из ограничений. В этом случае происходит повторное отключение соответствующих реле 22 — 24, и на входе блоков 82 — 84 получают напряжения, которые приводят к тому, что перемен326590

45 ные на выходах интеграторов 1 — 8 снова достигают значений, соответствующих ограничениям.

Когда переменные на выходах интеграторов 1 — 3 достигают значений, удовлетворяющих уравнению (1) и ограничениям, на выходе преобразователя 7 получают напряжение, равное нулю. При этом реле б отключается, и его контакты 14 — 1б подключают выходы блоков 8 — 10 ко входам второй структуры управления. Напряжения с выходов блоков

8 — 10 подают на вход усилителя 57 через контакты 47, 48, если определяется минимум оптимизируемой функции и значения частных производных оптимизируемой функции по всем переменным отрицательны или если определяется максимум, а значения частных производных положительны. При этом на реле 49, 50 подают отрицательные напряжения, и они не срабатывают. В противном случае на реле 49, 50 подают положительные напряжения, они срабатывают и переключают свои контакты. Тогда напряжения с выходов блоков 8 — 10 подают на вход усилителя 57 через инверторы 45, 4б и контакты 55, 5б реле 49, 50. Выходное напряжение усилителя

57 через контакты бО, если определяется максимум, или через инвертор 58 и контакты 59, если определяется минимум, подают на вход интегратора 8, на выходе которого получают значение оптимизируемой функции. Управляющие напряжения по остальным переменным снимают со входа или выхода инвертора 51 в зависимости от положения контактов б2 — б5 реле 49, 50. Полученные управляющие напряжения подают на входы соответствующих интеграторов 1, 2. При этом переменные на выходах интеграторов изменяются таким образом, что в любой момент времени их значения удовлетворяют уравнению (1), а оптимизируемая функция стремится к экстремуму. Если этот экстремум находится в области ограничений, то при достижении его управляющие напряжения на входах интеграторов 1 — 8 становятся равными нулю и изменение переменных прекращается, Если экстремум находится вне области ограничений, то величины переменных достигнут границы области ограничений. При этом нарушается одно или несколько условий д;(х;, у) )О и появляется напряжение на выходах преобразователей 18 — 20 и блоков

85 — 37, которые включают реле 22 — 24. Напряжение на выходе сумматора 81 включает реле б, которое переключает выходы блоков

8 — 10 со входов второй структуры на входы первой структуры. Под действием первой структуры на выходах интеграторов 1 — 8 снова устанавливаются значения переменных, удовлетворяющих уравнению (1) и ограничениям и происходит переключение на вторую структуру. В устройстве устанавливается режим колебаний переменных вблизи точки экстремума функций.

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

Предмет изобретения

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

1Риг A

Редактор Л. Утехина

Заказ 3959/2 Изд. № 1691 Тираж 448 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

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

Типография, пр. Сапунова, 2

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

Техред Е. Борисова

Корректоры Л. Новожилова и В. Жолудева