10.2 ДЕКОМПОЗИЦИЯ НА ОСНОВЕ РАЗДЕЛЕНИЯ переМЕННЫХ

Рассмотрим задачу ЛП, когда часть ограничений имеет блочно-диагональную структуру, а кроме связывающих ограничений имеются также и зсвязывающие переменные Y={y_i}, т.е.:

максимизировать

                                (10.2.1)

при условиях

                            (10.2.2)

                      (10.2.3)

                       (10.2.4)

где  - n₀ – мерный вектор; D₀ имеет размерность m×n₀, а D_j - размерность m_j×n₀ ; 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), g_k(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) и укажем применение для нее метода релаксации. Предположим, что при каждом матрица А имеет ранг m_j, т.е. содержит невырожденную квадратную подматрицу A_j1. Тогда ограничение (10.2.3) запишется в виде

                   (10.2.8)

где вектор Х_j разбивается на векторы Х_j1 и Х_j2. В соответствии с разбиением матрицы А_j можно выбирать матрицы оптимального базиса после решения соответствующих локальных задач:

максимизировать                                     c_jx_j

при условиях                      

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

Выражая, согласно (10.2.8), переменные x_j1 через остальные, получим

                          (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) и выводятся некоторые ограничения .

Пусть при некотором  первые r_j компонент вектора X_j1 являются отрицательными, а вектор  имеет g_i первых положительных компонент. Перепишем для полученного оптимального решения выражение (10.2.9) в виде:

               (10.2.14)

Рассмотрим два случая. В первом случае существует, по крайней мере, один ненулевой элемент подматрицы , образованный ее первыми r_j1 строками и g_j1 первыми столбцами. Обозначим соответствующие его  индексы через  и . Тогда с помощью линейных преобразований соотношения (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 -мерная функция, а M_y – некоторое множество в пространстве R^P.

При каждом фиксированном 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 c^Tx}                           (10.2.21)

при условиях

                     (10.2.21)

Целевая функция в (10.2.21) задается алгоритмически. Для ее нахождения при фиксированном у необходимо решить задачу ЛП:

минимизировать

 c^Tx                                       (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)

где , - подмножества индексов.

Пусть (z⁰,y⁰)– текущее оптимальное решение задачи (10.2.33). Согласно общей процедуре релаксации оптимальное решение (z⁰,y⁰) должно быть исследовано на допустимость к отброшенным ограничениям (10.2.31) и (10.2.32). Чтобы избавится от большого перебора, вводится вспомогательная задача ЛП вида:

максимизировать

                                    (10.2.36)

при условиях

                      (10.2.37)

Пусть - оптимальное решение (10.2.36), которое достигается на некоторой крайней точке . Тогда необходимо проверить условие

               (10.2.38)

Ясно, что оно будет выполняться, если

                 (10.2.39)

Заметим, что второе ограничение (10.2.37) в предположении ограниченности  выполняется автоматически. Таким образом, приходим к критерию оптимальности решения (z⁰,y⁰), который сводится к проверке выполнения нестрогого равенства в (10.2.39). В противном случае, когда имеет место обратное строгое неравенство

 ,                    (10.2.40)

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

Установим связь между методами разложения Бендерса и декомпозиции Данцига-Вульфа. Для этого рассмотрим следующую задачу ЛП (вместо (10.2.1)):

минимизировать

{c^Tx+d^Ty}                                  (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)

где  - крайние точки многогранника . В методе Бендерса выбирается некоторое подмножество индексов  и критерием оптимальности (z⁰,y⁰) является выполнение равенства

               (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)

Двойственная к координирующей задаче имеет вид:

минимизировать

 d^Ty+W                                      (10.2.55)

при условиях

               (10.2.56)

Сделав замену z = d^Ty + W, приходим к задаче:

минимизировать

 z                                          (10.2.57)

при условиях

               (10.2.58)

Как видим, задачу (10.2.57), (10.2.58) в точности совпадает с задачей Бендерса (10.2.48), (10.2.49).

В методе Данцига-Вульфа рассматривается локальная подзадача:

максимизировать

                                 (10.2.59)

при условиях

 

где {y₀} – оптимальные двойственные переменные, соответствующие сокращенной координирующей задачи (10.2.57) и замене переменных.

Критерий оптимальности в методе Данцига-Вульфа записывается в виде:

при условиях

что совпадает с критерием оптимальности в методе Бендерса (10.2.39).

Таким образом, методы Бендерса и Данцига-Вульфа являются двойственными друг к другу. Однако метод Бендерса применим к более широкому классу задач математического программирования, например к задачам частично-целочисленного и нелинейного программирования.