Устройство для решения задач линейного программирования Советский патент 1978 года по МПК G06G7/48 

Изобретение относится IK вычислительной технике и может 1быть использовано для решения задач линейного nporpa.M.MHрования. Известно устройство для решения задач линейного програ.ммирования, содержащее операционный усилитель и ключи, резистивные матрицы ограничений и источники ЭДС 1. Однако это устройство .не позволяет решать задачи бивалентного нрограмлгарования. Наиболее близким техническим решением к изобретению является устройство, содержашее резистивную матрицу ограничений 2. Такое устройство также не обеспечивает возможности решения задач бивалентного п.рограммирования. Цель изобретения - ра.сширение области применения устройства путем решения задач бивалентного лрогра.ммирования. Указанная цель достигается тем, что устройство содержит два регистра, блок (проверки условий, блок .сравнения и блок генерирования соседних точек, выходом подключенный к .первому входу первого регистра, Первый выход которого через резиСтнвную матрицу ограничений соединен с ВХОДОМ блока проверки условий. Выход блока проверки условий соединен с первыми входами блОКа генерирования соседних точек и блока сравнения, второй и третий входы блока сравнения подключены соот.ветственно « второму выходу первого реги.стра, третий выход которого соединен с входом второго регистра, и к первому выходу второго .регистра, второй выход которого соединен с вторым входом первого регистра. Выход блока сравнения связан с вторым входом генерирования соседних точек. Структурная схема устройства для решения задач линейного .програмлш.ровалия приведена на чертеже. Она содерж.итблок / генерирования соседних точек, регистры 2 и 5, рези.стивную -матрицу 4 ограничений, блок 5 провер.кл условий и бло.к 6 сравнения. Устройство осушествляет поиск .минимуматр,и ограничениях J ац Xj , где (1 , п), Xj 0,1. Функция F достигает минимума в том случае, когда вектор х { x,. .. , Х;„ . .. , Xji содерЖИт минимальное количество Xj, .набор которых удовлетворяет ограничениям (2). Так как Xj шрИНИмает значение «О или «1, то можно представить вектор х как конституенту единиды некоторой булевой функции от п переменных. Общее количество конституент единицы функции от п snepeмееных равно 2. Как известно, булеву функцию представить в виде п-,мерного куба, каждой вершине которого поставлена в соответствие одна конституента адин,ицы. Конституенты единицы, которые соответствуют вершинам, связанным в кубе ребром, отличаются друг от друга только одним разрядом. Назовем такие «онституенты (вершины) соседними. Пусть задана матрица (а/у ) ограничений и некоторый начальный вектор реше«ия А°, удовлетворяющий огра,ничвниям (2). В общем случае это может быть .вектор, все компоненты которого равны «1. Прос.мотрим все соседние с заданны.м векторы х°,...,х°. Если среди просмотренных векторов есть вектор ;/, для «отоРОГО ВЫЛОЛНЯЮТСЯ условия (2) и уСЛОВИЯ у ,.-.0/ у j.°. Xj I ЛJ, то ;вектор Л / может оыть принят как улучщбнвое значение вектора д;° и обозначен х . Далее следует просмотреть все соседние с х конститденты: д:/,. .., .г,/. Если среди соседних векторов не найдется вектора, удовлетворяющего ограничениям (2) и (4), то можно у(Величить гл бину поиска, просмотрев соседние векторы л:/ (где /, k-, п) и т. |Д. Задав какую-либо глубину поиска, можио .получить лоКальный ми-нимум функции F. Устройство работает следующим образом., Перед .началом решения в блоки 2 и 3 заносится .начальный вектор л;°. Блок 2 вы.ра(батывает вектор A:I° первой соседнейточки, который заносится в блок 3. Из блока 3 он поступает ,на матрвцу 4 ограничен.ий, в которой совместно с .блоком 5 про.веряется Зтловие (2). Если оно выполняется, то проверяется условие (4), в блоке 6 срав-нвния. Если выполнено и это условие, то Содержимое блока 3 переписывается в блок 2, а блок / выдает вактор х и 1цикл по.вторяется. Если не выполняется условие (2) или (4), то соответственно с блоков 5 или 6 сигнал подается в блок / для выработки следующего вектора х. Решение заканчивается, когда .среди всех просмотренных 1на заданную глубину соседних точек .не найдется ни одного вектора, удовлетворяющего ограничениям (2) и (4). Фор м у л а и 3 о б р е т е и и я Устройство для решения задач лине 1ного програ-мм.ирования, содержащее резистивную матрицу ограничений, отличающееся тем, что, с целью расширения области применения .путем решения задач бивалентного программирования, OiHo содержит два регистра, блок проверки условий, блок сравнения и блок генерирования соседних точек, выход которого соединен с .первым входом пер. регистра, пер.вый выход которого через резистивную матрицу ограничений соединен с входом блока проверки условий, выход которого соединен с первыми входами блока генерирования соседних точек и блока сравнения, второй и третий .входы Которого .подклЮ1чены соответственно к второму выходу первого регистра, третий выход которого соединен с входом второго регистра, и к первому выходу .второго регистра, второй выход которого соединен с .вторым входом первого регистра, выход блока .сравнения .соединен с вторым входом блока генерирования соседних точек. Источники инфорМащии, принятые во занимание при экспертизе: . Авторское свидетельство СССР № 283696, кл. G 06 G 7/48, 1973. 2. Авторское свидетельство СССР № 243278, к л. G 06 G 7/48, 1969.

JJ