Устройство для решения задачи оптимального распределения ресурсов
Изобретение относится к вычислительной технике. Целью изобретения является повышение производительности . Устройство содержит пе- . реключатели 1, 2 и 3, блоки 4 задания нелинейности, блок 5 умножения, сумматор 6, дифференцирующий блок 7, блок 8 определения экстремума, интегратор 9, блоки 10 масштабирования , сумматор 11, блок 12 сравнения с константой, блок 13 регистрации, блок 14 отображения, элемент 15 задержки . 1 ил. сл со
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (19) (11) 41654 А1 (51) 4 G 06 G 7/122
ОЛИСАНИЕ ИЗОБРЕТЕНИЯ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4063512/24-24 (22) 30.04,86 (46) 30.09,87, Бюл, У 36 (72) С,Б.Ларионов, А,M,Ïîëÿêoâ и Т,В.Алексеева (53) 681.325,057 (088.8) (56) Авторское свидетельство СССР
9 1005066, кл. G 06 G 15/20, 1981, Авторское свидетельство СССР
Ф 674049, кл. G 06 G 7/48, 1977.
I (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ
ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ (57) Изобретение относится к вычислительной технике. Целью изобретения является повышение производительности. Устройство содержит переключатели 1, 2 и 3, блоки 4 задания нелинейности, блок 5 умножения, сумматор 6, дифференцирующий блок 7, блок 8 определения экстремума, интегратор 9, блоки 10 масштабирования, сумматор 11, блок 12 сравнения с константой, блок 13 регистрации, блок 14 отображения, элемент 15 за— держки. 1 ил, 1
134
Изобретение относится к вычислительной технике и может быть исполь— зовано в автоматизированных системах управления.
Цель изобретения — повьш ение производительности.
На чертеже представлена блок;схема устройства.
Устройство содержит переключатели I 2 и 3, блоки 4 задания нели нейности, блок 5 умножения„ сумматор 6, дифференцирующий блок 7, блок
8 определения экстремума, интегратор
9, блоки 10 масштабирования, сумматор
11, блок 12 сравнения с константой, блок 13 регистрации, блок 14 отображения, элемент 15 задержки, Устройство предназначено для автоматического решения широкого класса задач нелинейного программирования, сводящихся к нахождению минимума функции
g = min2 о .(х.)
) при ограничениях к
Й..х. jP1 Для решения этой задачи в устройстве используется метод множителей Лагранжа, который позволяет свести задачу поиска экстремума функции k переменных к поиску экстремума функции одной переменной для заданного значения множителя Лагранжа . Функция Лагранжа имеет вид 1 к g(xP Л) = 2 min (q. (х )+Ad. х ). Оптимальные значения х .(j=1 k) P при заданном A находятся из решения уравнения 1654 верки удовлетворения найденных оптимальных значений х.(j=1 k) это перво) В начальное значение корректируется с, учетом отклонений полученного значе> ния затрат D от заданного ограничения D до тех пор, пока не выполнится равенство D„=D. После этого процесс коррекции 4 прекращается и задача считается решенной, Устройство автоматически после нахождения экстре15 40 мума по одной переменной (т,е, после нахождения очередчого оптимального значения х .) переходит к нахождению ! экстремума по другой переменной последовательно для всех переменных, Кроме того, устройство автоматически производит коррекцию выбранного множителя Лагранжа Я до тех пор, пока не выполнится условие D =D и автоматии чески регистрирует и отображает результаты решения задачи х .(j=1,k). Устроиство работает следующим об- разом. В исходном состоянии интегратор 9, блок 8 определения экстремума и сумматор 11 установлены в нулевое состаяние. Переключатель 3 соединяет источник входного сигнала с входом интегратора 9 для задания аргументов оптимизируемой функции, Кроме того, через переключатель 3 источник входного сигнала подключается к переключателю 2, который в исходном положе- нии соединяет его через один иэ блоков (вначале через первый блок 10) с соответствующим входом сумматора 11. С выхода интегратора 9 сигнал через переключатель 1 поступает на вход одного из блоков 4 (сначала на вход первого блока 4), так как частные про45 Ф вЂ” — (q. (х.)+Ad.. х.) = О. 3 ах, j j 3 Таким образом, задача сводится к нахождению частных производных заданной функции по всем переменным и нахождению.значений аргументов jx j 1 при которых производные равны нулю для заданного множителя Лагранжа. Наибольшую трудносТь в этой задаче составляет выбор множителя Лагранжа, при котором найденные оптимальные значения х:(х=1 k) удовлетворяли бы P заданным ограничениям, Процесс выбора необходимого 4 заключается в том, что сначала выбирается первоначальное значение Я,= 3 d„ а затем по мере решения задачи и пропроизводные находятся по всем переменным х, последовательно, т,е. сначала для х,, затем для х2 и т.д,, также последовательно находятся и оптимальные значения х (j=1 k). На P блоке 5 установлено в исходном состоянии значение множителя Лагранжа 31= il d, . Одновременно с выхода интегратора 9 сигнал поступает на вход блока 5, в котором он умножается на установленное значение Я d,, С выхода одного из блоков 4 и с выхода блока 5 сигналы поступают на соответствующие входы сумматора 6, в котором они складываются. Суммарный сигнал с выхода сумматора 6 поступает на вход дифференцирующего блока 7, который вырабатывает сигнал, пропорциональный 3 13 производной функции (о (х х ) по аргументу х, . Этот сигнал поступает на информационный вход блока 8, который при перемене знака производной выдает сигнал, свидетельствующий о нахождении экстремума (в частности минимума) функции (q, (х,)+Я„х,), Сигнал с выхода блока 8, свидетельствующий о нахождении экстремума по первой переменной х, и, следовательно, о нахождении оптимального значения х„„ используется для управления дальнейшей работой устройства ° Этот сигнал с выхода блока 8 посту-пает на его вход, устанавливая его в нулевое состояние, исходное для индикации об экстремуме следующей функции (q (х )+М, х, $. Одновременно с этим сигнал с выхода блока 8, поступая на управляющий вход переключателя 3, прекращает подачу через него на вход интегратора 9 и вход переключателя 2. В это же время сигнал с выхода блока 8 поступает на вход элемента 15 задержки и на управляющий вход блока 13 регистрации. На выходе интегратора 9 в этот момент времени присутствует сигнал, пропорциональный оптимальному значению переменной х (в которомфункция (q (х )+Я х j имеет минимум), Это значение записывается в блок 13, представляющий собой аналого-цифровой преобразователь, выходы которого соединены с входами регистра, по сигналу, который поступил на его управляющий вход с выхода блока 8. Это записанное в блоке регистрации значение х„ отображается н цифровой форме в блоке 14 отображения. После этого сигнал с выхода блока 8, задержанный элементом 15 задержки, поступает на вход интегратора 9, сбрасывая его в нулевое состояние, исходное для отработки следующего режима, т.е. для задания аргументов следующей оптимизируемой функции (q<(x )+h,õ ). Одновременно сигнал с выхода блока 8 поступает на управляющие входы переключателей 1 и 2, переключая их в следующее положение, т.е. переключатель 1 соединяет выход интегратора 9 со следующим блоком, в данном случае с вторым блоком 4, а переключатель 2 соединяет выход переключателя 3 с .соответствующим входом блока сумматора 11 через следующий блок 10, На выходе сумматора 11 в 41654 данный момент времени присутствует значение текущего уровня затрат. После того, как сигнал с выхода блока 8, поступив на его вход, сбросит его в исходное нулевое состояние, на выходе блока 8 пропадает сигнал, вследствие чего переключатель 3 соединяет источник входного сигнала с 10 входом интегратора 9, который уже готов к приему нового сигнала. Таким образом, сигнал, свидетельствующий о нахождении экстремума, с выхода блока 8 одновременно переклю15 чает цереключатель 3, который отключает источник сигнала от интегратора 9 и переключателя 2, переключает переключатели 1 и 2 в следующее положение для нахождения экстремумов сле20 дующих функций fq (х )+Д х-J запи сывает в блок 13 регйстрации числовое значение найденного оптимального значения с выхода интегратора 9, сбрасывает сам блок 8 в нулевое состояние 25 и по истечении задержки, определяемой элементом 15 задержки, переводит интегратор 9 в исходное состояние. Время задержки выбирается таким, чтобы за зто время найденное значение с вы30 хода интегратора 9 успело записаться в блок 13 регистрации, Таким образом, после окончания действия сигнала с выхода блока 8 neg5 реключатель 3, блок 8 и интегратор 9 находятся в исходном состоянии, а переключатели 1 и 2 переключены в следующее по порядку положение, Аналогично находятся остальные оптимальные 40 значения. Во время их нахождения сумматор 11 подсчитывает значение функции, определяющей ограничения к, ». d. -х., 1 45 путем сложения величин d...х. на каж3 дом шаге где х — найденные оптимальУ 1 ные величины а коэффициенты d зараФ 1 нее заданы и реализованы в блоках 10, . в которых найденные х. умножаются на 50 й; (блоки 10 могут быть реализованы в виде усилителей с постоянными коэффициентами усиления d.). Блок 12 на каждом шаге сравнивает йолученное значение функции D„ с заданным D,Ec55 ли в процессе нахождения очередного значения окажется, что DR ) D, то блок 12 прекращает дальнейший процесс нахождения значений следующим образом. Он вырабатывает сигнал, который с его 1341654 выхода поступает на входы интегратора 9, блока 8, блока 13 регистрации и сумматора 11, сбрасывает их в исходное нулевое состояние; Этот сигнал, кроме того, поступает на управляющие входы переключетелей 1 и 2, устанавливая их в первое положение. Таким образом,.блок 12 приводит все устройство в исходное состояние. Кро.ме того, одновременно с этим блок 72 вырабатывает сигнал, пропорциональный разности D„-D, который с его второго выхода поступает на вход блока 5. Этот сигнал выбирает новый множитель Лагранжа в соответствии со значением разности D„-D, т„е. чем больше эта разность, тем больше выбирается следующий множитель Лагранжа, Схемно этот выбор или установление нового значения множителя может реализоваться следующим образом. Блок 5 выполняется в виде усилителя с изменяющимся коэффициентом усиления. В данном случае коэффициент усиления будет играть роль множителя Лагранжа, а сигналы с выхода блока 12 будут менять этот коэффициент усиления, т.е, устанавливать новые значения множителей. Процесс установления новых значений множителей будет длиться до тех пор, пока не выполнится равенство D„=D. Этот процесс будет достаточно коротким, так как новое значение множителя будет выбираться пропорционально D„-D. Если эту пропорцию выбрать достаточно точно (при наладке устройства), то указанный . процесс можно свести к двум шагам. Аналогично работает устройство, если по окончании определения всех оптимальных значений окажется, что D c D„ в этом случае разность D„-D будет меньше нуля, т.е, множитель Лагранжа будет уменьшен пропорционально этой разности. Так как перед каждой установкой нового значения множителя блок 13 регистрации сбрасывается Ы ноль, то он регистрирует конечные оптимальные результаты, которые отображаются блоком 14, 1 Таким образом, автоматизация процесса решения задачи оптимального распределения ресурсов устройством достигается тем, что выборы и установка блоком 12 нового значения множителя Лагранжа и приведение этим блоком всего устройства в исходное состояние, переключение переключателей 1 и 2, регистрация и отображение найденных оптимальных значений с помощью управляющих сигналов с выхода блока 8 в процессе нахождения оптимальных значений х при каждом устанавливаемом значенйи множителя Лагранжа осуществляется автоматически. 10 Формула изобретения Устройство для решения задачи оптимального распределения ресурсов, содержащее три переключателя, интег15 ратор, выход которого соединен с информационным вхоцом первого переключателя и с входом множимого блока умножения, выходы первого переключателя соединены с входами соответст20 вующих блоков задания нелинейности, выходы которых и выход блока умножения соединены соответственно с входами слагаемых первого сумматора, выходы второго переключателя через блоки масштабирования соединены соответственно с входами слагаемых второго сумматора, выход которого подключен к входу блока сравнения с константой, информационный вход третьего 30 переключателя является информационным входом устройства, выход третьего переключателя соединен с информационным входом интегратора, выход первого сумматора через дифференцирующий блок дБ соединен с информационным входом блока определения экстремума, выход которого подключен к управляющим входам второго и третьего переключателей, о т л и ч а ю щ е е с я тем, 40 что, с цель1о повышения производительности, в него введены элемент задержки, блок регистрации, выход третьего переключателя соединен с информационным входом второгс переключателя,ус45 тановочный выход блока сравнения с константой соединен с первыми установочными входами блока определения экстремума, интегратора и с установочными входами второго сумматора, В0 первого и второго переключателей и блока регистрации, выход блока определения экстремума соединен со своим вторым установочным входом, с управляющим входом блока регистрации, с 55 управляющим входом первого переключателя и с входом элемента задержки, выход которого подключен к второму установочному входу интегратора, разрешающий выход блока сравнения под? 1341654 8 ключен к входу множителя блока умно- гистрации является выходом оптимальжения, информационный выход блока ре- ного значения устройства, Составитель А.Жеренов Редактор M.Äûëûí Техред М.Дидык Корректор М.Максимишинец Заказ 4438/53 Тираж 672 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4
