Устройство для решения задачи оптимального распределения ресурсов Советский патент 1987 года по МПК G06G7/122 

13

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

Цель изобретения - повьш1ение производительности.

На чертеже представлена блок,-схе- ма устройства.

Устройство содержит переключате- ли 1, 2 и 3, блоки 4 задания нелинейности, блок 5 умноженияр сумматор 6, дифференцирующий блок 7, блок 8 определения экстремума, интегратор 9, блоки 10 масштабирования, суммато 11, блок 12 сравнения с константой, блок 13 регистрации, блок 14 отобра- женияр элемент 15 задержки.

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

ния,

сводящихся к нахождению минимума функции

Q min Z q .(х .)

при ограничениях к

d.-x. iD. ,

„ J i „

Для решения этой задачи в устройстве используется метод множителей Лагранжа, который позволяет свести задачу поиска экстремума функции k переменных к поиску экстремума функции одной переменной для заданного значения множителя Лагранжа А . Фун

ция Лагранжа имеет вид

V ( ,

Q(x,A) Z.mintq. (х O+Ad.x..

Оптимальные значения x-(,k)

при заданном Л находятся из решения уравнения

q.(x.).Ad.x.0.

Таким образом, задача сводится к нахождению частных производных заданной функции по всем переменным и нахО5 одению , значений аргументов (х.|, при которых производные равны нулю для заданного множителя Лагранжа. Наибольшую тpyднoctь в этой задаче составляет выбор множителя Лагранжа, при котором найденные оптимальные значения x;(,k) удовлетворяли бы заданным ограничения.

Процес с выбора необходимого Д заключается в том, что сначала выбирается первоначальное значение Ad, а затем по мере решения задачи и про

5

0

5

0

0

5 50 55

верки удовлетворения найденных оптимальных значений x.(,k) это перво- начальное значение корректируется с учетом отклонений полученного значения затрат D(, от заданного ограничения D до тех пор, пока не выполнится равенство . После этого процесс коррекции /1 прекращается и задача считается решенной. Устройство автоматически после нахождения экстре- мума по одной переменной (т.е. после нахождения очередного оптимального значения х.) переходит к нахождению экстремума по другой переменной последовательно для всех переменных. Кроме того, устройство автоматически производит коррекцию выбранного i4Ho- жителя Лагранжа / до тех пор, пока не выполнится условие D р D и автоматически регистрирует и отображает ре- зультаты решения задачи x.(,k).

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

В исходном состоянии интегратор 9, блок 8 определения экстремума и сумматор 11 установлены в нулевое состояние. Переключатель 3 соединяет источник входного сигнала с входом интегратора 9 для задания аргументов оптимизируемой функции. Кроме того, через переключатель 3 источник входного сигнала подключается к переключателю 2, который в исходном положении соединяет его через один из блоков (вначале через первый блок 10) с соответствующим входом сумматора 11,

С выхода интегратора 9 сигнал через переключатель 1 поступает на вход одного из блоков 4 (сначала на вход первого блок а 4), так как частные про- производные находятся по всем переменным х- последовательно, т,е, сначала для х, затем для Х2 и т,д,, также последовательно находятся и оптимальные значения x.(,k). На блоке 5 установлено в исходном состоянии значение множителя Лагранжа Д Д d, . Одновременно с выхода интегратора 9 сигнал поступает на вход блока 5, ,в котором он умножается на установленное значение A-d,, С выхода одного из блоков 4 и с выхода блока 5 сигналы поступают на соответствующие входы сумматора 6, в котором они складываются. Суммарный сигнал с выхода сумматора 6 поступает на вход дифференцирующего блока 7, который вырабатывает сигнал, пропорциональный

производной функции q ( по аргументу х , Этот сигнал поступает на информационный вход блока 8, который при перемене знака производной выдает сигнал, свидетельствующий о нахождении экстремума (в частности минимума) функции ) + Д,х, .

Сигнал с выхода блока 8, свидетельствующий о нахождении экстремума по первой переменной х и, следовательно, о нахождении оптимального значения х, используется для управления дальнейшей работой устройства. Этот сигнал с выхода блока 8 посту- пает на его вход, устанавливая его в нулевое состояние, исходное для индикации об экстремуме следующей функции q(Xj). Одновременно с этим сигнал с выхода блока 8, поступая на управляющий вход переключателя 3,,прекращает подачу через него на вход интегратора 9 и вход переключателя 2. В это же время сигнал с выхода блока 8 поступает на вход элемента 15 задержки и на управляющий вход блока 13 регистрации. На выходе интегратора 9 в зтот момент времени присутствует сигнал, пропорциональный оптимальному значению переменкой X, (в котором функция Гя, (х) имеет fflнимyм), Это значение записывается в блок 13, представляющий собой аналого-цифровой преобразователь, 5 реключатель 3, блок 8 и интегратор 9

выходы которого соединены с входами регистра, по сигналу, который поступил на его управляющий вход с выхода блойа 8. Это записанное в блоке регистрации значение х отображается в цифровой форме в блоке 14 отображения. После этого сигнал с выхода блока 8, задержанный элементом 15 задержки, поступает на вход интегратора 9, сбрасывая его в нулевое состояние , исходное для отработки следующего режима, т.е. для задания аргументов следующей .оптимизируемой функции tq)(xj) + A, Xj . Одновременно сигнал с выхода блока 8 поступает на управляющие входы переключателей 1 и 2, переключая их в следующее положение, т.е. переключатель 1 соединяет выход интегратора 9 со следующим блоком, в данном случае с вторым блоком 4, а переключатель 2 соединяет выход переключателя 3 с .соответствующим входом блока сумматора 1 Г через следующий блок 10, На выходе сумматора 11 в

данный момент времени присутствует значение текущего уровня затрат.

После того, как сигнал с выхода с блока 8, поступив на его вход, сбросит его в исходное нулевое состояние, на выходе блока 8 пропадает сигнал, вследствие чего переключатель 3 соединяет источник входного сигнала с

0 входом интегратора 9, который уже готов к приему нового сигнала.

Таким образом, сигнал, свидетельствующий о нахождении экстремума, с выхода блока 8 одновременно переклю5 чает цереключатель 3, который отключает источник сигнала от интегратора 9 и переключателя 2, переключает переключатели 1 и 2 в следующее положение для нахождения экстремумов сле0 дующих функций q . (xp + , записывает в блок 13 регистрации числовое значение найденного оптимального значения с выхода интегратора 9, сбрасывает сам блок 8 в нулевое состояние

5 и по истечении задержки, определяемой элементом 15 задержки, переводит интегратор 9 в исходное состояние. Время задержки выбирается таким, чтобы за это время найденное значение с вы0 хода интегратора 9 успело записаться в блок 13 регистрации.

Таким образом, после окончания действия сигнала с выхода блока 8 пе0

5

находятся в исходном состоянии, а переключатели 1 и 2 переключены в следующее по порядку положение. Аналогично находятся остальные оптимальные значения. Во время их нахождения сумматор 11 подсчитывает значение функции определяющей ограничения

Ь,-.,.

путем сложения величин d х . на каждом шаге, где х- - найденные оптималь1

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

0 dj (блоки 10 могут быть реализованы в виде усилителей с постоянными коэффициентами усиления dj). Блок 12 на каждом шаге сравнивает полученное значение функции D, с заданным D.Ec5 ли в процессе нахождения очередного значения окажется, что В„ D, то блок 12 прекращает дальнейший процесс нахождения значений следующим образом. Он вырабатывает сигнал,который с его

5134

ыхода поступает на входы интеграора 9, блока 8, блока 13 регистраии и сумматора 11, сбрасывает их в сходное нулевое состояние.- Этот сигал, кроме того, поступает на управяющие входы переключетелей 1 и 2, устанавливая их в первое положение. Таким образом, блок 12 приводит все устройство в исходное состояние, Кро- ме того, одновременно с этим блок 12 вырабатывает сигнал, пропорциональный разности Dp-D, который с его второго выхода поступает на вход блока 5. Этот сигнал выбирает новый множитель Лагранжа в соответствии CD значением разности , т„е. чем больше- эта разность, тем больше выирается следующий множитель Лагранжа, Схемно этот выбор или установление нового значения множителя может реаизоваться следующим образом. Блок 5 выполняется в виде усилителя с изменяющимся коэффициентом усиления, В данном случае коэффициент усиления будет играть роль множителя Лагранжа, а сигналы с выхода блока 12 будут менять этот коэффициент усиления, т.е.. устанавливать новые значения множителей. Процесс установления новых значений множителей будет длиться до тех пор, пока не выполнится равенство , Этот процесс будет достаточно коротким, так как новое значение множителя будет выбираться пропорционально Dj,-D, Если эту пропорцию выбрать достаточно точно (при наладке устройства), то указанньш процесс можно свести к двум шагам. Аналогично работает устройство, если по окончании определения всех оптимальных значений окажется, что D Df в этом случае разность Dr,-D будет меньше нуля, т.е. множитель Лагранжа будет уменьшен пропорционально этой разности. Так как перед каждой установкой нового значения множителя блок 13 регистрации сбрасывается н ноль, то он регистрирует конечные оптимальные результаты, которые отображаются блоком 14,

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

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

Формула изобретения

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

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

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

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

0 что, с цельр повышения производительности, в него.введены элемент задерж- ки, блок peгиcтpau И5 выход третьего переключателя соединен с информацион- ньм входом второго переключателя,ус5 тановочный выход блока сравнения с константой соединен с первыми установочными входами )лока определения . экстремума, интегратора и с установочными входами второго сумматора,

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

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

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

Изобретение относится к вычислительной технике. Целью изобретения является повышение производительности. Устройство содержит пе- . реключатели 1, 2 и 3, блоки 4 задания нелинейности, блок 5 умножения, сумматор 6, дифференцирующий блок 7, блок 8 определения экстремума, интегратор 9, блоки 10 масштабирования, сумматор 11, блок 12 сравнения с константой, блок 13 регистрации, блок 14 отображения, элемент 15 задержки. 1 ил. сл со