10.3 ДЕКОМПОЗИЦИЯ Корнаи-Липтака
Пусть имеется задача ЛП вида:
максимизировать
cTx (10.3.1)
при условиях
(10.3.2)
(10.3.3)
где
cT=[c1,c2,.,cn]; xT=[x1,x2,.,xn]; bT0=[b1,b2,.,bm]
Рассмотрим подход к ее решению, использующий метод декомпозиции Корнаи-Липтака (20; 31).
Разобьем матрицу А0 на подматрицы 
, где при каждом 
матрица 
имеет размерность m x nj. Тогда соответственно разбиваем вектор с на подвектора с1, с2, ., сj, ., с и х - на подвектора х1, х2, ., хjn, где cj, xj - вектора, имеющие размерность 
, тогда задача (10.3.1)-(10.3.3) преобразуется к виду
максимизировать
(10.3.4)
при условиях
(10.3.5)
(10.3.6)
Введем m-мерные вектора-столбцы уі, удовлетворяющие условию
(10.3.7)
Сформулируем J задач ЛП:
максимизировать
(10.3.8)
при условиях
(10.3.9)
(10.3.10)
Рассмотрим вектор y = [y1, y2, ., yJ]. Обозначим через Му множество всех векторов у таких, что выполняется условие (10.3.7) и задачи (10.3.8)-(10.3.10) имеют решения. Оптимальные значения функционалов задач (10.3.8)-(10.3.10) зависят от уj, как от параметров. Указанную зависимость представим в виде fj(yj). Обозначим 
. Тогда задача (10.3.8)-(10.3.10) сводится к следующей координирующей задаче:
Максимизировать
F(y) (10.3.11)
при ограничениях
(10.3.12)
Если разложение матрицы А0 интерпретируется как разбиение системы на J подсистем, а вектор b0 рассматривается как общий ресурс системы, то задача (10.3.11),(10.3.12) заключается в нахождении оптимального распределения общего ресурса. Заметим, что здесь не вводится ограничения на знак величины yj (это означает, что система может как потреблять(+), так и производить ресурсы (-)). Рассмотрим задачу (10.3.11), (10.3.12). Ее анализ усложняется, поскольку функция F(y) аналитически не известна, а задана лишь алгоритмически. Для ее вычисления необходимо решить задачу ЛП (10.3.8)-(10.3.10).
Применение той или иной схемы максимизации функции F(y) порождает соответствующий метод разложения на основе принципа Корнаи-Липтака. Так, в работе Корнаи-Липтака предлагалось сведение этой задачи к минимаксной, далее решаемой методами теории игр. Рассмотрим этот подход.
Запишем двойственные задачи к задаче (10.3.8)-(10.3.10):
минимизировать 
(10.3.13)
при ограничениях
(10.3.14)
, (10.3.15)
где вектор-столбец 
имеет m компонент 
.
Пусть через 
обозначены выпуклые многогранники в пространстве Rm, задаваемые условиями (10.3.14), (10.3.15). Введем вектор 
с компонентами 
и множество 
. В соответствии с основной теоремой двойственности справедливо
. (10.3.16)
Таким образом,
(10.3.17)
и окончательно задача (10.3.11), (10.3.12) сводится к отысканию седловой точки:
найти
(10.3.18)
где 
-фиксированы,
и 
.
Задачу (10.3.18) можно решать методом матричных игр для фиктивной игры Брауна.
Указанный метод представляет собой итеративный процесс, где каждая итерация в терминах теории игр представляет собой определенную партию игры и соответствует выбору некоторых стратегий двух игроков. Эти стратегии в данной задаче являются векторами 
и y. Стратегии каждого игрока берутся наиболее выгодными с учетом ответа его противника.
Оптимальные стратегии для задачи (10.3.18) определяются в виде:
(10.3.19)
. (10.3.20)
Итеративный процесс, согласно методу Брауна, состоит из следующих шагов (52).
Начальная итерация (k=1).
Выбирается произвольная стратегия 
;
Полагаем 
Определяем 
согласно (10.3.19)
Полагаем 
Пусть уже проведено (k-1) итераций, в результате которых определены 
и 
.
k -ая итерация.
Определяем 
согласно (10.3.20);
Вычисляем 
;
Определяем 
согласно (10.3.19);
Вычисляем 
.
В силу теоремы Робинсона о сходимости метода Брауна последовательность 
при 
сходится к седловой точке задачи (10.3.18).
Метод разложения Корнаи-Липтака наиболее эффективен в случае, когда часть ограничений имеет блочно-диагональную структуру.
Введем в задачу (10.3.1)-(10.3.2) дополнительные блочные ограничения:
максимизировать 
(10.3.21)
при ограничениях
(10.3.22)
, (10.3.23)
где bj - mj -мерный вектор-столбец, а матрица Aj имеет размерность
mj x nj.
Составим функцию Лагранжа для задачи (10.3.8)-(10.3.10):
, (10.3.24)
где
.
Выберем достаточно большие границы изменения переменных и 
:
.
Можно показать, что задача (10.3.11), (10.3.12) в случае (10.3.21)-(10.3.24) сводится к игре двух лиц со стратегиями 
где
и функционал 
имеет вид
.
Окончательно мы приходим к задаче о нахождении седловой точки функции
.
Эта задача решается методом фиктивной игры Брауна. Тогда первый игрок (минимизирующий функционал) на каждом шаге итеративного процесса решает задачу:
минимизировать 
при ограничениях
где уі - фиксированы.
Заметим, что описанная задача решается отдельно по каждому виду s-го ресурса (
) , поэтому первый игрок может быть представлен как m независимых игроков.
При этом первого игрока можно интерпретировать как центр, который распределяет общие ресурсы, и большие ресурсы посылаются той подсистеме, где ценность их в терминах величин является большей. Второй игрок (максимизирующий функционал), в процессе итераций решает задачу о нахождении оптимальных значений двойственной переменных, соответствующих первой группе ограничений задач:
максимизировать 
(10.3.25)
при ограничениях
(10.3.26)
(10.3.27)
где уі - фиксированы.
Второй игрок рассматривается, как J независимых игроков (подсистем). Таким образом, метод Корнаи-Липтака осуществляет декомпозицию на (j+m) подзадач.
Поскольку итеративный процесс Брауна для матричных игр обладает очень медленной сходимостью, то для максимизации функций (10.3.25) целесообразно применить метод возможных направлений Зойтендейка (см.гл.6).
Рассмотрим задачу (10.3.11), когда исходная задача имеет вид (10.3.21)-(10.3.23).
Можно показать [52], что функции 
являются вогнутыми и кусочно-линейными, а точки излома функций соответствуют смене базиса в задачах (10.3.25)-(10.3.27).
Применим схему возможных направлений Зойтендейка для данной задачи в простейшем случае, когда некоторым заданным величинам 
соответствуют единственные оптимальные двойственные переменные 
.
Согласно основной теореме двойственности имеем:
, (10.3.28)
Следующие значения величин yj(yj0) задаются в методе Зойтендейка в виде
, (10.3.29)
где zj - m-меримый вектор возможных направлений, удовлетворяющий условию нормировки, например вида
,
где 
- параметр, определяющий величину шага (
).
Подставляя (10.3.29) в (10.3.11) с учетом (10.3.28) приходим к следующей задаче ЛП относительно неизвестных возможных направлений:
максимизировать
(10.3.30)
при ограничениях
(10.3.31)
(10.3.32)
Задача (10.3.30)-(10.3.32) распадается на m независимых подзадач. Пусть для любого s имеют место равенства :
Тогда оптимальное решение (10.3.30)-(10.3.32) имеет вид
(10.3.33)
Полученное правило (10.3.33) имеет очень простую экономическую интерпретацию: свободный ресурс отбирается у той подсистемы, для которой он наименее цен, и передается той подсистеме, для которой он наиболее цен.
При этом параметр , определяющий длину шага по данному направлению, находится в виде 
где 
- максимальное значение , удовлетворяющее ограничению
где -
максимальное значение , при котором сохраняются все исходные базисы в задачах (10.3.25), (10.3.26), а 
определяется максимизацией функции 
при ограничениях
.
Пример 10.2. Рассмотрим задачу:
минимизировать x1-2x2-3x3+x4 (1)
при ограничениях
Локальные параметрические задачи имеют вид:
минимизировать f1=x1-2x2 (2)
при ограничениях
Минимизировать
f2= -3x3+x4 (3)
при ограничениях
Задачи (1), (2) легко решаются графически. В результате получим
Координирующая задача имеет следующий вид:
минимизировать 
при ограничениях
.
Ее решение 
, откуда получим
.
Этот решение совпадает с оптимальным решением, полученным симплекс-методом.
Пример 10.3. Рассмотрим задачу:
максимизировать 
(1)
при ограничениях
Локальные задачи записываются в виде:
максимизировать 
(2)
при ограничениях
максимизировать 
(3)
при ограничениях
Для задачи (2) применим метод множителей Лагранжа. Функция Лагранжа:
Для задачи (3) получим
Координирующая задача имеет вид :
максимизировать 
при ограничениях
Ее решение 
. Оно определяет оптимальное решение исходной задачи
