Устройство для моделирования задач линейного программирования Советский патент 1986 года по МПК G06G7/48 

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

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

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

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

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

X (Х , Х , . . . , ) задачи линейного программирования, храняп);ееся в регистрах 7, используется в качестве начального приближения Х° X при поиске оптимального решения X (X , X 5.,.Д) текущей задачи линейного программирования. Возможны два режима работы устройства.

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

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

iMaKf (.11 О.Л«..---.,. н-)ин. . ,.-°,, , ()

х.0,...,х.о.(.3)

Коэффициенты о. решаемой системь уравнений моделируются проводимостя- ми резисторов матрицы 2, значения Х - напряжениями на ее выходах (сто бПах) ,

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

Е

г-не сработает схема 4 сравнения,

сигнал с выхода которой поступает на вход счетчика 5, увеличивая его содер жимое на 1. Возбуждается второй разрядный выход дешифратора 1, и далее устройство работает аналогично.

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

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

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

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

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

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

Время tj, достижения решения текущей задачи в известном устройстве пропорционально величине make. X,. определяемой максимальным временем заряда i-ro конденсатора в группе запоминающих элементов 3.

Время t достижения того же решения предлагаемым устройством пропорционально величине njakc(X, о т.е. меньше t.

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

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

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

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

1поизводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4