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

 

(i i) 480090

ОПИСА ИЕ

ИЗОБРЕТЕНИЯ

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

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

Ресо оаo_#_ (61) Дополнительное к авт. свид-ву (22) Заявлено 08.02.74 (21) 1994726/18-24 сприсоединение,м заявки № (51) М. Кл. б Об<у 7/38 (23) Приоритет

Совета Министров СССР па оелач изобретений Опубликовано 05.08.75. Бюллетень Ъа 29 (53) УДК 681.333:51 (088.8) и открытий

Дата опубликования описания 11.03.76 (72) Автор изобретения

Л. М. Бойчук

Ордена Ленина институт кибернетики АН Украинской ССР (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

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

Устройство содержит блок интеграторов 1 для изменения переменных; блок сумматоров

2, блок ограничений 3 для формирования сигнала, зависящего от функций ограничений и их градиентов; блок коэффициентов 4 для задания скорости движения и допустимой области; блок градиента 5 оптимизируемой функции; блок усилителей 6 для задания направления и скорости движения к экстремуму и

5 блок ортогонализации 7.

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

11 множительных устройств для умножения

15 вектора управления на выходе канала ограничений на выходное напряжение блока 10, блок 12 для вычитания напряжений на выходах блока усилителей 6 и на выходах блока 11.

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

480090.

15

20 (8) 25

35 (9,а) 1=т,(vf М) Hpííûå, например, на операционных усилитеЛЯХ.

Устройство предназначено для нахождения значений переменных, при которых функция

/ -- /(х), (1) где х — n-мерный вектор, достигает экстремума в допустимой области изменения переменных, определяемой системой ограничений в форме равенств и(или) неравенств д = — g.(õ) .О; / = — 1, т. (2)

Требуемое изменение во времени переменных производится с помощью интеграторов блока 1, описываемых дифференциальными уравнениями х= — и, (2,а) где U — вектор управляющих воздействий интеграторов.

Закон управления интеграторами таков и1+ pàî (3) где Р— вектор управления, определяющий движение к допустимой области (2); (Р— ортогонализованный вектор оптимизации, определяющий движение к экстремуму функции (1) .

Основное требование к векторам U и U o заключается в том, чтобы они всегда были ортогональны, т. е. их скалярное произведение должно быть равно нулю (и, и") = О. (4)

Вектор управления U формируется так же, как и в схеме прототипа, т. е. по методу

«штрафных» функций:

LL =- 7.vg. (5) где а(0 — коэффициент, определяющий скорость движения к допустимой области и реализуемый в блоке 4, а Vg — градиент некоторой положительно определенной функции ограничений

g = а(а а.) (5,а)

Градиент Vg получают в блоке 3. Вид функции (5, а) выбирают таким, что при выполнении условий (2), т. е, в допустимой области, выполняются также соотношения

g=.О, va=0. (5,б)

Вектор оптимизации Р равен и = ", Ь (6) где V f — градиент функции (1), получаемый в блоке 5; уо — коэффициент, определяющий направление и скорость движения к экстремуму функции (1) и реализуемый в блоке 6.

Ортогонализованный вектор оптимизации (6) можно вычислить, например, по формуле (" " ) .u, (7) (и, и ) 40

4 которая определяет структуру блока 7 (фиг. 2). В этой формуле J U, U (— скалярное произведение векторов (5) и (6), реализуемое в блоке 8; Р, Ь вЂ” квадрат модуля вектора (5), реализуемый в блоке 9, Требуемая для реализации выражения (7) операция деления производится в блоке 10, операция умножения — в блоке 11, операция вычитания векторов — с помощью блока 12.

При законе управления (3) скорость изменения функции ограничений (5, а) с учетом выражений (2, а, 5) равна

g==(vg х) =-(va ) ="(va М)+

+ — (и, и"). а

Так как а(0 и в силу свойства ортогональности (4), это выражение примет вид

g а (va, лд) О, что определяет устойчивое монотонное движение к допустимой области (2), независимое о изменения оптимизируемой функции (1).

Скорость изменения оптимизируемой функции при законе управления (3) равна

f Ì х) = (Vf и) = (Vf и ) + (Vf ") (9)

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

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

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

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

4soooo фиг 1

Фиг 2

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

Техред М. Семенов

Корректор Е. Рожкова

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

Заказ 122/16 Изд. № 934 Тираж 679 Подписное

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

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

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

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

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

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