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

 

<>622П8

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик (61) Дополнительное к авт. свид-ву— (22) Заявлено 27.04.77 (21) 2482044/18-24 (51) М.Кл.2 6 06 G 7 48 с присоединением заявки №вЂ”

Государственный комитет

Совета Министров СССР ао делам изобретений и открытий (23) Приоритет— (43) Опубликовано 30.08.78, Бюллетень ¹ 32 (3) УДК 681.33 (088.8) (45) Дата опубликования описания 07.08.78 (72) Авто р ы изобретения

Н. Н. Садовой и Ю. О. Чернышев

Ростовский-на-Дону институт сельскохозяйственного машиностроения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ при ограничениях (2) где (i= I, n), х; = 0,1. (3) Изобретение относится к вычислительной технике и может быть использовано для решения задач линейного программирования.

Известно устройство для решения задач линейного программирования, содержащее операционный усилитель и ключи, резистивные матрицы ограничений и источники ЭДС (1). Однако это устройство не позволяет решать задачи бивалентного программирования.

Наиболее близким техническим решением к изобретению является устройство, содержащее резистивную матрицу ограничений 12), Такое устройство также не обеспечивает возможности решения задач бивалентного программирования, Цель изобретения — расширение области применения устройства путем решения задач бивалентного,программирования. 20

Указанная цель достигается тем, что устройство содержит два регистр а, блок проверки условий, блок сравнения и блок генерирования соседних точек, выходом подключенный к первому входу первого ре- 25 гистра, первый выход которого через резистивную матрицу ограничений соединен с входом блока проверки условий. Выход блока проверки условий соединен с первыми входами блока генерирования соседних то- З0 чек и блока сравнения, второй и третий входы блока сравнения подключены соответственно к второму, выходу первого регистра, третий выход которого соединен с входом второго регистра, и к,первому выходу второго регистра, второй выход которото соединен с вторым входом первого регистра. Выход блока сравнения связан с вторым входом блока генерирования соседних точек.

Структурная схема устройства для решения задач линейного программирования приведена на чертеже.

Она содержит блок 1 генерирования соседних точек, регистры 2 и 8, резистнвную ,матрицу 4 огра ничений, блок 5 проверки условий и блок 6 сравнения.

Устройство осуществляет поиск минимума функции

622118

10 !

5 (4) 45

Функция F достигает минимума в том случае, когда вектор х=, х„..., х;,..., хд) содержит минимальное количество х, = 1, набор которых удовлетворяет ограничениям (2). Так как х; принимает значение «0» или

<1», то можно представить вектор х как конституенту единицы некоторой булевой функ,ции от и переменных. Общее количество конституент единицы функции от п nepehtGBHbIx равно 2". 1(ак известно, булеву функцию можно представить в виде п-.ìåðного куба, каждой вершине которого поставлена в соответствие одна конституента единицы. Конституенты единицы, которые соответствуют верши нам, связанным 8 кубе ребром, отличаются друг от друга только одним разрядом. Назовем такие конституенты (вер шин ы) с о седни ми.

Пусть задана матрица (а;, ) ограничений и некоторый начальный вектор решения хо, удовлетворяющий ограничениям (2).

В общем случае это может быть, вектор, все компоненты которого равны «1».

Просмотрим все соседние с заданным векторы хо,...,х,",. Если среди просмотренных,векторов есть вектор х ", для которого выполняются условия (2) и условия то;вектор х " может быть принят как улучшен ное значение вектора хо и обозначен х .

Далее следует просмотреть все соседние с х констит енты: х,,..., х,,, Если среди соседних векторов не найдется вектора, удовлетворяющего ограничениям (2) и (4), то можно увеличить глубину поиска, просмотрев соседние, векторы х > (где l, 1=1, п) и т. д. Задав какую-либо глубину поиска, можно, получить локальный минимум функции F.

Устройство работает следующим образом.

Перед началом решения в блоки 2 и 3 заносится начальный вектор хо. Блок 2 вы,ра батывает вектор х пер вой соседней точки, который, заносится,в блок 8. Из блока 8

Зо

40 он поступает на матрицу 4 ограничений, в которой совместно с блоком 5 проверяется условие (2). Если оно выполняется, то inpoверяется условпе (4), в блоке б сравнения.

Если выполнено и этЬ-условие, то содержимое блока 3 переписывается в блок 2, а блок /,âûäàåò вектор х и цикл повторяется. Если не выполняется условие (2) или (4), то соответственно с блоков б или 6 сигнал подается в блок 1 для выработки следующего вектора х.

Решени заканчивается, когда среди всех просмотренных на заданную глубину соседних точек не найдется ни одного вектора, удовлетворяющего ограничениям (2) и (4).

Формула изобрете ния

Устройство для решения задач линейного программирования, содержащее резистивную матрицу ограничений, о т л и ч а ющ е е с я тем, что, с целью расширения ооласти применения путем решения задач бизалентного программирования, îíî содержит два регистра, блок проверки условий, блок сравнения и блак генерирования соседних точек, выход которого соединен с ,первым входом лервого регистра, первый вы:од которого через резистивную матрицу ограничений соединен с входом блока проверки условий, выход которого соединен с первыми входами блока генерирования соседних точек и блока сравнения, второй и третий, входы которого подключены соответственно к второму выходу первого регистра, третий выход которого соединен с входом второго регистра, и к первому,выходу второго регистра,,второй выход которого соединен с,вторым входом первого рвгистра, выход блока сравнения соединен с вторым входом блока генерирования соседних точек.

Источники информации, принятые во внимание при экспертизе:

l. Авторское свидетельство СССР

N 283696, кл. G 06 G 7/48, 1973.

2. Авторское свидетельство СССР № 243278, кл. G 06 G 7/48, 1969.

622118

Составитель Г. Сорокин

Техред А. Камышникова

Корректор В. Гутман

Редактор И. Грузова

Подписное

Тип. Харьк. фил. пред. «Патент»

Заказ 519/763 Изд. № 582 Тираж 84!

НПО Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, Ж-35, Раушская наб., д. 4/5