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

 

CQO3 СОБЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (5ц 4 G 06 G 7/48

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНЯТИЙ г " Е (И"

И ;

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

К ABTOPCHOMY СВИДЕТЕЛЪСТВУ ИВА Р, (21) 3697332/24-24 (22) 15. 12. 83 (46) 23.04.86. Бюл. У 15 (71) Оренбургский политехнический институт (72) В.Е.Кацман, В.А.Волков и Т.В.Волкова . (53) 681.333(088.8) (56) Авторское свидетельство СССР

Ф 752363, кл. G 06 G 7/122, 1978.

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

Ф 243278, кл. С 06 G 7/48, 1968. (54) (57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ содержащее счетчик, генератор импульсов,дешифратор, матрицу масштабных резисторов,к горизонтальным и вертикальным шинам которой подключены соответственно одни и другие выходы масштабных резисторов, схему сравнения, группу запоминающих элементов и источник опорного напряжения, выход которого подключен к первому входу схемы сравнения и входу задания опорного напряжения дешифратора, разрядные выходы которого соединены с горизонтальными шинами матрицы масштабных резисторов и вторым входом схемы сравнения, первый и второй выходы счетчика подключены соответст„„SU„„. 1226495 А венно к входу запуска генератора импульсов и информационному входу дешифратора, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены группа регистров, груПпа цифроаналоговых преобразователей, группа коммутаторов, группа элементов ИЛИ и элемент задержки, вход и выход которого соединены соответственно с выходом генератора импульсов и входом счетчика, выходы регистров группы подключены к информационным входам соответствующих цифроаналоговых преобразователей группы, входы задания опорного напряжения которых объединены и сое- @ динены с выходом источника опо-,.лого напряжения, выходы цифроаналоговых

Ф преобразователей группы подключены С„ к информационным входам соответствуМ ющих коммутаторов группы, управляющие Я входы которых объединены и соединены

О еЕ с выходом генератора импульсов,выходы коммутаторов подключены к первым а вертикальные шины матрицы масштабных резисторов — к вторым входам со- Ж ответствующих элементов KIN группы, 4 выходы которых соединены с входами („ф соответствующих запоминающих элемен- (;Я тов группы.

I >

0, Х -а X +...a, Х --3 "", <1

„1 1 12 2 1>1 >

> I а. х ° o x -..a Х = э„, >2 2 ln u (2) х >0,..., Y„)o

Коэффициенты а. решаемой сис темы уравнений моделируются проводимостями резисторов матрицы 2, значения

Х. — напряжениями на ее выходах (стол-.

> б1тах) . Ю

Процесс моделирования начинается с внешнего запуска генератора 6„ который формирует импульс, поступа-Изобретение относится к вычислительной технике и может быть использовано для .решения задач линейнс>га програьжирования (текущего и оперативного планирования, управления, рас- 5 пределения ресурсов и т.п.)„ требующих повторных решений через некоторые интервалы времени (час, сутки, месяц и т.д) .

Цель изобретения — повышение быст- 10 родействия..

На чертеже представлена Функцио-= нальная схема устройства.

Устройство содержит дешифратор 1, матрицу 2 масштабных резисторов„груп- 15 пу запоминающих элементов 3, схему сравнения, счетчик 5, генератор 6 импульсов, группу резисторов 7> группу цифроаналоговых преобразователей 8, группу коммутаторов 9, элемент 10 2С> задержки, источник 11 опорнога напряжения, группу элементов ИЛИ 12.

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

Х = (Х„, Х,...,Х ) задачи линейного программирования, хранящееся в регистрах 7, используется в качестве начального приближения Х = Х

3() при поиске оптимального решения Х (Х,, Х,...,Х„ ) текущей задачи линейного программирования. Возможны дга режима работы устройства.

Режим 1. Самое первое решение задачи линейного программирования„ для - 5 которой предыдущая задача не решалась, осуществляется в том же режиме, что и при работе известного устройства, при этом в регистрах 7 хранятся коды начальных значений переменных, равные О.

Проводится моделирование задачи линейного программирования вида., ющий через элемент 10 задержки на

:вход счетчика 5, в счетчик записыва>l ется 1, и возбуждается первый разрядный выход дешифратора 1. При этом диоды дешифратора i, подключенные к: этому выходу, закрываются и начинается заряд конденсаторов запоминак>щих элементов 3 от источника 11 напряжения E через резисторы первой строки матрицы 2 и элементы ИЛИ 12.

Па мере заряда конденсаторов потенциал этой строки матрицы 2 повышается да тех пор, пока при совпадении указанного потенциала с величиной

Š— не сработает схема 4 сравнения, сигнал с выхода которой поступает на вход счетчика 5, увеличивая его содер кимое на 1. Возбуждается второй разрядный выход дешифратора 1, и далее устройства работает аналогично, При поступлении последнего импульса серии счетчик 5 выдает сигнал переполнения, вновь запускающий генератор 6, Затем цикл работы устройства автоматически повторяется, цикличсскае повторение процесса моделирования необходимо для восстановления точного решения Х полученного на запоминающих элементах 3 (конденсаторах), которые к концу каждого цикла нескальк:о разряжаются .

Режим 2. Моделирование последующей задачи линейного программирования> ,цля которой задано начальное приближение Х" как результат решения Х

1>> предьдущей задачи, выполняется сле,цующнм образом.

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

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

С приходом первого импульса генератора 6 на управляющие входы коммутаторов 9 напряжения с их выходов, пропорциональные кодам X начальных значений переменных, заносятся в группу запоминающих элементов 3. Затем импульс генератора 6 через элемент

10 задержки поступает на вход счетчика 5.

Составитель А.Шеренков

Редактор О.Бугир Техред Л.Олейник Корректор Е.Сирохман

Заказ 2136/50 Тираж 671 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4!5 производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

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

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

95 4 необходимо (как и в режиме 1) для восстановления точного решения.

Время t „ достижения решения текущей задачи в известном устройстве пропорционально величине make. Х

l;i) определяемой максимальным временем заряда i-ro конденсатора в группе запоминающих элементов 3.

Время t достижения того же решения предлагаемым устройством пропорционально величине make(X -Х . ) (l) (il т.е. меньше t