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

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

28IOI2

Союз Советских

Социалистических

Республик (у-в и т ъ @ мхта д.

М.,:„:, . cgy>

Зависимое от авт. свидетельства №

Кл. 42m>, 15/30

Заявлено 12.1 V.1969 (№ 1320594/18- 24) с присоединением заявки №

МПК С 061 15/30

УДК 681.325.6(088.8) Комитет па делам изобретений и открытий при Совете Министров

СССР

Приоритет

Опубликовано 03.1Х.1970, Бюллетень ¹ 28

Дата опубликования описания 25.XI.1970

Авторы изобретения

В. В. Васильев и Л. И. Костенко

Институт кибернетики АН Украинской ССР

Заявитель

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОГО

РАСПРЕДЕЛЕНИЯ НЕОДНОРОДНЫХ РЕСУРСОВ кой матрицы функционал х,, которая максимизирует

В последних выражениях а,, = — Iп (1 — Wij); 6,, = In (р, а„)

U; некоторое число, которому равны все не нулевые компоненты матрицы

Iп

20 дх;.

Для решения задачи применяется метод последовательного сокр ащения невязок. Вначале U; принимают достаточно большими и

25 все хц равны О. Затем поочередно уменьшают все зйачения U,, чтобы на каждом шаге выи полнялись равенства g х;, = С,.

j=l

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

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

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

Задача оптимального распределения неоднородных ресурсов состоит в определении таf(x) = > Р; (1 — П (1 — W, j)"j)

j=l г- 1 при выполнении условий: х,- 0;,х,у =- С, 1

Известно, что в точке оптимума выполняются условия:

1п = 0.. п..х (U ПРи хну + 0 д.-" " --, " ") U при х,.=0.

1! i =-1 j

28101 2 деления в 1-м столбце приводит к уменьшению остальных значений хт1 в этом столбце. Поэтому на каждом шаге итерационного процесса необходимо монотонно уменьшать U;. Монотонность процесса обеспечивает ему сходи- 5 мость. Приведенный итерационный IIlp01lñсс реализуется в предлагаемом устройстве с той разницей, что все U; определяются одновременно.

Предложен.ве устройство изображено на 10 чертеже. Оно состоит из регистров 1 — 9, схемы 10 формирования счетных импульсов, счетчиков-регистров 11 — 22, запоминающего устройства 28, генератора импульсов 24.

Счетчики 11 — 18 совместно с регистрами 15

1 — 8 образуют схемы с управляемыми коэффициентами пересчета. Значения коэффициентов пересчета определяются кодами чисел в р егистр ах.

Счетчики 17 — 19 вместе с регистрами 7 — 9 20 являются схемами сравнения величин распределяемых и распределенных ресурсов. Значения распределяемых ресурсов определяются кодами чисел в регистрах, а величины распределенных ресурсов получаются при работе 25 устройства в счетчиках 17 — 19.

k егистры 4 — Ь и счетчики-регистры 20 — 22 совместно со c! T÷èêàìè -;.— cb ооразуют схемы для оораоотки распределенных ресурсов в одном из столоцов матрицы распреде- 30 ления. Счетчики 14 — lb являются цифровыми аналогами логарифмов частных производны:. целевой функции одного столоца матрицы распределения. Б счетчиках-регистрах 2U — 22 содержатся коды переменных двойственной за- 35 дачи 0, которые уточняются на каждом шаге итерационного процесса. Регистры 4 — б служат для хранения исходных кодов счетчиков т4 — c o. ,Цля получения решения запоминающее уст- 40 роиство 2D, реализованное, например, на динамических линиях задержки, заносит в регистры 1 — 3 значения коэффициентов пересчета a», a», ..., а,„, в регистры Ф вЂ” b н счетчики

14 — со — начальные значения частных произ- 45 водных целевой функции biq, 0>, ..., Ь„,, а в регистры / — 9 — коды величин ресурсов (;ь, (. . 15 счетчиках 20 — i2 устанавливаются коды произвольных достаточно больших чисел. схема формирования счетных импуль- 50 сов 10 разделяет во времени выходные сигналы схем с управляемыми коэффициентами пересчета (в том случае, если они совпадают) и либо присчитывают эти сигналы к кодам чисел в счетчиках Н вЂ” 16, либо вычитает пх из 55 содержимых этих счетчиков.

Если код числа в каком-либо счетчике, на,пример в 14, "îëüøå кода в соответствующем ему счетчике 20, то выходные сигналы счетчика 11 вычитаются из содержимых счетчиков 60

14 lб. Одновременно импульсы генератора

24 увеличивают код числа в счетчике 17, который перед началом работы устройства устанавливается в нулевое состояние. Этот процесс эквивалентен увеличению значения х„и одновременному уменьшению всех логарифмоз .астных производных целевой функции, находящихся в нервом столбце матрицы рас пределенпя, па величину а х ь Если же код в счетчике 14 меньше кодов в счетчике 20 и регистре 4, то сигналы счетчика 11 складываются с содержимым счетчиков 14 — lб. Одновременно с этим импульсы генератора 24 уменьшают код числа в счетчике 17.

При условии, что содержимое счетчика 14 больше содержимого регистра 4, импульсы счетчика 11 не формируются схемой 10, а импульсы генератора не поступают на вход счетчика 17. Этим обеспечивается неотрицательность переменных.

Процесс уменьшения содержимых счетчиков 14 — lб пропорционально сумме а,, х,, и

i величения кодов в счетчиках 17 — 19 пропорционально хч продолжается до тех пор, пока хотя бы в одном из счетчиков 14 — lб код числа будет больше кода в соответствующем счетчике-регистре 20 — 22.

Следовательно, после отработки элементов первого столбца матрицы распределения коды чисел в каждом из счетчиков 14 — lб будут равны или меньше значений U;, а число импульсов, присчитанных в счетчиках 17 — 19, пропорционально х;-. Лналогично отрабатываются элементы всех столбцов матрицы распределения. При этом в счетчиках 17 — 19 зафиксируются величины распределенных ресурсов, Если они меньше C ;, то коды чисел U; в соответствующих счетчиках 20 — 22 уменьшаются, и приводится очередной шаг итерационнло процесса. Признаком получения решения является совпадение с точностью до заданной величины кодов чисел в счетчиках 17 — 19 с величинами ресурсов, подлежащих распределению.

Предмет изобретения

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

Составитель И. Н. Горелова

Редактор А. А. Глинков Техред А. А. Камышникова Корректор О. Б. Тюрина

Заказ 3405!18 Тираж 430 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий прп Совете Министров СССР

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

Типография, пр. Сапунова, 2