Устройство для моделирования задач

т

*1 у !

) !

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Сова Советских

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

Республик

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

Заявлено 06,III 1968 (¹ 1223407/18-24) с присоединением заявки №вЂ”

11риоритет

Опубликовано 05Х.1969. Бюллетень № 16

Дата опубликования описания 12.IX.1969

Кл. 42mI, 7/48

1ПК 6 06g

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

СССР

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

М. М. Манзон

Московский энергетический институт

Заявитель

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

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И

ЛИНЕЙНОЙ АЛГЕБРЫ

Изобретение относится к области электронной аналоговой техники.

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

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

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

Схема устройства, приведена на чертеже.

Основными элементами предлагаемого устройства являются матрица М переменных проводимостей с запоминающими конденсаторами, амплитудный компаратор АК и триггерный счетчик С, связанный через диодный матричный дешифратор Д "матрицей М прово2 димостей. Счетчик охвачен импульсной обратной связью через кипп-реле К.

Коэффициенты решаемой системы уравнений моделируются проводимостями резисторов ас, ао, аоа... матрицы M. Резисторы дешифратора также переменные. Их проводимости устанавли|ваются равными суммам проводимостей резисторов матрицы, подключенных к соответствующей шине дешифратора.

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

Для приведения устройства в действие достаточно нажатием кнопки запустить кипи-реле. Через определенный интервал времени кипп-реле автоматически сбрасывается и выдает импульс, поступающий на вход счетчика.

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

243278

Напряжение,,подаваемое через диод на ле- 25 вый вход амплитудного компаратора, постоянЕ но и равно —. Мгновенное значение погенци2 ала первой шины,дешифратора в возбужденном состоянии выразится так 30 з а»Х +адг Хо+а о Хо+а о П,+Е Q а1 =о

У1

)

2 а1 35

1=0 где Х Хг... — потенциалы вертикальных шин матрицы.

Это напряжение через диод поступает на правый вход амплитудного компаратора, ко- 40 торый срабатывает в момент равенства напряжений на обоих входах. Приравнивая написанные выражения, .получим а„Х,+а„Х,+а„Х,-+-а„П,=О. (1)

Пренебрегая пульсациями напряжений

Х1, Хз, Хз, можно считать, что равенство (1) выполняется во все моменты времени. Аналогичным путем получаем равенства

a„Xj+ a„Xà т ага Хо+ агоП1 =0 а,,Х, +а„Х,- - а„Х,+а„П,=О. (2) (3) Постоянное напряжение П1 определяет масптаб неизвестных.

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

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

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

С приходом последнего импульса серии счетчик сбрасывается в пулевое состояние и выдает импульс переполнения, который запускает кипп-реле. "1ерез определенный интервал времени капп-реле сбрасывается, и цикл 15 работы схемы автоматически повторяется.

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

Роль искомых неизвестных играют постоян- 20 ные составляющие напряжения на горизонтальных или вертикальных шинах матрицы проводимостей. з

a» Ye+ay Y+aз1Уз+ао1Пг=Х1 « а 1 о

3 а„У,+а„У,+а„У,+аогПг — Хг, айаг> о з а13 У1+аго Уг+азз YЗ+аозПг 3 Q aD ° о (4) (6) Если положить П вЂ” — О, то из уравнений (1), (2) и (3) получим Xi=0; Хо — — 0; Хз— — = О. Тогда в уравнениях (4), (5) и (6),правые части обращаются в,нуль и уравнения .принимают вид а» Y,=a„Yг+a„Yç+aî,Ïð — О> (7) а„У + а.„У,+а„Уо 1- огПг — О, (8)

a ç У, 1 a„Yôya„Y,+аозПг — О. (9) Эти уравнения могут быть использованы для моделирования сопряженной системы уравнений с транспонированной матрицей.

Масштаб неизвестных У1, Уз, Уз определяется напряжением Пз. Это соответствует сигмааналоговому методу моделирования.

В предлагаемом устройстве как мгновенные, так и средние значения потенциалов У>,.

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

В данном примере уравнения (7) и (8) можно рассматривать как ограничения, наложенные на неотрицательные переменные У1, У >, Уз, а коэффициенты уравнения (9) как коэффициенты целевой функции. Величина целевой функции моделируется проводимостью аоз. Принудительный, ввод целевой функции осуществляется путем изменения этой проводимости в желаемом направлении до тех пор, пока система ограничений станет несовместной, т. е. потенциалы Х,; Хq, Лз станут отклоняться от нуля.

Можно осуществить моделирование задач линейного программирования и по ро-аналоговому,методу. В этом случае роль неизвестных будут играть напряжения на конденсаторах (A>, Хз, Хз). Для обеспечения неотрицательности этих напряжений конденсаторы можно зашунтировать диодами.

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

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

Рсдакзор Л. А. Утехина Техред А. А. Камышникова Корректор Т. П. Лаврухина

Заказ 2288;1; Тираж 480 Подписно".

Ill Ï .ÈÃ1È Комитета по дедам изобретений ii открытий при Совстс Министров CCCP

Москва, Центр, пр. Серова, д. 4

Типография, пр. Сапунова, 2 меряются и рассматриваются как решение задачи.

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

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

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

10 соединен с выходами кипи-реле и амплитудного компаратора, один из входов которого соединен через диоды с горизонтальными шинами матрицы, а другой — с делителем напряже|ния.