10.2 ДЕКОМПОЗИЦИЯ НА ОСНОВЕ РАЗДЕЛЕНИЯ переМЕННЫХ
Рассмотрим задачу ЛП, когда часть ограничений имеет блочно-диагональную структуру, а кроме связывающих ограничений имеются также и зсвязывающие переменные Y={yi}, т.е.:
максимизировать
(10.2.1)
при условиях
(10.2.2)
(10.2.3)
(10.2.4)
где 
- n0 - мерный вектор; D0 имеет размерность m×n0, а Dj - размерность mj×n0 ; j = 1, 2, ., J соответственно.
Для решения задачи (10.2.1)-(10.2.4) можно применить метод декомпозиции Данцига-Вульфа, рассмотренный ранее. Однако в этом случае получаем довольно сложный трехуровневый алгоритм (31). Поэтому возникает идея проводить итерации при фиксированных значениях связывающих переменных Y и затем, используя оптимальное решение Х, корректировать Y. Указанная процедура порождает целый класс методов декомпозиции, которые основаны на разделении переменных. При этом часто способ расчленения подсказывает сама специфика задачи, а в других случаях этот прием проводится искусственно.
Для решения задачи (10.2.1)-(10.2.4) используется общий метод релаксации ограничений (предложенный Джоффрионом), который состоит в следующем (31).
Пусть рассматривается задача математического программирования:
максимизировать
f(x) (10.2.5)
при условиях
где f(x), gk(x) - вогнутые функции от переменных 
:
Мх - выпуклое подмножество. 
.
Идея релаксации состоит в следующем. Сначала решается релаксированная задача с небольшим числом ограничений. Если эта задача не имеет решения, то неразрешима также и исходная задача. В противном случае, если полученное решение удовлетворяет всем оставшимся ограничениям, то это оптимальное решение исходной задачи. Если же какие-либо условия не выполняются, то вводится одно или несколько оставшихся ограничений и вся процедура повторяется.
Метод релаксации является особенно эффективным, если заранее известно, что в оптимальной точке существенно лишь небольшое количество ограничений.
Дадим детальное описание процедуры релаксации. Пусть М={1,2,...,m}, а К - некоторое подмножество индексов из М. Вводится так называемая К-задача:
максимизировать
f(x) (10.2.6)
при условиях
(10.2.7)
Предположим, что при начальном выборе k задача (10.2.6) имеет конечный максимум, который достигается на оптимальном решении. Процедура релаксации является итерационной и состоит из следующих шагов (этапов).
1) Сначала полагаем 
и выбираем множество k так, чтобы f(x) была ограничена при условиях (10.2.7).
2) Решаем К-задачу (10.2.6)-(10.2.7). Если она не разрешима, то, очевидно, и исходная задача не имеет решения. В противном случае имеем оптимальное решение ХК задачи (10.2.6)-(10.2.7).
3) Решение ХК проверяем на допустимость к оставшимся ограничениям. Если 
, то ХК - оптимальное решение исходной задачи (10.2.5). В противном случае переходим к следующему этапу.
Пусть S - подмножество индексов М\К, в которых имеется, по крайней мере, один индекс k такой, что для него не выполняется соответствующее ограничение для ХК. Введем подмножество индексов P из k, для которых ограничения (10.2.7) на решении ХК выполняются как строгие неравенства: 
Если выполняется условие 
, то K заменяем на 
и возвращаемся к этапу 2.
Если выполняется условие 
, то K заменяем на 
и возвращаемся к этапу 2.
Оказывается, что такая процедура релаксации после решения конечного числа задач либо приводит к оптимальному решению исходной задачи (10.2.5), либо устанавливает ее неразрешимость (52).
Вернемся теперь к блочной задаче со связывающими переменными (10.2.1)-(10.2.4) и укажем применение для нее метода релаксации. Предположим, что при каждом 
матрица А имеет ранг mj, т.е. содержит невырожденную квадратную подматрицу Aj1. Тогда ограничение (10.2.3) запишется в виде
(10.2.8)
где вектор Хj разбивается на векторы Хj1 и Хj2. В соответствии с разбиением матрицы Аj можно выбирать матрицы оптимального базиса после решения соответствующих локальных задач:
максимизировать cjxj
при условиях 
где у - заданный вектор такой, что существуют допустимые решения этих задач для всех 
.
Выражая, согласно (10.2.8), переменные xj1 через остальные, получим
(10.2.9)
Целевая функция (10.2.1) и условия (10.2.2) после разбиения хj на хj1 и хj2 запишутся в виде
(10.2.10)
при условиях
(10.2.11)
Подставляя хj1 из (10.2.9) в (10.2.10) и (10.2.11), получим сокращенную задачу:
максимизировать
(10.2.12)
при условиях
(10.2.13)
где
Задача (10.2.12), (10.2.13) имеет m ограничений и 
переменных. Ее ограничения такие же, как и в исходной задаче (10.2.1)-(10.2.4), за исключением условий, когда 
. Именно эти последние ограничения и будут релаксироваться согласно описанной процедуре.
Итак, пусть найдено оптимальное решение 
сокращенной задачи (10.2.12), (10.2.13). Тогда, подставляя его в правую часть (10.2.9), получим решение исходной задачи 
(без предположения, что 
). Очевидно, критерием оптимальности решения 
для исходной задачи (10.2.1)-(10.2.4) является выполнение неравенства 
. Если некоторые из этих ограничений не выполняются, то, согласно общей системе релаксации, они вводятся в сокращенную задачу (10.2.12) и выводятся некоторые ограничения 
.
Пусть при некотором 
первые rj компонент вектора Xj1 являются отрицательными, а вектор 
имеет gi первых положительных компонент. Перепишем для полученного оптимального решения выражение (10.2.9) в виде:
(10.2.14)
Рассмотрим два случая. В первом случае существует, по крайней мере, один ненулевой элемент подматрицы 
, образованный ее первыми rj1 строками и gj1 первыми столбцами. Обозначим соответствующие его индексы через 
и 
. Тогда с помощью линейных преобразований соотношения (10.2.14) элемент 
переводится в левую часть (10.2.14), а элемент 
окажется при этом в правой части. Указанная операция приводит к новому базису и к новой сокращенной задаче (10.2.12), (10.2.13).
Во втором случае подматрица имеет только нулевые коэффициенты и тогда невозможно осуществить смену базиса. В этом случае выбирается некоторая отрицательная компонента вектора хj1, которую обозначим через 
и вводится дополнительное условие неотрицательности вида
(10.2.15)
где 
и 
- е строки матрицы 
соответственно.
Ограничения (10.2.15) добавляются к сокращенной задаче (10.2.12), (10.2.13). Таким образом, мы приходим к последовательности сокращенных задач вида (10.2.13) с измененными матрицами Аj1 и дополнительным ограничением (10.2.15), которая решается до тех пор, пока либо не приходим к оптимальному решению исходной задачи, либо не установим ее неразрешимость.
Метод разделения переменных Бендерса
В методе Бендерса рассматривается следующая задача (20;31):
минимизировать
(10.2.16)
при условиях
(10.2.17)
(10.2.18)
где с и х - n-мерные вектор-столбцы ; y - p-мерный вектор; A(m x n) - матрица размерности m x n ; b - m-мерный вектор g - m -мерная функция, а My - некоторое множество в пространстве RP.
При каждом фиксированном y задача (10.2.16) -(10.2.18) является задачей ЛП, и потому целесообразно разделить переменные x на y. Пусть 
- подмножество значений у, при подстановке которых в (10.2.17) имеется допустимое решение задачи ЛП. Множество Ру может быть задано явно. Рассмотрим многогранный конус 
. Этот конус задается конечным числом образующих векторов (базисных) 
,так что любой элемент (вектор), принадлежащий конусу К, может быть представлен в виде
(10.2.19)
(10.2.20)
Исходная задача (10.2.16)-(10.2.18) преобразуется тогда к виду:
минимизировать
{f(y)+min cTx} (10.2.21)
при условиях
(10.2.21)
Целевая функция в (10.2.21) задается алгоритмически. Для ее нахождения при фиксированном у необходимо решить задачу ЛП:
минимизировать
cTx (10.2.23)
при условиях
(10.2.24)
Рассмотрим двойственную к ней задачу:
максимизировать
(10.2.25)
при условиях
(10.2.26)
Согласно теореме 2.2 теории двойственности для оптимальных решений значения целевых функций пары сопряженных задач (10.2.3) и (10.2.5) равны. Поэтому задача (10.2.21) преобразуется к виду:
минимизировать
(10.2.27)
при условиях
(10.2.28)
Рассмотрим множество, (10.2.28). Как видим, оно не зависит от y и потому целесообразно рассматривать задачу (10.2.27), (10.2.28) вместо задачи (10.2.21). Допустим, что множество 
, определяемое условиями (10.2.28), ограничено, и пусть 
- его крайние точки (вершины многогранника). Тогда задача (10.2.27) перепишется в виде :
минимизировать
(10.2.29)
Последняя задача эквивалентна следующей:
минимизировать
z (10.2.30)
при условиях
(10.2.31)
(10.2.32)
Однако процесс решения задачи (10.2.30)-(10.2.32) затруднен в виду огромного числа ее ограничений. Поэтому далее применяем процедуру релаксации.
Допустим, что Му - замкнутое и ограниченное множество, а функции f(y) и g(y) - выпуклы. Задача (10.2.30) сначала рассматривается на небольшом числе ограничений:
минимизировать
z (10.2.33)
при условиях
; (10.2.34)
; (10.2.35)
где 
,
- подмножества индексов.
Пусть (z0,y0)- текущее оптимальное решение задачи (10.2.33). Согласно общей процедуре релаксации оптимальное решение (z0,y0) должно быть исследовано на допустимость к отброшенным ограничениям (10.2.31) и (10.2.32). Чтобы избавится от большого перебора, вводится вспомогательная задача ЛП вида:
максимизировать
(10.2.36)
при условиях
(10.2.37)
Пусть 
- оптимальное решение (10.2.36), которое достигается на некоторой крайней точке . Тогда необходимо проверить условие
(10.2.38)
Ясно, что оно будет выполняться, если
(10.2.39)
Заметим, что второе ограничение (10.2.37) в предположении ограниченности выполняется автоматически. Таким образом, приходим к критерию оптимальности решения (z0,y0), который сводится к проверке выполнения нестрогого равенства в (10.2.39). В противном случае, когда имеет место обратное строгое неравенство
, (10.2.40)
то это соотношение (10.2.40) вводится в качестве нового ограничения в задачу (10.2.30). Дальнейшие шаги выполняются в соответствии с общей схемой релаксации.
Установим связь между методами разложения Бендерса и декомпозиции Данцига-Вульфа. Для этого рассмотрим следующую задачу ЛП (вместо (10.2.1)):
минимизировать
{cTx+dTy} (10.2.41)
при условиях
; (10.2.42)
(10.2.43)
и двойственную к ней:
максимизировать
(10.2.44)
при условиях
(10.2.45)
(10.2.46)
(10.2.47)
Если - многогранник, то задача (10.2.30)-(10.2.32) для задачи (10.2.41) будет иметь вид:
минимизировать
z (10.2.48)
при условиях
, (10.2.49)
где - крайние точки многогранника . В методе Бендерса выбирается некоторое подмножество индексов 
и критерием оптимальности (z0,y0) является выполнение равенства
(10.2.50)
при условиях
Будем решать задачу (10.2.44)-(10.2.47) методом Данцига-Вульфа. Любая точка многогранника , задаваемого условиями (10.2.46), (10.2.47), представима в виде выпуклой комбинации крайних точек:
. (10.2.51)
Подстановка этого выражения в целевую функцию (10.2.44) и ограничение (10.2.45) приводят к следующей координирующей задаче:
максимизировать
(10.2.52)
при условиях
(10.2.53)
. (10.2.54)
Двойственная к координирующей задаче имеет вид:
минимизировать
dTy+W (10.2.55)
при условиях
(10.2.56)
Сделав замену z = dTy + W, приходим к задаче:
минимизировать
z (10.2.57)
при условиях
(10.2.58)
Как видим, задачу (10.2.57), (10.2.58) в точности совпадает с задачей Бендерса (10.2.48), (10.2.49).
В методе Данцига-Вульфа рассматривается локальная подзадача:
максимизировать
(10.2.59)
при условиях
где {y0} - оптимальные двойственные переменные, соответствующие сокращенной координирующей задачи (10.2.57) и замене переменных.
Критерий оптимальности в методе Данцига-Вульфа записывается в виде:
при условиях
что совпадает с критерием оптимальности в методе Бендерса (10.2.39).
Таким образом, методы Бендерса и Данцига-Вульфа являются двойственными друг к другу. Однако метод Бендерса применим к более широкому классу задач математического программирования, например к задачам частично-целочисленного и нелинейного программирования.
