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

Изобретение относится к вычислительной технике, и может быть йсполь эовано при исследовании задач матема тического программиро.вания, а также в качестве технического средства обу чения при изучении задач математичес кого анализа и нелинейного програм.мирования. Известно устройство для решения задач математического программирования, содержащее ангшоги систем функций, аналоги систем неравенства и аналог целевой функции 1 . Наиболее близким по технической сущности к изобретению является.устройство для решения задач математического программирования, содержащее блоки-аналоги систем функций, блоканалог целевой функции, аналог сисteM неравенств, преобразователь неравенств в уравнения, формирователь штрафной функции, резистор и переключатель С2 . Недостатками известных устройств являются низкое быстродействие и то, что они не позволяют формировать сигналы, необходимле для отображения ограничений решаемой задачи на электроннолучевом индикаторе. Цель изобретения - повьваение быстродействия и расширение функцио-, нальных возможностей за счет отображения ограничений решаемой задачи на индикаторе. Поставленная цель достигается тем, что в устройство, содержащее две Я-сетки, входы которыхявляются входом устройства, введены блок пороговых элементов, блок форкшрователей импульсов, элемент ИЛИ, электроннолучевой инда1катор, генератор тактовых импульсов, два интегратора, два триггера и блок управления, состоящий из двух счетчиков, двух селекторов кодов, элемента ИЛИ. и двух формирователей импульсов, выходам которых подключены соответственно к первсм и второму входам элемента ИЛИ, выход которого соединен с входом яркостной модуляции электроннолучевого индикатора , выход генератора тактовых импульсов подключен к счетному входу первого счетчика, выход переполнения которого соединен с входом второго формирователя импульсов, с входом первого триггера и со счетным входом второго счетчика, выход переполнения которого соединен с входом первого форм1рователя импульсов и с входом второго триггера, первого и второго триггеров соединены с входами соответственно первого и второго интеграторов, выходы которых подключены к входам отклонения луча электроннолучевого индикатора и к информационным входам первой и второй R-сеток, выходы которых соединены соответственно с первы1 5-и вторым входами блока пороговых элементов, группа выходов которого непосредственно и через блок формирователей импульсов подключена соответственно к первой и второй группам, входов элемента ИЛИ третий вход которого соединен с выхо дом элемента ИЛИ блока управления, группы информационных выходов первого и второго счетчиков подключены со ответственно к группс1М входов первог и второго селекторов кодов, выходы которых соединены соответственно с первым и вторым входами элементов ИЛ блока управления. На фиг,1 представлена блок-схема устройства для решения задач математического программирования; на фиг.2 диаграммы, поясняющие работу предлагаемого устройства. Устройство для рйыения задач мате матического программирования содержи R-сетки 1 и 2, блок 3 пороговых элементов, блок 4 формирователей импуль сов, элемент ИЛИ 5, электроннолучево индикатор 6, блок 7 управления, инте раторы 8 и 3, триггеры 10. и 11, блок 12, блок 7 управления .содержит форми рователи 13 и 14 импульсов, счетчики 15 и 16, селекторы 17 и 18кодов, элемент ИЛИ 19. . Уттройство предназначено для реше ния задач нелинейного програнашроваФ(х,Р)0; Гтах/a f(x} . сдв Ф - конечный оператор; f - скалярная Функция; X - вектор неизвестных; F - вектор иэвестных величин; /U целевая функция. Соответственно л ввиду этой решаемой задачи матрица 1 реэисторов-аналог систем функций и матрица 2 резис торов - аналог целевой функции представляют собой нелинейные функциональные многополюсники, содержащие нелинейные резисторы, функциональные преобразователи одной и нескольких независимых переменных, структура и параметры которых должны быть выбраны в соответствии с условиями (1) и (2). Блок 3 пороговых элементов содержит операционные усилители и аналого вые инверторы. В качестве пороговых элементов и аналоговых инверторов бл ка 3 использованы интегральные операционные усилители. Блок 4 формирователей импульсов содержит формирователи коротких импульсов и построен на основе интегральных компараторов. R-сетка 1 построена по схеме оС -аналога линейных алгебраических уравнений. Устройство работает следующим образе. Блок 7 управления и последовательно .включенные триггер 10 и интегратор 8 и триггер 11 и интегратор 9 обеспечивают формирование сетки прямоугольной системы координат на экране электроннолучевого индикатсфа 6 и сканирование переменшах р иаёмой задачи. Емкость счетчиков 15 и 16 должна соответствовать числу интервалов разбиения экрана индикатора по вертиКсши и горизонтсши. Сигналы переполнения этих счетчиков выполняют две функции: запускают формирователи 13 и 14 импульсов, выходные сигналы кото{%ix игршот роль синхронизирукяцих импульсов, и изменяют состояние счетных триггеров 10 и 11. Информационные кодовые выходы этих же счетчиков после прохождения через селекто ял 17 и 18 кодов и элемент ИЛИ 19 формируют изображение координатной сетки на экране электроннолучевого индикатора 6. Последовательно включенные триггеры 10 и 11 и интеграторы 8 и 9 обеспечивают формирование системы симметричных напряжений треугольной формы, играющих роль переменных моделируемой Задачи. Постоянные времени интег|заторов 8 и 9 должны быть выбраны таким образом, чтобы половина периода формирования треугольного напряжения соответствовала периоду импульсов на выходах счетчиков 15 и 16. Выходные Напряжения интегтэаторов 8 и 9 поступают на входы R-сетки 1 аналогов системы функций и R-сетки 2 аналога целевой функции-, а также подключены к входам вертикального и горизонтального отклонения индикатора 6. При подаче на входы R-сетки 1 и R-сетки 2, соответственно, аналога систем функций и аналога целевой функции, напряжений треугольной формы, с выходов блока генераторов развертки, на их выходах формируются сигналы невязок в условиях (1) и. (2). Эти сигналы после прохождения пороговых элементов блока 3 формируются в двоичные сигналы. Для опредё-; ленности можно принять, что, когда невязки е в условиях задачи (1) и (2), например, отрицательны, на вы-ходах пороговых элементов будут нулевые уровни сигналов, а когда невязки положительны - на выходах порого-. вых элементов будут единичные уровни сигналов. Обращение невязки в нуль будет соответствовать фронту изменения сигнала на выходе порогового эле мента. Так каксигналы развертки электроннолучевого индикатора 6 и входных переменных аналогов системы- функ ций и аналога целевой функции синхро низированы между собой с помощью сиг налов блока 7 управления, выходные сигналы блока 3 пороговых элементов после прохождения через элемент Ш1И S, подсвечивают области определения неравенств условий (1). Блок 4 формирователей импульсов формирует короткие импульсы из перепадов выходных сигналов тех пороговы элементов блока 3 пороговых элинентов, которые соответствуют уравнения и границам неравенств условий (1) и (2), изображения которых необходимо вывести на экране. Продолжительность импульсов этих фохяхирователей определяет толщину линий на экране электроннолучевого индикатора 6. Поскольку входные сигналы элемента ИЛИ 5 являются двоичными цифровым сигналами потенциального и импульсно го вида, этот блок кроме функции сме шивания сигналов может включать в се бя функции их логической обработки при решении. разнообразных з.адач по отображению пересечения или объединения областей, образуемых отдельными группами функций условий задачи (1) и (2). Работу предлагаемого устройства рассмотрим на иллюстративном примере моделирований и отображения задачи линейного программирования. ,-10 О уи. 5х +Х2-« max.(4) На выходах матрицы 1 формируются точки в соответствии с выражениями . 2 2 ,-8 -7 ,+Х2-10 5х +Х2-/ Эти выражения соответствуют условиям моделируемой задачи (3) и (4), записанным в форме с невязками g . Поскольку напряжения х и х, изменяясь во времени, пробегают област изменения выражений (5), токи такж являются функциями времени. Иэменяющиеся токи С поступают на входы .поро говых элементов блока 3 пороговых элементов, т.е. на операционные усилители, в обратной связи которых включены стабилитроны. Рассмотрим работу одного из таких элементов, на входе которого действует ток . При изменении величины х в отрицательной области ток также отрицателен. На выходе олерационно1хэ усилителя появляется положительное напряжение, которое смещает стабилитрон, включенный в обратную связь, в прямом направлении. На выходе этого операционного усилителя положительное напряжение, близкое к нулю (диод стабилитрона открыт, его сопротивление ма1по) . При изменении х в положитель1ной области, ток также положи- тельный, напряжение на выходе операционного усилителя отрицательное и равно напряжению стабилизации стабилитрона, ко-торый смещен в обратном ,направлении. Таким образом, на выходе операционного усилителя нулевое напряжение .тогда, когда нарушается первое из . неравенств условий (3), и отрицательное напряжение - когда это неравенство выполняется, граница между областями выполнения и нарушения неравенства соответствует перепаду выходного напряжения операционного усилителя. Остальные пороговые элементы работают аналогичным образом. Полярность включения стабилитронов в обратную связь операционных усилителей должна соответствовать знак реализуемого неравенства. Поэтому для пороговых элементов отображающих третье, четвертое и пятое неравенства из условий (3), стабилитроны включешл обратной полярностью по отношению к описанному. Аналоговые инверторы, включенные на выходах этих пороговых элементов, необходимы для согласования полярности и уровня сигналов блока 4 формирователей импульсов, элементы которого срабатывают при перепадах определенной полярности. Блок 4 формирователей импульсов формирует короткие, импульсы, соответствующие моментам прохождения компо нент вектора через ноль. Выходные сигналы блока 3 пороговых элементов и блока 4 формирователей импульсов смешиваются в элементе ИЛИ 5. Некоторые из сигналов этих блоков могут не использоваться, если этого не требуют условия (3) и (4). В данном сигналы шестого порогового элемента, а также первого и второго формирователя импульсов в смеситель импульсов не поступают. Выходные- сигналы блока 4 формирователей импульсов поступают на инверсные входы элемента ИЛИ 5. На фиг.2 показана область ограничений моделируемой задачи и изображение целевой функции для нескольких фиксированных ее значений. Точка М соответствует решению задачи линейного программирования для случая мак симилизации целевой функции. Такой же вид имеет изображение на экране электроннолучевого индикатора Технико-экономический эффект применения устройства будет состоять в повышении быстродействия и в расширении функциональных возможностей существующих.аналоговых и гибридных моделирующих систем путем обеспечения отображений условий задач на экране электроннолучевого индикатора, что позволит использовать его также в качестве технического средства обучения. Формула изобретения Устройство для решения згщач математического программирования,.содержащее две R-сетки, входы оторых являются входом устройства, отличающееся тем, что, с целью повышения быстродействия, в него вве дены блок пороговых элементову блок формирователей импульсов, элемент ИЛИ, электроннолучевой индикатор, генератор тактовых импульсов, два ин тегратора, два триггера и блок управ ления, состояьщй из двух счетчиков, двух селекторов кодов, элемента ИЛИ и двух формирователей импульсов, выходы которых подключены соответствен но к первому и второму входам элемен та ИЛИ, выход которого соединен с входом яркостной модуляции электроннолучевого индикатора, выход генератора тактовых импульсов подключен к счетному входу первого счетчика, выход переполнения которого соединен с входом второго формирователя импульсов, с входом первого триггера и со счетным входом второго счетчика, выход переполнения которого соединен с входом первого формирователя импульсов и с входом второго триггера, выходы первого и второго триггеров соединены с входами соответственно первого и второго интеграторов, выходы которых подключены к входам отклонения лу-ча электроннолучевого ингдикатора и к информационным входам первой и второй R-сеток, выходы которых соединены соответственно с первым и вторым входами блока пороговых элеVieHTOB, группа выходов которого непосредственно и через блок формирователей импульсов подключена соответственно к первой и второй группам входов элемента ИЛИ, третий вход которого соединен с выходом элемента ИЛИ блока управления, группы информацио,нных выходов первого и второго счетчиков подключены соответственно к группам входов первого и второго селекторов кодов, выходы которых соединены соответственно с первым и вторьм входами элементов ИЛИ блока управления . Источники инфО1 4ации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР 282761, кл, С Об G 7/34, 1969. 2.Авторское свидетельство СССР 304600, кл. G 06 G 7/34, 1970 (прототип) .

z

Ю

rri

n

-

4

rr

19