Локальные алгоритмы элиминации переменных, использующие в качестве структурного графа граф взаимосвязей переменных задачи.

Рассмотрим решение разреженной дискретной задачи оптимизации (8.8) – (8.10), структура которой описывается неориентированным графом взаимо­связей переменных , с помощью локального алгоритма элиминации переменных. ЛЭА использует упорядочение вершин графа.

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

Для данного упорядочения вершин графа в виде через обозначим множество вершин с индексами из , большими : .

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

Определение 8.9. Граф, полученный из графа с помощью

· удаления вершины и всех ребер, исходящих из нее и

· соединения ребрами всех ранее не соседних вершин в , называется -элиминационным графом графа и обозначается .

Описанная операция называется элиминацией вершины .

Для данного упорядочения работа ЛЭА состоит в последовательной элиминации вершин в текущем графе и вычислении соответствующей локальной информации о вершинах . Этот процесс порождает последовательность элиминационных графов: так что ‑ -элиминационный граф графа , а ‑ пустой граф.

Процесс преобразования графа взаимосвязей переменных, соот­вет­ству­ющий процедуре элиминации переменных с помощью локального алгоритма, известен как «элиминационная игра», которая впервые была введена Партером, как графовая интерпретация метода исключения Гаусса. Входом для алгоритма элиминационной игры является граф и упорядочение графа .

Одним из методов, позволяющим решать задачи ДО (P), является локальный алгоритм (ЛА) А, описанный в разделе 8.2.2. Одним из недостатков ЛА А является то, что он не решает до конца задачу дискретной оптимизации, а лишь упрощает ее (в отдельных случаях). Кроме того, между ЛА А и ЛА A, решающим квазиблочные задачи ДО, не видно явной связи.

Рассмотрим модификацию алгоритма A, несериальный ЛА (НСЛА), использующий парадигму динамического программирования (ДП) и позволяющий полностью решать задачи ДО путем элиминации переменных.

Рассмотрим задачу (P) ДО вида (8.8) – (8.10), структура которой задается графом взаимосвязей. Введем следующие обозначения для множеств вершин :

· Смежность множеств: (читается « смежно »), если существует вершина в и вершина в такие, что . означает .

· Окрестность множества вершин = . Замкнутая окрестность множества .

· Внутренность множества = .

· Граница множества = .

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

Локальный алгоритм элиминации переменных в задаче ДО состоит в последовательном исключении (элиминировании) пе­ре­менных, причем порядок, в котором переменные будут исключаться, важен, так как он существенно влияет на объем вычислений.

Рассмотрим описанную выше задачу ДО (P). Предположим без потери общности, что переменные исключаются в порядке . Рассмотрим исключение первой переменной . Найдем члены целевой функции, содержащие : и множество индексов ограничений, содержащих : . Совместно с в и в входят переменные из . Переменной соответствует следующая подзадача :

Тогда исходная задача (P) сводится к решению следующей задачи:

В последней задаче переменная, по сравнению с исходной задачей (P) из ограничений исключены ограничения с индексами из , а также члены целевой функции , однако появился новый член целевой функции , благодаря чему изменился граф взаимосвязей задачи: в нем вершина удалена, а вершины из соединены ребрами между собой (благодаря члену (содержащий вычисленную информацию), связавшему эти вершины между собой). Это называется «пополнением» (fill). Заметим, что вершины из образуют так называемую клику графа [6].

Новый граф взаимосвязей обозначим . Далее все окрестности пере­мен­ных находятся уже в новом графе . Алгоритм исключает оставшиеся переменные по одной за раз аналогичным образом. Будем предполагать, что пе­ременные перенумерованы так, что они исключаются следующим образом: . Исключение очередной переменной называется «шаг », а функ­ции (таблицы), вычисленные на этом шаге, будем обозначать .

ЛЭА может быть кратко записан так:

1. Перенумеровать переменные согласно порядку (в данном случае ).

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

Пример 8.1 (продолжение).

Рассмотрим решение задачи ДО (8.11)- (8.15) из примера 8.1. Обозначим ‑ множество всех переменных задачи; под­множества переменных, входящих в ограничения (8.12)- (8.15): ; .

Построим граф взаимосвязей этой задачи, сопоставляя каждой переменной задачи вершину графа и соединяя 2 вершины ребром, если соответствующие вершинам переменные взаимосвязаны, т.е. входят в одно и то же ограничение или, другими словами, входят в одно и то же подмножество . Так, вершины графа, соответствующие переменным , попарно соединены друг с другом ребрами, так как эти переменные входят в подмножество ; вершины для переменных также попарно соединены друг с другом реб­рами, так как эти переменные входят в подмножество то же можно сказать и о вершинах графа для переменных из подмножества и подмножества . В то же время не существует ребер графа, связывающих вершины и , так как эти переменные не входят одновременно ни в одно из подмножеств .

Как было отмечено выше, ЛА элиминации переменных состоит в после­довательном исключении переменных. Начнем с исключения переменной . Для этого проанализируем, используя граф взаимосвязей переменных (рис. 8.6 а)), с какими переменными связана ‑ с переменными и , состав­ляющими окрестность . Заметим, что вершина 1, соответ­ствующая пере­менной в графе, симплициальна, так как ее соседи (вершины 2 и 3) образуют клику. Построим из исходной задачи задачу оптимизации, содержащую пере­менную в целевой функции и ограничениях:

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

(8.12')

Далее для каждого набора значений переменных и , вычислим зна­чение переменной , для которого значение функции будет мак­си­маль­ным при соблюдении ограничения (8.12'). Вычисления запишем в таб­лицу 8.1, в которой

и ‑ значение переменной , соответствующее .

Таблица8.1. Вычисление

x2	x3	x1
	-
	-

Замечание. Символом «-» обозначено отсутствие допустимых решений.

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

.

Следуя обычной процедуре динамического программирования, рас­смотрим новую задачу (P₁), в которой уже нет исключенной переменной :

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

(8.13')

(P₁) (8.14')

(8.15')

Построим граф взаимосвязей этой новой задачи – элиминационный граф (рис. 8.6 б)).

Исключим на следующем шаге переменную . Для этого найдем окрестность , используя граф взаимосвязей переменных (рис. 8.6 б)): .

Построим задачу оптимизации, содержащую переменную в целевой функции и ограничениях:

Вычисления запишем в таблицу 8.2, в которой ‑ значение переменной , соответствующее .

Таблица 8.2. Вычисление

.

x2	x5
	-

Рассмотрим новую задачу (P₂), в которой уже нет переменной и ограничения (8.12') (учтенного в функции )

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

(8.14'')

(8.15'')

Граф взаимосвязей этой задачи показан на рис. 8.6 в).

Покажем возможность исключения сразу нескольких переменных (блока переменных). Анализируя граф взаимосвязей на рис. 8.6 в) и замечая, что и связаны лишь с (в ограничении (8.14'') и целевой функции), исключим их вместе (блоком), построив таблицу 8.3 для решения следующей оптимизационной задачи:

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

Таблица 8.3. Вычисление

.

		-
		-

В результате получим новую задачу (P₃), из которой исключен блок переменных и :

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

(8.15''')

Анализируя новый граф взаимосвязей на рис. 8.6 г) и замечая, что и связаны лишь с (в ограничении (8.15''') и целевой функции), исключим их вместе (блоком), построив таблицу 8.4 для решения следующей опти­ми­заци­онной задачи:

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

В результате получим новую задачу (P₄), из которой исключен блок пере­мен­ных и :

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

Решение последней задачи осуществляется сравнением значений целевой функции при и (табл. 8.5).

Таблица 8.4. Вычисление

.

		-

Таблица 8.5. Вычисление .

Из таблицы 8.5 получаем решение соответствующее макси­маль­ному значению целевой функции 18 исходной задачи. Порядок исключения переменных в приведенном примере: {x₁, x₅, (x₂, x₄), (x₆, x₇), x₃}. Можно убедиться, что исключение переменных в другом порядке, например, {x₃, x₆, x₇, x₂, x₁, x₄, x₅}, приводит к другому объему вычислений.

Таким образом, в рассматриваемом примере применялся принцип опти­мальности Беллмана, для нахождения максимального значения целевой функ­ции были построены таблицы. Чтобы найти само решение (значения пере­менных), нужно сделать обратный шаг процедуры динамического програм­мирования, анализируя таблицы в обратном порядке. Так, из таблицы 8.5 на­ходим оптимальное значение . Возвращаясь к таблице 8.4, находим для значения переменных и : . Из таблицы 8.3 находим, что значению соответствуют . Таблица 8.2 дает для значения соответствующее Зная , из таблицы 8.1 получим Итак, искомое решение , для которого достигается максимум целевой функции, равный 18.

К недостаткам описанного выше локального алгоритма элиминации пере­менных следует отнести то, что на каждом шаге он перебирает значения для всех переменных из исследуемой окрестности , а ЛА A ‑ лишь значения переменных из граничного множества . Ниже предлагается модификация ЛА эли­ми­нации переменных, сочетающая достоинства обоих алгоритмов.

Как мы уже отметили, ЛА элиминации переменных исследует окрест­ность некоторой переменной и находит для всех значений пере­мен­ных из этой окрестности оптимальное значение , что может приводить к боль­шому объему вычислений. Однако переменные из окрестности могут обла­дать разными свойствами по отношению к своей окрестности: одни из них имеют связи лишь с переменными из данной окрестности, другие же связаны и с переменными извне. Поэтому имеет смысл осуществлять полный перебор зна­чений лишь для переменных, принадлежащих границе окрестности , как в ЛА A, а оптимальные значения «внутренних» переменных окрестности (т. е. переменных из ) определять совместно с пере­менной , образуя «блок» переменных. В ЛА элиминации переменных пере­менные из могут рассматриваться как «блочная» переменная (или супер-переменная). Переменные в упорядочении , принадлежащие к , могут рассматриваться также как одна блочная переменная, про­индексированная переменной . При построении блочных переменных целесообразно использовать поня­тие «супер-вершины» [6], объединяющей в себе так называемые «нераз­ли­чи­мые вер­шины» (в графе G две смежные вершины u и v называются неразличимыми, если ).

Рассматривая квазиблочную задачу ДО, можно объединить все «внут­ренние» переменные блоков, являющиеся неразличимыми, в супер-вершины, со­от­ветствующие блокам, при этом общие переменные блоков (переменные из «перемычек») образуют другие супер-вершины. В результате решение ква­зи­блочной задачи ДО c помощью блочной модификации НСЛА сводится к ре­шению задачи с линейным графом вида и реализация этого алгоритма совпадает с ЛА A.

8.3.5. Графовые структуры локального элиминацион­ного алгоритма