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

 

АЙЙ

<ц711590

ОПИЮ Е

ИЗОБРЕТЕНИЯ

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6!) Дополнительное к авт, сеид-ву (22) Заявлено 16.0977 (21) 2528814/18-24 с присоединением заявки ¹ (23) Приоритет

Опубликовано 25,01.80. Бюллетень №

Дата опубликования описамия 280180 (51)М. Кл.2

G G 7/48

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

СССР но делам изобретений и открытий

{53) УДК 681. ЗЗ5 (088.8) (72) Авторы изобретения

Ю. О. Чернышев и H. H.Ñ адовой (71) ЗаявитеЛЬ Ростонский-на-Дону институт сельскохозяйственного машиностроения (54) УстРОЙстВО длЯ Ревени Я ЗАдАч

ЦЕЛОЧИСЛЕННОГО ПРОГРАИМИ POBAHHH

Изобретение относится к области вычислительной техники и может быть использовано при решении задач автоматического проектирования средств вычислительной техники.

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

Наиболее близким техническим решением к данному изобретению явля- 1э ется устройство, которое, как и дан-. ное устройство, содержит блок генерирования соседних точек, выход которого соединен со .входом блока регистров точек, один выход которого соединен с .первьм входом матрицы ограничений, а другой выход =-о .динен с первым входом, блока сравнения, второй вход которого подключен к выходу блока регистров цен, а выход матрицы ограничений через блок проверки условий соединен с первым входом блока генерирования соседних точек, второй вход которого подключен к выходу блока сравнения (21. Однако это ЗО устройство позволяет искать тольксэ минимум исследуемой функции.

Целью изобретения является расширение функциональ ных возможностей за счет решения минимаксных задач.

Укаэанная цель достигается тем, что устройство содержит блок задания режима, выход которого соединен с третьим нходом блока генерирования соседних точек, вторым входом матрицы ограничений и третьим входом блока сравнения.

На фиг. 1 приведена блок-схема устройства для решения задач целочисленного программирования.

На фиг. 2 представлена блок-схема матрицы ограничений.

Устройство содержит блок 1 задания режима, блок 2 генерирования соседних точек, блок 3 регистров точек, блок 4 регистров цен, матрицу

5 ограничений, блок 6 сравнения и блок 7 проверки условий.

Матрица 5 ограничений содержит модели вершин 8, модели ребер 9 и модели вершин 1 О.

711590

Устройство работает следующим образом. Оно осуществляет поиск минимума или максимума функции и = 7c х.

1 при ограничениях и

;.са„,х > ,- Ч () где =1,к, (2) (3) целое.

l(.5 = 0)3 l ol j1 (1

Так как х принимает значения 0 или

1, то вектор решения Х является и-мерным вектором, компоненты которого равны 0 или 1. В И-мерном пространстве каждое значение этого вектора определяет некоторую точку — вершину И -мерного куба. 2О

Матрица ограничений )а; () представляется в виде двудольного графа G = (Х, У, U), где ) Х -подмножество вершин графа G число которых равно числу. столбцов матрицы Il a q II,, ) У вЂ” подмножество вершин графа G число которых равно числу строк матрицы

J(a > Il, à I VI — множество ребер, соединяющих подмножество вершин Х) и У . Вершинам х,у 1х б х), У„ У } инцидентно ребро Ul>, если элемент

-„ik0Вводятся две дополнительные вершиНы с((источник) и Р (сток) . Bce вершины множества Х) соединяются с вер- Зшиной с(., а все вершины множества )У вЂ”

35 с вершиной . Каждому ребру О -б () полученной сети ставится в соответствие пропускная способность, равная 1, и цена с„- = Bjj каждой вершине у в у — цена с = в, а ребрам (у, ) пропускная способность, равная 1, На построенной таким образом сети проверка выполнения условия (2) осуществляется следующим образом. Из вершины с(.по некоторым ребрам (с(, х; ) пропускается поток вещества, насыцающий все дуги, инцидентные x . Если общая стоимость потока, пришедшего в вершину у, больше, чем значение цены в.(в этой вершине, то ребро (у, р) g() насыщается единицей вещества. При этом нужно отметить, что для вершин множества )У не вьлолняется правило сохранения вещества, то есть эти вершинц потребляют вещество внутри себя - служат дополнительными стока-, ми б

Если исходным потоком насыщаются все дуги (у, p) то условие (2) выполняется, в противном случае - не выполняется. 6О

Перед началом решения в блок 3 заносится начальный вектор Х9, в блок

4 - значение вектора цен с= с, с,, c„), а в матрицу 5 ограничений значение величины а11 и в (i, = 1, 65

n). Блок 1 настраивает блоки

5 н 6 для решения задачи на минимум (максимум) и выдает в блок 2 сигнал начала решения, Блок 2 вырабатывает о вектор Х„первой соседней точки, которая заносится в блок 3. И з блока 3 вектор поступает н". матрицу 5 ограничений и в блок б, где проверяются соответственно условие (2) и условие

O о

СХ 6< .Г.С К

3= 3 j ()> 9= j 3 (4) .

Если с выходов блоков 5 и б поступили сигналы о выполнении проверяемых условий, то в блоке 3 рассматриваемый вектор X принимается за центр е новой окрестности Х, блок 2 вццает первую соседнюю точку Х„ и цикл повторяется.

Если не выполняются условия (2) или (4), то соответственно с выходов блоков 5 или б сигнал поступит в блок 2 для выработки следующего вектора Х и т,д.

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

Матрица 5 ограничений (фиг.2) работает следующим образом. На модель 8„. от блока 3 поступает 1 -я компонента Вектор Х= х, х, ° ° ., х,, которая может принимать значение 0 или 1. Если значение х .=1, то по всем моделям 9, инцидейтньм этой модели 8 „ проходит единичный поток со стоимостью, равной значению а " и записанной в соответствующей модели

9, Если общая цена по всем моделям

9, инцидентныч модели 10, превышает величину в,записанную в эту модель 10, то с йее сигнал поступает на блок 7. Если от всех моделей 10 пришли сигналы на блок 7, значит условие (2), проверяемое на матрице 5 ограничений, выполняется, в противном случае - не вытолняется.

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

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

Редактор Э.Губницкая Техред М. Петко рр

Заказ 9014/37 Тираж 751 . Подписное

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

113035, Москва. Ж 35, Раушская Ha0., д. 4/5

Филиал DlltI Патент, г.ужгород, ул.Проектная, 4 ключен к выходу блока сравнения, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей за счет решения минимаксных задач, оно содержит блок зада.. ния режима, выход которого соединен 5 с третьим входом блока генерирования соседних точек, вторым входом матрицы ограничений и третьим входом блока сравнения.

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

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

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