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

Описание патента на изобретение SU711590A1

Устройство работает следующим образом. Оно осуществляет поиск минимума или максимума функции .-X; jz J J при ограничениях п , где -|7к, (2) Sa.-X; Ъ; -JH J Jt) Ч - целое.(3) S-° «ji Так как х принимает значения (Г или 1, то вектор решения X являетсяп- мерным вектором/, компоненты которого равны О или 1. В я-мерном пространст ве каждое значение этого вектора определяет некоторую точку вершину h-мерного куба. Матрица ограничений || представляется в виде двудольного графа G (X, У, и),.где I х -подмножест во вершин графа G;, число которых равно числу столбцов матрицы lloij )|, , jvj подмножество вершин графа G, число которых равно числу строк матрицы а (и - множество ребер, соединяквдих подмножество вершин Jx) и У , Вершинам х ,yj , У,-б{У|} инцидентно ребро Uij , если элемент а,. Вводятся две дополнительные верии ны о( (источник) и р) (сток) , Все вершины множества Х соединяются с вер шиной ct, а все вершины множества У с вершиной р). Каждому ребруК е и} полученной сети ставится в соответст вие пропускная способность, равная 1 .,- , каждой, вершине и цена c.j у,,-б|У - цена CJ-BJ, а ребрам (у.,-,(Ь) пропускная способность, равная 1. На построенной таким образом сети проверка выполнения условия (2) осущест вляется следующим образом. Из вершины oL по некоторым ребрам (d, х. ) пропускается поток вещества, насьщакщий все дуги, инцидентные х, Если общая стоимость потока, пришедшего в вершицу у.- , больше, чем значение цены BJ в этой вершине, то ребро (,р насыщается единицей вещества. При этом нужно отметить, что для вершин множества У| не выполняется правило сохранения вещества, то есть эти вер uniHb) потребляют вещество внутри себя - служат дополнительными стока-, ми. Если исходным потоком насыщаются то условие (2) вывсе дуги (у- ,р,) полняётся, в противном случае - не выполняется. Перед началом решения в блок 3 за .носится начальный вектор Х°, в блок 4 - значение вектора цен , с,, ,, ,j Сг(, а в матрицу 5 ограничений значение величины aij и в) (1,, п). Блок 1 настраивает блоки и 6 для решения задачи на минимум (максимум) и вьщает в блок 2 сигнал начала решения. Блок 2 вырабатывает вектор Х° первой соседней точки, которая заносится в блок 3, Из блока 3 вектор поступает нг. матрицу 5 ограничений и в блок 6, где проверяются соответственно условие (2) и условиеsc,re..±:c,K J i u)j с выходов блоков 5 и б поступии сигналы о выполнений проверяемых условий, то в блоке 3 рассматриваемый вектор Х° принимается за центр новой окрестности х , блок 2 вьщает первую соседнюю точку и цикл повторяется. Если не выполняются условия (2) или (4), то соответственно с выходов блоков 5 или 6 сигнал поступит в блок 2 для выработки следующего вектора Xg и т,д. Решение заканчивается, когда среди всех просмотренных на заданную глубину векторов не найдется ни одного, удовлетворяющего ограничениям (2) и (4).. Матрица 5 ограничений (фиг,2) работает следующим образом. На модель от блока 3 поступает i -я компонента вектор х(х, Xg, .,,, которая может принимать значение О или 1, Если значение , то по всем моделям 9, инцидентньв этой модели , проходит единичный поток со стоимостью, равной значению а -; и записанной в соответствующей модели 9, Если общая цена по всем моделям 9, инцидентньм модели 10, превышает величину В:,записанную в эту модель 10, то с нее сигнал поступает на блок 7. Если от всех моделей 10 пришли сигналы на блок 7, значит условие (2), проверяемое на матрице 5 ограничений, выполняется, в противном случае - не выполняется. Формула изобретения Устройство для решения задач целочисленного программирования, содержащее блок генерирования соседних точек, выход которого соединен со входом блока регистров точек, один выход которого соединен с первым входом матрицы ограничений,- а другой выход соединен с первьм входом блока сравнения, второй вход которого подключен к выходу блока регистров цен, а выход матрицы ограничений через блок проверки условий соединен с первым входом блока генерирования соседних точек, второй вход которого подключей к выходу блока сравнения, отличающееся тем, что, с целью расширения функциональных возможностей за счет решения минимаксных задач, оно содержит блок эадат. ния режима, выход которого соединен с третьим входом блока генерирования соседних точек, вторым входом матрицы ограничений и третьим входом блока сравнения.

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

1. Авторское свидетельство СССР по заявке 2482044/18-24, G 06 G 7/48, 27.04.77.

кл

2. Авторское свидетельство СССР по заявке 2523949/18-24, кл. G 06 G 7/48, 12.09.77, (прототип).

Похожие патенты SU711590A1

название год авторы номер документа
СПОСОБ СТРУКТУРНО-ФУНКЦИОНАЛЬНОГО СИНТЕЗА ЗАЩИЩЕННОЙ ИЕРАРХИЧЕСКОЙ СЕТИ СВЯЗИ 2013
  • Архипов Николай Сергеевич
  • Полянский Иван Сергеевич
  • Беседин Иван Игоревич
  • Еременко Владимир Тарасович
  • Фролов Михаил Михайлович
RU2547627C2
Устройство для решения задач линейного программирования 1977
  • Садовой Николай Николаевич
  • Чернышев Юрий Олегович
SU622118A1
Устройство для решения задач дискретного программирования 1977
  • Чернышов Юрий Олегович
  • Садовой Николай Николаевич
SU693396A1
Устройство для анализа параметров сетей 1987
  • Васильев Всеволод Викторович
  • Табунщик Иван Андреевич
  • Тонкаль Елена Владимировна
  • Федотов Николай Васильевич
SU1587533A1
Устройство для определения максимального паросочетания в транспортных сетях 1976
  • Чернышев Юрий Олегович
  • Садовой Николай Николаевич
SU669360A1
СИСТЕМЫ И СПОСОБЫ ДЛЯ МНОЖЕСТВЕННОГО ДОСТУПА С РАЗРЕЖЕННЫМ КОДОМ 2013
  • Никопур Хосейн
  • Балих Мохаммадхади
RU2603280C1
Устройство для поиска минимального значения интенсивности размещения в полносвязных матричных системах при двунаправленной передаче информации 2016
  • Борзов Дмитрий Борисович
  • Соколова Юлия Васильевна
RU2634198C1
УСТРОЙСТВО АССОЦИАТИВНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ 2019
  • Кучуганов Валерий Никонорович
RU2730179C1
УСТРОЙСТВО ДЛЯ ПОДСЧЕТА МИНИМАЛЬНОГО ЗНАЧЕНИЯ ИНТЕНСИВНОСТИ РАЗМЕЩЕНИЯ В СИСТЕМАХ С ДРЕВОВИДНОЙ ОРГАНИЗАЦИЕЙ 2008
  • Борзов Дмитрий Борисович
  • Минайлов Виктор Викторович
RU2379749C1
УСТРОЙСТВО ПОИСКА НИЖНЕЙ ОЦЕНКИ РАЗМЕЩЕНИЯ В МАТРИЧНЫХ СИСТЕМАХ 2004
  • Борзов Дмитрий Борисович
RU2275681C1

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

Формула изобретения SU 711 590 A1

SU 711 590 A1

Авторы

Чернышев Юрий Олегович

Садовой Николай Николаевич

Даты

1980-01-25Публикация

1977-09-16Подача