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

 

ii 497602

ОП ИСА НИ Е

ИЗОБРЕТЕН ИЯ

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

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

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

Республнк (61) Дополнительное к авт. свид-ву (22) Заявлено 23.01.73 (21) 1878718/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 30.12.75. Бюллетень № 48 (51) М, Кл. С 06g 7/48

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

Совета Министров СССР оо делам изобретений н открытнй (53) УДК 681.333(088.8) Дата опубликования описания 23.03.7б (72) Автор изобретения

Л. М. Бойчук

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

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

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

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

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

30 блок инверторов; к третьей группе входов бло497602

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

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

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

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

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

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

Блок формирования 8 весовых коэффициентов (фиг. 2) содержит блок решения линейных уравнений 11, инверторов 12, блок квадраторов 13 для получения квадратов выходных напряжений блока интепраторов 9, блок квадрата модулей градиентов ограничений 14„ блок скалярных произведений 15 градиентов ограничений; блок скалярных произведений 16

65 градиента оптимизируемой функции на векторы градиентов ограничений; блоки сумматоров

17, 18, 19; блоки усилителей 20, 21. Блоки 13, 14, 15, 18 предназначены для получения напряжений, пропорциональных коэффициентам указанной выше системы линейных уравнений, а блоки 12, 16, 17, 19, 20, 21 — для получения напряжений, пропорциональных свободным членам этой же системы.

Выход первого блока интеграторов 1 (фиг. 1) подключен ко входам блока 3, блока

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

В блоке формирования 8 весовых коэффициентов (фиг. 2) выходы блока квадраторов

13 подключены ко входам первого блока усилителей 20 и к одной группе входов второго блока сумматоров 18. Выход блока квадрата модулей градиентов ограничений 14 подключен к другой группе входов блока 18. Выходы блока 15 скалярных произведений градиентов ограничений подключены к одной из групп входов блока решения системы линейных алгебраических уравнений 11. Выходы блока

16 скалярных произведений градиента оптимизируемой функции и градиентов ограничений подключен к одной группе входов первого блока сумматоров 19, выходы которого подключены ко входам блока инвертэров 12, Выходы блока 20 подключены к одной группе входов третьего блока сумматоров 17, выходы которого подключены ко входам блока усилителей 21. Выходы второго блока усилителей

21 подключены к другой группе входов блока 19. Выход блока 18 подключен к одной из групп входов блока 11. Выходы блока инверторов 12 подключены к одной из групп входов блока 11. Блок формирования 8 связан с остальными блоками предлагаемого устройства следующим образом. Одна группа входов блока 17 подключена к выходам блока 5. Входы блока 13 подключены к выходам блока 9.

Входы блока 14 и одна из групп входов блока

15 и блока 16 подключены к выходам блока 4.

Одна из групп входов блока 16 подключена к выходам блока 2, 49760 2

60

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

f f(õ„..., х) лостигает экстремума в допустимой области изменения переменных, определяемой системой ограничений в форме равенств и неравенств:

g;,о,. (х„..., х„) (0, f =- 1, т .

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

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

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

Напряжения на входе второго блока интеграторов 9 начнут изменяться так, что напряжения на выходе блока квадраторов 13 увеличиваются. Когда основные переменные, т. е. напряжения на выходах блока 1 достигнут допустимой области, напряжения на выходах блока сумматоров 17 станут равными нулю.

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

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

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

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

- вого блока усилителей соединены с выходами блока квадраторов и второй группой входов второго блока сумматоров; выходы второго блока усилителей соединены со второй группой входов первого блока сумматоров.

497602

Составитель Е. Тимохина

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

Корректор М, Лейзерман

Редактор Н. Коляда

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

Заказ 363/17 Изд. № 2085 Тираж 679 Подписное

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

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