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

,М.Пол 1981.ССР 77,ЗАДАЧРЕСУРС ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ ЛИСАНИЕ К АВТОРСКОМУ СВИДЕТЕЛЬ(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ(57) Изобретение относится к вычислительной технике, Целью изобретения является повышение производительности, Устройство содержит переключатели 1, 2 и 3, блоки 4 задания нелинейности, блок 5 умножения,сумматор 6, дифференцирующий блокблок 8 определения экстремума, интегратор 9, блоки 10 масщтабирования, сумматор 11, блок 12 сравненияс константой, блок 13 регистрации,блок 14 отображения, элемент 15 задержки, 1 ил,1134Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системахуправления.Цель изобретения - повьшение производительности.На чертеже представлена блок;схема устройства.Устройство содержит переключатели 1, 2 и 3, блоки 4 задания нелинейности, блок 5 умножения сумматор 6, дифференцирующий блок 7, блок8 определения экстремума, интегратор9, блоки 10 масштабирования, сумматор11, блок 12 сравнения с константой,блок 13 регистрации, блок 14 отображения, элемент 15 задержки,Устройство предназначено для автоматического решения широкого класса задач нелинейного программирования, сводящихся к нахождению минимума функцииС = ппп Х с 1 . (х .)3 3при ограниченияхкЙ. х.сЭ,/=1Для решения этой задачи в устройстве используется метод множителей Лагранжа, который позволяет свести задачу поиска экстремума функции 1 переменных к поиску экстремума функции одной переменной для заданного значения множителя Лагранжа , Функция Лагранжа имеет вид1 кЯ(х,Л)= 2. пппс 1. (х )+Ай. х .Оптимальные значения х (1=1 1 с) при заданном 1 находятся из решения уравнения1654верки удовлетворения найденных оптимальных значений х.(1=1 к) это перво) . 5начальное значение корректируется с, учетом отклонений полученного значения затрат Вп от заданного ограничения Р до тех пор, пока не выполнится равенство П=Р. После этого процесс коррекции 3 прекращается и зада 10 ча считается решенной, Устройство автоматически после нахождения экстре 1520 2530 35 40 мума по одной переменной (т,е, после нахождения очередчого оптимального значения х .) переходит к нахождению экстремума по другой переменной последовательно для всех переменных, Кроме того, устройство автоматически производит коррекцию выбранного множителя Лагранжа Л до тех пор, пока не выполнится условие Э =0 и автоматиически регистрирует и отображает результаты решения задачи х .(1=1,1 с).3Устроиство работает следующим об- разом.В исходном состоянии интегратор 9, блок 8 определения экстремума и сумматор 11 установлены в нулевое состаяние, Переключатель 3 соединяет источник входного сигнала с входом интегратора 9 для задания аргументов оптимизируемой функции, Кроме того, через переключатель 3 источник входного сигнала подключается к переключателю 2, который в исходном положе- нии соединяет его через один иэ блоков (вначале через первый блок 10) с соответствующим входом сумматора 11.С выхода интегратора 9 сигнал через переключатель 1 поступает на входодного из блоков 4 (сначала на входпервого блока 4), так как частные про-- с 1, (х.)+Лспо. х. = О,аах, 1 13Таким образом, задача сводится кнахождению частных производных заданной функции по всем переменными нахождению значений аргументов х.при которых производные равны нулюдля заданного множителя Лагранжа.Наибольшую трудносТь в этой задачесоставляет выбор множителя Лагранжа,при котором найденные оптимальныезначения х:(х=1 1 с) удовлетворяли быйзаданным ограничениямПроцесс выбора необходимого 4 заключается в том, что сначала выбирается первоначальное значение Я,= Л с 1а затем по мере решения задачи и про 45 50 55 производные находятся по всем переменным х, последовательно, т,е, сначала для х затем для х и т,д.,также последовательно находятся иоптимальные значения х (1=1 Е), Наблоке 5 установлено в исходном состоянии значение множителя Лагранжа3= 3 д, . Одновременно с выхода интегратора 9 сигнал поступает на входблока 5, в котором он умножается наустановленное значение В Й С выхода одного из блоков 4 и с выхода блока 5 сигналы поступают на соответствующие входы сумматора 6, в которомони складываются. Суммарный сигнал свыхода сумматора 6 поступает на входдифференцирующего блока 7, которыйвырабатывает сигнал, пропорциональный3 13 производной Ьункциио (х1 хпо аргументу х, . Этот сигнал поступает на информационный вход блока 8, который при перемене знака производной выдает сигнал свидетельствующий о нахождении экстремума (в частности минимума) функции Гс 1,(х,)+Эх, . Сигнал с выхода блока 8, свидетельствующий о нахождении экстремума по первой переменной х, и, следовательно, о нахождении оптимального значения х используется для управления дальнейшей работой устройстваЭтот сигнал с выхода блока 8 посту- . пает на его вход, устанавливая его в нулевое состояние, исходное для индикации об экстремуме следующей Функции Ц (х)+д, Х, . Одновременно с этим сигнал с выхода блока 8, поступая на управляющий вход переключателя 3, прекращает подачу через него на вход интегратора 9 и вход переключателя 2. В это же время сигнал с выхода блока 8 поступает на вход элемента 15 задержки и на управляющий вход блока 13 регистрации, На выходе интегратора 9 в этот момент времени присутствует сигнал, пропорциональный оптимальному значению переменной х (в котором функция ц (х )+В х 1 имеет минимум). Это значение записывается в блок 13, представляющий собой аналого-цифровой преобразователь, выходы которого соединены с входами регистра, по сигналу, который поступил на его управляющий вход с выхода блока 8. Это записанное в блоке регистрации значение х отображается н цифровой форме в блоке 14 отображения, После этого сигнал с выхода блока 8, задержанный элементом 15 задержки, поступает на вход интегратора 9, сбрасывая его в нулевое состояние, исходное для отработки следующего режима, т.е. для задания аргументов следующей оптимизируемой функции с(х )+1,х 1. Одновременно сигнал с выхода блока 8 поступает на управляющие входы переключателей 1 и 2, переключая их в следующее положение, т,е, переключатель 1 соединяет выход интегратора 9 со следующим блоком, в данном случае с вторым блоком 4, а переключатель 2 соединяет выход переключателя 3 с,соответствующим входом блока сумматора 11 через следующий блок 10, На выходе сумматора 11 в 41 б 54данный момент времени присутствуетзначение текущего уровня затрат.После того, как сигнал с выходаблока 8, поступив на его вход, сбросит его в исходное нулевое состояние,на выходе блока 8 пропадает сигнал,вследствие чего переключатель 3 соединяет источник входного сигнала с10 входом интегратора 9, который ужеготов к приему нового сигнала.Таким образом, сигнал, свидетельствующий о нахождении экстремума, свыхода блока 8 одновременно переклю 15 чает цереключатель 3, который отключает источник сигнала от интегратора9 и переключателя 2, переключает переключатели 1 и 2 в следующее положение для нахождения экстремумов сле 20 дующих функций ц .(х .) +,х., записывает в блок 13 регйстрации числовоезначение найденного оптимального значения с выхода интегратора 9, сбрасывает сам блок 8 в нулевое состояние25 и по истечении задержки, определяемойэлементом 15 задержки, переводит интегратор 9 в исходное состояние. Время задержки выбирается таким, чтобыза зто время найденное значение с выЗО хода интегратора 9 успело записатьсяв блок 13 регистрации,Таким образом, после окончаниядействия сигнала с выхода блока 8 пе 35 реключатель 3, блок 8 и интегратор 9находятся в исходном состоянии, а переключатели 1 и 2 переключены в следующее по порядку положение, Аналогично находятся остальные оптимальные40 значения. Во время их нахождения сумматор 11 подсчитывает значение функции, определяющей ограниченияк,С Й х.,1 3145 путем сложения величин с 1 х, на каж 3дом шаге где х - найденные оптимальУные величины а коэффициенты д зараФнее заданы и реализованы в блоках 10,. в которых найденные х. умножаются на50 й, (блоки 10 могут быть реализованыв виде усилителей с постоянными коэффициентами усиления с 1 ). Блок 12 накаждом шаге сравнивает йолученноезначение функции Э с заданным Э,Ес 55 ли в процессе нахождения очередногозначения окажется, что Р ) О, то блок12 прекращает дальнейший процесс нахождения значений следующим образом,Он вырабатывает сигнал, который с еговыхода поступает на входы интегратора 9, блока 8, блока 13 регистрации и сумматора 11, сбрасывает их висходное нулевое состояние; Этот сигнал, кроме того, поступает на управляющие входы переключетелей 1 и 2,устанавливая их в первое положение.Таким образом,.блок 12 приводит всеустройство в исходное состояние. Кроме того, одновременно с этим блок 12вырабатывает сигнал, пропорциональный разности П-П, который с еговторого выхода поступает на входблока 5. Этот сигнал выбирает новыймножитель Лагранжа в соответствии созначением разности П-П, те. чембольше эта разность, тем больше выбирается следующий множитель Лагранжа,Схемно этот выбор или установлениенового значения множителя может реализоваться следующим образом. Блок 5выполняется в виде усилителя с изменяющимся коэффициентом усиления,В данном случае коэффициент усиления будет играть роль множителя Лагранжа, а сигналы с выхода блока 12будут менять этот коэффициент усиления, т.е, устанавливать новые значения множителей. Процесс установленияновых значений множителей будет длиться до тех пор, пока не выполнитсяравенство Р=П, Этот процесс будетдостаточно коротким, так как новоезначение множителя будет выбиратьсяпропорционально П-П, Если эту пропорцию выбрать достаточно точно (приналадке устройства), то указанный. процесс можно свести к двум шагам.Аналогично работает устройство,если по окончании определения всехоптимальных значений окажется, чтоР с П в этом случае разность П-Пбудет меньше нуля, т,е, множительЛагранжа будет уменьшен пропорционально этой разности, Так как передкаждой установкой нового значениямножителя блок 13 регистрации сбрасывается Ы ноль, то он регистрируетконечные оптимальные результаты, которые отображаются блоком 14,1Таким образом, автоматизация процесса решения задачи оптимальногораспределения ресурсов устройствомдостигается тем, что выборы и установка блоком 12 нового значения множителя Лагранжа и приведение этимблоком всего устройства в исходноесостояние, переключение переключателей 1 и 2, регистрация и отображение найденных оптимальных значений с помощью управляющих сигналов с выхода блока 8 в процессе нахождения оптимальных значений х 1 при каждом устанавливаемом значенйи множителя Лагранжа осуществляется автоматически,10 Формула изобретенияУстройство для решения задачи оптимального распределения ресурсов,содержащее три переключателя, интег ратор, выход которого соединен синформационным вхоцом первого переключателя и с входом множимого блокаумножения, выходы первого переключателя соединены с входами соответст вующих блоков задания нелинейности,выходы которых и выход блока умножения соединены соответственно с входами слагаемых первого сумматора,выходы второго переключателя черезблоки масштабирования соединены соответственно с входами слагаемых второго сумматора, выход которого подключен к входу блока сравнения с константой, информационный вход третьего 30 переключателя является информационнымвходом устройства, выход третьего переключателя соединен с информационнымвходом интегратора, выход первогосумматора через дифференцирующий блок ЗБ соединен с информационным входомблока определения экстремума, выходкоторого подключен к управляющимвходам второго и третьего переключателей, о т л и ч а ю щ е е с я тем, 40 что, с цель 1 о повышения производительности, в него введены элемент задержки, блок регистрации, выход третьегопереключателя соединен с информационным входом второгс переключателя,ус тановочный выход блока сравнения сконстантой соединен с первыми установочными входами блока определенияэкстремума, интегратора и с установочными входами второго сумматора, 50 первого и второго переключателей иблока регистрации, выход блока определения экстремума соединен со своимвторым установочным входом, с управляющим входом блока регистрации, с 55 управляющим входом первого переключателя и с входом элемента задержки,выход которого подключен к второмуустановочному входу интегратора, разрешающий выход блока сравнения под1341654 8ключен к входу множителя блока умно- гистрации является выходом оптимальжения, информационный выход блока ре- ного значения устройства,Составитель А.ЖереновРедактор М.Дылын Техред М.Дидык Корректор М.МаксимишинецЗаказ 4438/53 Тираж 672 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4