Патент ссср 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.