156703

Класс б 060; 420, 10 Юф 156703 СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ чс,"т.,1фг Подписная группа М 1 бб Г, Е. Пухов, Б, А. Борковский,В. В. Васильев, А, Е, Степанов и О. Н. ТокареваМОДЕЛИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯЗаявлено 18 сентября 1962 г. за ЛЪ 795137/26-24 з Комитет по делам изобретений и открытий при Совете Министров СССР Опубликовано в Бюллетене изобретений и товарнык знаков Ла 16 за 1963 г.(3) в двух вариантах. Известны моделирующие устройства для решения задач линейного программирования, содержащие обратимую модель линейных ограничений, обратимый сумматор и блок диодов.Предлагаемое моделирующее устройство аналогичного назначения отличается от известных тем, что для упрощения конструкции на входы обратимой модели ограничений включены регулируемые источники э.д,с.На фиг. 1 и 2 приводятся функциональные схемы вариантов выполнения описываемого устройства; на фиг. 3 - квазиобратимая модель системы линейных алгебраических уравнений; фиг. 4 относится к геометрической интерпретации примененного метода моделирования,Описываемое моделирующее устройство предназначено для решения общей невырожденной задачи линейного программирования оптимизации линейной формы (целевой функции)1 = С,Х, + С.,Ха+ + СХ (1) при линейных ограничениях вида:По первому варианту устройство состоит из следующих блоков (фиг. 1):обратимого линейного преобразователя параллельного действия, на котором моделируются линейные ограничения (2); обратимого сумматора ОС, реализующего линейную форму (1) и блока диодов 0, 0,0, предназначенного для обеспечения условий неотрицательности (3).Благодаря тому, что линейная форма (1) реализуется наравне с линейными ограничениями (2) с помощью обратимых элементов, ее значение можно не только получать, но и задавать, для чего в схеме фиг. 1 предусмотрен специальный источник с регулируемой э.д.с. Е,Это позволяет исключить необходимость подбора неизвестных с помощью того или иного алгоритма и получить решение более быстро,Для получения решения выполняются следующие операции: начальные значения неизвестных ХХи линейной формы р, удовлетворяющие лишь (2) и (3), получаются автоматически после установки коэффициентов а; с,. и Ь; при отключенном источнике э,д.с, Е (ключ К разомкнут, К 9 замкнут) за счет свойств квазианалоговой модели уравнений (1), (2), (3);полученное значение линейной формы р = р фиксируется при по- моши эд.с. Е, (ключ Кд замкнут, К разомкнут);значение и изменяется в требуемую сторону путем регулировки э.д.с. Е, до тех пор, пока и - т напряжений Х; на полюсах модели не обратятся в нуль.Поскольку задача предполагается невырожденной, ооращение в нуль и - т неизвестных является достаточным для получения оптимального решения.Таким образом, при построении модели по схеме фиг. 1 решение задачи может быть выполнено за два шага без привлечения симплекс- ного метода: на первом получается допустимое решение, удовлетворяющее лишь (2) и (3), но не обращающее (1) в минимум или максимум, а на втором делается переход от допустимого к оптимальному решению.Описанное вьппе целиком относится ко второму варианту моделирующего устройства для решения задач линейного программирования, схема которого приведена на фиг. 2.В схеме фиг. 2 в качестве основного решающего блока применена квазиобратимая модель системы линейных алгебраических уравнений, изображенная на фиг. 3, на которой моделируются линейная форма (1) и линейные ограничения (2). Для обеспечения условий неотрицательности усилители УУ Уохвачены цепями нелинейной обратной связи Оь В, , 1 Э. Значение линейной формы, как и в схеме фиг. 1, можно не только измерять (ключ К в положении 1), но и задавать от регулируемого источника Е (ключ К в положении 11).Достоинством схемы фиг. 2 является более высокий уровень машинных переменных.То, что в схемах фиг. 1 и 2 коэффициенты аи с, неотрицательны, не сужает класса решаемых задач, так как весьма просто осуществить переход от системы с произвольными знаками коэффициентов к эквивалентной системе уравнений только с положительными коэффициентами. Схемы фиг. 1 и 2 обладают абсолютной устой гивостью при произвольной матрице коэффициентов (2).Далее приводится геометрическая интерпретация рассмотренного двухшагового метода моделирования для частного случая, когдаи - тп =2.М 156703Выразим все переменные Х, через Х, и Х и перепишем линейную форму (1) и ограничивающие условия (2) и (3) в следующем виде:р = у,х, + у.х (4)Хд -- а, Х 1 + а., Х + Ц(й = 3, 4, и) (5)Х.)0(= 1, 2)г) (6)где у;, л 3 - некоторые постоянные.Прямые Х =0 в осях координат Хь Х (фиг. 4) ограничивают на плоскости многоугольник условий (5), (6). Область выполнения условий Х)0 отмечена направлением штриховки сторон многоугольника. Так, графически определяется область возможных пар чисел (Х Х), среди которых следует выбрать точки, обращающие форму (4) в минимум или максимум. Коэффициенты у 1 и у определяют направление семейства прямых аЬ и направление, в котором линейная форма р увеличивается,В двухшаговом методе моделирования в результате первого шага получается допустимое решение, удовлетворяющее (5) н (6), но не обращающее (4) в минимум или максимум. Прямая аЬ линейной формы пересекает при этом многоугольник условий, и модель выдает одну из точек, находящуюся на отрезке прямой аЬ внутри многоугольника,На втором шаге значение р изменяется в нужную сторону, что соответствует на фиг, 4 перемещению прямой аЬ параллельно самой себе. Такой параллельный перенос приведет прямую в данном случае либо в точку А, либо в точку С, в зависимости от того, что разыскивается, максимум или минимум линейной формы.Таким образом, описываемое моделирующее устройство имеет упрощенную конструкцию и позволяет исключить многошаговость при решении итерационными методами, чем обусловливается полезность его применения.Предмет изобретенияМоделирующее устройство для решения задач линейного программирования, содержащее обратимую модель линейных ограничений, обратимый сумматор и блок диодов, о т л и ч а ю щ е е с я тем, что, с целью упрощения конструкции, на входы обратимой модели линейны:; ограничений включены регулируемые источники э.д.с.