Устройство для решения задач линейного программирования

Союз Советских Социалистических Республик(45) Дата опубликования описания 07.08,78 Государственный кемите Совета Министров ССС(71) Заявител 54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАД ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ при ограничениях(3 Изооретенпе относится к вычислительной технике и может быть использовано для рещения задач линейного программирования,Известно устройство для решения задач линейного программирования, содержащее операционный усилитель и ключи, резистивные матрицы ограничений и источники ЭДС 11. Однако это устройство не позволяет решать задачи бивалентного программирования.Наиболее близким техническим решением к изобретению является устройство, содержащее резистивную матрицу ограничений 12, Такое устройство также не обеспечивает возможности решения задач бивалентного программирования,Цель изобретения - расширение области применения устройства путем решения задач бивалентного программирования.Указанная цель достигается тем, что устройство содержит два регистра, блок проверочки условий, блок сравнения и блок генерирования соседних точек, выходом подключенный к первому входу первого регистра, первый выход которого через резистивную матрицу ограничений соединен с входом блока проверки условий. Выход блока проверки условий соединен с первыми входами блока генерирования соседних точек и блока сравнения, второй и третий входы блока сравнения подключены соответственно к второму, выходу первого регистра, третий выход которого соединен с входом второго регистра, и к,первому выходу второго регистра, второй выход которото соединен с вторым входом первого регистра. Выход блока сравнения связан с вторым входом блока генерирования соседних точек.Структурная схема устройства для решения задач линейного программирования приведена на чертеже.Она содержит блок 1 генерирования соседних точек, регистры 2 и 8, резистнвную ,матрицу 4 ограничений, блок б проверки условий и блок 6 сравнения.Устройство осуществляет поиск минимума функцииП(4) 450 Функция Г достигает минимума в том случае, когда вектор х= , х, хь, х содержит минимальное количество х,=1, набор которых удовлетворяет ограничениям (2). Так как х, принимает значение 0 или 1, то можно представить вектор х как кон. ституенту единицы некоторой булевой функ,ции от и переменных. Общее количество конституент единицы функции от а переменных равно 2", 1(ак известно, булеву функцию можно представить в виде и-мерного куба, каждой вершине которого поставлена в соответствие одна конституента единицы. Конституенты единицы, которые соответствуют вершинам, связанным в кубе ребром, отличаются друг от друга только одним разрядом. Назовем такие конституенты (вер шин ы) с о седни ми.Пусть задана матрица (а;, ) ограничений и некоторый начальный вектор решения хо, удовлетворяющий ограничениям (2), В общем случае это может быть, вектор, все компоненты которого равны 1.Просмотрим все соседние с заданным векторы хох,",. Если среди просмотренных,векторов есть вектор х ", для которого выполняются условия (2) и условия то,вектор х" может быть принят как улучценное значение вектора хо и обозначен х. Далее следует просмотреть все соседние с х констит енты: х х, Если среди соседних векторов не найдется вектора, удовлетворяющего ограничениям (2) и (4), то можно увеличить глубину поиска, просмотрев соседние, векторы х (где 1, 1=1, п) и т. д. Задав какую-либо глубину поиска, можно,получить локальный минимум функции Р.Устройство работает следующим образом. Перед началом решения в блоки 2 и 3 заносится начальный вектор хо. Блок 2 вы,рабатывает вектор х, первой соседнейточки, который, заносится,в блок 3. Из блока 3 20 25 Зо 35 40 он поступает на матрицу 4 ограниченй, в которой совместно с блоком 5 проверяется условие (2). Если оно выполняется, то проверяется условие (4), в блоке б сравнения. Если выполнено и эть-условие, то содержимое блока 3 переписывается в блок 2, а блок (,выдает вектор х и цикл повторяется. Если не выполняется условие (2) или (4), то соответственно с блоков б или 6 сигнал подается в блок 1 для выработки следующего вектора х.Решение заканчивается, когда среди всех просмотренных на заданную глубину соседних точек не найдется ни одного вектора, удовлетворяющего ограничениям (2) и (4).Формула изобретенияУстройство для решения задач линевного программирования, содержащее резистивную матрицу ограничений, о т л и ч а ющ е е с я тем, что, с целью расширения области применения путем решения задач бизалентного программирования, оно содержит два регистра, блок проверки условий, блок сравнения и блак генерирования соседних точек, выход которого соединен с ,первым входом первого регистра, первый выход которого через резистивную матрицу ограничений соединен с входом блока проверки условий, выход которого соединен с первыми входами блока генерирования соседних точек и блока сравнения, второй и третий, входы которого подключены соответственно к второму выходу первого регистра, третий выход которого соединен с входом второго регистра, и к первому,выходу второго регистравторой выход которого соединен с,вторым входом первого рвгистра, выход блока сравнения соединен с вторым входом блока генерирования соседних точек,Источники информации, принятые во внимание при экспертизе:. Авторское свидетельство СССР ЛЪ 283696, кл. С О 6 6 7/48, 1973.2. Авторское свидетельство СССР243278, кл, 6 06 С 7/48, 1969.622118 Составитель Г. Сорокин Техред А. Камышникова Корректор В, Гутман Редактор И. Грузова Подписное Тип. Харьк. фил. пред. Патент Заказ 519763 Изд, Ыо 582 Тираж 84НПО Государственного комитета Совета Министров СССРпо делам изобретений и открытийМосква, Ж, Раушская наб., д. 4/5