Локальный алгоритм А.

Рассмотрим задачу Z ЦЛП с бинарными переменными :

(8.1)

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

(8.2)

(8.3)

Определение 8.1. Множество называется окрестностью первого порядка переменной , здесь .

Введем понятия -окрестности и -окрестности:

где

Окрестность произвольного порядка переменной определяется по индукции. Пусть известна окрестность р-го порядка. Окрестность -го по­рядка определим так: .

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

Введем так называемое внешнее кольцо , т.е. следующее множество переменных: .

Опишем ЛА .

1. Выберем некоторую переменную задачи .

2. Построим окрестность и множество .

3. Определим внешнее кольцо: .

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

5. Решим задачу для всевозможных булевых наборов (всего их ).

6. Если в результате решения этих задач получим, что либо

а) во всех оптимальных решениях задач , либо

б) во всех оптимальных решениях задач ,

тo в случае а) в оптимальном решении исходной задачи , а в случае б) в оптимальном решении исходной задачи .

7. Если в п. 6 имел место случай а) или б), переменной присваивается соответствующее значение и она исключается из задачи .

8. Перейти к п.1.

Как следует из вышеизложенного, в ЛА каждой переменной ставится в соответствие информационный вектор , содержащий информацию о предикатах : « во всех оптимальных решениях задачи » и : « во всех оптимальных решениях задачи ». Если , то ‑ истинный; если же , то ‑ ложный; если , то информация об истинности предиката отсутствует. Таким образом, ЛА позволяет переходить от одного множества переменных к другому множеству , содержащему больше информации о решении задачи ,т.е.причем , , где ‑функция ЛА.

8.2.3. Локальный декомпозиционный алгоритм решения задач дискретной оптимизации с блочно-древовидной структурой

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

Введем необходимые для дальнейшего изложения понятия. Пусть ‑ система окрестностей некоторых переменных , где ‑ соответственно множества индексов переменных и ограничений для -й окрестности, , причем

(8.4)

(8.5)

(8.6)

(8.7)

для любой тройки индексов .

Замечание. Отметим, что при определении понятия блочно-древовидной структуры мы пользуемся понятием окрестности, а не блока, хотя эти два понятия тесно связаны. Дело в том, что блочную структуру в матрице инциденций задачи ДО можно выделить с помощью анализа окрестностей переменных, нетрудно видеть, что если путем перестановки строк и столбцов матрицы инциденций и переменных и ограничений (8.2) задачи ДО (8.1)‑(8.3) можно собрать вместе ограничения с индексами из и переменные с индексами из , то мы получим подматрицу – блок.

Нетрудно видеть, что блочно-древовидная структура является частным случаем древовидной декомпозиции.

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

Определение 8.2.Блочно-древовидной назовем задачу ДО, для которой можно выделить систему окрестностей , удовлетворяющую свойствам (8.4) ‑ (8.7), причем граф пересечений окрестностей является деревом.

Будем говорить, что описанная задача ДО имеет блочно-древовидную (БД) структуру.

Замечание. Частным случаем БД структуры является квазиблочная структура, для которой граф пересечений окрестностей (или блоков) является линейным деревом (путем) (рис. 8.1).

Рис 8.1. Квазиблочная структура.

Одним из первых классов больших разреженных задач линейного программирования, которые начал изучать создатель линейного программирования G. Dantzig, был класс квазиблочных (или «лестничных») задач ЛП для динамического планирования[2]. Имеются другие примеры квазиблочных задач ЛП для многоэтапного планирования, составления расписаний, назначений и многоэтапного структурного проектирования. Квазиблочную структуру имеют задачи оптимального резервирования гостиничных номеров[3], аналогичные последним темпоральные задачи о ранце[4], получившие в последнее время применение при решении задач предварительного резервирования вычислительных ресурсов в Grid Computing, задачи линейного динамического программирования[5], некоторые задачи управления трудовыми ресурсами, динамические модели экономики, учитывающие в явном виде фактор времени, задачи управления в иерархических (обычно древовидных)структурах, сетевые задачи.

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

Изложим ЛА решенияБД задач ЦЛП вида (8.1) ‑(8.3),где матрица имеет БД структуру, содержащую блоков, и этой структуре соответствует дерево инцидентности блоков.

Рассмотрим вершину дерева и дерево D_r, состоящее из вершины и всех ее потомков. Введем необходимые обозначения: ‑ множество индексов переменных, принадлежащих блоку ; ‑ множество индексов переменных, принадлежащих одновременно блокам и ; если , то ‑ вектор переменных, общих для блоков и .

Обозначим через следующую задачу: для каждого вектора найти и , такие, чтобы

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

,

здесь ‑ значение целевой функции задачи , соответствующей дереву .

Решение задачи для вершины графа при фиксированном векторе обозначим таким образом:

.

Понятно, что .

Нетрудно заметить, что если зафиксировать вектор , то задача (8.1)‑(8.3) распадается на две задачи: первая соответствует дереву ; а вторая – . На этом свойстве и основано применение ЛА для решения БД задач ДО.

Алгоритм вычисляет информацию, поднимаясь от листьев дерева к корневой вершине. Изложим ЛА решения БД задачи ДО, характеризующейся деревом инцидентности блоков с вершинами, состоящим из слоев. Пусть в -м слое имеется вершин , разбитых на подмножества .

Алгоритм

Шаг 1. Положить для всех .

Шаг 2. Для каждой вершины слоя дерева решить задачу . Если эта задача не имеет решения ни для одной вершины данного слоя ‑ перейти к шагу 5, в противном случае ‑ к шагу 3.

Шаг 3. Если , то перейти на слой выше, т.е. положить и перейти к шагу 2, иначе ‑ к шагу 4.

Шаг 4.Конец вычислений. Решение задачи на уровне является решением исходной задачи: .

Шаг 5. Конец вычислений. Задача не имеет допустимых решений.

Пример, иллюстрирующий работу алгоритма . Решим имеющую БД структуру задачу ЦЛП, которой соответствует дерево инцидентности блоков на рис.8.2:

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

.

Рис. 8.2. Дерево инцидентности блоков в примере.

Начнем решение со слоя . Рассмотрим задачу, соответствующую

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

Если , то . Если , то .

Для соответствующая задача имеет вид

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

Если , то . Если , то .

Таким образом, все вершины слоя рассмотрены.

Перейдем на слой . Рассмотрим вершину . Для нее , вершина-предок . Соответствующая задача имеет вид

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

Если , то .

Если , то .

Рассмотрим вершину . Для нее . Нужно решить задачу

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

Если , то

,

если , то

.

Все задачи слоя рассмотрены.

Перейдем к слою , здесь всего одна вершина , причем . Соответствующая задача имеет вид

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

Решаем эту задачу, получаем, что оптимальному решению соответствуют , причем

.

Упорядочивая переменные, приходим к тому, что решение исходной задачи (которое, как уже отмечено, совпадает с решением задачи ) имеет вид x₁=1, x₂=0, x₃=1, x₄=0, x₅=1, x₆=0, x₇=1, x₈=0, x₉=1, x₁₀=1, x₁₁=0, x₁₂=1, x₁₃=1, x₁₄=0, Z_max=23.