Разложение Данцига — Вулфа

Метод декомпозиции Данцига — Вулфа представляет собой специализированный вариант симплекс-метода.

В 1960 г. Джордж Данциг и Филип Вулф^[англ.] разработали метод декомпозиции для решения задач высокой размерности со специальной структурой матрицы ограничений^[1].

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

Отличительной особенностью метода декомпозиции является использование координирующей задачи, которая имеет, по сравнению с исходной, небольшое число строк и большое число столбцов.

Метод генерации столбцов

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

Достаточно уметь генерировать столбец и иметь процедуру, выбирающую столбец для ввода в базис.

Часто такая процедура сводится к решению определенной подзадачи (не обязательно линейного программирования).

Принцип декомпозиции

Лемма Пусть ${\displaystyle R}$ - непустое замкнутое ограниченное множество в евклидовом пространстве и обладает конечным числом ${\displaystyle K}$ крайних точек, которые здесь будут обозначаться ${\displaystyle z_{k=1:K}}$. Тогда любая точка ${\displaystyle z}$ множества ${\displaystyle R}$ может быть представлена в виде выпуклой комбинации крайних точек множества R, т.е. для ${\displaystyle z}$ найдутся неотрицательные числа ${\displaystyle \delta _{k}}$ с общей суммой единица (${\displaystyle \sum _{k=1}^{K}\delta _{m}=1}$) и такие, что

(1) ${\displaystyle z=\sum _{k=1}^{K}\delta _{k}z_{k}}$.

Пусть поставлена задача

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

(2) ${\displaystyle c[N]x[N]}$

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

(3) ${\displaystyle A[M_{1},N]x[N]=b[M_{1}]}$

(4) ${\displaystyle A[M_{2},N]x[N]=b[M_{2}]}$

(5) ${\displaystyle x[N]\geq 0[N]}$

Ограничения (3) задают симплекс S, пусть ${\displaystyle z[K]}$ - его крайние точки.

Пусть x – допустимое решение По лемме ${\displaystyle x=z[N,K]\cdot \delta [K]}$

Подставим последнее выражение в (2) и (3).

Задача примет вид

Максимизировать (6) ${\displaystyle (c[N]\cdot z[N,K])\cdot \delta [K]=g[K]\cdot \delta [K]}$

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

(7) ${\displaystyle (A[M_{1},N]\cdot z[N,K])\cdot \delta [K]=D[M_{1},K]\cdot \delta [K]=b[M_{1}]}$

(8) ${\displaystyle \delta [K]\cdot 1[K]=1}$.

Эта задача эквивалентна исходной (2)-(5) и называется координирующей задачей.

Она имеет только ${\displaystyle |M_{1}|+1}$ строк ограничений по сравнению с ${\displaystyle |M_{1}|+|M_{2}|}$ строками исходной задачи, и очень большое число столбцов ${\displaystyle |K|}$, равное числу крайних точек множества ${\displaystyle S}$. Чтобы не хранить все эти столбцы в памяти ЭВМ, будем получать их по мере необходимости, пользуясь методом генерации столбцов.

Алгоритм

Решаем задачу (6)-(8) симплекс-методом с использованием метода генерации столбцов.

Для простоты предположим, что уже известно некоторое допустимое базисное решение.

Обозначим через ${\displaystyle \delta }$ ограничение (8), тогда двойственные переменные - это вектор ${\displaystyle d[M_{1}\cup {\delta }]}$.

Для ввода в базис необходимо найти ${\displaystyle z[N,m]}$, такой, что

${\displaystyle d[M_{1}]D[M_{1},K]+d[\delta ]<g[m]}$

Таким образом достаточно найти m, на котором достигается минимум

(9) ${\displaystyle d[M_{1}]A[M_{1},N]\cdot z[N,m]+d[\delta ]-c[N]z[N,m]}$

что эквивалентно решению задачи

минимизировать (10) ${\displaystyle (d[M_{1}]A[M_{1},N]-c[N])\cdot x[N])}$

при ограничениях (4) и (5).

Если найденный минимум не будет больше ${\displaystyle -d[\delta ]}$, задача решена.

В противном случае столбец ${\displaystyle D[M_{1},k]}$, соответствующий найденному решению, вводим в базис.

Блочные задачи

Пусть ограничения (4) имеют блочную структуру

${\displaystyle {\begin{pmatrix}A[M_{1},N_{1}]&0[M_{1},N_{2}]&\cdots &0[M_{1},N_{n}]\\0[M_{2},N_{1}]&A[M_{2},N_{2}]&\cdots &0[M_{2},N_{n}]\\\cdots &\cdots &\cdots &\cdots &\\0[M_{n},N_{1}]&0[M_{n},N_{2}]&\cdots &A[M_{n},N_{n}]\\\end{pmatrix}}}$

Задача (10),(4),(5) распадается на отдельные подзадачи

Найти минимум

(11) ${\displaystyle (d[M_{k}]A[M_{k},N_{k}]-c[N_{k}])z[N_{k}]+d[\delta ]}$

при условиях

(12) ${\displaystyle A[M_{k},N_{k}]z[N_{k}]=b[M_{k}]}$