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

 

О Il И C:-А----Н И-Е

ИЗОБРЕТЕН ИЯ 477428

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

Социвлистицеских

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (б1) Дополнительное к авт. свид-ву— (22) Заявлено 15,02.74 (21) 1998364/18-24 с присоединением заявки №вЂ” (23) Приоритет—

Опубликовано 15.07.75. Бюллетень № 26

Дата опубликования описания 09.03.76 (51) М. Кл. G 06g 7/38

Государственный комитет

Совета Министров СССР

Il0 делам изооретений и открытий (53) УДК 681.333:51 (088.8) (72) Авторы изобретения

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

Ордена Ленина институт кибернетики AH Украинской ССР (71) Заявитель

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

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

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

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

2 блоков умножения второй и четвертой групп.

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

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

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

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

На фиг. 1 приведена блок-схема устрой2р ства; на фиг. 2 — схема блока тангенциального управления

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

3р ограничений и производит переключения в (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

477428

3 схеме блока частных производных 7, вычи!:ляющего значения частных производных вспомогательной и оптимизируемой функций, блок вспомогательной функции 8 для вычисления значений вспомогательной функции, основной блок управления 9, формирующий нормальные управляющие напряжения для интеграторов 1 — 4, блок тангенциального управления 10 для формирования тангенциальных управляющих напряжений и реле управления 11 с нормально замкнутыми контактами 12 — 15 для подачи тангенциальных управляющих напряжений на входы интеграторов 1 — 4.

Блок тангенциального управления (см. фиг. 2) содержит блоки умножения 16 — 29 и суммирующие усилители 30 — 25.

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

Выходы блока ограничений 5 соединены со входами блока логики 6, выходы которого соединены со входами блока вспомогательной функции 8. Переключающие контакты релейных элементов блока логики 6 включены в схему блока частных производных 7, выходы которого соединены со входами основного блока управления 9 и блока тангенциального управления 10.

Выход блока вспомогательной функции 8 соединен со входом основного блока управления 9 и реле управления 11. Выходы основного блока управления подключены ко входам соответствующих интеграторов 1 — 4.

Выходы блока тангенциального управления 10 через нормально замкнутые контакты 12 — 15 реле управления 11 подключены ко входам соответствующих интеграторов 1 — 4.

В блоке тангенциального управления (см. фиг. 2) входы блоков умножения 16 — 18 соединены со входами блоков умножения, соответственно 20 — 22 и 26 — 28.

Выходы блоков умножения 20 — 22 соединены со входами блоков умножения, соответственно, 23 — 25. Входы блока умножения 19 соединены со входом блока умножения 29.

Выходы блоков умножения 16 — 19 подключены ко входу суммирующего усилителя 30, выход которого соединен со входами блоков умножения 23 — 25.

Выходы блоков умножения 23 — 25 подключены ко входам суммирующих усилителей, соответственно, 32 — 34, Выходы блоков умножения 20 — 22 подключены ко входу суммирующего усилителя 31, выход которого соединен со входами блоков умножения 26 — 29.

Выходы блоков умножения 26 — 28 подключены ко входам суммирующих усилителей, соответственно, 32 — 34. Выход блока умножения 29 соединен со входом усилителя 35.

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

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

Устройство (см. фиг. 1) предназначено

5 для определения значений переменных Х!, Х, ..., Х„, при которых оптимизируемая функция

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

15 g,(xi, х,...,х„)) 0, j = 1, 2,..., m. (2) Функция у должна быть выпукла и иметь непрерывные частные производные первого порядка. Функции g (xi, х, ..., х„) должны

20 определять выпуклую область.

Все неравенства (2) сводят к одному неравенству с помощью логической операции обобщенной конънжции

25 6 (х) = д!Лд Л " Лд,„) 0. (3) Эта логическая функция обладает той особенностью, что в любых значениях переменных х; ее значение равно наименьшему

30 из значений сравниваемых функций.

Неравенство (3) сводится к равенству путем введения вспомогательной переменной z.

U, = х; = — аФФ; — vP (yi(Z Ф . +Ф )—

i=! — Ф,Х Ф,у;), (5)

Л

U. =z — аФФ„+фФ Х Ф;у;, (6) где ix=ccnst)0 1 1 при Ф)0

P=const)0 0 при Ф(0, Ф;=;Ф,=; у;=

9р 69 бу

6х! 62 бх

Управляющие напряжения U; и U, 55 обеспечивают такое изменение переменных

Ф (х!, xg,...,х„, z) = G (х!, х,...,xÄ)—

35 1

rcz =0 (4)

Равенство (4) описывает гиперповерхность

Ф b (а+1)-мерном пространстве переменных х!, х, ..., х„, z, все точки которой удов40 летворяют неравенству (3). Искомая экстремальная точка, удовлетворяющая ограничениям (2), обязательно должна находиться на гиперповерхности Ф.

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

50 о и

477428

56

Ф

U; = х; = U, . + Y U;., U = z = U, +v U,", 60

5

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

Из выражения (4) следует, что т. е. частные производные вспомогательной функции Ф (х!, х>, ..., х„, z) по переменным

xi, x>, ..., х„равны частным производным той функции ограничений g (xi, x>, ..., х„), значение которой наименьшее в данной точке пространства переменных х>, х2, ..., х„

Выражения (5) и (6) можно представить в следующем виде где U,. = — аФФ„U, = — аФФ, — управляющие напряжения, вырабатываемые основным блоком управления 9, и л

U ; — P fy;(Z Ф2 +Ф ) — Ci;Z Ci; ;);

i=! i-1

U," — рФ,, » Ф,.y,-—

i-! управляющие напряжения, вырабатываемые блоком тангенциального управления 10.

Устройство имеет переменную структуру.

Первая структура работает в том случае, когда значения переменных на выходах интеграторов не удовлетворяют условию Ф)) О.

При этом v=О, и устройство приводит переменные к соотношению (4) .

Вторая структура работает в том случае, когда значения переменных удовлетворяют условию Ф) О. При этом v=1, и устройство изменяет переменные так, что значения функций Ф (xi, х,, х„, z) и f (xi, x>, ..., х„) уменьшаются. Когда переменные достигают значений, соответствующих условию (4), дальнейшее их изменение происходит в направлении уменьшения оптимизируемой функции у при поддержании между ними соотношения (4).

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

С выхода блока ограничений 5 напряжения

<0

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

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

На выходе блока частных производных 7 получают также значения частных производных оптимизируемой функции. С выходов блока частных производных напряжения, равные значениям частных производных вспомогательной функции, подают на входы основного блока управления 9 и блока тангенциального управления 10. На вход блока тангенциального управления подают также с выходов блока частных производных 7 напряжения, равные значениям частных производных оптимизируемой функции. С выхода блока логики 6 напряжение подают на вход блока вспомогательной функции 8. На вход этого же блока подают значение вспомогательной переменной z с выхода интегратора 4 вспомогательной переменной 4. На выходе блока вспомогательной функции 8 .получают напряжение, равное значению вспомогательной функции Ф (х!, х,,х„, z) с обратным знаком.

С выхода блока вспомогательной функции 8 напряжение подают на вход основного блока управления 9 и реле управления 11.

Так как в рассматриваемом случае значение вспомогательной функции отрицательно, то на реле управления 11 с:выхода блока вспомогательной функции 8 подают положительное напряжение, в результате чего реле управления размыкает контакты 12 — 15. С выходов основного олока управления 9 HB Bxo. ды соответствующих интеграторов 1 — 4 подают управляющие напряжения, которые обепечивают такое изменение переменных на выходах интеграторов 1 — 4, при котором наиряжение на выходе блока ограничений 5, равное значению первой функции ограничений, уменьшается (ио абсолютной величине) .

Когда напряжение на выходе блока логик!г 6 достигает нуля, реле управления 11 замыкает контакты 12 — 15 и подключает выходы блока тангенциального управления 10 ко входам интеграторов 1 — 4. С выходов блока тангенциального управления 10 на входы соответствующих интеграторов 1 — 4 подают управляющие напряжения, обеспечивающие такое изменение перемененных на выходах интеграторов 1 — 4, при котором значение оптимизируемой функции уменьшается при сохранении неизменного значения вспсмогательной функции.

47 7428

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

Блок тангенциального управления 10 работает следующим образом.

Напряжения, равные значениям частных производных вспомогательной функции, подают на входы блоков умножения 16 — 19, 20 — 22 и 26 — 29.

Напряжения, равные значениям частных производных оптимизируемой функции, подают на входы блоков умножения 20 — 22 и

23 — 25. С блоков умножения 16 — 19 напряжения, равные квадратам значений соответствующих частных производных, подают на вход суммирующего усилителя 30, выходное напряжение которого поступает на входы всех блоков умножения 23 — 25.

Выходные напряжения блоков умножения

20 — 22 подают на вход суммирующего усилителя 31, с выхода которого напряжение подают на входы всех блоков умножения

26 — 29. Выходные напряжения блоков умножения 23 — 25 и 26 — 28 попарно подают на входы суммирующих усилителей 32 — 34, на выходах которых получают тангенциальные управляющие напряжения для интеграторов

1 — 3 основных переменных (см. фиг. 1).

Выходное напряжение блока умножения 29 подают на вход усилителя 35, на выходе которого получают тангенциальное управляющее напряжение для интегратора 4 вспомогательной переменной 4 (см. фиг. 1).

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

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

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

4О суммирующих усилителей, выходы которых соединены с выходами блока.

477428

Составитель Н, Шелнпова

Редактор F Семанова Техред М. Семенов Корректор О. Тюрина

Заказ 7690 Изд. № 1659 Тираж 679 Подписное

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

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

МО I, Загорский филиал