Всесоюзная

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Сои)д Советских

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

Республик

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

Заявлено 11.IX.1969 (№ 1360320/18-24) с присоединением заявки №вЂ”

Приоритет

Опубликовано 20.111.1973. Бюллетень № 15

Дата опубликования описания 5Х1.1973

М. Кл. G 06K 7/48

Комитет по делам изобретений и отнрытий ори Совете Министров

СССР

УДК 681.332.4 (088.8) Авторы изобретения

А. Г. Тимошенко и Э. 3. Трайнин

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

Заявитель

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

РАСПРЕДЕЛЕНИЯ ОДНОРОДНОГО РЕСУРСА

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

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

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

С этой целью в устройство введены ин вертирующий усилитель, элемент аналоговой памяти, два распределителя импульсов и конденсаторы.

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

Устройство содержит регулируемые источники э.д.с. 1 — 9; управляемые ключи 10 — 27; инвертирующий усилитель 28; двухвходовые суммирующие усилители постоянного тока

29 — 81; конденсаторы 82 — 84; элементы 35 — 87 аналоговой памяти на усилителях постоянного тока; распределитель импульсов 88; выходы

10 89 — 43 распределителя импульсов 88; логические схемы разделения 44 и 45; распределитель импульсов 4б; выходы 47 и 48 распределителя импульсов 4б; шина нулевого потенциала 49.

Источники 1 —.9 предназначены для модели1 рования коэффициентов исходной матрицы.

Коэффициенты строк матрицы выражают степень дохода от вложения в пункты потребления долей ресурса, равных нулю для первой строки, единице — для второй и двум — для

20 третьей.

Ключи 10 — 12 предназначены для поэтапного подключения шины нулевого потенциала 49 к входам источников э.д.с., моделирующих коэффициенты соответствующих столбцов мат25 рицы.

Ключи 18 — 21 служат для подключения выходов источников э.д.с., к вторым входам соответствующих суммирующих усилителей. При этом попарно суммируются напряжения, моЗО делирующие такие коэффициенты произ374626

65 вольных двух столбцов, сумма индексов которых (2.

Двухвходовые суммирующие усилители постоянного тока, собранные в схему индикатора экстремального напряжения, предназначены для формирования соответствующих сумм из двух напряжений и выбора максимальной из них. Это напряжение фиксируется соответствующим элементом 85 — 87 аналоговой памяти.

Принцип работы устройства состоит в следующем.

На первом цикле оптимизации ресурс распределяется между двумя произвольными пунктами потребления, например между первым и вторым.

Потенциал с выхода 47 распределителя импульсов 4б замыкает ключи 11 и 12; присоединяющие шину нулевого потенциала 49 на входы источников э.д.с., моделирующих коэффициенты первого и второго столбцов матрицы.

На каждом такте работы устройства потенциалы с выходов 89 — 41 распределителя импульсов 88 включают те ключи устройства, с помощью которых на вторые входы суммирующих усилителей поступают напряжения соответствующих источников э. д. с.

На первом такте распределяется доля ресурса, равная нулю, на втором — единице и т. д.

Так например, на третьем такте генератора импульсов замыкаются ключи 15, 1б, 18, 19, 20, 21 и 27, при этом на суммирующем усилителе

29 суммируются напряжения источников э.д.с.

9 и 8, а на суммирующих усилителях 80 и 81— источников 5 и б и 2 и 9, Максимальная из этих сумм через ключ 27 поступает на вход элемента аналоговой памяти 87. Таким ооразом, после трех тактов работы устройства выполняется оптимальное распределение ресурса и всех его частей по двум пунктам потребления, При этом величина напряжения на выходе индикатора экстремального напряжения соответствует ожидаемому доходу от полученного распределения двух единиц ресурса, а место экстремума определяет стратегию распределения.

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

Таким образом, после первого цикла оптимизации на элементах аналоговой памяти

85 — 87 будут зафиксированы напряжения, полученные в результате оптимального распределения ресурса между первым и вторым пунктами потребления.

При следующем такте работы устройства замыкаются ключи 22, 24, 2б и указанн ые напряжения передаются на первые входы соответствующих суммирующих усилителей, где запоминаются конденсаторами 82 — 84.

При последнем такте работы устройства потенциал с выхода 48 распределителя импульсов 89 поступает на вход распределителя импульсов 4б. При этом, усправляющий потенциал появится на выходе 48 распределителя импульсов 4б, и к шине нулевого потенциала

49 подключается источники э.д. с. 1, 4, 7, моделирующие коэффициенты третьего столбца матрицы.

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

Этот процесс несложно автоматизировать.

При количестве пунктов потребления, равном

m, задача будет решена максимум после

/m — 1/ циклов оптимизации. Количество суммирующих усилителей и устройств аналоговой памяти зависит только от числа частей ресурса /и+ 1/ и не зависит только от числа пунктов потребления.

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

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

Составитель Е. Тимохина

Техред Л. Грачева

Корректор Е. Талалаева

Редактор Н. Данилович

Заказ 1564/17 Изд Ъг, 376 Тираж 647 Подписное

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

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

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