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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СО11ИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (51) 4 С 06 G 7/122

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

00 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3865262/24-24 (22) 07.03. 85 (46) 07.02.88. Вюл. У 5 (72) О.Г.Алексеев,А.Н.Мардас,В.IO.Мержанов,Д.В.Соловьев и H.È.ß÷êóëà (53) 681.333 (088.8) (56) Авторское свидетельство СССР

739562, кл. 0 06 G 7/48, 1980.

Авторское свидетельство СССР

У 1327125, кл. G 06 G 7/122, 1985. (54) УСТРОЙСТВО ДЛЯ РЕ111ЕНИЯ ЗАДАЧ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ (57) Изобретение относится к области вычислительной техники и может быть использовано для решения широко при„.,SU„„1372335 А1 меняющейся при планировании задачи оптимального распределения однородных ресурсов. Целью изобретения является расширение функциональных возможностей устройства эа счет реализации возможности решения задач с существенно нелинейными функциями эффективности использования ресурсов и управляющими переменными. Изобретение содержит блок задания исходных данных, блок коммутации, блок вычисления приращений, блок вычисления целевой функции, блок выбора максимума и блок синхронизации. I э.п. ф-лы, 3 ил.

1 l 372335 2

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

С = max Qf; (х;), Х при ограничениях х; Â, при x,= О, 1, 2,...,n,, е и! где f;(x,) — функция, характеризук щая эффективность использования ресурсов в

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

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

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

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

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

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

Устройство содержит блок 1 задания исходных данных, состоящий из m узлов 1, — 1,„ задания исходных данных, блок 2 коммутации, состоящий из m узлов 2,-2,„ коммутации, блок 3 вычисления приращений, блок 4 вычисления целевой функции, блок 5 выбора макси45 ного распределения ресурсов градиентным методом, который для задач с однородными ресурсами и выпуклыми функ50 циями f (х ) (i = 1, m) приводит к

Ф

ЗО

40 мума, блок 6 синхронизации. Каждый узел задания исходных данных блока l содержит потенциометры 7,-7„, блок 3 вычисления приращений — операционные усилители Я, -8,„ и ключи 9, -9, блок 5 выбора максимума — операционные усилители 10< †1, токозадающие резисторы ll — 11, резисторы 12 12 обратной связи, разделительные диоды 13,—

13 и 14„ — 14„„ ключи 15, -!5 °

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

22, элемент 23 индикации, выключатель

24, разделительные диоды 25 и 26,элемент НЕ 27, группу индикаторных счетчиков 28,-28„„ группу элементов И

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

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

d,..., с1„. На вход а подается питание, которое в исходном состоянии распределителя будет и на выходном

Й канале. Поступление сигнала на вход Ь обеспечивает возврат распределителя в исходное состояние, а на вход с — переключение напряжения с канала на канал в прямой последова.тельности.

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

Принцип действия устройства основывается на решении задачи оптимальточному решению. Работа осуществляется за В шагов, на каждом из которых определяется h f; (х, ) = Е, (х;„)-f (х; ) тип функции по mqx(hf; (х;)) и значение аргумента этой выбранной функции увеличивается на единицу. В результате определяются значения х, по показателям индикаторных счетчиков 28, значение максимально достижимой эф3 1 372335 4 фективности С по показателям индикатора 1 7 блока 4.

Перед началом работы подвижные контакты потецциометров 7„ каждого узла I, >ада>«ия исходных данных блока ) (i = 1, n, j = 1, n) устанавливаются в положение, которым соответствуют выход««ь<е ««апряжения, пропорциональные значениям f (х ) (i = ),m, )p

j = ), k), а остальные по)енциометры 7 (i = ),ш, j = k+) n) остаются в исходном состоянии, которому соответствует нулевое выходное напряжение, счетчик 19 устанавливается в состояние (N-B), где N — емкость сч е т чика .

Работа начинается при поступлении сигнала на вход запуска блока 6. При этом сигнал запуска «оступит на вхо- 20 ды а группы распреде.«ителей 3) уровней блока 6. На выходах й, распределителей 31 уровней появятся сигналы, которые, поступая на управляющие входы блока 2 коммутации, откроют соот- 25 ветствую«>«ие ключи 32 первой группы.

При этом сигналы, пропорциональны

Г (I), с выходов блока ) поступают на неинвертиру«>шие входы операционных усилителей 8 блока 3. Ключи 9 3р блока 3 открыты, так как на их управляющие входы поступают сигналы с инвертирующего выхода триггера 20 блока 6 управления. Поэтому с выходов суммирующих усилителсй 8 блока 3 сигналы поступают на входы блока 5 выбора максимума.

Блок 5 работает следующим образом.

С входов блока 5 сигналы через токозадающие резисторы 11 поступают на 40 входы операционных усилителей 10.

Выходной сигнал появится на выходе того операционного усилителя 10 °, на входе которого будет присутствовать наибольший сигнал. Этот сигнал посту- 45 лает на управляющий вход ключа 15, и открывает его. Пусть, например, максималь«<«,«й сигнал присутствует на входе первого операционного ус«)лйтеля 10<, тогда откроется ключ 15, и на первом выходе блока 5 появится вы50 ходной сигнал, который поступит на первый вход элемента ИЛИ 30 блока 6, на счет«<ый вход счетчика 28< группы блока 6 и на вход элемента И 29, группы блока 6. С выхода элемента ИДИ

30 блока 6 сигнал поступит на счетный вход счетчика 19 и на вход установки в единицу триггера 20.

Триггер 20 переходит в еди«ичп< е состояние. Высокий потенциал с его инверсного выхода перестает поступат« на управляя><>«««««е входы ключей 9 б««о ка

3. Ключи закрывая>тся. Тем самым п)>екраща е т ся нос тупле ние входных с иг «< алов на входы блока 5. Счетчики 28, и 19 изменяют свое содержимое на единицу, с прямого выхода триггера 20 блока 6 сигнал поступает на э:«емент

21 а с выхода элемента И

29, группы блока 6 — на вход с распределителя 31, уровней группы. При этом происходит переключение сигнала с выхода <1 на выход й<. Ключ 32, первой группы первого узла 2< коммутации блока 2 закроется и откроются ключи 32 первой группы И 33, второй группы первого узла 2, коммутации блока 2. Сигнал, пропорциональный

f (2), появится на первом выходе пер«и>го узла коммутации 21, а сигнал, пропорциональный Г,(i) — на втором выходе первого узла 2, коммутации блока 2. Эти сигналы поступят соответственно на неинвертирующий и инвертирующий входы операционного усилителя 8, блока 3. На выходе операционного усилителя 8, будет формироваться сигнал, пропорциональный

Л),(х ) = f,(2) — f<(1). Кроме того, сигнал> пропорциональный f <(I), поступает на первый вход сумматора 16 блока 4, и показания индикатора )7 станут пропорциональны Г,(«).

К этому моменту сигнал с выхода элемента 21 задержки блока 6 через разделительный диод 25 поступит на вход установки в "0" триггера 20 блока 6. Триггер перейдет в нулевое состояние. Выходной сигнал с его инверсного выхода откроет ключи 9 блока 3.

На этом первый ««iar работы устройства заканчивается. Дальнейшая работа устройства будет проходить аналогично.

На последнем шаге решения с выхода счетчика 19 блока 6 сигнал переполнения поступит на управляющий вход ключа 22 и через элемент HE — на входы элементов И 29 группы, прекращая работу устройства. Ключ 22 откроется и элемент 23 индикации сработает. 3aroрание элемента 23 индикации свидетельствует об окончании работы.

Показания индикаторных счетчиков

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

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

31 уровней сигналом по входу b возвращается н исходное состояние.

Аналогичным образом решается задачи при линеиных 1 (х ) и ограниче 15

IVl ниях вида à х В, x E jo lj (i=

-I

1, m), т.е. задача, решаемая с помощью известного устройства. При подготовке исходных данных необходимо каждую функцию а, х, представить в виде С (х ) = (c, /à )У,, где у; = О, 1, 2,..., а,, а счетчик 39 установить перед началом решения в состояние (N-B), где В =, а . Линейность

1 функций g, (х,) обеспечивает постоянство приращений 6q; (y, ) = ц (y„, ) — Ч;(у,), а следовательно, и возможность определения значений x = 1

30 при у, = а, и х, = О в противном случае.

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

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

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

ИЛИ являются группой входов блока, первый вход j — го элемента И грутшы объединен с информационным входом

j-го индикаторного счетчика группы (j = 1, 2,..., m) и объединен с j-м входом элемента ИЛИ, вторые входы всех элементов И группы объединены и подключены к выходу элемента НЕ, вход которого подключен к выходу счетчика, выход счетчика подключен к управляющему входу ключа, выход которого подключен к входу индикаторного элемента, а информационный вход ключа подключен к шине питания, выход элемента ИЛИ подключен к входу счетчика и к единичному входу триггера, прямой выход которого через последовательно соединенные элемент задержки и первый разделительный диод подключен к входу установки в "Оп триггера, входы установки в "0" индикаторных счетчиков группы и счетчика объединены и подключены к аноду второго разделительного диода и через выключатель со единены с шиной питания, катод второго разделительного диода . подключен к входу установки нуля триггера, инверсный выход триггера является выходом блока, информационные входы всех распределителей уровня группы объединены и являются вхо 7 1372335 Я дом запуска б,пока, входы установки в исходное состояние всех распределителей уровней группы объединены с входом установки в "0 счетчика, пе5 рекличавщий вход каждого j-ro pacnpeделителя уровня группы подключен к выходу j-ro элемента И группы, группа выходов „ -".a распределителя уровня группы является j-и группой информационных выходов блока.

1372335

0m Юлаева Ю

Составитель Т.Сапунова

Техред М.Ходанич

Редактор В.Данко

Корректор Г1.Пилипенко

Заказ 484/41 Тираж 704 Подписное

В11ИИЛИ Государственного комитета СССР по делам изобретений и открытий

)13035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектпан, 4