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

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

„1.

обеспечи-

С max f ; (х; ) ,

X 1-1

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

тп

23х; ё В, при х, О, 1, 2,...,п.,

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

распределенных в i-ю отрасль ;

п; - максимальное количество ресурсов, которое может быть освоено в i-и отрасли;

В - общее количество ресурсов ;

С - максимально достижимая эффективность использования ресурсов (в рублях, тоннокилометрах и т.п.).

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

На фиг.1 приведена блок-схема устройства для решения задач оптимального распределения ресурсов; на фиг,2 -

Блок 4 вычисления целевой функц содержит сумматор 16 и индикатор 1 вход 18 запуска устройства. Блок 6

16 синхронизации содержит счетчик 19, триггер 20, элемент 21 задержки,кл 22, элемент 23 индикации, выключат 24, разделительные диоды 25 и 26,э мент ffE 27, группу индикаторных сч

20 чиков 28,-28, группу элементов И

, элемент ИЛИ 30, группу ра пределителей 31,-31„, уровня, кажды элемент коммутации блока 2 содержи первую и вторую группы ключей 32,25 и 33,-33г„ соответственно.

Каждый распределитель 31 уровне может быть выполнен на основе коль вых сдвигающих схем, многоустойчив схем или регистровых схем, каждый

30 распределитель 31 уровней имеет вх ды а, b и с и выходы (каналы) d, d(,..., d. На вход а подается пит ние, которое в исходном состоянии распределителя будет и на выходном d канале. Поступление сигнала на вход b обеспечивает возврат распре лителя в исходное состояние, а на вход с - переключение напряжения с канала на канал в прямой последова

40 .тельноети.

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

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

35

схема блока синхронизации; на фиг.З - Q циями f; (х ) (i 1 , т) приводит к

схема узла коммутации,

точному решению. Работа осуществляется за В шагов, на каждом из которых определяется &f; (xj f; (х,., )-f (х;) тип функции по тах( (xj)) и значеУстройство содержит блок 1 задания исходных данных, состоящий из m

узлов 1,- задания исходных данных, g ние аргумента этой выбранной функции

блок 2 коммутации, состоящий из m уз-увеличивается на единицу. Б результалов 2,-2 коммутации, блок 3 вычис-те определяются значения х; по пока-

ления приращений, блок 4 вычислениязателям индикаторных счетчиков 28,

целевой функции, блок 5 выбора макси-значение максимально достижимой эф

мума, блок 6 си1гхронизации. Каждый узел задания исходных данных блока 1 содержит потенциометры , блок 3

вычисления приращений - операционные усилители 8,-8 и ключи , блок 5 выбора максимума - операционные уси- . лители lO,-10, токозадающие резисторы 11, -11 , резисторы 1 2,- 1 2 обрат-

ной связи, разделительтдае диоды 13,- 13 и 14,-14,„, ключи 15,-15.

Блок 4 вычисления целевой функции содержит сумматор 16 и индикатор 17, вход 18 запуска устройства. Блок 6

синхронизации содержит счетчик 19, триггер 20, элемент 21 задержки,ключ 22, элемент 23 индикации, выключатель 24, разделительные диоды 25 и 26,элемент ffE 27, группу индикаторных счетчиков 28,-28, группу элементов И

, элемент ИЛИ 30, группу распределителей 31,-31„, уровня, каждый элемент коммутации блока 2 содержит первую и вторую группы ключей 32,32

и 33,-33г„ соответственно.

Каждый распределитель 31 уровней может быть выполнен на основе кольцевых сдвигающих схем, многоустойчивых схем или регистровых схем, каждый

распределитель 31 уровней имеет входы а, b и с и выходы (каналы) d, d(,..., d. На вход а подается питание, которое в исходном состоянии распределителя будет и на выходном d канале. Поступление сигнала на вход b обеспечивает возврат распределителя в исходное состояние, а на вход с - переключение напряжения с канала на канал в прямой последова-

.тельноети.

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

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

точному решению. Работа осуществляется за В шагов, на каждом из которых определяется &f; (xj f; (х,., )-f (х;) тип функции по тах( (xj)) и значение аргумента этой выбранной функции

фективности С по показателям индика тора 17 блока 4.

Перед началом работы подвижные контакты потенциометров 7: каждого у-эла I; задания исходных данн1,1х блока 1 (i 1, п, j 1, п) устанавливаются в положение, которым соответствуют выходные напряжения, пропор- циональные значениям f;(x ) (i l,m j 1, k), a остальные no teHUHOMeT- ры 7 (i 1,и, j k+l,n) остаются в исходном состоянии, которому соответствует нулевое выходное напряжение, счетчик 19 устанавливается в состояние (N-B), где N - емкость счетчика.

Работа начинается нри ностунлении сигнала на вход чануска блока 6. При этом сигнал запуска Г1оступит на вхо- ды а группы распределителей 31 уровней блока 6. На выходах d распределителей 31 уровней появятся сигналы, которые, поступая на управляющие входы блока 2 ко п гутации, откроют соот- ветствующие ключи 32 первой группы. При этом сигналы, пропорциональны f- (I), с выходов блока 1 поступают на неинвертирующие входы операционных усилителей 8 блока 3, Ключи 9 блока 3 открыты, так как на их управляющие входы поступают сигналы с инвертирующего выхода триггера 20 блока 6 управления. Поэтому с выходов суммирующих усилителей 8 блока 3 сиг налы ноступают на входы блока 5 выбора максимума.

Блок 5 работает следующим образом С входов блока 5 сигналы через токо- задающие резисторы 11 поступают на входы операционных усилителей 10. Выходнор сигнал появится на выходе того операционного усилителя 10;, на входе которого будет присутствовать наибольщий сигнал. Этот сигнал посту- пает на управляющий вход ключа 15, и открывает его. Пусть, например, максимальшлй сигнал присутствует на входе первого операционного усилителя 10, , тог да откроется ключ 15, и на первом выходе блока 5 появится вы ходной сигнал, который поступит на первыГ вход элемента ИЛИ 30 блока 6, на счетн1.1й вход счетчика 28 ( группы блока 6 и на вход элемента И 29, группы блока 6. С выхода элемента ИЛИ 30 блока 6 сигнал поступит на счетный вход счетчика 19 и на вход установки в единицу триггера 20.

, ю 5

20 25 jO ...

Q дд

50

5

Триггер 20 переходит в единичное состояние. Высокий потенциал с его инверсног о выхода перестает поступат на управляющие входы ключей 9 блока 3. Ключи закрыван)тся. Тем самым прекращается поступление, входных сигналов на входы блока Ь. Счетчики 28, и 19 изменяют свое содержимое на единицу, с прямого выхода триггера 20 блока 6 сигнал поступает на э.темент 21 задержки, а с выхода элемента И 29, грунпы блока 6 - на вход с распределителя 31, уровней группы. При этом происходит переключение сигнала с выхода d на выход d,. Ключ 32, первой группы первого узла 2, коммутации блока 2 закроется и откроются ключи 32 2 nepBoii группы И 33, второй группы первого узла 2, коммутации блока 2. Сигнал, нропорциональный f| (2), появится на первом выходе первого узла коммутации 21, а сигнал, пропорциональный f,(I) - на втором выходе первого узла 2, коммутации блока 2. Эти сигналы поступят соответственно на нсинвертирующий и инвертирующий входы операционного усилителя 8, блока 3. На выходе операционного усилителя 8 будет формироваться сигнал, пропорциональный Af ,(х) f,(2) - f,(I). Кроме того, сигнал, нропорциональный f ,(1), поступает на первый вход сумматора 16 блока 4, и показания индикатора 17 станут пропорциональны f ,(1),

К этому моменту сигнал с выхода элемента 21 задержки блока 6 через разделительный диод 25 поступит на вход установки в О триггера 20 блока 6. Триггер перейдет в нулевое состояние. Выходной сигнал с его инверсного выхода откроет ключи 9 блока 3. На этом первый ш аг работы устройства заканчивается. Дальнейшая работа усч- ройства будет проходить аналогично На последнем шаге решения с выхода счетчика 19 блока 6 сигнал переполнения поступит на управляющий вход ключа 22 и через элемент НЕ - на входы элементов И 29 группы, прекращая ра- боту устройства. Ключ 22 откроется и элемент 23 индикации сработает. Загорание элемента 23 индикации свиде тельствует об окончании работы.

Показания индикаторных счетчиков 28 блока 6 будут соответствовать количеству ресурсов, распределительных

в L-ю отрасль, а показания индикатора 1 7 будут пропорцнональиь значению максимально достижимой эффективности использования ресурсов. Для возврата устройства в исходное состояние отключается сигнал запуска от входа запуска устройства и кратковременно включается выключатель 24. Тем самым обнуляются счетчик 19 и группа счетчиков 28, а группа распределителей 31 уровней сигналом по входу b BOS - вращается в исходное состояние.

Аналогичным образом решается задачи при линейных f(X| ) и ограниче-

г„ л

ниях вида

г т Х1а;Х; ё В, х; е о,1) (i

1, m), т.е. задача, решаемая с помощью известного устройства. При подготовке исходных данных необходимо каждую функцию а;х , представить в виде Cf .Cx;) (с;/а;)у;, где у; 0, 1, 2,..., а;, а счетчик 39 установить перед началом решения в состояние

началом решения (N-B), где В .

Линейность

функций ер;(х;) обеспечивает постоянство приращений (у;) Cf; (у; + | ) Ср; (у ), а следовательно, и возможность определения значений х; 1 при yi а; их, О в противном случае .

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

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

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

.

10

15

20

25

45

55

723356

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

2. Устройство по п.1, отличающееся тем, что блок синхронизации содержит группу распределителей уровня, группу элементов И, группу индикаторных счетчиков, элемент ИЛИ, элемент НЕ, счетчик, ключ, индикаторный элемент, триггер, элемент задержки, два разделительных диода и выключатель, входы элемента ИЛИ являются группой входов блока, первьш вход j-ro элемента И группы объединен с информационным входом J-го индикаторного счетчика группы

(J 1, 2т) и объединен с j-м

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

30

35

40

50

дом запуска , входы установки в делителя уровня группы подключен к исходное состояние всех распредели- выходу -го элемента И группы, груп- телей уровней группы объединены с па выходов j-ro распределителя уровни

входом установки в О счетчика, пе

группы является j-й группой информа

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

реключающий вход каждого j-ro распре- ционных выходов блока.

U

t xsMxy а, ,

Фиг. г

11

U

От 6flOf a 6

Ki

Фиг.З