Локальные элиминационные алгоритмы в задачах дискретной оптимизации


Рассмотрим задачу ДО с ограничениями

(8.8)

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

, (8.9)

, (8.10)

где , ; ~ – одно из отношений , – конечное множество возможных значений переменной . Функции называются компонентами целевой функции.

Пример 8.1. Найти максимум функции с бинарными переменными:

(8.11)

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

(8.12)

(8.13)

(8.14)

(8.15)

 

8.3.3. Задание структуры разреженных задач дискретной оптимизации с помошью графового и гиперграфового представлений

Элементный граф

Рассмотрим подробнее детали реализации ЛЭА при решении задач ДО в случае, когда структурный граф является графом взаимосвязейпеременных, который в литературе называется также графом ограничений [33]. В графе взаимосвязей задачи ДО вершины соответствуют переменным, причем две вершины соединяются ребром, если соответствующие переменные имеются в одном и том же ограничении.

Определение 8.3. Две переменные и взаимосвязаны в задаче ДО с ограничениями, если они появляются вместе в одном компоненте ЦФ или в одном и том же ограничении (другими словами, если переменные входят одновременно во множество или во мно­жест­во .

Определение 8.4. Графом взаимосвязей задачи ДО называется неориентированный граф , для которого

· множество вершин соответствует множеству переменных задачи ДО;

· две вершины графа соединены ребром тогда и только тогда, когда соответствующие им переменные взаимосвязаны.

В дальнейшем будем отождествлять переменные задачи ДО с вершинами графа взаимосвязей.

 

 
 

 


Основным понятием в теории локальных алгоритмов является понятие близости элементов, определяемое понятием окрестности.

Определение 8.5. Две вершины и в графе называются соседними, если .

Определение 8.6. Множество переменных, соседних с переменной в графе , обозначается (или ) и называется окрест­ностью переменной .



Дата добавления: 2016-06-05; просмотров: 1266;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.