Устройство работает следующим образом. Оно осуществляет поиск минимума или максимума функции .-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, (прототип).
название | год | авторы | номер документа |
---|---|---|---|
СПОСОБ СТРУКТУРНО-ФУНКЦИОНАЛЬНОГО СИНТЕЗА ЗАЩИЩЕННОЙ ИЕРАРХИЧЕСКОЙ СЕТИ СВЯЗИ | 2013 |
|
RU2547627C2 |
Устройство для решения задач линейного программирования | 1977 |
|
SU622118A1 |
Устройство для решения задач дискретного программирования | 1977 |
|
SU693396A1 |
Устройство для анализа параметров сетей | 1987 |
|
SU1587533A1 |
Устройство для определения максимального паросочетания в транспортных сетях | 1976 |
|
SU669360A1 |
СИСТЕМЫ И СПОСОБЫ ДЛЯ МНОЖЕСТВЕННОГО ДОСТУПА С РАЗРЕЖЕННЫМ КОДОМ | 2013 |
|
RU2603280C1 |
Устройство для поиска минимального значения интенсивности размещения в полносвязных матричных системах при двунаправленной передаче информации | 2016 |
|
RU2634198C1 |
УСТРОЙСТВО АССОЦИАТИВНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ | 2019 |
|
RU2730179C1 |
УСТРОЙСТВО ДЛЯ ПОДСЧЕТА МИНИМАЛЬНОГО ЗНАЧЕНИЯ ИНТЕНСИВНОСТИ РАЗМЕЩЕНИЯ В СИСТЕМАХ С ДРЕВОВИДНОЙ ОРГАНИЗАЦИЕЙ | 2008 |
|
RU2379749C1 |
УСТРОЙСТВО ПОИСКА НИЖНЕЙ ОЦЕНКИ РАЗМЕЩЕНИЯ В МАТРИЧНЫХ СИСТЕМАХ | 2004 |
|
RU2275681C1 |
Авторы
Даты
1980-01-25—Публикация
1977-09-16—Подача