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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Сеез СоветскнкСоциалистическикРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(61) Дополнительное к авт. сеид-ву(22) Заявлено 22,06,81(21) 3303551/18-24 31) М.КЛ. с присоедикеиием заявки Й 90 06 6 7/122 Государственный комитет СССР но делам нзобретеннй н открытнйДата опубликования описания 20.01,83(72) АвторизобретенмяЛ.А.Симах ч Институт проблем моделирования в энергетике АН Украинской ССР(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧМАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАН ИЯ Изобретение относится к вычислительной технике, и может быть использовано при исследовании задач математического программирования, а такжев качестве технического средства обу-.чения при изучении задач математического анализа и нелинейного програм.мирования.Известно устройство для решениязадач математического программирования, содержащее аналоги систем функций, аналоги систем неравенства ианалог целевой функции 1 3. Наиболее близким по технической сущности к изобретению является.устройство для решения задач математического программирования, содержащее блоки-аналоги систем функций, блок- аналог целевой функции, аналог систем неравенств, преобразователь неравенств в уравнения, Формирователь штрафной функции, реэнстор и переключатель 2 3,Недостатками известных устройств являются низкое быстродействие и то, что они не позволяют Формировать сигналы, необходиьие для отображения ограничений решаемой задачи на электроннолучевом индикаторе. ЗО Цель изобретения - повышение быстродействия и расширение функцио-, нальных возможностей эа счет отображения ограничений решаемой задачи на индикатореПоставленная цель достигается тем, что в устройство, содержащее две й-сетки, входы которыхявляются входом устройства, введены блок пороговых элементов, блок формирователей импульсов, элемент ИЛИ, электроннолучевой индикатор, генератор тактовых импульсов, два интегратора, два триггера н блок управления, состоящий из двух .счетчиков, двух селекторов кодов, элемента ИЛИ,и двух Формирователей импульсов, выходы которых подключены соответственно к первому и второму входам элемента ИЛИ, выход которого соединен с входом яркостной модуляции электроннолучевого индикатора, выход генератора тактовых импульсов подключен к счетному входу первого счетчика, выход переполнения которого соединен с входом второго формирователя импульсов, с входом первого триггера и со счетным входом второго счетчика, выход переполнения которого соединен с входом первого Формирователя импульсов и с входомЯ шечивают Формирование системы симметричных напряжений треугольной Формы, играющих роль переменных моделируемой задачи. Постоянные времени интеграторов 8 и 9 должны быть выбраны та ким образом, чтобы половина периодаформирования треугольного напряжения соответствовала периоду импульсов на выходах счетчиков 15 и 16. Ф(х, Г) Ор(2) второго триггера, выходы первого и второго триггеров соединены с входа- ми соответственно первого и второго интеграторов, выходы которых подключены к входам отклонения луча электроннолучевого индикатора и к информационным входам первой и второй В-сеток, выходы. которых соединены соответственно с первыъ.и вторым входами блока пороговых элементов, группа выходов которого непосредственно и Ю через блок формирователей импульсов подключена соответственно к первой и второй группам. входов элемента ИЛИ, третий вход которого соединен с выходом элемента ИЛИ блока управления, . 15 группы информационных выходов первого и второго счетчиков подключены соответственно к группам входов первого и второго селекторов кодов, выходы которых соединены соответственно с 20 первым и вторым входами элементов ИЛИ блока управления.На фиг.1 представлена блок-схема устройства для решения задач математического программирования; на Фиг.2-25 диаграммы, поясняющие работу предлагаемого устройства.Устройство для решения задач математического программирования содержит й-сетки 1 и 2, блок 3 пороговых элементов, блок 4 Формирователей импульсов, элемент ИЛИ 5, электроннолучевой индикатор 6, блок 7 управления, интеграторы 8 и 9, триггеры 10.и 11, блок 12, блок 7 управления .содержит формирователи 13 и 14 импульсов, счетчики 15 и 16, селекторы 17 и 18 кодов, элемент ИЛИ 19.Уттройство предназначено для решения задач нелинейного программирования4 4где ф - конечный оператор;скалярная Функция;х - вектор неизвестных;Г - вектор известных величин;- целевая функция.Соответственно, ввиду этой решае-,мой задачи матрица 1 резисторов-ана-,лог систем функций и матрица 2 резисторов - аналог целевой функции представляют собой нелинейные Функциональные многополюсники, содержащиенелинейные резисторы, Функциональныепреобразователи одной и нескольких .независимых переменных, структура ипараметры которых должны быть выбраны в соответствии с условиями (1) 6 Ои (2),Блок 3 пороговых элементов содержит операционные усилители и аналоговые инверторы. В качестве пороговыхэлементов и аналоговых инверторов бло 65 ка 3 использованы интегральные операционные усилители,Блок 4 формирователей импульсовсодержит Формирователи коротких импульсов и построен на основе интегральных компараторов.к-сетка 1 построена по схемес 6-аналога линейных алгебраическихуравнений.Устройство работает следующим образом,Блок 7 управления и последовательно,включенные триггер 10 и интегратор8, и триггер 11 и интегратор 9 обеспечивают формирование сетки прямоугольной системы координат на экранеэлектроннолучевого индикатора 6 исканирование переменных решаемой задачи. Емкость счетчиков 15 и 16 должна соответствовать числу интерваловразбиения экрана индикатора по вертикали и горизонтали. Сигналы переполнения этих счетчиков выполняют двефункции; запускают формирователи 13 и14 импульсов, выходные сигналы которых играют роль синхронизирующих импульсов, и изменяют состояние счетных триггеров 10 и 11.ИнФормационные кодовые выходыэтих же счетчиков после прохождениячерез селекторы 17 и 18 кодов и элемент ИЛИ 19 формируют изображениекоординатной сетки на экране электроннолучевого индикатора 6.Последовательно включенные триггеры 10 и 11 и интеграторы 8 и 9 обесВыходные напряжения интеграторов 8 и 9 поступают на входы й-сетки 1 аналогов системы функций и й-сетки 2 аналога целевой Функции; а также подключены к входам вертикального и горизонтального отклонения индикатора 6.При подаче на входы К-сетки 1 и К-сетки 2, соответственно, аналога систем функций и аналога целевой функции, напряжений треугольной формы с выходов блока генераторов развертки, на их выходах Формируютсясигналы невязок 6 в условиях (1) и.(2). Эти сигналы после прохожденияпороговых элементов блока 3 Формируются в двоичные сигналы. Для опреде-,ленности можно принять, что, когданевязки Е в условиях задачи (1) и(2), например, отрицательны, на выходах пороговых элементов будут нулевые уровни сигналов, а когда невязки положительны - на выходах порого-.эых элементов будут единичные уровни сигналов. Обращение невязки в нуль будет соответствовать Фронту измене-. ния сигнала на выходе порогового элемента.Так как сигналы развертки электроннолучевого индикатора б и входных переменных аналогов системы- функций и аналога целевой функции синхронизированы между собой с помощью сиг- налов блока 7 управления, выходные 10 сигналы блока 3 пороговых элементов после прохождения через элемент ИЛИ , подсвечивают области определения неравенств условий (1),5Блок 4 Формирователей импульсов формирует короткие импульсы из перепадов выходных сигналов тех пороговых элементов блока 3 пороговых элементов, которые соответствуют уравнениям 0 и границам неравенств условий (1) и (2); изображения которых необходимо вывести на экране. Продолжительность импульсов этих формирователей опре- деляет толщину линий на экране электроннолучевого индикатора б.Поскольку входные сигналы элемента ИЛИ 5 являются двоичными цифровьвюи сигналами потенциального и импульсного вида, этот блок кроме функции смешивания сигналов может включать в се- ф бя Функции их логической обработки при решении. разнообразных задач по отображению пересечения или объединения областей, образуемых отдельными группами функций условий задачи З 5 (1) и (2).Работу Предлагаемого устройства рассмотрим на иллюстративном примере моделирований и отображения задачи линейного программирования. 49 х 0 х О х 8 (3) х а 7х, +х4 0 45 и,=5 х 1+х 2 -ь аах, (4)На выходах матрицы 1 Формируются точки в соответствии с выражениями, а 1 =к 56 Е =х Е =х -8Э ф Е =х -7 (5) Е =х+хЕь=5 х+х-ф 55 Эти выражения соответствуют условиям моделируемой задачи (3) и (4), записанным в форме с невязкамиПоскольку .напряжения х и х, изменяясь во времени, пробегают область изменения выражений (5), токи 6 также являются Функциями времени. Изменяющиеся токи С поступают на входы,пороговых элементов блока 3 пороговых элементов, т.е. на операционные уси лители, в обратной, связи которыхвключены стабилитроны,Рассмотрим работу одного из такихэлементов, на входе которого действует ток Я . При изменении величиных в отрйцательной области ток Е,также отрицателен.На выходе операционного усилителяпоявляется положительное напряжение,которое смещает стабилитрон, включенный в обратную связь, в прямом направлении. На выходе этого операцион"ного усилителя положительное напряжение, близкое к нулю (диод стабилитрона открыт, его сопротивление майо). При изменении х в положитель 1 ной области, ток Е также положительный, напряжение на выходе операционного усилителя отрицательное иравно напряжению стабилизации стабилитрона, который смещен в обратномнаправлении.Таким образом, на выходе операционного усилителя нулевое напряжениетогда, когда нарушается первое изнеравенств условий (3), и отрицательное напряжение - когда это неравенство выполняется, граница между областями выполнения и нарушения неравенствасоответствует перепаду выходного на пряжения операционного усилителя.Остальные пороговые элементы работают аналогичным образом. Полярностьвключения стабилитронов в обратнуюсвязь операционных усилителей должнасоответствовать знаку реализуемогонеравенства. Поэтому для пороговыхэлементов отображающих третье, четвертое и пятое неравенства из условий(3), стабилитроны включены обратнойполярностью но отношению к описанному. Аналоговые инверторы, включенные на выходах этих пороговых элементов, необходимы для согласования полярности и уровня сигналов блока 4 формирователей импульсов, элементы которого срабатывают при перепадах определенной полярности.Блок 4 Формирователей импульсов формирует короткие импульсы, соответствующие моментам прохождения компо нент вектора через ноль.Выходные сигналы блока 3 пороговых элементов и блока 4 формирователей импульсов смешиваются в элементе ИЛИ 5. Некоторые из сигналов этих блоков могут не использоваться, если этого не требуют условия (3) и (4). В данном случае сигналы шестого порогового элемента, а также первого и второго формирователя импульсов в смеситель импульсов не поступают,Выходные сигналы блока 4 Формирователей импульсов поступают на инверсные входы элемента ИЛИ 5.На фиг.2 показана область ограничений моделируемой задачи и изобра 983717 в, жение целевой функции для нескольких фиксированных ее значений. Точка М соответствует решению задачи линейного программирования для случая макснмилизации целевой функции.Такой же вид имеет изображение на экране электроннолучевого индикатора,Технико-экономический эффект применения устройства будет состоять в повышении быстродействия и в расширении функциональных возможностей существующих. аналоговых и гибридных моделирующих систем путем обеспечения отображений условий задач на экране электроннолучевого индикатора, что позволит использовать его также в качестве технического средства обучения.1Формула изобретенияУстройство для решения задач математического программированиясодержащее две й-сетки, входы оторых являются входом устройства, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены блок пороговых элементов блок формирователей импульсов, элемент ИЛИ, электроннолучевой индикатор, генератор тактовых импульсов, два интегратора, два триггера и блок управления, состоящий из двух счетчиков, двух селекторов кодов, элемента ИЛЙ и двух формирователей импульсов, выходы которых подключены соответственно к первому и второму входам элемента ИЛИ, выход которого соединен с входом яркостной модуляции электроннолучевого индикатора, выход генерато.ра тактовых импульсов подключен ксчетному входу первого счетчика,. выход переполнения которого соединен свходом второго формирователя импуль 5 сов, с входом первого триггера и сосчетным входом второго счетчика, вы"ход переполнения которого соедийен свходом первого формирователя импульсов и с входом второго триггера, вы 10 ходы первого и второго триггеровсоединены с входами соответственнопервого и второго интеграторов, выходы которых подключены к входам отклонения луча электроннолучевого ин 5:дикатора и к информационным входампервой и второй й-сеток, выходы которых соединены соответственно с первыми вторым входами блока пороговых элементов, группа выходов которого непосредственно и через блок формирователей импульсов подключена соответственно к первой и второй группам входов элемента ИЛИ, третий вход которого соединен с выходом элемента ИЛИблока управления, группы информационных выходов первого и второго счетчиков подключены соответственно к группам. входов первого и второго селекторов кодов, выходы которых соединены соответственно с первым и вторымвходами элементов ИЛИ блока управления,Источники информации,принятые во внимание при экспертизе1, АвторскОе свидетельство СССР9 282761, кл, С 06 С 7/34, 1969,2Авторское свидетельство СССРР 304600, кл, С 06 С 7734, 1970 (прототип)..Шишкина Техред Ж.Кастелевич КорректорО,Вила едакт лиал ППП "Патент", г.ужгород, ул.Проектная Заказ 9927/59 Тираж 731 ВБИИПИ Государственного ко по делам изобретений и 113035, Москва, Ж, Раушмит тк ка Подписноеа СССРтийнаб., д,4/