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

ОПИСАНИЕИЗОБРЕТЕН ИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 281012 Союз Советских Социалистических Республик( 1320594/18-2 Заявлено 12.1 Ч.196с присоединениемПриоритетОпубликовано 03.1 аявкиПК С 06 15/3 Комитет па делам изобретений и открытий при Совете Министров СССР,1970, Бюллетень28 а опубликования описания 25.Х 1.1970 Авторыизобретения В, В, Васильев и Л, И. Костенко ститут кибернетики АН Украинской ССвитель ЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОГОЯ НЕОДНОРОДНЫХ РЕСУРСОВ ТРОЙСТВО ДЛ РАСПРЕДЕЛ ой матрицьфункционалНх) = максимизируе котора вычислительнои лектронного моого планироваЛ П Ур,.1 - ЦИ - к=1 г 1) Е) Я.Известно решение подобных задач на универсальных цифровых вычислительных маши. нах с использованием счетчиков, регистров, запоминающих устройств.Предложенное устройство отличается тем. что оно содержит схемы с управляемыми коэффициентами пересчета, схемы отработки распределенных ресурсов и схемы сравнения величин распределенных и распределяемых ресурсов, установочнье входы которых соединены с запоминающим устройством, а счетные входы схем с управляемыми коэффициентами пересчета и схем сравнения соединены с пенератором импульсов, выходы схем с управляемыми коэффициентами пересчета соединены с входами схемы формирования счетных импульсов, выход которой подключен ко входам схем отработки распределенных ресурсов, которые соединены со схемами сравнения величин распределенных и распределяемых ресурсов. Устройство позволяет получить решение рассматриваемой задачи с оольшой точностью и обеспечить возможность автоматического ввода исходных данных.Задача оптимального распределения неоднородных ресурсов состоит в определении та 5 при выполнен и условии: ; З О; , х =- С в точке оптимп а выпо звестно, чт условия: дх " Ц. 1 п =6 -ах с а О т-:1 и х;,)Опри х,;=О В последних выражениях а = - 1 п(1 - %); 6 У; некоторое число, котор нулевые компоненты матриц 1 п 20 дх; Для решения задачи и последовательного сокр аще чале У; принимают доста все х;, равны О. Затем поо все зйачения У чтобы на и,. = 1 п(р,. а)ом равны все не рименяется методния невязок. Внаточно большими иередно уменьшаюткаждом шаге вы лнялись равенствах, = С В связи с тем, что ресурсы зависимы, у0 личение любой из компонент матрицы расп Предложение относится к технике и предназначено для делирования задач оптимал ниделения в 1-м столбце приводит к уменьшению остальных значений хт 1 в этом столбце, Поэтому на каждом шаге итерационного процесса необходимо монотонно уменьшать с 1;. Монотонность процесса обеспечивает ему сходи мость. Приведенный итерационный процесс реализуется в предлагаемом устройстве с той разницей, что все 0; определяются одновременно.Предложенное устройство изображено на 10 чертеже. Оно состоит из регистров 1 - 9, схемы 10 формирования счетных импульсов, счет. чиков-регистров 11 - 22, запоминающего устройства 23, генератора импульсов 24.Счетчики 11 - 13 совместно с регистрами 15 1 - 3 образуют схемы с управляемыми коэффициентами пересчета. Значения коэффициентов пересчета определяются кодами чисел в р егистр ах.Счетчики 17 - 19 вместе с регистрами 7 - 9 20 являются схемами сравнения величин распределяемых и распределенных ресурсов. Значения распределяемых ресурсов определяются кодами чисел в регистрах, а величины распределенных ресурсов получаются при работе 25 устройства в счетчиках 17 - 19.Регистры 4 - Ь и счетчики-регистры 20 - 22 совместно со счетчиками - - сб ооразуют схемы для оораоотки распределенных ресурсов в одном из столоцов матрицы распреде ления, Счетчики 14 - 1 Ь являются цифровыми аналогами логарифмов частных производных целевой функции одного столоца матрицы распределения. Б счетчиках-регистрах 20 - 22 содержатся коды переменных двойственной за дачи /, которые уточняются на каждом шаге итерационного процесса. Регистры 4 - б служат для хранения исходных кодов счетчиков т 4 - со.,Цля получения решения запоминающее уст роиство 2 д, реализованное, например, на динамических линиях задержки, заносит в регистры 1 - 3 значения коэффициентов пересчета а а , , а в регистры Ф - Ь н счетчики 14 - сь - начальные значения частных произ водных целевой функции Ьь О, Ь а в регистры 7 - 9 - коды величин ресурсов (;, С . 15 счетчиках 20 - 2 устанавливаются коды произвольных достаточно больших чисел. Схема формирования счетных импуль сов 10 разделяет во времени выходные сигналы схем с управляемыми коэффициентами пересчета в том случае, если они совпадают) и либо присчитывают эти сигналы к кодам чисел в счетчиках Н - 16, либо вычитает пх из 55 содержимых этих счетчиков.Если код числа в каком-либо счетчике, на,пример в 14, больше кода в соответствующем ему счетчике 20, то выходные сигналы счетчика 11 вычитаются из содержимых счетчиков 60 14 1 б. Одновременно импульсы генератора 24 увеличивают код числа в счетчике 17, который перед началом работы устройства устанавливается в нулевое состояние. Этот процесс эквивалентен увеличению значения хи одновременному уменьшению всех логарифмоз .астных производных целевой функции, находящихся в нервом столбце матрицы распределенпя, па величину ах. Если же код в счетчике 14 меньше кодов в счетчике 20 и регистре 4, то сигналы счетчика П складываются с содержимым счетчиков 14 - 1 б. Одновременно с этим импульсы генератора 24 уменьшают код числа в счетчике 17.При условии, что содержимое счетчика 14 больше содержимого регистра 4, импульсы счетчика 11 не формируются схемой 10, а импульсы генератора не поступают на вход счетчика 17, Этим обеспечивается неотрицательность переменных,Процесс уменьшения содержимых счетчиков 14 - 1 б пропорционально сумме а х и увеличения кодов в счетчиках 17 - 19 пропорционально хи продолжается до тех пор, пока хотя бы в одном из счетчиков 14 - 1 б код числа будет больше кода в соответствующем счетчике-регистре 20 - 22.Следовательно, после отработки элементов первого столбца матрицы распределения коды чисел в каждом из счетчиков 14 - 1 б будут равны или меньше значений l;, а число импульсов, присчитанных в счетчиках 17 - 19, пропорционально х; . Лналогично отрабатываются элементы всех столбцов матрицы распределения. При этом в счетчиках 17 - 19 зафиксируются величины распределенных ресурсов, Если они меньше С;, то коды чисел (/,. в соответствующих счетчиках 20 - 22 уменьшаются, и приводится очередной шаг итерационнло процесса. Признаком получения решения является совпадение с точностью до заданной величины кодов чисел в счетчиках 17 - 19 с величинами ресурсов, подлежащих распределению,Предмет изобретенияУстройство для решения задачи оптимального распределения неоднородных ресурсов, содержащее генератор импульсов, регистры, счетчики, запоминающее устройство, отличающееся тем, что, с целью упрощения и повышения точности, оно содержит выполненные на регистрах и счетчиках схемы с управляемыми коэффициентами пересчета, схемы отработки распределенных ресурсов и схемы сравнения величин распределенных и распределяемыхресурсов, установочные входы которых соединены с запоминающим устройством, а счетные входы схем с управляемыми коэффициентами ,пересчета и схемы сравнения соединены с генератором импульсов, выходы схем с управляемыми коэффициентами пересчета соединены с входами схемы формирования счетных импульсов, выход ксторой подключен ко вхо. дам схем отработки распределенных ресурсов, соединенным со схемами сравнения величин распределенных и распределяемых ресурсов,281012 Составитель И. Н. Горелова Техред А, А. Камышиикова Корректор О, Б. Тюрина Редактор А. А. Глинк пография, пр. Сапунова, 2 Заказ 3405/18ЦНИИПИ Комите Тираж 480делам изобретений и открытий прп Совете МинисМосква, Ж, Раушская наб., д. 4/5 одписнов ССС