Патент ссср 410409

 

р;,";-;.: .

ОПИCАНИЕ

ИЗОБРЕТЕ Й Кя.г (418469

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

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

Республик

И АВТОРСИОМУ CBN,.@ôÈÏÜÑ7ÁÓ

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

Заявлено 28.VI.1971 (№ 1674089/18-24) с присоединением заявки №

Приоритет

Опубликовано 05.1.1974. Бюллетень ¹ 1

Дата опубликования описания 27Х.1974

М. Кл. G 06g 7/40

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

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

УДК 681.335:51(088 8) Авторы изобретения

Л. М. Боичук и 1О. В. Костенко

Ордена Ленина институт кибернетики АН Украинской ССР

Заявитель

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО

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

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

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

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

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

Блок-схема устройства приведена на чер15 теже.

Она содержит интеграторы 1 — 3 для изменения переменных, интегратор 4 для изменения вспомогательной переменной, блок ограничений

5, который вычисляет значения функций огра20 ничений, блок логики 6, который определяет наименьшее из значений функций ограничений и производит переключения в блоке частных производных 7 вспомогательной функции, блок 8 для вычисления значений вспомога25 тельной функции, основной блок управления

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

30 11 для формирования вспомогательных управ410409

Ul — х1 аФФ1 — g Х (6) 15 где дФ д<Ь

Ф1— дх; z (7) (8) 25

z == — U, = U,.+U„ где

60 ляющих напряжений; реле управления 12 с нормально замкнуты 1и контактами 13 — б для подачи вспо.i огатсльпь. х управляющих на" пряжений на входы пп-еграторов 1 — 4.

Выходы интеграторов 1 — 3 подключены ко входам блока пер"=крестных свя";.é 10, блока ограничений 5 и бл;KQ чаcTIIbrх производных

7, выход иптегратора вспомогательной геременной 4 подключен ко входам блока частных производных 7 и блока вспомогательной функции 8. Выходы блока. Ограничений 5 соединены со входами блока логи II б, выходы которого соединены со входами блока вспомогательной функции 8 и блока час-.Hblx ппоизводных 7.

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

9, блока перекрестных связей 10 и вспомогательного блока управления 11. Выход блока вспомогательной функции 8 соединен со входом основного блока управления 9 и реле управления 12. Выходы основного блока управления 9 подключены ко входам интеграторов 1 — 4. Выходы блока перекрестных связей 10 соединены со входами вспомогате.; ь "oro блока управления 11, выходы которо"o;врез нормально замкнутые контакты 13 в l6 ;;е. .» управлениями

12 подключены 10 B. :oëам интеграторов 1 — 4.

Устройство предпазначе: о,для определения значений переменных х; (i =- 1,2, ..., n), при которых целевая функция у ==- f(x„x„..., х„) (1) достигает наибольш;.го (или наименьшего) значения в допустимой области, определяемой системой ограничений ду (х,э х„..., х„) =..-. О / = 1, 2,..., ol (2)

Функция f, (х„..., х„) должна быть выпукла и иметь непрерывные частные производные первого порядка. Функции Я1(„х,,..., х„) должны иметь IIo.. ечывпые част: ые производные первого пор. :...;а;. or рсдел-.ть некоторую выпуклую область.

Все неравенor= .а (2) сводят к одному нераве1?ству с помощ!-ю логической Операции обобще ной коныонкции

G =.,r, 7,... / д„,:= О. (3) Эта логическая функция отличается тем, что в любой момент времени ее значение равно наименьшему из значений сравниваемых функций.

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

Ф (х„..., х„, z) =- G (х,, х„) — — kz = О.

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

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

1 — 1 и

Q С,1Ф, —, C«0)1 — С„Ф,; (5)

l-1 l-=l+1

У : — z: — аФФ вЂ” "(С1 Фп

1=1

1 при Ф О! О при Ф(О

Cl, — — C,l — +(fl6Ir — f,Ô,) 1) i;

Cl = :(1Ф

B выражениях (7) и (9) знак «плюс» соответствует поиску, максимума целевой функции (1), а знак «минус» — поиску минимума.

Управляющие напряжения (5) и (6) Обеспечивают такое изменение переменных х,,..., х„, z при котором изображающая точка из любого начального положения выходит на гиперповерхность (4) и движется по ней в направлении увеличения (или уменьшения) целевой функции.

Из выражения (4) следует, что: д0

Ф1 = дх1

40 т. е. частные производные вспомогательной функции Ф(х„..., х„, z) по переменнымх„х„..., х„равны частным производным той функ ции ограничений gl(х„...,х„), значение кото

45 рой наименьшее в данной точке пространства переменных х,, х,,..., х„.

Выражения (5) и (б) можно подставить в следующем виде: х;:- Ul —— Ul — 1 г + Ы;

Ul = — аФФ1, U — аФФ управляющие напряжения, вырабатываемые основным блоком управления 9, l — 1 и

Ul С,1Ф, — g С«Ф,+С„Ф„.

1=1 1=1+1 управляющие напряжения, вырабатываемые

65 вспомогательным блоком управления 11.

410409

40

5

Таким образом, устройство имеет переменную структуру. Первая структура работает в том случае, когда значения переменных на выходах интеграторов 1 — 3 не удовлетворяют условию Ф) О. При этом 7 = О и устройство приводит переменные к соотношению (4). Вторая структура работает в том случае, когда значения переменных удовлетворяют условию

Ф) О. При этом у = 1 и устройство изменяет переменные так, чтобы выполнять условие (4) и одновременно увеличивать (или уменьшать) целевую функцию. Когда переменные достигают значений, соответствующих условию (4), дальнейшее их изменение происходит -в направлении оптимизации целевой функции при поддержании между ними соотношения (4) . ,Пусть, например, начальные значения:пере-: менных на выходах интеграторов 1 —,4 таковы, что значение первой функции ограничений

g, (х„х,,..., х„) отрицательно, а значения остальных двух функций положительны.

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

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

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

Ф(х„х„...,х„, г)с обратным знаком. С выхода блока вспомогательной функции 8 напряжение подают на вход основного блока управления

9 и реле управления 12. Так как в рассматриваемом случае значение вспомогательной функции Ф (х„х„..., х„, z) отрицательно, то на реле управления 12 с выхода блока вспомогательной функции 8 подают положительное напряжение, в результате чего реле управления

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

10 напряжения, равные значениям коэффициентов перекрестных - связей. Управляющие напряжения, которые подают на входы интеграторов 1 — 4 с выходов вспомогательного блока управЛения 11, обеспечивают такое изменение переменных на,выходах интеграторов 1 — 4,-- при котором целевая функция увеличивается (или уменьшается) при сохранении неизменного значения вспомогательной функции Ф (х„х„..., х„, z).

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

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

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

449499

Составитель О. Сахаров

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

Корректор:В. Брыксина

Редактор Т. Орловская

Заказ 1072/9 Изд. № 337 Тираж 624 Подписное,ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

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

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