Патент ссср 156703

Класс G 060; 426, 10

М 156703

СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВх

Подписная группа М 1бб

Г. Е. Пухов, Б. А. Борковский, В. В. Васильев, А. Е. Степанов и О. Н. Токарева

МОДЕЛИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Заявлено 18 сентября 1962 г. за ¹ 795137/26-24 в Комитет по делам изобретений и открытий при Совете Министров СССР

Опубликовано в «Бюллетене изобретений и товарнык знаков» ¹ 16 за 1963 г. а, Х + а,яХа + ... + а,„Х„= bi а,Х, + а аХ + ... + а.,„Х„= b., (2) а,Хт+ а Ха+... + а„,„Х„=Ь„

Х) 0(/=1,2,..., n) (3) в двух вариантах.

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

Предлагаемое моделирующее устройство аналогичного назначения отличается от известных тем, что для упрощения конструкции íà Входы обратимой модели ограничений включены регулируемые источники э.д.с.

На фиг. 1 и 2 приводятся функциональные схемы вариантов выполнения описываемого устройства; на фиг. 3 — квазиобратимая модель системы линейных алгебраических уравнений; фиг. 4 относится к геометрической интерпретации примененного метода моделирования.

Описываемое моделирующее устройство предназначено для решения общей невырожденной задачи линейного программирования оптимизации линейной формы (целевой функции)

1 = С,Х, + Саха+... +- С„Х„ (1) при линейных ограничениях вида: № 156703

По первому варианту устройство состоит из следующих блоков (фиг. 1): обратимого линейного преобразователя параллельного действия, на котором моделируются линейные ограничения (2); обратимого сумматора ОС, реализующего линейную форму (1) и блока диодов

DI, D, D„, предназначенного для обеспечения условий неотрицательности (3) .

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

Для получения решения выполняются следующие операции: начальные значения неизвестных Х,< >, ... Х и линейной формы ф >, удовлетворяющие лишь (2) и (3), получаются автоматически после установки коэффициентов а;,, с,. и b; при отключенном источнике э.д.с. Е (ключ К разомкнут, К замкнут) за счет свойств квазианалоговой модели уравнений (1), (2), (3); полученное значение линейной формы p = р,ф фиксируется при помоши э.д.с. Е (ключ К замкнут, К разомкнут); значение и изменяется в требуемую сторону путем регулировки э.д.с. Е . до тех пор, пока и — т напряжений Х; на полюсах модели не обратятся в нуль.

Поскольку задача предполагается невырожденной, ооращение в нуль n — m неизвестных является достаточным для получения оптимального решения.

Таким образом, при построении модели по схеме фиг. 1 решение задачи может быть выполнено за два шага без привлечения симплексного метода: на первом получается допустимое решение, удовлетворяющее лишь (2) и (3), но не обращающее (1) в минимум или максимум, а на втором делается переход от допустимого к оптимальному решению.

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

В схеме фиг. 2 в качестве основного решающего блока применена квазиобратимая модель системы линейных алгебраических уравнений, изображенная на фиг. 3, на которой моделируются линейная форма (1) и линейные ограничения (2). Для обеспечения условий неотрицательности усилители У,,У,..., У„охвачены цепями нелинейной обратной связи D, D, ..., D„. Значение линейной формы, как и в схеме фиг. 1, можно не только измерять (ключ К в положении 1), но и задавать от регулируемого источника Е., (ключ К в положении П).

Достоинством схемы фиг. 2 является более высокий уровень машинных переменных.

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

Далее приводится геометрическая интерпретация рассмотренного двухшагового метода моделирования для частного случая, когда и — m=2.

¹ 156703

Выразим все переменные Х, через Х, и Х> и перепишем линейную форму (1) и ограничивающие условия (2) и (3) в следующем виде:

p = у1х1 + у х (4)

Хд —— u»Х1+ а Х + Ц(юг=3, 4, ...и) (5)

Х.) 0 (i = 1, 2,... n) (6)

l где у,, .. — некоторые постоянные.

Прямые Х =0 в осях координат Хь Х> (фиг. 4) ограничивают на плоскости многоугольник условий (5), (6). Область выполнения условий Х ) 0 отмечена направлением штриховки сторон многоугольника

Так, графически определяется область возможных пар чисел (Х,, Х.), среди которых следует выбрать точки, обращающие форму (4) в минимум или максимум. Коэффициенты у1 и у. определяют направление семейства прямых ab и направление, в котором линейная форма и увеличивается.

В двухшаговом методе моделирования в результате первого шага получается допустимое решение, удовлетворяющее (5) н (6), но не обращающее (4) в минимум или максимум. Прямая а b линейной формы пересекает при этом многоугольник условий, и модель выдает одну из точек, находящуюся на отрезке прямой а о внутри многоугольника.

На втором шаге значение р ииззммеенняяееттсся я в в ннуужжннуую ю ссттоо1р ооннуу, что соответствует на фиг. 4 перемещению прямой ab параллельно самой себе.

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

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

Предмет изобретения

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

¹ 156703 Лги Ю

f 1

I п

Г

i Ъ (риг хг

Составитель А. Хохлов

Редактор Е. В. Семанова Техред А. А. Камышникова Корректор М. И. Эльмус

Типография, пр. Сапунова, 2.

Подп. к печ. 10/IX — 63 г. Формат бум. 70>6108

Зак. 2111/8 Тираж 1050 Цена 4 коп.

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

Москва, Центр, пр Серова, д. 4.