Отличительной особенностью многих практических задач исследования является их большая размерность. В частности, при решении задач оптимального планирования на макроуровне, матрица ограничений достигает размерности 104-105. При такой размерности классические методы математического программирования (линейного, нелинейного, дискретного) оказываются малоэффективными. Т.е. мы сталкиваемся здесь с феноменом 'проклятие размерности' в понимании Р.Беллмана.
Это обусловило необходимость разработки специальных методов как точных, так и приближенных, предназначенных для задач большой размерности. Большинство из этих методов использует идею декомпозиции, которая заключается в расчленении исходной задачи большой размерности, нахождении независимых решений для каждой из них и последующей увязке этих частных решений в общее решение исходной задачи. Впервые идея декомпозиции применительно к задачам ЛП была сформулирована Г.Данцигом и Вульфом, а позднее была развита в работах Д.Б.Юдина, Б.Г.Гольштейна [12], М.Месаровича, Л.Лэсдона [31], В.Цуркова [52] и др.
10.1. МЕТОД ДЕКОМПОЗИЦИИ Данцига-Вульфа
В 1960 г. Данциг и Вульф разработали метод декомпозиции для решения задач высокой размерности со специальной структурой матрицы ограничений [31].
Этот метод оказался наиболее эффективным для решения задач, матрица ограничений которых имеет блочно-диагональный вид с небольшим числом переменных. Однако, как показали дальнейшие исследования, метод применим также и для задач ЛП с матрицей общего вида. Соответствующий метод предложен Д.Б.Юдиным и Э.Г.Гольштейном и называется 'блочным программированием' [12].
Отличительной особенностью метода декомпозиции является использование координинующей задачи, которая имеет по сравнению с исходной небольшое число строк и большое число столбцов. Существенным является то, что для решения координирующей задачи не требуется задания всех столбцов в явном виде. Они генерируются в процессе использования симплекс-метода. Такой подход называют методом генерации столбцов. Сущность его состоит в следующем. Пусть имеется задача Л.П вида:
максимизировать:
(10.1.1)
при ограничениях:
(10.1.2)
Аj и b- m- мерные векторы-столбцы (m<n).
Допустим, что известно некоторое допустимое базисное решение (Д.Б.Р.) XB и соответствующая ему матрица из базисных векторов A. Допустим также, что XB был найден методом обратной матрицы. Тогда одновременно был найден и вектор относительных оценок 
где Cx-вектор коэффициентов целевой функции для текущего базиса.
Чтобы определить возможность улучшения Д.Б.Р. XB для каждого небазисного вектора Aj вычисляется величина оценки
(10.1.3)
Если 
то начальное решение может быть улучшено путем введения в базис переменной XS. Однако, если имеется большое число небазисных столбцов (n³103), то нахождение DS путем вычисления Dj для всех небазисных векторов 
и последующего их сравнения практически невозможно. И что очень важно, оказывается, что это и не требуется.
Будем предполагать, что все столбцы AS выбираются из некоторого выпуклого множества S, определяемого системой неравенств и равенств. Тогда вектор-столбец, который необходимо ввести в базис, можно определить в результате решения вспомогательной задачи вида:
минимизировать
(10.1.4)
где 
- некоторая заданная функция вектора Aj. В зависимости от структуры множества S и вида функции C(Aj) выбирается наиболее эффективный метод решения указанной задачи. Такой способ называют методом генерации столбцов, так как при решении задачи (10.1.4.) фактически используется лишь небольшое число столбцов, генерируемых по мере надобности. При этом значительно снижается требуемый объем памяти для хранения текущих результатов, что является существенным преимуществом при решении задач большой размерности.
Принцип декомпозиции
Рассмотрим задачу ЛП, матрица ограничений которой имеет блочно-диагональную структуру вида
. (10.1.5)
Строка 
называется связывающей, так как она связывает вместе все переменные задачи в некотором ограничении или их группе. Соответствующая задача Л.П. записывается в виде:
максимизировать
(10.1.6)
при условиях
(10.1.7)
(10.1.8)
Заметим, что к виду (10.1.5) можно привести матрицу любой задачи ЛП при p=1 в результате соответствующего разбиения ограничений на два подмножества. Действительно, произвольную задачу можно записать в виде:
максимизировать
(10.1.9)
при условиях
(m1 ограничений), (10.1.10)
(m2 ограничений), (10.1.11)
. (10.1.12)
Предположим, что выпуклое многогранное множество S2, определяемое условием (10.1.11), является ограниченным, т.е. представляет собой многогранник (это условие не является ограничительным). Тогда справедлива лемма о крайней точке, доказанная в приложении 1.
Пусть
- непустое замкнутое ограниченное множество, 
- его крайние точки. Тогда любая точка 
может быть представлена в виде выпуклой комбинации крайних точек множества R, т.е.
(10.1.3)
Обобщение этой леммы на случай, если множество является неограниченным, формулируется так: пусть 
- непусто. Любая точка принадлежит множеству R тогда и только тогда, когда она может быть представлена как выпуклая комбинация крайних точек и линейной комбинации с неотрицательными коэффициентами направляющих векторов неограниченных ребер множества, т.е.
(10.1.14)
где
В соответствии с леммой любой элемент S2 может быть представлен в виде
где 
xj - крайние точки многогранника S2.
Исходная задача (10.1.9)-(10.1.12) может быть сформулирована таким образом. Из всех решений (10.1.11)-(10.1.12) необходимо выбрать такое, которое удовлетворяет (10.1.10) и обращает функцию (10.1.9) в максимум. Подставляя (10.1.14) в (10.1.9), получим новое выражение для целевой функции
(10.1.15)
а подставив (10.1.14) в (10.1.10), получим
. (10.1.16)
Обозначим
(10.1.17)
С учетом (10.1.15)-(10.1.17) приходим к следующей задаче:
максимизировать 
(10.1.18)
при ограничениях
(10.1.19)
(10.1.20)
(10.1.20)
Эта задача, которая эквивалентна исходной (10.1.9)-(10.1.12), называется координирующей задачей. Она имеет только 
строк ограничений по сравнению с 
строками исходной задачи, и очень большое число столбцов, равное числу крайних точек множества S2. Чтобы не хранить все эти столбцы в памяти ЭВМ, будем получать их по мере необходимости, пользуясь методом генерации столбцов. С этой целью для каждого небазисного вектора вычислим величину
(10.1.22)
Представим вектор 
в виде 
где вектор 
соответствует ограничениям (10.1.19) а 
- единственному ограничению (10.1.20). Используя формулы (10.1.16), (10.1.17) для определения 
и 
, получим
(10.1.23)
В соответствии с обычными правилами симплекс-метода для определения переменной 
, вводимой в базис, необходимо минимизировать
. (10.1.24)
Так как оптимальное решение задачи ЛП (при условии, что допустимое множество 
- ограничено) достигается в крайней точке этого множества, то выполнение операции (10.1.24) эквивалентно решению подзадачи вида:
минимизировать
(10.1.25)
при ограничениях
. (10.1.26)
Найдя ее решение 
проверяем условие
и, если оно выполняется, то вектор 
выгодно ввести в базис. Далее определяем компоненты вектора 
который следует ввести в базис координирующей задачи
(10.1.27)
а также соответствующий коэффициент в целевой функции
(10.1.28)
Этот подход оказывается особенно эффективным, если 
т.е. исходная задача записывается в виде
максимизировать
(10.1.29)
при ограничениях
(10.1.30)
.... (10.1.31)
(10.1.32)
Для такой задачи подзадача (10.1.25)-(10.1.26) будет иметь вид:
минимизировать
(10.1.33)
при ограничениях
(10.1.34)
(10.1.35)
В силу аддитивности целевой функции (10.1.33) и независимости ограничений (10.1.34) задача (10.1.33) распадается на независимые задачи вида
(10.1.36)
при ограничениях
(10.1.37)
Обозначим решение задачи (10.1.36) через 
а 
Если 
то вектор 
может быть введен в базис координирующей задачи. Если же 
то текущее решение оптимально.
Описание алгоритма декомпозиции
Дадим формальное описание алгоритма декомпозиции Данцига-Вульфа для решения задачи (10.1.29)-(10.1.32) (20). Пусть уже имеется начальное допустимое базисное решение задачи (10.1.18)-(10.1.21), которому соответствует вектор разрешающих множителей 
. Каждая итерация алгоритма состоит из двух этапов.
Первый этап. 1. Используя вектор оценок предыдущей итерации, сформируем и решим подзадачи (10.1.36)-(10.1.37) и найдем оптимальное значение целевой функции, а также соответствующие решения 
2. Вычислим минимальную оценку
(10.1.38)
3. Если то вычисление заканчивается и определяем оптимальное решение задачи (10.1.29)-(10.1.32)
(10.1.39)
где 
- предыдущее базисное решение координирующей задачи, а 
- крайняя точка , соответствующая базисной переменной 
Если 
то переходим ко второму этапу.
Второй этап. Формируем столбец 
который необходимо ввести в базис задачи (10.1.18)-(10.1.21):
(10.1.40)
Вводим вектор 
в базис, выполняем первый шаг симплекс-метода, после чего находим новое допустимое базисное решение
а также новый вектор оценок
На этом итерация заканчивается и переходим к первому этапу очередной итерации.
Как видно из описания, алгоритм декомпозиции Данцига-Вульфа представляет собой двухуровневый алгоритм, где на первом уровне решаются подзадачи (10.1.36), (10.1.37), а на втором уровне - координирующая задача (10.1.18)-(10.1.21). Если координирующая задача является невырожденной, то на каждой итерации значение целевой функции возрастает, и поскольку число базисов ее конечно и ни один из них не используется дважды, оптимальное решение находится за конечное число шагов.
Ограниченная координирующая задача
Как следует из приведенного выше описания алгоритма декомпозиции, оптимизационная задача в нем решается лишь на первом уровне, тогда как на втором фактически выполняется лишь одна итерация симплекс-метода. Однако возможна модификация этого метода, заключающаяся в решении оптимизационных задач на двух уровнях. В этом случае решается так называемая ограниченная координирующая задача, которая получается из координирующей задачи (10.1.18)-(10.1.21) в результате отбрасывания всех столбцов, за исключением базисных и претендующих на включение в базис на текущей итерации.
Такую ограниченную координирующую задачу можно представить в виде:
максимизировать
(10.1.41)
при ограничениях
(10.1.42)
где 
- переменные текущего базиса: 
- переменная, вводимая в базис (для нее 
). Если текущий базис является невырожденным, то из него будет выведена переменная, для которой 
и полученное решение будет оптимальным.
Заметим, что возможны случаи, когда использование ограниченной координирующей задачи по сравнению с обычной координирующей задачей дает эффект.
Варианты декомпозиции прямой задачи
Существует много разных способов декомпозиции прямой задачи, каждый из которых приводит к своей форме координирующей и ограниченной координирующей задач.
Рассмотрим, например, вариант декомпозиции для матрицы блочно-диагонального вида. Обозначим решение системы 
(10.1.43)
где 
крайние точки многогранника 
;
Тогда координирующая задача будет иметь вид:
максимизировать
(10.1.44)
при ограничениях
(10.1.45)
(10.1.46)
где 
Координирующая задача (10.1.44)-(10.1.46) отличается от координирующей задачи (10.1.18)-(10.1.21). Во-первых, она имеет не одно, а 
ограничений типа (10.1.46), во-вторых, решение для каждой подсистемы 
самостоятельно выражается через переменные 
, тогда как в задаче (10.1.13)-(10.1.21) эти решения рассматривались совместно. Применим метод обратной матрицы с использованием процедуры генерации столбцов для решения задачи (10.1.44)-(10.1.46).
Пусть 
- базисная матрица размерности 
а 
- вектор относительных оценок для этого решения ( -оценка ограничений (10.1.45), а 
- оценка для i-го ограничения (10.1.46)).
Вычисляем теперь оценки 
для векторов, соответствующих переменным
(10.1.47)
Для определения 
при фиксированном 
решаем подзадачу вида:
минимизировать
(10.1.48)
при ограничениях
(10.1.49)
Если
то текущее решение - оптимально, в противном случае - в базис задачи (10.1.44)-(10.1.46) вводится переменная, для которой
(10.1.50)
Если этот минимум достигается при 
а 
решение подзадачи с индексом 
то в базис координирующей задачи вводится столбец
где 
-мерный вектор, все компоненты которого равны 0, за исключением 
-й компоненты, равной 1.
Пример 10.1. Для иллюстрации метода декомпозиции рассмотрим задачу ЛП:
максимизировать
(1)
при ограничениях
(2)
(3)
(4)
Эта задача имеет одно связывающее ограничение и два независимых блока. Области допустимых решений неравенств обоих подсистем представлены на рис. 10.1.
Разбиение задачи (1)-(4) может быть осуществлено разными способами, и каждому из них будет соответствовать своя координирующая задача с определенным типом ограничений вида 
Воспользуемся видом ограничений и построим ограниченную координирующую задачу, которая будет иметь два ограничения. Пусть 
и 
- допустимые решения блоков (1) и (2) соответственно. Тогда справедливо соотношение
и 
где 
крайние точки множеств 
и 
соответственно определяемые ограничениями (3) и (4).
Целевая функция (1) в векторном виде запишется:
а связывающее ограничение
где 
Запишем теперь координирующую задачу:
максимизировать
(5)
при условиях
(6)
(7)
(8)
(9)
Выберем в качестве начального допустимого базисного решения 
Будем решать эту задачу методом обратной матрицы. Начальная симплекс-таблица будет иметь вид Табл. 10.1.
В последней строке таблицы находятся переменные {
}:
где 
соответствует ограничению (7); 
- ограничению (8), а 
соответствует ограничению (8), а 
- ограничению (9).
Первая итерация. Первый этап. Составим и решим подзадачи, отвечающие начальному ДБР:
1) минимизировать
при ограничениях 
2) минимизировать
при ограничениях 
Оптимальные решения этих задач легко находятся графически и равны:
Найдем минимальные оценки векторов-столбцов:
Тогда оптимальные решения подзадач 
и 
образуют новые столбцы координирующей задачи, которые имеют вид:
Второй этап. Запишем ограниченную координирующую задачу, используя ее текущий базис и эти столбцы:
максимизировать (14)
при условиях
Для решения этой задачи используем метод обратной матрицы, как наиболее подходящий для реализации процедуры генерации новых столбцов, и введем их в исходное ограничение. Используя ее, получим последовательность основных таблиц 10.2-10.4 и вспомогательную таблицу 10.5, где приводятся оценки 
для векторов задачи. Решение, полученное в табл. 10.4 (цикл 2) , оказывается оптимальным, так как для него все оценки в табл. 10.5 будут положительными. В табл. 10.2 вводится 
а выводится 
Таблица 10.2 Таблица 10.3
|
|
Таблица 10.4 Таблица 10.5
В результате получили новое оптимальное решение задачи
При этом значение целевой функции равно 
Вторая итерация. Первый этап. Из последней строки табл. 10.4 находим вектор оценок
Используем это значение 
для формирования целевых функций подзадач.
Подзадача 1. Минимизировать 
при условии 
Подзадача2.Минимизировать 
при условии 
Решив эти подзадачи, получим оптимальные решения
которым отвечают следующие минимальные оценки:
и столбцы
Так как 
то необходимо перейти ко второму этапу.
Второй этап. Составим новую ограниченную координирующую задачу, которая включает базисные столбцы оптимального решения предыдущей задачи и новые столбцы:
минимизировать 
при ограничениях
Решаем эту задачу методом обратной матрицы, использовав в качестве начального базиса оптимальный базис предыдущей координирующей задачи (табл. 10.4). Результаты решения приводятся в табл. 10.6-10.8. В табл. 10.6 выводится 
, вводится 
.
Табл. 10.8 является вспомогательной. В ней приведены только оценки векторов.
Таблица 10.6 Таблица 10.7
Таблица 10.8
Итак, в результате решения координирующей задачи получено новое решение: 
. Ему соответствует следующее решение исходной задачи:
и значение ц.ф. 
.
Третья итерация. Первый этап. Вектор оценок 
имеет вид (см.табл.10.7.):
Составим подзадачи.
Подзадача 1. Минимизировать 
при следующих ограничениях: 
.
Подзадача 2. Минимизировать 
при следующих ограничениях: 
.
Решив эти задачи находим оптимальные решения:
И значения минимальных оценок векторов:
Так как они неотрицательны, то полученное на второй итерации решение 
является оптимальным.
