156357

, Е, Пух ЮЩЕЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАИНЕЙНОГО ПРОГРАММИРОВАНИЯ МОДЕ декабря 1961тений и отк Заявлено 1 в Комитет по делам изоб Опубликовано в Бюллетенезобретений Известны моделирующие устроист программирования, содержащие блок нпчепий, сумматор для вьчисления ли11 редлагаемое моделирующее устр о 1 личается от известных тем, что для ших усилителей, увеличения устойчиво пения влияния неидеальности характер ния задач в нем в качестве блока моде применен обратимый линейный преобр ство, выполненное в виде системы ре ключевой схемы, служащее для реали присоединенное параллельно к полюс разователя, к диодам и ко входам суммНа фиг. 1 показана функциональ ства; на фиг. 2 - схема обратимого лЗадача описываемого моделирующ делению минимакса (т, е. минимума одится к опрелинейной форь(2 е. х при следующих условиях:искомые переменные х,. должх, ) О; ЗО БРЕТ ЕНИЯСВИДЕТЕЛЬСТВУ г. за755152(26-24тий при Совете Министров СССРтоварных знаков15 за 1963 г ва для решения задач линейного моделирования линейных огранейной формы и диоды.ойство аналогичного назначения уменьшения числа отрабатываюсти работы устройства и устраистик диодов на точность решепирования линейных ограничений азователь и логическое устройгулируемых источников э.д.с. и зации симплексного метода и ам обратимого линейного преобатора.ная схема описываемого устройинейного преобразователя.его устройства свили максимума)и должны удовлетворять линейной системе уравненийах,+а, х.,+ + а,х+Ь,=Оатгхг + атх ++ атп"и+ гт 0 (3) где т - число уравнений; гг - число неизвестных; агг Ь сг,. - известные вещественные числа, которые могут быть положительными, отрицательными или равными нулю (некоторые из них)(г = 1,2, гг, г = 1,2 иг),При решении сформулированной задачи, представляющей собой общую задачу линейного программирования, могут встретиться три случая: система условий противоречива, так как неопределенная система линейных уравнений (3) не имеет неотрицательных решений; система (3) имеет пеотрицателы ые решения, минимакс линейной формы (1) равен + сс или - э.-.; значение минимакса линейной формы (1) на множество неотрицательных решений конечно.На практике обычно имеет место последний случай. Описываемое моделирующее устройство содеркит примененный в качестве блока моде;шрования линейных ограничений (3) обратимый линейный преобразователь ОЛП параллельного или последовательного действия, позволяющий получать т известных х,; грн задании и - т любых других, диоды 0 - 0, служащие для реализации условий (2); регулируемые источники э.д.с. ег - , е моделирующие соответствующие нсизвсстные выражения (1) и (3); сумматор Х, собранный из необратимых операциониых усилителей и служащий для получения значения линейной формы (1): ключи Кг - К. В описываемом устройстве как более быстродействующий применен ОЛП параллельного действия (фиг. 2), образованный параллельно соединенным обратимыми операционными отрабатывающими усилителями У каждый из которых служит для моделирования одного из уравнений (3). Коэффициенты а,. моделируРгются отношением сопротивлений а =, а постоянные члены/ )-)Ь; - ;б постоянными напряжениями. Схема ОЛП (фиг. 2) изображена в предполокении, что все а; ) О, Однако это не является ограничением, поскольку при наличии отрицательных коэффициентов а система (3) всегда может быть заменена эквивалентной с неотрицательными коэффициентами путем введения дополнительных неизвестных. Описываемое моделирующее устройство позволяет реализовать получение искомых неизвестных х хпри помощи симплексного метода, достоинством которого является неизбежная сходимость к точному рецюнию, если значение минимакса линейной формы (1), на множестве неотрицательных решений (3) при условиях (2) конечно.Для получения решения задачи на модели требуются следующие операции.1. Находят начальное решение хР, х 0 х 0 (верхний индекс означает номер шага), соответствующее системе уравнений (3) и условиям (2). Это решение выдается обратным линейным преобразователем ОЛП при включенных диодах 0 ь 0 и отключенных ключах К, К,11. Устанавливают любые и - т э.д.с., например,е,+г, е ,егак, чтобыоие" =х ,.г, е =хи замыкают ключиК,+г, ,К.э. д. с.,фиксирующие какие-либо напряжения,в нашем случаех,и+Ех) называгот далее определяющими, а полюсы, к которым не присоединены э. д. с., - свободными.111. Отключают диоды Р, Ра (не обязательно).17. Любую из определяющих э. д. с. е,+р, где 14 р(гг - ггг,увеличивают или уменьшают так, чтобы напряжение 1 изменялось в требуемом направлении.Зависимости напряжений )е и х ца свободных полюсах от э.д.с. е,+, . ОЕевидеЕО, линейные, причеми=ог е,+,-гх;: х -е е,где: )1, хг, г, г - некоторые постоянные.Могут встретиться три основных случая,Случай 1-й. Э. д.с. е,. равна нулю, причем ее увеличение не ведет к желаемому изменению )1,Случай 2-Й. Уменьшение э.д.с. е,+р приводит и тому, что она обращается в чуль, а напряжения ца всех свободных полюсах остаются положительными.Случаи 3-й. Увеличение или уменьшение э.д.с. е;-р приводит к обрагцению в нуль напряжения на одном из свободных полюсов, причем остальные напрягкения остаются неотрицательными.Ъ. Дальнейший порядок решения зависит от того, какой из указанных случаев имеет место. В случае 1-м нужно переходить к регулированию одной из полученных ранее определяющих э. д. с., например э. д.с. е ,+р+ц,где О - положительное илп отрицательное целое число, удов;,етворяю шее условию1: рдгг - ггг.В случае 2-м уменьшают э.д.с. е,.р до нуля и переходят к ре- ГУЛИРОВЗЕ 1 ИЕО Э Д С Е п - , р.Е,г ТаК, ЧТООЫ 1 ЗМЕЦЯЛОСЬ В НУЖН 1 1 О СТОРОНВ случае 3-м регулирование е, прекращают в момент, когда напряжение на одном из свободных полюсов обращается в нуль, затем замыкают ключ КЕ, соответствующий этому полюсу, и, наконец, РеЗмыкзют ключ 1(, р, иРи помощи котоРого РегУЛНРУемаЯ э. д. с. е, р Оыла пРисоединена к цепи. После РазмыкаеЕНЯ этого ключа Э. д. С. Е а - р уСТаНВВЛИВВЕТСя ца НУЛЬ. УКазацНОЕ ПЕрЕК,ЕОЧЕНИЕ КЛЕО- чс Ие приведет к изменению напрягкеииШ на полюсах преобразователя Сдо.1 Осле окончания операций, соответствующих 3-му случаю (осцовном 1), получается положение, отличающееся от положения, которое име,ю место после выполнения операции 3 только тем, что вместо клю- ЧЕЕ Ко+1 Клг - 2, , . Ка ОназаЛИСЬ 31 МИНУТЕМИ ДРУГИЕ П - гн КЛЕС- чей и определяющими стали другие э. д. с.Дальнейшее решение сводится к повторению четвертой и пятой оперееций до тех пор, пока никакое регулирование определяющих э.д.с. не будет приводить к изменению и в требуемом направлении.Если решаемая задача имеет единственное решение, то разобранный процесс будет Выполнен за конечное число шагов, как это следует из теории симплексного метода.Таким образом, описываемое моделирующее устройство позволяет уменьшить число отрабатывающих усилителей, увеличить устойчивость работы и устранигь влияние неидеальности характеристик диодов на точность решения задач, чем обусловливается полезность применения устройства.Предмет изобретенияМоделирующее устройство для решения задач линейного программирования, содержащее блок моделирования линейных ограничений, сумматор для вычисления линейной формы и диоды, отличающееся тем, что, с целью уменьшения числа отрабатывающих усилителей, увеличения устойчивости работы устройства и устранения влияния не- идеальности характеристик диодов на точность решения задач, в нем в качестве блока моделирования линейных ограничений применен обратимый линейный преобразователь и логическое устройство, выполненное в виде системы регулируемых источников э,д.с. и ключевой схемы, служащее для реализации симплексного метода и присоединенное параллельно к полюсам обратимого линейного преобразователя, к диодам и ко входам сумматора.