Патент ссср 156357
Иллюстрации
Реферат
№ 156357
Еласс G 06f; 42m, 36
СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
11одпасная гругг гга Л5 174
Г. Е. Пухов
МОДЕЛИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Заявлено 13 декабря 1961 г. за ЛЪ 755152/26-24 в Комитет по делам изобретений и открытий при Совете Министров СССР
Опубликовано в «Бюллетене изобретений и товарных знаков» Лге 15 за 1963 г.
1 = С,х, + Саха + ... + С„х„ при следующих условиях: искомые переменные х,. должны быть не отрицательными, т. е. х,) 0; х,) 0; ...х„) 0 (2) Известны моделирующие устройства для решения задач линейного программирования, содержащие блок моделирования линейных ограничений, сумматор для вычисления линейной формы и диоды.
Предлагаемое моделирующее устройство аналогичного назначения
01личается от известных тем, что для уменьшения числа отрабатывающих усилителей, увеличения устойчивости работы устройства и устранения влияния неидеальности характеристик диодов на точность решения задач в нем в качестве блока моделирования линейных ограничений применен обратимый линейный преобразователь и логическое устройство, выполненное в виде системы регулируемых источников э. д. с. и ключевой схемы, служащее для реализации симплексного метода и присоединенное параллельно к полюсам обратимого линейного преобразователя, к диодам и ко входам сумматора.
На фиг. 1 показана функциональная схема описываемого устройства; на фиг. 2 — схема обратимого линейного преобразователя.
Задача описываемого моделирующего устройства сводится к определению минимакса (т. е. минимума или максимума) линейной формы и должны удовлетворять линейной системе уравнений а„х,+а, х. +... +а,„х„+Ь,=О а,х, + а .,х,, +... + а „х„+ b =0 (3) где т — число уравнений; n — число неизвестных; а,, b,, с,,— известные вещественные числа, которые могут быть положительными, отрицательными или равными нулю (некоторые из них) (i = 1,2, ...и,/=1,2, ... т).
При решении сформулированной задачи, представляющей собой общую задачу линейного программирования, могут встретиться три случая: система условий противоречива, так как неопределенная система линейных уравнений (3) не имеет неотрицательных решений; система (3) имеет пеотрицателы ые решения, минимакс линейной формы (1) равеп + cc или — -; значение минимакса линейной формы (1) на множество неотрицательных решений конечно.
На практике обычно имеет место последний случай. Описываемое моделирующее устройство содер>кит примененный в качестве блока моде;шрования линейных ограничений (3) обратимый линейный преобразователь ОЛП параллельного или последовательного действия, позволяющий получать m известных х,.; грн задании n — т любых других, диоды 13> — D„, служащие для реализации условий (2); регулируемые источники э. д. с. e> — . е,, моделирующие соответствующие нсизвсстные выражения (1) и (3); сумматор —., собранный из необратимых о перациоцпых усилителей и служащий для получения значения линейной формы (1): ключи I(, — К„. В описываемом устройстве как более бb> стродействующий применен ОЛП параллельного действия (фиг. 2), образованный параллельно соединенным обратимыми операционными отрабатывающими усилителями У „„каждый из которых служит для моделирования одного из уравнений (3). Коэффициенты а;. моделируР к тся отношением сопротивлений а .=, а постоянные члены
// ) Я
b,—:b постоянными напряжениями. Схема ОЛП (фиг. 2) изобраксна в предполо>кении, что все а; ) О. Однако это не является ограничением, поскольку при наличии отрицательных коэффициентов а,-, система (3) всегда может быть заменена эквивалентной с неотрицательными коэффициентами путем введения дополнительных неизвестных.
Описываемое моделирующее устройство позволяет реализовать получение искомых неизвестных х,... х„при помощи симплексного метода, достоинством которого является неизбежная сходимость к точному рецюнию, если значение минимакса линейной формы (1), на множестве неотрицательных решений (3) при условиях (2) конечно.
Для получения решения задачи на модели требуются следующие операции.
I. Находят начальное решение х,0, хФ,..., х 0„ (верхний индекс означает номер шага), соответствующее системе уравнений (3) и условиям (2). Это решение выдается обратным линейным преобразователем
ОЛП при включенных диодах 0ь... D „и отключенных ключах к,,,к„.
II. Устанавливают любые и — т э.д.с., например, е„,+, е„,+, ...,е„ гак, чтобы о э е"„, — х„,, ...е„=х„ и замыкают ключи
К„,, ...,К„.
X 156357 э. д. с.,фиксирующие какие-либо напряжения(в нашем случаех +1,...x=„) назывгпот далее определяющими, а полюсы, к которым не присоединены э. д. с., — свободными.
III. Отключают диоды D,,..., D» (Ele обязательно).
IV. Любую из определяющих э. д. с. e„,+„, где14рСп — т,увеличивают или уменьшают так, чтобы напряжение !! изменялось в требуемом направлении.
Зависимости напряжений LL и х! На свободных полюсах от э.д.с. е„,+, . очевид!!о, линейные, причем и = 1 1,е»,+„ ! 1
X- XI -1- l Е,» где: р, х1, l0, 11 — некоторые постоянные.
Могут встретиться три основных случая.
Случай 1-й. Э. д. с. e»,+p равна нулю, причем ее увеличение не ведет к желаемому изменению )!.
Случай 2-й. Уменьшение э. д. с. е»+р приводит и тому, что она обращается в чуль, а напряжения на всеx свободных полюсах остаются положительными.
Случаи 3-й. Увеличение или уменьшение э.д.с. е»;- приводит к обра1цению в нуль напряжения на одном из свободных полюсов, причем остальные напряжения остаются неотрицательными.
V. Дальнейший порядок решения зависит от того, какой из указанных случаев имеет место. В случае 1-м нужно переходить и регу;шрованию одной из полученных ранее определяющих э. д. с., например э.д. с. е»,+p+q где q — положительное Iul! отрицательное целое число, удовлетворяющее условию
Р— — У < Д вЂ” 11, .
В с;.учае 2-м уменьшают э.д. с. е», „до нуля и переходят к ре-! улнровани!о э. д. c. e „„q ð TBK, HTQ()hl изменя locb B H I H, Io сторон ..
В случае 3-м регулирование e „, „прекращают в момент, когда напряжение на одном из свободных полюсов обращается в нуль, затем замыкают ключ К,, соответствующий этому полюсу, и, наконец, размыкают ключ 1(», р, при помощи которого регулируемая э. д. с. е» „была присоединена к цепи. После разх!ыка!!Ня этого ключа э. . с. е»,— р 1 станавливается llа нуль. Указанное переклlочение к,llочсй не приведет к 1!зменс1!Ню напря2ке11Н11! на полюсах преобразователя
СДО.
1!осле окончания операций, соответствующих 3-му случаю (основному ), получается положение, отличающееся от положения, которое име.ю место после выполнения операции 3 только тем, что вместо клю !е1! R» -1-1 lcm —, 2 ° .. Ь оказались 311 мкн1 ть! ми ")ругие 11 — 1н кл 1счей и определяюшимн стали другие =;. д. с.
Дальнейшее решение сводится к повторению четвертой и пятой операций до тех пор, пока никакое регулирование определяющих э.д. с. не будет приводить к изменению и, в требуемом направлении.
Если решаемая задача имеет единственное решение, то разобранный процесс будет выполнен за конечное число шагов, как это следует из теории симплексного метода.
Таким образом, описываемое моделирующее устройство позволяет уменьшить число отрабатывающих усилителей, увеличить устойчивость работы и устранигь влияние неидеальности характеристик диодов на точность решения задач, чем обусловливается полезность применения устройства.
¹ !56357
Предмет изобретения
Моделирующее устройство для решения задач линейного программирования, содержащее блок моделирования линейных ограничений, сумматор для вычисления линейной формы и диоды, о т л и ч а ю щ е е с я тем, что, с целью уменьшения числа отрабатывающих усилителей, увеличения устойчивости работы устройства и устранения влияния неидеальности характеристик диодов на точность решения задач, в нем в качестве блока моделирования линейных ограничений применен обратимый линейный преобразователь и логическое устройство, выполненное в виде системы регулируемых источников э.д. с. и ключевой схемы, служащее для реализации симплексного метода и присоединенное параллельно к полюсам обратимого линейного преобразователя, к диодам и ко входам сумматора.