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

:г А ЙтЪГ ц 711590 ОПИЮ Е ИЗОБРЕТЕНИЯ Союз Советских Социалистических Республик(22) Заявлено 16.0977 (21) 2528814/18-24с присоединением заявки Но(23) ПриоритетОпубликовано 2 5,01.80 Бюллетень МДата опубликования описания 28,0180(51)М. Кл. С 06 С 7/48 Государственный комитет СССР но делам изобретений и открытий(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАИМИ РОВАН ИЯ Изобретение относится к областивычислительной техники и может бытьиспользовано при решении задач автоматического проектирования средстввычислительной техники,Известно устройство для решениязадач дискретного программиронания,содержащее блок генерирования соседних точек два регистра, блок сравнения, резистинную матрицу ограниченийи блок проверки условий 1, Однакоэто устройство .не учитывает индексовцен компонентов искомого решения.Наиболее близким техническим решением к данному изобретению является устройство, которое, как и дан-.ное устройство, содержит блок генерирования соседних точек, выход которого соединен со входом блока регистров точек, один выход которого 20соединен с первьм входом матрицы ограничений, а другой выход -о динен спервым входом, блока сравнения, второй вход которого подключен к выходу блока регистров цен, а выход матрицы ограничений через блок проверки условий соединен с первым входомблока генерирования соседних точек,второй вход которого подключен к выходу блока сравнения (21. Однако это ЗО устройство позволяет искать толькоминимум исследуемой функции. Целью изобретения является расширение функциональных возможностей за счет решения минимаксных задач. Укаэанная цель достигается тем,что устройство содержит блок заданиярежима, выход которого соединен стретьим нходом блока генерированиясоседних точек, вторым входом матрицы ограничений и третьим входом блока сравнения,На фиг. 1 приведена блок-схемаустройства для решения задач целочисленного программирования.На фиг. 2 представлена блок-схемаматрицы ограничений. Устройство содержит блок 1 задания режима, блок 2 генерирования соседних точек, блок 3 регистров точек, блок 4 регистров цен, матрицу 5 ограничений, блок 6 сравнения и блок 7 проверки условий. Матрица 5 ограничений содержит модели вершин 8, модели ребер 9 и модели вершин 10.при ограничениях где =1 А (2)(3) целое. Формула изобретения Устройство работает следующим образом. Оно осуществляет поиск минимума или максимума Функции Так как х принимает значения О или 1, то вектор решения Х является п15 мерным вектором, компоненты которого равны О или 1, В И-мерном пространстве каждое значение этого вектора определяет некоторую точку - вершину И -мерного куба. 2 ОМатрица ограничений (1 а; ) представляется в виде двудольного граФа 6 = (Х, У, (, где ) Х-подмножество вершин графа С, число которых равно числу. столбцов матрицы )о 1 )(,)У) 25 подмножество вершин графа 6, число которых равно числу строк матрицы (О)1, а- множество ребер, соединяющих подмножество вершинХ) иу, Вершинам х у) 1 х 1 бх)У 1 еЧ 3 Оинцидентно ребро ;, если элемент10.Вводятся две дополнительные вершиНы с( (источник) и(сток) . Все вершины множества Х) соединяются с вер- З- шиной с(., а все вершины множества У -35 с вершиной . Каждому ребруОЮО полученной сети ставится в соответствие пропускная сПособность, равная 1, и цена с= а, каждой вершине у ву - цена с = в, а ребрам ( у, ) - 4 О пропускная способность, равная 1, На построенной таким образом сети проверка выполнения условия (2) осуществляется следующим образом, Из вершины с(,по некоторым ребрам (с(, х; ) пропускается поток вещества, насыцающий все дуги, инцидентные х . Если общая стоимость потока, пришедшего в вершину у , больше, чем значение цены в в э 4 ой вершине, то ребро (у, р) онасыщается единицей вещества. При этом нужно отметить, что для вершинмножества )У не вьлолняется правило сохранения вещества, то есть эти вершинц потребляют вещество внутри себя . служат дополнительными стока-,миеЕсли исходным потоком насыщаются все дуги (у , ) то условие (2) выполняется, в противном случае - не выполняется, 6 ОПеред началом решения в блок 3 заносится начальный вектор Х 9, в блок4 - значение вектора цен с:с, с,с, а в матрицу 5 ограниченийэначение величины а 1 и в (.,= 1, 65 и) . Блок 1 настраивает блокин 6 для решения задачи на минимум (максимум) и выдает в блок 2 сигнал начала решения, Блок 2 вырабатываетовектор Х первой соседней точки, которая заносится в блок 3. Из блока 3 вектор поступает н", матрицу 5 ограничений и в блок б, где проверяются соответственно условие (2) и усло- вие Если с выходов блоков 5 и б поступили сигналы о выполнении проверяемых условий, то в блоке 3 рассматриваемый вектор Х принимается за центрВновой окрестности Х, блок 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 Г.Сороктко рректор Г.Решетни одпи с но тираж 751рственного комиэобретений и оХ, Раушская акаэ 9014/37 ЦИИИПИ Гос по делам 113035, Москвтета СССРкрытийнаб., д. 4/5 Проектная, 4 ключен к выходу блока сравнения,о т л и ч а ю щ е е с я тем, что, сцелью расширения функциональных воэможностей за счет решения минимаксных задач, оно содержит блок зада. -ния Режима, выход которого соединен 5с третьим входом блока генерированиясоседних точек, вторым входом матрицы ограничений и третьИм входом блока сравнения. Составителедактор Э.Губницкая Техред М,Филиал ППППатент , г.ужго Источники информации,принятые во внимание прн экспертизе1. Авторское свидетельство СССРпо заявке 9 2482044/18-24,кл. 6 06 6 7/48, 27.04,77. 2, Авторское свидетельство СССР по заявке 9 2523949/18-24,кл. С Об С 7/48, 12.09,77,