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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Ссиоз Советскнк

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. сеид-ву(22) Заявлено 22. 06. 81 (21) 3303551/18-24 (31) М. КЛ. с присоедикеиием заявки Й9G 06 G 7/122

Государственный комитет

СССР но делам нзобретеннй н открытнй (23) Приормтет—

Опубликовано 23,1282. бюллетень М 47

ИЗ} УДК681..333 (088.8) Дата опубликования описания 20. 01, 83 (72) Автор изобретенмя

Юс.

1 р Л.А.Симах ч

;1

Институт проблем моделирования в энергетике

АН Украинской ССР (71) Заявитель

I (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

MATENATH×EÑÊ0ÃÎ ПРОГРАММИРОВАН ИЯ

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

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

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

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

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

Поставленная цель достигается тем, что в устройство, содержащее две

8-сетки, входЫ которых являются входом устройства, введены блок пороговых элементов, блок формирователей импульсов, элемент ИЛИ, электроннолучевой индикатор, генератор тактовых импульсов, два интегратора, два триггера н блок управления, состоящий из двух .счетчиков, двух селекторов кодов, элемента ИЛИ.и двух формирователей импульсов, выходы которых подключены соответственно к первому и второму входам элемента ИЛИ, выход которого соединен с входом яркостной модуляции электроннолучевого индикатора, выход генератора тактовых импульсов подключен к. счетному входу первого счетчика, выход переполнения которого соединен с входом второго формирователя импульсов, с входом первого триггера и со счетным входом второго счетчика, выход переполнения которого соединен с входом первого формирователя импульсов и с входом.983717

P шечиэают Формирование системы симметричных напряжений треугольной формы, играющих роль переменных моделируемой задачи. Постоянные времени интеграторов 8 и 9 должны быть выбраны та-

0 ким образом, чтобы половина периода формирования треугольного напряжения соответствовала периоду импульсов на выходах счетчиков 15 и 16.

Ф(х,г) <о;

{ „) п)ах

1yFn (.2 ) второго триггера, выходы первого и второго триггеров соединены с входа- ми соответственно первого и второго интеграторов, выходы которых подключены к входам отклонения луча электроннолучевого индикатора и к информационным входам первой и второй

R-сеток, выходы. которых соединены соответственно с первыъ и вторым входа» ми блока пороговых элементов, группа выходов которого непосредственно и через блок формирователей импульсов подключена соответственно к первой .и второй группам, входов элемента ИЛИ, третий вход которого соединен с выхо дом элемента ИЛИ блока управления, . 15 группы информационных выходов первого и второго счетчиков подключены соответственно к группам входов первого и второго селекторов кодов, выходы которых соединены соответственно с 20 первым и вторым входами элементов ИЛИ блока управления.

На фиг.1 представлена блок-схема устройства для решения задач математического программирования; на фиг.2-25 диаграммы, поясняющие работу предлагаемого устройства.

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

R-сетки 1 и 2, блок 3 пороговых элеглентоэ, блок 4 формирователей импульсоэ, элемент ИЛИ 5, электроннолучевой индикатор 6, блок 7 управления, интеграторы 8 и 9, триггеры 10.и 11, блок

12, блок 7 управления .содержит форми- рователи 13 и 14 импульсов, счетчики

15 и 16, селекторы 17 и 18 кодов, элемент ИЛИ 19.

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

4 где ф — конечный оператору скалярная функция; х — вектор неизвестных; вектор известных величину и — целевая функция.

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

Блок 3 пороговых элементов содержит операционные усилители и аналоговые инэерторы. 8 качестве пороговых элементов и аналоговых инверторов бло-65 ка 3 использованы интегральные операционные усилители.

Блок 4 формирователей импульсов содержит формирователи коротких импульсов и построен на основе интегральных компараторов.

R-сетка 1 построена по схеме

aL-аналога линейных алгебраических уравнений.

Устройство работает следующим образом.

Блок 7 управления и последовательно,включенные триггер 10 и интегратор

8, и триггер 11 и интегратор 9 обеспечивают формирование сетки прямоугольной системы координат на экране электроннолучевого индикатора 6 и сканирование переменных решаемой задачи. Емкость счетчиков 15 и 16 должна соответствовать числу интервалов разбиения экрана индикатора по вертикали и горизонтали. Сигналы переполнения этих счетчиков выполняют две функции: запускают формирователи 13 и

14 импульсов, выходные сигналы которых играют роль синхронизирующих импульсов, и изменяют состояние счетных триггеров 10 и 11.

Информационные кодовые выходы этих же счетчиков после прохождения через селекторы 17 и 18 кодов и элемент ИЛИ 19 формируют изображение координатной сетки на экране электроннолучевого индикатора 6.

Последовательно включенные триггеры 10 и 11 и интеграторы 8 и 9 обесВыходные напряжения интеграторов

8 и 9 поступают на входы R-сетки 1 аналогов системы функций и R-сетки 2 аналога целевой Функции; а также подключены к входам вертикального и горизонтального отклонения индикатора 6.

При подаче на входы R-сетки 1 и

R-сетки 2, соответственно, аналога систем функций и аналога целевой функции, напряжений треугольной формы с выходов блока генераторов развертки, на их выходах формируются сигналы невязок в условиях (1) и. (2) . Эти сигналы после прохождения пороговых элементов блока 3 формируются э двоичные сигналы. Для опреде- ленности можно принять, что, когда невязки Е э условиях задачи (1) и (2), например, отрицательны, на выходах пороговых элементов будут нулевые уровни сигналов, а когда невязки положительны — на выходах порого-.

983717 эых элементов будут единичные уровни сигналов. Обращение невязки в нуль будет соответствовать фронту измене-. ния сигнала на выходе порогового элемента.

Так как сигналы развертки электроннолучевого индикатора б и входных переменных аналогов системы- функций и аналога целевой функции синхронизированы между собой с помощью сигналов блока 7 управления, выходные 1(» сигналы блока 3 пороговых элементов после прохождения через элемент ИЛИ

5„ подсвечивают области определения неравенств условий (1). !

Блок 4 формирователей импульсов формирует короткие импульсы из перепадов выходных сигналов тех пороговых элементов блока 3 пороговых элементов, которые соответствуют уравнениям » и границам неравенств условий (1) и (2); изображения которых необходимо вывести на экране. Продолжительность импульсов этих формирователей опре деляет толщину линий на экране элек троннолучевого индикатора б.

Поскольку входные сигналы элемента ИЛИ 5 являются двоичными цифровьвж сигналами потенциального и импульсного вида, этот блок кроме функции смешивания сигналов может включать в се- » бя функции их логической обработки при решении. разнообразных задач по отображению пересечения или объединения областей, образуемых отдельными группами функций условий задачи (1) и (2).

Работу Предлагаемого устройства рассмотрим на иллюстративном примере моделирований и отображения задачи линейного программирования. 49 х1) 0 х >О х„<8 (3) хна 7 х1+х2 104 0 45 и.=5х1+х2 -ь пах. (4)

На выходах матрицы 1 формируются точки в соответствии с выражениями, 1 х1 56

Е2 =х2

Е =х -8

Э

Е+=х -7 (5)

Е5 х +х2-10

Еь=5х„+х2-) . $S

Эти выражения соответствуют условиям моделируемой задачи (3) и (4), записанным в форме с невязками

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

Рассмотрим работу одного из таких элементов, на входе которого действует ток Я . При изменении величины х в отрйцательной области ток 8 также отрицателен.

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

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

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

Аналоговые инверторы, включенные на выходах этих пороговых элементов, необходимы для согласования полярности и уровня сигналов блока 4 формирователей импульсов, элементы которого срабатывают при перепадах определенной полярности.

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

Выходные сигналы блока 3 пороговых элементов и блока 4 формирователей импульсов смешиваются в элементе

ИЛИ 5. Некоторые из сигналов этих блоков могут не использоваться, если этого не требуют условия (3) и (4).

В данном случае сигналы шестого порогового элемента, а также первого и второго формирователя импульсов в смеситель импульсов не поступают.

Выходные сигналы блока 4 формирователей импульсов поступают на инверсные входы элемента ИЛИ 5.

На фиг.2 показана область ограничений моделируемой задачи и изобра983717 в, жение целевой функции для нескольких фиксированных ее значений. Точка М соответствует решению задачи линейного программирования для случая макснмилизации целевой функции.

Такой же вид имеет изображение на экране электроннолучевого индикатора.

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

Формула изобретения

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

ИЛИ, электроннолучевой индикатор, генератор тактовых импульсов, два интегратора, два триггера и блок управления, состоящий из двух счетчиков, двух селекторов кодов, элемента ИЛЙ и двух Формирователей импульсов, выходы которых подключены соответственно к первому и второму входам элемента HJIH, выход которого соединен с входом яркостной модуляции электроннолучевого индикатора, выход генератора тактовых импульсов подключен к счетному входу первого счетчика,. выход переполнения которого соединен с входом второго формирователя-импульсов, с входом первого триггера и со счетным входом второго счетчика, вы» ход переполнения которого соедийен с входом первого формирователя импульсов и с входом второго триггера, вы10 ходы первого и второго триггеров соединены с входами соответственно первого и второго интеграторов, выходы которых подключены к входам отклонения луча электроннолучевого ин35 -дикатора и к информационным входам первой и второй R-сеток, выходы которых соединены соответственно с первым и вторым входами блока пороговых элементов, группа выходов которого непосредственно и через блок формирователей импульсов подключена соответственно к первой и второй группам входов элемента ИЛИ, третий вход которого соединен с выходом элемента ИЛИ блока управления, группы информационных выходов первого и второго счетчиков подключены соответственно к группам. входов первого и второго селекторов кодов, выходы которых соединены соответственно с первым и вторым входами элементов ИЛИ блока управ» ления.

Источники информации, принятые во внимание при экспертизе

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

9 282761, кл, С 06 G 7/34, 1969, 2 ° Авторское свидетельство СССР

Р 304600, кл. G 06 С 7/34, 1970 (прототип).

983717

Составитель B.Ðûáèí

Редактор A.Øèøêèíà Техред Ж.Кастелевич

Корректор О. Билак филиал ППП "Патент", г.ужгород, ул.Проектная, 4

Заказ 9927/59 Тираж 731 Подписное

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

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